Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
arXiv:2309.08404 · doi:10.1109/TIT.2024.3455228
Abstract
We consider the problem of signal estimation in a generalized linear model (GLM). GLMs include many canonical problems in statistical estimation, such as linear regression, phase retrieval, and 1-bit compressed sensing. Recent work has precisely characterized the asymptotic minimum mean-squared error (MMSE) for GLMs with i.i.d. Gaussian sensing matrices. However, in many models there is a significant gap between the MMSE and the performance of the best known feasible estimators. In this work, we address this issue by considering GLMs defined via spatially coupled sensing matrices. We propose an efficient approximate message passing (AMP) algorithm for estimation and prove that with a simple choice of spatially coupled design, the MSE of a carefully tuned AMP estimator approaches the asymptotic MMSE in the high-dimensional limit. To prove the result, we first rigorously characterize the asymptotic performance of AMP for a GLM with a generic spatially coupled design. This characterization is in terms of a deterministic recursion (`state evolution') that depends on the parameters defining the spatial coupling. Then, using a simple spatially coupled design and a judicious choice of functions for the AMP algorithm, we analyze the fixed points of the resulting state evolution and show that it achieves the asymptotic MMSE. Numerical results for phase retrieval and rectified linear regression show that spatially coupled designs can yield substantially lower MSE than i.i.d. Gaussian designs at finite dimensions when used with AMP algorithms.
41 pages, 4 figures. Appeared in the IEEE Transactions on Information Theory
References in corpus (22)
- Message Passing Algorithms for Compressed Sensing
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC
- Statistical physics of inference: Thresholds and algorithms
- Spatially Coupled LDPC Codes Constructed from Protographs
- Compressive Phase Retrieval via Generalized Approximate Message Passing
- Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
- Statistical physics-based reconstruction in compressed sensing
- Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
- Approximate message-passing decoder and capacity-achieving sparse superposition codes
- The Numerics of Phase Retrieval
- Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
- Spatially Coupled Sparse Codes on Graphs - Theory and Practice
- Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
- Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
- A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
- Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
- Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
- Performance Improvement of Iterative Multiuser Detection for Large Sparsely-Spread CDMA Systems by Spatial Coupling
- Sparse Regression Codes
- Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
- Near-Optimal Coding for Many-user Multiple Access Channels