Support Recovery from Compressed Measurements: A Non-Convex Approach

Jie Shen
Ph.D. Candidate, Department of Computer Science
Rutgers University
SERC 306
Friday, January 26, 2018 - 11:00
In machine learning and high-dimensional statistics, it is of central importance to understand when a tractable algorithm recovers the support of a sparse signal from its compressed measurements. In this work, we present a novel analysis on the support recovery performance for a family of non-convex algorithms. We show that under proper conditions, these algorithms recover the support of an arbitrary s-sparse signal within "O(s kappa log(kappa))" iterations where "kappa" is an appropriate condition number. This gives the best known results for prominent non-convex algorithms. In addition, we characterize the trade-off between statistical accuracy and computational complexity among the members of the family. Compared to convex programs such as the Lasso, we prove that the non-convex algorithms are computationally more efficient, and are able to solve ill-conditioned problems. The empirical study perfectly matches our theoretical findings.