Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information

Emmanuel J. Candès, Justin Romberg, Terence Tao · IEEE Transactions on Information Theory / arXiv · 2006 · information-theory · 10.1109/TIT.2005.862083 · record candes2006-robust-uncertainty
tag layer · 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.

How to read this page. The article itself is not reproduced here — this paper is not cleared for redistribution, so what follows is the tag layer alone. The evidence sentences are withheld with the article. The table at the foot lists every tag the record carries; each row names the facet it belongs to, and the whose words column says whether the tag records the paper's own wording or the tagger's sentence about the paper. Every tag links to each other paper in the corpus carrying it. The machine-readable edition of the same thing is the TEI file beside this one, where the tags live in standOff, and the article is at its publisher via the link below. 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.

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, each linking to every other paper in the corpus that carries it. A tag appears here whether or not its words occur in the article — the spans below are only the ones a sentence in this paper licenses. Of the 7 concept tags on this paper, 2 are grounded in a quoted sentence.

compressed sensing sparse signal Fourier transform convex optimization uncertainty principle exact recovery sparsity compressed sensing: a sparse signal can be reconstructed exactly from far fewer measurements than the Nyquist rate requires, by l1-norm (convex) minimization signal Fourier sparse reconstruction frequency minimization convex coefficients recovery ℓ1 minimization Fourier coefficients regression least-squares sample-size sample sizes variance mathematical-proof

Legend

relation to other work	`claim_relations`	how this paper stands to another: agrees, contradicts, extends, qualifies
claim type	`claim_type`	the shape of the claim: existence, mechanism, method, critique, prediction, null
concept edge	`concept_edges`	an asserted relation between two concepts, with the sentence asserting it
concept	`concepts`	an idea the paper works with, quoted where the paper uses it
content tag	`content_tags`	a finding, definition, quantity, statistic or variable named in the paper
limitation	`limitations`	what the paper says its evidence cannot support
mechanism	`mechanisms`	how the reported effect is said to come about
method	`method`	how the paper produced its evidence
phenomenon	`phenomenon`	the effect or regularity under study
sense	`senses`	a distinct use of a term, quoted where the paper fixes it
transfer	`transfers`	a method or concept carried in from another field

The paper

The full text is not reproduced here. This article is not cleared for redistribution, so the page carries the tag layer only. Its evidence sentences are withheld; the grounding status remains with each tag, and the article itself is at https://doi.org/10.1109/TIT.2005.862083. The reading view exists for the papers whose licence permits it.

Every tag on this page

claim_relations 3 · claim_type 1 · concept_edges 1 · concepts 2 · content_tags 8 · limitations 7 · mechanisms 1 · method 1 · phenomenon 1 · senses 2 · transfers 1

Relations on this page carry a quotation for the claim. Where a relation was separately evidenced — and so tested against the vocabulary for its type — the row says so; none of 1 relation here carry that mark. The rest are the tagger’s reading of the sentence quoted beside them.

This record holds no controls. A layer is empty when the tagger recorded nothing in it — which is not the same as the paper having nothing to record.

facet	tag	field	conf.	whose words
claim_type	method Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_type`		the paper's words
phenomenon	exact signal reconstruction from incomplete Fourier samples Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`phenomenon`		the paper's words
method	mathematical-proof Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: mathematical-proof	`method`		the paper's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: compressed sensing: a sparse signal can be reconstructed exactly from far fewer measurements than the Nyquist rate requires, by l1-norm (convex) minimization	`mechanisms[0]`		the tagger's words
limitations	exact recovery holds only under a sparsity condition on the signal Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: every exact-recovery guarantee: it holds PROVIDED THAT f IS SPARSE	`limitations[0]`		the tagger's words
limitations	The sufficient condition proved is not sharp; the numerical experiments only show it is within a constant factor of the achievable bound. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: 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	`limitations[1]`		the tagger's words
limitations	The particular dual polynomial construction used in the proof is a known source of looseness. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: 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)	`limitations[2]`		the tagger's words
limitations	Robustness to measurement error is not established; under perturbation exact recovery no longer holds and only preliminary calculations are offered. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the noiseless case only: under measurement perturbation, ONE CANNOT EXPECT EXACT RECOVERY	`limitations[3]`		the tagger's words
limitations	The deterministic uniqueness theorem depends on the signal length being prime. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: 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	`limitations[4]`		the tagger's words
limitations	The robust uncertainty principle underlying the analysis is stated but not developed here. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the robust uncertainty principle as used here: BECAUSE OF SPACE LIMITATION, WE ARE UNABLE TO BELABORATE ON THIS FACT AND ITS IMPLICATIONS ANY FURTHER	`limitations[5]`		the tagger's words
limitations	The 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. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`limitations[6]`	0.95	the tagger's words
transfers	recovering a sparse signal from few frequency samples by solving a convex l1-minimization (linear-programming) problem Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`transfers[0]`		the tagger's words
concepts	exact recovery Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: exact recovery	`concepts[5]`	0.95	the paper's words
concepts	sparsity Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: sparsity	`concepts[6]`	0.9	the paper's words
senses	PRIME 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 Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`senses[0]`	1.0	the tagger's words
senses	exact 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 Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`senses[1]`	0.95	the tagger's words
claim_relations	builds-on → convex optimization / linear programming (mathematics) Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[0]`		the tagger's words
claim_relations	builds-on → the literature on l1 minimisation for sparse representation in overcomplete dictionaries [7, 8, 9, 12, 14] Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[1]`		the tagger's words
claim_relations	extends → sampling-pattern results on exact recovery from consecutive Fourier coefficients [10, 11, 21] Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[2]`		the tagger's words
concept_edges	exact recovery —operationalised-as→ convex optimization Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. strength of the relation: 0.9 · note: 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. 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. also in: exact recovery · convex optimization	`concept_edges[0]`	0.95	the tagger's words
content_tags	Exact reconstruction is possible by solving a convex optimization problem. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.findings[0]`		the tagger's words
content_tags	The recovery solves an optimization problem that finds the object of minimal complexity. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.findings[1]`		the tagger's words
content_tags	Fourier coefficients Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: 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. also in: Fourier coefficients	`content_tags.variables[0]`		the tagger's words
content_tags	exact recovery Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: exact recovery	`content_tags.variables[1]`		the tagger's words
content_tags	ℓ1 minimization Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: ℓ1 minimization	`content_tags.definitions[0]`		the tagger's words
content_tags	regression Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: regression	`content_tags.statistics[1]`		the tagger's words
content_tags	sample-size Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: sample-size	`content_tags.statistics[2]`		the tagger's words
content_tags	variance Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: 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. also in: variance	`content_tags.statistics[3]`		the tagger's words

Interpretive choices

Tags that could not be placed in the text:

none — every tag was located in the text

What was deliberately not tagged, and why, is recorded per paper by the tagger. Where a paper has no such record, this page says so rather than implying that nothing was declined.