Robustness to Unknown Error in Sparse Regularization

DOI10.1109/TIT.2017.2788445MaRDI QIDQ4682942zbMATH OpenOpenAlexFDO

Authors Simone Brugiapaglia, Ben Adcock

Publication date 19 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.10299

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Quadratically-constrained basis pursuit has become a popular device in sparse regularization; in particular, in the context of compressed sensing. However, the majority of theoretical error estimates for this regularizer assume an a priori bound on the noise level, which is usually lacking in practice. In this paper, we develop stability and robustness estimates which remove this assumption. First, we introduce an abstract framework and show that robust instance optimality of any decoder in the noise-aware setting implies stability and robustness in the noise-blind setting. This is based on certain sup-inf constants referred to as quotients, strictly related to the quotient property of compressed sensing. We then apply this theory to prove the robustness of quadratically-constrained basis pursuit under unknown error in the cases of random Gaussian matrices and of random matrices with heavy-tailed rows, such as random sampling matrices from bounded orthonormal systems. We illustrate our results in several cases of practical importance, including subsampled Fourier measurements and recovery of sparse polynomial expansions.

Cited in

(13)

• Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling
• On the robustness of minimum norm interpolators and regularized empirical risk minimizers
• On the robustness of noise-blind low-rank recovery from rank-one measurements
• Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements
• Correcting for unknown errors in sparse high-dimensional function approximation
• Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
• NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems
• Least sparsity of \(p\)-norm based optimization problems with \(p>1\)
• Robustness in sparse high-dimensional linear models: relative efficiency and robust approximate message passing
• On the geometry of polytopes generated by heavy-tailed random vectors
• Robust recovery of a kind of weighted l1-minimization without noise level
• A mixed ℓ₁ regularization approach for sparse simultaneous approximation of parameterized PDEs
• Robust sparse recovery with sparse Bernoulli matrices via expanders

This page was built for publication: Robustness to Unknown Error in Sparse Regularization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4682942)