| phenomenon | low-rank matrix completion— “Our main result (Theorem 1.3) extends to a variety of other low-rank matrix completion problems beyond the sampling of entries.” |
| claim-type | method— “In this paper, we consider an alternative which minimizes the sum of the singular values over the constraint set.” |
| method — evidence | — “To prove Theorem 1.3, we first establish sufficient conditions which guarantee that the true low-rank matrix M is the unique solution to (1.5) in Sect. 3.” |
| transfer | from compressive sampling in signal acquisition: 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— “Our work is inspired by results in the emerging field of compressive sampling or compressed sensing, a new paradigm for acquiring information about objects of interest from what appears to be a highly incomplete set of measurements [10, 12, 16].” | transfers[0] |
| mechanism | 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— “This is unfortunately of little practical use because this optimization problem is not only NP-hard, but all known algorithms which provide exact solutions require time doubly exponential in the dimension n of the matrix in both theory and practice [13]. If a matrix has rank r, then it has exactly r nonzero singular values so that the rank… | mechanisms[0] |
| mechanism | 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— “Whereas the rank function counts the number of nonvanishing singular values, the nuclear norm sums their amplitude and in some sense, is to the rank functional what the convex (cid:4)1 norm is to the counting (cid:4)0 norm in the area of sparse signal recovery.” | mechanisms[1] |
| mechanism | 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— “Note that for any subspace, the smallest μ(U ) can be is 1, achieved, for example, if U is spanned by vectors whose entries all have magnitude 1/ n. The largest possible value for μ(U ) is n/r which would correspond to any subspace that contains a standard basis element.” | mechanisms[2] |
| mechanism | 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— “Clearly, this matrix cannot be recovered from a sampling of its entries unless we pretty much see all the entries. The reason is that for most sampling sets, we would only get to see zeros so that we would have no way of guessing that the matrix is not zero.” | mechanisms[3] |
| mechanism | 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— “Then if we do not have samples from the first row, for example, one could never guess the value of the first component of x1 by any method whatsoever; no information about x1 is observed. There is of course nothing special about the first row and this argument extends to any row or column. To have any hope of recovering an unknown matrix, one… | mechanisms[4] |
| mechanism | 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— “We have just seen that if the sampling is adversarial, e.g., one observes all of the entries of M but those in the first row, then one would not even be able to recover matrices of rank 1. But what happens for most sampling sets? Can one recover a low-rank matrix from almost all sampling sets of cardinality m?” | mechanisms[5] |
| mechanism | 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— “A0 The coherences obey max(μ(U ), μ(V )) ≤ μ0 for some positive μ0.” | mechanisms[6] |
| mechanism | 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— “Indeed, when the matrix variable is symmetric and positive semidefinite, the nuclear norm of X is the sum of the (nonnegative) eigenvalues and thus equal to the trace of X. Hence, for positive semidefinite unknowns, (1.5) would simply minimize the trace over the constraint set:” | mechanisms[7] |
| builds-on | convex optimization (nuclear-norm minimization)— “finds the matrix with minimum nuclear norm that fits the data” | claim_relations[0] |
| extends | the theory of compressed sensing— “From this viewpoint, the results in this paper greatly extend the theory of compressed sensing by showing that other types of interesting objects or structures, beyond sparse signals and images, can be recovered from a limited set of measurements.” | claim_relations[1] |
| builds-on | the nuclear norm heuristic introduced by Fazel [19]— “Nuclear norm minimization is a recent heuristic introduced by Fazel in [19], and is an extension of the trace heuristic often used by the control community; see, e.g., [4, 28].” | claim_relations[2] |
| extends | the notion of incoherence of a unitary transformation introduced in [9]— “This paper generalizes the notion of incoherence to problems beyond the setting of sparse signal recovery.” | claim_relations[3] |
| sense | '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— “It is therefore impossible to recover all low-rank matrices from a set of sampled entries but can one recover most of them” | senses[0] |
| sense | 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— “In other words, for most problems, the nuclear norm relaxation is formally equivalent to the combinatorially hard rank minimization problem” | senses[1] |
| sense | 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— “if a matrix has row and column spaces that are incoherent with the standard basis, then nuclear norm minimization can recover this matrix from a random sampling of a small number of entries” | senses[2] |
| control | the whole recovery procedure repeated 50 times for every (n, m, r) triple — held — rules out a single lucky or unlucky draw of the sampled entries - 50 repetitions per parameter setting turn one outcome into a rate— “For each (n, m, r) triple, we repeated the following procedure 50 times.” | controls[0] |
| holds when | nuclear norm —same-as→ rank minimization — for most problems, not for all— “In other words, for most problems, the nuclear norm relaxation is formally equivalent to the combinatorially hard rank minimization problem”— “for most problems” | concept_edges[0] |
| weight | nuclear norm —same-as→ rank minimization — 0.9— “In other words, for most problems, the nuclear norm relaxation is formally equivalent to the combinatorially hard rank minimization problem” | concept_edges[0] |
| outcome (stated by the tagger, no quotation) | control — held | controls[0] |
| for which use | limitation — 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— “It would be of interest to extend our results to the case where the unknown matrix is approximately low-rank.” | limitations[0] |
| for which use | limitation — 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— “Interestingly, the experiments reveal very similar plots for different n, suggesting that our asymptotic conditions for recovery may be rather conservative.” | limitations[1] |
| for which use | limitation — 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— “Standard interior point methods will be impractical for problems where the unknown matrix has hundreds of rows or columns.” | limitations[2] |
| for which use | limitation — the general recovery problem: WE LEAVE THIS GENERAL LOW-RANK RECOVERY PROBLEM FOR FUTURE WORK— “To avoid unnecessary confusion and notational clutter, we leave this general low-rank recovery problem for future work.” | limitations[3] |
| for which use | limitation — 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— “It is therefore impossible to recover all low-rank matrices from a set of sampled entries but can one recover most of them” | limitations[4] |
| for which use | limitation — 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— “In other words, for most problems, the nuclear norm relaxation is formally equivalent to the combinatorially hard rank minimization problem” | limitations[5] |
| for which use | limitation — 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— “if a matrix has row and column spaces that are incoherent with the standard basis, then nuclear norm minimization can recover this matrix from a random sampling of a small number of entries” | limitations[6] |
| for which use | limitation — 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— “this optimization problem is not only NP-hard, but all known algorithms which provide exact solutions require time doubly exponential in the dimension” | limitations[7] |
| evidence status note | mechanism — 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.— “Whereas the rank function counts the number of nonvanishing singular values, the nuclear norm sums their amplitude and in some sense, is to the rank functional what the convex (cid:4)1 norm is to the counting (cid:4)0 norm in the area of sparse signal recovery.” | mechanisms[1] |
| evidence status note | mechanism — 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.— “Clearly, this matrix cannot be recovered from a sampling of its entries unless we pretty much see all the entries. The reason is that for most sampling sets, we would only get to see zeros so that we would have no way of guessing that the matrix is not zero.” | mechanisms[3] |
| replication | untested |
| limitation | The guarantee covers exactly low-rank matrices; extension to approximately low-rank matrices is left open.— “It would be of interest to extend our results to the case where the unknown matrix is approximately low-rank.” | limitations[0] |
| limitation | The sampling bounds proved may be far more demanding than what is needed in practice.— “Interestingly, the experiments reveal very similar plots for different n, suggesting that our asymptotic conditions for recovery may be rather conservative.” | limitations[1] |
| limitation | The semidefinite program the theory relies on does not scale with off-the-shelf solvers.— “Standard interior point methods will be impractical for problems where the unknown matrix has hundreds of rows or columns.” | limitations[2] |
| limitation | The general problem of recovery from arbitrary linear functionals is not treated.— “To avoid unnecessary confusion and notational clutter, we leave this general low-rank recovery problem for future work.” | limitations[3] |
| limitation | The paper states that the general problem is impossible and narrows the question before answering it.— “It is therefore impossible to recover all low-rank matrices from a set of sampled entries but can one recover most of them” | limitations[4] |
| limitation | The tractable method is a relaxation whose equivalence to the real problem holds for most instances, not all.— “In other words, for most problems, the nuclear norm relaxation is formally equivalent to the combinatorially hard rank minimization problem” | limitations[5] |
| limitation | The recovery guarantee holds only for matrices whose row and column spaces satisfy an incoherence condition.— “if a matrix has row and column spaces that are incoherent with the standard basis, then nuclear norm minimization can recover this matrix from a random sampling of a small number of entries” | limitations[6] |
| limitation | The exact-solution alternative is not merely slow but doubly exponential in the dimension.— “this optimization problem is not only NP-hard, but all known algorithms which provide exact solutions require time doubly exponential in the dimension” | limitations[7] |