Source-linked AI summary
Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
Qinqing Zheng, John Lafferty
TL;DR
The paper addresses rectangular matrix completion by seeking global recovery guarantees for a low-rank matrix from incomplete observations. It lifts the matrix to a positive semidefinite matrix, factors the lift, and applies gradient descent to a regularized nonconvex objective. With O(μr^2κ^2n max(μ, log n)) random observations, the method linearly converges to the global optimum with high probability, while removing the column-space regularizer can lead to a different lifted solution.
Problem
Rectangular matrix completion requires recovering a low-rank matrix from incomplete observations, while identifiability and tractable globally convergent algorithms are difficult because the problem is generally NP-hard.
Method
The method lifts X⋆ to a higher-dimensional positive semidefinite matrix, factors the lift, initializes spectrally, and applies projected gradient descent to a regularized nonconvex objective.
Results
With O(μr^2κ^2n max(μ, log n)) random observations, the algorithm linearly converges to the global optimum with high probability.
Takeaways & Limitations
The analysis extends successful Burer–Monteiro applications to rectangular matrix completion and provides empirical evidence that the algorithm is fast and scalable.
Takeaways & Limitations
The column-space regularizer is needed for the analysis; when λ = 0, the algorithm typically converges to another positive semidefinite lifting differing in the top-left and bottom-right blocks.
Abstract
from arXiv · showhide
We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple gradient descent scheme. With $O( μr^2 κ^2 n \max(μ, \log n))$ random observations of a $n_1 \times n_2$ $μ$-incoherent matrix of rank $r$ and condition number $κ$, where $n = \max(n_1, n_2)$, the algorithm linearly converges to the global optimum with high probability.
1 Introduction
The paper studies whether Burer–Monteiro factorization and gradient descent can provide tractable global convergence guarantees for rectangular matrix completion, a generally NP-hard problem. It lifts the matrix-completion task to a higher-dimensional positive semidefinite factorization and analyzes the resulting nonconvex optimization.
- Approach: Burer–Monteiro methods factor a semidefinite variable and optimize the resulting nonconvex objective over the factor.Prior work showed this strategy can be effective for several practically important problems despite worst-case limitations.
- Problem setting: Rectangular matrix completion seeks to recover a low-rank matrix from a small fraction of observed entries.The target rank satisfies r ≪ min(n1, n2).
- Motivation: Identifiability and uniqueness are necessary for the true matrix to be recoverable from incomplete observations.The paper emphasizes identifying when X⋆ is the unique minimizer of the matrix-completion objective.
- Motivation: Because matrix completion is generally NP-hard, the paper seeks tractable instance families and efficient algorithms with global convergence guarantees.
- Approach: The paper lifts X⋆ to a positive semidefinite matrix Y⋆, factors it as Y⋆ = Z⋆Z⋆ᵀ, and applies gradient descent with spectral initialization.The analysis establishes sufficient measurement conditions for identifiability and geometric convergence with explicit rate bounds.
2 Semidefinite Lifting, Factorization, and Gradient Descent
The method converts rectangular matrix completion into constrained optimization over a factor of a lifted positive semidefinite matrix. It uses incoherence assumptions, spectral initialization, column-space regularization, and projected gradient descent, while noting a limitation when the regularizer is removed.
- Assumptions: The analysis assumes an incoherent target matrix and studies uniform observations through an equivalent Bernoulli sampling model.The Bernoulli model observes each entry with probability p = m/(n1n2), and results transfer to uniform sampling.
- Semidefinite lifting: The lifted factorization seeks a factor equivalent to Z⋆ up to an orthogonal transformation.The symmetric decomposition is nonunique, so the target solution is an equivalence class of factors.
- Regularization: Because observations constrain only the off-diagonal block, the lifted problem has extra minimizers beyond the matrices of direct interest.The method adds a column-space regularizer to align the top and bottom factor blocks and focus analysis on Y⋆.
- Regularization: The analysis establishes that λ = 1/2 yields linear convergence, allowing the regularization parameter to be treated as fixed.
- Optimization: Projected gradient descent optimizes the regularized nonconvex loss over an incoherent feasible set.The gradient uses the observed-entry residual, while projection is implemented by row-wise clipping.
- Initialization: The initialization forms X0 = p^-1PΩ(X⋆) and constructs Z0 from its top rank-r singular factors.The estimator X0 is unbiased under the Bernoulli sampling model.
- Algorithm: The algorithm outputs the converged projected iterate after repeated gradient updates.Its step size is normalized by the initial factor norm, and the feasible-set scale also depends on that norm.
- Practical behavior: The authors report that iterates typically remain incoherent in practice, so the projection step may be omitted.This is presented as an empirical observation rather than the main theoretical guarantee.
3 Main Result: Convergence Analysis
The main results establish geometric convergence of the factorized gradient method under random sampling, using spectral initialization, incoherence control, and a local regularity condition. With sufficient observations and correctly specified rank, the iterates converge globally and linearly with high probability.
- Global convergence: With probability at least 1 − c1n^−c2, Algorithm 1 converges geometrically using λ = 1/2 and a constant step size η/σ⋆.The theorem applies to the rectangular matrix completion setting with correctly specified rank.
- Global convergence: Theorem 2 gives global convergence when the sampling probability satisfies p ≥ c0µr^2κ^2 log n.The result assumes the input rank is correctly specified and provides high-probability convergence.
- Sampling requirements: The sampling requirement includes p ≥ c3 max(µr^2κ^2, µr log n), with probability at least 1 − c1n^−c2.This condition is part of the theorem's sufficient-observation regime.
- Linear convergence: Each update reduces the distance to Z⋆ by at least a fixed factor, yielding linear convergence once the iterates enter the local neighborhood.The analysis measures distance modulo the solution set and uses a local regularity condition.
- Proof sketch: Spectral initialization places the starting point near the solution, after which local regularity makes the iterates move closer to the optimum at every iteration.The proof uses concentration of the sampled observation operator and establishes a local regularity condition near the solution set.
4 Related Work
Prior work developed convex, manifold, alternating-minimization, and factorized nonconvex approaches for matrix completion, with trade-offs in sample complexity, computational cost, resampling, and convergence guarantees. This paper extends Burer–Monteiro-style first-order analysis to rectangular matrix completion without resampling.
- Convex methods: Nuclear norm methods offer near-optimal sample complexity but require expensive singular value thresholding that limits scalability.Under incoherence, cited work establishes bounds such as O(μrn log^2 n), while proximal iterations can incur full SVD costs.
- Optimization methods: Manifold and projected-gradient methods can achieve exact or global recovery, but their convergence or practical computational guarantees remain limited in matrix completion.The cited manifold method has unknown convergence rate and high per-iteration complexity; SVP has global guarantees under RIP but only experimental support in completion.
- Alternating minimization: Alternating minimization obtains progressively improved rank and condition-number dependencies, but prior guarantees rely on resampling independent observation sets across iterations.Reported dependencies include rκ^8, r^7κ^6, and an improved r^2κ^2 bound under resampling.
- Resampling: Resampling-based analyses make sample complexity depend on target accuracy, whereas this paper’s algorithm is stated to avoid resampling and remain independent of ε.The cited comparison explicitly contrasts increasing sample requirements as ε approaches zero with the proposed independence from ε.
- Factorized methods: Burer–Monteiro factorization has enabled first-order global-optimality results for factorized models, and this work generalizes such results to rectangular matrix completion.Prior work includes asymmetric factorization for rectangular matrices and convergence in the lifted space; the paper extends results beyond semidefinite settings.
5 Experiments
Experiments compare the proposed gradient method with several matrix-completion baselines in runtime, computational complexity, and sample-complexity settings. The results indicate favorable scaling for gradient descent and phase transitions near a linear dimension–rank observation count.
- Computational Complexity: GD requires 2mr + m + n^2r operations for gradient computation and 4nr operations for updating each iterate.The comparison includes per-iteration complexities for nuclear norm minimization, SVP, OptSpace, and other methods.
- Computational Complexity: Full SVD makes nuclear norm minimization cost O(n^3) per iteration, while SVP requires O(n^2r) for rank-r projection.These costs are contrasted with GD’s sparse-observation gradient and low-cost iterate update.
- Runtime Comparison: On 4000 × 2000 rank-3 data with 199057 observations, runtime was compared among GD, SVP, OptSpace, nuclear norm minimization, and trust-region methods.The experiment used randomized low-rank SVD for SVP, OptSpace, and GD.
- Runtime Comparison: For larger instances, AltMin scaled the slowest, while GD and trustRegion runtimes increased more slowly than SVP.Nuclear and OptSpace were excluded because they did not scale well to the tested sizes.
- Sample Complexity: Across four square asymmetric cases, phase transitions occurred around m ≈ 3.5nr, suggesting sample complexity linear in dimension and rank.The experiments used sizes 500 × 500 or 1000 × 1000 and ranks 10 or 20, with success defined by relative error below 10^-6.
6 Conclusion
The paper establishes a high-probability linear-convergence guarantee for a lifted, factorized gradient method and supports its scalability with empirical evidence. The analysis relies on concentration and local geometric properties of the observation operator and feasible set.
- Conclusion: O(µr^2κ^2n max(µ, log n)) random observations suffice for linear convergence to the global optimum with high probability.The paper also conjectures that O(nr) observations may suffice for exact recovery.
- Empirical evidence: Empirical evidence indicates that the simple algorithm is fast and scalable, while Figure 2 reports runtime growth and sample-complexity experiments.The conclusion suggests that lifting may extend to more general problem classes.
- Technical basis: The proof uses concentration results and restricted strong convexity and smoothness properties for matrices in the relevant tangent subspace.These properties are established uniformly with high probability under sampling conditions.
- Technical basis: The feasible-set projection is shown to be a contraction, supporting the analysis of projected gradient updates.The contraction result applies to row-wise clipping onto the feasible set.
B.1 Proof of Lemma 1
The proof of Lemma 1 controls the initialization error by relating the sampled matrix's singular values to the ground truth and by using local curvature and smoothness conditions.
- Initialization: Weyl’s theorem relates the singular values of the sampled matrix to those of the ground truth through the sampling error bound δ.This comparison is used to control the initialization distance.
- Initialization: The initialization distance is bounded by decomposing the error H = Z0 − Z0 and exploiting symmetry and positive semidefiniteness properties.The argument combines algebraic identities with bounds on the factorization error.
- Initialization: The required initialization accuracy follows after substituting the sampling-error bound and applying the incoherence assumption.The proof states that the resulting condition holds uniformly in the relevant neighborhood.
- Local geometry: Local curvature and local smoothness conditions are introduced for the objective within a neighborhood of the target factor.These conditions are analogous to restricted strong convexity and restricted strong smoothness.
C.1 Proof of the Local Curvature Condition
The local-curvature proof lower-bounds the objective’s quadratic behavior near the target by combining observation-operator bounds, tangent-space structure, and parameter restrictions.
- Curvature bound: The proof expands the curvature expression and applies inequalities such as Cauchy–Schwarz to separate its component terms.The resulting bounds are assembled across several intermediate inequalities.
- Curvature bound: The tangent-space constraints and symmetry relations simplify the directional terms used in the lower bound.The proof explicitly uses conditions such as Z⊤DZ = 0 and symmetry of H⊤Z.
- Curvature bound: With δ = 1/16 and a bounded factor error, the lower bound holds uniformly with high probability over the feasible neighborhood.The uniformity follows from the cited lemmas used in the argument.
- Positive semidefinite case: For positive semidefinite ground truth, lifting and the regularizer are unnecessary, and the lower bound yields standard restricted strong convexity.This is obtained by directly lower-bounding the relevant Frobenius-norm term.
C.2 Proof of the Local Smoothness Condition
The local-smoothness proof upper-bounds the gradient variation near the target using norm inequalities, tangent-space identities, and uniform sampling bounds.
- Smoothness bound: The gradient norm is controlled by maximizing its inner product with unit-Frobenius-norm perturbation matrices.This converts the smoothness analysis into a bound on directional gradient terms.
- Smoothness bound: The proof expands the factorized expressions and applies Cauchy–Schwarz and product-norm inequalities to bound each component.The estimates use identities involving Z, H, and the tangent-space constraints.
- Smoothness bound: Choosing λ = 1/2, δ = 1/16, and a bounded factor error completes the local smoothness estimate.The parameter choices are combined with the preceding inequalities.
- Assumptions: The proof assumes the factors satisfy the incoherence condition and works uniformly within the prescribed neighborhood.These assumptions are part of the scope of the smoothness result.
- Positive semidefinite case: For positive semidefinite ground truth, omitting the regularizer yields a standard restricted strong smoothness condition.The paper states this as the corresponding simplified case.
C.3 Proof of Lemma 3
The proof combines bounds from the smoothness condition and earlier equations, then controls failure probabilities to establish a regularity condition with high probability.
- The smoothness condition is rearranged to obtain a further bound.
- Equations (56) and (62) are combined to derive the next proof implication.
- The probability that Lemmas 8–10 fail, together with the required sample probability, is upper-bounded.
- The regularity condition (63) holds with probability at least 1 − c1n−c2, for constant c, c1, and c2.
D.1 Proof of Lemma 2
The proof analyzes a clipped gradient-descent update by introducing the iterate error and applying a lemma under a specified step-size range.
- The iterate is updated by projected gradient descent as Zk+1 = PC(Zk − η∇f(Zk)).The projection operator PC is described as row-wise clipping.
- The iterate error is defined as Hk = Zk − Zk.
- The proof uses the definition of RC(ε, α, β) for one case and requires 0 < η ≤ min {α/2, 2/β} for another.