Fundamental Limits and Algorithms for Sparse Linear Regression with Sublinear Sparsity
Lan V. Truong; 24(64):1−49, 2023.
Abstract
In this study, we investigate the normalized mutual information and minimum mean-square-error (MMSE) of sparse linear regression in the sub-linear sparsity regime. We extend the adaptive interpolation method in Bayesian inference for linear regimes to sub-linear ones in order to establish exact asymptotic expressions for these metrics. Additionally, we propose a modified version of the well-known approximate message passing algorithm to approach the MMSE fundamental limit and rigorously analyze its state evolution. Our findings demonstrate 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. Furthermore, we provide insights on how to modify existing AMP algorithms for linear regimes to sub-linear ones.
[abs]