PaperlayerView exact revision on arXiv

Source-linked AI summary

Matrix Completion from a Few Entries

Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh

arXiv:0901.3150v4cs.LGstat.ML

TL;DR

The paper asks when a limited set of observed ratings suffices to infer the missing entries of a low-rank matrix efficiently. It uses a spectral completion procedure that trims high-degree rows and columns, projects onto the leading rank-r subspace, and cleans residual errors. The method achieves small relative RMSE from O(nr) observations and exact recovery from O(n log n) observations for bounded rank, while leaving sharper RMSE and threshold characterizations as open problems.

  • Problem

    The paper asks whether known ratings provide sufficient information to infer unknown entries and whether this inference can be solved efficiently for massive datasets.

  • Method

    The algorithm trims high-degree rows and columns, projects the observed matrix onto its top r singular components, and cleans residual errors by minimizing a discrepancy function.

  • Results

    O(nr) random observations yield arbitrarily small relative RMSE, while bounded-rank matrices can be reconstructed exactly from O(n log n) observations.

  • Takeaways & Limitations

    The approach is efficient enough for large datasets and improves the spectral estimate through trimming and subsequent cleaning.

  • Takeaways & Limitations

    The RMSE decay suggested by simulations and quantitatively sharp exact-completion thresholds remain to be characterized.

Abstract

from arXiv · show

Let M be a random (alpha n) x n matrix of rank r<<n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M from |E| = O(rn) observed entries with relative root mean square error RMSE <= C(rn/|E|)^0.5 . Further, if r=O(1), M can be reconstructed exactly from |E| = O(n log(n)) entries. These results apply beyond random matrices to general low-rank incoherent matrices. This settles (in the case of bounded rank) a question left open by Candes and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(|E|r log(n)), which opens the way to its use for massive data sets. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices.

1 Introduction

The paper studies whether a small random set of ratings can support efficient low-rank matrix completion, and proposes a spectral algorithm with trimming and cleaning. It establishes near-optimal observation requirements, exact recovery for bounded rank, and practical computational complexity.

  • Motivation: Collaborative filtering asks whether known ratings provide enough information to infer unknown ratings and whether this inference can be performed efficiently.The efficiency question matters because real datasets are massive.
  • Model: The model assumes a rank-r rating matrix with incoherent, unstructured factors and a uniformly random observed-entry set E.The observed matrix M_E retains revealed entries and sets all others to zero.
  • Algorithm: Trimming removes rows and columns with unusually many observations before spectral projection, preventing concentrated singular vectors from dominating the estimate.The naive method performs poorly when |E|=Θ(n) because high-degree rows and columns create misleading singular directions.
  • Algorithm: Trimming makes the hidden rank-3 structure more apparent in singular-value distributions, especially when revealed-entry degrees have heavy tails.The figure compares spectra before and after trimming.
  • Algorithm: The algorithm trims M_E, keeps its top r singular components, and cleans residual errors by minimizing the discrepancy F(X,Y).The procedure requires only the first r singular vectors of a sparse matrix for its spectral projection.
  • Main results: O(nr) random observations yield arbitrarily small relative RMSE, while exact reconstruction requires O(n log n) observations for bounded rank and the cleaning step can converge to M.Theorem 1.1 is optimal in order because M has Θ(nr) degrees of freedom; the extra log n for bounded-rank exact completion reflects the coupon-collector requirement.

2 Incoherence property and some notations

The paper formalizes incoherence through conditions on the factor matrices U and V, fixes normalization conventions for U, V, and Σ, and specifies the random-observation model and notation used throughout.

  • Incoherence property: U and V are represented by their column vectors, with orthogonality and normalization absorbed into the diagonal matrix Σ.Σ is ordered as Σ1 ≥ Σ2 ≥ ··· ≥ Σr > 0.
  • Incoherence property: The matrices U, V, and Σ are called (µ0, µ1)-incoherent when they satisfy the paper’s stated incoherence properties.The assumptions differ from those in Candès and Recht only by normalization.
  • Assumptions: The second incoherence assumption A2 implies the bounded-entry condition with Mmax = µ1r^1/2.The paper defines high probability relative to uniformly random observations, with parameters bounded away from 0 and ∞ where required.
  • Observation model: The observed set E is uniformly random, and ε is defined from |E| relative to √mn; for square matrices, ε is the average number of revealed entries per row or column.An independent-entry observation model is also used, with equivalent guarantees up to a vanishing shift in ε.
  • Notation: The analysis assumes m ≥ n, so α ≥ 1, and uses standard Euclidean, Frobenius, operator-norm, scalar-product, and [N] notation.The transpose can be used when m < n.

3 Proof of Theorem 1.1 and technical results

The section analyzes the trimmed matrix’s singular spectrum and uses two technical lemmas to establish Theorem 1.1. The key result is that the trimmed spectrum preserves the signal structure of the full low-rank matrix.

  • The singular value decomposition is redefined using the trimmed matrix f ME rather than the original observed matrix ME.This trimming-based decomposition is the foundation for the subsequent spectral analysis.
  • The singular values of f ME are close to those of the full matrix M, apart from a trivial rescaling.
  • Lemma 3.1 provides the spectral estimate with probability larger than 1−1/n3.The supplied passage states the probability guarantee but omits the displayed bound itself.
  • The estimate generalizes a bound on the second eigenvalue of random graphs and makes the rank-3 structure visible in the spectrum of f ME.
  • Theorem 1.1 follows by combining Lemmas 3.1 and 3.2 through the triangle inequality and a Frobenius-norm bound for matrices of rank at most 2r.

4 Proof of Lemma 3.2

The proof of Lemma 3.2 controls the spectral error by discretizing unit vectors and separating light from heavy couples. Concentration handles light couples, while a sparse-graph discrepancy estimate handles heavy couples.

  • The proof reduces the spectral bound to discrete vector sets, controls light couples by a union bound, and controls heavy couples through graph discrepancy.
  • Light couples are treated with large-deviation estimates for a random variable Z and a union bound over discretized sets.
  • The trimmed row and column sets retain at least m−max{e−C1ǫm, C2α} and n−max{e−C1ǫn, C2} indices, respectively, with probability larger than 1−1/n4.
  • For sufficiently large C relative to √α, the remaining light-couple error probability has order e−Θ(n).
  • The heavy-couple contribution is bounded using a strengthened sparse bipartite-graph estimate, with probability larger than 1−1/2n3 for α≥1.

5 Proof of Lemma 3.1

This section applies the variational principle for singular values to subspaces orthogonal or parallel to previously selected singular vectors. Upper and lower bounds are obtained by complementary choices of subspace.

  • The variational principle for singular values is the central tool recalled in this section.
  • For the upper bound, the subspace is chosen as the orthogonal complement of span(v1, . . . , vq−1).
  • The lower bound is proved analogously using H = span(v1, . . . , vq).

6 Minimization on Grassmann manifolds and proof of Theorem 1.2

The paper minimizes its reconstruction cost over a product of Grassmann manifolds using regularized gradient descent. Local geometric and curvature results establish the behavior needed to prove Theorem 1.2.

  • 6 Minimization on Grassmann manifolds and proof of Theorem 1.2: The cost function F is defined on M(m,n) ≡ G(m,r) × G(n,r), where points represent pairs of r-dimensional subspaces.
  • 6 Minimization on Grassmann manifolds and proof of Theorem 1.2: The geodesic update can be evaluated in time O(nr), and standard step selection can replace explicit line minimization.
  • 6 Minimization on Grassmann manifolds and proof of Theorem 1.2: The gradient descent algorithm follows geodesics, minimizes a regularized cost along each geodesic, and constrains iterates to remain within distance γ of the initialization.
  • 6 Minimization on Grassmann manifolds and proof of Theorem 1.2: The regularization forces the iterates to remain incoherent, using row-norm constraints on the factor matrices.
  • 6 Minimization on Grassmann manifolds and proof of Theorem 1.2: In a sufficiently small neighborhood of the target u, F is well approximated by a parabola.
  • 6 Minimization on Grassmann manifolds and proof of Theorem 1.2: Within that neighborhood, F has no stationary point other than u, under the assumptions of Lemma 6.5 and with probability at least 1−1/n4.

7 Proof of Lemma 6.4

The proof establishes probabilistic bounds needed for Lemma 6.4 by controlling sparse-observation terms under incoherence and local-distance assumptions.

  • Probabilistic estimates: The proof uses Lemma 7.1 and incoherence to control terms involving the observed-entry operator and matrix factors.The resulting estimates invoke the sparse-matrix spectral bound and the inequality ||x′||2 ≤ ||x||2.
  • Degree control: For ǫ ≥ C1 log n, the maximum degree is bounded by a quantity of the same order as the average degree with high probability.The bound is stated with probability larger than 1 − 1/(2n^5).
  • Lower bound on F(x): A lower bound on F(x) is derived by separating its terms and bounding the absolute value of the fourth term.The argument introduces the matrix S realizing the minimum in Eq. (4).
  • Local control: For d(x, u) ≤ δ ≤ Σmin/(C0Σmax), the estimates imply the claimed local bound involving ||S − Σ||2.The proof combines upper and lower bounds and uses σmin(S)^2 and σmax(S)^2 estimates.

8 Proof of Lemma 6.5

The proof of Lemma 6.5 analyzes geodesic directions and gradient terms, showing that the main positive contribution dominates error terms in a sufficiently small neighborhood.

  • Geodesic construction: The geodesic velocity at x is expressed using the singular value decomposition of W, yielding an explicit formula for cW.An analogous expression is used for bZ, and both are compared with the original tangent directions.
  • Gradient bounds: For d(x, u) ≤ δ = Σmin/(C0Σmax), the proof lower bounds ⟨grad eF(x), bw⟩ and shows ⟨grad G(x), bw⟩ ≥ 0.Together, these inequalities imply the desired gradient bound by Cauchy–Schwarz.
  • Term decomposition: The inner product ⟨grad F(x), bw⟩ is decomposed into a main term A and error terms B1, B2, and B3.The proof proceeds by lower bounding A and upper bounding the three error groups.
  • Error control: B3 ≤ A/10, while the component bounds imply B2 ≤ A/10 and complete the required upper-bound estimates.The proof concludes under the stated δ and ǫ hypotheses.
  • Gradient of G: If ||X(i)||2 > 3µ0r, then the derived inner-product bound makes ⟨X(i), cW(i)⟩ positive.The argument uses a bound on ||X(i) − cW(i)|| and a sufficiently small δ.

A Proof of Remark 4.2

Remark 4.2 is proved by applying concentration bounds to the relevant events, with separate treatment of large and small ǫ.

  • Relation to prior work: The result is presented as a generalization of an analogous Friedman–Kahn–Szemerédi and Feige–Ofek result with a stronger probability statement.The stronger statement can be obtained using concentration-of-measure inequalities.
  • Concentration argument: The proof begins by applying a Chernoff bound to the event under consideration.The resulting probability estimate is used to control the event at scale 1/(2n^4).
  • Small-ǫ regime: For small ǫ, the proof uses the condition ǫ ≤ 3√α together with C2 ≥ 130.The argument also assumes ǫ ≥ 3√α, described as typically relevant.

B Proof of Remark 4.4

The proof of Remark 4.4 decomposes the contribution into light-couple and heavy-couple parts, controlling rows and columns outside the light sets.

  • Light couples: The light-couple contribution is analyzed under independent edge revelation with probability ǫ/√… .The passage identifies its expected contribution as the starting point for the bound.
  • Matrix decomposition: MA is formed by zeroing rows and columns of M whose indices are outside the light sets Al and Ar.This isolates the matrix portion associated with the selected light rows and columns.
  • Excluded indices: Entries of MA − M are nonzero only outside the light sets and are bounded in magnitude by Mmax.The sizes of the excluded row and column sets are controlled by δ.
  • Heavy couples: The heavy-couple contribution is bounded using the definition of heavy couples, and the two contributions are then summed.The proof explicitly invokes the heavy-couple definition for the second bound.

C Proof of Remark 4.5

The proof establishes a spectral bound by representing the sampling pattern as a bipartite graph and verifying bounded-degree and discrepancy properties. It partitions the terms into cases, bounds each contribution, and derives the required constant bound.

  • Graph properties: The matrix Q is associated with a bipartite graph G whose bounded-degree and discrepancy properties drive the proof.The discrepancy property compares observed edge counts with their expected counts for every pair of row and column subsets.
  • Discretization: The proof discretizes row and column coordinates into subsets A_i and B_j and tracks edge counts e_i,j against expectations μ_i,j.The partition is based on coordinate magnitudes, with e_i,j counting edges between A_i and B_j and μ_i,j giving the corresponding average count.
  • Case analysis: The remaining sum over α_iβ_jσ_i,j is bounded by splitting index pairs into cases governed by degree, discrepancy, and logarithmic conditions.The analysis explicitly partitions the proof into five cases and treats the C1 and C2 contributions separately.
  • Case analysis: 32ξ2/∆2 = O(1) bounds the contribution in one logarithmic case.This bound follows from an intermediate probability inequality together with Eq. (74).
  • High-probability property: The discrepancy property holds with probability at least 1 − 1/2n^3 for the trimmed adjacency matrix Q.Trimming cannot increase the number of edges between any two subsets, so the property transfers from the original random matrix graph Q0.
  • High-probability property: For the original random graph, the discrepancy condition holds with probability at least 1 − 1/2(mn)^p using ξ1 = 2e and ξ2 = (3p + 12)(α^1/2 + α^-1/2).Taking p = 3/2 under the assumption α ≥ 1 yields the stated high-probability result.

D Proof of remarks 6.1, 6.2 and 6.3

These remarks establish relationships among principal-angle distances and matrix distances, then control orthonormalization and row norms for a nearby matrix. The proof uses explicit minimization, singular-value bounds, and the triangle inequality.

  • Remarks 6.1 and 6.2: The distances d_c(X1, X2) and d_p(X1, X2) are expressed through the principal angles between the column spaces of X1 and X2.The formulas use 2 sin(θ/2) for d_c and sin θ for d_p, followed by elementary inequalities.
  • Orthonormalization: An orthonormal basis X′′ is formed as X′A, with A chosen symmetric, and its singular values are tracked through σ_i(A^-1).The construction preserves the distance bound d(U, X′) ≤ δ before the subsequent estimates.
  • Orthonormalization: The approximation error satisfies ||(U − X′Q1)^T(U − X′Q1)||_F ≤ nδ^2.This estimate appears in the comparison between X′ and the nearby orthonormalized representation.
  • Row-norm control: 3μ0 bounds every row norm of X′′, placing X′′ in K(3μ0).The proof then shows d(X′, X′′) ≤ 3δ and concludes using the triangle inequality.
  • Remark 6.3: The minimization over A is attained at A = Y^T V/n because the Frobenius-norm objective is quadratic.The resulting inequality follows by direct algebraic manipulation.
Loading 0901.3150v4…