Generalized Orthogonal Approximate Message-Passing for Sublinear Sparsity
This work addresses signal reconstruction in compressed sensing for scenarios with sublinear sparsity, offering improved performance over prior methods, though it is incremental as it builds on existing AMP frameworks.
The paper tackles the problem of reconstructing sparse signals from generalized linear measurements under sublinear sparsity conditions, proposing Generalized Orthogonal Approximate Message-Passing (GOAMP) to improve convergence for orthogonally invariant sensing matrices. It proves that GOAMP achieves error-free reconstruction under certain conditions and outperforms existing algorithms, such as generalized AMP, in simulations with ill-conditioned matrices.
This paper addresses the reconstruction of sparse signals from generalized linear measurements. Signal sparsity is assumed to be sublinear in the signal dimension while it was proportional to the signal dimension in conventional research. Approximate message-passing (AMP) has poor convergence properties for sensing matrices beyond standard Gaussian matrices. To solve this convergence issue, generalized orthogonal AMP (GOAMP) is proposed for signals with sublinear sparsity. The main feature of GOAMP is the so-called Onsager correction to realize asymptotic Gaussianity of estimation errors. The Onsager correction in GOAMP is designed via state evolution for orthogonally invariant sensing matrices in the sublinear sparsity limit, where the signal sparsity and measurement dimension tend to infinity at sublinear speed in the signal dimension. When the support of non-zero signals does not contain a neighborhood of the origin, GOAMP using Bayesian denoisers is proved to achieve error-free signal reconstruction for linear measurements if and only if the measurement dimension is larger than a threshold, which is equal to that of AMP for standard Gaussian sensing matrices. Numerical simulations are also presented for linear measurements and 1-bit compressed sensing. When ill-conditioned sensing matrices are used, GOAMP for sublinear sparsity is shown to outperform existing reconstruction algorithms, including generalized AMP for sublinear sparsity.