Source-linked AI summary
Completing Any Low-rank Matrix, Provably
Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, Rachel Ward
TL;DR
Exact low-rank matrix completion guarantees had required incoherent row and column spaces under uniform sampling. This paper uses leverage-score-dependent sampling and shows that any rank-r matrix can be recovered with Θ(nr log^2 n) observations, while also giving extensions for unknown leverage scores and weighted minimization.
Problem
Prior exact-recovery guarantees generally required incoherent row and column spaces together with uniform random sampling, which can miss the mass of coherent matrices.
Source: §1 · p. 2Method
The paper samples entries with probabilities proportional to the sum of the corresponding row and column leverage scores and analyzes recovery using nuclear norm minimization.
Source: §1 · p. 2Results
Θ(nr log^2 n) observations suffice to recover any rank-r matrix with high probability under leverage-score sampling, which is necessary in a precise sense.
Source: §1 · p. 2Takeaways & Limitations
For unknown leverage scores, the paper gives a near-optimal scheme when one space is incoherent and a two-phase estimate-then-sample strategy for general matrices.
Source: §1 · pp. 2–3The necessity result has restrictions on the sampling distributions and the values of the leverage scores.
Source: §3.2 · p. 9
Abstract
from arXiv · showhide
Matrix completion, i.e., the exact and provable recovery of a low-rank matrix from a small subset of its elements, is currently only known to be possible if the matrix satisfies a restrictive structural constraint---known as {\em incoherence}---on its row and column spaces. In these cases, the subset of elements is sampled uniformly at random. In this paper, we show that {\em any} rank-$ r $ $ n$-by-$ n $ matrix can be exactly recovered from as few as $O(nr \log^2 n)$ randomly chosen elements, provided this random choice is made according to a {\em specific biased distribution}: the probability of any element being sampled should be proportional to the sum of the leverage scores of the corresponding row, and column. Perhaps equally important, we show that this specific form of sampling is nearly necessary, in a natural precise sense; this implies that other perhaps more intuitive sampling schemes fail. We further establish three ways to use the above result for the setting when leverage scores are not known \textit{a priori}: (a) a sampling strategy for the case when only one of the row or column spaces are incoherent, (b) a two-phase sampling procedure for general matrices that first samples to estimate leverage scores followed by sampling for exact recovery, and (c) an analysis showing the advantages of weighted nuclear/trace-norm minimization over the vanilla un-weighted formulation for the case of non-uniform sampling.
1. Introduction
Earlier guarantees paired uniform sampling with incoherence, which can miss most of a coherent matrix’s mass. The paper replaces that restriction with leverage-score-based sampling and develops extensions for unknown leverage scores and non-uniform sampling.
1. Introduction
- Uniform sampling can miss most of a coherent matrix’s mass, motivating recovery methods that adapt sampling to the matrix.Earlier sufficient conditions generally required both uniform random sampling and incoherent row and column spaces.Source: §1 · p. 2
- Θ(nr log^2 n) observations suffice to exactly recover any rank-r matrix with high probability under leverage-score sampling, and this sampling is necessary in a precise sense.Each entry’s sampling probability is proportional to the sum of its row and column leverage scores.Source: §1 · p. 2
- A matrix with an incoherent column space and arbitrary row space admits a near-optimal sampling scheme without prior leverage-score knowledge.The scheme uses the incoherent space to support sampling and leverage-score estimation.Source: §1 · p. 2
- A two-phase strategy first samples uniformly and then samples according to estimated leverage scores; numerical evidence shows performance on par with optimal sampling and better than uniform sampling.The strategy assumes no prior knowledge of the matrix’s leverage scores.Source: §1 · p. 3
- For non-uniform samples, the paper gives a weight-selection strategy that reduces weighted nuclear-norm sampling complexity to that of the unweighted formulation.It also provides the first exact recovery guarantee for weighted nuclear-norm minimization.Source: §1 · p. 3
- The analysis uses concentration bounds for a weighted ℓ∞,2 norm that captures the relative importance of matrix rows and columns.The authors expect these bounds to be relevant beyond the specific settings and algorithms considered.Source: §1 · p. 3
2. Related Work
Related work establishes exact completion guarantees mainly for incoherent matrices under uniform sampling, while neighboring areas use weighted sampling for other matrix and recovery problems. The paper places its leverage-score approach among these connections and outlines the later results.
2. Related Work
- Earlier exact-completion guarantees paired uniform random sampling with incoherent matrices, using nuclear norm minimization and other algorithms.The cited work also considers settings with sparse errors and additive noise.Source: §2 · p. 3
- Matrix sparsification samples individual entries by squared magnitude or magnitude, whereas column selection samples columns proportionally to statistical leverage scores.For matrix completion, the paper reports that leverage-score sampling outperforms ℓ1 and ℓ2 element-wise sampling theoretically and empirically.Source: §2 · p. 4
- Local-coherence sampling in compressed sensing provides a related approach for extending sparse-recovery guarantees beyond mutual incoherence.The passage describes applications in polynomial expansions, uncertainty quantification, spherical-harmonic interpolation, and MRI.Source: §2 · p. 4
- A prior row-coherent completion method observes entire columns and uses O(r^2 n log r) entries, quadratic in r.The paper’s cited comparison concerns a setting where only the row space may be coherent.Source: §2 · p. 4
2.1 Organization
- The paper presents coherent-matrix results in Section 3, a two-phase algorithm in Section 4, and weighted nuclear-norm guarantees in Section 5.Proofs of the main theorems are in the appendix.Source: §2.1 · p. 4
3. Main Results
The section establishes recovery guarantees for coherent matrices through sampling tied to leverage scores, then develops a knowledge-free strategy for a row-coherent setting and a precise necessity result for leveraged sampling.
3. Main Results
- Leveraged sampling makes the true matrix the unique nuclear-norm minimizer, with observations guided by the row and column leverage-score structure.Leverage scores are localized measures of incoherence; sampling more often in important rows and columns allows some discrepancy between the sampling distribution and the leverage pattern.Source: §3 · pp. 5–6
- The recovery guarantee matches the Θ(nr) degrees-of-freedom lower bound up to an O(log^2(n)) factor.The section also states an improvement for uniform sampling and uniform incoherence: its corollary removes the need for an extra joint-incoherence constraint.Source: §3 · pp. 6–7
3.1 Knowledge-Free Completion for Row Coherent Matrices
- When the column space is incoherent but the row space may be arbitrary, sampling selected rows estimates column leverage scores without prior leverage-score knowledge, enabling exact recovery.The procedure recovers the column leverage scores exactly with high probability and uses at most c1µ0rn log^2 n samples.Source: §3.1 · p. 7
3.2 Necessity of Leveraged Sampling
- The necessity result shows that, under its specified conditions, location-invariant sampling can leave distinct matrices indistinguishable, while leveraged sampling is sufficient up to logarithmic factors.The authors qualify the result: its sampling distributions and leverage-score values are restricted, though they argue it captures essential difficulties for coherent matrices.Source: §3.2 · pp. 8–9
4. A Two-Phase Sampling Procedure
The two-phase procedure estimates leverage scores from an initial uniform sample, then uses those estimates to guide the remaining samples. Experiments show it can approach oracle leveraged sampling in mild-to-moderate coherence, while outperforming uniform sampling for coherent matrices.
4. A Two-Phase Sampling Procedure
- The procedure spends βm samples uniformly to estimate leverage scores, then draws the remaining (1 −β)m samples using those estimates before nuclear norm minimization.The initial estimate is computed from a rank-r approximation of the uniformly sampled matrix.Source: §4 · pp. 9–10
- The initial uniform estimate can be poor for highly coherent matrices, whereas experiments suggest the procedure significantly outperforms uniform sampling for coherent matrices between the incoherent and highly coherent extremes.For incoherent matrices, the initial uniform samples alone can suffice for recovery.Source: §4 · p. 10
4.1 Numerical Experiments
- For α ≤0.7, estimated-leverage sampling has nearly the same sample complexity as oracle leveraged sampling; both recover with roughly 10n log(n) samples.For α > 0.6, uniform and element-based strategies degrade, and uniform sampling needs significantly more samples at higher α.Source: Figure 1 · p. 11, §4.1 · p. 11
- For coherent matrices, β between 0.5 and 0.8 gives the fewest samples for successful recovery, while β = 1 reduces to uniform sampling.Even with β = 0.9, using estimated leverage scores for the remaining 10% improves recovery over pure uniform sampling.Source: §4.1 · pp. 11–12
- The two-phase algorithm’s sample complexity appears to scale roughly as Θ(n log(n)) for power-law matrices with α = 0.5 and α = 0.7.A phase transition occurs at Θ(n log(n)) samples for each tested dimension.Source: Figure 3 · p. 12, §4.1 · p. 13
- With Gaussian noise levels σ = 0.1 and σ = 0.2, estimated-leverage sampling has error almost as low as exact leveraged sampling, while uniform sampling suffers dramatically.The comparison uses power-law matrices with α = 0.5 and α = 0.7.Source: §4.1 · p. 13
5. Weighted Nuclear Norm Minimization
For non-uniform observations, the paper analyzes weighted nuclear norm minimization by relating its weights to the leverage scores of a scaled matrix. The resulting guarantee permits heavily sampled rows and columns to assist less-sampled ones, unlike the unweighted condition.
5. Weighted Nuclear Norm Minimization
- The guarantee assumes a rank-r matrix satisfying the standard incoherence condition and applies when sampling probabilities have a product form.Theorem 7 states a sufficient condition for unique recovery with high probability under these assumptions.Source: §5 · pp. 14–15
- The weighted program is equivalent to completing the scaled matrix RMC with an unweighted problem, then rescaling the solution.The proof relates the scaled matrix’s leverage scores to the non-uniform observations.Source: §5 · p. 14
- Weighted nuclear norm minimization has a sufficient recovery condition that is less restrictive than the unweighted condition for non-uniform observations.Theorem 7 gives the first exact recovery guarantee for weighted nuclear norm minimization.Source: §5 · p. 15
- The weighted condition lets heavily sampled rows and columns assist less-sampled ones, unlike the unweighted condition, which constrains the least-sampled row and column.The benefit is most significant when observations are very non-uniform.Source: §5 · p. 15
Appendix A. Proof of Theorem 2
The proof uses convex duality to establish unique recovery by constructing a dual certificate. Its key departure from earlier analyses is to bound weighted row- and column-based norms rather than relying on unweighted elementwise bounds.
Appendix A. Proof of Theorem 2
- The analysis bounds a weighted ℓ∞,2 norm of the certificate instead of the ℓ∞ norm used in earlier proofs.The weighted norm is the maximum of weighted row and column norms.Source: Appendix A · pp. 16–17
- The proof reduces unique optimality to constructing a dual certificate that satisfies the required subgradient conditions.The certificate is supported on the observed entries and must also meet the conditions in Proposition 8.Source: Appendix A · pp. 16–17
- The weighted bounds yield a tighter bound on the certificate and therefore less restrictive conditions for matrix completion.The paper contrasts these bounds with standard and joint incoherence conditions involving uniform bounds by µ0 and µstr.Source: Appendix A · p. 16
- The dual certificate is constructed with the golfing scheme by splitting the observed set into k0 = 20 log n independent sampling rounds.The proof then checks the certificate conditions using concentration bounds for the weighted norms.Source: Appendix A · p. 17
A.1 Proof of Optimality Condition (Proposition 8)
Proposition 8 supplies a sufficient condition for unique optimality. The proof combines nuclear-norm subgradient duality with the certificate's support and projection conditions.
A.1 Proof of Optimality Condition (Proposition 8)
- A nuclear-norm subgradient and a dual certificate show that every feasible alternative has strictly larger objective unless it equals M.The argument uses PΩ(Y) = Y to make the certificate's inner product with a feasible difference vanish.Source: §A.1 · p. 20
- The proof uses ∥PT RΩPT − PT∥op ≤ 1/2 to rule out a nonzero feasible difference lying entirely in the tangent space.This condition is invoked to obtain the contradiction that completes the uniqueness argument.Source: §A.1 · p. 20
A.2 Proof of Technical Lemmas
The technical-lemma proofs rely on matrix Bernstein concentration and auxiliary facts about the matrix entries.
A.2 Proof of Technical Lemmas
- Four technical lemmas are used in the proof of the main theorem.Their proofs are presented using the matrix Bernstein inequality.Source: §A.2 · p. 21
- The proofs use the matrix Bernstein inequality to establish their concentration bounds.Source: §A.2 · p. 21
- The appendix also invokes additional facts stated for all row and column indices.Source: §A.2 · p. 21
A.2.1 Proof of Lemma 9
The four technical-lemma proofs use concentration arguments to control sampled matrix quantities, with matrix Bernstein bounds and union bounds appearing across the proofs.
A.2.1 Proof of Lemma 9
- The Sij are independent and mean-zero, and under the lemma’s condition their norm is at most 1/(c0 log n), when pij ≥ c0(µi+νj)r log n/n.Source: §A.2.1 · p. 21
A.2.2 Proof of Lemma 10
- Lemma 10 derives both stated bounds using the matrix Bernstein inequality.Source: §A.2.2 · p. 22
A.2.3 Proof of Lemma 11
- Lemma 11 controls row and column terms, applies matrix Bernstein, and takes a union bound over indices.The proof bounds weighted row and column norms of the sampled matrix.Source: §A.2.3 · pp. 22–24
A.2.4 Proof of Lemma 12
- Lemma 12 bounds four sums, applies Bernstein concentration, and uses a union bound over all index pairs.Source: §A.2.4 · pp. 25–26
Appendix B. Proof of Corollary 4
The proof shows that sampling rows can preserve the matrix's row space, allowing the leveraged-sampling recovery guarantee to apply. It also bounds the realized sample count around its expectation.
Appendix B. Proof of Corollary 4
- Sampling rows means selecting each row with probability p and observing all its elements.The proof uses this setup to establish that the sampled rows retain the matrix's row space.Source: Appendix B · p. 26
- The sampled rows have full rank and the same row space as the matrix, so applying Theorem 2 guarantees exact recovery.The proof states a recovery probability of at least 1 − 5n^-10.Source: Appendix B · p. 27
- The actual number of observations is at most twice its expectation with probability at least 1 − n^-10, for sufficiently large c0.The proof obtains this concentration bound using Hoeffding’s inequality.Source: Appendix B · p. 27
Appendix C. Proof of Theorem 6
The proof constructs rank-r matrices that satisfy the stated leverage-score constraints but agree on observed entries while differing on unobserved ones. This supplies a counterexample for the sampling scheme considered.
Appendix C. Proof of Theorem 6
- The first matrix is constructed as a rank-r block diagonal matrix with r blocks and disjoint column supports.Its construction uses orthonormal A and a matrix B with corresponding block supports.Source: Appendix C · p. 28
- A second rank-r matrix satisfies the leverage constraints yet differs from the first only on an unobserved block, leaving the observations unchanged.The construction also establishes that the second matrix belongs to the specified class.Source: Appendix C · p. 29
- The constructed matrices differ in 2n/(ν_j0 r) elements.The proof identifies this count with the size of the unobserved block.Source: Appendix C · p. 29
Appendix D. Proof of Theorem 7
The proof of Theorem 7 bounds leverage scores for a transformed matrix and applies Theorem 2 to an equivalent problem. The appendix also states the matrix Bernstein inequality used in the paper.
Appendix D. Proof of Theorem 7
- A constrained minimization is bounded by considering an extreme point of its feasible set.The proof uses this bound in its derivation for Theorem 7.Source: Appendix D · pp. 31–32
- The proof transforms the matrix to RMC, bounds the transformed leverage scores under the incoherence assumption, and applies Theorem 2 to the equivalent problem.The transformed column space is the column space of RU.Source: Appendix D · pp. 30–32
Appendix E. Matrix Bernstein Inequality
- The stated matrix Bernstein inequality assumes independent, zero-mean random matrices with an almost-sure bound on their norms.The appendix states the inequality for matrices in R^(n1×n2).Source: Appendix E · p. 32