|
Applied Math Seminar
Fast Approximate Solution of Underdetermined Systems of Linear
Equations
|
|
Recent developments in theory and applications of sparse signal approximation have generated a great deal of interest in problems involving underdetermined systems of linear equations, whose solution is sparse. In this talk, we introduce Stagewise Orthogonal Matching Pursuit (StOMP), an algorithm for approximate solution of underdetermined linear systems, that often recovers the sparsest solution in a fraction of the time needed by traditional methods. Our proposed algorithm successively transforms the signal into a negligible residual, following a simple iterative procedure consisting of computation of a correlation vector, thresholding, and projection. We rigorously derive a conditioned Gaussian distribution for the correlation coefficients at each stage of the procedure and rigorously establish a large-system limit for the performance variables of StOMP. We compute large-sample phase transitions, establishing limits on the number of samples needed for approximate recovery of a sparse vector by StOMP. We demonstrate that the performance limits of the algorithm are comparable with the performance of costly convex optimization methods. To showcase the performance of the algorithm, we discuss a potential application drawing from MR Imaging. We consider the reconstruction of a 3-D volume from partial MRI data, obtained by random sampling in the frequency domain. We apply StOMP to solve the underlying underdetermined linear system, and obtain good accuracy reconstruction at a low computational cost. |