Source-linked AI summary
Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach
Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, Sujay Sanghavi
TL;DR
The paper asks whether non-square matrix sensing remains well behaved after representing rank-r matrices as UV^⊤, despite the resulting bilinear non-convexity. It reformulates the problem through an augmented semidefinite variable with a regularizer and analyzes first- and second-order conditions under RIP. The main result is that this factorization introduces no spurious local minima under the stated assumptions.
Problem
The paper addresses whether bilinear factorization creates spurious local minima in non-square matrix sensing, a question left open by results for square PSD matrices.
Method
The analysis uses an equivalent semidefinite reformulation with an augmented variable, a regularizer, and balanced factorizations while retaining RIP assumptions on the original sensing map.
Results
Under RIP, the paper shows that UV^⊤ parametrization does not introduce spurious local minima; first- and second-order critical points are global minima under the theorem’s conditions.
Takeaways & Limitations
Non-square matrix sensing can retain the favorable no-spurious-local-minima geometry established for the analogous square PSD setting.
Takeaways & Limitations
The analysis assumes RIP for A on m×n matrices, while the reformulated map B acts on (m+n)×(m+n) matrices and therefore requires a different analysis.
Abstract
from arXiv · showhide
We consider the non-square matrix sensing problem, under restricted isometry property (RIP) assumptions. We focus on the non-convex formulation, where any rank-$r$ matrix $X \in \mathbb{R}^{m \times n}$ is represented as $UV^\top$, where $U \in \mathbb{R}^{m \times r}$ and $V \in \mathbb{R}^{n \times r}$. In this paper, we complement recent findings on the non-convex geometry of the analogous PSD setting [5], and show that matrix factorization does not introduce any spurious local minima, under RIP.
1 Introduction and Problem Formulation
The paper studies non-square matrix sensing through bilinear low-rank factorization and asks whether this reparameterization creates spurious local minima. Under RIP assumptions, it reformulates the problem with balanced factors and a regularizer to establish favorable optimization geometry.
- 1 Introduction and Problem Formulation: Matrix sensing recovers a rank-r matrix X⋆ from undersampled noisy linear observations b = A(X⋆) + w.The sensing map appears in applications including imaging, data analytics, quantum computing, systems, and sensor localization.
- 1 Introduction and Problem Formulation: Low-rank constraints and nuclear-norm relaxations can require costly SVD computations, motivating direct factorization X = UV^⊤.The factors have dimensions U ∈ R^{m×r} and V ∈ R^{n×r}.
- 1 Introduction and Problem Formulation: The central question is whether bilinearity in the factored variable space introduces spurious local minima.This is the additional non-convexity created by replacing the matrix variable with factors.
- 1 Introduction and Problem Formulation: Under standard RIP assumptions on A, the paper shows that UV^⊤ parametrization does not introduce spurious local minima.This is the paper’s main stated contribution for non-square matrix sensing.
- 1 Introduction and Problem Formulation: The result generalizes analyses from square PSD sensing to the non-square target-matrix setting.The extension requires a different but equivalent reformulation and analysis.
- 1.1 Assumptions and Definitions: The sensing operator is assumed to satisfy the Restricted Isometry Property, which controls measurements of low-rank matrices.The paper also describes Gaussian, Pauli, Fourier, and noiselet sensing mechanisms as characteristic examples.
- 1.1 Assumptions and Definitions: Because factorization is non-unique, the analysis measures distance to balanced or equally-footed factorizations of X⋆.Balanced factors share singular values equal to the square roots of X⋆’s singular values.
- 1.2 Problem Re-formulation: The proof reduces the bilinear problem to a semidefinite formulation using an augmented variable W and sensing map B, then adds a regularizer g.The regularizer preserves equivalence while restricting optimal representations to balanced factorizations.
2 Main Results
The main results characterize the non-square matrix-sensing landscape by bounding second-order critical points’ distance from the target, with exact recovery in the noiseless rank-r setting. They also give bounds for noisy and high-rank settings.
- Main theorem: Theorem 2.1 bounds the distance from any first- and second-order critical point to the global minimum under the balanced singular values assumption.The result applies to a target matrix W⋆ and the objective f + g.
- Main theorem: The theorem also yields a bound on Dist(U, V; X⋆) in terms of the measurement residual ||A(U⋆V⋆⊤) − b||.This connects factor distance to the discrepancy between the observed measurements and the target-generated measurements.
- Noiseless matrix sensing: In the noiseless rank-r setting, if 0 ≤ δ2r ≤ δ4r ≲ 0.0363, every critical point satisfying first- and second-order conditions is a global minimum.The conclusion follows because the right-hand side of the distance bound is zero.
- Noisy matrix sensing: For noisy rank-r sensing, the analysis assumes X⋆ = U⋆V⋆⊤ and b = A(U⋆V⋆⊤) + w, with 0 ≤ δ2r ≤ δ4r < 0.02.Under these assumptions, the distance of any local minimum to U⋆V⋆⊤ is bounded.
- High-rank matrix sensing: For arbitrary-rank targets, the paper considers the best rank-r approximation X⋆_r and assumes noisy observations plus a balanced factorization, requiring 0 ≤ δ2r ≤ δ4r < 0.005.The resulting bound concerns the distance between a local factor pair and the balanced factorization of X⋆_r.
3 Proof of Main Results
The proof translates first- and second-order optimality conditions into matrix-direction inequalities, then combines RIP-based lemmas and auxiliary bounds to relate a critical point to the target.
- Optimality conditions: The analysis formulates first-order stationarity and second-order positive-semidefinite Hessian conditions for the composite objective f + g.The Hessian condition is expressed through arbitrary matrix directions Z.
- Proof strategy: The proof selects directions based on the aligned factor error W − W⋆R and decomposes them columnwise for the second-order analysis.It first uses Z = W − W⋆R and then defines corresponding directions Z1, …, Zr.
- Conclusion: The proof concludes after substituting the auxiliary bounds into the main inequality and establishing the claimed result.The final steps explicitly plug the bounds into equations (17) and related expressions.
4 What About Saddle Points?
The section extends the landscape analysis from local minima to saddle points by showing that the objective satisfies the strict saddle property, enabling randomly initialized gradient descent to reach a global minimum with high probability.
- Saddle-point setting: Second-order optimality already handles saddle points whose Hessian is positive semidefinite, while the section separately studies saddles with both positive and negative eigenvalues.The harder case involving simultaneous positive, negative, and zero eigenvalues is excluded.
- Saddle-point setting: Saddle points matter practically because gradient-based methods can become stuck there despite having gradient information.Such points may lie far from the global optimum.
- Strict saddle property: A strict-saddle objective requires every stationary point that is not a local minimum to have a negative minimum Hessian eigenvalue.This is the defining condition used for the convergence result.
- Convergence consequence: Under this property, randomly initialized gradient descent with a sufficiently small step size converges to a local minimum almost surely, and here this supports convergence to the global minimum with high probability.The convergence theorem is stated for twice-differentiable objectives.
- Strict saddle property: The section shows that f + g satisfies the strict saddle property under the stated noiseless RIP setting.The result is presented using the analysis developed for the PSD setting.