Signal recovery for quantized compressed sensing

Many systems, including telecommunication systems, radar and imaging systems, biomedical systems, control and robotics systems, rely on powerful digital signal processing (DSP). DSP algorithms are hard pressed to provide accurate estimates of a signal from as few as possible noisy measurements. If the signal to be estimated is sparse and high dimensional, a novel DSP technique, called compressed sensing (CS), allows efficient recovery from (possibly noisy) low dimensional representation. Even though reconstruction guarantees of a number of CS recovery algorithms have been known for almost a decade, many nonlinear distortions introduced by a practical measurement system are often not considered in the analysis. Neglecting these distortions could in turn have a detrimental effect on the performance of a recovery algorithm in a practical application. In this thesis, the focus is on algorithms for recovering sparse vectors from measurements tampered with some of the most common nonlinear distortions that appear in practice, namely quantization and modulo distortions, which are not treated with classical CS recovery algorithms. To present date, many reconstruction algorithms have been proposed to solve noisy CS problems. Among them, the class of approximate message passing (AMP) algorithms stands out for its low computational complexity, low reconstruction error, and the ability to predict the states of the algorithm across iterations (at least in the large system limit). Furthermore, the Bayesian approximate message passing (BAMP) algorithm has the ability to incorporate a signal prior to additionally improve the estimate, while the generalized approximate message passing (GAMP) algorithm allows for reconstruction of sparse signals from nonlinear measurements. These facts make the AMP algorithms particularly interesting for our problems involving quantization and modulo distortions with known prior. BAMP follows the probabilistic estimation approach where a prior distribution is assumed for the unknown signal. A commonly used family of distributions that promotes sparsity of the solution is the Bernoulli-Gauss (BG) mixture. In this thesis, it is shown how a BG mixture can be thought of as a limiting case of a mixture of two Gaussian distributions. This concept is extended to the case where the prior is modelled as a mixture of n Gaussian distributions, which covers a much larger class of signals. For that case explicit analytic update rules are derived for the BAMP algorithm. Furthermore, a novel approach is presented to the known Analysis-by-Synthesis (AbS) quantization scheme, where the BAMP algorithm is used to further reduce the end-to-end reconstruction MSE from quantized CS measurements. In many practical applications the computationally demanding AbS quantization scheme is not feasable, and CS measurements are simply scalar quantized. During the storage or communication over a noisy channel, the quantized measurements might be corrupted in different ways. Reconstruction by conventional algorithms on such highly distorted measurements will result in poor accuracy. To address these problems, the well established GAMP algorithm can be used and tailored for scalar quantized CS measurements corrupted with noise. Analytical expressions are provided for the nonlinear updates assuming different noise models, and numerical experiments are conducted to show that the GAMP algorithm outperforms conventional CS algorithms under the considered model assumptions. Finally, a problem is considered that typically appears in the context of calibration of sensing devices: unknown dynamic range of the input signal. Traditionally, this problem was addressed by clipping or saturating the input, which results in a loss of information about the signal. Alternatively, by taking modulo measurements, the input samples exceeding the sensor's threshold are simply folded back to it's dynamic range. Even though the sampling theory for recovering a sparse signal from its low-pass filtered version and modulo measurements already exists, in this thesis the application of the GAMP algorithm is investigated for recovering a sparse signal from modulo samples of noisy randomized projections of the unknown signal.11