Upper-bounding ${\ell }_1$-optimization weak thresholds

Abstract

In our recent work \cite{StojnicCSetam09} we considered solving under-determined systems of linear equations with sparse solutions. In a large dimensional and statistical context we proved that if the number of equations in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that a polynomial ${\ell }_1$-optimization technique succeeds in solving the system. We provided lower bounds on the proportionality constants that are in a solid numerical agreement with what one can observe through numerical experiments. Here we create a mechanism that can be used to derive the upper bounds on the proportionality constants. Moreover, the upper bounds obtained through such a mechanism match the lower bounds from \cite{StojnicCSetam09} and ultimately make the latter ones optimal.

arXiv admin note: text overlap with arXiv:0907.3666

References in corpus (7)

• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• On Verifiable Sufficient Conditions for Sparse Signal Recovery via ${\ell }_1$ Minimization
• On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

Cited by in corpus (5)

• A framework to characterize performance of LASSO algorithms
• The Gaussian min-max theorem in the Presence of Convexity
• Precise Error Analysis of Regularized M-estimators in High-dimensions
• Universality in Learning from Linear Measurements
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective