Matrix completion

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 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 2012.08496 §1.1 2012.08496 §3.8. Zero-filling the unobserved entries and dividing by p makes the surrogate unbiased for M* 2012.08496 §3.8. The rank r must be known; the monograph gives no rule for choosing it 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 2012.08496 §3.8. Card: Spectral Methods for Data Science.

Guarantees, for an incoherent M* with coherence μ and condition number κ 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*‖ 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⁻⁵) 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 2012.08496 §4.4.

The paper's constants are unstated, and the bounds are order statements 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* 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 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 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 2012.08496 §3.9.

When to use which

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.

# 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 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: monograph covering spectral matrix completion with subspace, Frobenius and entrywise bounds 2012.08496 §3.8 2012.08496 §4.4, and Gram-based tensor completion 2012.08496 §3.9.