Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
By E.J. Candes, Justin K. Romberg, Terence Tao. 2004
16,406 citations recorded by the source corpus.
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.
Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Radiology, Nuclear Medicine and Imaging
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
- E.J. Candes
- Richard Baraniuk
- Yonina C. Eldar
- Wotao Yin
- Francis R. Bach
- Marco F. Duarte
- Julien Mairal
- Martin J. Wainwright
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Lei Zhang
- Dacheng Tao
- Ming-Hsuan Yang
- Xiaogang Wang
- Trevor Darrell
- Jitendra Malik
- Andrew Zisserman
In Radiology, Nuclear Medicine and Imaging
- E.J. Candes
- David L. Donoho
- Chengbo Li
- Yonina C. Eldar
- Justin K. Romberg
- Richard Baraniuk
- Rick Chartrand
- Yin Zhang
Citations in the corpus
- Age-Based Scheduling Policy for Federated Learning in Mobile Edge Networks (2019, background): “where ‖ · ‖0 is the L-0 norm [22] and Pk = {Pk,n, n ∈ Ck} is the transmit power on the allotted subchannels.”
- Discovering governing equations from data by sparse identification of nonlinear dynamical systems (2015, methodology): “This formulation is closely related to the compressive sensing framework, which allows for the sparse vector ξ to be determined from relatively few incoherent random measurements [15, 16, 17, 18, 19, 20].”
- A Singular Value Thresholding Algorithm for Matrix Completion (2008, methodology): “Our algorithm is inspired by recent work in the area of 1 minimization, and especially by the work on linearized Bregman iterations for compressed sensing; see [11, 12, 13, 27, 55, 67] for linearized Bregman iterations and [17, 19, 20, 21, 30] for some information about the field of compressed sensi”
- Robust Lasso With Missing and Grossly Corrupted Observations (2011, neutral): “[30], [8]).”
- Alternating Back-Propagation for Generator Network (2016, methodology): “We can learn the model from the compressively sensed data (Candès, Romberg, and Tao, 2006).”
- Decoding by linear programming (2005, methodology): “/∈ T, 7 where sgn(cj) is the sign of cj (sgn(cj) = 0 for cj = 0). The two conditions above say that a specific dual program is feasible and is called the exact reconstruction property in [5], see also [4]. For |T| ≤ S with S obeying the hypothesis of Theorem 1.4, FT has full rank since δS < 1 and ”
- Compressive Sensing in Electromagnetics - A Review (2015, methodology): “In order to minimize the acquisition time in SFCW-GPR prototypes [110], TV formulations solved with interior-point methods [98] have been investigated also.”
- Fixed point and Bregman iterative methods for matrix rank minimization (2009, background): “The basis pursuit problem has received an increasing amount of attention since the emergence of the field of compressed sensing (CS) [11; 14].”
- A framelet-based image inpainting algorithm (2008, background): “However, there are several reasons why ‖Dα‖1, where α is the wavelet coefficient and D is a diagonal matrix, is a good approximation, see [5,18,24].”
- Sparse MRI: The application of compressed sensing for rapid MR imaging (2007, background): “The formal results can be found by searching for the phrases compressed sensing (CS) or compressive sampling (14,15).”
- SPARSE RECONSTRUCTION FOR SAR IMAGING BASED ON COMPRESSED SENSING (2010, positive): “Such algorithms include basis pursuit (BP) [19], orthogonal match-pursuit (OMP) [20] and regularized orthogonal matching pursuit (ROMP) [21].”
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems (2009, background): “The problem (4) has attracted much interest in compressed sensing [8, 9, 10, 14, 15] and is also known as the basis pursuit problem.”
- Compressive sensing for seismic data reconstruction via fast projection onto convex sets based on seislet transform (2016, methodology): “The well-known exited sparsity-promoting transforms in the exploration geophysics field include the Fourier(Bochner and Chandrasekharan, 1949), wavelet transform(Akansu et al., 2010), and curvelet transform (Candès et al., 2006a).”