Theory and software for sparse approximation algorithm phase transitions.

Abstract: We review the eigen-analysis and convex polytope approaches for the development of sparse approximation and compressed sensing algorithms. Problems which can be recast as convex relaxations are amenable to a precise analysis, but non-convex formulated algorithms have a dramatically less precise theoretical understanding. We present a gpu accelerated software package for the empirical investigation of non-convex algorithms. Large scale testing reveals a map of problem parameters and which algorithm has the lowest complexity for that problem parameters.
This work is joint with Bah, Blanchard, and Donoho.