mlsanityData to 7 Oct 2026

Fundamental limits and algorithms for sparse linear regression with sublinear sparsity

arXiv 2101.11156 ↗First posted 27 Jan 2021cs.IT cs.LG math.ITcited by 0

Not on the map. Why?

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.

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

Builds on

15 of 45 references.

References · 15

  1. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
  2. 2014From Denoising to Compressed Sensingcited by 67
  3. 2017Learned D-AMP: Principled Neural Network based Compressive Image Recoverycited by 65
  4. 2017Estimation of Low-Rank Matrices via Approximate Message Passingcited by 41
  5. 2020Generalization Error of Generalized Linear Models in High Dimensionscited by 25
  6. 2014Phase transitions and sample complexity in Bayes-optimal matrix factorizationcited by 22
  7. 2019Inference with Deep Generative Priors in High Dimensionscited by 17
  8. 2020All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimationcited by 16
  9. 2015Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decodingcited by 5
  10. 2016Conditional Sparse Linear Regressioncited by 4
  11. 2019Asymptotics of MAP Inference in Deep Networkscited by 4
  12. 2020On the All-Or-Nothing Behavior of Bernoulli Group Testingcited by 3
3 more
  1. 2020Information theoretic limits of learning a sparse rulecited by 3
  2. 2019Support Recovery in the Phase Retrieval Model: Information-Theoretic Fundamental Limitscited by 2
  3. 20190-1 phase transitions in sparse spiked matrix estimationcited by 1

Built on by

Not cited yet.