A Caltech Library Service

Just relax: convex programming methods for identifying sparse signals in noise

Tropp, Joel A. (2006) Just relax: convex programming methods for identifying sparse signals in noise. IEEE Transactions on Information Theory, 52 (3). pp. 1030-1051. ISSN 0018-9448. doi:10.1109/TIT.2005.864420.

PDF - Published Version
See Usage Policy.

PDF - Erratum
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Tropp, Joel A.0000-0003-1024-1791
Additional Information:© 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.
Subject Keywords:Algorithms, approximation methods, basis pursuit, convex program, linear regression, optimization methods, orthogonal matching pursuit, sparse representations
Issue or Number:3
Record Number:CaltechAUTHORS:TROieeetit06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9040
Deposited By: Archive Administrator
Deposited On:22 Oct 2007
Last Modified:08 Nov 2021 20:55

Repository Staff Only: item control page