Robustness to unknown error in sparse regularization

Simone Brugiapaglia, Rick Archibald and I have been investigating the robustness of constrained l1-minimization regularization to unknown measurement errors.  The vast majority of existing theory for such problems requires an a priori bound on the noise level.  Yet in many, if not most, real-world applications such a bound is unknown.  Our work provides the first recovery guarantees for a large class of practical measurement matrices, thereby extending existing results for subgaussian random matrices.  Besides this, our work sheds new light on sparse regularization in practice, addressing questions about the relationship between model fidelity, noise parameter estimation and reconstruction error.

Simone will be presenting this work at SPARS2017 and SampTA 2017.  In the meantime our conference paper is available here:

Recovery guarantees for compressed sensing with unknown errors

Approximating high-dimensional functions via compressed sensing

Simone Brugiapaglia, Clayton Webster and I have written a chapter that surveys recent trends in high-dimensional approximation using the theory and techniques of compressed sensing:

Polynomial approximation of high-dimensional functions via compressed sensing

In it we demonstrate how the structured sparsity of polynomial coefficients of high-dimensional functions can be exploited via weighted l1 minimization techniques.  This yields approximation algorithms whose sample complexities are essentially independent of the dimension d.  Hence the curse of dimensionality is mitigated to a significant extent.

Frames and numerical approximation

Frames of Hilbert spaces are ubiquitous in image and signal processing, coding theory and sampling theory.  However, they are far less widely known in numerical analysis.

In a new paper with Daan Huybrechs, we take a look at frames from a numerical analyst’s perspective:

Frames and numerical approximation

First, we point out that frames can be useful tools in numerical analysis where orthonormal bases may be difficult or impossible to construct.  Second, we investigate issues concerning stability and accuracy in frame approximations.  Our main result is that frame approximations are stable and accurate, provide the function being approximated has representations in the frame with small-norm coefficients.

One application of this work is meshfree approximation of functions on complex geometries using so-called Fourier extensions.  Daan maintains a GitHub page with fast algorithms for computing such approximations.


Impossibility theorems for stable approximation

Alexei Shadrin, Rodrigo Platte and I have just finished a paper on stability and instability in approximating analytic functions from nonequispaced points:

Optimal sampling rates for approximating analytic functions from pointwise samples

In it, we generalize Rodrigo’s previous work (with Arno Kuijlaars and Nick Trefethen) from equispaced nodes to arbitrary nonequispaced nodes.  In particular, our result quantifies the tradeoff between convergence rates and ill-conditioning for nodes distributed according to modified Jacobi weight functions.  We also determine a necessary and sufficient sampling rate for stable approximation with polynomial least-squares fitting.

Sparsity and parallel acquisition: improved recovery guarantees

My postdoc Il Yong Chun, visiting student Chen Li and I have developed some new and improved recovery guarantees for parallel acquisition systems.  These are described in two submitted conference papers:

Optimal sparse recovery for multi-sensor measurements

Sparsity and parallel acquisition: optimal uniform and nonuniform recovery guarantees

These new results build on a previous paper of ours which introduced a compressed sensing framework for multi-sensor systems – see this past news item.  The new results explain the practical recovery capabilities of a much broader class of sensing scenarios.

Compressed sensing in multi-sensor architectures

My postdoc Il Yong Chun and I recently completed a new paper titled Compressed sensing and parallel acquisition.  In it we present a theoretical framework for the use of compressed sensing in multi-sensor systems.  These systems are found numerous applications, ranging from parallel MRI, to multi-view imaging and generalized sampling theory.  Our work provides a first mathematical analysis of the gains offered by parallel acquisition and compressed sensing, and presents new insight into questions of optimal sensor design.