{'fraction_non_alphanumeric': 0.049762454697387944, 'fraction_numerical': 0.01915385048729649, 'mean_word_length': 3.92181146025878, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Local and Global Linear Convergence of General Low-rank Matrix Recovery Problems

We study the convergence rate of gradient-based local search methods for solving low-rank matrix recovery problems with general objectives in both symmetric and asymmetric cases, under the assumption of the restricted isometry property. First, we develop a new technique to verify the Polyak-Lojasiewicz inequality in a neighborhood of the global minimizers, which leads to a local linear convergence region for the gradient descent method. Second, based on the local convergence result and a sharp strict saddle property proven in this paper, we present two new conditions that guarantee the global linear convergence of the perturbed gradient descent method. The developed local and global convergence results provide much stronger theoretical guarantees than the existing results. As a by-product, this work significantly improves the existing bounds on the RIP constant required to guarantee the non-existence of spurious solutions.


Introduction
The low-rank matrix recovery problem is to recover an unknown low-rank ground truth matrix from certain measurements. This problem has a variety of applications in machine learning, such as recommendation systems (Koren, Bell, and Volinsky 2009) and motion detection (Zhou, Yang, and Yu 2013;Fattahi and Sojoudi 2020), and in engineering problems, such as power system state estimation (Zhang, Madani, and Lavaei 2018).
In this paper, we consider two variants of the low-rank matrix recovery problem with a general measurement model represented by an arbitrary smooth function. The first variant is the symmetric problem, in which the ground truth M * ∈ R n×n is a symmetric and positive semidefinite matrix with rank(M * ) = r, and M * is a global minimizer of some loss function f s . Then, M * can be recovered by solving the optimization problem: (1) Note that minimizing f s (M ) over positive semidefinite matrices without the rank constraint would often lead to finding a solution with the highest-rank possible rather than the Copyright © 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
rank-constrained solution M * . The second variant of the low-rank matrix recovery problem to be studied is the asymmetric problem, in which M * ∈ R n×m is a possibly nonsquare matrix with rank(M * ) = r, and it is a global minimizer of some loss function f a . Similarly, M * can be recovered by solving min f a (M ) s. t. rank(M ) ≤ r, M ∈ R n×m . (2) As a special case, the loss function f s or f a can be induced by linear measurements. In this situation, we are given a linear operator A : R n×n → R p or A : R n×m → R p , where p denotes the number of measurements. To recover M * from the vector d = A(M * ), the function f s (M ) or f a (M ) is often chosen to be Besides, there are many natural choices for the loss function, such as a nonlinear model associated with the 1-bit matrix recovery (Davenport et al. 2014). The symmetric problem (1) can be transformed into an unconstrained optimization problem by factoring M as XX T with X ∈ R n×r , which leads to the following equivalent formulation: min X∈R n×r f s (XX T ). (4) In the asymmetric case, one can similarly factor M as U V T with U ∈ R n×r and V ∈ R m×r . Note that (U P, V (P −1 ) T ) gives another possible factorization of M for any invertible matrix P ∈ R r×r . To reduce the redundancy, a regularization term is usually added to the objective function to enforce that the factorization is balanced, i.e., U T U = V T V is satisfied (Tu et al. 2016). Since every factorization can be converted into a balanced one by selecting an appropriate P , the original asymmetric problem (2) is equivalent to where φ > 0 is an arbitrary constant.
To handle the symmetric and asymmetric problems in a unified way, we will use the same notation X to denote the arXiv:2104.13348v4 [math.OC] 8 Mar 2022 matrix of decision variables in both cases. In the symmetric case, X is obtained from the equation M = XX T . In the asymmetric case, X is defined as To rewrite the asymmetric problem (5) in terms of X, we apply the technique in Tu et al. (2016) by defining an auxiliary function F : R (n+m)×(n+m) → R as in which the argument of the function F is partitioned into four blocks, denoted as N 11 ∈ R n×n , N 12 ∈ R n×m , N 21 ∈ R m×n , N 22 ∈ R m×m . The problem (5) then reduces to which is a special case of the symmetric problem (4). Henceforth, the objective functions of the two problems will be referred as to g s (X) = f s (XX T ) and g a (X) = F (XX T ), respectively. The unconstrained problems (4) and (5) are often solved by local search algorithms, such as the gradient descent method, due to their efficiency in handling large-scale problems. Since the objective functions g s (X) and g a (X) are nonconvex, local search methods may converge to a spurious (non-global) local minimum. To guarantee the absence of such spurious solutions, the restricted isometry property (RIP) defined below is the most common condition imposed on the functions f s and f a (Bhojanapalli, Neyshabur, and Srebro 2016;Ge, Jin, and Zheng 2017;Zhu et al. 2018;Zhang et al. 2018b,a;Zhang, Sojoudi, and Lavaei 2019;Ha, Liu, and Barber 2020;Zhang and Zhang 2020;Bi and Lavaei 2020;Zhang, Bi, and Lavaei 2021;Zhang 2021). Definition 1 (Recht, Fazel, and Parrilo (2010); Zhu et al. (2018)). A twice continuously differentiable function f s : R n×n → R satisfies the restricted isometry property of rank (2r 1 , 2r 2 ) for a constant δ ∈ [0, 1), denoted as δ-RIP 2r1,2r2 , if holds for all matrices M, K ∈ R n×n with rank(M ) ≤ 2r 1 and rank(K) ≤ 2r 2 . In the case when r 1 = r 2 = r, the notation RIP 2r,2r will be simplified as RIP 2r . A similar definition can be also made for the asymmetric loss function f a . The state-of-the-art results on the non-existence of spurious local minima are presented in Zhang, Bi, and Lavaei (2021); Zhang (2021). Zhang, Bi, and Lavaei (2021) shows that the problem (4) or (5) is devoid of spurious local minima if i) the associated function f s or f a satisfies the δ-RIP 2 property with δ < 1/2 in case r = 1, ii) the function f s or f a satisfies the δ-RIP 2r property with δ ≤ 1/3 in case r > 1. Zhang (2021) further shows that a special case of the symmetric problem (4) does not have spurious local minima if iii) f s is in the form (3) given by linear measurements and satisfies the δ-RIP 2r property with δ < 1/2. The absence of spurious local minima under the above conditions does not automatically imply the existence of numerical algorithms with a fast convergence to the ground truth. In this paper, we will significantly strengthen the above two results by establishing the global linear convergence for problems with an arbitrary rank r and a general loss function f s or f a under the almost same RIP assumption as above, i.e., δ < 1/2 for the symmetric problem and δ < 1/3 for the asymmetric problem.
One common approach to establish fast convergence is to first show that the objective function has favorable regularity properties, such as strong convexity, in a neighborhood of the global minimizers, which guarantees that common iterative algorithms will converge to a global minimizer at least linearly if they are initialized in this neighborhood. Second, given the local convergence result, certain algorithms can be utilized to reach the above neighborhood from an arbitrary initial point. Note that randomization and stochasticity are often needed in those algorithms to avoid saddle points that are far from the ground truth, such as random initialization (Lee et al. 2016) or random perturbation during the iterations (Ge et al. 2015;Jin et al. 2017). In this paper, we deal with the two above-mentioned aspects for the low-rank matrix recovery problem separately.

Notations and Conventions
In this paper, I n denotes the identity matrix of size n × n, A ⊗ B denotes the Kronecker product of matrices A and B, and A 0 means that A is a symmetric and positive semidefinite matrix. σ i (A) denotes the i-th largest singular value of the matrix A. A = vec(A) is the vector obtained from stacking the columns of a matrix A. For a vector A of dimension n 2 , its symmetric matricization mat S (A) is defined as (A + A T )/2 with A being the unique matrix satisfying A = vec(A). For two matrices A and B of the same size, their inner product is denoted as A, B = tr(A T B) and A F = A, A denotes the Frobenius norm of A. Given a matrix M and a set Z of matrices, define Moreover, v denotes the Euclidean norm of a vector v. The action of the Hessian ∇ 2 f (M ) of a matrix function f on any two matrices K and L is given by

Summary of Main Contributions
For the local convergence, we prove in Section 3 that a regularity property named the Polyak-Łojasiewicz (PL) inequality always holds in a neighborhood of the global minimizers. The PL inequality is significantly weaker than the regularity condition used in previous works to study the local convergence of the low-rank matrix recovery problem, while it still guarantees a linear convergence to the ground truth. Hence, as will be compared with the prior literature in Section 2, not only are the obtained local regularity regions remarkably larger than the existing ones, but also they require significantly weaker RIP assumptions. Specifically, if f s satisfies the δ-RIP 2r property for an arbitrary δ, we will show that there exists some constant µ > 0 such that the objective function g s of the symmetric problem (4) satisfies the PL inequality for all X in the region Here, dist(X, Z) is the Frobenius distance between the matrix X and the set Z of global minimizers of the problem (4). A similar result will also be derived for the asymmetric problem (5). Based on these results, local linear convergence can then be established. Compared with the previous results, our new results are advantageous for two reasons. First, the weaker RIP assumptions imposed by our results allow them to be applicable to a much broader class of problems, especially those problems with nonlinear measurements where the RIP constant of the loss function f s or f a varies at different points. In this case, the region in which the RIP constant is below the previous bounds may be significantly small or even empty, while the region satisfying our bounds is much larger since the radius of the region is increased by more than a constant factor. Second, when the RIP constant is large and global convergence cannot be established due to the existence of spurious solutions, the enlarged local regularity regions identified in this work can reduce the sample complexity to find the correct initial point converging to the ground truth. This has a major practical value in problems like data analytics in power systems (Jin et al. 2021) in which there is a fundamental limit to the number of measurements due to the physics of the network. For the global convergence analysis, in Section 4, we first study the symmetric problem (4) with an arbitrary objective and an arbitrary rank r and prove that the objective g s satisfies the strict saddle property if the function f s has the δ-RIP 2r property with δ < 1/2. Note that this result is sharp, because in Zhang et al. (2018a) a counterexample has been found that contains spurious local minima under δ = 1/2. Using the above strict saddle property and the local convergence result proven in Section 3, we show that the perturbed gradient descent method with local improvement will find an approximate solution X satisfying XX T − M * F ≤ in O(log 1/ ) number of iterations for an arbitrary tolerance . Moreover, the convergence result for symmetric problems also implies the global linear convergence for asymmetric problems under the δ-RIP 2r condition with δ < 1/3.

Assumptions
The assumptions required in this work will be introduced below. To avoid using different notations for the symmetric and asymmetric problems, we use the universal notation f (M ) henceforth to denote either f s (M ) or f a (M ). Similarly, M * denotes the ground truth in either of the cases.
Assumption 1. The function f is twice continuously differentiable. In addition, its gradient ∇f is ρ 1 -restricted Lipschitz continuous for some constant ρ 1 , i.e., the inequality holds for all matrices M and M with rank(M ) ≤ r and rank(M ) ≤ r. The Hessian of the function f is also ρ 2restricted Lipschitz continuous for some constant ρ 2 , i.e., the inequality holds for all matrices M, M , K with rank(M ) ≤ r, rank(M ) ≤ r and rank(K) ≤ 2r.
Assumption 2. The function f satisfies the δ-RIP 2r property. Furthermore, ρ 1 in Assumption 1 is chosen to be large enough such that ρ 1 ≥ 1 + 2δ.
Assumption 3. The ground truth M * satisfies M * F ≤ D, and the initial point X 0 of the local search algorithm also satisfies X 0 X T 0 F ≤ D, where D is a constant given by the prior knowledge (every large enough D satisfies this assumption).
Note that the results of this paper still hold if the gradient and Hessian of the function f are restricted Lipschitz continuous only over a bounded region. Here, for simplicity we assume that these properties hold for all low-rank matrices.
As mentioned before Definition 1, the RIP-related Assumption 2 is a widely used assumption in studying the landscape of low-rank matrix recovery problems, which is satisfied in a variety of problems, such as those for which f is given by a sufficiently large number of random Gaussian linear measurements (Candès and Plan 2011). Moreover, in the case when the function f does not satisfy the RIP assumption globally, it often satisfies RIP in a neighborhood of the global minimizers, and the theorems in this paper can still be applied to obtain local convergence results.
For the asymmetric problem, it can be verified that, by choosing the coefficient φ of the regularization term as in Assumption 4, the function F in (7) satisfies the 2δ/(1 + δ)-RIP 2r property after scaling (see Zhang, Bi, and Lavaei (2021)). Other values of φ can also lead to the RIP property on F , but the specific value in Assumption 4 is the one minimizing the RIP constant. Furthermore, if M * = U * V * T is a balanced factorization of the ground truth M * , theñ is called the augmented ground truth, which is obviously a global minimizer of the transformed asymmetric problem (7).M * is independent of the factorization (U * , V * ), and We include the proofs of the above statements in Appendix A for completeness. In addition, we prove in Appendix A that the gradient and Hessian of the function g s in the symmetric problem (4) and those of the function g a in the asymmetric problem (5) share the same Lipschitz property over a bounded region. Using the above observations, one can translate any results developed for symmetric problems to similar results for asymmetric problems by simply replacing δ with 2δ/(1 + δ), D with 2D, and σ r (M * ) with 2σ r (M * ).

Related Works
The low-rank matrix recovery problem has been investigated in numerous papers. In this section, we focus on the existing results related to the linear convergence for the factored problems (4) and (5) solved by local search methods. The major previous results on the local regularity property are summarized in Table 1. In this table, each number in the last column reported for the existing works denotes the radius R such that their respective objective functions g satisfy the (α, β)-regularity condition Here, Z is the set of global minimizers, and P Z (X) is a global minimizer Z ∈ Z that is the closest to X. The (α, β)-regularity condition is slightly weaker than the strong convexity condition, and it can lead to linear convergence on the same region. In Table 1, we do not include specialized results that are only applicable to a specific objective Hou, Li, and Zhang 2020), or probabilistic results for randomly generated measurements (Zheng and Lafferty 2015). Moreover, Li and Lin (2020); Zhou, Cao, and Gu (2020) used the accelerated gradient descent to obtain a faster convergence rate, but their convergence regions are even smaller than the ones based on the (α, β)-regularity condition as listed in Table 1. Each number in the last column reported for our results refers to the radius of the region satisfying the PL inequality, which is a weaker condition than the (α, β)-regularity condition while offering the same convergence rate guarantee. It can be observed that we have identified far larger regions than the existing ones under weaker RIP assumptions by replacing the (α, β)-regularity condition with the PL inequality.
Regarding the existing global convergence results for the low-rank matrix recovery problem, Jin et al. (2017) established the global linear convergence for the symmetric problem in a very specialized case with f s being a quadratic loss function, and Tu et al. (2016) proposed the Procrustes flow method with the global linear convergence for the linear measurement case under the assumption that the function f s satisfies the 1/10-RIP 6r property for symmetric problems or the function f a satisfies the 1/25-RIP 6r property for asymmetric problems under a careful initialization. Zhao, Wang, and Liu (2015) established the global linear convergence for asymmetric problems with linear measurements under the assumption that f a satisfies δ-RIP 2r with δ ≤ O(1/r) using alternating exact minimization over variables U and V in (5). In addition, the strict saddle property proven in Ge, Jin, and Zheng (2017) leads to the global linear convergence of perturbed gradient methods for the linear measurement case under the 1/10-RIP 2r assumption for symmetric problems and the 1/20-RIP 2r assumption for asymmetric problems. Later, Zhu et al. (2018) proved a weaker strict saddle property under the 1/5-RIP 2r,4r assumption for symmetric problems with general objectives, while Li, Zhu, and Tang (2017) proved the same weaker property under the 1/5-RIP 2r,4r assumption for asymmetric problems with general objectives and nuclear norm regularization. Our results requiring the δ-RIP 2r property with δ < 1/2 for symmetric problems with general objectives and the δ-RIP 2r property with δ < 1/3 for asymmetric problems with general objectives depend on significantly weaker RIP assumptions and thus can be applied to a broader class of problems, which is a major improvement over all previous results on the global linear convergence.
Besides local search methods for the factored problems, there are other approaches for tackling the low-rank matrix recovery. Earlier works such as Candès and Recht (2009);Recht, Fazel, and Parrilo (2010) solved the original nonconvex problems based on convex relaxations. Although they can achieve good performance guarantees under the RIP assumptions, they are not suitable for large-scale problems. Other approaches for solving the low-rank matrix recovery include applying the inertial proximal gradient descent method directly to the original objective functions without factoring the decision variable M (Dutta et al. 2020). However, it may converge to an arbitrary critical point, while in this paper we show that RIP-based local search methods can guarantee the global convergence to a global minimum.

Local Convergence
In this section, we present the local regularity results for problems (4) and (5), which state that the functions g s and g a satisfy the PL inequality locally, leading to local linear convergence results for the gradient descent method. The proofs are delegated to Appendix B.
First, we consider the symmetric problem (4). The development of the local PL inequality for this problem is enlightened by the high-level idea behind the proof of the absence of spurious local minima in Zhang, Sojoudi, and Lavaei (2019); Zhang and Zhang (2020); Bi and Lavaei (2020). The objective is to find a function f * s corresponding to the worstcase scenario, meaning that it satisfies the δ-RIP 2r property with the smallest possible δ while the PL inequality is violated at a particular matrix X. This is achieved by designing a semidefinite program parameterized by X with constraints implied by the δ-RIP 2r property and the negation of the PL inequality. Denote the optimal value of the semidefinite program by δ * f (X). If a given function f s satisfies δ-RIP 2r with δ < δ * f (X) for all X ∈ R n×r in a neighborhood of the global minimizers, it can be concluded that the PL inequality holds for all matrices in this neighborhood.
Lemma 1. Consider the symmetric problem (4) and an ar-

Objective
Assumption Radius of Local Regularity Region Bhojanapalli, Kyrillidis, and Sanghavi (2016) S/G f s Convex, δ 2r ≤ δ 1 100 Table 1: Previous local regularity results for the low-rank matrix recovery problems and the comparison with our results ("S", "A", "L" and "G" stand for the symmetric case, asymmetric case, linear measurement and general nonlinear function).
bitrary positive numberC satisfying There exists a constant µ > 0 such that the PL inequality holds for all matrices in the region where Z is the set of global minimizers of the problem (4).
In the above, note that σ r (M * ) and thusC are always positive because M * is assumed to be rank r. Both the (α, β)-regularity condition used in the prior literature and the PL inequality deployed here guarantee a linear convergence if it is already known that the trajectory at all iterations remains within the region in which the associated condition holds. However, there is a key difference between these two conditions. The (α, β)-regularity condition ensures that dist(X, Z) is nonincreasing during the iterations under a sufficiently small step size, and thus the trajectory never leaves the local neighborhood. In contrast, the weaker PL inequality may not be able to guarantee this property. To resolve this issue, in our convergence proof we will adopt a different distance function given by XX T − M * F . By Taylor's formula and the definition of the δ-RIP 2r property, we have for all matrices M ∈ R n×n with rank(M ) ≤ r. Therefore, if M, M ∈ R n×n are two matrices such that f s (M ) ≤ f s (M ), then the inequality (11) implies that Therefore, the distance function XX T − M * F is almost nonincreasing if the function value g s (X) does not increase. Combining this idea with the local PL inequality proved in Lemma 1, we obtain the next local convergence result. Theorem 2. For the symmetric problem (4), the gradient descent method converges to the optimal solution linearly if the initial point X 0 satisfies and the step size η satisfies Specifically, there exists some constant µ > 0 (which depends on X 0 but not on η) such that where X t denotes the output of the algorithm at iteration t. Note that since the left-hand side of (13) is nonnegative, we have 0 ≤ 1 − µη ≤ 1. As a remark, although our bound on the step size η in Theorem 2 seems complex, it essentially says that η needs to be small, and the upper bound on the acceptable values of the step size can be explicitly calculated out routinely after all the parameters of the problem are given. Furthermore, using the transformation from asymmetric problems to symmetric problems, one can obtain parallel results for the asymmetric problem (5) as below.
Theorem 3. Consider the asymmetric problem (5). The PL inequality is satisfied in the region where Z denotes the set of global minimizers and Moreover, local linear convergence is guaranteed for the gradient descent method if the initial point X 0 satisfies and the step size η satisfies

Global Convergence
Having developed local convergence results, the next step is to design an algorithm whose trajectory will eventually enter the local convergence region from any initial point. The major challenge is to deal with the saddle points outside the local regularity region. One common approach is the perturbed gradient descent method, which adds random noise to jump out of a neighborhood of a strict saddle point. Using the symmetric problem as an example, the basic idea is to first use the analysis in Jin et al. (2017) to show that the perturbed gradient descent method will successfully find a matrix X that approximately satisfies the first-order and second-order necessary optimality conditions, i.e., after a certain number of iterations where the number depends on κ. Here, λ min (∇ 2 g s (X)) denotes the minimum eigenvalue of the matrix G that satisfies the equation for all U, V ∈ R n×r . The second step is to prove the strict saddle property for the problem, which means that for appropriate values of κ the two conditions in (14) imply that XX T − M * F is so small that X is in the local convergence region given by Theorem 2. After this iteration, the algorithm switches to the simple gradient descent method. This two-phase algorithm is commonly called the perturbed gradient descent method with local improvement , whose details are given by Algorithm 1 in Appendix C. The proofs in this section are also given in Appendix C.
In this section, we will present two conditions that guarantee the global linear convergence of the above algorithm. For symmetric problems, the next lemma provides the strict saddle property and fulfills the purpose for the second step mentioned above. Its proof is a generalization of the one for the absence of spurious local minima under the same assumption in Zhang (2021).
Lemma 4. Consider the symmetric problem (4) with δ < 1/2. For every C > 0, there exists some κ > 0 such that for every X ∈ R n×r the two conditions given in (14) will imply XX T − ZZ T F < C. The remaining step is to show that the trajectory of the perturbed gradient descent method will always belong to a bounded region in which the gradient and Hessian of the objective g s are Lipschitz continuous (see Appendix C). Combining the above results with Theorem 3 in Jin et al. (2017), we can obtain the following global linear convergence result. Theorem 5. Consider the symmetric problem (4) with δ < 1/2. For every > 0, the perturbed gradient descent method with local improvement under a suitable step size η and perturbation size w finds a solutionX satisfying Here, η and w are defined in Algorithm 1 in Appendix C.
In the above theorem, the order O(log(1/ )) of the convergence rate is determined by the number of iterations spent in the second phase of the algorithm, because the number of iterations in the first phase is independent of . Note that we only show the relationship between the number of iterations and , but the convergence rate also depends on the initial point X 0 and the loss function f s . Moreover, although not being related to the final convergence rate, Theorem 3 in Jin et al. (2017) also shows that the number of iterations in the first phase is polynomial with respect to the problem size.
For asymmetric problems with arbitrary objectives and rank r, if we apply the transformation from asymmetric problems to symmetric problems and replace δ in Theorem 5 with 2δ/(1+δ), Theorem 5 immediately implies the following global linear convergence result. Theorem 6. Consider the asymmetric problem (5) with δ < 1/3. For every > 0, the perturbed gradient descent method with local improvement under a suitable step size η and perturbation size w finds a solutionX satisfying XX T −M * F ≤ with high probability in O(log(1/ )) number of iterations.

Numerical Illustration
In this section, we conduct numerical experiments to demonstrate the behavior of the perturbed gradient descent algorithm for solving low-rank matrix recovery problems. The linear convergence rate observed for the examples below supports our theoretical analyses in Section 3 and Section 4.
In the first experiment, we consider the loss function (3) induced by a linear operator A with Here, each entry of A i is independently generated from the standard Gaussian distribution. As shown in Candès and Plan (2011), such linear operator A satisfies RIP with high probability if the number of measurements is large enough.
Since it is NP-hard to check whether the resulting loss function f s or f a satisfies the δ-RIP 2r for certain δ, the δ parameter is estimated as follows: For the symmetric problem (4), we first generate 10 4 random matrices X ∈ R n×2r with each entry independently selected from the standard Gaussian distribution, and then find the proper scaling factor a ∈ R and the smallest δ such that holds for all generated matrices X. The δ parameter for the asymmetric problem (5) can be estimated similarly. After that, the ground truth M * = XX T or M * = U V T is generated randomly with each entry of X or (U, V ) independently selected from the standard Gaussian distribution. The initial point is generated in the same way. Figure 1(a) and (b) show the difference between the obtained solution and the ground truth together with the norm of the gradient of the objective function at different iterations. The convergence behavior clearly divides into two stages. The convergence rate is sublinear initially and then switches to linear when the current point moves into the local region associated with the PL inequality. In Figure 1(a) and (b), the marker shows the first time when the current point falls into the local convergence region provide in Theorem 2 or Theorem 3. It can be seen that these theorems predict the boundary of the transition from a sublinear convergence rate to the linear convergence rate fairly tightly. After this point, O(log(1/ )) additional iterations are needed to find an approximate solution with accuracy . On the other hand, the occasion when perturbation needs to be added is rare in practice since it is unlikely for the trajectory to be very close to a saddle point. However, such perturbation is necessary theoretically to deal with pathological cases.
Second, we consider the 1-bit matrix recovery (Davenport et al. 2014) with full measurements, which is a nonlinear low-rank matrix recovery problem. In this problem, there is an unknown symmetric ground truth matrixM ∈ R n×n withM 0 and rank(M ) = r. One is allowed to take independent measurements on every entryM ij , where each measurement value is a binary random variable whose distribution is given by Y ij = 1 with probability σ(M ij ) and Y ij = 0 otherwise. Here, σ(x) is commonly chosen to be the sigmoid function e x /(e x + 1). After a number of measurements are taken, let y ij be the percentage of the measurements on the (i, j)-th entry that are equal to 1. The goal is to find the maximum likelihood estimator for the ground trutĥ M , which can be formulated as finding the global minimizer M * of the problem (4)  To establish the RIP condition for the function f s above, consider its Hessian ∇ 2 f s (M ) that is given by for every M, K, L ∈ R n×n . On the region we have 1/12 < σ (M ij ) ≤ 1/4, and thus the function f s satisfies the δ-RIP 2r property with δ < 1/2. Note that due to the noisy measurements the global minimizer M * is not equal toM in general. However, for demonstration purposes we should know M * a priori, and hence we consider the case when the number of measurements is large enough such that y ij = σ(M ij ) and M * =M . In Figure 1(c), the ground truth and the initial point are generated randomly in the region (15). Here, we can observe a similar two-stage convergence behavior as in the example with linear measurements. We experiment on the same problem with a larger matrix size n as shown in Figure 1(d), which also gives similar results.

Conclusion
In this paper, we study the local and global convergence behaviors of gradient-based local search methods for solving low-rank matrix recovery problems in both symmetric and asymmetric cases. First, we present a novel method to identify a local region in which the PL inequality is satisfied, which is significantly larger than the region associated with the regularity conditions proven in the prior literature. This leads to a linear convergence result for the gradient descent method over a large local region. Second, we develop the strict saddle property for symmetric problems under the δ-RIP 2r property with δ < 1/2. Then, we prove the global linear convergence of the perturbed gradient descent method for symmetric problems under the δ-RIP 2r property with δ < 1/2, and the same convergence property can also be guaranteed for asymmetric problems with δ < 1/3. Compared with the existing results, these conditions are remarkably weaker and can be applied to a larger class of problems.

A Properties of the Factored Objectives
We first study the smoothness properties for the gradient and Hessian of the objective function g s in the symmetric problem (4). The following lemma is borrowed from the proof of Theorem 7 in Bi and Lavaei (2020). Lemma 7. If Q is a quadratic form satisfying δ-RIP 2r , then |[Q](K, L) − K, L | ≤ 2δ K F L F , for all matrices K, L ∈ R n×n of rank at most 2r. Lemma 8. For a given constant R greater than D, the gradient ∇g s of the function g s in the symmetric problem (4) is 8ρ 1 r 1/2 R-restricted Lipschitz continuous and the Hessian ∇ 2 g s is 4ρ 1 r 1/4 R 1/2 (2r 1/2 Rρ 2 /ρ 1 + 3)-restricted Lipschitz continuous over the region Furthermore, for every U, V ∈ D, it holds that There are four terms in the above expression. The first term can be upper bounded as

Similarly, the sum of the second and third terms can be bounded as
where Lemma 7 is applied in the second step. Moreover, we can upper bound the last term as F , which implies that the Hessian ∇ 2 g s has the desired Lipschitz property.
Next, we verify some facts about the augmented ground truthM * for the asymmetric problem, which will be useful in the transformation from asymmetric problems to symmetric problems.
Lemma 9. The augmented ground truthM * defined in (8) is independent of the balanced factorization of the ground truth M * . Furthermore, M * F = 2 M * F , σ r (M * ) = 2σ r (M * ). Proof. By expanding all the terms, it can be checked that the inequality ). Then, if (U 1 , V 1 ) and (U 2 , V 2 ) are two balanced factorizations of the ground truth M * , we must have and thusM * is unique. Assume that (U * , V * ) is a balanced factorization of M * , the remaining equalities follow from the fact that for all i ∈ {1, . . . , r}.
In the following, we will show that the gradient and the Hessian of the objective function g a in the transformed asymmetric problem (7) satisfies the same Lipschitz property as in Lemma 8. This means that those proofs in the remainder of this paper that depend on the Lipschitz property of g s can be applied to both the symmetric problem (4) and the transformed asymmetric problem (7). Lemma 10. The gradient ∇g a and the Hessian ∇ 2 g a in the transformed asymmetric problem (7) satisfy the same Lipschitz property as in Lemma 8.
Proof. Consider arbitrary low-rank matrices N, N , K ∈ R (n+m)×(n+m) written in block forms in the same way as in (6), with rank(N ) ≤ r, rank(N ) ≤ r and rank(K) ≤ 2r. First, we will prove that the gradient ∇F and the Hessian ∇ 2 F of the transformed function F are still ρ 1 -restricted Lipschitz continuous and ρ 2 -restricted Lipschitz continuous, respectively. Given the gradient in which the second inequality is due to the ρ 1 -restricted Lipschitz continuity of ∇f a , while the last inequality follows from the choice φ = (1 − δ)/2 in Assumption 4 and ρ 1 ≥ 1 + 2δ in Assumption 2. Moreover, since it is clear that ∇ 2 F is ρ 2 /2-restricted Lipschitz continuous as the second term in the above equation is independent of N . Next, we can repeat the argument in Lemma 8 with the function f s replaced with 4F/(1 + δ), noting that the latter function satisfies the 2δ/(1 + δ)-RIP 2r property as proven in Theorem 12 of Zhang, Bi, and Lavaei (2021).
Using the Lipschitz properties proven in Lemma 8, we will show that the objective value decreases at each iteration of the gradient descent algorithm with a sufficiently small step size η. Although the following lemma is stated for the symmetric problem (4), a similar result holds for the transformed asymmetric problem (7).
Lemma 11. Given a matrix X ∈ R n×r satisfying be the result of a one-step gradient descent applied to the symmetric problem (4) with the step size η satisfying 1/η ≥ 12ρ 1 r 1/2 (R + D) Proof.

Now, one can write
As a result, g s (X ) ≤ g s (X) − η ∇g s (X) 2 F /2.

B Proofs for Section 3
First, we need to introduce some notations that will be used throughout this section and next two sections. For every X ∈ R n×r , define e := vec(XX T − M * ) and let X ∈ R n 2 ×nr be the matrix satisfying X vec(U ) = vec(XU T + U X T ), ∀U ∈ R n×r .
The following lemma is the key to the analysis of optimality conditions for the spurious local minima of the symmetric problem (4), which will be used in both this and next sections.
Lemma 12. For every X ∈ R n×r , there exists a symmetric matrix H ∈ R n 2 ×n 2 satisfying the δ-RIP 2r property such that X T He ≤ ∇g s (X) F , 2I r ⊗ mat S (He) + (1 + δ)X T X λ min (∇ 2 g s (X))I nr .
Proof. For given matrix N ∈ R n×n , define an auxiliary function h N : R n×n → R by letting The mean value theorem over the function h N implies that where H ∈ R n 2 ×n 2 is the symmetric matrix that is independent of N and satisfies for all K, L ∈ R n×n . Moreover, since ∇ 2 f s ((1 − t)XX T + tM * ) satisfies the δ-RIP 2r property for all t ∈ [0, 1], H also satisfies the δ-RIP 2r . Now, we will prove the desired inequalities after choosing H as above. First, let U ∈ R n×r be the matrix satisfying vec(U ) = X T He and N = XU T + U X T . Then, by the equation (17), which arrives at the first inequality to be proved. Next, for every U ∈ R n×r with U = vec(U ), the equation (17) with in which W ∈ R n×n is the unique matrix satisfying vec(W ) = He. Therefore, in which the second inequality is due to the δ-RIP 2r property of the function f s . This leads to the second inequality to be proved.
The following lemma borrowed from Bhojanapalli, Neyshabur, and Srebro (2016) will also be useful. Lemma 13. Let X, Z ∈ R n×r be two arbitrary matrices such that X T Z is symmetric and positive semidefinite. It holds that Proof of Lemma 1. Define The assumption (9) onC implies that δ < q 1 , and thus one can always find a sufficiently small µ > 0 such that We choose µ = µ 2 /(1 + δ). Assume on the contrary that at a particular matrix X in the region (10). Obviously, XX T = M * . It results from (11) that and thus ∇g s (X) F ≤ µ XX T − M * F . Therefore, if we define δ * f (X, µ ) to be the optimal value of the optimization problem H is symmetric and satisfies δ-RIP 2r , then Lemma 12 shows that δ * f (X, µ ) ≤ δ. However, Lemma 14 (to be stated next) shows that which contradicts the inequality (19).
Lemma 14. If X ∈ R n×r is a matrix in the region (10) such that XX T = M * , then the optimal value δ * f (X, µ ) of the optimization problem (20) satisfies where q 1 and q 2 are defined in (18).
Proof. Let Z ∈ Z be a global minimizer such that ZZ T = M * . The fact that X is in the region (10) implies that X − Z F ≤ C. Without loss of generality, it can be assumed that X T Z is symmetric and positive semidefinite. If this is not the case, then we use the singular value decomposition X T Z = P DQ T in which P, Q ∈ R n×n are orthogonal and D ∈ R n×n is diagonal. By defining R = QP T , the matrix ZR becomes another global minimizer and X T (ZR) = P DQ T QP T = P DP T 0, implying that we can continue the following argument with ZR instead of Z.
The optimal value of the problem (20) is equal to that of the problem (1 − δ)I n 2 H (1 + δ)I n 2 .
This can be proved by applying Lemma 18 with a = µ e and a sufficiently large b such that both the optimal solutions of (20) and (21) satisfy the second constraint in (41) and (42). Now, define η * f (X, µ ) to be the optimal value of the following optimization problem: max Note that the first constraint in (21) and (22) is actually equivalent to X T He ≤ µ e . Given any feasible solution (δ, H) to the problem (21), is a feasible solution to the above problem (22). Therefore, To prove the desired inequality, it is sufficient to upper bound η * f (X, µ ) by finding a feasible solution to the dual problem of (22) given below: min U1,U2,G,λ,y tr(U 2 ) + µ 2 e 2 λ + tr(G), s. t. tr(U 1 ) = 1, As shown in the first part of the proof of Lemma 19 in Bi and Lavaei (2020), there exists a nonzero vector y ∈ R nr such that and If θ is the angle between e and Xy, then the above inequality implies that θ < π/2 and Therefore, cos θ ≥ q 1 .
(26) On the other hand, the Wielandt-Hoffman theorem implies that Combining the above inequality and (25) gives Again, θ is the angle between e and Xy. Then, The inequalities (26) and (27) imply that The proof is completed by the above inequality and (23).
Proof of Theorem 2. DefineC Then, it follows from Lemma 1 that there exists a constant µ > 0 such that the PL inequality is satisfied in the region By Lemma 13, in order to prove that a matrix X belongs to D, it suffices to show that Next, we prove by induction that X t satisfies (28) and g s (X t ) ≤ g s (X t−1 ) at each step of the iteration. Obviously, (28) holds for X 0 . At step t, by Lemma 11, the induction assumption and our choice of the step size η imply that g s (X t ) ≤ g s (X t−1 ) ≤ · · · ≤ g s (X 0 ). Then, the inequality (12) immediately implies that X t satisfies (28). Finally, since X t is guaranteed to be contained in a region satisfying the PL inequality for all t, we can apply Theorem 1 in Karimi, Nutini, and Schmidt (2016) to obtain

Now, (13) follows from the above inequality and (11).
After the transformation from asymmetric problems to symmetric problems, the proof of Theorem 3 is similar to that of Theorem 2, and thus it is omitted here.

C Proofs for Section 4
We first present the perturbed gradient descent algorithm with local improvement adapted from the general algorithm in Jin et al. (2017) for solving the symmetric problem (4), which can be also used to solve (5) after the transformation from asymmetric problems to symmetric problems. In Algorithm 1, X 0 is the initial point and 1 − γ is the success probability of the algorithm, while η and w are respectively the step size and perturbation size which are further determined by the parameter c. Furthermore, the parameter κ determines at what time the corresponding point is sufficiently close to the ground truth so that it belongs to the local convergence region and thus perturbations are no longer necessary in future iterations. After the first loop ends, the current matrix X t will satisfy (14). The choice of the parameters c and κ will be given in the proof of Theorem 5, but they can also be selected empirically.
The following lemma will be useful in the proof of Lemma 4, which can be obtained by combining Lemma 6 and Lemma 7 in Zhang, Bi, and Lavaei (2021).
Lemma 15. For any C > 0, there exist some κ > 0 and ζ > 0 such that for each X ∈ R n×r the two inequalities in (14) together with σ r (X) ≤ ζ will imply XX T − ZZ T F < C.
Proof of Lemma 4. Let ζ be the constant given by Lemma 15. We only need to consider all X ∈ R n×r satisfying σ r (X) > ζ, since the opposite case can be directly handled by applying Lemma 15. By Lemma 12, if X satisfies the approximate first-order and second-order necessary optimality conditions (14), we must have δ ≥ δ * (X, κ), where δ * (X, κ) is the optimal value of the following optimization problem: 2I r ⊗ mat S (He) + (1 + δ)X T X −κI nr , H is symmetric and satisfies δ-RIP 2r .
On the other hand, both the assumption δ < 1/2 and Lemma 16 imply that for some constant Γ, which further implies that The strict saddle property can then be proved by choosing a sufficiently small κ.
Lemma 16. Given a constant ζ > 0, if X ∈ R n×r is a matrix satisfying XX T = M * and σ r (X) > ζ, then the optimal value δ * (X, κ) of the optimization problem (29) satisfies Proof. Let Z ∈ Z be a global minimizer such that ZZ T = M * . By Lemma 18 with a = b = κ and an argument similar to the one in the proof of Lemma 14, we can introduce a relaxed optimization problem whose optimal value η * (X, κ) satisfies η * (X, κ) ≥ 1 − δ * (X, κ) 1 + δ * (X, κ) .
To prove the desired inequality, we need to find an upper bound for η * (X, κ), which can be achieved by finding a feasible solution to the dual problem of (30): min U1,U2,W, G,λ,y tr(U 2 ) + X T X, W + κ tr(W ) + κ 2 λ + tr(G) s. t. tr(U 1 ) = 1, Before describing the choice of the dual feasible solution, we need to represent the error vector e in a different form. Let P ∈ R n×n be the orthogonal projection matrix onto the range of X, and P ⊥ ∈ R n×n be the orthogonal projection matrix onto the orthogonal complement of the range of X. Then, Z can be decomposed as Z = PZ + P ⊥ Z, and there exists a matrix R ∈ R r×r such that PZ = XR. Note that then it can be verified that Moreover, we have XŶ T +Ŷ X T 2 F = 2 tr(X T XŶ TŶ ) + tr(X TŶ X TŶ ) + tr(Ŷ T XŶ T X) in which the first inequality is due to tr(X TŶ X TŶ ) = 1 4 tr((X T X(I r − RR T )) 2 ) = 1 4 tr((X(I r − RR T )X T ) 2 ) ≥ 0.
Assume first that Z ⊥ = P ⊥ Z = 0. The other case will be handled at the end of this proof. In the case when Z ⊥ = 0, we also have XŶ T +Ŷ X T = 0. Otherwise, the inequality (33) and the assumption σ r (X) > 0 imply thatŶ = 0. The orthogonality and the definition ofŶ in (32) then give X − XRR T = 0, P ⊥ ZR T = 0.
The first equation above implies that R is invertible since X has full column rank, which contradicts Z ⊥ = 0. Now, define the unit vectorsû Then,û 1 ⊥û 2 and e = e ( 1 − α 2û 1 − αû 2 ) We first describe our choices of the dual variables W and y (which will be scaled later). Let with Q, P orthogonal and S, G diagonal, such that S 11 = σ r (X) 2 . Fix a constant γ ∈ [0, 1] that is to be determined and define withŷ defined in (32) and Here, E ij is the elementary matrix of size n × r with the (i, j)-entry being 1. By our construction, X T V i = 0, which implies that In addition, and Therefore, which together with (34) implies that e Xy − w = 1, e, Xy − w = γα + 1 − γ 2 1 − α 2 = ψ(γ).
Next, the inequality (33) and the assumption σ r (X) > ζ imply that Putting (36), (38), (39) and (40) into the above equation, we can obtain Choosing the best γ ∈ [0, 1] to minimize the far right-side of the above inequality leads to Here, α and β are defined in (35) and (37), respectively. In the proof of Theorem 1.2 in Zhang (2021), it is shown that η 0 (X) ≤ 1/3 for every X with XX T = ZZ T , which gives our desired inequality. Finally, we still need to deal with the case when P ⊥ Z = 0. In this case, we know that Xŷ = e withŷ defined in (32). Then, it is easy to check that forms a feasible solution to the dual problem (31) whose objective value is 2κ y * , which is at most κ/( √ 2ζ e ) by the inequality (33).
Lemma 17. Consider Algorithm 1 for solving the symmetric problem (4). If the initial matrix X 0 satisfies X 0 X T 0 F ≤ D, the step size η satisfies 1/η ≥ 48ρ 1 r 1/2 1 + δ 1 − δ D , and the perturbation size w satisfies then during the first loop the trajectory X t is always confined in the region Proof. For convenience, we introduce the set The iteration is initialized at the point X 0 ∈ D 1 . Assume that at some time instance t the current matrix X t ∈ D 1 , g s (X t ) ≤ g s (X 0 ), and some perturbation needs to be added because ∇g s (X t ) F is small. In this case, a random noise W is generated from the uniform distribution in the ball of radius w. The algorithm saves the original point X t toX t and replaces X t with X t + W . Then, similar to the inequality (16), the old pointX t satisfies and thus the new point X t satisfies by our choice of the parameter w. Due to the design of the perturbed gradient descent algorithm, the perturbation will never be taken in the next t thres number of iterations (t thres is defined in Algorithm 1). As a result, Lemma 11, X t ∈ D and our choice of the step size η imply that g s (X t+1 ) ≤ g s (X t ). Hence, the inequality (12) gives which shows that X t+2 ∈ D. Repeating this argument, it can be concluded that g s (X t+k ) ≤ g s (X t ) and X t+k ∈ D for all k = 1, . . . , t thres . After X t+tthres is obtained, the algorithm compares g s (X t+tthres ) with g s (X t ), and the iteration continues only if g s (X t+tthres ) ≤ g s (X t ). When this is the case, g s (X t+tthres ) ≤ g s (X 0 ), and by the inequality (12) again, we have and thus X t+tthres ∈ D 1 . Assume that no perturbation is added at steps t + t thres + 1, . . . , t + t thres + l − 1. Then, using a similar argument as above, we can prove that g s (X t+tthres+k ) ≤ g s (X t+tthres ) ≤ g s (X 0 ), X t+tthres+k ∈ D 1 , ∀k = 1, . . . , l − 1. If perturbation needs to be added at step t + t thres + l, we can repeat the above argument with t + t thres + l instead of t, which leads to the desired result.
Proof of Theorem 5. In the first stage of the algorithm, the perturbed gradient descent method is applied. If the parameter c is sufficiently small, then the step size η and the perturbation size w will satisfy the assumptions in Lemma 17. In this case, Lemma 17 implies that the iterations are taken within a region in which ∇g s and ∇ 2 g s are Lipschitz continuous. Let κ be the constant given by Lemma 4 such that the approximate second-order necessary optimality conditions (14) will imply that is the radius of the local linear convergence region provided by Theorem 2. Now, Theorem 3 in Jin et al. (2017) shows that with probability 1 − γ the first loop will stop with a solutionX satisfying (14), and thusX is within the local convergence region. Note that the number of iterations in this stage is fixed for a given initial matrix X 0 , and that this number is independent of .
Next, the gradient descent algorithm is run with initialization at the matrixX. Theorem 2 implies that after an additional O(log(1/ )) number of iterations we find a solutionX satisfying the accuracy requirement.

D Reformulation of RIP-Constrained Optimization
In this section, we will prove the following lemma that is used in Appendix B and Appendix C, which is a generalization of Theorem 8 in Zhang, Sojoudi, and Lavaei (2019). Lemma 18. For every a, b ≥ 0, the following two optimization problems min δ,H δ s. t. X T He ≤ a, 2I r ⊗ mat S (He) + (1 + δ)X T X −bI nr , H is symmetric and satisfies δ-RIP 2r , and min δ,H δ s. t. I nr X T He (X T He) T a 2 0, 2I r ⊗ mat S (He) + (1 + δ)X T X −bI nr , (1 − δ)I n 2 H (1 + δ)I n 2 , have the same optimal value.
Proof. Let OPT(X, Z) be the optimal value of (41) and LMI(X, Z) be the optimal value of (42). Our goal is to prove that OPT(X, Z) = LMI(X, Z) for given X, Z ∈ R n×r . Let (v 1 , . . . , v n ) be an orthogonal basis of R n such that (v 1 , . . . , v d ) spans the column spaces of both X and Z. Note that d ≤ 2r. Let P ∈ R n×d be the matrix with the columns (v 1 , . . . , v d ) and P ⊥ ∈ R n×(n−d) be the matrix with the columns (v d+1 , . . . , v n ). Then, P T P = I d , P T ⊥ P ⊥ = I n−d , P T ⊥ P = 0, P T P ⊥ = 0, P P T + P ⊥ P T ⊥ = I n , P P T X = X, P P T Z = Z. Define P = P ⊗ P . Consider the auxiliary optimization problem min δ,H δ s. t.
I nr X T He (X T He) T a 2 0, 2I r ⊗ mat S (He) + (1 + δ)X T X −bI nr , (1 − δ)I d 2 P T HP (1 + δ)I d 2 , and denote its optimal value as the function LMI(X, Z). Given an arbitrary symmetric matrix H ∈ R n 2 ×n 2 , if H satisfies the last constraint in (42), then it obviously satisfies δ-RIP 2r and subsequently the last constraint in (41). On the other hand, if H satisfies the last constraint in (41), for every matrix Y ∈ R d×d with Y = vec(Y ), since rank(P Y P T ) ≤ d ≤ 2r and vec(P Y P T ) = PY, by δ-RIP 2r property, one arrives at which implies that H satisfies the last constraint in (43). Moreover, since the first constraint in (41) and the first constraint in (42) and (43) are equivalent, the above discussion implies that LMI(X, Z) ≥ OPT(X, Z) ≥ LMI(X, Z).
Before stating Lemma 20 and Lemma 21 that were needed in the proof of Lemma 18, we should first state a preliminary result below. Lemma 19. Defineê andX in the same way as e and X, except that X and Z are replaced byX andẐ, respectively. Then, it holds that e = Pê, X(I r ⊗ P ) = PX, P T X =X(I r ⊗ P ) T .
Since the columns of I r ⊗ P and I r ⊗ P ⊥ form a basis for R nr , the above inequalities imply that S is positive semidefinite, and thus the second constraint in (42) is satisfied.
Proof. The dual problem of the optimization problem defining LMI(X,Ẑ) can be expressed as SinceÛ 1 = 1 − µ X 2 2d 2 I d 2 − µr 2 M,Û 2 = 1 − µ X 2 2d 2 I d 2 + µr 2 M,V = µI dr ,Ĝ = I dr ,λ = 1,ŷ = 0, where M = vec(I d )ê T +ê vec(I d ) T , is a strict feasible solution to the above dual problem (44) as long as µ > 0 is sufficiently small, Slater's condition implies that strong duality holds for the optimization problem defining LMI(X,Ẑ). Therefore, we only need to prove that the optimal value of (44) is smaller than or equal to the optimal value of the dual of the optimization problem defining LMI(X, Z) given by: The above claim can be verified by noting that given any feasible solution (Û 1 ,Û 2 ,V ,Ĝ,λ,ŷ) to (44), the matrices form a feasible solution to (45), and both solutions have the same optimal value.