Computing performance guarantees for compressed sensing

There are various conditions on the CS matrix for unique and stable recovery. These include universality, or spark, and UUP. Furthermore, quantitative bounds on the stability depend on related properties of the CS matrix. The construction of good CS matrices - satisfying the various properties - is key to successful practical applications of compressive sensing. Unfortunately, verifying the satisfiability of any of these properties for a given CS matrix involves infeasible combinatorial search. Our methods use i and semidefinite relaxation into a convex problem. Given a set of candidate CS matrices, our approach provides tools for the selection of good CS matrices with verified and quantitatively favorable performance.