In all of these settings, we often encounter the following rank-constrained optimization problem: minimize

where the objective function f : R n×m → R is smooth. Whether the objective function f is convex or nonconvex, the rank constraint renders low-rank matrix optimizations of the form (1) highly nonconvex and computationally NP-hard in general [6]. Significant efforts have been devoted to transforming (1) into a convex problem by replacing the rank constraint with one involving the nuclear norm. This strategy has been widely utilized in matrix inverse problems [7] arising in signal processing [5], machine learning [8], and control [6]. With convex analysis techniques, nuclear norm minimization has been proved to provide optimal performance in recovering low-rank matrices [9]. However, in spite of the optimal performance, solving nuclear norm minimization is very computationally expensive even with specialized first-order algorithms. For example, the singular value thresholding algorithm [10] requires performing an expensive singular value decomposition (SVD) in each iteration, making it computationally prohibitive in large-scale settings. This prevents nuclear norm minimization from scaling to practical problems.

To relieve the computational bottleneck, recent studies propose to factorize the variable into X = UV T , and optimize over the n × r and m × r matrices U and V rather than the n × m matrix X. The rank constraint in (1) then is automatically satisfied through the factorization. This strategy is usually referred to as the Burer-Monteiro type decomposition after the authors in [11], [12]. Plugging this parameterization of X in (1), we can recast the program into the following one: minimize U ∈R n×r ,V ∈R m×r h(U , V ):=f (UV T ).

(2)

The bilinear nature of the parameterization renders the objective function of (2) nonconvex. Hence, it can potentially have spurious local minima (i.e., local minimizers that are not global minimizers) or even saddle points. With technical innovations in analyzing the landscape of nonconvex functions, however, several recent works have shown that the factored objective function h(U , V ) in certain matrix inverse problems has no spurious local minima [13]- [15].

In this paper, we provide a comprehensive geometric analysis for solving general low-rank optimizations of the form (1) using the factorization approach (2). Our work actually rests on the recent works [16]- [20] ensuring a number of iterative optimization methods (such as gradient descent) converge to a local minimum with random initialization provided the problem satisfies the so-called strict saddle property (see Definition 3 in Section II). If the objective function further obeys the robust strict saddle property [16] (see Definition 4 in Section II) or belongs to the class of so-called X functions [17], the recent works [16], [17] show that many local search algorithms can converge to a local minimum in polynomial time. The implications of this line of work have had a tremendous impact on a number of nonconvex problems in applied mathematics, signal processing, and machine learning.

We begin this paper in Section II with the notions of strict saddle, strict saddle property, and robust strict saddle property. Considering that many invariant functions are not strongly convex (or even convex) in any neighborhood around a local minimum point, we then provide a revised robust strict saddle property 1 requiring a regularity condition (see Definition 8 in Section II) rather than strong convexity near the local minimum points (which is one of the requirements for the strict saddle property). The stochastic gradient descent algorithm is guaranteed to converge to a local minimum point in polynomial time for problems satisfying the revised robust strict saddle property [16], [20].

In Section III, we consider the geometric analysis for solving general low-rank optimizations of the form (1) using the factorization approach (2). Provided the objective function f satisfies certain restricted strong convexity and smoothness conditions, we show that the low-rank optimization problem with the factorization (2) (with an additional regularizer-see Section III for the details) obeys the revised robust strict saddle property. In Section III-C, we consider a stylized application in matrix sensing where the measurement operator satisfies the restricted isometry property (RIP) [7]. In the case of Gaussian measurements, as guaranteed by this robust strict saddle property, a number of iterative optimizations can find the unknown matrix X ? of rank r in polynomial time with high probability when the number of measurements exceeds a constant times (n + m)r 2 .

Our main approach for analyzing the optimization geometry of ( 2) is based on the geometric analysis for the following non-square low-rank matrix factorization problem: given

In particular, we show the optimization geometry for the low-rank matrix factorization problem (3) is preserved for the general low-rank optimization (2) under certain restricted strong convexity and smoothness conditions on f . Thus, in Appendix A, we provide a comprehensive geometric analysis for (3), which can be viewed as an important foundation of many popular matrix factorization problems such as the matrix sensing problem and matrix completion. We show that the low-rank matrix factorization problem (3) (with an additional regularizer) has no spurious local minima and obeys the strict saddle property-that is the objective function in (3) has a directional negative curvature at all critical points but local minima-not only for the exact-parameterization case where rank(X ? )=r, but also for the over-parameterization case where rank(X ? ) <rand the under-parameterization case where rank(X ? ) >r . The strict saddle property and lack of spurious local minima ensure that a number of local search algorithms applied to the matrix factorization problem (3) converge to global optima which correspond to the best rank-r approximation to X ? . Further, we completely analyze the low-rank matrix factorization problem (3) for the exact-parameterization case and show that it obeys the revised robust strict saddle property.

Unlike the objective functions of convex optimizations that have simple landscapes, such as where all local minimizers are global ones, the objective functions of general nonconvex programs have much more complicated landscapes. In recent years, by exploiting the underlying optimization geometry, a surge of progress has been made in providing theoretical justifications for matrix factorization problems such as (2) using a number of previously heuristic algorithms (such as alternating minimization [21], gradient descent, and the trust region method). Typical examples include phase retrieval [22]- [24], blind deconvolution [25], [26], dictionary learning [27]- [29], phase synchronization [30] and matrix sensing and completion [14], [31]- [36].

These iterative algorithms can be sorted into two categories based on whether a good initialization is required. One set of algorithms consist of two steps: initialization and local refinement. Provided the function satisfies a regularity condition or similar properties, a good guess lying in the attraction basin of the global optimum can lead to global convergence of the following iterative step. We can obtain such initializations by spectral methods for phase retrieval [23], phase synchronization [30] and low-rank matrix recovery problems [31], [32], [37], [38]. As we have mentioned, a regularity condition is also adopted in the revised robust strict saddle property.

Another category of works attempt to analyze the landscape of the objective functions in a larger space rather than the regions near the global optima. We can further separate these approaches into two types based on whether they involve the strict saddle property or the robust strict saddle property. The strict saddle property and lack of spurious local minima are proved for low-rank, positive semidefinite (PSD) matrix recovery [13] and completion [14], PSD matrix optimization problems with generic objective functions [39], low-rank non-square matrix estimation from linear observations [15], low-rank nonsquare optimization problems with generic objective functions [40] and generic nuclear norm regularized problems [39]. The strict saddle property along with the lack of spurious local minima ensures a number of iterative algorithms such as gradient descent [16] and the trust region method [41] converge to the global minimum with random initialization [16], [18], [29].

A few other works which are closely related to our work attempt to study the global geometry by characterizing the landscapes of the objective functions in the whole space rather than the regions near the global optima or all the critical points. As we discussed before, a number of local search algorithms are guaranteed to find a local optimum (which is also the global optimum if there are no spurious local minima) because of this robust strict saddle property. In [16], the authors proved that tensor decomposition problems satisfy this robust strict saddle property. Sun et al. [22] studied the global geometry of the phase retrieval problem. The very recent work in [42] analyzed the global geometry for PSD low-rank matrix factorization of the form (3) and the related matrix sensing problem when the rank is exactly parameterized (i.e., r =r a n k ( X ? )). The factorization approach for matrix inverse problems with quadratic loss functions is considered in [36]. We extend this line by considering general rankconstrained optimization problems including a set of matrix inverse problems.

Finally, we remark that our work is also closely related to the recent works in low-rank matrix factorization of the form (3) and its variants [13]- [15], [31]- [33], [36], [40], [42]. As we discussed before, most of these works except [36], [42] (but including [15] which also focuses on nonsymmetric matrix sensing) only characterize the geometry either near the global optima or all the critical points. Instead, we characterize the globalgeometry for general (rather than PSD) low-rank matrix factorization and sensing. Because the analysis is different, the proof strategy in the present paper is also very different than that of [15], [40]. The results for PSD matrix sensing in [42] build heavily on the concentration properties of Gaussian measurements, while our results for matrix sensing depend on the RIP of the measurement operator and thus can be applied to other matrix sensing problems whose measurement operator is not necessarily from a Gaussian measurement ensemble. Also, [36] considers matrix inverse problems with quadratic loss functions and its proof strategy is very different than that in the present paper: the proof in [36] is specified to quadratic loss functions, while we consider the rank-constrained optimization problem with general objective functions in (1) and our proof utilizes the fact that the gradient and Hessian of the low-rank matrix sensing are respectively very close to those in low-rank matrix factorization. Furthermore, in terms of the matrix factorization, we show that the objective function in (3) obeys the strict saddle property and has no spurious local minima not only for exact-parameterization (r =rank ( X ? )), but also for over-parameterization (r>rank(X ? ))a n d under-parameterization (r<rank(X ? )). Local (rather than global) geometry results for exact-parameterization and under-parameterization are also covered in [40]. As noted above, the work in [36], [42] for low-rank matrix factorization only focuses on exact-parameterization (r =rank (X ? )). The under-parameterization implies that we can find the best rank-r approximation to X ? by many efficient iterative optimization algorithms such as gradient descent.

Before proceeding, we first briefly introduce some notation used throughout the paper. The symbols I and 0 respectively represent the identity and zero matrices with appropriate sizes. Also I n is used to denote the n × n identity matrix. For any natural number n,w el e t[n] or 1:n denote the set {1, 2, ..., n}.W eu s e|Ω| denote the cardinality (i.e., the number of elements) of a set Ω. MATLAB notations are adopted for matrix indexing; that is, for the n × m matrix A, its (i, j)-th element is denoted by

We say that a (not necessarily square) matrix A ∈ R n×r is orthonormal if the columns of A are normalized and orthogonal to each other, i.e., A T A = I.T h es e to fr × r orthonormal matrices is denoted by O r := {R ∈ R r×r : R T R = I}. We say that a (not necessarily square) matrix A ∈ R n×r is orthogonal if hA[:,i], A[:,j]i =0for all i 6 = j; that is the columns of A are orthogonal to each other, but are not necessarily normalized and could even be zero.

If a function h(U , V ) has two arguments, U ∈ R n×r and V ∈ R m×r , we occasionally use the notation h(W ) when we put these two arguments into a new one as

for all i ∈ {1, 2,...,n},j ∈{1, 2,...,m}. The Hessian of f (Z) can be viewed as an nm

for all i, j ∈{ 1,...,nm},w h e r ez[i] is the i-th entry of the vectorization of Z. An alternative way to represent the Hessian is by a bilinear form defined via

These two notations will be used interchangeably whenever the specific form can be inferred from context.

In this section, we provide a number of important definitions in optimization and group theory. To begin, suppose h(x):

Definition 2 (Strict Saddles; or Ridable Saddles in [29]): A critical point x is a strict saddle if the Hessian matrix evaluated at this point has a strictly negative eigenvalue, i.e., λ min (∇ 2 h(x)) < 0.

Definition 3 (Strict Saddle Property [16]): A twice differentiable function satisfies the strict saddle property if each Intuitively, the strict saddle property requires a function to have a directional negative curvature at all of the critical points but local minima. This property allows a number of iterative algorithms such as noisy gradient descent [16] and the trust region method [41] to further decrease the function value at all the strict saddles and thus converge to a local minimum.

In [16], the authors proposed a noisy gradient descent algorithm for the optimization of functions satisfying the robust strict saddle property.

Definition 4 (Robust Strict Saddle Property [16]): Given α, γ, , δ, a twice differentiable h(x) satisfies the (α, γ, , δ)-robust strict saddle property if for every point x at least one of the following applies:

1) There exists a local minimum point x ? such that kx ? -xk≤δ, and the function h(x 0 ) restricted to a 2δ neighborhood of x ? (i.e., kx ?x 0 k≤2δ)isα-strongly convex; 2) λ min ∇ 2 h(x) ≤-γ; 3) k∇h(x)k≥.

In words, the above robust strict saddle property says that for any point whose gradient is small, then either the Hessian matrix evaluated at this point has a strictly negative eigenvalue, or it is close to a local minimum point. Thus the robust strict saddle property not only requires that the function obeys the strict saddle property, but also that it is well-behaved (i.e., strongly convex) near the local minima and has large gradient at the points far way to the critical points.

Intuitively, when the gradient is large, the function value will decrease in one step by gradient descent; when the point is close to a saddle point, the noise introduced in the noisy gradient descent could help the algorithm escape the saddle point and the function value will also decrease; when the point is close to a local minimum point, the algorithm then converges to a local minimum. Ge et al. [16] rigorously showed that the noisy gradient descent algorithm (see [16,Algorithm 1]) outputs a local minimum in a polynomial number of steps if the function h(x) satisfies the robust strict saddle property.

It is proved in [16] that tensor decomposition problems satisfy this robust strict saddle property. However, requiring the local strong convexity prohibits the potential extension of the analysis in [16] for the noisy gradient descent algorithm to many other problems, for which it is not possible to be strongly convex in any neighborhood around the local minimum points. Typical examples include the matrix factorization problems due to the rotational degrees of freedom for any critical point. This motivates us to weaken the local strong convexity assumption relying on the approach used by [23], [31] and to provide the following revised robust strict saddle property for such problems. To that end, we list some necessary definitions related to groups and invariance of a function under the group action.

Definition 5 (Definition 7.1 [43])): A (closed) binary operation, •, is a law of composition that produces an element of a set from two elements of the same set. More precisely, let G be a set and a 1 ,a 2 ∈Gbe arbitrary elements. Then (a 1 ,a 2 ) → a 1 • a 2 ∈G.

Definition 6 (Definition 7.2 [43])): A group is a set G together with a (closed) binary operation • such that for any elements a, a 1 ,a 2 ,a 3 ∈G the following properties hold:

• There exists an identity element e ∈Gsuch that e • a = a • e = a. • There is an element a

With this definition, it is common to denote a group just by G without saying the binary operation • when it is clear from the context.

Definition 7: Given a function h(x):R n → R and a group G of operators on R n ,w es a yh is invariant under the group action (or under an element a of the group) if

for all x ∈ R n and a ∈G.

Suppose the group action also preserves the energy of x, i.e., ka(x)k = kxk for all a ∈G .S i n c ef o ra n yx ∈ R n , h(a(x)) = h(x) for all a ∈G, it is straightforward to stratify the domain of h(x) into equivalent classes. The vectors in each of these equivalent classes differ by a group action. One implication is that when considering the distance of two points x 1 and x 2 , it would be helpful to use the distance between their corresponding classes:

where the second equality follows because ka 1 (x 1 ) -

Another implication is that the function h(x) cannot possibly be strongly convex (or even convex) in any neighborhood around its local minimum points because of the existence of the equivalent classes. Before presenting the revised robust strict saddle property for invariant functions, we list two examples to illuminate these concepts.

Example 1: As one example, consider the phase retrieval problem of recovering an n-dimensional complex vector x ? from y i = b H i x ? ,i =1,...,p , the magnitude of its projection onto a collection of known complex vectors b 1 , b 2 ,...,b p [22], [23]. The unknown x ? can be estimated by solving the following natural least-squares formulation [22], [23] minimize

, where we note that here the domain of x is C n . For this case, we denote the corresponding

and the group action as a(x)=e jθ x,w h e r ea = e jθ is an element in G. It is clear that h(a(x)) = h(x) for all a ∈G. Due to this invariance of h(x), it is impossible to recover the global phase factor of the unknown x ? and the function h(x) is not strongly convex in any neighborhood of x ? . Example 2: As another example, we revisit the general factored low-rank optimization problem (2): minimize U ∈R n×r ,V ∈R m×r h(U , V )=f (UV T ).

We recast the two variables U , V into W as W = U V .

For this example, we denote the corresponding G = O r and the group action on W as a(W )= UR VR where a = R ∈G.W eh a v et h a th(a(W )) = h(W ) for all a ∈G since UR(VR) T = UV T for any R ∈O r . Because of this invariance, in general h(W ) is not strongly convex in any neighborhood around its local minimum points even though f (X) is a strongly convex function; see [42] for the symmetric low-rank factorization problem and Theorem 2 in Appendix A for the nonsymmetric low-rank factorization problem.

In the examples illustrated above, due to the invariance, the function is not strongly convex (or even convex) in any neighborhood around its local minimum point and thus it is prohibitive to apply the standard approach in optimization to show the convergence in a small neighborhood around the local minimum point. To overcome this issue, Candès et al. [23] utilized the so-called regularity condition as a sufficient condition for local convergence of gradient descent applied for the phase retrieval problem. This approach has also been applied for the matrix sensing problem [31] and semi-definite optimization [37].

Definition 8 (Regularity Condition [23], [31]): Suppose h(x):R n → R is invariant under the group action of the given group G.L e tx ? ∈ R n be a local minimum point of h(x). Define the set B(δ, x ? ) as

where the distance dist(x, x ? ) is defined in (4). Then we say the function h(x) satisfies the (α, β, δ)-regularity condition if for all x ∈ B(δ, x ? ),w eh a v e h∇h(x), x -a(x ? )i≥α dist(x, x ? )foot_2 + βk∇h(x)k 2 , (5) where a = arg min a 0 ∈G kx -a 0 (x ? )k.

We remark that (α, β) in the regularity condition (8) must satisfy αβ ≤ 1 4 since by applying Cauchy-Schwarz h∇h(x), x -a(x ? )i≤k∇h(x)k dist(x, x ? ) and the inequality of arithmetic and geometric means

Lemma 1: [23], [31] If the function h(x) restricted to a δ neighborhood of x ? satisfies the (α, β, δ)-regularity condition, then as long as gradient descent starts from a point x 0 ∈ B(δ, x ? ), the gradient descent update

with step size 0 <ν≤ 2β obeys x t ∈ B(δ, x ? ) and

The proof is given in [23]. To keep the paper self-contained, we also provide the proof of Lemma 1 in Appendix B. We remark that the decreasing rate 1 -2να ∈ [0, 1) since we choose ν ≤ 2β and αβ ≤ 1 4 . Now we establish the following revised robust strict saddle property for invariant functions by replacing the strong convexity condition in Definition 4 with the regularity condition.

Definition 9 (Revised Robust Strict Saddle Property for Invariant Functions): Given a twice differentiable h(x): R n → R and a group G, suppose h(x) is invariant under the group action and the energy of x is also preserved under the group action, i.e., h(a(x)) = h(x) and ka(x)k 2 = kxk 2 for all a ∈G.G i v e nα, β, γ, , δ, h(x) satisfies the (α, β, γ, , δ)robust strict saddle property if for any point x at least one of the following applies:

1) There exists a local minimum point x ? such that dist(x, x ? ) ≤ δ, and the function h(x 0 ) restricted to 2δ a neighborhood of x ? (i.e., dist(x 0 , x ? ) ≤ 2δ) satisfies the (α, β, 2δ)-regularity condition defined in Definition 8; 2) λ min ∇ 2 h(x) ≤-γ; 3) k∇h(x)k≥. Compared with Definition 4, the revised robust strict saddle property requires the local descent condition instead of strict convexity in a small neighborhood around any local minimum point. With the convergence guarantee in Lemma 1, the convergence analysis of the stochastic gradient descent algorithm in [16] for the robust strict saddle functions can also be applied for the revised robust strict saddle functions defined in Definition 9 with the same convergence rate. 2 We omit the details here and refer the reader to [20] for more details on this. In the rest of the paper, the robust strict saddle property refers to the one in Definition 9.

In this section, we consider the minimization of general rank-constrained optimization problems of the form (1) using the factorization approach (2) (which we repeat as follows):

where the rank constraint in ( 1) is automatically satisfied by the factorization approach. With necessary assumptions on f in Section III-A, we provide geometric analysis of the factored problem in Section III-B. We then present a stylized application in matrix sensing in Section III-C.

Before presenting our main results, we lay out the necessary assumptions on the objective function f (X). As is known, without any assumptions on the problem, even minimizing traditional quadratic objective functions is challenging. For this reason, we focus on problems satisfying the following two assumptions.

Assumption 1: f (X) has a critical point X ? ∈ R n×m which has rank r.

Assumption 2: f (X) is (2r, 4r)-restricted strongly convex and smooth, i.e., for any n × m matrices X, D with rank(X) ≤ 2r and rank(D) ≤ 4r, the Hessian of f (X) satisfies

for some positive a and b.

Assumption 1 is equivalent to the existence of a rank r X ? such that ∇f (X ? )=0, which is very mild and holds in many matrix inverse problems including matrix sensing [7], matrix completion [9] and 1-bit matrix completion [44], where the unknown matrix to be recovered is a critical point of f . Assumption 2 is also utilized in [32, Conditions 5.3 and 5.4] and [40], where weighted low-rank matrix factorization and a set of matrix inverse problems are proved to satisfy the (2r, 4r)-restricted strong convexity and smoothness condition (6). We discuss matrix sensing as a typical example satisfying this assumption in Section III-C.

Combining Assumption 1 and Assumption 2, we have that X ? is the unique global minimum of (1).

Proposition 1: Suppose f (X) satisfies the (2r, 4r)restricted strong convexity and smoothness condition ( 6) with positive a and b. Assume X ? is a critical point of f (X) with rank(X ? )=r.T h e nX ? is the global minimum of (1), i.e.,

and the equality holds only at X = X ? .

The proof of Proposition 1 is given in Appendix C. We note that Proposition 1 guarantees that X ? is the unique global minimum of (1) and it is expected that solving the factorized problem (9) also gives X ? . Proposition 1 differs from [40] in that it only requires X ? as a critical point, while [40] needs X ? as a global minimum of f . Before presenting the main result, we note that if f satisfies (6) with positive a and b and we rescale f as

It is clear that f and f 0 have the same optimization geometry (despite the scaling difference). Let a 0 = 2a a+b =1-c and b 0 = 2a a+b =1+c with c = b-a a+b .W eh a v e0 <a 0 ≤ 1 ≤ b 0 and a 0 + b 0 =2 . Thus, throughout the paper and without the generality, we assume

Now let

for any R ∈O r . We first introduce the following ways to stack U and V together that are widely used through the paper:

Before moving on, we note that for any solution

A sa ne x t r e m ee x a mple, R 1 = cI and R 2 = 1 c I where c can be arbitrarily large. In order to address this ambiguity (i.e., to reduce the search space of W for (3)), we utilize the trick in [15], [31], [32], [40] by introducing a regularizer ρ and turn to solve the following problem

where

We remark that W ? is still a global minimizer of the factored problem ( 29) since both the first term and ρ(W ) achieve their global minimum at W ? . The regularizer ρ(W ) is applied to force the difference between the Gram matrices of U and V as small as possible. The global minimum of ρ(W ) is 0,w h i c h is achieved when U and V have the same Gram matrices, i.e., when W belongs to

Informally, we can view (9) as finding a point from E that also minimizes the first term in (9). This is rigorously established in the following result which reveals that any critical point W of g(W ) belongs to E (that is U and V are balanced factors of their product UV T )f o ra n yµ>0. Lemma 2 ( [40, Theorem 3]): Suppose G(W ) is defined as in (9) with µ>0. Then any critical point W of G(W ) belongs to E, i.e.,

For completeness, we include the proof of Lemma 2 in Appendix D.

We now characterize the global optimization geometry of the factored problem (9). As explained in Section II that G(W ) is invariant under the matrices R ∈O r ,w efi r s t recall the discussions in Section II about the revised robust strict saddle property for the invariant functions. To that end, we follow the notion of the distance between equivalent classes for invariant functions defined in (4) and define the distance between W 1 and W 2 as follows

For convenience, we also denote the best rotation matrix R so that kW 1 -W 2 Rk F achieves its minimum by

which is also known as the orthogonal Procrustes problem [45]. The solution to the above minimization problem is characterized by the following lemma.

L e m m a3 ([ 4 5 ] ) :

An optimal solution for the orthogonal Procrustes problem ( 13) is given by

Moreover, we have

To ease the notation, we drop W 1 and W 2 in R(W 1 , W 2 ) and rewrite R instead of R(W 1 , W 2 ) when they (W 1 and W 2 ) are clear from the context. Now we are well equipped to present the robust strict saddle property for G(W ) in the following result.

Theorem 1: Define the following regions

Let G(W ) be defined as in (9) with µ = 1 2 . Suppose f (X) has a critical point X ? ∈ R n×m of rank r and satisfies the (2r, 4r)-restricted strong convexity and smoothness condition (6) with positive constants a =1-c, b =1+c and c ≤ 1 100

Then G(W ) has the following robust strict saddle property: 1) For any W ∈R 1 , G(W ) satisfies the local regularity condition:

where dist(W , W ? ) and R are defined in ( 12) and ( 13), respectively. 2) For any W ∈R 2 , G(W ) has a directional negative curvature, i.e.,

3) For any W ∈R 3 = R 0 3 ∪R 00 3 ∪R 000 3 , G(W ) has large gradient:

The proof of this result is given in Appendix L. The main proof strategy is to utilize Assumption 1 and Assumption 2 about the function f to control the deviation between the gradient (and the Hessian) of the general low-rank optimization (9) and the counterpart of the matrix factorization problem so that the landscape of the general low-rank optimization (9) has a similar geometry property. To that end, in Appendix A, we provide a comprehensive geometric analysis for the matrix factorization problem (3). The reason for choosing µ = 1 2 is also discussed in Appendix A-F. We note that the results in Appendix A are also of independent interest, as we show that the objective function in (3) obeys the strict saddle property and has no spurious local minima not only for exact-parameterization (r =rank ( X ? )), but also for over-parameterization (r>rank(X ? ))a n d under-parameterization (r<rank(X ? )). Several remarks follow.

Remark 1: Note that

Thus, we conclude that R 1 ∪R 2 ∪R 0 3 ∪R 00 3 ∪R 000 3 = R (n+m)×r . Now the convergence analysis of the stochastic gradient descent algorithm in [16], [20] for the robust strict saddle functions also holds for G(W ).

Remark 2: Theorem 1 states that the objective function for the general low-rank optimization (9) also satisfies the robust strict saddle property when (14) holds. The requirement for c in ( 14) can be weakened to ensure the properties of g(W ) are preserved for G(W ) in some regions. For example, the local regularity condition (15) holds when c ≤ 1 50 which is independent of X ? . With the analysis of the global geometric structure in G(W ), Theorem 1 ensures that many local search algorithms can converge to X ? (which is the the global minimum of (1) as guaranteed by Proposition 1) with random initialization. In particular, stochastic gradient descent when applied to the matrix sensing problem ( 22) is guaranteed to find the global minimum X ? in polynomial time.

Remark 3: Local (rather than global) geometry results for the general low-rank optimization ( 9) are also covered in [40], which only characterizes the geometry at all the critical points. Instead, Theorem 1 characterizes the global geometry for general low-rank optimization (9). Because the analysis is different, the proof strategy for Theorem 1 is also very different than that of [40]. Since [40] only considers local geometry, the result in [40] requires c ≤ 0.2, which is slightly less restrictive than the one in (14).

Remark 4: To explain the necessity of the requirement on the constants a and b in (14), we utilize the symmetric weighted PCA problem (so that we can visualize the landscape of the factored problem in Figure 1) as an example where the objective function is

where Ω ∈ R n×n contains positive entries. The Hessian quadratic form for f (X) is given by [∇ 2 f (X)](D, D)= kΩ Dk 2 F for any D ∈ R n×n . Thus, we have

Comparing with (6), we see that f satisfies the restricted strong convexity and smoothness conditions with the constants a

In this case, we also note that if each entry W ij is nonzero (i.e., min ij |Ω[i, j]| 2 > 0), the function f (X) is strongly convex, rather than only restrictively strongly convex, implying that (20) has a unique optimal solution X ? . By applying the factorization approach, we get the factored objective function

To illustrate the necessity of the requirement on the constants a and b as in (14) so that the factored problem (21) has no spurious local minima and obeys the robust strict saddle property, we set X ? = 11 11 which is a rank-1 matrix and can be factorized as X ? = U ? U ?T with U ? = 1 1 .

We then plot the landscapes of the factored objective function The global geometry of low-rank matrix recovery but with analysis customized to linear measurements and quadratic loss functions is also covered in [36], [42]. Since Theorem 1 only requires the (2r, 4r)-restricted strong convexity and smoothness property (6), aside from low-rank matrix recovery [46], it can also be applied to many other low-rank matrix optimization problems [47] which do not necessarily involve quadratic loss functions. Typical examples include 1-bit matrix completion [44], [48] and Poisson principal component analysis (PCA) [49]. We refer to [40] for more discussion on this issue. In next section, we consider a stylized application of Theorem 1 in matrix sensing and compare it with the result in [42].

In this section, we extend the previous geometric analysis to the matrix sensing problem minimize

where A : R n×m → R p is a known linear measurement operator and X ? is the unknown rank r matrix to be recovered. In this case, we have

The derivative of f (X) at X ? is ∇f (X ? )=A * A(X ? -X ? )=0, which implies that f (X) satisfies Assumption 1. The Hessian quadratic form ∇ 2 f (X)[D, D] for any n × m matrices X and D is given by

The following matrix Restricted Isometry Property (RIP) serves as a way to link the low-rank matrix factorization problem (29) with the matrix sensing problem (22) and certifies f (X) satisfying Assumption 2. Definition 10 (Restricted Isometry Property (RIP) [7], [50]): The map A : R n×m → R p satisfies the r-RIP with constant δ r iffoot_3

holds for any n × m matrix D with rank(D) ≤ r.

If A satisfies the 4r-restricted isometry property with constant δ 4r ,t h e nf (X) satisfies the (2r, 4r)-restricted strong convexity and smoothness condition (6) with constants a = 1 -δ 4r and b =1-δ 4r since

for any rank-4r matrix D. Comparing ( 24) with ( 6), we note that the RIP is stronger than the restricted strong convexity and smoothness property (6) as the RIP gives that (24) holds for all n × m matrices X, while Assumption 2 only requires that ( 6) holds for all rank-2r matrices. Now, applying Theorem 1, we obtain a similar geometric guarantee to Theorem 1 for the matrix sensing problem (22) when A satisfies the RIP.

3 , R 000 3 be the regions as defined in Theorem 5. Let G(W ) be defined as in (22) with µ = 1 2 and A satisfying the 4r-RIP with

Then G(W ) has the following robust strict saddle property: 1) For any W ∈R 1 , G(W ) satisfies the local regularity condition:

where dist(W , W ? ) and R are defined in ( 12) and ( 13), respectively. 2) For any W ∈R 2 , G(W ) has a directional negative curvature, i.e.,

3) For any W ∈R 3 = R 0 3 ∪R 00 3 ∪R 000 3 , G(W ) has large gradient:

Remark 6: Similar to ( 14), the requirement for δ 4r in (25) can be weakened to ensure the properties of g(W ) are preserved for G(W ) in some regions. For example, the local regularity condition (26) holds when δ 4r ≤ 1 50 which is independent of X ? . Note that Tu et al. [31,Section 5.4,(5.15)] provided a similar regularity condition. However, the result there requires δ 6r ≤ 1 25 and dist(W , W ? ) ≤ 1 2 √ 2 σ r (X ? ) which defines a smaller region than R 1 . Based on this local regularity condition, Tu et al. [31] showed that gradient descent with a good initialization (which is close enough to W ? ) converges to the unknown matrix W ? (and hence X ? ). With the analysis of the global geometric structure in G(W ), Theorem 1 ensures that many local search algorithms can find the unknown matrix X ? in polynomial time.

Remark 7: A Gaussian A will have the RIP with high probability when the number of measurements p is comparable to the number of degrees of freedom in an n × m matrix with rank r. By Gaussian A we mean the `-th element in y = A(X), y `,i sg i v e nb y

where the entries of each n × m matrix A `are independent and identically distributed normal random variables with zero mean and variance 1 p . Specifically, a Gaussian A satisfies (23) with high probability when [5], [7], [46] p r(n + m)

Now utilizing the inequality kX ? k F ≤ √ rkX ? k for ( 14), we conclude that in the case of Gaussian measurements, the robust strict saddle property is preserved for the matrix sensing problem with high probability when the number of measurements exceeds a constant times (n + m)r 2 κ(X ? ) 3 where κ(X ? )= σ1(X ? ) σr (X ? ) . This further implies that, when applying the stochastic gradient descent algorithm to the matrix sensing problem (22) with Gaussian measurements, we are guaranteed to find the unknown matrix X ? in polynomial time with high probability when

When X ? is an n × n PSD matrix, Li et al. [42] showed that the corresponding matrix sensing problem with Gaussian measurements has similar global geometry to the low-rank PSD matrix factorization problem when the number of measurements

Comparing ( 27) with (28), we find both results for the number of measurements needed depend similarly on the rank r,b u t slightly differently on the spectrum of X ? . We finally remark that the sampling complexity in (27) is O((n+m)r 2 ),whichis slightly larger than the information theoretically optimal bound O((n + m)r) for matrix sensing. This is because Theorem 1 is a direct consequence of Theorem 1 in which we directly characterize the landscapes of the objective functions in the whole space by combining the results for matrix factorization in Appendix A and the restricted strong convexity and smoothness condition. We believe this mismatch is an artifact of our proof strategy and could be mitigated by a different approach, like utilizing the properties of quadratic loss functions [36].

If one desires only to characterize the geometry for critical points, then O((n + m)r) measurements are enough to ensure the strict saddle property and lack of spurious local minima for matrix sensing [15], [40]. We finally note that for matrix completion where the RIP is not satisfied, [36] proves the robust strict saddle property for the factorization approach by utilizing an additional regularizer which promotes incoherence of W .

In this appendix, we consider the low-rank matrix factorization problem minimize

where ρ(W ) is the regularizer used in (9) and repeated here:

We provide a comprehensive geometric analysis for the matrix factorization problem (29). In particular, we show that the objective function in (29) obeys the strict saddle property and has no spurious local minima not only for exact-parameterization (r =r a n k ( X ? )), but also for over-parameterization (r>rank(X ? )) and under-parameterization (r<rank(X ? )). For the exact-parameterization case, we further show that the objective function satisfies the robust strict saddle property, ensuring global convergence of many local search algorithms in polynomial time. As we believe these results are also of independent interest and to make it easy to follow, we only present the main results in this appendix and defer the proofs to other appendices.

Similar to (8), let X ? = ΦΣΨ T = r i=1 σ i φ i ψ T i be a reduced SVD of X ? ,w h e r eΣ is a diagonal matrix with σ 1 ≥ ••• ≥ σ r along its diagonal, and denote U ? = ΦΣ 1/2 R, V ? = ΨΣ 1/2 R for any R ∈O r . The following result to some degree characterizes the relationship between the nonsymmetric low-rank matrix factorization problem (29) and the following PSD low-rank matrix factorization problem [42]:

where M ∈ R n×n is a rank-r PSD matrix. Lemma 4: Suppose g(W ) is defined as in (29) with µ>0. Then we have

In particular, if we choose µ = 1 2 ,t h e nw eh a v e

The proof of Lemma 4 is given in Appendix E. Informally, Lemma 4 indicates that minimizing g(W ) also results in minimizing WW T -W ? W ?T 2 F (which is the same form as the objective function in (30)) and hence the distance between W and W ? (though W ? is unavailable at priori). The global geometry for the PSD low-rank matrix factorization problem ( 30) is recently analyzed by Li et al. in [42].

We first provide the gradient and Hessian expression for g(W ). The gradient of g(W ) is given by

which can be rewritten as

Standard computations give the Hessian quadratic form

×r (where

where

By Lemma 2, we can simplify the equations for critical points as follows

Now suppose W is a critical point of g(W ). We can apply the Gram-Schmidt process to orthonormalize the columns of U such that U = UR,w h e r eR ∈O r = R ∈ R r×r , R T R = I and U is orthogonal. 4

](∆R, ∆R), indicating that W and W have the same Hessian information. Thus, without loss of generality, we assume U and V are orthogonal (including the possibility that they have zero columns). With this, we use u i and v i to denote the i-th columns of U and V , respectively. It follows from ∇g(W )=0 that

,...,( λ r p r , λ r q r ), (0, 0) . Now we identify all the critical points of g(W ) in the following lemma, which is formally proved with an algebraic approach in Appendix F.

Lemma 5: Let X ? = ΦΣΨ T = r i=1 σ i φ i ψ T i be a reduced SVD of X ? and g(W ) be defined as in (29) with

Intuitively, (35) means that a critical point W of g(W ) is one such that UV T is a rank-`approximation to X ? with `≤ r and U and V are equal factors of this rank-à pproximation. Let λ 1 ,λ 2 ,...,λ r denote the diagonals of Λ.

Unlike Σ, we note that these diagonals λ 1 ,λ 2 ,...,λ r are not necessarily placed in decreasing or increasing order. Actually, this equation (Σ -Λ)Σ = 0 is equivalent to

for all i ∈{ 1, 2,...,r}. Further, we introduce the set of optimal solutions:

It is clear that the set X containing all the optimal solutions, the set C containing all the critical points and the set E containing all the points with balanced factors have the nesting relationship: X⊂C⊂E . Before moving to the next section, we provide one more result regarding W ∈E. The proof of the following result is given in Appendix G.

Lemma 6:

where E is defined in (10), we have

and

Lemma 6 implies that the Hessian of ρ(W ) evaluated at any critical point W is PSD, i.e., ∇ 2 ρ(W ) 0 for all W ∈ C. Despite this fact, the following result establishes the strict saddle property for g(W ).

Theorem 2: Let g(W ) be defined as in (29) with µ>0 and rank(X ? )=r.LetW = U V be any critical point satisfying ∇g(W )=0,i . e . ,W ∈C.A n yW ∈C\X is a strict saddle of g(W ) satisfying

Furthermore, g(W ) is not strongly convex at any global minimum point W ∈X.

The proof of Theorem 2 is given in Appendix H. We note that this strict saddle property is also covered in [40,Theorem 3], but with much looser bounds (in particular, directly applying [40,Theorem 3] gives λ min (∇ 2 g(W )) ≤ -0.1σ r (X ? ) rather than λ min (∇ 2 g(W )) ≤-σ r (X ? ) in ( 39)). Theorem 2 actually implies that g(W ) has no spurious local minima (since all local minima belong to X ) and obeys the strict saddle property. With the strict saddle property and lack of spurious local minima for g(W ), the recent results [18], [19] ensure that gradient descent converges to a global minimizer almost surely with random initialization. We also note that Theorem 2 states that g(W ) is not strongly convex at any global minimum point W ∈X because of the invariance property of g(W ). This is the reason we introduce the distance in (12) and also the robust strict saddle property in Definition 9.

In this section, we briefly discuss the over-parameterized scenario where the low-rank matrix X ? has rank smaller than r. Similar to Theorem 2, the following result shows that the strict saddle property also holds in this case.

Theorem 3: Let X ? = ΦΣΨ T = r 0 i=1 σ i φ i ψ T i be a reduced SVD of X ? with r 0 ≤ r,a n dl e tg(W ) be defined as in (29)

Further, all the local minima (which are also global) belong to the following set

Finally, any W ∈C\X is a strict saddle of g(W ) satisfying

The proof of Theorem 3 is given in Appendix I. We note that this strict saddle property is also covered in [40,Theorem 3], but with much looser bounds (in particular, directly applying [40,Theorem 3] gives λ min (∇ 2 g(W )) ≤-0.1σ r 0 (X ? ) rather than λ min (∇ 2 g(W )) ≤-σ r 0 (X ? ) in Theorem 3). E. Extension to Under-Parameterized Case: rank (X ? ) >r

We further discuss the under-parameterized case where rank(X ? ) >r. In this case, (3) is also known as the low-rank approximation problem as the product UV T forms a rank-r approximation to X ? . Similar to Theorem 2, the following result shows that the strict saddle property also holds for g(W ) in this scenario.

Theorem 4: Let X ? = ΦΣΨ T = r 0 i=1 σ i φ i ψ T i be a reduced SVD of X ? with r 0 >rand σ r (X ? ) >σ r+1 (X ? ). 5Also let g(W ) be defined as in (29)

where we recall that Φ[:, Ω] is a submatrix of Φ obtained by keeping the columns indexed by Ω and Σ[Ω, Ω] is an `× `matrix obtained by taking the elements of Σ in rows and columns indexed by Ω.

Further, all local minima belong to the following set

Finally, any W ∈C\X is a strict saddle of g(W ) satisfying

The proof of Theorem 4 is given in Appendix J. It follows from Eckart-Young-Mirsky theorem [51] that for any W ∈X, UV T is the best rank-r approximation to X ? . Thus, this strict saddle property ensures that the local search algorithms applied to the factored problem (29) converge to global optimum which corresponds to the best rank-r approximation to X ? . Note that Theorems 2-4 require µ>0. Based on these results, it has been recently proved in [52] that the strict saddle property also holds for g(W ) even when µ =0 , but without an explicit bound on λ min (∇ 2 g(W )) as in Theorems 2-4.

We now consider the revised robust strict saddle property defined in Definition 9 for the low-rank matrix factorization problem (29). As guaranteed by Theorem 2, g(W ) satisfies the strict saddle property for any µ>0. However, too small a µ would make analyzing the robust strict saddle property difficult. To see this, we denote

for convenience. Thus we can rewrite g(W ) as the sum of f (W ) and ρ(W ). Note that for any W = U V ∈C where C

is the set of critical points defined in (35), W = UM VM -1 is a critical point of f (W ) for any invertible M ∈ R r×r .T h i s further implies that the gradient at W reduces to ∇g( W )=∇ρ( W ), w h i c hc o u l db ev e r ys m a l li fµ is very small since ρ(W )=

. On the other hand, W could be far away from any point in X for some M that is not wellconditioned. Therefore, we choose a proper µ controlling the importance of the regularization term such that for any W that is not close to the critical points X , g(W ) has large gradient. Motivated by Lemma 4, we choose µ = 1 2 . The following result establishes the robust strict saddle property for g(W ).

Theorem 5: Let R 1 , R 2 , R 0 3 , R 00 3 , R 000 3 be the regions as defined in Theorem 1. Let g(W ) be defined as in (29) with µ = 1 2 .T h e ng(W ) has the following robust strict saddle property:

1) For any W ∈R 1 , g(W ) satisfies local regularity condition:

where dist(W , W ? ) and R are defined in ( 12) and ( 13), respectively. 2) For any W ∈R 2 , g(W ) has a directional negative curvature:

3) For any W ∈R 3 = R 0 3 ∪R 00 3 ∪R 000 3 , g(W ) has large gradient:

The proof is given in Appendix K. Remark 8: Recall that all the strict saddles of g(W ) are actually rank deficient (see Theorem 2). Thus the region R 2 attempts to characterize all the neighbors of the saddle saddles by including all rank deficient points. Actually, (41) holds not only for W ∈R 2 ,b u tf o ra l lW such that σ r (W )

). The reason we add another constraint controlling the term kW ? W ?T k F is to ensure this negative curvature property in the region R 2 also holds for the matrix sensing problem discussed in next section. This is the same reason we add two more constraints kW k≤ 20 19 kW ? k F and kWW T k F ≤ 10 9 kW ? W ?T k F for the region R 0 3 .

We first repeat that X ? = ΦΣΨ T = is a reduced SVD of X ? . We separate U into two parts-the projections onto the column space of Φ and its orthogonal complement-by denoting U = ΦΛ

1 Φ = 0 and Λ 1 being a r × r diagonal matrix with non-negative elements along its diagonal. Similarly, denote V = ΨΛ

is a r × r diagonal matrix with non-negative elements along its diagonal. Recall that any

Since E 1 is orthogonal to Φ, (47) further implies that

From (50), we have

is the inner product between two PSD matrices. Thus E 1 = 0. With a similar argument we also have E 2 = 0.

With E 1 = E 2 = 0, (49) reduces to

1 is not a diagonal matrix anymore. Then we have

implying that the set of the locations of non-zero diagonals in Λ 1 is identical to Ω. A similar argument applied to (48) gives

Noting that (51) implies

Finally, we note that

] Ω play a role in U and V , respectively. Thus one can set

APPENDIX G PROOF OF LEMMA 6 Utilizing the result that any point W ∈Esatisfies

(and similarly for the other two terms).

We then rewrite the last two terms in (32) as

, where the last line holds because A -A T , A + A T =0 .

Plugging these with the factor W T W = 0 into the Hessian quadratic form [∇ 2 ρ(W )](∆, ∆) defined in (32) gives

This implies that the Hessian of ρ evaluated at any W ∈E is PSD, i.e., ∇ 2 ρ(W ) 0.foot_6

We begin the proof of Theorem 2 by characterizing any

denote the location of the first zero diagonal element in Λ. Noting that λ i ∈{σ i , 0}, we conclude that

In words, φ k and ψ k are orthogonal to U and V , respectively. Let α ∈ R r be the eigenvector associated with the smallest eigenvalue of W T W .Suchα simultaneously lives in the null spaces of U and V since W is rank deficient indicating

which further implies

With this property, we construct ∆ by setting ∆ U = φ k α T and ∆ V = ψ k α T . Now we show that W is a strict saddle by arguing that g(W ) has a strictly negative curvature along the constructed direction ∆,i . e . ,[∇ 2 g(W )](∆, ∆) < 0.T ot h a t end, we compute the five terms in (31) as follows

where

. Plugging these terms into (31) gives

The proof of the strict saddle property is completed by noting that

which further implies

where the first equality holds because

and the second equality follows since

We finish the proof of (39) by noting that

Now suppose W ? ∈X. Applying (38), which states that the Hessian of ρ evaluated at any critical point W is PSD, we have

since U ? V ?T -X ? = 0.W eshowg is not strongly convex at W ? by arguing that λ min (∇ 2 g(W ? )) = 0. For this purpose, we first recall that U ? = ΦΣ 1/2 , V ? = ΨΣ 1/2 ,w h e r ew e assume R = I without loss of generality. Let {e 1 , e 2 ,...,e r } be the standard orthobasis for R r ,i.e.,e `is the `-th column of the r × r identity matrix. Construct

,w h e r e ∆ (i,j) U = U ? e j e T i -U ? e i e T j , ∆ (i,j) V = V ? e j e T i -U ? e i e T j , for any 1 ≤ i<j≤ r.T h a ti s ,t h e`-th columns of the matrices ∆ (i,j) U and ∆ (i,j) V are respectively given by

for any 1 ≤ i<j≤ r. We then compute the five terms in (31) as follows

where the last two lines hold because

∆ (i,j) = U ?T U ? (e j e T i -e i e T j )-V ?T V ? (e j e T i -e i e T j ) = 0 since U ?T U ? = V ?T V ? .

Authorized licensed use limited to: COLORADO SCHOOL OF MINES. Downloaded on June 28,2021 at 19:24:04 UTC from IEEE Xplore. Restrictions apply.

where the last equality in the first line holds because

the fourth and last lines holds because

Now plugging these terms into (31) yields

The proof of the strict saddle property is completed by noting that

where the last inequality holds because of (55) and because i ≤ r.

We first establish the following useful results. Lemma 7: For any two PSD matrices A, B ∈ R n×n , we have σ n (A)trace(B) ≤ trace (AB) ≤kAk trace(B).

2 be the eigendecompositions of A and B, respectively. Here Λ 1 (Λ 2 ) is a diagonal matrix with the eigenvalues of A (B) along its diagonal. We first rewrite trace (AB) as

Noting that Λ 1 is a diagonal matrix, we have

The other direction follows similarly.

Corollary 2: For any two matrices A ∈ R n×r and B ∈ R r×r ,w eh a v e σ r (B)kAk F ≤kABk F ≤kBkkAk F .

We provide one more result before proceeding to prove the main theorem.

Lemma 8:

).

(57)

We first rewrite the terms (ℵ 1 ), (ℵ 2 ) and (ℵ 3 ) as follows

where

It follows from Lemma 3 that W T W ? R = R T W ?T W is PSD, where R = arg min R 0 ∈Or kW -W ? R 0 k 2 F .W efi r s t perform the change of variable W ? R → W ? to avoid R in the following equations. With this change of variable we have instead W T W ? = W ?T W is PSD. We now rewrite the gradient ∇g(W ) as follows:

Plugging this into the left hand side of (40) gives

, WW T (59) where the last line follows from the fact that W ?T W ? = 0. We first show the first term in the right hand side of the above equation is sufficiently large

where the first inequality follows from Lemma 8 since W T W ? = W ?T W is PSD and kW -W ? k≤ σ On the other hand, we attempt to control the gradient of g(W ). To that end, it follows from (58) that

where the first inequality holds since (a + b) 2 ≤ 1+ a 2 + (1 + )b 2 for any >0.

Combining (59)-(62), we can conclude the proof of ( 40) as long as we can show the following inequality:

To that end, we upper bound kW k as follows:

(1/2) 1 (X ? ) and dist(W , W ? ) ≤ σ (1/2) r (X ? ). This completes the proof of (40).

To show (41), we utilize a strategy similar to that used in Appendix H for proving the strict saddle property of g(W ) by constructing a direction ∆ such that the Hessian evaluated at W along this direction is negative. For this purpose, denote

where we recall that Φ and Ψ consist of the left and right singular vectors of X ? , respectively. The optimal solution W ? has a compact SVD W ? = Q( √ 2Σ 1/2 )R. For notational convenience, we denote Σ =2 Σ,w h e r eΣ is a diagonal matrix whose diagonal entries in the upper left corner are σ 1 ,...,σ r .

For any W , we can always divide it into two parts, the projections onto the column spaces of Q and its orthogonal complement, respectively. Equivalently, we can write

where QΛ 1/2 R is a compact SVD form representing the projection of W onto the column space of Q,a n dE T Q = 0 (i.e., E is orthogonal to Q). Here R ∈O r and Λ is a diagonal matrix whose diagonal entries in the upper left corner are λ 1 ,...,λ r , but the diagonal entries are not necessarily placed either in decreasing or increasing order. In order to characterize the neighborhood near all strict saddles C\X, we consider W such that σ r (W )

r (X ? ).L e t k := arg min i λ i denote the location of the smallest diagonal entry in Λ. It is clear that

Let α ∈ R r be the eigenvector associated with the smallest eigenvalue of W T W .

Recall that µ = 1 2 . We show that the function g(W ) at W has directional negative curvature along the direction

(66) We repeat the Hessian evaluated at W for ∆ as follows

The remaining part is to bound the five terms.

Bounding terms Π 1 , Π 3 and Π 4 : We first rewrite these three terms:

Noting that

Plugging this into (67) gives

Bounding terms Π 2 and Π 5 : To obtain an upper bound for the term Π 2 , we first rewrite it as follows

We then have

To bound these two terms in the above equation, we note that

Then we have

where the last utilizes the fact that E T q k = 0 since E is orthogonal to Q. Plugging these into (69) gives

Merging together: Putting (68) and (70) together yields

where the third line follows because by assumption σ r (W )

r (X ? ), by construction λ k ≤ 1 2 σ r (X ? ) (see (65)), and σ k ≥ σ r =2σ r (X ? ). This completes the proof of (41).

In order to show that g(W ) has a large gradient in the three regions R 0 3 ∪R 00 3 ∪R 000 3 , we first provide a lower bound for the gradient. By (58), we have

where the third equality follows because W ?T W ? = U ?T U ? -V ?T V ? = 0 and the last line utilizes the fact that the inner product between two PSD matrices is nonnegative.

1) Large Gradient for the Region R 0 3 : To show k∇g(W )k 2 F is large for any W ∈R 0 3 , again, for any W ∈ R (n+m)×r , we utilize (64) to write W = QΛ 1/2 R + E,w h e r eQ is defined in (63), QΛ 1/2 R is a compact SVD form representing the projection of W onto the column space of Q,andE T Q = 0 (i.e., E is orthogonal to Q). Plugging this form of W into the last term of (71) gives

Authorized licensed use limited to: COLORADO SCHOOL OF MINES. Downloaded on June 28,2021 at 19:24:04 UTC from IEEE Xplore. Restrictions apply.

since Q is orthogonal to E. The remaining part is to show at least one of the two terms is large for any W ∈R 0 3 by considering the following two cases.

Case I: kEk 2 F ≥ 4 25 σ r (X ? ).A sE is large, we bound the second term in (72):

where the first inequality follows from Corollary 2, the first equality follows from the fact W T W = R T ΛR+ E T E,and the last inequality holds because by assumption that σ 2 r (W ) ≥

where we utilize kEk 2 ≤kEk F ≤ 2 5 σ 1/2 r (X ? ). On the other hand,

which together with the assumption that dist(W , W

). We now bound the first term in (72):

where the third line holds because kEE T k F ≤k Ek 2 F ≤ This completes the proof of (42).

2) Large Gradient for the Region R Proof: Let A = Φ 1 Λ 1 R T 1 and B = Φ 2 Λ 2 R T 2 be the SVDs of A and B, respectively. Then

3) Large Gradient for the Region R 000 3 : By (58), we have h∇g(W ), W i Throughout the proofs, we always utilize X = UV T unless stated otherwise. To give a sense that the geometric result in

Similar to what used in Appendix K-A, we perform the change of variable W ? R → W ? to avoid R in the following equations. With this change of variable we have instead W T W ? = W ?T W is PSD.

We first control |h∇G(W ) -∇g(W ), W -W ? i| as follows:

|h∇G(W ) -∇g(W ), W -W ? i| ≤ h∇f (X), (U -U ? )V T i-hX -X ? , (U -U ? )V T i + h∇f (X), U (V -V ? ) T i-hX -X ? , U (V -V ? ) T i ≤ c kX - This completes the proof of (15).

Let ∆ = q k α T be defined as in (66). First note that

where the last equality holds because σ r (W )

r (X ? ). Also utilizing the particular structure in ∆ yields

Due to the assumption 20 19 kW ? W ?T k F ≥k WW T k F , we have where the last line holds when c ≤ σr (X ? ) 50kX ? kF . This completes the proof of (16).

C. Large Gradient for the Region R 0 3 ∪R 00 3 ∪R 000

To show that G(W ) has large gradient in these three regions, we mainly utilize Lemma 11 to guarantee that ∇G(W ) is close to ∇g(W ).

1) Large Gradient for the Region R This completes the proof of (18).

3) Large Gradient for the Region R 000 . This completes the proof of (19).