Abstract
This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with $m$ nonzero entries in dimension $d$ given $ {rm O}(m ln d)$ random linear measurements of that signal. This is a massive improvement over previous results, which require ${rm O}(m^{2})$ measurements. The new results for OMP are comparable with recent results for another approach called Basis Pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems.
Keywords
Emphasis (telecommunications)Matching pursuitDimension (graph theory)SIGNAL (programming language)Basis pursuitSignal processingSignal reconstructionComputer scienceMatching (statistics)AlgorithmGreedy algorithmMathematicsCombinatoricsStatisticsCompressed sensingTelecommunications
Affiliated Institutions
Related Publications
Compressed sensing
Suppose x is an unknown vector in Ropfm (a digital image or signal); we plan to measure n general linear functionals of x and then reconstruct. If x is known to be compressible ...
Compressed sensing
Suppose x is an unknown vector in Ropf <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> (a digital image or signal); we pla...
Atomic Decomposition by Basis Pursuit
The time-frequency and time-scale communities have recently developed a large number of overcomplete waveform dictionaries --- stationary wavelets, wavelet packets, cosine packe...
Sparsity and incoherence in compressive sampling
We consider the problem of reconstructing a sparse signal x^0\\in{\\bb R}^n from a limited number of linear measurements. Given m randomly selected samples of Ux0, where U is an...
Signal Reconstruction From Noisy Random Projections
Recent results show that a relatively small number of random projections of a signal can contain most of its salient information. It follows that if a signal is compressible in ...
Publication Info
- Year
- 2007
- Type
- article
- Volume
- 53
- Issue
- 12
- Pages
- 4655-4666
- Citations
- 9473
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
9473
OpenAlex
Cite This
Joel A. Tropp,
Anna C. Gilbert
(2007).
Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit.
IEEE Transactions on Information Theory
, 53
(12)
, 4655-4666.
https://doi.org/10.1109/tit.2007.909108
Identifiers
- DOI
- 10.1109/tit.2007.909108