Sparse solution of underdetermined linear systems: Algorithms and applications.

摘要

Recent developments in theory and applications of sparse signal representation have generated a great deal of interest in finding the sparsest solution of underdetermined systems of linear equations. The main contributions of this dissertation are in the development and analysis of algorithms to find the sparsest solution of undetermined linear systems, and in offering potential applications in signal processing, image processing, and digital communications.; First, we suggest the use of the Homotopy algorithm, originally developed by Osborne et al. and Efron et al., to solve ℓ1 minimization problems whose solution is sparse. We show that when the solution is sufficiently sparse, Homotopy has the following k-step solution property: If the sparsest solution has at most k nonzeros, the algorithm recovers it in k steps. When the conditions for this property are met, Homotopy runs in a fraction of the time it takes to solve the ℓ1 minimization problem with general-purpose solvers.; Next, we introduce Stagewise Orthogonal Matching Pursuit (StOMP), a rapid iterative method to find sparse approximate solutions to underdetermined linear systems. We demonstrate that StOMP is much faster than competing approaches to recover sparse solutions, and at the same time, its ability to recover the sparsest solution is comparable with that of ℓ1 minimization.; Then, we offer a practitioner's viewpoint of Compressed Sensing, a notion proposing that compressible signals can be accurately reconstructed from incomplete measurements by solving an ℓ1 minimization problem. We conduct an empirical analysis of Compressed Sensing, establishing that it may be applied successfully in various practical settings. In addition, we suggest several extensions to the original proposal, and describe a natural application of this theory for fast acquisition of MRI data.; Finally, we propose a class of 'random' codes for robust transmission over a communication channel corrupted by two types of interference: white Gaussian noise and sparse impulse noise. We show that the transmitted information may be decoded using the Homotopy algorithm, and demonstrate that for certain channel configurations, the rate at which we can reliably transmit information with a negligible probability of error using the proposed codes is comparable to the fundamental limits set by Shannon's capacity.