Spatial Coupling for High-Dimensional Estimation

Abstract

Many signal processing and statistical problems allow flexibility in the way in which measurements are acquired. For example, in compressed sensing MRI, the sampling frequencies can be chosen to optimize reconstruction performance. This thesis investi- gates spatial coupling, a design technique that can enhance reconstruction performance with efficient algorithms for a variety of inference problems. For many high-dimensional regression models with unstructured designs, the Bayes-optimal estimator is computa- tionally intractable. The main idea in spatial coupling is to chain simple, unstructured measurement schemes together to obtain significant gains in performance. This concept has been investigated in the contexts of low-density parity-check (LDPC) codes and compressed sensing, to achieve the information-theoretically optimal performance with efficient message-passing algorithms. This thesis investigates spatial coupling for a range of statistical problems, starting with generalized linear models (GLMs). Recent work has precisely characterized the asymptotic minimum mean-squared error (MMSE) for GLMs with i.i.d. Gaussian sensing matrices. In many of these models, there is currently a significant gap between the MMSE and the performance of the best known feasible algorithms. 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 as the dimensions of the signal and the observation grow proportionally. Numerical experiments for phase retrieval and rectified linear regression demonstrate the performance gains due to coupling at finite lengths. We then investigate linear models with matrix-valued signals with correlated columns. We propose a novel spatially coupled AMP algorithm for this setting and use it to design an efficient decoder for the Gaussian multiple access channel with random user activity, in the regime where the number of users is proportional to the code length. We provide asymptotic guarantees of the error performance of the decoder and demonstrate that it outperforms the i.i.d. Gaussian AMP decoder and finite-length achievability bound. We generalize our AMP algorithms to non-Gaussian, binary-valued sensing matrices and apply them to quantitative group testing and pooled data testing. In both cases, we show that AMP achieves almost-exact recovery of a linear number of defectives from a sublinear number of tests. The performance of these spatially coupled AMP algorithms surpasses that of uncoupled AMP and optimization-based algorithms for different noise levels and distributions.