# Upper-bounding ℓ1-optimization weak thresholds

arXiv: https://arxiv.org/abs/1303.7289 · HTML: https://mlsanity.com/paper/1303.7289/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2013.

## Built on by (most cited first, 14 of 14)

- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Asymptotics of feature learning in two-layer networks after one gradient-step](https://mlsanity.com/paper/2402.04980/) (2024)
- [A phase transition between positional and semantic learning in a solvable model of dot-product attention](https://mlsanity.com/paper/2402.03902/) (2024)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [Fixed width treelike neural networks capacity analysis -- generic activations](https://mlsanity.com/paper/2402.05696/) (2024)
- [High-Dimensional Statistics: Reflections on Progress and Open Problems](https://mlsanity.com/paper/2605.05076/) (2026)
- [Asymptotic Dynamics of Alternating Minimization for Bilinear Regression](https://mlsanity.com/paper/2402.04751/) (2024)
- [Causal Inference (C-inf) -- closed form worst case typical phase transitions](https://mlsanity.com/paper/2301.00793/) (2023)
- [Causal Inference (C-inf) -- asymmetric scenario of typical phase transitions](https://mlsanity.com/paper/2301.00801/) (2023)
- [Ridge interpolators in correlated factor regression models -- exact risk analysis](https://mlsanity.com/paper/2406.09183/) (2024)
- [Precise analysis of ridge interpolators under heavy correlations -- a Random Duality Theory view](https://mlsanity.com/paper/2406.09199/) (2024)
- [Theoretical limits of descending ℓ0 sparse-regression ML algorithms](https://mlsanity.com/paper/2410.07651/) (2024)
- [A large deviation view of stationarized fully lifted blirp interpolation](https://mlsanity.com/paper/2506.19273/) (2025)

## Abstract (arXiv)

In our recent work citeStojnicCSetam09 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 ℓ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 citeStojnicCSetam09 and ultimately make the latter ones optimal.