# Theoretical limits of descending ℓ0 sparse-regression ML algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 94 references that are in the map.
- First posted on arXiv 10 Oct 2024.

## Builds on (most cited first, 12 of 12)

- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Regularly random duality](https://mlsanity.com/paper/1303.7295/) (2013)
- [Another look at the Gardner problem](https://mlsanity.com/paper/1306.3979/) (2013)
- [Fully lifted random duality theory](https://mlsanity.com/paper/2312.00070/) (2023)
- [Upper-bounding ℓ1-optimization weak thresholds](https://mlsanity.com/paper/1303.7289/) (2013)
- [Lifting ℓ1-optimization strong and sectional thresholds](https://mlsanity.com/paper/1306.3770/) (2013)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Approximate Survey Propagation for Statistical Inference](https://mlsanity.com/paper/1807.01296/) (2018)
- [A performance analysis framework for SOCP algorithms in noisy compressed sensing](https://mlsanity.com/paper/1304.0002/) (2013)
- [Generalized Approximate Survey Propagation for High-Dimensional Estimation](https://mlsanity.com/paper/1905.05313/) (2019)
- [Random linear systems with sparse solutions -- finite dimensions](https://mlsanity.com/paper/1612.06344/) (2016)

## Abstract (arXiv)

We study the theoretical limits of the ℓ0 (quasi) norm based optimization algorithms when employed for solving classical compressed sensing or sparse regression problems. Considering standard contexts with deterministic signals and statistical systems, we utilize Fully lifted random duality theory (Fl RDT) and develop a generic analytical program for studying performance of the maximum-likelihood (ML) decoding. The key ML performance parameter, the residual root mean square error (RMSE), is uncovered to exhibit the so-called phase-transition (PT) phenomenon. The associated aPT curve, which separates the regions of systems dimensions where an ℓ0 based algorithm succeeds or fails in achieving small (comparable to the noise) ML optimal RMSE is precisely determined as well. In parallel, we uncover the existence of another dPT curve which does the same separation but for practically feasible descending ℓ0 (dℓ0) algorithms. Concrete implementation and practical relevance of the Fl RDT typically rely on the ability to conduct a sizeable set of the underlying numerical evaluations which reveal that for the ML decoding the Fl RDT converges astonishingly fast with corrections in the estimated quantities not exceeding ~ 0.1% already on the third level of lifting. Analytical results are supplemented by a sizeable set of numerical experiments where we implement a simple variant of dℓ0 and demonstrate that its practical performance very accurately matches the theoretical predictions. Completely surprisingly, a remarkably precise agreement between the simulations and the theory is observed for fairly small dimensions of the order of 100.