Phase transitions for greedy sparse approximation algorithms (Q629259)

The authors deal with three illustrative greedy algorithms -- compressed sensing machine pursuits (CoSeMP), subspace pursuits (SP), and iterative hard thresholdings (IHT) -- that have similar uniform guarantees of successful recovery of sparse signals when the measurement matrix \(A\) satisfies the ubiquitous restricted isometry property (RIP). These three algorithms are related. The authors develop several techniques. They derive an important theorem that can be used for CoSeMP, SP, and IHT algorithms. The phase-transition framework translates the generic RIP-based conditions of Theorem 3.