Stability and robustness of l(1)-minimizations with Weibull matrices and redundant dictionaries
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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.
