Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit

Finding the sparsest solution to underdetermined systems of linear equations y = Φ x is NP-hard in general. We show here that for systems with “typical”/“random” Φ, a good approximation to the sparsest solution is obtained by applying a fixed number of standard operations from linear algebra. Our proposal, Stagewise Orthogonal Matching Pursuit (StOMP), successively transforms the signal into a negligible residual. Starting with initial residual r 0 = y , at the s -th stage it forms the “matched filter” Φ T rs-1 , identifies all coordinates with amplitudes exceeding a specially chosen threshold, solves a least-squares problem using the selected coordinates, and subtracts the least-squares fit, producing a new…