PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Optimality in Low-rank Matrix Optimization

Zhihui Zhu, Qiuwei Li, Gongguo Tang, Michael B. Wakin

arXiv:1702.07945v3cs.ITmath.OC

TL;DR

The paper addresses low-rank optimization with general objective functions, where factorization reduces dimension but introduces nonconvexity. It analyzes a regularized factored formulation under restricted strong convexity and smoothness, showing that its landscape has no spurious local minima and satisfies the strict saddle property. Consequently, iterative methods can reach global solutions from random initialization.

  • Problem

    Low-rank matrix optimization is difficult because rank constraints make the problem nonconvex, while factorization can create spurious local minima and bad saddle points.

  • Method

    The paper factorizes X as UV^T and analyzes a regularized factored objective for general f(X) under restricted strong convexity and smoothness.

  • Results

    The factored objective has no spurious local minima and obeys the strict saddle property, with all local minima corresponding to the global solution X⋆.

  • Takeaways & Limitations

    These geometric guarantees allow iterative algorithms such as gradient descent and trust-region methods to converge globally from random initialization.

Abstract

from arXiv · show

This paper considers the minimization of a general objective function $f(X)$ over the set of rectangular $n\times m$ matrices that have rank at most $r$. To reduce the computational burden, we factorize the variable $X$ into a product of two smaller matrices and optimize over these two matrices instead of $X$. Despite the resulting nonconvexity, recent studies in matrix completion and sensing have shown that the factored problem has no spurious local minima and obeys the so-called strict saddle property (the function has a directional negative curvature at all critical points but local minima). We analyze the global geometry for a general and yet well-conditioned objective function $f(X)$ whose restricted strong convexity and restricted strong smoothness constants are comparable. In particular, we show that the reformulated objective function has no spurious local minima and obeys the strict saddle property. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) can provably solve the factored problem with global convergence.

I. INTRODUCTION

The paper studies low-rank optimization by factorizing rectangular matrices, then analyzes when the resulting nonconvex problem has a benign global geometry. Under restricted strong convexity and smoothness, it establishes global optimization guarantees for a broad class of objectives.

  • I. INTRODUCTION: Low-rank optimization is broadly useful but computationally difficult because rank constraints make even convex objectives nonconvex and generally NP-hard.Applications include quantum tomography, collaborative filtering, sensor localization, matrix recovery, and matrix completion.
  • I. INTRODUCTION: The factorization X = UV^T reduces variable size, but its bilinear form can introduce spurious local minima and problematic saddle points.The factors U and V have dimensions n × r and m × r, respectively.
  • I. INTRODUCTION: The paper generalizes prior geometric analyses from quadratic inverse-problem losses to general objective functions f(X).The analysis targets low-rank matrix optimization problems beyond matrix sensing and completion.
  • I. INTRODUCTION: Under (2r, 4r)-restricted strong convexity and smoothness, the factored objective has no spurious local minima and satisfies the strict saddle property.The theorem assumes a critical point X⋆ of rank at most r and uses an additional regularizer.
  • I. INTRODUCTION: These geometric properties allow iterative methods such as trust-region optimization and stochastic gradient descent to recover the global minimizer from random initialization.The restricted conditions also ensure that X⋆ is the unique global minimum of the original low-rank problem.
  • I. INTRODUCTION: The framework applies beyond low-rank recovery to robust PCA, 1-bit matrix completion, and Poisson PCA, while addressing general nonsymmetric and rectangular matrices.The paper emphasizes that prior PSD results cannot be directly applied to this broader setting.

B. Strict Saddle Property

The paper defines strict saddles through negative Hessian curvature and uses a regularized factorization to analyze the factored objective. Under its restricted curvature conditions, every critical point is either globally minimizing or a strict saddle.

  • B. Strict Saddle Property: A strict saddle is a critical point whose Hessian has a strictly negative eigenvalue, and the strict saddle property requires every critical point to be either a local minimum or such a saddle.This directional negative curvature enables algorithms to move away from non-minimizing critical points.
  • B. Strict Saddle Property: For functions with the strict saddle property, methods including gradient descent and trust-region optimization can find a local minimum.The stated guarantee applies to twice continuously differentiable objectives.
  • B. Strict Saddle Property: Restricted strong convexity and smoothness make the low-rank critical point X⋆ the unique global minimum of the original problem.This conclusion follows from the stated rank and curvature assumptions.
  • B. Strict Saddle Property: The factorization X = UV^T reduces variable size but creates a bilinear nonconvex landscape that may contain spurious minima or degenerate saddles.The paper’s goal is to rule out these unfavorable critical points under suitable assumptions.
  • B. Strict Saddle Property: A regularizer penalizes unequal Gram matrices of U and V, resolving factorization ambiguity while preserving the global minimizer.Its global minimum is attained when U and V have the same Gram matrices.

B. Main Results

Under comparable restricted strong convexity and smoothness, the factored objective categorizes critical points into global minima or strict saddles. This geometry supports global recovery, including over-parameterized factorizations, while weighted examples show the conditioning requirement is meaningful.

  • Proof strategy: Theorem 3 is proved by showing that every non-minimizing critical point has negative curvature along a direction based on its distance from a rotated optimum.The proof uses Δ := W − W⋆R, where R minimizes the rotation-aligned factor distance.
  • Main theorem: Theorem 3 guarantees no spurious local minima and strict saddles when β/α ≤ 1.5, with µ ≤ α/16 and a rank-r⋆ critical point.Global minima satisfy UV^T = X⋆, while every other critical point has strictly negative Hessian curvature.
  • Algorithmic implication: Strict-saddle geometry lets iterative methods reach the unique global minimizer from random initialization, including when the factorization is over-parameterized.The cited discussion names trust-region and stochastic-gradient methods and covers r > r⋆.
  • Scope and limitation: The analysis extends beyond exact parameterization and its constants are not fully optimized, although the room for relaxing β/α ≤ 1.5 is limited.The paper notes that more sophisticated analysis may slightly relax the threshold, while the weighted example constrains improvement.
  • Conditioning boundary: Weighted symmetric factorization has a strict saddle when a < 2 but a spurious local minimum when a > 2, demonstrating the role of conditioning.The example satisfies restricted strong convexity and smoothness, yet still exhibits a spurious minimum beyond the favorable dynamic range.

C. Stylized Applications

The general geometric theorem yields concrete guarantees for matrix sensing and weighted low-rank factorization. In matrix sensing, a moderate RIP condition suffices, whereas arbitrary weights can still produce spurious minima.

  • Matrix sensing: The matrix-sensing objective inherits restricted strong convexity and smoothness from the 4r-RIP condition.The cited derivation identifies the constants through the RIP bounds for rank-4r matrices.
  • Matrix sensing: With 4r-RIP constant δ4r ≤ 1/5 and µ ≤ (1−δ4r)/16, matrix sensing has no spurious local minima and satisfies the strict saddle property.The result follows because the restricted smoothness-to-convexity ratio is at most 1.5 under this RIP condition.
  • Weighted factorization: The weighted formulation uses an elementwise weight matrix Ω and an added regularizer g(U,V) in its factored objective.The objective is constructed from the weighted matrix product and the regularizer defined earlier in the paper.
  • Weighted factorization: For weighted factorization, concentrated weights are expected to support efficient optimization, but arbitrary weights can make the problem NP-hard and introduce spurious local minima.The favorable case is described as close to unweighted matrix factorization, which obeys the strict saddle property.
  • Weighted factorization: Under the theorem’s conditions, the weighted low-rank factorization objective has no spurious local minima and satisfies the strict saddle property.The cited corollary applies the general theorem to the weighted formulation with its added regularizer.

3) 1-bit Matrix Completion:

The paper applies its framework to 1-bit matrix completion by modeling binary observations with logistic or probit likelihoods. Under bounded entries and full observations, the objective satisfies the required restricted curvature conditions, supporting factorization-based recovery.

  • 1-bit matrix completion: The logistic model uses q(x) = e^x/(1+e^x), while the probit model uses the Gaussian CDF with scale parameter σ.These links define the observation probabilities used in the 1-bit likelihood formulation.
  • 1-bit matrix completion: The likelihood objective is convex for both logistic and probit observation models, and full measurements establish the restricted curvature condition.The cited passages define FΩ,Y as a negative log-likelihood and state the full-observation setting Ω = [n] × [m].
  • 1-bit matrix completion: For full 1-bit measurements and logistic regression with γ ≤ 1.3, the negative log-likelihood satisfies restricted strong convexity and smoothness.The result follows from the curvature bounds for the logistic model on the bounded domain ∥X∥∞ ≤ γ.
  • 1-bit matrix completion: Matrix factorization can be applied to 1-bit matrix recovery when the recovered matrix entries are bounded.The paper contrasts this with nuclear-norm constraints and reports empirical support for 1-bit matrix completion.
  • Proof connection: The proof framework classifies non-global critical points through negative Hessian curvature, using restricted strong convexity and smoothness inequalities.The proof develops gradient, Hessian, projection, and factor-distance lemmas to establish the strict-saddle conclusion.

B. The Formal Proof

The proof partitions critical points into globally optimal points and nonoptimal points, then establishes strict negative curvature at every nonoptimal point.

  • B. The Formal Proof: Critical points split into C1, containing globally optimal solutions, and C2, whose strict-saddle behavior remains to be shown.The proof uses this partition to establish both global optimality and the strict saddle property.
  • B. The Formal Proof: For each W in C2, the proof chooses Δ as the difference between W and its nearest global factor W⋆.Because X ≠ X⋆, this direction is nonzero and can expose curvature away from the optimum.
  • B. The Formal Proof: The Hessian’s dominant term Π1 is strictly negative, while the remaining terms are bounded as relatively small contributions.The bounds rely on the stated conditions α ≤ 1.5 and μ ≤ 1/(16α).
  • B. The Formal Proof: The Hessian bilinear form along Δ is always negative, proving that every W in C2 is a strict saddle.This completes the argument that the factored objective has no spurious local minima.
  • B. The Formal Proof: The regularizer’s Hessian contribution has little influence when μ is small, yielding a more negative curvature bound as μ decreases.The proof contrasts the regularizer contribution with the positive-semidefinite Hessian structure of the unregularized component.

V. EXPERIMENTS

The experiments evaluate iterative local-search methods for low-rank matrix sensing, matrix completion, and 1-bit matrix completion.

  • V. EXPERIMENTS: Experiments cover matrix sensing, matrix completion, and 1-bit matrix completion using local-search algorithms for the factored problem.The matrix factorization approach is denoted NVX and implemented with the minFunc package.

A. Matrix Sensing

Experiments compare factorized optimization with projection, thresholding, and convex methods across recovery success, over-parameterization, and computation time.

  • A. Matrix Sensing: Matrix factorization has negligible performance differences from SVP and convex optimization for matrix sensing.The comparison uses phase-transition experiments and similar guarantees under Gaussian sensing operators satisfying RIP.
  • A. Matrix Sensing: The factorized method recovers X⋆ with r = r⋆ and with r > r⋆, but over-parameterization slows convergence.The experiment uses r⋆ = 4, n = m = 50, R = 7, and r from 4 through 7.
  • A. Matrix Sensing: Matrix-completion recovery assumes incoherence, under which the sampling projection satisfies RIP for low-rank incoherent matrices.Theorem 4 gives a Bernoulli-sampling condition ensuring this RIP with high probability.
  • A. Matrix Sensing: Global convergence from random initialization is guaranteed when local-search iterates remain incoherent, a hypothesis also required by SVP.The authors report empirical support for incoherence during gradient descent.
  • A. Matrix Sensing: For matrix completion, factorization has a phase transition similar to SVP and slightly better than SVT and the convex approach in measurement requirements.The experiment varies rank from 1 to 30 with n = m = 100.
  • A. Matrix Sensing: The matrix factorization approach is much faster than SVP, SVT, and convex optimization as matrix-completion dimension grows.Its time savings come from avoiding the SVD required by SVP and SVT; the convex approach is reported as non-scalable.

C. 1-bit Matrix Completion

The experiments compare matrix factorization with a convex method for 1-bit matrix completion under probit and logistic regression models. Across varied problem dimensions and noise levels, matrix factorization performs slightly better in the reported probit experiments.

  • Method: The factorization method replaces the entrywise maximum constraint with a smooth Frobenius-norm regularizer before optimizing over factors U and V.The resulting objective remains convex in X and is then factorized as X = UV^T.
  • Results: Matrix factorization has slightly better performance than the convex approach for 1-bit matrix completion in the reported experiments.The comparison averages results over 10 Monte Carlo trials and varies n, p, r, or σ.
  • Probit regression: The probit experiments measure relative Frobenius error while varying n, p, r, and σ against the convex baseline CVX.Figure 5 uses NVX for matrix factorization and CVX for the convex approach, with results plotted on a log scale.
  • Logistic regression: The logistic experiments compare the same two approaches while varying n and p at fixed rank r = 2.Figure 6 reports relative Frobenius error in the log scale.

APPENDIX A PROOF OF LEMMA 1

This appendix proof establishes intermediate Hessian and gradient relations used in analyzing the factored objective. It relies on restricted strong convexity and smoothness for low-rank matrices, together with rank bounds along relevant paths.

  • Hessian argument: The Hessian bilinear form is treated as invariant under independent scalings of its two matrix arguments.The proof normalizes nonzero arguments to unit Frobenius norm before applying the curvature condition.
  • Rank-restricted curvature: The proof uses restricted strong convexity and smoothness because the matrices involved have rank at most 2r or 4r.The rank bounds apply to interpolation paths, differences, and factor-induced perturbations.
  • Critical-point analysis: The proof connects critical-point identities for the factorization to bounds involving the difference between factored products and the target matrix.It uses X = UV^T, X⋆ = U⋆V⋆, the vanishing gradient at X⋆, and pseudoinverse-based constructions.

2 ZUV T

These proof fragments establish auxiliary matrix inequalities used in the geometric analysis. The argument combines orthogonal alignment, singular-value bounds, and positive-semidefinite inner-product properties.

  • PSD inequality: The proof completes an auxiliary estimate by using nonnegativity of an inner product between positive-semidefinite matrices.This PSD inner-product property supplies the required inequality direction.
  • Factor alignment: Orthogonal alignment yields a lower bound relating Gram-matrix differences to the factor discrepancy through singular values.The bound uses R minimizing the Frobenius distance between aligned factors and includes min{σ_r1(C), σ_r2(D)}.

APPENDIX E PROOF OF (20)

The appendix proves bounds for terms in the factorized objective by decomposing factor errors and applying restricted strong convexity. Alignment identities and PSD inner-product inequalities control the resulting expressions.

  • Term Π1: The proof bounds the first term using aligned factor errors ΔU = U − U⋆R and ΔV = V − V⋆R.The derivation invokes the stationarity condition at X⋆ and restricted strong convexity.
  • PSD control: Nonnegative PSD inner products provide the final inequality direction in the factor-error bounds.The proof explicitly uses the inner product between PSD matrices as a nonnegative quantity.
  • Gram identities: The argument uses U^TU = V^TV and U⋆^TU⋆ = V⋆^TV⋆ to simplify Gram-matrix expressions.These identities reduce the remaining algebra needed for the target inequality.
Loading 1702.07945v3…