PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-rank Matrix Completion using Alternating Minimization

Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi

arXiv:1212.0467v1stat.MLcs.LGmath.OC

TL;DR

The paper studies when alternating minimization can reliably recover low-rank matrices despite the non-convexity of bilinear factorization. It analyzes alternating minimization for matrix completion and matrix sensing, showing recovery under standard conditions with geometric convergence and a simpler analysis.

  • Problem

    Alternating minimization is widely used for low-rank recovery, but there has been almost no theoretical understanding of when it works.

  • Method

    The paper analyzes alternating minimization for matrix completion and matrix sensing, including least-squares factor updates and an analysis framework viewing the method as a perturbed power method.

  • Results

    Under standard RIP and incoherence conditions, alternating minimization recovers the true matrix for both problems and converges geometrically in O(log(1/ε)) steps for matrix sensing.

  • Takeaways & Limitations

    Alternating minimization provides global optimality guarantees with faster convergence, though possibly higher sample complexity than existing methods.

  • Takeaways & Limitations

    Matrix completion requires clipping, observed-set partitioning, and separate control of iterate incoherence, making its analysis more complicated.

Abstract

from arXiv · show

Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix Challenge. In the alternating minimization approach, the low-rank target matrix is written in a bi-linear form, i.e. $X = UV^†$; the algorithm then alternates between finding the best $U$ and the best $V$. Typically, each alternating step in isolation is convex and tractable. However the overall problem becomes non-convex and there has been almost no theoretical understanding of when this approach yields a good result. In this paper we present first theoretical analysis of the performance of alternating minimization for matrix completion, and the related problem of matrix sensing. For both these problems, celebrated recent results have shown that they become well-posed and tractable once certain (now standard) conditions are imposed on the problem. We show that alternating minimization also succeeds under similar conditions. Moreover, compared to existing results, our paper shows that alternating minimization guarantees faster (in particular, geometric) convergence to the true matrix, while allowing a simpler analysis.

1 Introduction

Low-rank matrices are parameterized bilinearly to reduce computation and support factor constraints, while alternating minimization makes each update tractable despite overall non-convexity. This paper addresses the limited theory for this approach in matrix completion and matrix sensing, showing recovery under comparable conditions.

  • Representing X as UV^† reduces optimization size when rank k is much smaller than m and n, which matters for massive matrices such as recommender systems.The factors U and V are substantially smaller than X and therefore more efficient to optimize.
  • Bilinear factorization also makes it easier to impose additional factor constraints, such as sparse U and V in sparse PCA.
  • Alternating minimization alternates between optimizing U and V; each fixed-factor subproblem is typically convex and efficiently solvable, although the joint problem is non-convex.
  • Matrix completion recovers a low-rank matrix from a small subset of entries, while matrix sensing recovers one from affine linear measurements.Matrix completion is a special case of matrix sensing in which each observed entry is a single-element measurement.
  • Without additional conditions, matrix completion and matrix sensing can be ill-posed, have multiple low-rank solutions, and be NP hard in general.The paper studies whether alternating minimization succeeds under conditions that make these problems well defined and tractable.

2 Our Results

The paper gives the first global-optimality guarantees for alternating minimization in matrix sensing and completion under standard assumptions. It establishes geometric convergence while identifying computational and sample-complexity trade-offs.

  • Contributions: Alternating minimization receives the first global-optimality guarantees for both matrix sensing and matrix completion under standard problem conditions.The sensing analysis uses matrix RIP, while completion relies on incoherence and random observations.
  • Matrix Sensing: AltMinSense alternates least-squares updates for U and V, initialized with the top-k left singular vectors of a measurement-derived matrix.Each factor update is a simple least-squares problem, while the initialization is crucial for convergence to the true subspace.
  • Matrix Sensing: O(log(1/ε)) steps yield geometric convergence of AltMinSense to the optimal solution under standard RIP assumptions.The theorem applies when the measurement operator satisfies an appropriate 2k-RIP condition.
  • Matrix Sensing: Stage-AltMin addresses a condition-number dependence that makes the required measurement count grow quadratically with κ.Its stagewise strategy removes dominant singular vectors sequentially and achieves a near-optimal measurement requirement.
  • Matrix Completion: AltMinComplete partitions observed entries across iterations and recovers incoherent matrices in O(log(1/ε)) steps under random sampling.The method modifies standard alternating minimization to simplify the analysis.

3 Related Work

The paper positions alternating minimization as a widely used, practical heuristic whose theoretical guarantees were largely absent, then presents scalable algorithms with geometric convergence under comparable conditions.

  • Alternating minimization is widely applied because it offers low-memory, fast, flexible, and parallelizable iterations.
  • Before this work, theoretical analysis largely provided only guarantees of convergence to local minima.
  • The paper analyzes alternating minimization for matrix completion and matrix sensing, two practically important low-rank recovery problems.
  • AltMinSense and AltMin-Completion achieve geometric convergence to optima while using relatively cheap iterations, making them more scalable for their respective problems.
  • The analysis requires conditions similar to existing algorithms, but its sample complexity depends on the underlying matrix condition number.

4 Matrix Sensing

For matrix sensing under RIP, the paper proves exact recovery by alternating minimization and analyzes its iterates as perturbed power-method updates whose subspace error decreases exponentially.

  • Under RIP, AltMinSense recovers the underlying low-rank matrix exactly.
  • Under RIP, alternating minimization behaves like a perturbed power method, with an error term that shrinks as iterates approach the true subspace.
  • The analysis measures progress using principal-angle distance between the subspaces spanned by iterates and the true singular-vector subspaces.
  • The distance between the iterated and true subspaces decreases exponentially with iteration count.
  • 4.1 Rank-1 Case: The rank-1 proof bounds the update error under 2-RIP and uses this bound to establish the contraction argument.
  • 4.2 Rank-k Case: For rank-k matrices, the proof represents updates as power-method-type steps with bounded decreasing error, using error-matrix lemmas and QR-based analysis iterates.

5 Matrix Completion

Matrix completion is analyzed under incoherence assumptions, with alternating minimization viewed as a perturbed power method whose iterates converge geometrically while preserving incoherence.

  • 5 Matrix Completion: AltMinComplete recovers the underlying matrix using O(n log n) measurements when k and σ∗ are constant.
  • 5 Matrix Completion: The analysis treats alternating minimization as a perturbed power method with controllable error under incoherence.
  • 5 Matrix Completion: Matrix completion requires clipping at initialization and partitioning observations across 2T + 1 sets for subsequent updates.
  • 5 Matrix Completion: The proof establishes geometric decay in distances between the iterates’ subspaces and the corresponding target subspaces.
  • 5 Matrix Completion: Initialization uses an SVD of PΩ(M) followed by clipping to obtain an iterate close enough to the target while maintaining incoherence.
  • 5 Matrix Completion: Each update preserves incoherence with high probability, enabling the induction used to prove convergence.

6 Stagewise AltMin Algorithm

Stage-AltMin addresses matrix sensing’s condition-number difficulty by solving progressively larger rank problems, yielding recovery guarantees with controlled stagewise error.

  • 6 Stagewise AltMin Algorithm: Large condition numbers make the direct measurement requirement significantly larger than the information-theoretic bound.
  • 6 Stagewise AltMin Algorithm: Stage-AltMin solves a rank-i problem at each of k stages to recover the top i singular vectors up to O(σ∗_{i+1}).
  • 6 Stagewise AltMin Algorithm: The method initializes each stage with one SVP step before applying alternating minimization.
  • 6 Stagewise AltMin Algorithm: Under δ2k ≤ 1/(10k), Stage-AltMin decreases the reconstruction error during each stage.
  • 6 Stagewise AltMin Algorithm: The stagewise proof combines initialization, error reduction, and induction across successive singular-value stages.

7 Summary and Discussion

The paper establishes global-optimality guarantees for alternating minimization in matrix completion and sensing, using a perturbed-power-method analysis under standard conditions.

  • 7 Summary and Discussion: For both matrix completion and matrix sensing, alternating minimization recovers the true matrix under conditions such as RIP and incoherence.
  • 7 Summary and Discussion: The analysis provides the first global-optimality guarantees for alternating-minimization algorithms in these two recovery problems.
  • 7 Summary and Discussion: The framework views alternating minimization as a perturbed power method and controls perturbations through RIP or incoherence.
  • 7 Summary and Discussion: The results indicate faster computational convergence but possibly higher statistical, or sample, complexity than existing algorithms.
  • 7 Summary and Discussion: The appendix supplies supporting tools including Bernstein’s inequality and an RIP-based result for incoherent matrices.
  • 7 Summary and Discussion: A trimming issue in a cited theorem is removed because the chosen sampling rate makes excessive row or column observations unlikely.

B Matrix Sensing: Proofs

The matrix-sensing proof rewrites alternating updates using RIP-based inner-product control and analyzes the resulting least-squares update equations.

  • B Matrix Sensing: Proofs: RIP implies approximate preservation of inner products between rank-k matrices, which is used throughout the sensing analysis.
  • B Matrix Sensing: Proofs: The proof bounds the resulting inequalities by decomposing rank at most 2k matrices and applying the RIP of the measurement operator.
  • B Matrix Sensing: Proofs: A scalar rescaling parameter can leave the left-hand side unchanged while altering the right-hand side, enabling optimization of the bound.
  • B Matrix Sensing: Proofs: The alternating update is derived from the first-order optimality condition of the least-squares objective.
  • B Matrix Sensing: Proofs: The update is expressed through blockwise matrix relations involving the sensing matrices and the current factor iterate.

B.1 Rank-1 Matrix Sensing: Proofs

The rank-1 matrix sensing proofs establish spectral and singular-value bounds under a 2k-RIP condition, then use these bounds to control alternating updates and subspace error.

  • Spectral-norm bounds are derived by testing matrices against arbitrary unit vectors and applying RIP.
  • The factor iterates are related through a full-rank change-of-basis matrix when their column spaces coincide.
  • The proofs assume the linear measurement operator satisfies RIP for rank-2k matrices.
  • The resulting bounds control minimum singular values and subspace distance across alternating updates.

B.3 Noisy Matrix Sensing: Proofs

The noisy matrix sensing proofs extend the exact-case analysis by separating measurement error from noise and bounding their effects on alternating updates.

  • The noisy model observes b = A(M + N), with recovery accuracy depending additively on the Frobenius norm of N.
  • Under the theorem’s conditions, after T = 4 log(2/ǫ) steps, the AltMinSense iterates satisfy the stated recovery bounds.
  • The noisy-case proof follows the exact-case proof while treating incomplete measurements and the noise matrix as separate error sources.
  • The update for bV t+1 decomposes into an exact-signal term and an additional noise error term G.
  • The analysis handles two cases according to the relationship between consecutive singular values, including a case where a small next singular value yields small effective noise.

C.1 Initialization: Proofs

The initialization proofs analyze an SVD-based starting point and a trimming step designed to preserve proximity to the target subspace and incoherence.

  • The initial factor U 0 is obtained from the singular vectors of a preliminary matrix and is shown to be close to U ∗ with high probability.
  • The resulting trimmed basis retains the desired proximity and incoherence properties.
  • The initialization guarantee requires a sampling condition of the form p > C′k^4 log n.
  • The trimming step sets overly large entries to zero before constructing an orthonormal basis eU.
  • The proof assumes U ∗ is incoherent and the input subspace is sufficiently close, with distance bounded by 1/64k.

C.2 Rank-1 Matrix Completion: Proofs

The rank-1 matrix completion proofs control sampled update terms using diagonal structure, concentration, incoherence, and spectral-norm bounds.

  • The resulting inequalities bound the update through spectral norms and complete the rank-1 completion proof.
  • The analysis assumes incoherence of v∗ and ut when bounding the sampled update error.
  • Bernstein’s inequality gives uniform concentration bounds for the sampled coordinate quantities Zj.
  • For rank-1 completion, sampled quantities are represented through diagonal matrices B and C, enabling coordinatewise bounds.
  • The sampling set is formed by independently including each matrix entry with probability p subject to a logarithmic lower bound.

C.3 General Rank-k Matrix Completion: Proofs

This section develops probabilistic bounds used in the rank-k matrix-completion analysis, including conditioning, norm control, and error-term estimates. The proofs repeatedly use incoherence, Bernstein’s inequality, and union bounds.

  • Application to the main lemma: The proof of Lemma 5.6 combines the preceding lemmas and separately bounds ∥B^−1∥_2 and ∥C_j∥_2 for error and incoherence analyses.The matrices U^t and U* are treated as orthonormal-column matrices in the supporting argument.
  • Proof setup: The proofs introduce vectorization and row- or column-wise representations to express matrix inequalities in Euclidean norm.They define x = vec(X) and distinguish columns and rows of X when bounding quadratic forms and error terms.
  • Conditioning bounds: The analysis bounds the smallest singular values of matrices B_j using concentration and incoherence arguments.With the stated choice of p, a union bound gives σmin(B_j) ≥ (1 − δ_2k) for every j with probability greater than 1 − 1/n^3.
  • Concentration lemmas: Lemma C.7 analyzes matrices C_j through bilinear forms involving arbitrary unit vectors and applies Bernstein’s inequality.The proof evaluates expectations and second moments for the relevant random variables before invoking concentration.
  • Error control: Lemma C.8 bounds the second part of an error term using auxiliary matrices B_jD − C_j, incoherence, and the distance between U^t and U* .The proof reduces the bound to a spectral norm expression and combines several prior inequalities, including Lemmas C.6 and C.7.
Loading 1212.0467v1…