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 (3)

• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

Cited by in corpus (1)

• A framework to characterize performance of LASSO algorithms