Global Optimality in Low-rank Matrix Optimization

I Introduction

Consider the minimization of a general objective function $f(\boldsymbol{X})$ over all low-rank $n\times m$ matrices:

The bilinear nature of the parameterization renders the objective function of (2) nonconvex even when $f(\boldsymbol{X})$ is a convex function. Hence, the objective function in (2) can potentially have spurious local minima (i.e., local minimizers that are not global minimizers) or “bad” saddle points that prevent a number of iterative algorithms from converging to the global solution. By analyzing the landscape of nonconvex functions, several recent works have shown that the factored objective function $h(\boldsymbol{U},\boldsymbol{V})$ in certain matrix inverse problems has no spurious local minima .

We generalize this line of work by focusing on a general objective function $f(\boldsymbol{X})$ in the optimization (1), not necessarily a quadratic loss function coming from a matrix inverse problem. By focusing on a general objective function, we attempt to provide a unifying framework for low-rank matrix optimizations with the factorization approach. We provide a geometric analysis for the factored program (2) and show that, under certain conditions on $f(\boldsymbol{X})$, all critical points of the objective function $h(\boldsymbol{U},\boldsymbol{V})$ are well-behaved. Our characterization of the geometry of the objective function ensures that a number of iterative optimization algorithms converge to a global minimum.

The purpose of this paper is to analyze the geometry of the factored problem $h(\boldsymbol{U},\boldsymbol{V})$ in (2). In particular, we attempt to understand the behavior of all of the critical points of the objective function in the reformulated problem (2).

Before presenting our main results, we lay out the necessary assumptions on the objective function $f(\boldsymbol{X})$. As is known, without any assumptions on the problem, even minimizing traditional quadratic objective functions is challenging. For this purpose, we focus on the model where $f(\boldsymbol{X})$ is $(2r,4r)$-restricted strongly convex and smooth, i.e., for any $n\times m$ matrices $\boldsymbol{X},\boldsymbol{G}$ with $\operatorname{rank}(\boldsymbol{X})\leq 2r$ and $\operatorname{rank}(\boldsymbol{G})\leq 4r$, the Hessian of $f(\boldsymbol{X})$ satisfies

for some positive $\alpha$ and $\beta$. A similar assumption is also utilized in [20, Conditions 5.3 and 5.4]. With this assumption on $f(\boldsymbol{X})$, we summarize our main results in the following informal theorem.

As guaranteed by Proposition 1 (in Section III), the $(2r,4r)$-restricted strong convexity and smoothness property (3) ensures that $\boldsymbol{X}^{\star}$ is the unique global minimum of (1). Theorem 1 then implies that we can recover the rank-$r^{\star}$ global minimizer $\boldsymbol{X}^{\star}$ of (1) by many iterative algorithms (such as the trust region method and stochastic gradient descent ) even from a random initialization. This is because 1) as guaranteed by Theorem 2, the strict saddle property ensures local search algorithms converge to a local minimum, and 2) there are no spurious local minima.

Since our main result only requires the $(2r,4r)$-restricted strong convexity and smoothness property (3), aside from low-rank matrix recovery , it can also be applied to many other low-rank matrix optimization problems which do not necessarily involve quadratic loss functions. Typical examples include robust PCA , 1-bit matrix completion and Poisson principal component analysis (PCA) .

I-B Related Works

Compared with the original program (1), the factored form (2) typically involves many fewer variables (or variables with much smaller size) and can be efficiently solved by simple but powerful methods (such as gradient descent , the trust region method , and alternating methods ) for large-scale settings, though it is nonconvex. In recent years, tremendous effort has been devoted to analyzing nonconvex optimizations by exploiting the geometry of the corresponding objective functions. These works can be separated into two types based on whether the geometry is analysed locally or globally. One type of work analyzes the behavior of the objective function in a small neighborhood containing the global optimum and requires a good initialization that is close enough to a global minimum. Problems such as phase retrieval , matrix sensing , and semi-definite optimization have been studied.

Another type of work attempts to analyze the landscape of the objective function and show that it obeys the strict saddle property. If this particular property holds, then simple algorithms such as gradient descent and the trust region method are guaranteed to converge to a local minimum from a random initialization rather than requiring a good guess. We approach low-rank matrix optimization with general objective functions (1) via a similar geometric characterization. Similar geometric results are known for a number of problems including complete dictionary learning , phase retrieval , orthogonal tensor decomposition , and matrix inverse problems . Empirical evidence also supports using the factorization approach for estimating a low-rank PSD matrix from a set of rank-one measurements corrupted by arbitrary outliers and for recovering a dynamically evolving low-rank matrix from incomplete observations .

Our work is most closely related to certain recent works in low-rank matrix optimization. Bhojanapalli et al. showed that the low-rank, PSD matrix sensing problem has no spurious local minima and obeys the strict saddle property. Similar results were exploited for PSD matrix completion , PSD matrix factorization and low-rank, PSD matrix optimization problems with generic objective functions . Our work extends this line of analysis to general low-rank matrix (not necessary PSD or even square) optimization problems. Another closely related work considers the low-rank, non-square matrix sensing problem and matrix completion with the factorization approach . We note that our general objective function framework includes the low-rank matrix sensing problem as a special case (see Section III-C). Furthermore, our result covers both over-parameterization where $r>r^{\star}$ and exact parameterization where $r=r^{\star}$. Wang et al. also considered the factored low-rank matrix minimization problem with a general objective function which satisfies the restricted strong convexity and smoothness condition. Their algorithms require good initializations for global convergence since they characterized only the local landscapes around the global optima. By categorizing the behavior of all the critical points, our work differs from in that we instead characterize the global landscape of the factored objective function.

This paper continues in Section II with formal definitions for strict saddles and the strict saddle property. We present the main results and their implications in matrix sensing, weighted low-rank approximation, and 1-bit matrix completion in Section III. The proof of our main results is given in Section IV. We conclude the paper in Section VI.

II Preliminaries

II-B Strict Saddle Property

We say $\boldsymbol{x}$ a critical point if the gradient at $\boldsymbol{x}$ vanishes, i.e., $\nabla h(\boldsymbol{x})={\bf 0}$.

A critical point $\boldsymbol{x}$ is a strict saddle if the Hessian matrix evaluated at this point has a strictly negative eigenvalue, i.e., $\lambda_{\min}(\nabla^{2}h(\boldsymbol{x}))<0$.

A twice differentiable function satisfies the strict saddle property if each critical point either corresponds to a local minimum or is a strict saddle.

Intuitively, the strict saddle property requires a function to have a directional negative curvature at all critical points but local minima. This property allows a number of iterative algorithms such as noisy gradient descent and the trust region method to further decrease the function value at all the strict saddles and thus converge to a local minimum.

(informal) For a twice continuously differentiable objective function satisfying the strict saddle property, a number of iterative optimization algorithms (such as gradient descent and the the trust region method) can find a local minimum.

III Problem Formulation and Main Results

This paper considers the problem (1) of minimizing a general function $f(\boldsymbol{X})$ (over the set of low-rank matrices) which is assumed to have a low-rank critical point $\boldsymbol{X}^{\star}$ with $\operatorname{rank}(\boldsymbol{X}^{\star})=r^{\star}\leq r$ such that $\nabla f(\boldsymbol{X}^{\star})={\bf 0}$. Because of the restricted strong convexity and smoothness condition (3), the following result establishes that if $f(\boldsymbol{X})$ has a critical point $\boldsymbol{X}^{\star}$ with $\operatorname{rank}(\boldsymbol{X}^{\star})\leq r$, then it is the unique global minimum of (1).

Suppose $f(\boldsymbol{X})$ satisfies the $(2r,4r)$-restricted strong convexity and smoothness condition (3) with positive $\alpha$ and $\beta$. Assume $\boldsymbol{X}^{\star}$ is a critical point of $f(\boldsymbol{X})$ with $\operatorname{rank}(\boldsymbol{X}^{\star})=r^{\star}\leq r$. Then $\boldsymbol{X}^{\star}$ is the global minimum of (1), i.e.,

and the equality holds only at $\boldsymbol{X}=\boldsymbol{X}^{\star}$.

First note that if $\boldsymbol{X}^{\star}$ is a critical point of $f(\boldsymbol{X})$, then

where $\widetilde{\boldsymbol{X}}=t\boldsymbol{X}^{\star}+(1-t)\boldsymbol{X}$ for some $t\in$. This Taylor expansion together with $\nabla f(\boldsymbol{X}^{\star})={\bf 0}$ and (3) (both $\widetilde{\boldsymbol{X}}$ and $\boldsymbol{X}^{\prime}-\boldsymbol{X}^{\star}$ have rank at most $2r$) gives

Although the new variable $\boldsymbol{W}$ has much smaller size than $\boldsymbol{X}$ when $r\ll\min\{n,m\}$, the objective function in the factored problem (2) may have a much more complicated landscape due to the bilinear form about $\boldsymbol{U}$ and $\boldsymbol{V}$. The reformulated objective function $h(\boldsymbol{U},\boldsymbol{V})$ could introduce spurious local minima or degenerate saddle points even when $f(\boldsymbol{X})$ is convex. Our goal is to guarantee that this does not happen.

We remark that $\boldsymbol{W}^{\star}$ is still a global minimizer of the factored problem (5) since $f(\boldsymbol{X})$ achieves its global minimum over the low-rank set of matrices at $\boldsymbol{X}^{\star}$ and $g(\boldsymbol{W})$ also achieves its global minimum at $\boldsymbol{W}^{\star}$. The regularizer $g(\boldsymbol{W})$ is applied to force the difference between the two Gram matrices of $\boldsymbol{U}$ and $\boldsymbol{V}$ to be as small as possible. The global minimum of $g(\boldsymbol{W})$ is , which is achieved when $\boldsymbol{U}$ and $\boldsymbol{V}$ have the same Gram matrices, i.e., when $\boldsymbol{W}$ belongs to

III-B Main Results

Our main argument is that, under certain conditions on $f(\boldsymbol{X})$, the objective function $\rho(\boldsymbol{W})$ has no spurious local minima and satisfies the strict saddle property. This is equivalent to categorizing all the critical points into two types: 1) the global minima which correspond to the global solution of the original convex problem (1) and 2) strict saddles such that the Hessian matrix $\nabla^{2}\rho(\boldsymbol{W})$ evaluated at these points has a strictly negative eigenvalue. We formally establish this in the following theorem, whose proof is given in the next section.

For any $\mu>0$, each critical point $\boldsymbol{W}=\begin{bmatrix}\boldsymbol{U}\\ \boldsymbol{V}\end{bmatrix}$ of $\rho(\boldsymbol{W})$ defined in (5) satisfies

Equation (7) shows that any critical point $\boldsymbol{W}$ belongs to $\mathcal{E}$ for the objective function in the factored problem (5) with any positive $\mu$. This demonstrates the reason for adding the regularizer $g(\boldsymbol{U},\boldsymbol{V})$. Thus, any iterative optimization algorithm converging to some critical point of $\rho(\boldsymbol{W})$ results in a solution within $\mathcal{E}$. Furthermore, the strict saddle property along with the lack of spurious local minima ensures that a number of iterative optimization algorithms find the global minimum.

The constants appearing in Theorem 3 are not optimized. We use $\mu\leq\frac{1}{16}\alpha$ simply to include $\mu=\frac{1}{16}$ which is utilized for the matrix sensing problem in . If the ratio between the restricted strong convexity and smoothness constants $\frac{\beta}{\alpha}\leq 1.4$, then we can show that $\rho(\boldsymbol{W})$ has no spurious local minima and obeys the strict saddle property for any $\mu\leq\frac{1}{4}\alpha$ (where $\mu=\frac{1}{4}$ is utilized for the matrix sensing problem in ). In all cases, a smaller $\mu$ yields a more negative constant in (8); see Section IV for more discussion on this. This implies that when the restricted strong convexity constant $\alpha$ is not provided a priori, one can always choose a small $\mu$ to ensure the strict saddle property holds, and hence guarantee the global convergence of many iterative optimization algorithms.

The constant $1.5$ for the dynamic range $\frac{\beta}{\alpha}$ in Theorem 3 is also not optimized and it is possible to slightly relax this constraint with more sophisticated analysis. However, the following example involving weighted symmetric matrix factorization implies that the room for improving this constant is rather limited. Let

Now consider the following weighted low-rank matrix factorization:

whose gradient $\nabla h(\boldsymbol{U})$ and Hessian $\nabla^{2}h(\boldsymbol{U})$ are given by:

and $\lambda_{2}=4a>0$. We conclude that this $\boldsymbol{U}$ is a strict saddle point when $a<2$ and a spurious local minimum when $a>2$. This weighted symmetric matrix factorization problem (9) satisfies the restricted strong convexity and smoothness condition (3) with constants $\alpha=\|\boldsymbol{\Omega}\|_{\min}^{2}=1$ and $\beta=\|\boldsymbol{\Omega}\|_{\max}^{2}=1+a$ (where $\|\boldsymbol{\Omega}\|_{\min}$ and $\|\boldsymbol{\Omega}\|_{\max}$ represent the smallest and largest entries in $\boldsymbol{\Omega}$; see Section III-C). Thus, we have a counter example which demonstrates the existence of spurious local minima when $\frac{\beta}{\alpha}>3$.

We finally remark that although Theorem 3 requires the additional regularizer (4), empirical evidence (see experiments in Section V) shows we can get rid of this regularizer for many iterative algorithms with random initialization.

We prove Theorem 3 in Section IV. Before proceeding, we present two stylized applications of Theorem 3 in matrix sensing and weighted low-rank approximation.

III-C Stylized Applications

We first consider the implication of Theorem 3 in the matrix sensing problem where

holds for any $n\times m$ matrix $\boldsymbol{X}$ with $\operatorname{rank}(\boldsymbol{X})\leq r$.

Note that, in this case, the gradient of $f(\boldsymbol{X})$ at $\boldsymbol{X}^{\star}$ is

which implies that $\boldsymbol{X}^{\star}$ is a critical point of $f(\boldsymbol{X})$. The Hessian quadrature form $\nabla^{2}f(\boldsymbol{X})[\boldsymbol{Y},\boldsymbol{Y}]$ for any $n\times m$ matrices $\boldsymbol{X}$ and $\boldsymbol{Y}$ is given by

If $\mathcal{A}$ satisfies the $4r$-restricted isometry property with constant $\delta_{4r}$, then $f(\boldsymbol{X})$ satisfies the $(2r,4r)$-restricted strong convexity and smoothness condition (3) with constants $\alpha=1-\delta_{4r}$ and $\beta=1-\delta_{4r}$ since

for any rank-$4r$ matrix $\boldsymbol{Y}$. Now, applying Theorem 3, we can characterize the geometry for the following matrix sensing problem with the factorization approach:

where $g(\boldsymbol{U},\boldsymbol{V})$ is the added regularizer defined in (4).

Suppose $\mathcal{A}$ satisfies the $4r$-RIP with constant $\delta_{4r}\leq\frac{1}{5}$, and set $\mu\leq\frac{1-\delta_{4r}}{16}$. Then the objective function in (11) has no spurious local minima and satisfies the strict saddle property.

This result follows directly from Theorem 3 by noting that $\frac{\beta}{\alpha}=\frac{1+\delta_{4r}}{1-\delta_{4r}}\leq 1.5$ if $\delta_{4r}\leq\frac{1}{5}$. We remark that Park et al. [19, Theorem 4.3] provided a similar geometric result for (11). Compared to their result which requires $\delta_{4r}\leq\frac{1}{100}$, our result has a much weaker requirement on the RIP of the measurement operator.

III-C2 Weighted Low-Rank Matrix Factorization

We now consider the implication of Theorem 3 in the weighted matrix factorization problem , where

Here $\boldsymbol{\Omega}$ is an $n\times m$ weight matrix consisting of positive elements and $\circ$ denotes the point-wise product between two matrices. In this case, the gradient of $f(\boldsymbol{X})$ at $\boldsymbol{X}^{\star}$ is

which implies that $\boldsymbol{X}^{\star}$ is a critical point of $f(\boldsymbol{X})$. The Hessian quadrature form $\nabla^{2}f(\boldsymbol{X})[\boldsymbol{Y},\boldsymbol{Y}]$ for any $n\times m$ matrices $\boldsymbol{X}$ and $\boldsymbol{Y}$ is given by

Thus $f(\boldsymbol{X})$ satisfies the $(2r,4r)$-restricted strong convexity and smoothness condition (3) with constants $\alpha=\|\boldsymbol{\Omega}\|_{\min}^{2}$ and $\beta=\|\boldsymbol{\Omega}\|_{\max}^{2}$ since

where $\|\boldsymbol{\Omega}\|_{\min}$ and $\|\boldsymbol{\Omega}\|_{\max}$ represent the smallest and largest entries in $\boldsymbol{\Omega}$, respectively. Now we consider the following weighted matrix factorization problem:

where $g(\boldsymbol{U},\boldsymbol{V})$ is the added regularizer defined in (4). For an arbitrary weight matrix $\boldsymbol{\Omega}$, it is proven that the weighted low-rank factorization can be NP-hard and has spurious local minima. When the elements in the weight matrix $\boldsymbol{\Omega}$ are concentrated, it is expected that (12) can be efficiently solved by a number of iterative optimization algorithms as it is close to an (unweighted) matrix factorization problem (where $\boldsymbol{\Omega}$ is a matrix of ones) which obeys the strict saddle property . The following result characterizes the geometric structure in the objection function of (12) by directly applying Theorem 3.

Suppose $\boldsymbol{\Omega}$ satisfies $\frac{\|\boldsymbol{\Omega}\|_{\max}^{2}}{\|\boldsymbol{\Omega}\|_{\min}^{2}}\leq 1.5$. Set $\mu\leq\frac{\|\boldsymbol{\Omega}\|_{\min}^{2}}{16}$. Then the objective function in (12) has no spurious local minima and satisfies the strict saddle property.

III-C3 1-bit Matrix Completion

for all $(i,j)\in\Omega$. Typical choices for $q$ include the logistic regression model where $q(x)=\frac{e^{x}}{1+e^{x}}$ and the probit regression model where $q(x)=1-\Phi(-x/\sigma)=\Phi(x/\sigma)$. Here $\Phi$ is the cumulative distribution function (CDF) of a mean-zero Gaussian distribution with variance $\sigma^{2}$. In , the authors attempt to recover $\boldsymbol{X}^{\diamond}$ from the incomplete nonlinear measurements $\{Y_{ij}\}_{(i,j)\in\Omega}$ by minimizing the negative log-likelihood function

which results in a maximum likelihood (ML) estimate.

We note that $F_{\Omega,\boldsymbol{Y}}$ is a convex function for both the logistic model and the probit model. The following result also establishes that $F_{\Omega,\boldsymbol{Y}}$ satisfies the restricted strong convexity and smoothness condition if we observe full 1-bit measurements, i.e., $\Omega=[n]\times[m]$.

Then $F_{\Omega,\boldsymbol{Y}}$ satisfies the restricted strong convexity and smoothness condition:

The proof of Lemma 1 is given in Appendix A. Now we consider the logistic regression model where $q(x)=\frac{e^{x}}{1+e^{x}}$.

Suppose $\Omega=[n]\times[m]$ and $\gamma\leq 1.3$. Consider the logistic regression model where $q(x)=\frac{e^{x}}{1+e^{x}}$. Then $F_{\Omega,\boldsymbol{Y}}$ satisfies the restricted strong convexity and smoothness condition with

Applying Lemma 1 with direct calculation gives

where $q^{\prime}(x)=\frac{e^{x}}{(1+e^{x})^{2}}$. Now if we restrict $\|\boldsymbol{X}\|_{\infty}\leq 1.3$, we have

Under the assumption that $\boldsymbol{X}^{\diamond}$ is low-rank, a nuclear norm constraint is utilized in to force a low-rank solution. Corollary 3 implies that we can apply matrix factorization for 1-bit matrix recovery given that the elements of $\boldsymbol{X}$ are bounded. For the setting where $\Omega$ is only a subset of $[n]\times[m]$, considered the 1-bit matrix completion problem with the rank constraint and established a stronger statistical recovery guarantee than that in . Empirical evidence (see and Section V-C) supports that matrix factorization also works for 1-bit matrix completion.

IV Proof of Theorem 3

In this section, we provide a formal proof of Theorem 3. The main argument involves showing that each critical point of $\rho(\boldsymbol{W})$ either corresponds to the global solution of (1) or is a strict saddle whose Hessian $\nabla^{2}\rho(\boldsymbol{W})$ has a strictly negative eigenvalue. Specifically, we show that $\boldsymbol{W}$ is a strict saddle by arguing that the Hessian $\nabla^{2}\rho(\boldsymbol{W})$ has a strictly negative curvature along $\boldsymbol{\Delta}:=\boldsymbol{W}-\boldsymbol{W}^{\star}\boldsymbol{R}$, i.e., $[\nabla^{2}\rho(\boldsymbol{W})](\boldsymbol{\Delta},\boldsymbol{\Delta})\leq-\tau\|\boldsymbol{\Delta}\|_{F}^{2}$ for some $\tau>0$. Here $\boldsymbol{R}$ is an $r\times r$ orthonormal matrix such that the distance between $\boldsymbol{W}$ and $\boldsymbol{W}^{\star}$ rotated through $\boldsymbol{R}$ is as small as possible.

We first present some useful results. The $(2r,4r)$-restricted strong convexity and smoothness assumption (3) implies the following isometry property, whose proof is given in Appendix B.

Suppose the function $f(\boldsymbol{X})$ satisfies the $(2r,4r)$-restricted strong convexity and smoothness condition (3) with positive $\alpha$ and $\beta$. Then for any $n\times m$ matrices $\boldsymbol{Z},\boldsymbol{G},\boldsymbol{H}$ of rank at most $2r$, we have

We remark that Lemma 2 is a variant of [19, Lemma 3.2]. While the result there requires the $4r$-RIP condition of the objective function, our result depends on the $(2r,4r)$-restricted strong convexity and smoothness condition. Our result is also slightly tighter than [19, Lemma 3.2].

If $\boldsymbol{C}={\bf 0}$, then we have

We present one more useful result in the following Lemma.

Finally, we provide the gradient and Hessian expressions for $\rho(\boldsymbol{W})$. The gradient of $\rho(\boldsymbol{W})$ is given by

IV-B The Formal Proof

Any critical point $\boldsymbol{W}$ of $\rho(\boldsymbol{W})$ satisfies $\nabla\rho(\boldsymbol{W})={\bf 0}$, i.e.,

Now we turn to prove the strict saddle property and that there are no spurious local minima.

First, note that as guaranteed by Proposition 1, $\boldsymbol{X}^{\star}$ is the unique $n\times m$ matrix with rank at most $r$. Also the gradient of $f(\boldsymbol{X})$ vanishes at $\boldsymbol{X}^{\star}$ since (1) is an unconstraint optimization problem. Denote the set of critical points of $\rho(\boldsymbol{W})$ by

We separate $\mathcal{C}$ into two subsets:

satisfying $\mathcal{C}=\mathcal{C}_{1}\cup\mathcal{C}_{2}$. Since any critical point $\boldsymbol{W}$ satisfies (18), $g(\boldsymbol{W})$ achieves its global minimum at $\boldsymbol{W}$. Also $f(\boldsymbol{X})$ achieves its global minimum at $\boldsymbol{X}^{\star}$. We conclude that $\boldsymbol{W}$ is the globally optimal solution of $\rho$ for any $\boldsymbol{W}\in\mathcal{C}_{1}$. If we show that any $\boldsymbol{W}\in\mathcal{C}_{2}$ is a strict saddle, then we prove that there are no spurious local minima as well as the strict saddle property. Thus, the remaining part is to show that $\mathcal{C}_{2}$ is the set of strict saddles.

To show that $\mathcal{C}_{2}$ is the set of strict saddles, it is sufficient to find a direction $\boldsymbol{\Delta}$ along which the Hessian has a strictly negative curvature for each of these points. We construct $\boldsymbol{\Delta}=\boldsymbol{W}-\boldsymbol{W}^{\star}\boldsymbol{R}$, the difference from $\boldsymbol{W}$ to its nearest global factor $\boldsymbol{W}^{\star}$, where

The following result (which is proved in Appendix E) states that $\Pi_{1}$ is strictly negative, while the remaining terms are relatively small, though they may be nonnegative:

where $(i)$ utilizes Lemmas 2 and 4, $(ii)$ utilizes the following inequality (which is proved in Appendix F)

and $(ii)$ holds because $\frac{\beta}{\alpha}\leq 1.5$ and $\mu\leq\frac{1}{16}\alpha$. Thus, if $\boldsymbol{X}\neq\boldsymbol{X}^{\star}$, $\left[\nabla^{2}\rho(\boldsymbol{X})\right](\boldsymbol{\Delta},\boldsymbol{\Delta})$ is always negative. This implies that $\boldsymbol{W}$ is a strict saddle.

To complete the proof, we utilize Lemma 3 to further bound the last term in (23):

From (23), we observe that a smaller $\mu$ yields a more negative bound on $\left[\nabla^{2}\rho(\boldsymbol{X})\right](\boldsymbol{\Delta},\boldsymbol{\Delta})$. This can be explained intuitively as follows. First note that any critical point $\boldsymbol{W}$ satisfies (18) provided $\mu>0$, no matter how large or small $\mu$ is. The Hessian information about $g(\boldsymbol{W})$ is represented by the terms $\Pi_{3}$ and $\Pi_{4}$. We have

where the last line holds since for any $r\times r$ matrix $\boldsymbol{A}$,

Thus the Hessian of $\rho$ evaluated at any critical point $\boldsymbol{W}$ is a PSD matrixThis can also be observed since any critical point $\boldsymbol{W}$ is a global minimum point of $\rho(\boldsymbol{W})$, which directly indicates that $\nabla^{2}\rho(\boldsymbol{W})\succeq{\bf 0}$. instead of having a negative eigenvalue. In low-rank, PSD matrix optimization problems, the corresponding objective function (without any regularizer such as $g(\boldsymbol{W})$) is proved to have the strict saddle property . Therefore, $h(\boldsymbol{W})$ is also expected to have the strict saddle property, and so is $\rho(\boldsymbol{W})$ when $\mu$ is small, i.e., the Hessian of $g(\boldsymbol{W})$ has little influence on the Hessian of $\rho(\boldsymbol{W})$ when $\mu$ is small. Our results also indicate that when the restricted strict convexity constant $\alpha$ is not provided a priori, we can always choose a small $\mu$ to ensure the strict saddle property of $\rho(\boldsymbol{W})$ is met, and hence we are guaranteed the global convergence of a number of local search algorithms applied to (5).

V Experiments

In this section, we present a set of experiments on matrix sensing, matrix completion, and 1-bit matrix completion to demonstrate the performance of iterative algorithms for low-rank matrix optimization. Unless noted otherwise, we denote the matrix factorization approach by NVX and use the minFunc packageSoftware available at https://www.cs.ubc.ca/$\sim$schmidtm/Software/minFunc.html to perform the local search algorithms for the factored problem.

where the entries of each $n\times m$ matrix $\boldsymbol{Y}_{i}$ are independent and identically distributed (i.i.d.) normal random variables with zero mean and variance $\frac{1}{p}$ for $i\in\{1,2,\ldots p\}$. For each pair of $r$ and the number of measurements, 10 Monte Carlo trials are carried out and for each trial, and we claim matrix recovery to be successful if the relative reconstruction error satisfies

where we denote by $\widehat{\boldsymbol{X}}$ the reconstructed matrix. Figure 1 displays the phase transition for factorized gradient descent starting from a random initialization, the singular value projection (SVP) method proposed in which requires a SVD in each iteration, and the convex approach which solves

We see that there are only negligible differences between the different approaches for matrix sensing; these approaches also have very similar performance guarantees when the Gaussian sensing operator $\mathcal{A}$ satisfies the RIP . We note that with or without the regularizer $g$ as defined in (4), local search algorithms have similar performance with random initialization. Hence, throughout all of the experiments, we simply discard the regularizer $g$, but we stress that identical performance is observed if we have this regularizer $g$.

V-B Matrix Completion

We compare the performance of the matrix factorization approach with SVP , the convex approach, and singular value thresholdingSoftware available at http://svt.stanford.edu/ (SVT) for matrix completion where we want to recover a low-rank matrix $\boldsymbol{X}^{\star}$ from incomplete measurements $\{X^{\star}_{ij}\}_{(i,j)\in\Omega}$, where $\Omega\subset[n]\times[m]$. Let $\mathcal{P}_{\Omega}$ denote the projection onto the index set $\Omega$. The convex approach (denoted by CVX) attempts to use the nuclear norm as a convex relaxation of the rankness and solves

Though $\mathcal{P}_{\Omega}$ does not satisfy the $r$-RIP (10) for all low-rank matrices $\boldsymbol{X}$, it satisfies the RIP when restricted to low-rank incoherent matrices.

[48, Theorem 4.2] Without loss of generality, assume $n\geq m$. There exists a constant $C\geq 0$ such that for $\Omega\in[n]\times[m]$ chosen according to the Bernouli model with density greater than $Cu^{2}r^{2}\log n/\delta^{2}m$, with probability at least $1-e^{-n\log n}$, the RIP holds for all $\mu$-incoherent matrices $\boldsymbol{X}$ of rank at most $r$.

Thus, if local search algorithms (such as gradient descent) start with a random initialization and the iterates remain incoherent, then Theorem 3 guarantees the global convergence of the matrix factorization approach with these algorithms. We note that this hypothesis is also required for SVP . Though we can add a regularizer for incoherence as in , empirical evidence supports this hypothesis that the iterates in gradient descent are incoherent.

In the first set of experiments, we set $n=m=100$ and vary the rank $r$ from $1$ to $30$. Similar to the setup for matrix sensing in Section V-A, we generate a rank-$r$ random matrix and randomly obtain $p$ entries, i.e., $|\Omega|=p$. Figure 3 displays the phase transition for gradient descent with a random initialization, SVP , singular value thresholding (SVT) , and the convex approach. As can been seen, the matrix factorization approach has similar phase transition to SVP, and is slightly better than SVT and the convex approach in terms of the number of measurements needed for successful recovery.

In the second set of experiments, we set $r=5$ and $p=3r(2n-r)$ (3 times the number of degrees of freedom within a rank-$r$ $n\times n$ matrix), and vary $n$ from $40$ to $5120$. We compare the time needed for the four approaches in Figure 4; our matrix factorization approach is much faster than the other methods. The time savings for the matrix factorization approach comes from avoiding performing the SVD, which is needed both for SVT and SVP in each iteration. We also observe that convex approach has the highest computational complexity and is not scalable (which is the reason that we only present its time for $n$ up to $640$).

V-C 1-bit Matrix Completion

In the last set of experiments, we compare the performance of the matrix factorization approach with the convex approachSoftware available at http://mdav.ece.gatech.edu/software/ in for 1-bit matrix completion. We first note that to make the recovery problem well-posed, a constraint on $\|\boldsymbol{X}\|_{\infty}$ (the entry-wise maximum of the matrix $\boldsymbol{X}$) is applied in to require that the matrix is not too “spiky”. Instead of using the constraint on $\|\boldsymbol{X}\|_{\infty}$, we add a smooth regularizer $\|\boldsymbol{X}\|_{F}^{2}$ and turn to minimize the following objective function

To evaluate the performance of this factorization approach on 1-bit matrix completion, we generate $n\times r$ matrices $\boldsymbol{U}^{\diamond}$ and $\boldsymbol{V}^{\diamond}$ with entries drawn i.i.d. from a uniform distribution on $[-\frac{1}{2},\frac{1}{2}]$ and construct a random $n\times n$ matrix $\boldsymbol{X}^{\diamond}$ with rank $r$. Similar to the setup in , the matrix is then scaled so that $\|\boldsymbol{X}^{\diamond}\|=1$. We obtain 1-bit observations $\{Y_{i,j}\}_{(i,j)\in\Omega}$ by adding Gaussian noise of variance $\sigma^{2}$ and recording the sign of the resulting value (15), where the subset of indices $\Omega$ is chosen at random with $\operatorname{E}|\Omega|=p$. We compare the performance of the factorization approach and the convex approach over a range of different values of $n$, $p$, $r$ or $\sigma$. Figures 5(a)-(d) show the normalized squared Frobenius norm of the error $\frac{\|\widehat{\boldsymbol{X}}-\boldsymbol{X}^{\diamond}\|}{\|\boldsymbol{X}^{\diamond}\|_{F}^{2}}$ (where $\widehat{\boldsymbol{X}}$ denotes the reconstructed matrix) and average the results over 10 draws of Monte Carlo trials. We observe that matrix factorization approach has slightly better performance than the convex approach for 1-bit matrix completion . Note that this phenomenon (the factorization approach having better performance) is also observed in . We repeat these experiments but obtaining 1-bit observations with the logistic regression model where $g(x)=\frac{e^{x}}{1+e^{x}}$ for (15) and display the results in Figure 6.

VI Conclusion

This paper considers low-rank matrix optimization on general (nonsymmetric and rectangular) matrices with general objective functions. By focusing on general objective functions, we provide a unifying framework for low-rank matrix optimizations with the factorization approach. Although the resulting optimization problem is not convex, we show that the reformulated objection function has a simple landscape: there are no spurious local minima and any critical point not being a local minimum is a strict saddle such that the Hessian evaluated at this point has a strictly negative eigenvalue. These properties guarantee that a number of iterative optimization algorithms (such as gradient descent and the trust region method) will converge to the global optimum from a random initialization.

Appendix A Proof of Lemma 1

We compute the partial derivative of $F_{\Omega,\boldsymbol{Y}}$ in terms of $X_{i,j}$ as

Appendix B Proof of Proposition 2

This proof follows similar steps to the proof of [51, Lemma 2.1]. First note that the bilinear form $[\nabla^{2}f(\boldsymbol{Z})](\boldsymbol{G},\boldsymbol{H})=\sum_{i,j,k,l}\frac{\partial^{2}f(\boldsymbol{Z})}{\partial\boldsymbol{Z}_{ij}\partial\boldsymbol{Z}_{kl}}\boldsymbol{G}_{ij}\boldsymbol{H}_{kl}$ implies $[\nabla^{2}f(\boldsymbol{Z})](\boldsymbol{G},\boldsymbol{H})$ is invariant under all scalings for both $\boldsymbol{G}$ and $\boldsymbol{H}$, i.e.,

Now suppose both $\boldsymbol{G}$ or $\boldsymbol{H}$ are nonzero. By the scaling invariance property of both sides in (3), we assume $\|\boldsymbol{G}\|_{F}=\|\boldsymbol{H}\|_{F}=1$ without loss of generality. Note that the $(2r,4r)$-restricted strong convexity and smoothness condition (3) implies

Appendix C Proof of Lemma 2

It follows from (19) and (20) that any critical point $\boldsymbol{W}$ satisfies

On the other hand, we give an upper bound on the right hand side of (29):

Appendix D Proof of Lemma 3

When $\boldsymbol{C}\neq{\bf 0}$, the proof follows directly from the following results.

If $\boldsymbol{C}={\bf 0}$, then we have

Appendix E Proof of (22)

We prove the upper bounds for the four terms as follows.

Bounding term $\Pi_{1}$: Utilizing the fact that $\boldsymbol{\Delta}_{\boldsymbol{U}}=\boldsymbol{U}-\boldsymbol{U}^{\star}\boldsymbol{R}$ and $\boldsymbol{\Delta}_{\boldsymbol{V}}=\boldsymbol{V}-\boldsymbol{V}^{\star}\boldsymbol{R}$, we have

where $(i)$ follows from (19) and (20), $(ii)$ utilizes $\nabla f(\boldsymbol{X}^{\star})={\bf 0}$, and $(iii)$ follows by using the $(2r,4r)$-restricted strict convexity property (3):

where the first line follows from the integral form of the mean value theorem for vector-valued functions, and the second line uses the fact that both $t\boldsymbol{X}+(1-t)\boldsymbol{X}^{\star}$ and $\boldsymbol{X}-\boldsymbol{X}^{\star}$ have rank at most $2r$, and the $(2r,4r)$-restricted strong convexity of the Hessian $\nabla^{2}f(\cdot)$.

Bounding term $\Pi_{2}$: By the smoothness condition (3), we have

Appendix F Proof of (24)

To show (24), expanding the left hand side of (24), it is equivalent to show

Thus, we obtain (24) by noting that the above equation is equivalent to

References