A Caltech Library Service

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

Candès, Emmanuel J. and Romberg, Justin and Tao, Terence (2006) Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52 (2). pp. 489-509. ISSN 0018-9448.

See Usage Policy.


Use this Persistent URL to link to this item:


This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. Manuscript received June 10, 2004; revised September 9, 2005. [Posted online: 2006-01-23] The work of E. J. Candes is supported in part by the National Science Foundation under Grant DMS 01-40698 (FRG) and by an Alfred P. Sloan Fellowship. The work of J. Romberg is supported by the National Science Foundation under Grants DMS 01-40698 and ITR ACI-0204932. The work of T. Tao is supported in part by a grant from the Packard Foundation. Communicated by A. Høst-Madsen, Associate Editor for Detection and Estimation. E. J. Candes and T. Tao wish to thank the Institute for Pure and Applied Mathematics at the University of California at Los Angeles (UCLA) for their warm hospitality. E. J. Candes would also like to thank Amos Ron and David Donoho for stimulating conversations, and Po-Shen Loh for early numerical experiments on a related project. We would also like to thank Holger Rauhut for corrections on an earlier version and the anonymous referees for their comments and references.
Subject Keywords:Convex optimization, duality in optimization, free probability, image reconstruction, linear programming, random matrices, sparsity, total-variation minimization, trigonometric expansions, uncertainty principle
Issue or Number:2
Record Number:CaltechAUTHORS:CANieeetit06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:4792
Deposited By: Archive Administrator
Deposited On:07 Sep 2006
Last Modified:02 Oct 2019 23:16

Repository Staff Only: item control page