Algorithms for recovery of sparse signals in compressed sensing

• Main Author: Tran, Anh Vu.
• Other Authors: Justin Dauwels
• Format: Final Year Project
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity; DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
• Online Access: http://hdl.handle.net/10356/52687
• Institution: Nanyang Technological University

In real-world applications, most of the signals can be approximated by sparse signals. When dealing with sparse or compressible signal, the traditional process of acquiring the signal and then discard most of the samples for compression is inefficient and memory consuming. Recent developments in statistics and signal processing have introduced the method of compressed sensing as an efficient reconstruction of sparse signals based on incomplete set of measurements. Compressed sensing comes from the idea of sparse approximation, where a sparse signal in high dimensional space can be represented by lower number of linear measurements if these measurements are incoherent enough. The investigation of computational methods for sparse linear inverse problem in this report focuses on two main classes: convex optimization and greedy algorithm. For the first approach, we used a linear programming technique to solve the basis pursuit formulation of the sparse approximation. It has strong, uniform guarantees and stability, the down side is that its time complexity doesn’t have a strong polynomial bound. For the greedy algorithms, Orthogonal Matching Pursuit and Compressive Sampling Matching Pursuit are investigated. Advantage of these methods is their fast runtime and can provide the optimal solution under specific circumstance. However, Orthogonal Matching Pursuit doesn’t have a universal set of measurements and Compressive Sampling Matching Pursuit is highly sensitive to the input sparsity. The ultimate comparison is between the convex optimization of the regularized basis pursuit and Compressive Sampling Matching Pursuit.