Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0

By Simon Foucart, Ming-Jun Lai. 2009

757 citations recorded by the source corpus.

Abstract We present a condition on the matrix of an underdetermined linear system which guarantees that the solution of the system with minimal l q -quasinorm is also the sparsest one. This generalizes, and slightly improves, a similar result for the l 1 -norm. We then introduce a simple numerical scheme to compute solutions with minimal l q -quasinorm, and we study its convergence. Finally, we display the results of some experiments which indicate that the l q -method performs better than other available methods.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/6d3a09d61e8350a9970ce70b7ced5bceea12b2c4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

A Probabilistic and RIPless Theory of Compressed Sensing (2010, background): “[23], it is known that the error bound (1.”
Non-convex Optimization for Machine Learning (2017, methodology): “A popular approach in this direction uses Lq regularization with 0 q 1 [Chartrand, 2007, Foucart and Lai, 2009, Wang et al., 2011].”
L1−2 minimization for exact and stable seismic attenuation compensation (2018, background): “They include Lp (Chartrand 2007; Foucart & Lai 2009; Lai et al. 2013; Woodworth & Chartrand 2016), log-sum penalty (LSP, Candes et al. 2008), truncated L1 (Wang & Yin 2010; Hu et al. 2013), capped L1 minimization (Zhang 2010b) and minimax concave penalty (Zhang 2010a).”
Improved bounds on Restricted isometry for compressed sensing (2013, background): “Key Words and Phrases: Compressed sensing, Restricted isometry constants, Restricted isometry property, Sparse approximation, Sparse signal recovery.”
Modified-CS: Modifying compressive sensing for problems with partially known support (2009, background): “For CS, two of the best (weakest) sufficient conditions that use only ’s are given in [22], [ 23 ], and [11].”
Collaborative Sparse Regression for Hyperspectral Unmixing (2014, background): “The mutual coherence is also related to the restricted isometric properties (RIP) of the libraries [18] (see also [15], [19] and the variant proposed in [20]), which establish sufficient conditions under which the unmixing solutions can be exactly recovered through linear programming techniques.”
Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance (2010, result): “As in [19], we here state this results in terms of a quantity that is related to the restricted isometry property, but is scale-invariant.”
Sparse Unmixing of Hyperspectral Data (2011, methodology): “As in (P δ 0 ), the stability of the solution of problem (P δ 1 ) has also been provided [28], [ 35 ].”