PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding Alternating Minimization for Matrix Completion

Moritz Hardt

arXiv:1312.0925v4cs.LGcs.DSstat.ML

TL;DR

Alternating minimization is practical but has lacked strong theoretical guarantees because it is iterative and non-convex. This paper analyzes it through a robust noisy Power Method and smoothed QR framework, proving recovery from random entries under incoherence. The resulting method improves sample requirements, including for matrices close to low-rank in Frobenius norm, while retaining nearly linear-time behavior.

  • Problem

    Alternating minimization is empirically successful for matrix completion, but its recovery guarantees and theoretical behavior remain poorly understood.

  • Method

    The paper analyzes alternating minimization as a noisy Power Method and controls intermediate coherence using MedianLS and smoothed QR perturbations.

  • Results

    The algorithm provably recovers low-rank matrices from random subsamples under incoherence, with improved sample bounds that also apply to Frobenius-close low-rank matrices.

  • Takeaways & Limitations

    The analysis provides a theoretical justification for alternating minimization while preserving update costs linear in n+|Ω| up to logarithmic factors.

  • Takeaways & Limitations

    The guarantees assume incoherence and incur a factor O(k(∥M∥F/σk)2) loss relative to the information-theoretic measurement bound.

Abstract

from arXiv · show

Alternating Minimization is a widely used and empirically successful heuristic for matrix completion and related low-rank optimization problems. Theoretical guarantees for Alternating Minimization have been hard to come by and are still poorly understood. This is in part because the heuristic is iterative and non-convex in nature. We give a new algorithm based on Alternating Minimization that provably recovers an unknown low-rank matrix from a random subsample of its entries under a standard incoherence assumption. Our results reduce the sample size requirements of the Alternating Minimization approach by at least a quartic factor in the rank and the condition number of the unknown matrix. These improvements apply even if the matrix is only close to low-rank in the Frobenius norm. Our algorithm runs in nearly linear time in the dimension of the matrix and, in a broad range of parameters, gives the strongest sample bounds among all subquadratic time algorithms that we are aware of. Underlying our work is a new robust convergence analysis of the well-known Power Method for computing the dominant singular vectors of a matrix. This viewpoint leads to a conceptually simple understanding of Alternating Minimization. In addition, we contribute a new technique for controlling the coherence of intermediate solutions arising in iterative algorithms based on a smoothed analysis of the QR factorization. These techniques may be of interest beyond their application here.

1 Introduction

The paper develops a provable, efficient alternating-minimization framework for matrix completion, addressing the gap between practical speed and nuclear-norm recovery guarantees. Its analysis yields improved sample bounds, applies to approximately low-rank matrices, and controls convergence and intermediate coherence.

  • Approach: Alternating minimization updates one factor at a time through least squares, forming a tractable framework for non-convex low-rank optimization.Separating the factors makes each update computationally cheap and requires storing only 2k vectors.
  • Motivation: The paper addresses the lack of recovery guarantees for fast matrix-completion algorithms comparable to nuclear-norm minimization.Nuclear-norm methods have strong guarantees but require solving a semidefinite program, which is prohibitive for realistic instance sizes.
  • Results: At least k4(σ1/σk)4µ(U) improvement over Jain–Netrapalli–Sanghavi is obtained, while outperforming Keshavan when σ1/σk ≫ k1/3.The comparison concerns the stated sample-complexity bounds for alternating minimization.
  • Efficiency and analysis: The algorithm’s update cost is linear in n+|Ω| up to logarithmic factors, with exponentially fast convergence from logarithmic dependence on 1/ε.The analysis uses a noisy Power Method perspective, MedianLS, and smoothed QR perturbations to control convergence and coherence.
  • Results: For noisy matrices, the algorithm recovers a rank-k approximation in Frobenius norm under constraints on the residual N and singular-value separation.The theorem guarantees both approximate recovery of the dominant subspace and Frobenius reconstruction error.
  • Results: No dependence on the condition number is required for the stated Frobenius-error corollary when σ1 ⩾ kσk/ε.The resulting sample requirement is polynomial in k and coherence, and the paper states this is tight for k = O(1) up to constants.

2 Proof overview and techniques

The proof views alternating least squares as noisy subspace iteration and combines robust power-method convergence with smoothed QR orthonormalization to control errors and coherence.

  • Robust convergence of subspace iteration: The analysis models each least-squares update as a noisy power-method step, followed by orthonormalization.The update has the form Yℓ = AXℓ−1 + Gℓ, where Gℓ captures sampling or computation noise.
  • Robust convergence of subspace iteration: The convergence proof uses the tangent of the largest principal angle as a potential function.Under suitable noise conditions, the convergence rate is essentially (σk+1 + ∆)/(σk − ∆), with ∆ ≪ σk.
  • Least-squares updates: MedianLS computes O(log n) independent least-squares updates and takes their componentwise median to obtain stronger bounds on the update error.The error norm decreases as the iterates approach the target subspace, enabling near-exact recovery for rank at most k.
  • Initialization: The initialization procedure approximately computes the leading singular vectors of PΩ(A), then truncates them to avoid large coordinates.It produces X0 satisfying ∥V⊤X0∥ ≤ 1/4.
  • Smooth orthonormalization: Smoothed orthonormalization adds controlled Gaussian noise before QR factorization to avoid condition-number dependence when bounding iterate coherence.The analysis exploits that the noisy update already contains perturbations and places the iterate columns in a subspace of dimension at most 2k.
  • Putting things together: The final proof inductively maintains small coherence, uses matrix concentration to control noise, and applies smooth orthonormalization to preserve the invariant.The algorithm splits samples into independent pieces for iterative updates; its rectangular-matrix extension uses dilation.

3 Robust local convergence of subspace iteration

Noisy subspace iteration views each update as a power-method step perturbed by potentially adaptive noise. Under suitable initialization, spectral-gap, and noise conditions, principal-angle error contracts to the target accuracy.

  • Robust noisy iteration: Noisy subspace iteration computes Y_ℓ = AX_ℓ−1 + G_ℓ and orthonormalizes it to obtain X_ℓ.The perturbation G_ℓ may be adversarially and adaptively chosen in each round.
  • Principal-angle potential: The analysis tracks the tangent of the largest principal angle between the target subspace R(U) and the iterate R(X_ℓ).This quantity serves as the convergence potential.
  • Local convergence: Once the potential is at most ε, one step preserves the ε bound; when it lies in [ε,1/2], it decreases by a factor 1 − γ_k/2.These are the two local-convergence claims used in the iteration analysis.
  • Global convergence: If ∥V^⊤X_0∥⩽1/4 and the noise family is (ε/2)-admissible, then ∥V^⊤X_L∥⩽ε for any L ⩾ 4γ_k^-1.The admissibility condition accommodates shrinking error terms across iterations.

4 Least squares update rule

The least-squares update is rewritten as a noisy matrix-power step, Y = AX + G. Median aggregation strengthens row-wise concentration so that all rows satisfy the desired error bound simultaneously.

  • Least squares update: The least-squares optimizer satisfies linear equations derived from the gradient of the sampled reconstruction objective.For each row, the update uses B_i = X^⊤P_iX when B_i is invertible.
  • Noisy power-method form: The update can be expressed as Y = AX + G, with G decomposed into matrix and noise contributions G_M + G_N.This form enables the noisy subspace-iteration analysis.
  • Deviation analysis: Fresh independent samples make the current update analyzable conditional on the history generating X.The row-wise error is controlled through concentration bounds for the sampling projections.
  • Median update: Component-wise medians of independent least-squares solutions yield a strong concentration bound for every row simultaneously.Using t = O(log n) samples permits a union bound over all n rows.

5 Incoherence via smooth QR factorization

SmoothQR controls the coherence of intermediate iterates by adding calibrated Gaussian noise before orthonormalization. Its analysis uses Gaussian perturbations to ensure conditioning and bounds both coherence and injected error.

  • Motivation: Direct QR factorization can produce a high-coherence iterate when Y_ℓ is ill-conditioned.SmoothQR addresses this by perturbing Y_ℓ before orthonormalization.
  • Noise calibration: The noise level is selected by binary search because the norm of the least-squares error G_ℓ is unknown.The added noise is intended to have limited effect when its norm is bounded by the existing error.
  • Gaussian conditioning: A Gaussian perturbation ensures the projected matrix has smallest singular value at least Ω(τ) with probability 1 − exp(−Ω(n)).The guarantee assumes k = o(n/log n) and bounded input norm.
  • SmoothQR guarantee: SmoothQR outputs X′ with coherence at most µ while bounding the perturbation H by ∥H∥⩽τν.It terminates in O(log(n/ε)) steps with probability 1 − O(n^-4).

6 Convergence bounds for alternating minimization

The convergence theorem combines initialization, median least squares, and SmoothQR under a sampling condition p ≳ p_init + p_LS. It yields rapid convergence and Frobenius reconstruction guarantees.

  • Sample complexity: The total sampling requirement is the sum of initialization samples and samples used for least-squares iterations.The theorem requires p ≳ p_init + p_LS.
  • Reconstruction error: The output satisfies ∥M − XY^⊤∥_F⩽ε∥A∥_F with probability 9/10.This is the Frobenius-norm reconstruction consequence of the subspace guarantee.
  • Proof strategy: The proof maintains admissible sampling error and coherence inductively while SmoothQR controls the additional perturbation at every iteration.The argument sums failure probabilities over at most L⩽n steps.

7 Finding a good starting point

The initialization procedure computes approximate top singular vectors from the observed matrix, randomly rotates and truncates them to enforce incoherence, and returns a starting subspace close to the target.

  • 7 Finding a good starting point: The procedure computes the top k singular vectors of P_Ω(A) and truncates them to ensure incoherence.It is used as a fast initialization procedure for the main algorithm.
  • 7 Finding a good starting point: A random orthonormal transformation spreads singular-vector entries before truncation, yielding a tighter coherence bound than previous approaches.The rotation is applied before truncation rather than truncating the unrotated vectors directly.
  • 7 Finding a good starting point: The initialization input consists of the target dimension k, observed indices Ω, observed entries PΩ(A), and coherence parameter µ.The procedure is defined for an unknown symmetric matrix A.
  • 7 Finding a good starting point: With probability 9/10, Initialize returns an orthonormal X satisfying ∥V ⊤X∥F ⩽1/4 and µ(X) ⩽32µ(U)logn.The guarantee gives both proximity to the target singular subspace and controlled coherence.
  • 7 Finding a good starting point: Approximate singular-value decomposition suffices, with the k-th singular value computed to accuracy γkσk/100k using Power Method iterations.The text states that the running time of this step is dominated by the running time of LS.
  • 7 Finding a good starting point: The initialization analysis uses a spectral separation argument to bound the distance between the observed matrix's and target matrix's singular subspaces.The Davis–Kahan bound gives ∥V ⊤W ∥ ⩽ 2ε/(γkσk).

A Large deviation bounds

This appendix section introduces matrix concentration tools used to control random-matrix deviations and eigenvalue behavior.

  • A Large deviation bounds: The appendix directs readers to existing background for the matrix concentration inequalities used in the analysis.The cited background reference is Tro.
  • A Large deviation bounds: Matrix Bernstein applies to independent mean-zero random matrices with bounded operator norm.The stated setup uses dimensions d1 × d2 and an almost-sure bound R.
  • A Large deviation bounds: Matrix Chernoff applies to independent positive semidefinite self-adjoint matrices with bounded largest eigenvalue.The theorem is stated for matrices of dimension d and bound R.

A.1 Error bounds for initialization

This appendix section analyzes the error introduced when a matrix is estimated from independently sampled entries.

  • A.1 Error bounds for initialization: Lemma A.3 considers a random subset Ω formed by independently including each entry with probability p.It applies to a general matrix A ∈ R^{m×n}.
  • A.1 Error bounds for initialization: The proof represents PΩ(A) − A as a sum of independent random matrices using Bernoulli sampling variables.Each ξij indicates whether entry (i,j) belongs to Ω.
  • A.1 Error bounds for initialization: The lemma's conclusion is obtained by applying Matrix Bernstein to the sampled-entry deviation.The proof then uses the expectation of the sampling operator and an entrywise bound on A.

A.2 Error bounds for least squares

This appendix section develops probabilistic bounds for sampled least-squares systems and their interaction with incoherent orthonormal factors.

  • A.2 Error bounds for least squares: Lemma A.4 assumes an incoherent fixed orthonormal matrix X and samples coordinates independently with probability p.Its setup includes a target failure parameter δ and a coordinate index i.
  • A.2 Error bounds for least squares: The sampled Gram matrix B is formed from independent Bernoulli-weighted row outer products and satisfies E[B] = I_k.The proof lower-bounds λ_min(B) using Matrix Chernoff.
  • A.2 Error bounds for least squares: The analysis bounds the probability that λ_min(B) falls below 1 − δ by k exp(−10logn).This probability estimate follows from the stated sampling condition and Matrix Chernoff.
  • A.2 Error bounds for least squares: A separate lemma studies diagonal Bernoulli rescaling P applied to a vector z orthogonal to the columns of X.The proof centers the rescaling through D = P − I and uses independence of its diagonal entries.
  • A.2 Error bounds for least squares: Markov's inequality is used to convert the resulting moment calculation into a probabilistic bound.The supplied proof excerpt ends at this step.

B Additional lemmas and proofs for smooth QR factorization

The appendix establishes technical bounds used in the paper’s main convergence arguments, including Gaussian projection behavior, coherence control, and subspace coherence relations.

  • Gaussian projection bounds: A Gaussian perturbation remains well-conditioned after projection: σ_k(P_V(G + H)) ⩾ Ω(τ) with probability 1 − exp(−Ω(n)).The proof combines Gaussian concentration with a net argument over the unit sphere.
  • Coherence control: For H ∼ N(0,1/n)^(n×k), the projected matrix satisfies ρ(PH) ⩽ O(log n) with probability 1 − 1/n^5.The argument bounds the row norms of H and the spectral norm of U^⊤H.
  • Subspace coherence: If R(X) ⊆ R(Y), then the coherence of X is bounded by the dimension of Y: µ(X) ⩽ k′.This relation is used as a direct subspace-coherence comparison.
  • Theorem 6.1 support: The appendix applies a technical lemma under Theorem 6.1’s assumptions to bound ρ(NX_{ℓ−1})/ν^2 by µ* for every ℓ ∈ [L].The proof invokes the lower bound on p and Equation 2 to finish the bound.

C Splitting up the subsample

The appendix provides a sample-splitting procedure that converts one Bernoulli subsample into independent lower-density subsamples, and reduces rectangular matrices to symmetric ones for analysis.

  • Sample splitting: Split(Ω,t) outputs independent samples Ω_1,...,Ω_t, each including every entry independently with probability p_i ⩾ p/t.This preserves the distributional assumption required by later arguments.
  • Sample splitting: The construction simulates the split by assigning sampled entries, including multiplicities, to random subsets of the t output sets.The resulting union has the required multiplicity distribution while producing the independent outputs.
  • Symmetric reduction: A rectangular matrix B can be embedded into a symmetric matrix A whose rank is 2·rank(B), with each singular value of B repeated twice.The corresponding singular vectors encode the left and right singular spaces of B.
  • Symmetric reduction: A rank-2k approximation to A yields a rank-2k approximation to B with the same error, while the top singular spaces preserve the relevant left-right structure.The reduction defines the top-2k space of A from the top-k left and right spaces of B.
  • Implementation details: The rectangular aspect ratio can be kept constant by splitting B into m × O(m) blocks and recovering the blocks separately.A uniform subsample of B is transferred to A by splitting observations between B and B^⊤.
Loading 1312.0925v4…