A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements

Qinqing Zheng; John Lafferty

Source-linked AI summary

A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements

Qinqing Zheng, John Lafferty

arXiv:1506.06081v3Jun 19, 2015stat.MLcs.LG

TL;DR

Rank minimization and related semidefinite programs need scalable algorithms beyond methods suited to small problems. The paper factors the positive semidefinite variable and applies gradient descent to a nonconvex residual objective. With O(r^3κ^2n log n) random measurements, it proves high-probability exact recovery and linear convergence, while experiments suggest O(rn log n) scaling.

Problem
Semidefinite programs and affine rank minimization are important but existing optimization methods face scalability challenges, while rank minimization is nonconvex and generally NP hard without structural conditions.
Method
The method factors the positive semidefinite matrix as X = ZZ⊤ and optimizes the resulting nonconvex squared-residual objective with gradient descent, constructed initialization, and step size.
Results
O(r^3κ^2n log n) random measurements suffice for high-probability exact recovery and linear convergence to the global optimum; experiments suggest O(rn log n) scaling.
Takeaways & Limitations
Factoring the semidefinite variable and using first-order optimization yields an efficient, scalable approach applicable to rank minimization and certain semidefinite programs.
Takeaways & Limitations
The proven measurement bound is O(r^3κ^2n log n), while the lower O(rn log n) scaling remains conjectural or empirically suggested.

Abstract

from arXiv · show

We propose a simple, scalable, and fast gradient descent algorithm to optimize a nonconvex objective for the rank minimization problem and a closely related family of semidefinite programs. With $O(r^3 κ^2 n \log n)$ random measurements of a positive semidefinite $n \times n$ matrix of rank $r$ and condition number $κ$, our method is guaranteed to converge linearly to the global optimum.

1 Introduction

The paper targets scalable rank minimization and related semidefinite programs under random measurements, using gradient descent on a nonconvex formulation. It proves exact recovery, linear convergence, and lower computational cost under the stated setting.

Semidefinite programs are important across applied mathematics, signal processing, and machine learning, but interior-point methods handle only relatively small problems.
The affine rank minimization problem seeks a minimum-rank matrix satisfying affine constraints and is challenging because the optimization is nonconvex and generally NP hard without structural conditions.
The paper assumes a positive semidefinite solution and Gaussian Orthogonal Ensemble measurement matrices Ai with A(X)i = tr(AiX).
Factoring X⋆ as Z⋆Z⋆⊤ yields a nonconvex squared-residual objective that the paper optimizes with gradient descent using a constructed initialization and step size.
O(r^3n log n) constraints suffice for exact recovery with high probability, while experiments suggest the bound may improve to O(rn log n).
The method converges linearly, has lower computational cost than previous methods, and significantly outperforms alternatives when measurement matrices are sparse.

2 Semidefinite Programming and Rank Minimization

The paper connects positive semidefinite rank minimization with constrained nuclear-norm semidefinite programs through variable transformations. Under restricted-isometry conditions, the corresponding solutions coincide.

A positive-definite SDP objective matrix can be factored as eC = LL⊤, enabling a transformation to constraints of the form tr(AiX) = bi.
The transformed SDP has the same minimum as the corresponding rank-minimization formulation after mapping minimizers through L and L−1.
Because X is positive semidefinite, its trace equals its nuclear norm, so the transformed problem is a nuclear norm relaxation of rank minimization.
If δ2r < 1, a rank-r solution satisfying the affine constraints is unique among matrices of rank at most r.
If δ5r < 1/10, nuclear norm minimization attains the rank-r solution, which is positive semidefinite and therefore coincides with the related SDP solution.
This connection justifies comparing the gradient method with nuclear norm relaxation, SVP, and AltMinSense after dropping the positive semidefinite constraint.

3 Related Work

Prior approaches provide recovery guarantees but face computational or practical limitations. The paper positions its positive-semidefinite factorized method as a scalable, provably convergent alternative.

Nuclear norm methods are convex but can be impractical at scale because singular value thresholding requires an expensive SVD at every iteration.
SVP achieves linear convergence under an RIP condition, but its per-iteration best-rank approximation is constructed from an SVD.
AltMinSense avoids per-iteration SVD by alternating least-squares updates of two factors, but those least-squares problems are often ill-conditioned in practice.
The paper states that efficient, scalable, and provably convergent algorithms had not yet been obtained, then exploits positive semidefiniteness to pursue these goals.
Procrustes Flow combines a few SVP initialization iterations with subsequent gradient descent.

4 A Gradient Descent Algorithm for Rank Minimization

The algorithm adapts Wirtinger Flow to positive semidefinite rank minimization by factoring the matrix and optimizing a squared-residual objective. A spectral initialization places the iterates near the solution, where linear convergence can be established.

The method parallels Wirtinger Flow by minimizing a sum of squared residuals with a first-order gradient algorithm.
For real-valued rank-one cases, the objective and results generalize Wirtinger Flow for phase retrieval to matrix rank minimization.
A spectral initialization uses a linear combination of constraint values and measurement matrices to form an unbiased estimate of the solution.
The initialization uses the eigendecomposition X⋆ = U⋆ΣU⋆⊤ and constructs the factor from the eigenvectors and nonzero eigenvalues.
Linear convergence follows from local regularity near Z⋆, although the objective lacks the global strong-convexity and Lipschitz-gradient properties used in standard analyses.
Figure 1 illustrates that both Z⋆ and −Z⋆ minimize the rank-one objective and shows linear convergence for n = 200, m = 1000, and r = 2.
The algorithm uses a constant step size proportional to 1/∥Z0∥F because ∥Z⋆∥F is unknown.

5 Convergence Analysis

The analysis establishes linear convergence of the factored gradient descent method under local regularity and sufficiently many random measurements, assuming the rank is correctly specified. It also gives a high-probability initialization guarantee and identifies a gap between the algorithm’s sample complexity and that required by regularity.

Solution geometry: The symmetric factorization is nonunique, so convergence is measured relative to the solution set of equivalent factors.Any factor Z⋆U with U orthonormal represents the same matrix X⋆.
Exact recovery: The algorithm targets exact recovery under the assumption that the true rank is correctly specified.When the rank is unknown, the paper suggests starting from a low rank and increasing it gradually.
Initialization: m ≥ c0κ^2r^3n log n measurements suffice with high probability for the spectral initialization to be close enough to the optimal factor.Here κ is the ratio of the largest to smallest nonzero eigenvalues of X⋆.
Convergence: Under the stated regularity and concentration events, each sufficiently near iterate moves closer to the optimum, yielding linear convergence with a constant step size.The proof establishes local regularity, verifies it with high probability, and uses that property to contract the distance to the solution set.
Sample complexity: The algorithm requires O(r^3κ^2n log n) measurements, whereas the regularity condition requires only O(r^2κ^2n log n).The paper conjectures that the overall bound could improve to O(rn log n), supported by its experiments.

6 Experiments

Experiments compare the gradient method with nuclear norm relaxation, SVP, and AltMinSense on dense and sparse measurements, runtime, and sample complexity. The method is faster in both runtime settings and exhibits near-linear-rank sample scaling.

6 Experiments: The experiments compare gradient descent with nuclear norm relaxation, SVP, and AltMinSense on synthetic rank-minimization datasets.AltMinSense, SVP, and the gradient scheme are assumed to know the true rank; ADMM is used for nuclear norm minimization.
6.1 Computational Complexity: The gradient scheme requires 2n^2r operations for matrix multiplications, while nuclear norm relaxation additionally incurs O(n^3) SVD and O(m^2) dual-update costs.The other methods have O(mn^2ρ) affine-transformation cost; AltMinSense has the highest stated complexity.
6.1 Computational Complexity: The gradient method removes SVD overhead and has low cost when measurement matrices are sparse.For dense measurements, affine transformation dominates; for sparse measurements, the remaining computational components dominate.
6.3 Sample Complexity: For rank-1 and rank-2 targets, phase transitions occur around m = 1.5n and m = 2.5n, respectively, for SVP and the gradient method.These transitions are close to the degrees of freedom, and the results support sample complexity scaling linearly with rank.

7 Conclusion

The paper connects a special affine rank-minimization problem to semidefinite programs with random constraints and develops a gradient-descent procedure for this setting. It proves high-probability convergence with O(r^3n log n) measurements, while conjecturing O(rn log n) suffices and broader applicability of the factorized approach.

7 Conclusion: The method connects a special case of affine rank minimization to semidefinite programs with random constraints.
7 Conclusion: The gradient-descent procedure establishes convergence to the optimal solution with O(r^3n log n) measurements.
7 Conclusion: The paper conjectures that O(rn log n) measurements suffice and that the sampling-matrix conditions can be significantly weakened.
7 Conclusion: The factorized nonconvex first-order technique may be effective for a wider class of semidefinite programs, motivating further study.

A Proof of Lemma 1

This proof section develops GOE expectation identities and supporting concentration, geometric, curvature, and smoothness lemmas used in the convergence analysis. These ingredients establish local conditions for the gradient scheme.

A. Proof of Lemma 1: For a GOE matrix A, the proof establishes E((x⊤Ax)A) = 2xx⊤ for any vector x.The calculation uses diagonal variance 2 and off-diagonal variance 1.
A. Proof of Lemma 1: For fixed vectors x and y, the GOE identity is E[Axy⊤A] = x⊤yI + yx⊤.This identity supplies the expectation of second-order terms involving random measurement matrices.
A. Proof of Lemma 1: The proof bounds random measurement operator norms, including an average squared operator-norm bound of 9n with probability at least 1 − mCe^−ρn.A tighter high-probability operator-norm estimate is also noted as O(2√n + n^1/6).
A. Proof of Lemma 1: Lemmas bound factor-column perturbations and second-order terms for matrices near a factor Z⋆ of the target.The argument uses Frobenius-norm perturbations, singular values, and properties of aligned factors.
A. Proof of Lemma 1: The analysis verifies local curvature and local smoothness conditions needed for linear convergence of the gradient scheme.The proof invokes Nesterov’s result for gradient schemes under a regularity condition analogous to strong convexity and smoothness.

D.3 Proof of the Regularity Condition

The regularity-condition proof combines local curvature and smoothness bounds to control the gradient dynamics near the target factor. The resulting parameter requirements depend on the target spectrum and measurement dimension.

D.3 Proof of the Regularity Condition: Combining the curvature and smoothness inequalities yields the regularity bound used in the convergence analysis.
D.3 Proof of the Regularity Condition: For α ≥ 24 and β ≥ σ1σr · 513n, the required parameter conditions are satisfied.
D.3 Proof of the Regularity Condition: The proof uses Weyl’s theorem to relate eigenvalues of the perturbed matrix to those of the target-related matrix.
D.3 Proof of the Regularity Condition: The distance between the initialized factor and the target factor is bounded through a perturbation H and the Frobenius norm ∥H∥F.

F Sample Complexity

The proof establishes high-probability concentration under sample sizes scaling as m ≥ c n log n, using Gaussian, χ2, union-bound, and matrix Bernstein arguments.

m ≥ c n log n suffices for the assumptions to hold with high probability, with c depending on δ, r, and κ.
The technical GOE lemma bounds the relevant random matrix norm with probability at least 1 − C e^−ρn.
Gaussian and χ2 tail inequalities control individual entries and column-related quantities before union bounds combine the events.For example, the proof records P(|a11| > 2√n) ≤ 2e^−n and χ2 tail bounds for auxiliary variables.
Matrix Bernstein bounds are applied after controlling the operator norms of the random summands and their variance parameters.The proof computes variance quantities including ν2 = (2n + 6)m and ν2 = m(8n + 24).

Proof of (ii)

The proof of (ii) reduces the analysis to the first two columns of a GOE matrix and bounds the resulting rank-two operator using concentration of their norms.

Proof of (ii): u = e1 and u⊥ = e2 suffice by orthogonal invariance, reducing the proof to the first and second columns of Ai.
Proof of (ii): ∥S∥ ≤ 2∥v∥∥q∥ + 2 converts concentration of the column norms into an operator-norm bound.
Proof of (ii): With probability at least 1 − 4e^−n, both column norms are no larger than √(13n + 1).
The surrounding formulation introduces an auxiliary variable V and applies ADMM to an equality-constrained dual problem, with spectral-norm projection and singular-value thresholding updates.