Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information — TEI-tagged view

Emmanuel J. Candès, Justin Romberg, Terence Tao · 2006 · information-theory · doi:10.1109/TIT.2005.862083 · full text at the source · TEI xml · tagged edition · index · concepts · authors
Where this record's text came from. faceted 2026-08 by reading the locally held text (pdftext); every evidence string verified as an exact substring of that text before merging. method: no enumerated value fits a theorem-and-proof mathematics paper, so 'mathematical-proof' is used; Section 5 does report numerical recovery experiments, which are the paper's only empirical check ('Our experiments are of the following form:'). The PDF-to-text extraction badly interleaves the mathematics with the prose, so many otherwise usable sentences are not contiguous in the source and were rejected; the phenomenon quote was taken from a maths-free sentence for that reason. The typo 'experiements' in the first limitation is verbatim in the source. Note that the source file renders Omega as U+2126 (ohm sign), not U+03A9, so quotes containing it must use the ohm sign. Replication status is 'untested': the paper reports no external replication. 2026-08-15 schema-0.3 pass: every quote verified as an exact substring of the staged text and anchored at merge time; concept terms verified present; every edge endpoint an existing node.
2 quotes on this page were cut from a different copy of this article. This project holds two extractions of this paper: the plain text every other quote here is anchored in, and the publisher’s own HTML edition, which we are not licensed to republish. They are verbatim in the second and cannot be found in the first — not because the tagging is wrong, but because the extraction damaged the passage: a page number dropped into the middle of a number, a formula moved out of its sentence, a ligature where two letters belong. The record names the copy for each one. The quote is the paper’s; the extraction is not.
Other fields define these differently the same word, defined another way in another discipline
recovery 5 fields · sample-size 5 fields · frequency 2 fields · variance 2 fields
Tags on this paper every tag the record carries, whether or not the words occur in the text below — a number is how many papers in the corpus carry that tag; a tag with no number is unique to this paper
compressed sensing3 sparse signal Fourier transform2 convex optimization2 uncertainty principle exact recovery sparsity3 mathematical-proof27

Our tag layer for this paper

Cross-disciplinary analysis
content-tags & facets: phenomenon · claim-type · cross-domain-transfer · mechanism · claim-relation · replication-status · limitation — grounded in the full text
phenomenonexact signal reconstruction from incomplete Fourier samples— “In many applications of practical interest, we often wish to reconstruct an object (a discrete signal, a discrete image, etc.) from incomplete Fourier samples.”
claim-typemethod— “We propose instead a strategy based on convex optimization.”
method — evidence— “Using duality theory, we will be able to derive necessary and sufficient conditions for (P1) to recover f .”
transferfrom convex optimization / mathematics (l1 minimization, linear programming): recovering a sparse signal from few frequency samples by solving a convex l1-minimization (linear-programming) problem— “exact recovery may be obtained by solving a convex optimization problem”transfers[0]
mechanismcompressed sensing: a sparse signal can be reconstructed exactly from far fewer measurements than the Nyquist rate requires, by l1-norm (convex) minimization— “we show that we can recover f exactly from observations”mechanisms[0]
builds-on convex optimization / linear programming (mathematics)— “exact recovery may be obtained by solving a convex optimization problem”claim_relations[0]
builds-on the literature on l1 minimisation for sparse representation in overcomplete dictionaries [7, 8, 9, 12, 14]— “This literature certainly influenced our thinking in the sense it made us suspect that results such as Theorem 1.3 were actually possible.”claim_relations[1]
extends sampling-pattern results on exact recovery from consecutive Fourier coefficients [10, 11, 21]— “Our results, namely, Theorems 1.1 and 1.3 are quite distinct and far more general since they address the radically different situation in which we do not have the freedom to choose the samples at our convenience.”claim_relations[2]
sensePRIME is a property of an integer here, with no relation to a priming prime: the deterministic uniqueness theorem holds only when the signal length N is a prime number, because Z_N then has no non-trivial subgroups— “Note that if N is not prime, the lemma (and hence the theorem) fails, essentially because of the presence of non-trivial subgroups of ZN with addition modulo N ; see [6], [18] for further discussion.”senses[0]
senseexact recovery - a property of the NOISELESS problem only; under perturbation the paper says plainly that one cannot expect it, and asks instead how far the minimiser lies from the true object— “Then one might still want to reconstruct f via f ♯ = argmin g k kℓ1 , ˆg(ω) = ˆf (ω) + ˆh(ω), ω ∀ ∈ Ω. In this setup, of course, one cannot expect exact recovery”senses[1]
auditexact recovery —operationalised-as→ convex optimization — Audit 2026-09-28: DOUBTFUL - read against its full span and kept, but exact recovery 'may be obtained by solving' a convex optimization problem; operationalised-as is loose.— “In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for α which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp”concept_edges[0]
noteexact recovery —operationalised-as→ convex optimization — The paper's central move stated in one clause - '…recovery may be obtained by solving a CONVEX OPTIMIZATION…' - and immediately bounded: the condition on the support size is sharp EXCEPT FOR THE LOGARITHMIC FACTOR. The guarantee and the size of the remaining gap are given together.— “In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for α which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp”concept_edges[0]
weightexact recovery —operationalised-as→ convex optimization — 0.9— “In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for α which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp”concept_edges[0]
for which uselimitation — every exact-recovery guarantee: it holds PROVIDED THAT f IS SPARSE— “provided that f is sparse”limitations[0]
for which uselimitation — the sharpness of the sufficient condition: OUR METHODS DO NOT QUITE ATTAIN THIS THEORETICAL UPPER BOUND FOR CORRECT RECOVERY, [and] OUR NUMERICAL EXPERIMENTS SUGGEST THAT THEY DO COME WITHIN A CONSTANT FACTOR - the gap is measured, not proved— “While our methods do not quite attain this theoretical upper bound for correct recovery, our numerical experiements suggest that they do come within a constant factor of this bound (see Figure 2).”limitations[1]
for which uselimitation — the tightness of the analysis, with the responsible step named: ONE SOURCE OF SLACK IN THE THEORETICAL ANALYSIS IS THE WAY IN WHICH WE CHOOSE THE POLYNOMIAL P(t)— “One source of slack in the theoretical analysis is the way in which we choose the polynomial P (t) (as in (2.11)).”limitations[2]
for which uselimitation — the noiseless case only: under measurement perturbation, ONE CANNOT EXPECT EXACT RECOVERY— “In this setup, of course, one cannot expect exact recovery.”limitations[3]
for which uselimitation — the deterministic uniqueness theorem: IF N IS NOT PRIME, THE LEMMA (AND HENCE THE THEOREM) FAILS, ESSENTIALLY BECAUSE OF THE PRESENCE OF NON-TRIVIAL SUBGROUPS— “Note that if N is not prime, the lemma (and hence the theorem) fails, essentially because of the presence of non-trivial subgroups of ZN with addition modulo N ; see [6], [18] for further discussion.”limitations[4]
for which uselimitation — the robust uncertainty principle as used here: BECAUSE OF SPACE LIMITATION, WE ARE UNABLE TO BELABORATE ON THIS FACT AND ITS IMPLICATIONS ANY FURTHER— “Because of space limitation, we are unable to belaborate on this fact and its implications any further, but will do so in a companion paper.”limitations[5]
replicationuntested
limitationexact recovery holds only under a sparsity condition on the signal— “provided that f is sparse”limitations[0]
limitationThe sufficient condition proved is not sharp; the numerical experiments only show it is within a constant factor of the achievable bound.— “While our methods do not quite attain this theoretical upper bound for correct recovery, our numerical experiements suggest that they do come within a constant factor of this bound (see Figure 2).”limitations[1]
limitationThe particular dual polynomial construction used in the proof is a known source of looseness.— “One source of slack in the theoretical analysis is the way in which we choose the polynomial P (t) (as in (2.11)).”limitations[2]
limitationRobustness to measurement error is not established; under perturbation exact recovery no longer holds and only preliminary calculations are offered.— “In this setup, of course, one cannot expect exact recovery.”limitations[3]
limitationThe deterministic uniqueness theorem depends on the signal length being prime.— “Note that if N is not prime, the lemma (and hence the theorem) fails, essentially because of the presence of non-trivial subgroups of ZN with addition modulo N ; see [6], [18] for further discussion.”limitations[4]
limitationThe robust uncertainty principle underlying the analysis is stated but not developed here.— “Because of space limitation, we are unable to belaborate on this fact and its implications any further, but will do so in a companion paper.”limitations[5]
limitationThe guarantee does not survive measurement error, and the paper says so before anyone else can: under a small perturbation 'one cannot expect exact recovery', and the question becomes how far the minimiser is from the true object rather than whether it equals it.— “Then one might still want to reconstruct f via f ♯ = argmin g k kℓ1 , ˆg(ω) = ˆf (ω) + ˆh(ω), ω ∀ ∈ Ω. In this setup, of course, one cannot expect exact recovery”limitations[6]
Content tags
content-observations: finding · quantity · variable · definition · key-term — grounded in the full text
findingExact reconstruction is possible by solving a convex optimization problem.— “In short, exact recovery may be obtained by solving a convex optimization problem.”content_tags.findings[0]
findingThe recovery solves an optimization problem that finds the object of minimal complexity.— “The recovery consists of solving a straightforward optimization problem that finds f ♯ of minimal complexity”content_tags.findings[1]
variableFourier coefficients (independent)— “knowledge of its Fourier coefficients on the set”content_tags.variables[0]
evidence status notevariable — QUOTE RECOVERED FROM THE PAPER'S OWN CHARACTERS. The recorded quote was LETTERS-ONLY IDENTICAL to this stretch of the staged text but not an exact substring of it - spaces, hyphens, ligature glyphs or mathematical operators differed, so it could never anchor. This is the file's own text between the same two letters: not produced by a rule about the damage, copied out of the file. Round-trip checked (the recovered span is letters-only equal to the original) and length-checked. The text as originally recorded is kept in evidence as extracted.content_tags.variables[0]
variableexact recovery (dependent)— “exact recovery may be obtained by solving a convex optimization problem”content_tags.variables[1]
definitionℓ1 minimization— “solution to the ℓ1 minimization problem”content_tags.definitions[0]
key-termssignal, Fourier, sparse, reconstruction, frequency, minimization, convex, coefficients, recovery
Concepts
terms this paper carries, each with the sentence it was cut from — the layer that joins one paper to another. Terms with no quote yet are on CONCEPTS.html.
conceptexact recovery— “In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for α which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp”concepts[5]
conceptsparsity— “In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for α which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp”concepts[6]
Statistics — cross-field join keys
field-invariant statistical terms, used in their statistical sense (gated on a number / symbol / test). A p-value or a standard deviation means the SAME thing in physics, biology, psychology and sociology — so these are the strongest cross-field join keys. Grounded verbatim.
regression β as written: least-squares— “Indeed with knowledge of T , a reasonable strategy might be to recover f by the method of least-squares, namely, → In practice, the matrix inversion might be problematic.”content_tags.statistics[1]
sample-size n/N as written: sample sizes— “Note that the problem here does not really have anything to do with ℓ1-minimization per se; f cannot be reconstructed from its Fourier samples on Ω thereby showing that Theorem 1.1 does not work ’as is’ for arbitrary sample sizes.”content_tags.statistics[2]
variance σ²— “Randomly generate f by setting f (t) = 0, t T c and drawing both the real and T from independent Gaussian distributions with mean ∈ imaginary parts of f (t), t zero and variance one2”content_tags.statistics[3]
evidence status notevariance — QUOTE RECOVERED FROM THE PAPER'S OWN CHARACTERS. The recorded quote was LETTERS-ONLY IDENTICAL to this stretch of the staged text but not an exact substring of it - spaces, hyphens, ligature glyphs or mathematical operators differed, so it could never anchor. This is the file's own text between the same two letters: not produced by a rule about the damage, copied out of the file. Round-trip checked (the recovered span is letters-only equal to the original) and length-checked. The text as originally recorded is kept in evidence as extracted.content_tags.statistics[3]

When we have changed our mind. Some entries in the table begin with a word in capitals and the reason for it. EVIDENCE CORRECTED — the finding still stands, but we had quoted the wrong sentence from the paper, and the quotation has been replaced with the right one. RETRACTED — the entry itself was wrong; it stays on the page, marked, with the reason, rather than being deleted. WITHDRAWN AND REPLACED — the entry was wrong, and a corrected version of it appears in the entries below. Each mark carries its own reason, in brackets, because the reasons differ from one entry to the next. An entry we have WITHDRAWN is removed from this page and kept in the record, with its reason. A line reading Audit and a date is a later re-reading of the entry against its whole sentence: DOUBTFUL means it was kept, and the reason says what is loose about it. Quotation marks inside the tagger's sentence. Where a tag is the tagger's own sentence, a phrase in quotation marks inside it is borrowed from the paper — the tagger's wording around it is not. The paper's own sentence is the evidence quote for that row; on this page it is withheld with the article, and the article is at its publisher. Nothing inside quotation marks anywhere on this page is ours: if it is quoted, it is the paper's. Whose words a concept carries. A concept entry records a term the paper itself uses, so the term, the sense given for it, and its evidence are the paper's own words, quoted where the paper fixes them. This is the opposite of a sense entry in the tag table, which is the tagger's sentence about how the paper uses a term. Where a concept entry could not be grounded in the paper's words, the entry says so on its own row.

Tag layer © the Meta-Tagging Project, CC BY 4.0. The paper text is © its authors/publisher and is linked, not reproduced. Excerpts shown are short quotations for identification and verification. · back to index · concepts · authors · עברית
© 2026 Shir Sivroni · ORCID 0009-0000-2597-2824