Just relax: convex programming methods for identifying sparse signals in noise
This paper studies a difficult and fundamental problem that arises throughout electrical engineering, applied mathematics, and statistics. Suppose that one forms a short linear combination of elementary signals drawn from a large, fixed collection. Given an observation of the linear combination that has been contaminated with additive noise, the goal is to identify which elementary signals participated and to approximate their coefficients. Although many algorithms have been proposed, there is little theory which guarantees that these algorithms can accurately and efficiently solve the problem. This paper studies a method called convex relaxation, which attempts to recover the ideal sparse signal by solving a convex program. This approach is powerful because the optimization can be completed in polynomial time with standard scientific software. The paper provides general conditions which ensure that convex relaxation succeeds. As evidence of the broad impact of these results, the paper describes how convex relaxation can be used for several concrete signal recovery problems. It also describes applications to channel coding, linear regression, and numerical analysis.
© Copyright 2006 IEEE. Reprinted with permission. Manuscript received June 7, 2004; revised February 1, 2005. [Posted online: 2006-03-06] This work was supported by the National Science Foundation Graduate Fellowship. Communicated by V. V. Vaishampayan, Associate Editor At Large. The author wishes to thank A.C. Gilbert and M.J. Strauss for their patience and encouragement. The detailed and insightful remarks of the anonymous referees prompted the author to see his results de novo. He believes that the current work is immeasurably better than the original submission on account of their attention and care. Thanks also to the Austinites, who have told the author for years that he should just relax.
Published - TROieeetit06.pdf
Erratum - Tropp2009p12810.1109TIT.2008.2009806.pdf