Exact Matrix Completion via Convex Optimization

Emmanuel J. Candes; Benjamin Recht

Source-linked AI summary

Exact Matrix Completion via Convex Optimization

Emmanuel J. Candes, Benjamin Recht

arXiv:0805.4471v1May 29, 2008cs.IT

TL;DR

Recovering a matrix from relatively few observed entries is challenging, especially when the matrix is low-rank. The paper shows that nuclear-norm minimization can exactly recover most such matrices from random samples, with very high probability under stated conditions.

Problem
The paper asks whether missing entries in a partially observed, potentially low-rank matrix can be recovered from comparatively few samples.
Method
It uses nuclear-norm minimization, a convex relaxation of rank minimization, to fit the observed entries.
Results
The method exactly recovers most incoherent low-rank matrices from random entry samples with probability at least 1−cn^-3.
Takeaways & Limitations
For most suitable low-rank matrix-completion problems, nuclear-norm relaxation is formally equivalent to the combinatorially hard rank-minimization approach.
Takeaways & Limitations
Matrices whose singular vectors are aligned with the standard basis may require observing nearly all entries for exact recovery.

Abstract

from arXiv · show

We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys m >= C n^{1.2} r log n for some positive numerical constant C, then with very high probability, most n by n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.

1 Introduction

The section introduces matrix completion as recovering missing entries from partial observations, emphasizing practical settings where the underlying matrix is low-rank or approximately low-rank. It motivates the problem through recommender systems, geometric triangulation, and covariance estimation.

Problem setting: Matrix completion seeks to recover a matrix from a sampling of its entries, including partially filled survey-response tables.The motivating survey example represents individuals as rows and questions as columns, with many unanswered questions.
Problem setting: Low-rank or approximately low-rank structure makes recovery from sampled entries relevant across practical applications.A matrix has rank r when its rows or columns span an r-dimensional space.
Applications: The Netflix problem involves inferring users’ preferences for unrated movies from sparse ratings to support recommendations.Users typically rate only very few movies, leaving scattered observed entries in the data matrix.
Applications: Triangulation from incomplete data reconstructs low-dimensional geometry using partial, noisy distance estimates between objects such as wireless sensors.Each sensor estimates distances from signal-strength readings involving its nearest fellow sensors.
Applications: Covariance matrices can also be recoverable from limited information when variables depend on a comparatively smaller number of factors.This provides another example of a matrix that may be low-rank or approximately low-rank.

1.1 Impediments and solutions

Entrywise matrix completion is impossible for adversarially sampled or highly concentrated low-rank matrices, but generic low-rank matrices can be exactly recovered from uniformly sampled entries using tractable nuclear-norm minimization.

Impediments: A rank-1 matrix concentrated in one entry is generally unrecoverable because most samples reveal only zeros, making it indistinguishable from the zero matrix.This shows that no method can recover every low-rank matrix from incomplete entry samples.
Model: Uniform random sampling is analyzed for generic low-rank matrices whose left and right singular-vector families are selected uniformly at random, without assumptions on singular values.The model excludes pathological alignment while allowing arbitrary singular values.
Impediments: At least one observation per row and column is necessary; otherwise an unobserved component can never be inferred.For rank-1 M = xy*, missing an entire row leaves the corresponding component of x unobserved.
Solution: Rank minimization captures the ideal recovery objective but is NP-hard, with exact known algorithms requiring doubly exponential time in matrix dimension.The paper therefore replaces rank minimization with nuclear-norm minimization, a convex program solvable efficiently via semidefinite programming.
Guarantee: n^6/5 entries suffice for ranks r = O(1) or r = O(log n), ignoring logarithmic factors, while recovery is exact with probability at least 1−cn^-3 under the theorem’s conditions.The nuclear-norm program uniquely recovers the matrix and is formally equivalent to rank minimization for most problems covered by the theorem.

1.2 Main results

Exact recovery by nuclear norm minimization is guaranteed for randomly sampled entries when a matrix’s row and column spaces are sufficiently incoherent with the standard basis. The theorem provides high-probability recovery bounds and includes random orthogonal and bounded-singular-vector models as examples.

Recovery conditions: Low coherence prevents a low-rank matrix from lying in the sampling operator’s null space, reducing the observations needed for exact recovery.Highly concentrated singular vectors can make recovery require nearly all entries, so both row and column spaces must be sufficiently spread relative to the standard basis.
Main theorem: Theorem 1.3 states that nuclear norm minimization uniquely recovers an n1×n2 rank-r matrix from uniformly sampled entries under assumptions A0 and A1.The success probability is at least 1 −cn^-β for β > 2 when the theorem’s sampling condition holds.
Main theorem: For r ≤µ0^-1 n1/5, the theorem gives an improved sampling estimate with the same success probability.The improved estimate applies in the stated low-rank regime.
Examples: Random orthogonal matrices with r > log n have µ(U), µ(V) = O(1) and µ1 = O(log n) with very large probability, so Theorem 1.1 follows as a special case.Exact recovery is then guaranteed when m satisfies the theorem’s sampling bounds (1.6) or (1.7).
Examples: If singular-vector components are bounded with µB = O(1), then µ(U), µ(V) ≤ µB and A1 holds most of the time with µ1 = O(√log n).For ranks not exceeding µB^-1, the corresponding sampling condition guarantees exact recovery.

1.3 Extensions

The main matrix-completion theorem extends beyond entry sampling to measurements in arbitrary orthonormal bases, including applications such as multiclass and multitask learning. The authors also expect analogous recovery from arbitrary linear functionals, but leave that general problem for future work.

Orthonormal-basis measurements: Theorem 1.3 extends to low-rank matrix completion when observations are inner products in two arbitrary orthonormal bases.The relevant rank-minimization problem uses bases (f_i) and (g_i) rather than canonical entry measurements.
Learning applications: Multiclass and multitask learning fit this framework because the class-specific classifier vectors are assumed to span a low-dimensional subspace.The associated classifier matrix is therefore low-rank and can be addressed through nuclear norm minimization under the theorem’s conditions.
Orthonormal-basis measurements: Nuclear norm minimization recovers the unique optimum from enough random basis measurements when the matrix’s column and row spaces are incoherent with the respective bases.The condition is applied to the transformed matrix F X G∗.
Arbitrary linear functionals: The results likely extend to observing a small number of uniformly random linear functionals from an orthonormal basis of matrix space.This formulation includes standard entry sampling as the canonical-basis case.
Arbitrary linear functionals: The general linear-functional recovery problem is left for future work, although matrices with small inner products against every basis element may be recoverable.The authors explicitly defer this broader formulation to avoid unnecessary confusion and notational clutter.

1.4 Connections, alternatives and prior art

The paper connects nuclear norm minimization to trace heuristics, semidefinite programming, and compressed sensing. It also contrasts the general approach with prior random-measurement results and a special sampling scheme that enables direct completion but has practical drawbacks.

Convex formulations: Nuclear norm minimization extends the trace heuristic and can be formulated as a semidefinite program, including for nonsymmetric general matrices.For positive semidefinite variables, the nuclear norm equals the trace; the formulation introduces auxiliary variables W1 and W2.
Connections to compressed sensing: The work extends compressed sensing beyond sparse signals and images to recovery of other structured objects from highly incomplete measurements.Its proofs combine compressed-sensing ideas with probabilistic tools, including operator-norm bounds associated with Bourgain and Rudelson.
Prior art: Prior work established sufficient conditions for nuclear norm recovery of minimum-rank solutions under Gaussian or Bernoulli linear measurements using restricted-isometry ideas.The measurement equations use independent random Gaussian or Bernoulli coefficients, rather than direct entry sampling.
Alternative recovery schemes: When every entry in r selected rows and columns is observed and the intersecting r × r block is invertible, a rank-r matrix can be completed directly from a block identity.The scheme generalizes to any r observed rows and columns with an invertible intersection, but its special sampling pattern creates practical drawbacks.

1.5 Notations and organization of the paper

This section defines the paper’s notation and outlines its proof architecture: establishing uniqueness via dual certificates, constructing those certificates, and relating them to subsequent results.

The paper first connects the random orthogonal and incoherent row- and column-space models to the assumptions of Theorem 1.3.
Section 3 establishes sufficient conditions for the true low-rank matrix M to be the unique solution to (1.5).
Section 4 constructs a dual vector with two crucial properties and gives the proof architecture showing these properties when measurements are sufficiently numerous.
Notations: Matrices use bold capitals, vectors bold lowercase, and scalars or entries nonbold; indexed notation identifies entries and vector components.
Notations: The paper defines spectral, Frobenius, nuclear, and maximum-entry matrix norms, along with the Euclidean inner product and vector ℓ2 norm.
Notations: Linear matrix operators use calligraphic letters, the identity operator is I, and operator size is measured by its spectral norm.

2 Which matrices are incoherent?

The section characterizes incoherence through size conditions on singular vectors and examines two models in which these conditions hold with high probability. Random sign patterns and random orthogonal models are shown to produce matrices suitable for recovery.

Incoherence conditions: Almost all matrices whose singular vectors have sufficiently small entries satisfy A0 and A1 with µ0 = µB and µ1 proportional to µB.A1 can fail when corresponding rows of the singular-vector matrices are identical.
Incoherent basis model: O(µB√log n): almost all sign sequences satisfy A1 at this scale when combined with singular vectors whose entries are bounded by µB/n.The incoherent basis model uses random signs and entrywise-bounded orthonormal singular vectors.
Incoherent basis model: CµB(β + 2) log n: incoherent-basis matrices obey A1 with probability at least 1 − cn^-β.This is stated for any β > 0 and numerical constants c and C.
Random orthogonal model: 1 − cn^-3 log n: the random orthogonal model satisfies the lemma’s incoherence bounds, including ∥P_{1≤k≤r} u_kv_k*∥∞ ≤ C log n√r̄/n.Here r̄ = max(r, log n).
Random orthogonal model: r ≥ C′(log n)^3: the random orthogonal model admits the sharper bound ∥P_{1≤k≤r} u_kv_k*∥∞ ≤ C√r log n/n.The improved estimate applies when r exceeds a constant multiple of (log n)^3.

3 Duality

The section characterizes nuclear-norm subgradients and derives a dual-certificate criterion for unique matrix recovery. Uniqueness follows when the sampling operator is injective on the tangent space and an appropriate dual point exists.

Subgradient characterization: Nuclear-norm subgradients at a rank-r matrix consist of the singular-vector component plus W, whose column and row spaces are orthogonal to the corresponding singular subspaces.The accompanying characterization also requires W to have spectral norm at most 1.
Uniqueness criterion: A feasible rank-r matrix is the unique minimizer if a dual point produces a nuclear-norm subgradient satisfying the stated certificate conditions and R_Ω is injective on T.The tangent space T has dimension r(n_1 + n_2 − r), matching the rank-r degrees of freedom.
Proof strategy: For M = Pr_k, recovery reduces to establishing tangent-space injectivity and constructing λ such that Y = R*Ωλ satisfies the dual certificate condition.This lemma is presented as the proof strategy for the paper’s main result.
Proof of uniqueness: The uniqueness proof analyzes feasible perturbations H with RΩ(H) = 0 and shows the nuclear norm strictly increases unless H lies in T.Injectivity on T then forces H = 0, proving strict uniqueness.

4 Architecture of the proof

The proof constructs a dual certificate Y supported on the observed entries and establishes the two conditions ensuring unique nuclear-norm recovery. It analyzes injectivity under Bernoulli sampling, then bounds the certificate’s orthogonal component by combining five lemmas to obtain the stated sample regimes.

Dual certificate construction: The candidate dual certificate Y is supported on Ω and chosen by least squares so that its projection onto T matches the target tangent-space component.Minimizing its Frobenius norm reduces to controlling the orthogonal component P_T⊥(Y), whose spectral norm must be below 1.
Sampling model: The proof replaces fixed-size uniform sampling with an independent Bernoulli model whose expected sample count is m, transferring failure bounds back to the uniform model.Under the Bernoulli model, the uniform-model failure probability is bounded by twice the Bernoulli-model failure probability.
Injectivity: Injectivity of A_ΩT is proved by showing that p^-1P_T(P_Ω−pI)P_T has small operator norm, making P_TP_ΩP_T invertible on T.This also makes the least-squares certificate well-defined and establishes the sampling injectivity condition.
Certificate norm bound: Five lemmas bound the terms in a power-series expansion of (P_TP_ΩP_T)^−1, together yielding ∥P_T⊥(Y)∥<1 with probability at least 1−cn^−β.This certificate bound supplies the remaining sufficient condition for exact recovery.
Sample regimes: When μ_0r≤n^3/4, the combined bounds yield exact recovery under the paper’s general sample condition; when μ_0r≤n^1/5, they simplify to the small-rank condition.The general and small-rank conclusions follow from different maxima of lemma-derived sample requirements.

5 Connections with Random Graph Theory

Random sampling must cover every row and column and connect the associated bipartite row–column graph for rank-1 recovery to be possible. These conditions correspond to injectivity of the sampling operator, which holds at the same order n log n sample scale as complete coverage and graph connectivity.

Coupon Collection: At least one observation per row and column is necessary for any rank-1 recovery method.With uniformly sampled entries, filling every row is the coupon collector’s problem, and the same requirement applies to columns.
Coupon Collection: An unobserved row or column creates a nontrivial null space in PΩ restricted to T, so PT PΩPT cannot be invertible.For an unobserved row, e_iv* lies in T and is annihilated by PΩ; the analogous construction applies to an unobserved column.
Coupon Collection: n log n samples are required to observe all rows with high probability, and Theorem 4.1 yields invertibility at the same order.Thus, the theorem’s logarithmic factors are unavoidable.
Bipartite Graph Connectivity: A disconnected bipartite graph of observed entries prevents rank-1 recovery because separate connected components do not determine the relative factors.Rows and columns form graph vertices, with an edge for each observed entry; disconnected components leave ambiguity between component-wise factors.
Bipartite Graph Connectivity: Graph disconnection produces a nontrivial null space of PΩ restricted to T, so invertibility of PT PΩPT implies full connectivity.Uniform sampling obtains a fully connected graph with large probability at order n log n samples, matching the theorem’s stronger invertibility property.

6 Proofs of the Critical Lemmas

Section 6 proves the critical lemmas underlying the recovery argument by combining moment bounds, noncommutative Khintchine, decoupling, and Bernstein inequalities. It establishes high-probability spectral-norm estimates for fixed matrices under coherence and sampling conditions, while noting possible logarithmic refinements are not pursued.

Proof setup: The proofs repeatedly reduce random operator bounds to spectral-norm estimates for auxiliary matrices in the square case, with rectangular extensions obtained by replacing n with min(n1, n2).The square-matrix presentation uses bounds that extend directly to rectangular matrices.
Lemma 4.4: The proof of the first critical bound uses symmetrization, Jensen’s inequality, the noncommutative Khintchine inequality, Schatten norms, and Markov’s inequality to control operator-norm tails.Schatten 1- and 2-norms coincide with the nuclear and Frobenius norms, respectively.
Lemma 4.4: Theorem 6.3 gives a reusable high-probability bound for a fixed n × n matrix, with probability at least 1 − n^−β when np ≥ β log n and β > 2.The theorem is derived without assumptions on the matrix E beyond a maximum-entry bound.
Proof limitations: A sharper upper bound without the logarithmic term might follow from random-matrix and concentration-of-measure results, but those refinements are left unexplored.Theorem 6.3 itself provides a large-deviation result for the largest singular value of an i.i.d.-entry matrix, sharp up to a stated qualification.

7 Numerical Experiments

Numerical experiments tested nuclear norm recovery across matrix sizes, ranks, and measurement counts, finding broader recovery regions for positive semidefinite matrices and Gaussian projections than for entry sampling.

Full matrices: 50 trials per (n, m, r) triple evaluated recovery of randomly generated rank-r matrices from uniformly sampled entries.Matrices were generated as products of two n × r Gaussian factors, and recovery required relative Frobenius error below 10^-3.
Positive semidefinite matrices: 50 trials per (n, m, r) triple evaluated recovery of random rank-r positive semidefinite matrices from uniformly sampled entries.The experiment used trace minimization with X ⪰ 0, and recovery required relative Frobenius error below 10^-3.
Positive semidefinite matrices: The recovery region was much larger for positive semidefinite matrices than for general matrices sampled by entries.The positive semidefinite experiment normalized measurements by D_n = n(n+1)/2 and used d_r = nr − r(r−1)/2 for the rank-r matrix dimension.
Gaussian projections: Gaussian projections produced a far larger recovery regime than entry sampling because each observation measures contributions from every matrix entry.The same nuclear norm program was used, with X ⪰ 0 additionally imposed in the positive semidefinite case.

8 Discussion

The discussion identifies the sample complexity achieved for exact recovery and outlines whether fewer measurements might suffice. It also proposes extending the framework to approximately low-rank matrices and noisy observations.

Measurement complexity: n^1.2r log n measurements suffice for exact recovery of rank-r n × n matrices when the rank is moderate.The paper asks whether exact recovery could be guaranteed with fewer measurements, given the matrix’s (2n − r)r degrees of freedom.
Measurement complexity: Higher-order terms in the series may be controllable with the same spectral-norm techniques, potentially enabling stronger recovery bounds.The analysis explicitly bounds the first four terms and uses a general argument for the remainder, while suggesting that higher-order terms could be treated similarly.
Approximately low-rank matrices: Approximately low-rank matrices cannot generally be completed exactly, motivating guarantees for recovering a good approximation from partial entries.The discussion focuses on matrices whose smaller singular values are small or negligible and compares recovery with truncated-SVD approximation.
Approximately low-rank matrices: The desired approximate-recovery guarantee is that the nuclear-norm error ||M⋆−M||* be comparable to the truncation error ||M−Mr||*.A similar comparison could also be considered in a different norm.
Robustness to noise: Noise robustness remains open: replacing exact fitting with ||PΩ(X − Y)||F ≤ ϵ should ideally yield recovery error proportional to the noise level.The proposed formulation minimizes the nuclear norm subject to a tolerance determined by the noise bound ϵ.

9 Appendix

The appendix develops concentration and deviation tools used in the paper’s proofs. It states a Talagrand-type inequality, applies it to the random variable Z, and supplements it with a Bernoulli moment lemma.

Concentration inequality: Talagrand’s concentration inequality is stated for suprema over a countable, sign-symmetric family of functions applied to independent Banach-space-valued variables.The setup defines Y⋆ using independent variables Y1, . . . , Yn and a family F satisfying f ∈ F implies −f ∈ F.
Concentration inequality: Theorem 9.1 assumes |f| ≤ B and E f(Yi) = 0, with the variance parameter σ2 defined as a supremum of summed second moments.The theorem applies for all t ≥ 0, while σ2 and the numerical constant K are specified in the surrounding passages.
Application to Z: The appendix applies Theorem 9.1 to the random variable Z from Theorem 4.2 using matrix families constrained by ∥X1∥F ≤ 1 and ∥X2∥F ≤ 1.The construction introduces Yab = p−1(δab − p) PT(…) and takes a supremum over the specified matrices.
Application to Z: B = 2µ0(nr/m) and t = λ are substituted into the concentration bound to establish the claim.The passage also notes n = max(n1, n2) and uses the inequality log(1+u) ≥ (log 2) min(1, u) for u ≥ 0.
Bernoulli deviation lemma: Lemma 9.2 introduces i.i.d. Bernoulli variables with P(δi = 1) = p and reduces the analysis to estimating a qth moment of a maximum.The subsequent argument uses integration by parts when q ≤ np and the condition nq e−np ≤ 1.