The Experts below are selected from a list of 189 Experts worldwide ranked by ideXlab platform

Justin Romberg - One of the best experts on this subject based on the ideXlab platform.

  • Robust uncertainty principles: Exact Signal reconstruction from highly incomplete frequency information
    IEEE Transactions on Information Theory, 2006
    Co-Authors: Emmanuel J Candes, Justin Romberg, Terence Tao
    Abstract:

    This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a Discrete-Time Signal $f \in \C^N$ and a randomly chosen set of frequencies $\Omega$ of mean size $\tau N$. Is it possible to reconstruct $f$ from the partial knowledge of its Fourier coefficients on the set $\Omega$? A typical result of this paper is as follows: for each $M > 0$, suppose that $f$ obeys $$ # \{t, f(t) \neq 0 \} \le \alpha(M) \cdot (\log N)^{-1} \cdot # \Omega, $$ then with probability at least $1-O(N^{-M})$, $f$ can be reconstructed exactly as the solution to the $\ell_1$ minimization problem $$ \min_g \sum_{t = 0}^{N-1} |g(t)|, \quad \text{s.t.} \hat g(\omega) = \hat f(\omega) \text{for all} \omega \in \Omega. $$ In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for $\alpha$ which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp. The methodology extends to a variety of other setups 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$.

  • Robust uncertainty principles: exact Signal reconstruction from highly incomplete frequency information
    IEEE Transactions on Information Theory, 2006
    Co-Authors: Emmanuel J Candes, Justin Romberg
    Abstract:

    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.

Emmanuel J Candes - One of the best experts on this subject based on the ideXlab platform.

  • Robust uncertainty principles: Exact Signal reconstruction from highly incomplete frequency information
    IEEE Transactions on Information Theory, 2006
    Co-Authors: Emmanuel J Candes, Justin Romberg, Terence Tao
    Abstract:

    This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a Discrete-Time Signal $f \in \C^N$ and a randomly chosen set of frequencies $\Omega$ of mean size $\tau N$. Is it possible to reconstruct $f$ from the partial knowledge of its Fourier coefficients on the set $\Omega$? A typical result of this paper is as follows: for each $M > 0$, suppose that $f$ obeys $$ # \{t, f(t) \neq 0 \} \le \alpha(M) \cdot (\log N)^{-1} \cdot # \Omega, $$ then with probability at least $1-O(N^{-M})$, $f$ can be reconstructed exactly as the solution to the $\ell_1$ minimization problem $$ \min_g \sum_{t = 0}^{N-1} |g(t)|, \quad \text{s.t.} \hat g(\omega) = \hat f(\omega) \text{for all} \omega \in \Omega. $$ In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for $\alpha$ which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp. The methodology extends to a variety of other setups 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$.

  • Robust uncertainty principles: exact Signal reconstruction from highly incomplete frequency information
    IEEE Transactions on Information Theory, 2006
    Co-Authors: Emmanuel J Candes, Justin Romberg
    Abstract:

    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.

Terence Tao - One of the best experts on this subject based on the ideXlab platform.

  • Robust uncertainty principles: Exact Signal reconstruction from highly incomplete frequency information
    IEEE Transactions on Information Theory, 2006
    Co-Authors: Emmanuel J Candes, Justin Romberg, Terence Tao
    Abstract:

    This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a Discrete-Time Signal $f \in \C^N$ and a randomly chosen set of frequencies $\Omega$ of mean size $\tau N$. Is it possible to reconstruct $f$ from the partial knowledge of its Fourier coefficients on the set $\Omega$? A typical result of this paper is as follows: for each $M > 0$, suppose that $f$ obeys $$ # \{t, f(t) \neq 0 \} \le \alpha(M) \cdot (\log N)^{-1} \cdot # \Omega, $$ then with probability at least $1-O(N^{-M})$, $f$ can be reconstructed exactly as the solution to the $\ell_1$ minimization problem $$ \min_g \sum_{t = 0}^{N-1} |g(t)|, \quad \text{s.t.} \hat g(\omega) = \hat f(\omega) \text{for all} \omega \in \Omega. $$ In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for $\alpha$ which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp. The methodology extends to a variety of other setups 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$.

Jr S L Marple - One of the best experts on this subject based on the ideXlab platform.

  • computing the Discrete Time analytic Signal via fft
    IEEE Transactions on Signal Processing, 1999
    Co-Authors: Jr S L Marple
    Abstract:

    Starting with a real-valued N-point Discrete-Time Signal, frequency-domain algorithms are provided for computing (1) the complex-valued standard N-point Discrete-Time "analytic" Signal of the same sample rate; (2) the complex-valued decimated N/2-point Discrete-Time "analytic" Signal of half the original sample rate; and (3) the complex-valued interpolated NM-point Discrete-Time "analytic" Signal of M Times the original sample rate. Special adjustment of the transform end points are shown to be necessary in order to generate proper Discrete-Time "analytic" Signals.

David L Donoho - One of the best experts on this subject based on the ideXlab platform.

  • uncertainty principles and ideal atomic decomposition
    IEEE Transactions on Information Theory, 2001
    Co-Authors: David L Donoho
    Abstract:

    Suppose a Discrete-Time Signal S(t), 0/spl les/tsuperposition of atoms taken from a combined Time-frequency dictionary made of spike sequences 1/sub {t=/spl tau/}/ and sinusoids exp{2/spl pi/iwt/N}//spl radic/N. Can one recover, from knowledge of S alone, the precise collection of atoms going to make up S? Because every Discrete-Time Signal can be represented as a superposition of spikes alone, or as a superposition of sinusoids alone, there is no unique way of writing S as a sum of spikes and sinusoids in general. We prove that if S is representable as a highly sparse superposition of atoms from this Time-frequency dictionary, then there is only one such highly sparse representation of S, and it can be obtained by solving the convex optimization problem of minimizing the l/sup 1/ norm of the coefficients among all decompositions. Here "highly sparse" means that N/sub t/+N/sub w/Time atoms, N/sub w/ is the number of frequency atoms, and N is the length of the Discrete-Time Signal. Underlying this result is a general l/sup 1/ uncertainty principle which says that if two bases are mutually incoherent, no nonzero Signal can have a sparse representation in both bases simultaneously. For the above setting, the bases are sinusoids and spikes, and mutual incoherence is measured in terms of the largest inner product between different basis elements. The uncertainty principle holds for a variety of interesting basis pairs, not just sinusoids and spikes. The results have idealized applications to band-limited approximation with gross errors, to error-correcting encryption, and to separation of uncoordinated sources. Related phenomena hold for functions of a real variable, with basis pairs such as sinusoids and wavelets, and for functions of two variables, with basis pairs such as wavelets and ridgelets. In these settings, if a function f is representable by a sufficiently sparse superposition of terms taken from both bases, then there is only one such sparse representation; it may be obtained by minimum l/sup 1/ norm atomic decomposition. The condition "sufficiently sparse" becomes a multiscale condition; for example, that the number of wavelets at level j plus the number of sinusoids in the jth dyadic frequency band are together less than a constant Times 2/sup j/2/.