Please use this identifier to cite or link to this item:
Title: Algorithms for recovery of sparse signals in compressed sensing
Authors: Tran, Anh Vu.
Keywords: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
Issue Date: 2013
Abstract: 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.
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:EEE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
  Restricted Access
1.69 MBAdobe PDFView/Open

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.