Analysis, algorithms and applications of compressed sensing

• Main Author: Yang, Zai
• Other Authors: Zhang Cishen
• Format: Theses and Dissertations
• Language: English
• Published: 2014
• Subjects: DRNTU::Engineering::Electrical and electronic engineering::Electronic systems::Signal processing
• Online Access: https://hdl.handle.net/10356/59537
• Institution: Nanyang Technological University

Compressed sensing (CS) is an emerging research area which studies the problem of recovering a high dimensional sparse signal from its low dimensional linear samples. While CS can acquire a signal with a sub-Nyquist sampling rate, it requires a nonlinear signal reconstruction strategy which is computationally expensive compared to the simple linear reconstruction procedure in the traditional Nyquist sampling case. Given the exact information of the sampling/sensing system, existing results have shown that the signal of interest can be accurately recovered via convex relaxation (l_1 minimization) and/or other approaches provided the signal is sufficiently sparse. To understand the sparsity-undersampling tradeoff is essential in CS, which is the first task of this thesis. Phase transition is currently the most precise tool to describe the tradeoff in the sense that it provides a condition that is both necessary and sufficient. While existing results are focused on the real valued signal and system case, we extend it to the complex case, discovering a new phase transition curve of l_1 minimization which is positioned well above the real one. On the other hand, the sampling system may not be exactly known a priori, the signal recovery performance in the presence of system perturbations is also studied in this thesis. In particular, a structured sensing matrix perturbation is studied which has practical relevance. Under mild sufficient conditions, it is shown that a sparse signal can be recovered by l_1 minimization and the recovery error is at most proportional to the measurement noise level, which is similar to the standard CS result. In the special noise free case, the recovery is exact provided that the signal is sufficiently sparse with respect to the perturbation level. Secondly, computationally efficient algorithms for CS are developed in the thesis. l_1 minimization has favorable guarantees of signal recovery accuracy but most solvers are slower than expected for practical problems of high dimension. In the thesis, two first-order algorithms are proposed for the l_1 minimization problem in CS: one exactly solves the problem and the other is a relaxed version of the first one. The latter can be considered as a modified iterative soft thresholding algorithm and is easy to implement. Sparse Bayesian learning (SBL) is another popular approach to the sparse signal recovery. In SBL, the signal sparsity information is exploited by assuming a sparsity-inducing prior for the signal that is then estimated using Bayesian inference. In the thesis, a new sparsity-inducing prior is introduced and efficient algorithms are developed for the signal recovery. The main algorithm is shown to produce a sparser solution than existing SBL methods while preserving their desirable properties. Moreover, a Bayesian framework is introduced in the thesis for the CS problem with quantized measurements. All proposed algorithms are compared with state-of-the-art algorithms through numerical simulations. At last, applications of CS to direction of arrival (DOA) estimation and motion correction in magnetic resonance imaging (MRI) are presented by exploiting the spatial sparsity of the source signals and the image sparsity in an appropriate domain, respectively. The proposed approach to the DOA estimation resolves the problem that the true DOAs may not lie on the discretized sampling grid which is typically required in existing methods. The new method can maintain high estimation accuracy even under a very coarse sampling grid. While existing applications of CS to MRI are focused on accelerating the scanning process by undersampling k-space data, a sparsity-driven approach to the motion correction in MRI is presented for the first time in the thesis.