---
kind: concept
slug: matrix-completion
title: Matrix completion
summary: >-
  Recovers a low-rank matrix from a random subset of its entries. Spectral completion rescales the observed entries by 1/p and takes a rank-r truncated SVD. It needs uniform sampling, incoherence and a known rank; the monograph gives subspace and Frobenius bounds, plus entrywise bounds for the same estimator.
tags: [low-rank, spectral-methods, missing-data]
papers: ["2012.08496"]
related: [spectral-clustering, leave-one-out-analysis, collaborative-filtering]
status: draft
updated_at: 2026-10-19
---

## Overview

The goal is to estimate a hidden matrix M* of rank r when only some of its
entries are observed. Each entry of M* is observed independently with
probability p, and the observed set is the sampling pattern [arxiv:2012.08496
§3.8]. The output is an estimate of the matrix, or of its row and column
subspaces [arxiv:2012.08496 §3.8].

**Shared structure.** Every variant builds a surrogate matrix from the observed
entries whose expectation is M*, then reads the estimate off its top singular
or eigen vectors [arxiv:2012.08496 §1.1] [arxiv:2012.08496 §3.8]. Zero-filling
the unobserved entries and dividing by p makes the surrogate unbiased for M*
[arxiv:2012.08496 §3.8]. The rank r must be known; the monograph gives no
rule for choosing it [arxiv:2012.08496 §3.8].

## Variants

The variants below differ in **the object being completed**: a two-way matrix
or a three-way tensor unfolded into a matrix.

### Spectral matrix completion

Zero the unobserved entries, divide the rest by p, and take the rank-r truncated
SVD of the result. The estimate is U Σ Vᵀ from that SVD [arxiv:2012.08496
§3.8]. This is the spectral method for matrix completion, which the monograph
credits to earlier work on spectral recovery from sampled matrices
[arxiv:2012.08496 §3.8]. Card: [Spectral Methods for Data Science](/papers/2012.08496).

Guarantees, for an incoherent M* with coherence μ and condition number κ
[arxiv:2012.08496 §3.8]:

- Subspace (ℓ2): with n₁p ≥ C₁κ²μr log n₂, the larger of the two subspace
  distances is at most a constant times κ√(μr log n₂ / (n₁p)) [arxiv:2012.08496
  §3.8].
- Matrix (Frobenius): with n₂p ≥ Cμr log n₂, the error ‖UΣVᵀ − M*‖_F is at most
  a constant times √(μr² log n₂ / (n₁p)) times the spectral norm ‖M*‖
  [arxiv:2012.08496 §3.8].
- Entrywise: the same estimator has row-wise (ℓ2,∞) and entrywise (ℓ∞) bounds
  under the stronger sample condition n₁p ≥ Cκ⁴μ²r² log n, with n = n₁ + n₂.
  The ℓ∞ bound is κ²μ²r²√(log n / (n₁³p)) times ‖M*‖, with probability at least
  1 − O(n⁻⁵) [arxiv:2012.08496 §4.4]. The monograph states these are about √n₁
  (row-wise) and n₁ (entrywise) times smaller than the ℓ2 bounds, as orders of
  magnitude [arxiv:2012.08496 §4.4].

The paper's constants are unstated, and the bounds are order statements
[arxiv:2012.08496 §1.3].

### Gram-based tensor completion

For an n×n×n tensor of rank r, unfold the tensor into an n × n² matrix A*
[arxiv:2012.08496 §3.9]. Form the Gram matrix of the observed unfolding, scale
it by p⁻², and set its diagonal to zero. The estimate is the span of the top r
eigenvectors [arxiv:2012.08496 §3.9]. The diagonal must be removed: at small p
it is large and not constant, and it would hide the low-rank part
[arxiv:2012.08496 §3.9]. This variant gives subspace guarantees only, with a
sample condition on p of order n^(−3/2) up to the μ, κ, r and log factors
[arxiv:2012.08496 §3.9].

## When to use which

| Situation | Use | Why |
|---|---|---|
| Two-way data, entries missing uniformly at random, rank r known | Spectral matrix completion | It is the variant with matrix guarantees in the monograph [arxiv:2012.08496 §3.8]. Needs p known for the 1/p rescaling [arxiv:2012.08496 §3.8]. |
| Rank is unknown | Not covered | No rank-selection rule is given; the analysis assumes r [arxiv:2012.08496 §3.8]. |
| Observed entries are not uniformly sampled | Not covered | Heterogeneous sampling patterns are listed as open [arxiv:2012.08496 §5]. |
| Mass concentrated on few entries or rows | Check incoherence first | A matrix with mass on a single entry can make recovery impossible without incoherence [arxiv:2012.08496 §3.8]. |
| Need the entrywise error, not only the subspace | Spectral matrix completion, entrywise analysis | Entrywise bounds hold for the same estimator, but they need the stronger sample condition [arxiv:2012.08496 §4.4]. |
| Three-way tensor, low rank under unfolding | Gram-based tensor completion | Subspace bound only [arxiv:2012.08496 §3.9]. Do not expect entrywise or Frobenius bounds from it. |
| Small p, few samples per row | Use the sample conditions as a check | Each bound needs n₁p or n₂p above a multiple of μr log n, so very sparse sampling falls outside the theory [arxiv:2012.08496 §3.8]. |

## Implementation sketch

Spectral matrix completion, in the form the monograph analyzes. The unbiasing
step and the truncated SVD are the whole method; there is no iteration.

```pseudocode
# Spectral matrix completion  [arxiv:2012.08496 §3.8]
# Input:  observed (n1, n2), mask (n1, n2) of 0/1 on the sampled set,
#         sampling probability p, target rank r
# Output: U (n1, r), Sigma (r, r), V (n2, r)

def spectral_complete(observed, mask, p, r):
    # Zero the unobserved entries and rescale by 1/p, so E[M] = M*  [§3.8]
    M = (observed * mask) / p
    # Rank-r truncated SVD of the rescaled matrix  [§3.8]
    U_full, s, Vt_full = svd(M, full_matrices=False)
    return U_full[:, :r], diag(s[:r]), Vt_full[:r, :].T
```

The estimate of M* is U Σ Vᵀ. For the tensor variant, replace the matrix
above with the zero-diagonal Gram matrix of the unfolding, scaled by p⁻²,
and take its top r eigenvectors [arxiv:2012.08496 §3.9].

## Contradictions

None known. The page rests on a single source, so there are no competing
results to compare.

## Papers

- [Spectral Methods for Data Science: A Statistical Perspective](/papers/2012.08496): monograph covering spectral matrix completion with subspace, Frobenius and entrywise bounds [arxiv:2012.08496 §3.8] [arxiv:2012.08496 §4.4], and Gram-based tensor completion [arxiv:2012.08496 §3.9].