Exact Matrix Completion via Convex Optimization

Emmanuel J. Candès, Benjamin Recht · Foundations of Computational Mathematics / arXiv · 2009 · mathematics · 10.1007/s10208-009-9045-5 · record candes2009-matrix-completion
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. The method vocabulary offered (behavioural-experiment, fmri, simulation, review, ...) has no slot for a theorem-proving mathematics paper, so I used 'mathematical-proof'; the paper does also report simulations (Sect. 7, 50 runs per (n,m,r) triple with SDPT3), which would justify 'simulation' as a secondary method tag. The paper also differentiates itself sharply from [29] (Gaussian-measurement nuclear-norm results) and from the SVD-based procedure of [3], but those passages state that the prior methods do not address this problem rather than contradicting a claim, so I did not force them into a claim relations type. Discipline could equally be 'signal-processing' or 'optimization'. 2026-08-14 and 2026-08-16 schema-0.3 passes: 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. Update, 15 September 2026: EXCEPTION, measured with the merge gate's own predicate (Paper.locate): 3 quote(s) on this record are not found as one exact string in the current staged text - content_tags.findings[0].evidence, content_tags.findings[1].evidence, content_tags.statistics[3].evidence. The sentence above does not hold for them as written. Where a row records why - the quote is grounded in another copy of the paper, joins two passages with an ellipsis, or differs from the staged text by extraction noise - that note stays on the row. Update, 16 September 2026: EXCEPTION TO THE DATED PASS ABOVE, on this record only: this record carries 2 composite quote fields - a quote assembled from two or more passages joined by an ellipsis. A COMPOSITE IS NOT AN EXACT CONTIGUOUS SUBSTRING of the staged text and is deliberately not anchored: each of its parts is verified separately at the offsets in evidence composite spans, and a part occurring more than once carries span null rather than a guessed offset. So the 'every quote verified as an exact substring' clause of the dated pass above DOES NOT HOLD for those fields, and never did - the parts were verified, the whole was not. Nothing is deleted, re-grounded or withdrawn: this writes down an exception that was always true of composites and had not been recorded, so a reader was told more than the pass had checked.

The quality of the text these quotes were cut from. symbol-font-not-extractable: mathematical notation is lost to '(cid:NN)' markers - 2453 of them, 14.4% of an internal file by character, but only 5.5% sit isolated in running prose (the rest cluster inside formulae). Omega, the norms and the inequality operators render as markers. 29 distinct codes with the top two accounting for 38% - ONE SYMBOL FONT WITH NO ToUnicode MAP, not a general extraction failure; a broken text font needs hundreds of codes. THE ARGUMENT OF THE PAPER IS READABLE AND TAGGABLE; THE EQUATIONS ARE NOT. 42 live quotes, 1 carrying a marker. The web page we fetched carries 1742 markers of its own and is not a repair.

Some quotes on this page contain (cid:NN). The PDF this text was extracted from encodes 6 characters in a way that names no letter, so the extractor could not say what they were. The quotes keep them because a quote is reproduced exactly or it proves nothing — the marks are the source’s, not the tagging’s.

3 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 · statistical-significance 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 9 concept tags on this paper, 5 are grounded in a quoted sentence.

matrix completion convex optimization low-rank matrix nuclear norm compressed sensing incoherent standard basis rank minimization sampling operator the quantity actually wanted - the rank - is replaced by the sum of the singular values, because minimising rank is NP-hard and every known exact algorithm takes time doubly exponential in the dimension, while the substitute is convex the substitution is licensed by an analogy the authors state rather than assume: the nuclear norm stands to the rank function as the convex l1 norm stands to the counting l0 norm in sparse signal recovery - one counts nonvanishing singular values, the other sums their amplitude the informal requirement that the singular vectors be spread out is converted into a MEASURED quantity - the coherence of a subspace against the standard basis - whose smallest value is one, attained when the spanning vectors' entries all share a magnitude, and whose largest is attained by any subspace containing a standard basis element necessity is established by exhibiting a matrix rather than by argument: this one cannot be recovered from a sample of its entries unless nearly all are seen, because for most sampling sets one would see only zeros and would have no way to guess the matrix is not zero a second necessary condition is derived the same way, from an adversarial sampling set rather than a random one: with no sample in some row, one component is unobserved and no method whatsoever can recover it, so at least one observation per row and per column is required the impossibility is side-stepped by changing the question from ALL sampling sets to MOST - adversarial sampling defeats even rank one, so what is asked instead is whether recovery succeeds for almost all sampling sets of a given size the class of matrices the theorem covers is fixed by an explicitly stated assumption rather than left to the reader: both coherences must be bounded above by a single positive constant, which is what turns 'the singular vectors are spread out' into a checkable premise the convex program is put into a form existing software already solves: for a positive semidefinite unknown the nuclear norm IS the trace of the matrix, so the heuristic collapses into minimising the trace over the constraint set matrix completion low-rank convex recovery entries incoherence rank nuclear norm minimization chi-square chi-squared degrees-of-freedom degrees of freedom sample-size sample size statistical-significance 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
control	`controls`	an experiment run to eliminate a rival explanation
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.1007/s10208-009-9045-5. The reading view exists for the papers whose licence permits it.

Every tag on this page

claim_relations 4 · claim_type 1 · concept_edges 1 · concepts 5 · content_tags 7 · controls 1 · limitations 8 · mechanisms 8 · method 1 · phenomenon 1 · senses 3 · 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.

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	low-rank matrix completion 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: the quantity actually wanted - the rank - is replaced by the sum of the singular values, because minimising rank is NP-hard and every known exact algorithm takes time doubly exponential in the dimension, while the substitute is convex	`mechanisms[0]`	0.95	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: 2026-08-16: TWO FAILED GLYPHS INSIDE THIS QUOTE. The staged text reads "what the convex (cid:4)1 norm is to the counting (cid:4)0 norm" - the extraction could not map the script-l character and left the raw PDF font code "(cid:4)" in its place, twice. Read as l-1 and l-0, the standard sparse-recovery notation. The quote is an exact substring of the staged file. It is kept rather than dropped because this sentence IS the licence for the paper's central substitution - the nuclear norm stands to rank as the convex norm stands to the counting norm - and a mechanisms layer that silently omitted it would be tidier and less true. also in: the substitution is licensed by an analogy the authors state rather than assume: the nuclear norm stands to the rank function as the convex l1 norm stands to the counting l0 norm in sparse signal recovery - one counts nonvanishing singular values, the other sums their amplitude	`mechanisms[1]`	0.95	the tagger'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: the informal requirement that the singular vectors be spread out is converted into a MEASURED quantity - the coherence of a subspace against the standard basis - whose smallest value is one, attained when the spanning vectors' entries all share a magnitude, and whose largest is attained by any subspace containing a standard basis element	`mechanisms[2]`	0.85	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: 2026-08-16: THE SUBJECT OF THIS QUOTE IS ANAPHORIC AND ITS REFERENT IS NOT QUOTABLE. "this matrix" is the rank-one matrix with a single nonzero entry in the top-right corner, defined in the preceding sentence as M = e1 e_n^. The span was NOT widened to reach that definition because the intervening text is the flattened matrix display, which the extraction renders as stray zeros and box-drawing characters - 'M = e1e n = [ 0 0 ... 0 0 . . . 0 . . . ] , 0 1 0 0 ...' - so a wider span would quote rubble to fix a pronoun. Recorded here instead. also in: necessity is established by exhibiting a matrix rather than by argument: this one cannot be recovered from a sample of its entries unless nearly all are seen, because for most sampling sets one would see only zeros and would have no way to guess the matrix is not zero	`mechanisms[3]`	0.85	the tagger'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: a second necessary condition is derived the same way, from an adversarial sampling set rather than a random one: with no sample in some row, one component is unobserved and no method whatsoever can recover it, so at least one observation per row and per column is required	`mechanisms[4]`	0.85	the tagger'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: the impossibility is side-stepped by changing the question from ALL sampling sets to MOST - adversarial sampling defeats even rank one, so what is asked instead is whether recovery succeeds for almost all sampling sets of a given size	`mechanisms[5]`	0.85	the tagger'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: the class of matrices the theorem covers is fixed by an explicitly stated assumption rather than left to the reader: both coherences must be bounded above by a single positive constant, which is what turns 'the singular vectors are spread out' into a checkable premise	`mechanisms[6]`	0.85	the tagger'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: the convex program is put into a form existing software already solves: for a positive semidefinite unknown the nuclear norm IS the trace of the matrix, so the heuristic collapses into minimising the trace over the constraint set	`mechanisms[7]`	0.85	the tagger's words
limitations	The guarantee covers exactly low-rank matrices; extension to approximately low-rank matrices is left open. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the exact-recovery guarantee: IT WOULD BE OF INTEREST TO EXTEND OUR RESULTS TO THE CASE WHERE THE UNKNOWN MATRIX IS APPROXIMATELY LOW-RANK - only exactly low-rank is covered	`limitations[0]`		the tagger's words
limitations	The sampling bounds proved may be far more demanding than what is needed in practice. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the sampling bound as a practical requirement: THE EXPERIMENTS REVEAL VERY SIMILAR PLOTS FOR DIFFERENT n, SUGGESTING THAT OUR ASYMPTOTIC CONDITIONS FOR RECOVERY MAY BE RATHER CONSERVATIVE	`limitations[1]`		the tagger's words
limitations	The semidefinite program the theory relies on does not scale with off-the-shelf solvers. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: any large-scale application of the method as specified: STANDARD INTERIOR POINT METHODS WILL BE IMPRACTICAL FOR PROBLEMS WHERE THE UNKNOWN MATRIX HAS HUNDREDS OF ROWS OR COLUMNS	`limitations[2]`		the tagger's words
limitations	The general problem of recovery from arbitrary linear functionals is not treated. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the general recovery problem: WE LEAVE THIS GENERAL LOW-RANK RECOVERY PROBLEM FOR FUTURE WORK	`limitations[3]`		the tagger's words
limitations	The paper states that the general problem is impossible and narrows the question before answering it. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the exact-recovery result reported here: the authors state it is impossible to recover all low-rank matrices from sampled entries, and pose the answerable question as whether most can be recovered	`limitations[4]`	1.0	the tagger's words
limitations	The tractable method is a relaxation whose equivalence to the real problem holds for most instances, not all. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the use of nuclear norm minimisation as a stand-in for rank minimisation: the paper states the relaxation is formally equivalent to the combinatorially hard rank minimization problem for most problems	`limitations[5]`	1.0	the tagger's words
limitations	The recovery guarantee holds only for matrices whose row and column spaces satisfy an incoherence condition. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: any application of this recovery result: it applies to matrices whose row and column spaces are incoherent with the standard basis, a property of the matrix that must hold for the guarantee to bind	`limitations[6]`	1.0	the tagger's words
limitations	The exact-solution alternative is not merely slow but doubly exponential in the dimension. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the claim that this method makes the problem tractable: the exact formulation is NP-hard and all known exact algorithms require time doubly exponential in the matrix dimension	`limitations[7]`	1.0	the tagger's words
transfers	the compressed-sensing result that an object can be recovered exactly from far fewer measurements than its dimension, carried over from signal acquisition to the recovery of a low-rank matrix from a sample of its entries Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`transfers[0]`	0.9	the tagger's words
controls	the whole recovery procedure repeated 50 times for every (n, m, r) triple Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. eliminates: a single lucky or unlucky draw of the sampled entries - 50 repetitions per parameter setting turn one outcome into a rate · outcome (stated by the tagger, no quotation): held	`controls[0]`	0.85	the tagger's words
concepts	nuclear norm Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: nuclear norm	`concepts[3]`		the paper's words
concepts	incoherent Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: incoherent	`concepts[5]`		the paper's words
concepts	standard basis Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: standard basis	`concepts[6]`		the paper's words
concepts	rank minimization Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: rank minimization	`concepts[7]`		the paper's words
concepts	sampling operator Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: sampling operator	`concepts[8]`		the paper's words
senses	'exact' recovery - EXACT UNDER CONDITIONS, NOT IN GENERAL: recovery of the true matrix is proved for matrices incoherent with the standard basis and from a random sample, after the paper has stated that recovering ALL low-rank matrices is impossible, so the word describes the outcome when the hypotheses hold rather than the reach of the method 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	the nuclear norm - A HEURISTIC STANDING IN FOR RANK: the problem actually wanted is combinatorially hard, the nuclear norm is introduced as a heuristic optimisation, and the theorem is that the two coincide for most problems - so the method solves a different problem that usually has the same answer Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`senses[1]`	1.0	the tagger's words
senses	incoherence - THE HYPOTHESIS THE HEADLINE DEPENDS ON: the recoverable matrices are those whose row and column spaces are incoherent with the standard basis, a property nothing in an application guarantees and which the result cannot be quoted without Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`senses[2]`	1.0	the tagger's words
claim_relations	builds-on → convex optimization (nuclear-norm minimization) 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	extends → the theory of compressed sensing 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	builds-on → the nuclear norm heuristic introduced by Fazel [19] 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
claim_relations	extends → the notion of incoherence of a unitary transformation introduced in [9] Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[3]`		the tagger's words
concept_edges	nuclear norm —same-as→ rank minimization Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. holds when: for most problems, not for all · strength of the relation: 0.9 also in: nuclear norm · rank minimization	`concept_edges[0]`		the tagger's words
content_tags	m ≥ C·n^1.2·r·log n — sample complexity: entries sufficient to recover most rank-r n×n matrices Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.quantities[0]`		the tagger's words
content_tags	1.25 — replacing 1.2 with 1.25 makes the result hold for all ranks Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.quantities[1]`		the tagger's words
content_tags	matrix completion Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: matrix completion	`content_tags.definitions[0]`		the tagger's words
content_tags	nuclear norm minimization Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: nuclear norm minimization	`content_tags.definitions[1]`		the tagger's words
content_tags	chi-square Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: chi-square	`content_tags.statistics[0]`		the tagger's words
content_tags	degrees-of-freedom Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: degrees-of-freedom	`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. 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: sample-size	`content_tags.statistics[2]`		the tagger's words

Interpretive choices

Tags that could not be placed in the text:

content_tags.findings[0] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
NOT MACHINE-VOUCHED: declared-ellipsis - An elided quote: its 2 pieces ('We show that one can perfectly recover m' ... 'minimum nuclear norm that fits the data.') are each in our copy of the paper, and the quote marks the cut with an ellipsis, so the joined string is in no copy. Located mechanically, piece by piece.
content_tags.findings[1] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
NOT MACHINE-VOUCHED: declared-ellipsis - An elided quote: its 2 pieces ('Our notion of incoherence generalizes th' ... 'rs submit ratings on a subset of entries') are each in our copy of the paper, and the quote marks the cut with an ellipsis, so the joined string is in no copy. Located mechanically, piece by piece.
content_tags.statistics[3] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
NOT MACHINE-VOUCHED: not-in-our-copy - The quote is in the original web page we fetched for this paper, but not in the text we tag against, which was extracted differently. Checked with ligatures, hyphens, spacing and punctuation set aside.

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.