# Fundamental limits and algorithms for sparse linear regression with sublinear sparsity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 45 references that are in the map.
- First posted on arXiv 27 Jan 2021.

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

- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [From Denoising to Compressed Sensing](https://mlsanity.com/paper/1406.4175/) (2014)
- [Learned D-AMP: Principled Neural Network based Compressive Image Recovery](https://mlsanity.com/paper/1704.06625/) (2017)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [Generalization Error of Generalized Linear Models in High Dimensions](https://mlsanity.com/paper/2005.00180/) (2020)
- [Phase transitions and sample complexity in Bayes-optimal matrix factorization](https://mlsanity.com/paper/1402.1298/) (2014)
- [Inference with Deep Generative Priors in High Dimensions](https://mlsanity.com/paper/1911.03409/) (2019)
- [All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation](https://mlsanity.com/paper/2006.07971/) (2020)
- [Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding](https://mlsanity.com/paper/1501.05892/) (2015)
- [Conditional Sparse Linear Regression](https://mlsanity.com/paper/1608.05152/) (2016)
- [Asymptotics of MAP Inference in Deep Networks](https://mlsanity.com/paper/1903.01293/) (2019)
- [On the All-Or-Nothing Behavior of Bernoulli Group Testing](https://mlsanity.com/paper/2001.10137/) (2020)
- [Information theoretic limits of learning a sparse rule](https://mlsanity.com/paper/2006.11313/) (2020)
- [Support Recovery in the Phase Retrieval Model: Information-Theoretic Fundamental Limits](https://mlsanity.com/paper/1901.10647/) (2019)
- [0-1 phase transitions in sparse spiked matrix estimation](https://mlsanity.com/paper/1911.05030/) (2019)

## Abstract (arXiv)

We establish exact asymptotic expressions for the normalized mutual information and minimum mean-square-error (MMSE) of sparse linear regression in the sub-linear sparsity regime. Our result is achieved by a generalization of the adaptive interpolation method in Bayesian inference for linear regimes to sub-linear ones. A modification of the well-known approximate message passing algorithm to approach the MMSE fundamental limit is also proposed, and its state evolution is rigorously analyzed. Our results show that the traditional linear assumption between the signal dimension and number of observations in the replica and adaptive interpolation methods is not necessary for sparse signals. They also show how to modify the existing well-known AMP algorithms for linear regimes to sub-linear ones.