Fundamental limits and algorithms for sparse linear regression with sublinear sparsity

2021/01/26 by Lan V. Truong, Truong, Lan V. · 1 citation
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Distributed Sensor Networks and Detection Algorithms #Blind Source Separation Techniques

paper · pdf · doi:10.48550/arxiv.2101.11156

Abstract

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.

Cited by

• Generalized Orthogonal Approximate Message-Passing for Sublinear Sparsity

Related

• Interplay of minimax estimation and minimax support recovery under sparsity
• Information theoretic limits of learning a sparse rule
• Generalized Orthogonal Approximate Message-Passing for Sublinear Sparsity
• Minimax and adaptive estimation of general linear functionals under sparsity
• Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds