PaperlayerView exact revision on arXiv

Source-linked AI summary

The Power of Convex Relaxation: Near-Optimal Matrix Completion

Emmanuel J. Candes, Terence Tao

arXiv:0903.1476v1cs.IT

TL;DR

The paper asks how many observed entries are needed to recover a low-rank matrix exactly, since completion is otherwise ill-posed. It analyzes nuclear-norm minimization as a tractable convex approach and shows that, under strong incoherence, it succeeds with sampling near the information-theoretic limit. The results establish exact recovery with high probability and no error for suitable randomly sampled entries.

  • Problem

    Matrix completion is ill-posed from partial observations, motivating bounds on the minimum samples needed for exact recovery of low-rank matrices.

  • Method

    The paper studies nuclear-norm minimization and uses dual certificates and matrix estimates to analyze when it exactly recovers the observed matrix.

  • Results

    Under strong incoherence and uniformly random sampling, nuclear-norm minimization recovers the matrix exactly with probability at least 1 − n^-3 when the stated sample condition holds.

  • Takeaways & Limitations

    Exact recovery occurs nearly as soon as it is information theoretically possible, making the near-optimal sampling results practical for low-rank matrix recovery.

  • Takeaways & Limitations

    The analysis does not address noisy observations; the authors defer the noisy matrix completion problem to later work.

Abstract

from arXiv · show

This paper is concerned with the problem of recovering an unknown matrix from a small fraction of its entries. This is known as the matrix completion problem, and comes up in a great number of applications, including the famous Netflix Prize and other similar questions in collaborative filtering. In general, accurate recovery of a matrix from a small number of entries is impossible; but the knowledge that the unknown matrix has low rank radically changes this premise, making the search for solutions meaningful. This paper presents optimality results quantifying the minimum number of entries needed to recover a matrix of rank r exactly by any method whatsoever (the information theoretic limit). More importantly, the paper shows that, under certain incoherence assumptions on the singular vectors of the matrix, recovery is possible by solving a convenient convex program as soon as the number of entries is on the order of the information theoretic limit (up to logarithmic factors). This convex program simply finds, among all matrices consistent with the observed entries, that with minimum nuclear norm. As an example, we show that on the order of nr log(n) samples are needed to recover a random n x n matrix of rank r by any method, and to be sure, nuclear norm minimization succeeds as soon as the number of entries is of the form nr polylog(n).

1 Introduction

Matrix completion is ill-posed without structural assumptions, but low rank makes exact recovery meaningful. This paper studies the sampling limits and shows nuclear-norm minimization can achieve near-optimal recovery under incoherence conditions.

  • Motivation: Matrix completion seeks to infer an entire matrix from a sampled subset of its entries, with applications including collaborative filtering and computer vision.Recommendation systems use partial user preferences to predict preferences for unrated items.
  • Motivation: Without assumptions on M, missing entries cannot be uniquely determined from the observed entries.The problem is therefore ill-posed when only PΩ(M) is available.
  • Minimal sampling: Low-rank structure makes recovery meaningful because only a limited number of factors contribute to the matrix.For an n × n rank-r matrix, at least 2nr − r^2 samples are required by degrees-of-freedom counting.
  • Minimal sampling: m < 2nr − r^2 makes exact completion impossible, while random observations require on the order of nr log n samples because of a coupon collector’s effect.Below the degrees-of-freedom threshold, infinitely many rank-at-most-r matrices can share the observed entries.
  • Convex relaxation: Rank minimization seeks the lowest-rank matrix consistent with the observations, but it is generally NP-hard and impractical for moderately large n.The paper instead studies nuclear norm minimization, which had been shown to enable exact recovery under low coherence.
  • Main contribution: nr polylog(n) samples suffice for nuclear norm minimization on useful matrix classes, approaching the information-theoretic nr log n scale.The paper gives a positive answer to whether convex recovery can approach the near-optimal sampling limit.

1.3 Main results

The paper develops incoherence-based conditions under which nuclear-norm minimization recovers low-rank matrices from nearly the minimum number of observed entries. Its main theorems establish high-probability exact recovery and improve the rank dependence of the sampling requirement.

  • Assumptions: Strong incoherence controls whether singular vectors are sufficiently spread out for efficient matrix completion.The property is defined through parameters µ1 and µ2 associated with the column and row spaces, both bounded by µ.
  • Assumptions: The assumptions constrain singular vectors but leave the singular values completely unrestricted.This follows from the geometry of the nuclear norm and its singular-value-independent subgradient.
  • Theorems: Nuclear-norm minimization exactly recovers every entry with high probability under strong incoherence and sufficiently many uniformly random samples.Theorem 1.1 states recovery with probability at least 1 − n^-3 for fixed bounded-rank matrices.
  • Theorems: For bounded-rank matrices with µ = O(1), exact nuclear-norm recovery occurs nearly at the information-theoretic limit of m ≥ c0 n log n samples.The result requires only a logarithmic-factor increase over the minimum possible sample count.
  • Theorems: The proof extends recovery beyond bounded rank and Theorem 1.2 replaces quadratic dependence on r with linear dependence.Theorem 1.2 is described as general and nonasymptotic.

1.4 A surprise

The paper finds nuclear-norm minimization unexpectedly effective: under suitable conditions, its performance nearly matches rank minimization despite being a convex relaxation. This parallels the compressed-sensing phenomenon for minimum ℓ1 norm.

  • A surprise: The convex relaxation is rigorously exact nearly as soon as the low-rank completion problem has a unique solution.The paper emphasizes that the gap between combinatorial rank minimization and convex optimization can be surprisingly small.
  • A surprise: The phenomenon parallels compressed sensing, where the sparsest solution can coincide with the solution having minimum ℓ1 norm.The analogy connects nuclear-norm minimization for matrices with ℓ1-norm minimization for underdetermined linear systems.

1.5 Model matrices

The paper develops several matrix models whose singular vectors are sufficiently spread out to satisfy strong incoherence and enable nuclear-norm recovery. These models yield exact recovery guarantees, while also exposing rank- and model-dependent limitations.

  • Model families: Uniformly bounded, low-rank low-coherence, and random orthogonal models provide examples with small strong incoherence parameters.The models rely on singular vectors with small components or random orthogonal structure.
  • Uniformly bounded model: Random selection and sign randomization of bounded orthonormal singular vectors establish strong incoherence with high probability.The analysis uses concentration inequalities and union bounds to control the relevant parameters.
  • Limitations: For large rank, bounded entrywise singular vectors alone do not ensure the required incoherence, so randomization and sign flips can be necessary.The Hadamard example has ∥u_k∥_ℓ∞ ≤ 1/√n but repeated rows prevent the desired scaling.
  • Low-rank low-coherence model: When r = O(1) and singular vectors are spread out with µB = O(1), the low-rank low-coherence model has strong incoherence parameter µ = O(1).Under these conditions, the paper applies its matrix-completion theorem to obtain exact recovery.
  • Random orthogonal model: For the random orthogonal model, the strong incoherence parameter is µ = O(log n), with logarithmic exponents improved when the rank is larger or bounded.The recovery guarantee holds with probability at least 1 − n^-3; the exponent 8 can be lowered to 7 for r ≥ log n and to 6 for r = O(1).
  • Limitations: The random orthogonal recovery condition is not substantially improvable in general, although specializing the proofs may reduce its logarithmic power.Reaching the optimal nr log n level may still require substantial additional work, even for bounded rank.

1.6 Comparison with other works

The paper contrasts its guarantees with earlier matrix-completion and compressed-sensing approaches. Its results improve an earlier incoherence bound and differ from other methods in assumptions, regimes, or measurement models.

  • Earlier incoherence results: Earlier work required µ0r ≤ n1/5 and therefore guaranteed recovery only when m ≥ C n6/5r log n.The comparison uses the earlier incoherence model and its stated sampling condition.
  • Earlier incoherence results: Under strong incoherence with µ = O(1), this paper needs only nr polylog(n) samples, improving the earlier bound in the minimal-sampling regime.The improvement is stated relative to the n6/5r log n requirement.
  • Parameter relationships: The paper relates incoherence and strong incoherence parameters in both directions, allowing results from one model to transfer to the other.The stated relationships involve µ0, µ1, µ2, and rank-dependent factors.
  • Compressed sensing: The compressed-sensing approach in uses Gaussian measurements, making its model completely different from matrix completion from observed entries.The paper therefore does not treat the two settings as directly comparable.
  • Alternative matrix-completion method: The approach in [13] achieves accurate recovery with order nr log n samples but is not directly comparable because it uses an asymptotic fixed-ratio regime and clustered singular values.This paper does not impose the same singular-value range assumption.

1.7 Lower bounds

The lower-bound result shows that coherence constrains what matrix completion can achieve information-theoretically. Below the stated threshold, distinct low-rank incoherent matrices can produce identical observations with nontrivial probability.

  • Lower-bound theorem: If the theorem’s sampling condition fails, distinct rank-at-most-r matrices with incoherence parameter µ0 can agree on all observed entries with probability at least δ.The observation pattern follows the Bernoulli model, with each entry sampled independently at probability p = m/n^2.
  • Information-theoretic impossibility: Because multiple candidates are consistent with the observations, no algorithm can be guaranteed to recover the matrix from PΩ(M) alone.This impossibility persists even when rank and coherence are known in advance.
  • Sampling scale: The necessary sample count is about the degrees of freedom multiplied by µ0 log n, making coherence directly determine the oversampling factor.A rank-r matrix has 2nr(1 − r/2n) degrees of freedom in the square setting.
  • Sampling models: The Bernoulli and uniform sampling models differ only by minor adjustments for the results discussed here.In the Bernoulli model, the number of observed entries concentrates sharply around its mean m.

1.8 Notation

The notation section fixes the paper’s matrix setting, asymptotic conventions, empty-set conventions, norms, and linear-operator notation. The main results are presented for square matrices with sufficiently large dimension.

  • Matrix setting: The paper works exclusively with square matrices for notational simplicity, while stating that non-square results follow by the same proof strategy.It sets n = max(n1, n2) for the non-square extension and assumes n is sufficiently large.
  • Standing assumptions: The analysis assumes m is at least 2nr.This is a standing sampling assumption used in the paper’s notation and results.
  • Norms: The paper uses spectral, Frobenius, Euclidean, and nuclear norms for matrices or vectors as appropriate.The nuclear norm is among the matrix norms used throughout the analysis.
  • Operators: Linear transformations on matrix space use calligraphic notation, with PΩ representing an observation operator and I denoting the identity operator.The operator identity is distinguished from the identity matrix.
  • Asymptotic notation: The paper uses O(·), ≲, and poly(·) for asymptotic bounds and related growth notation.These conventions express absolute-constant bounds and polynomial growth.
  • Set and sum conventions: Indicator functions, cardinalities, and empty-set conventions define how discrete expressions and sums are interpreted.Sums over an empty tuple are treated as trivial sums with one summand, unlike empty sums.

2 Lower bounds

The paper proves information-theoretic lower bounds showing that arbitrary low-rank matrices cannot be recovered unless random observations are sufficiently numerous. The argument uses matrices whose structure forces coverage of rows, columns, or diagonal blocks.

  • General lower bound: No method can recover every rank-r, coherence-µ0 matrix unless the number of random samples satisfies the paper’s lower-bound condition.The lower bound is first established for Bernoulli sampling and then transferred to uniform sampling with a fixed sample count.
  • Rank-one example: For rank one, recovery requires observing at least one entry in every relevant row or column.The proof constructs M=xy* with y=(1,...,1), so an unobserved row prevents recovery of the corresponding entries.
  • General rank: For general rank r, disjoint singular-vector supports create diagonal blocks that each require sampled entries for recovery.The construction uses supports of length ℓ=nµ0r and produces a block-diagonal matrix.

3 Strategy and Novelty

The recovery proof converts nuclear-norm optimality into the construction of a dual certificate, then controls that certificate using moment estimates for a normalized sampling operator. This strategy yields high-probability exact recovery under the paper’s incoherence assumptions.

  • Duality: A dual certificate together with injectivity of the sampling operator on the tangent space makes the true matrix the unique nuclear-norm minimizer.The certificate must match the tangent-space component and have controlled orthogonal-complement norm.
  • Certificate construction: The candidate certificate is chosen by solving a minimum-Frobenius-norm problem subject to the sampling and tangent-space constraints.This choice aims to keep the orthogonal-complement component small enough for spectral-norm control.
  • Operator expansion: The inverse sampling operator is expanded as a convergent Neumann series after normalizing the sampling operator to have mean zero.The resulting certificate reduces the proof to bounding spectral norms of powers of the normalized operator.
  • Key estimates: Moment estimates show that the candidate certificate satisfies the required norm bound with high probability under the two theorem assumptions.The paper obtains ∥P_T⊥(Y)∥≤1/2 with probability at least 1−n^-3, which implies the main recovery theorems.
  • Novelty: The paper’s novelty is to estimate the relevant spectral norms with moment methods rather than bounding each term of the certificate series separately.Raising the matrix to a large power reduces the problem to combinatorial path statistics, producing nearly optimal sampling bounds.

4 Moments

The moment analysis expands matrix expressions into weighted paths and then reorganizes them as combinatorial configurations. Independence and zero-mean factors eliminate configurations with singly visited pairs, leaving strongly admissible structures for counting.

  • Path expansion: The expansion of A^a0b0 is a sum over paths of length k+1 in [n]×[n], with horizontal, vertical, or non-rook moves.Vertices contribute ξ factors and the terminal vertex contributes an additional E factor, while edges contribute c factors.
  • Spider representation: The expansion of the moment trace is represented by a closed body path with 2j directed legs, forming a combinatorial spider.The body alternates horizontal and vertical rook moves, while the legs carry weights from the c, ξ, and E factors.
  • Configuration encoding: Coordinate overlaps are encoded by admissible pairs of sequences and injections that represent the same configuration inside [n]×[n].The sequences record equality patterns among horizontal and vertical coordinates, while the injections enumerate their grid representations.
  • Cancellation: Zero-mean independence removes terms in which any coordinate pair appears exactly once, so the remaining configurations are strongly admissible.Strong admissibility requires every element of the associated set Ω to be visited at least twice.

5 Quadratic bound in the rank

The first moment estimate obtains a quadratic dependence on the rank by bounding strongly admissible configurations through recycled coordinates and pair counting. An exponent bound and a counting lemma make the resulting series summable under the stated dimension condition.

  • Bounding the expansion: The quadratic-rank estimate starts by taking absolute values in the strongly admissible expansion and applying coefficient bounds.The argument then controls the resulting sum using combinatorial properties of the configurations.
  • Path structure: Non-rook moves are exactly the steps where both coordinates change, and they determine the set Q used in the exponent analysis.The set Q records indices whose path moves are neither horizontal nor vertical.
  • Recycling: Recycled and totally recycled triples track coordinate reuse, with Q′ collecting recycled triples among the relevant indices.These classifications measure how much a configuration’s coordinate identifications reduce its contribution.
  • Exponent control: The exponent bound gives |J|+|K|−|Q|−|Ω|≤−|Q′|+1 for every admissible tuple.The proof checks separately how recycled, totally recycled, and unrecycled triples change the exponent.
  • Pair counting: For fixed q=|Q′|, the number of strongly admissible pairs is at most O(j(k+1))^(2j(k+1)+q).The count follows by exposing sequence indices in lexicographic order and bounding choices according to the recycling case.
  • Conclusion: When n≥c0j(k+1), the resulting series can be summed to obtain the first moment bound.This completes the proof of the quadratic-rank estimate under the stated dimension condition.

6 Linear bound in the rank

Section 6 bounds generalized spider configurations by induction, simplifying configurations through guardedness, rook moves, and row or column reductions. The resulting summand estimate supports the paper’s linear-in-rank sampling analysis, though the logarithmic exponent is not optimal.

  • Configuration framework: Strongly admissible quadruplets encode generalized spiders whose non-rook moves occur only at positions in LU ∩ LV.The sets LU and LV determine which U and V factors appear in the expansion, while strong admissibility requires each vertex to be visited at least twice.
  • Summand estimate: X ≤ O(j(k + 1))^6j(k+1)(r/np)^j(k+1)n bounds the aggregate contribution after counting strongly admissible configurations.The estimate follows from the summand bound and crude counts of admissible pairs and (LU, LV ) choices.
  • Scope of the bound: The proof’s exponent 6 could likely be lowered, but reaching the optimal exponent 1 would require substantial additional effort.This limitation concerns the counting and analysis used to obtain the bound, not the validity of the stated estimate.
  • Inductive strategy: The proof uses nested induction on |J| + |K| and |LU ∩ LV |, treating fewer rows or columns and fewer non-rook opportunities as simpler configurations.The inner induction preserves the number of rows and columns, while the outer induction reduces their total and may introduce O(1 + |J| + |K|) terms.
  • Configuration reductions: An unguarded non-rook move is replaced by two rook moves, preserving XC while decreasing |LU ∩ LV | by one.The construction stretches the affected leg and increments subsequent labels so the transformed object remains a valid configuration.

7 Discussion

The discussion argues that the paper’s near-optimal sampling results are practically relevant because nuclear-norm minimization can be solved efficiently. It also identifies robustness to noisy observations as an important direction beyond the paper’s exact-recovery setting.

  • Practicality: Efficient algorithms for nuclear-norm minimization have solved instances with close to a billion unknown entries in minutes on a personal computer.The discussion cites singular-value thresholding as an example of such an algorithm.
  • Practicality: The near-optimal sampling results are therefore presented as practical for recovering low-rank matrices from few entries.Their practical relevance depends on the availability of efficient nuclear-norm minimization algorithms.
  • Open direction: The paper does not address noisy matrix completion, where observed low-rank entries contain a small amount of noise and recovery would be approximate rather than exact.The authors state that their methods may be amenable to this problem and defer progress to later work.

8 Appendix

The appendix transfers failure-probability bounds between Bernoulli and uniform sampling models and develops recurrence and operator estimates used in the analysis. These arguments preserve the main sampling conclusions up to minor probability adjustments.

  • Sampling-model transfer: A uniform sampling lower bound follows from the Bernoulli model by conditioning on the observed set’s cardinality.The conditional distribution of the sampled set given its size is uniform, enabling comparison of the two models.
  • Sampling-model transfer: Under the uniform model, the probability of failure is bounded by at most twice the corresponding Bernoulli-model probability.The appendix uses monotonicity of failure probability with respect to the number of observed entries.
  • Operator estimates: The appendix derives coefficient recurrences by expanding PT = QT + ρ′I and applying identities following from (3.13).Induction on k then establishes the recurrence relations for the coefficient sequences.
  • Operator estimates: Lemma 8.2 bounds the recurrence sequences geometrically when λ = ρ′/p < 1.The proof applies induction and uses the contraction conditions on ρ′ and p.
Loading 0903.1476v1…