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. 489509. ISSN 00189448. http://resolver.caltech.edu/CaltechAUTHORS:CANieeetit06

PDF
See Usage Policy. 1167Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:CANieeetit06
Abstract
This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discretetime 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 1O(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 1O(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 twodimensional) 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 

Additional Information:  © Copyright 2006 IEEE. Reprinted with permission. Manuscript received June 10, 2004; revised September 9, 2005. [Posted online: 20060123] The work of E. J. Candes is supported in part by the National Science Foundation under Grant DMS 0140698 (FRG) and by an Alfred P. Sloan Fellowship. The work of J. Romberg is supported by the National Science Foundation under Grants DMS 0140698 and ITR ACI0204932. The work of T. Tao is supported in part by a grant from the Packard Foundation. Communicated by A. HøstMadsen, 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 PoShen 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, totalvariation minimization, trigonometric expansions, uncertainty principle 
Issue or Number:  2 
Record Number:  CaltechAUTHORS:CANieeetit06 
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:CANieeetit06 
Alternative URL:  http://dx.doi.org/10.1109/TIT.2005.862083 
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  4792 
Collection:  CaltechAUTHORS 
Deposited By:  Archive Administrator 
Deposited On:  07 Sep 2006 
Last Modified:  26 Dec 2012 09:01 
Repository Staff Only: item control page