Stability and robustness of l(1)-minimizations with Weibull matrices and redundant dictionaries Academic Article uri icon


  • We investigate the recovery of almost s-sparse vectors x N from undersampled and inaccurate data y=Ax+e m by means of minimizing z1 subject to the equality constraints Az=y. If m = sln(N/s) and if Gaussian random matrices A mN are used, this equality-constrained 1-minimization is known to be stable with respect to sparsity defects and robust with respect to measurement errors. If m = sln(N/s) and if Weibull random matrices are used, we prove here that the equality-constrained 1-minimization remains stable and robust. The arguments are based on two key ingredients, namely the robust null space property and the quotient property. The robust null space property relies on a variant of the classical restricted isometry property where the inner norm is replaced by the 1-norm and the outer norm is replaced by a norm comparable to the 2-norm. For the 1-minimization subject to inequality constraints, this yields stability and robustness results that are also valid when considering sparsity relative to a redundant dictionary. As for the quotient property, it relies on lower estimates for the tail probability of sums of independent Weibull random variables. 2012 Elsevier Inc. All rights reserved.

published proceedings


author list (cited authors)

  • Foucart, S.

citation count

  • 51

complete list of authors

  • Foucart, Simon

publication date

  • January 2014