# Lifting ℓ1-optimization strong and sectional thresholds

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

## Key facts

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

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

- [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [Fixed width treelike neural networks capacity analysis -- generic activations](https://mlsanity.com/paper/2402.05696/) (2024)
- [Injectivity capacity of ReLU gates](https://mlsanity.com/paper/2410.20646/) (2024)
- [Lifted RDT based capacity analysis of the 1-hidden layer treelike sign perceptrons neural networks](https://mlsanity.com/paper/2312.08257/) (2023)
- [Deep ReLU networks -- injectivity capacity upper bounds](https://mlsanity.com/paper/2412.19677/) (2024)
- [Capacity of the Hebbian-Hopfield network associative memory](https://mlsanity.com/paper/2403.01907/) (2024)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Theoretical limits of descending ℓ0 sparse-regression ML algorithms](https://mlsanity.com/paper/2410.07651/) (2024)
- [Phase transition of descending phase retrieval algorithms](https://mlsanity.com/paper/2506.18275/) (2025)
- [Phase retrieval with rank d measurements -- descending algorithms phase transitions](https://mlsanity.com/paper/2506.18282/) (2025)
- [A large deviation view of stationarized fully lifted blirp interpolation](https://mlsanity.com/paper/2506.19273/) (2025)

## Abstract (arXiv)

In this paper we revisit under-determined linear systems of equations with sparse solutions. As is well known, these systems are among core mathematical problems of a very popular compressed sensing field. The popularity of the field as well as a substantial academic interest in linear systems with sparse solutions are in a significant part due to seminal results citeCRT,DonohoPol. Namely, working in a statistical scenario, citeCRT,DonohoPol provided substantial mathematical progress in characterizing relation between the dimensions of the systems and the sparsity of unknown vectors recoverable through a particular polynomial technique called ℓ1-minimization. In our own series of work citeStojnicCSetam09,StojnicUpper10,StojnicEquiv10 we also provided a collection of mathematical results related to these problems. While, Donoho's work citeDonohoPol,DonohoUnsigned established (and our own work citeStojnicCSetam09,StojnicUpper10,StojnicEquiv10 reaffirmed) the typical or the so-called weak threshold behavior of ℓ1-minimization many important questions remain unanswered. Among the most important ones are those that relate to non-typical or the so-called strong threshold behavior. These questions are usually combinatorial in nature and known techniques come up short of providing the exact answers. In this paper we provide a powerful mechanism that that can be used to attack the "tough" scenario, i.e. the strong threshold (and its a similar form called sectional threshold) of ℓ1-minimization.