Geometric Analysis of Matrix Sensing over Graphs
Authors: Haixiang Zhang
Ying Chen
Javad Lavaei
Venue: NeurIPS 2023 poster (2023)
Keywords: Low-rank matrix optimization
non-convex optimization

Abstract: In this work, we consider the problem of matrix sensing over graphs (MSoG). As a general case of matrix completion and matrix sensing problems, the MSoG problem has not been analyzed in the literature and the existing results cannot be directly applied to the MSoG problem. This work provides the first theoretical results on the optimization landscape of the MSoG problem. More specifically, we propose a new condition, named the $\Omega$-RIP condition, to characterize the optimization complexity of the problem. In addition, with an improved regularizer of the incoherence, we prove that the strict saddle property holds for the MSoG problem with high probability under the incoherence condition and the $\Omega$-RIP condition, which guarantees the polynomial-time global convergence of saddle-avoiding methods. Compared with state-of-the-art results, the bounds in this work are tight up to a constant. Besides the theoretical guarantees, we numerically illustrate the close relation between the $\Omega$-RIP condition and the optimization complexity.

Geometric Analysis of Matrix Sensing over Graphs
Haixiang Zhang
Ying Chen Department of IBOR University of California, Berkeley
Department of Mathematics University of California, Berkeley
Berkeley, CA 94720 ha Lelxxingg_hang@eeeeeee
Berkeley, CA 94720
edu
ying-chen(bbereeley edu
Javad Lavaei
Department of IEOR
University of California, Berkeley Berkeley, CA 94720 lavaei @wwrreeee.............. edu
Abstract
In this work, we consider the problem of matrix sensing over graphs (MSoG). As a general case of matrix completion and matrix sensing problems, the MSoG problem has not been analyzed in the literature and the existing results cannot be directly applied to the MSoG problem. This work provides the first theoretical results on the optimization landscape of the MSoG problem. More specifically, we propose new condition, named the Q--IP condition, to characterize the optimization complexity of the problem. In addition, with an improved regularizer of the incoherence, we prove that the strict saddle property holds for the MSoG problem with high probability under the incoherence condition and the Q-RIP condition, which guarantees the polynomial-time global convergence of saddle- avoiding methods. Compared with state-of-the-art results, the bounds in this work are tight up to a constant. Besides the theoretical guarantees, we numerically illustrate the close relation between the Ω-RIP condition and the optimization complexity.
1 Introduction
In a wide range problems in the fields machine learning. signal processing and power systems, an unknown low-rank matrix parameter should be estimated from few measurements of the matrix. To be more specific, given some measurements of the unknown symmetric and positive semi-definite (PSD) matrix M E Roxn of rank n, the low-rank matrix optimization problem be formulated as (1)
min f(M;M") s. M rank(M) S ME
where f(; Mn) is loss function that penalizes the mismatch between M and M The goal is to recover the matrix M via finding a global minimizer of problem (1). Applications of this problem include matrix sensing [31, 40, 38J, matrix completion [10, 11, 17], phase retrieval [8, 33, 14], and power systems [39, 24]; see the review papers [13, 15] for more applications. Early attempts to deal with the nonconvex rank constraint the problem focused on solving a convex relaxation of (1); see [10, 31, 11, 7J. However, the convex relaxation approach usually updates the matrix variable via the Singular Value Decomposition (SVD) in each iteration. This will lead to an ((z3) computational complexity in each iteration and On??) space complexity, which prohibitively
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

high for scage-scale problems; see the numerical comparison in [41]. Similar issues are observed for algorithms based on the Singular Value Projection [20] and Riemannian optimization algorithms [35, 36, 19, 1, 27].
To improve the computation and memory efficiency, the Burer-Monteiro factorization approach was proposed in [6], which is based on the fact that the mapping U' + UU is surjective onto the manifold of PSD matrices of rank at most r, where U R More coneretely, problem (1) is equivalent to
(2)
min f(UU"; UERaxe
Due to the non-convexity of the mapping U + UUT, problem (2) is an unconstrained non-convex problem and may have spurious second-orde order critical points (i.e., second-order critical points that do not correspond to the ground truth matrix M*). In general, saddle-avoiding local search methods are only able to find c-approximate second-order critical points'. As a result, local search methods with random initialization will likely be stuck at spurious second-order critical points and unable to converge to the ground truth solution. However, in a variety of real-world applications, simple algorithms such as perturbed gradient descent methods and alternating minimization methods have achieved empirical success on problem (2). Recently, substantial progress has been made on the theoretical explanation of the benign behavior of these algorithms. For example, the alternating minimization algorithm was studied [21, 28, 29]. The (stochastic) gradient descent algorithm, which is in general easier implement than the alternating minimization algorithm, in [8, 34, 37, 14, 13]. Moreover, the gradient descent algorithm is proved to have the implicit regularization phenomenon in the vveepparamettrizzaioon case [26, 32).
analyzed
Besides the algorithmic analysis, a large amount of literature [17, 33, 42, 38] focused on the geometric analysis of the landscape of problem (2), which usually depends on the strict-saddle property [33]. Intuitively, the strict-saddle property states that at any feasible point of problem (2), at least one of
the three properties will hold: (i) the point is close to a global solution; (ii) the norm of the gradient is large: (iii) the Hessian matrix has a negative eigenvalue.
the later two cases, saddle-escaping algorithms [12, 23, 2] are able to find descent direction and thus, these algorithms will converge globally in polynomial time. The formal definition of the strict-saddle property is provided in Section 3.1. In the following, we review the state-of tee-thheatt conditions for two special classes of problem (2) that guarantee the strict-saddle property; see the survey [15] for other problem classes.
1.1 Matrix sensing and the Restricted Isometry Property (RIP) condition
In the matrix sensing problem, the information of the ground truth matrix M is gathered via the measurement operator AA The loss function f is usually chosen to be the negative likelihodood function. For example, in the classic linear matrix sensing problem, the operator A is a linear operator defined as (3)
A(M) = (A, ..... (Am, M)], VM E R"X*
where m is the number of measurements and A, E Rax* contains independently identically dis- tributed (i.i.) Gaussian random entries and A,'s are independent of each other. If the measurement noise is Gaussian, the maximum likelihood estimation is equivalent to the following minimization problem
(4)
min |AAUUT) - A(M')
UER
More examples of the (non-linear) matrix sensing problem are discussed in [42]. One of the most important conditions that guarantee the benign landscapes is the RIP condition:
Definition (RIP Condition(31, 421). Given natural numbers and 8, the function f(; M*) is said
to satisfy the Restricted Isometry Property (RIP) of rank (2r, 2s) for a constant d E [0. 1), denoted
as 6-RIP 2r.2s, if
(5)
[1-8)]KIPP & [VM)(M (K S (1+ (1+8)|KK
holds for all matrices M, K E IR such that rank(M) < 2r and rank(K) < 2s, where [ f(M; M)) (K, K) is the curvature the Hessian at point M along direction K.
A point zo is called an e-approximate second-order critical point to the optimization problem min, F(x) if V FFr( |e and Amin F(x)) 2 -c.
2

---

For the linear matrix sensing problem (4), it is proved in [9] that the 8-RIP 2r: condition holds with high probability m = 2) The RIP condition is also established in many other applications of the matrix sensing problem [42, 4] and of independent research interest. The constant ó plays critical role in characterizing the optimization landscape of problem (2). More specifically, in [5], the authors showed that the strict-saddle property holds for problem (2) if the 8-RIP condition holds with 8 < 1/2. Counterexamples have been constructed in [40, 38] to illustrate that the strict-saddle property may fail under the 8-R 3-RIP22r.2- condition with 5 2 1/2.
1.2 Matrix completion and the incoherence condition
In spite of the strong theoretical results under the RIP condition, there exist a large number of applications that do not satisfy the RIP condition. A well-studied class of problems that does not satisfy the RIP condition is the matrix completion problem. For the matrix completion problem, a subset Q2 C [n] [n]] of entries of M are observed and the goal is to recover the low-rank ground truth matrix from the observed entries, For every matrix M E Rax,, we denote the projection of M onto Ω Ma, namely,
{o My if (i,j) Q otherwise.
(Ma)i
Using the lo-loss function, the matrix completion problem defined as (6)
min UER
M - Mall
The matrix completion problem (6) is special case of the linear matrix sensing problem (4), where the sample size m equal to [S2] and each measurement matrix A, contains exactly one nonzero entry. We note that the 5-RIP2rr.2- condition does not hold for problem (6) unless observe all entries of M* i.e., when f = [n] x [n]. As an alternative to the RIP condition, the incoherence of M is useful in characterizing the complexity of problem (6).
Definition 2 (Incoherence Condition [10]). Given E nl. the ground truth matrix M* is said to be p-incoherent
(7)
VeT S Vpr/n, Vi E
where V (V**) is the truncated SVD of M* and e is the i-th standard basis of RR"
Intuitively, the incoherence of M measures the sparsity of the low-rank ground truth matrix. If the incoherence large, the matrix M* highly sparse and necessary to measure considerably many entries of M to observe nonzero entries. On the other hand, a relatively small incoherence of .M* is able to avoid the extreme case. Except the limited literature on the deterministic matrix completion problem [3, 25, 30], the majority of the matrix completion literature considered the following Bernoulli sampling model:
Definition 3 (Bernoulli Sampling Model), Given sampling rate p (0, 1). each index (i,5) [n] x [n] belongs to the set Q independently with probability p.
Under the Bernoulli sampling model, the objective function of problem (6) is well-behaved over the set of matrices with small incoherence. Therefore, regularizer that penalizes the incoherence of UUT is included and instead solve the following regularized matrix completion problem:
|I(UU)) Malle + + ig(n] (1 - UERaxr
(8)
min
where (xr) == max 0} for all x E IR and a, À > O are constants. Intuitively, the coefficient 1/p used to "normalize" the fz-norm. We note that there exists an algorithm that can solve problem (6) without the incoherence regularizer [13]. However, the algorithm relies on the spectral initialization,
which requires more computational effort than the factorization approach (2). proved in [18, 17] that if the sampling rate satisfies
(9)
ap 2 Olu² ( (x*)) log
the problem (8) satisfies the strict-saddle property with high probability, where x* is the condition lower bound mp 2 O(rr log n) is necessary for the exact completion with high probability.
number of M On the other hand, it is proved in [11] that the
3

---

3
2
4
6
Figure 1: Example of the problem of matrix sensing over graphs. The vertex set is V = [6] and the edge set is = {(1, 1), (1,2), (1,3), (1, (2, (3, (3, 5), (4, 6), 6) (5, 6), (6,6))
1.3 Motivating example: Matrix sensing over graphs
Although the matrix sensing problem and the matrix completion problem well-studied in literature, we show that there exist important applications of (2) that belong to a much broader class of problems than the special classes previously studied by the existing works. Hence, the current theoretical results cannot be directly applied to these applications and it remains unknown whether saddle-avoiding algorithms can find the ground truth matrix M in polynomial time.
Consider an undirected graph G = (V,E), where V and & are the set of vertices and the set of edges, respectively. For the notational simplicity, assume that V [n]. Then, the edge set & is subset of [n] x (n). The goal of this problem to recover the ground truth matrix M via measurements of its entries (Mr () E). Instead of directly observing each entry My . for each node E V, observe a "mixture" (i.e., the output of a function) of the entries in the set
E, = {ii,j) I is incident to i}.
Denote the loss function for node as (Me, Mg)) The total loss function is the of the loss function for all nodes; namely, we consider the problem
(10)
min UERUXP
Σ KE(n)
fa (EUU)))M;M)
Since Ui the above problem is special case of the general problem (11)
min ff [(UU));;ME]]
UERWXy
where we define / [e; = Eiein] Si [(UU)) )a, M We name the problem (11) the matrix sensing over graphs (MSoG) problem. The MSoG problem has number of applications, including the state estimation problem in power systems [39, 24]. We note that in those applications, the loss function fi is quadratic function of entries of Mg, and M see the example in the end of this section and the srrah-structured quadratic sensing problem in [24].
To better understand (10) as special type of MSoG, we consider toy example where the undirected vertices and is plotted in Figure In this example, the objective function of the
graph & has MSoG problem is
[[Me; ME) = (M11 M12, M1a; Mi1 Mīg, Mis) + f22M1 M29; M M22)
+ faM3,, M31, Mas; M M2a, M55) + fa(Ma1, M43, MaS; M M Mi6)
+ fa (MMs,, Mss; Mca, Mt3) + Jo(Ma4, Mes. Mee; M M Mea).
where we recall that we factorize M into UTT in the Burer- Montr-ronteiro factorization approach. Hence, only 13 entries of the matrix M with n 36 entries appear in the measurements. For example, the entry Mis does not appear in any measurements. If we directly observe these 13 entries, we can define the loss function by the f2lloss function:
fi (M1,, M12, M13; Mf Mi2. Mía) (M1 2 (M12 2 + (M1s Mia)
We can define other loss functions f2..... fe similar way. Then, the MSoG problem reduces to the matrix completion problem with Ω = E, namely, the objective function becomes
M(M |

---

Therefore, the matrix completion problem (6) is a special case of the MSoG problem (11) and the existing results for the matrix completion problem cannot be directly applied to problem (11). Similarly, if 12 is complete graph, the matrix sensing problem (10) becomes a special case of the MSOG problem. Moreover, since some entries of M do not appear in any of the measurements in general, it is easy to verify that the RIP condition (5) does not hold for problem (11). In summary,
the existing results based on the RIP condition [38] and the incoherence condition [17, 13], as well as the results for other applications of the low-rank matrix optimization problem, cannot be directly applied to the MSoG problem.
Next, we show that the power state estimation problem [39. 24] can be formulated as the MSoG problem (11). This is the most important data-analysis problem for power systems and is solved every 5-15 minutes in practice using heuristic methods with little theoretical guarantees. Several major blackouts were attributed the failure of solving this problem. An N-bus power system can be represented by an undirected graph g (V. E), where V = [N] and & C V x V are the set of buses and the set of lines, respectively. The state of the power system is characterized by the voltage phasors v E CN where C.V is the N-dimensional complex space. Our goal is to recover the voltage phasors via some measurements, without loss of generality, we assume that we measure the voltage magnitude at each bus and the active power flows over each line, Suppose that + iy for x, E RN, where is the imagnary unit. Define
E 22
:=
The following two types of measurements are available:
1. For each bus k E V. the voltage magnitude is defined as |vv where the magnitude for complex number
I& + iyı: is defined as |eal2 2 == 2 + uk The voltage magnitude can be written in the matrix form as
|ms| = x (eRof + +
where e₁ is the k-th standard basis of R.N.
2. For each line (k, e) E &, let Y&e E C be the admittance of the line. The active power flow from bus to bus is P&t number z. We observe the active power flows pue and pek for all lines (k, é) E E. Suppose that Ysz- = Pse + iQke for Pkk, Que E IK for all (ks, E. Then, the active power flow can be written in the matrix form
(vx(1% - V where z" is the conjugate of complex
Pkt z [Pre exee + + eN= + Que(eneT
e(e z.
Therefore, these observations can be written the quadratic form z" M, z for some matrices MI,..., Mm R2Nx2N where m 2N + ||] is the number of observations. For each sens- ing matrix Mj. only the diagonal entries and [k. E), (N + k. f), (k, N + f), (N + N + entries for (k: E) E E may be nonzero. In addition, we fix 3/1 2N+1 0 since a unitary transformation on will not change the loss function. As result, the problem can be written as a (2N 1) -)-dimensional rank-1 MSoG problem:
min WER2N
Σ
] (M,, wwT ZzT)² s.t. WN+1 O.
1.4 Problem formulation and contributions
In this work, we propose the first sufficient condition that guarantees the benign landscape of the MSoG problem. More specifically, we consider the case when the graph G is random graph obeying the Erdös Rényi model. Namely, each pair (i.j) E V x V belongs to the edge set independently with probability p. Under this random graph model and the assumption that the vertex set is [n]. each entry MC is indirectly observed (i.e., is involved in some measurements) independently with probability p. For comparison with the existing results of the matrix completion problem (6), we denote the edge set, which is equivalent to the set of indices of observed entries, as Ω C [r]] [m]. Then, the set follows the Bernoulli sampling model (Definition problem, aim at recovering the ground truth matrix M by solving the following problem with an
3). Similar to the matrix completion
5

---

improved regularizer:
min 2 ((UU)))) :M + Eienn (llef
(12)
VER p
where we define the regularizer
r(x) = X {f[ [(0 (())==
aay ay 10a)+ + 99]* (1- (w|) dy, Vo E IR
Note that in problem (12), we use a novel incoherence regularizer that is different from those in the prior literature. The regularizer is the convolution between [(x ay 10a)_ 9a] and the probability density function 1 - |y| on [-1, 1J. which is twice continuously differentiable in (the set of discontinuous points of the derivatives is a zero measure set). Hence, the regularizer (lle, U))e) twice continuously differentiable in U. In addition, we can exchange the convolution and the differentiation with respect to æ. Since the integrand is a quartic polynomial, the objective value and the derivatives of the regularizer can be exactly evaluated by numerical integration schemes with O(1) ) computations. Let R C R be the set of U such that ||e: Ul O(a) for all i [n]. The intuition behind the design of the incoherence regularizer to ensure that every approximate first-order critical point of problem (11) must lie in set R. More specifically, the regularizer ensures that (i) outside R, the gradient of the regularizer is large enough such that any approximate first-order critical point must lie in R, (ii) the regularizer and its Hessian matrix have sufficiently small contribution to the objective function in R.
Besides the randomness model of Ω we make the following three assumptions about problem (12). Assumption 1. The loss function f is twice continuously differentiable. Assumption 2. The ground truth matrix M is PSD and rank-r.
Assumption 3. The ground truth matrix M is a global minimizer of f((-); Ma]-
We note that these assumptions are standard in the low-rank optimization literature. The first assumption is a mild regularity assumption on the loss function and is satisfied by a wide range of loss functions, including the fz-loss and the negative log-likelihode function of various probability distributions. The second assumption is based on the prior knowledge about the specific application. The third assumption is necessary for the exact recovery of the ground truth M
We give an informal statement of the main result in the following theorem. Here, consider the (6, 12) condition, which is an extension of the classic 5-RIP condition. Intuitively, the constant 8 E [0, 1) measures the similarity between f and the fo-loss function. The rigorous definition is provided in Definition 4.
Theorem (Informal). Suppose that the loss function f satisfies the (2)-RPP condition with high probability over Q and the sampling rate p satisfies
up 2 0ly2r²(('")) logn))
where x² is the condition number of M Then, with a suitable choice of the parameters a and X, problem (12) satisfies the strict saddle property with high probability. Furthermore, there exist algorithms that can find solution Ug such that [ ||r S c in polynomial time with the same probability.
The above theorem provides the first theoretical result for the MSoG problem. Basically, Theorem I says that combination of the incoherence condition and the Ω-RIP condition is sufficient to guarantee that problem (12) can be solved in polynomial time with high probability. In addition, the lower bound the sampling rate is better than the bound in [17] (i.e., the bound in (9)). This is result of our improved regularizer. Finally, the upper bound on the Q-RIP constant an absolute constant (namely, 1/16).
We note that since the result of Theorem only holds with high probability, it is not necessary for the Q-RIP condition to hold for all subsets Q. Instead, we only require the Q-RIP condition to hold for a set of Ω that correspond to a high probubility over the distribution of In the special case when Ωt is a deterministic subset that satisfies similar "benign" properties as the random graph case, only need the Q-RIP condition for this deterministic subset Ω.
Remark 1.

---

The next informal theorem shows that our upper bound is optimal up to a constant.
Theorem 2 (Informal). There exists a loss function f such that: (i) f satisfies the (1/2, (2)-RRIP2r222 condition for all Q2 C 'n] x [n), (ii) for all p E [0, 11, problem (12) has a spurious second-order critical point with probability at least (3 v / 0.38.
Intuitively, Theorem 2 provides a negative result saying that the tightest upper bound on the RIP constant cannot be better than 1/2 if the problem (12) has benign landscape with high probability. This is also the first negative result on the problem (12).
1.5 Notation
For every natural number n, we denote [n]] := {1..... n). The operator 2- 2-norm and the Frobenius norm of a matrix M are denoted as ||M and [I. respectively. The trace of matrix M denoted as tr(M). The inner product between two matrices is defined
(M, == tr(M"N). For any matrix M E Ruxx, we denote its singular values by 01 (MM) 2 ... ...2 (M)). Let Le be the singular value (M.). The condition number of M is K² 0. 00/00. The minimum eigenvalue of matrix M is denoted as Amin (M). For any two matrices A, B E R=xm, we use A & B to denote the fourth-order tensor whose (i, j, k; f) element is A The identity tensor is denoted as I. The notation M ž 0 means that the matrix M is PSD. The sub-matrix Reg.et consists of the i-th to the j-th rows and the k-th to the f-th columns of matrix R. The action of the Hessian v on any two matrices K and L is given by [V2 f(M) L) Eis.kel' (MM) ee The notation (g)) means that there exists an absolute constant C' such that f S C g. The notation (g) means that there exist absolute constants C2, C22 > 0 such that C S f C2 g.
2 R-RIP Condition
Since the objective function f (My; Mā)) does not satisfy the classic RIP condition unless all elements of MM are observed (i.e., when f = [m/] x [n]),, it is necessary to consider a generalization of the RIP condition to the partial observation case.
Definition& 4 (Ω-RIP Condition). Given a subset f2 C [m] [m] and natural numbers the function
[(; M*) is said to satisfy the R-Restricted Isometry Property (St-RIP rank (2r, 28) for a constant 8 E [0,1), denoted as (6, R)-RIP 2r,2s if
(13)
(1-6) Kal 1 <
f(Ma (M*)) (Ko, Kn) S (1+))|Kal?
holds for all matrices M, K E RR such that rank(M) S 2r, rank (K) S 2s.
Note that the matrix completion problem satisfies the (0. 22--RP2rr condition. In the following, we demonstrate another example for which the Ω-RIP condition holds with a non-zero constant 5.
Example (Linear matrix sensing over graphs). In the linear matrix sensing over graphs problem, the loss function is defined as
f(Moi M2) =- (A(M)) - A(M
where the linear operator A: Buxnn + IRTh (defined in (3)) is generated by Gaussian measarements and m. is the number of measurements. For all subsets C. [n] x [n], a similar proof to that of Theorem 2.3 of [9] implies that the (5, R...RRRPP2222. condition holds with high probability when m 2 cnr /52 for some constant >> O. The intuition behind the proof is that the constructed c-net for the linear matrix sensing problem also an c-net for the linear MSoG problem since ||Ma MallF < || - M'lle for all M, M' E Rgax..
Remark 2. In the above example and other examples in practice, the Q-RIP condition holds with high probability for a fixed subset Ω. Therefore, we can focus the event when the Q-RIP condition holds since otherwise the results will only differ by a sufficiently small probability.
In Section 4 and Appendix C, we numerically show that the optimization complexity of problem (11) is closely related to the Ω-RIP constant and the sampling rate
A point Up is called a spurious second-orde critical point of problem (12) if Up satisfies the first- and the second-on second-order necessary optimality conditions but UoUi F M
7

---

3
Theoretical Results
In this section, we provide strong theoretical results on the MSoG problem (12). We first develop sufficient condition on the benign landscape of problem (12) and then study the tightness of our developed condition.
3.1 Global landscape: Striet saddle property
First, we develop conditions under which problem (12) does not have any spurious second-order critical points and therefore saddle-sscaping methods (e.g.. [22, 23)) can find approximate global minimum in polynomial time. To guarantee the global convergence, the strict saddle property is commonly considered in the literature:
Definition 5 (Strict Saddle Property [33]). Consider optimization problem XCRR F(x) and let X denote the set of its global minima. We say that the problem satisfies the (0, ()73)))) -strict saddle property for 0, 3.77
at least one of the following conditions is satisfied for every x X:
dist (x, S 0;
[VF(())l 2 3; Amin F2)(()) -
where (x, == inf || 1F the distance between x and X
For the low-rank optimization problem, the distance in the factorization space is equivalent to the distance in the matrix space in the sense that there exist constants ei (x(",, (x²)) > 0 such that
(1x²) IIU - U" & || (U*)) I c2((x)) IU U'IIF
holds for all U X' long as ||U U U*I|F small and X'* is bounded [34]. Denote the objective function of problem (12) as E(U). As an example of saddle-avoiding methods, the accelerated perturbed gradient descent algorithm [23] can find point Un such that
| = O()), Amin (eE(U))] -0(ve
in (c-11.7)) iterations with high probability. we choose c > 0 to be small enough, the strict saddle property ensures that the point Un satisfies [[ M O We note that the Lipschitz continuity of the Hessian of can be guaranteed by the regularity assumption and the boundedness of trajectories of the algorithm, which can be proved in similar way as Theorem 8 in [22]. In summary, if the strict saddle property holds, we can apply saddle-avoiding methods to achieve the polynomial- -ime global convergence for problem (12).
Now, we prove that the problem (12) satisfies the strict saddle property with high probability under the 12-RIP2r.2r condition and the incoherence condition. Compared with Theorem 1, we assume, for the simplicity of the statement of the theorem, that the Q2-IP condition holds for all subset 52 since otherwise, the result will only differ by small probability.
Theorem 3. Suppose that the loss function satisfies the (5, R1PP 2r.2r condition for all Ω C [n] x [n] and
( n2
(VB vnd)nn Vpr
--=
np
2
n), 8< 16"
Then, there exists small constant e >> O such that with probability at least 1 - 1-1--L/pee 1/poly(n), the MSoG problem (12) satisfies the (0, B, 7)-strict saddle property with
0 O(c/ot),
==c. -==((110)))
In Theorem 3, we provide the first theoretical results on the MSoG problem (12). Basically, the theorem shows that if the 12-RIP2r.27 constant is smaller than an absolute constant, then the same sampling rate as for the matrix completion problem is sufficient to guarantee the benign landscape of problem (12). Therefore, the result is generalization of the results in [17], which considered the case when the Q-RIP constant 8 is zero and the sampling rate p satisfies stricter condition (9), On the other hand, if the sampling rate p is equal to 1, Theorem guarantees that the strict saddle property holds when the (regular) RIP condition holds with å < 1/16. Compared with the state-of- ofeee-------tttttt results in [38, 5]. the upper bound on 8 in our work may not be optimal but only worse by an absolute constant. We leave the improvement of the upper bound as future work.

---

3.2 Tightness of the Q-RIP condition
To study the tightness of our Q-RIP condition for problem (12), we construct an instance of problem (12) that satisfies the R condition but has spurious second-order critical points. Note that the existence of spurious second-order critical points negates the strict saddle property. The counterexample is based on a similar idea those in [38]. More specifically, assume that n 2 2r and consider the tensor:
H : Σ ie(rl
{
[
@ (62- 12
+ (e2:e21) @ (e2122)
2
+
[ @ (e2)e2) + (e2 @ (E 1 x1
2
1
[(e2-
( x (e2--122) + [22 @ (e21 ,
4
1
(e2=-122) (e2: 1) + (e2:) (e2i 122 }
where e, E R is the i-th standard basis of R". The rank-r ground truth matrix M is constructed as
e2r-11, M = U-")T" Eieeo 02-16-111
Then, the loss function is given by
fa/2(Mai MD) [ Ma) (3 (2 (M₃ - MR), VM R"x*.
is proved in [38] that Ω2 = [n] x [n]]. the function fa/2 satisfies the 1/2-RIP2r.2 2r.2r condition and has a spurious second-order critical point. In this work, we generalize the results to the case when the set Q is random and the objective function contains a regularizer.
Theorem 4. Suppose that the loss function in problem (12) chosen to be fa/2- Then, it holds that:
1. The loss function J3/2 satisfies the 1/2,2))RIPPp condition for all Q C [m]] x [n]]
2. For all p E (0, 1). problem (12) has a spurious second-order critical point with probability least 1
(1+2222)
2 (3 v52/2.
We note that the results in Theorem 4 holds for all p E [0, 1]. From Theorem 4, cannot improve the upper bound of 8 in Theorem to be better than 1/2. In addition, this result shows that our bound in Theorem 3 is optimal up to a constant. This tightness result is consistent with that of the matrix sensing problem [40, 38].
4 Numerical Illustrations
In this section, we show how the optimization complexity is related to the Q-RIP constant and the sampling rate p via numerical example. Here, the optimization complexity refers to the probability that the randomly initialized gradient descent algorithm can find the ground truth matrix M In this example, we choose a random orthogonal matrix V R=xn and define the loss function be
1 JIM (VM*V")a (c-I I H) [M (VM'V")o. VM R
MMi (VMVV ao]
where e a hypee--parameter and the tensor H and the ground truth M are defined in Section 3.2. In addition, by similar analysis in Section 3.2, can prove that the function fo satisfies the
2 condition we choose e = 3/2. We also numerically verify this conclusion by
checking the curvature 2 (Mp; MG]](K K) along 10a random directions K E pax= Since fa/2 is quadratic function, the (1/2,0) RIP 2r,2r condition is given by
3
3 Koll Ko -
Koll? < Ko
I I )
AK ERa
2
2

---

0.7
0.01
0.01
0.00
0.00
0.00
0.01
0.75
0.15
0.16
0.12
0.15 0.15 0.14 0.14
0.15 0.13
0.11
0.08
0.12
0.12
Sampling Rate
0.8
0.60
0.57
0.60
0.53 0.55 0.51 0.56 0.59 0.52 0.49
0.47
0.53
0.49
0.85
0.79
0.81
0.78
0.77 0.77 0.76 0.76 0.77 0.76 0.74
0.73
0.75
0.78
0.9
0.93
0.92
0.91
0.92 0.92 0.93 0.91
0.90
0.90
0.88
0.87
0.85
0.81
0.95
0.98
0.98
0.97
0.97
0.66
1.0
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.81
0.72
0.53
0.34
0.21
0.11
0.25
0.35
0.4
0.45
0.6
0.65
RIP Constant
Figure 2: Success rate of the algorithm with different sampling rate p and RIP constant 6.
where we define the tensor multiplication K H' K Ei Hisut Kg & for K E RR
and fourth-order tensor H(' B In addition, since the identity tensor I satisfies the (0, 9)- 2r, condition,
straightforward to prove that the function fe satisfies the (6, 22)-R22P2222 2r:27 condition with 8 = 1/(2c - 1) for all c 2 1.
We choose the problem size be 10 and 5. The regularization parameters = 100. The set of sampling rates and Q2-IPP constants are
10 and
p E (0.7,0.75.... 0.75....... 0.95, 1.0}, å E (0.2,0.25,... 0.75, 0.8}.
We solve each problem instance by the Burer-Monterio factorization and the perturbed accelerated gradient descent descent algorithm [23], where the constant step size is 0.007/c. We generate 100 independent problem instances and compute the success rate of the gradient descent algorithm with random initialization. We say that the algorithm successfully solves the instance if the generalization error |UU* || is less than 10-3 If this condition fails, means that the algorithm is stuck at spurious local solution.
The results are plotted in Figure 2. We can from the figure that the optimization complexity grows when 8 becomes smaller and when p becomes larger. This result shows that the Q--IP condition plays important role in characterizing the optimization complexity of problem (12). To be more concrete, we expect that an upper bound on the Q-RIP constant will be able to guarantee the benign optimization landscape of problem (12). Moreover, the result is consistent with the results for the matrix sensing problem and the matrix completion problem. Furthermore, we can see that when the Q-RIP constant is smaller than 1/2, the success rate has stronger correlation with p than 8. This observation is also reflected in Theorem 1, where the lower bound on the sampling rate is on the same order as those in the existing works [18, 17] if 5 is upper bounded. For the cases when p close to 1 and is larger than 0.5, the success rate is better than the case when p = 1. One possible explanation for this phenomenon is that the loss function fo has multiple global minima when the sampling rate is smaller than 1. Instead of converging to spurious local solution, the implicit regularization [26] makes the perturbed gradient descent algorithm more likely to converge the global solution with the "minimal complexity", which is likely the ground truth VM*VT. If the sampling rate is much smaller than 1, the number of spurious local minima will increase and the perturbed gradient descent algorithm may stuck at spurious local minima and fail to converge to the ground truth.
5 Conclusion
In this work, we provide the first theoretical analysis of the MSoG problem. A new notion, dubbed as the Q-RIP condition, is proposed and shown to be useful in characterizing the optimization complexity of the MSoG problem. Using an improved incoherence regularizer, we proved the polynomial global convergence of saddle-avoiding methods under the Q-RIP condition and the incoherence condition. The bounds on the sampling rate and the Ω-RIP constant are state-of-the-art up to constant. Moreover, we showed that our bound on the Q-RIP condition is tight (up to constant). Future works include improving the upper bound on the Q-RIP constant and the lower bound on the sampling rate.
10

---

References
[1] Ahn, K., Suarez, F:: Riemannian perspective matrix factorization. arXiv preprint arXiv:2102.00937 (2021)
[2] Allen-Zhu, Z., Li, Y:: Neon2: Finding local minima via first-order oracles. Advances Neural
Information Processing Systems 31 (2018)
[3] Bhojanapalli, S., Jain, P.: Universal matrix completion. In: International Conference on Machine Learning, pp. 1881-1889. PMLR (2014)
[4] Bi, Y., Lavaei, J.: On the absence of spurious local minima in nonlinear low-rank matrix recovery problems. In: International Conference on Artificial Intelligence and Statistics, pp. 379-387. PMLR (2021)
[5] Bi, Y., Zhang, H., Lavaei, J.: Local and global linear convergence of general low-rank matrix recovery problems. In: Proceedings of 36th AAAI Conference on Artificial Intelligence (AAAI,, Vancouver, Canada, pp. 1-9 (2022)
[6] Burer, S., Monteiro, R.D.: A nonlinear programming algorithm for solving semidefinite pro- grams via low-rank factorization. Mathematical Programming 95(2), 329-357 (2003)
[7] Candès, E.J., Li. X., Ma, Y., Wright, J.: Robust principal component analysis? Journal of the
ACM (JACM) 58(3). 1-37 (2011)
[8] Candes, E.J., Li, X., Soltanolkotabi, M.: Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions Information Theory 61(4), 1985-2007 (2015)
[9] Candes, E.J., Plan, Y.: Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Transactions on Information Theory 57(4), 2342-222 2359 (2011)
[10] Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Foundations of Computational mathematics 96)) 717-772 (2009)
[11] Candès, E.J., Tao, T.: The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory 56(5), 2053-2080 (2010)
[12] Cartis, C., Gould, N.I., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained
optimization. part i: motivation, convergence and numerical results. Mathematical Programming 127(2), 245-2955555 (2011)
[13] Chen, J., Liu, D., Li, X.: Nonconvex rectangular matrix completion via gradient descent without f2.00 regularization. IEEE Transactions on Information Theory 66(9). 5806-5841 (2020)
[14] Chen, Y., Chi, Y., Fan, J., Ma, C.: Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming 176(1), 5-37 (2019)
[15] Chi, Y., Lu, Y.M., Chen, Y.: Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing 67(20), 5239 5269 (2019)
[16] Chou, H.H., Gieshoff, C., Maly, J., Rauhut, H.: Gradient descent for deep matrix factorization:
Dynamics and implicit bias towards low rank. arXiv preprint arXiv:201 1..220111137777 11772 (2020)
[17) Ge, R., Jin, C., Zheng, Y.: No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In: International Conference Machine Learning, pp. 1233-1242, PMLR (2017)
[18] Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum. Advances in Neural Information Processing Systems pp. 2981-2980 (2016)
[19] Hou, T.Y., Li, 7.,, Zhang, Z.: Fast global convergence for low-rank matrix recovery via rieman- nian gradient descent with random initialization. arXiv preprint arXiv:2012.1545 (2020)
[20] Jain, P., Meka, R., Dhillon, I.: Guaranteed rank minimization via singular value projection.
Advances in Neural Information Processing Systems 23 (2010)
[21] Jain, P., Netrapalli, P., Sanghavi, S.: Low-rank matrix completion using alternating minimization.
In: Proceedings of the forty-fifth annual ACM symposium Theory of computing, pp. 665-674 (2013) [22] Jin, C., Ge, R., Netrapalli, P., Kakade, S.M., Jordan, M.I.: How to escape saddle points efficiently. In: International Conference on Machine Learning, pp. 1724-1732, PMLR (2017)
11

---

[23] Jin, C., Netrapalli, P., Jordan, M.I.: Accelerated gradient descent escapes saddle points faster than gradient descent. In: Conference On Learning Theory, pp. 1042-1085. PMLR (2018)
[24] Jin, M., Lavaei, J., Sojoudi, S., Baldick, R.:
Boundary defense against eyber threat for power system state estimation. IEEE Transactions on Information Forensics and Security 16, 1752- 1767 (2020)
[25] Király, F.J., Theran, L.. Tomioka, R.: The algebraic combinatorial approach for low-rank matrix completion. J. Mach. Learn. Res. 16(1), 1391-1436 (2015)
[26] Li, Y., Ma, T., Zhang, H.: Algorithmic regularization in over-pas perr-aaaeterizedd matrix sensing and neural networks with quadratic activations. In: Conference On Learning Theory, pp. 2-47.
PMLR (2018)
[27] Luo, Y., Li, X., Zhang, A.R.: Nonconvex factorization and manifold formulations are almost equivalent in low-rank matrix optimization. arXiv preprint arXiv:2108.0171 (2021)
[28] Netrapalli, P., Jain, P., Sanghavi, S.: Phase retrieval using alternating minimization. Advances in Neural Information Processing Systems 26 (2013)
[29] Netrapalli, P., UN, N., Sanghavi, S., Anandkumar, A., Jain, P.: Non-convex robust pca. Advances in Neural Information Processing Systems 27 (2014)
[30] Pimentel-Alarcee D.L., D.,., Boston, N., Nowak, R.D.: A characterization of deterministic sampling
patterns for low-rank matrix completion. IEEE Journal of Selected Topics in Signal Processing
10(4), 623-636 (2016)
[31] Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review 52(3), 471-501 (2010)
[32] Stöger, D., Soltanolkotabi, M.: Small random initialization is akin spectral learning: Opti- mization and generalization guarantees for overparameterized low-rank matrix reconstruction. Advances in Neural Information Processing Systems 34 (2021)
[33] Sun, J.. Qu Q.. Wright, J.: A geometric analysis of phase retrieval. Foundations of Computa- tional Mathematics 18(5), 1131-1198 (2018)
[34] Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M.. Recht, B.: Low-rank solutions of linear matrix equations via procrustes flow. In: International Conference on Machine Learning, pp. 964-973. PMLR (2016)
[35] Wei, K., Cai, J.F., Chan, T.F.,, Leung, S.: Guarantees of riemannian optimization for low rank matrix recovery. SIAM Journal on Matrix Analysis and Applications 37(3), 1198-1222 (2016)
[36] Wei, K., Cai, J.F., Chan, T.F., Leung, S.: Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems & Imaging 14(2) (2020)
[37] Yi, X., Park, D., Chen, Y.. Caramanis, C.: Fast algorithms for robust pea via gradient descent. Advances in neural information processing systems 29 (2016)
[38] Zhang, H., Bi, Y., Lavaei, J.: General low-rank matrix optimization: Geometric analysis and
sharper bounds. Advances in Neural Information Processing Systems 34 (2021)
[39] Zhang, R. Y., Lavaei. J., Baldick, R.: Spurious local minima in power system state estimation.
IEFE transactions on control of network systems 6(3), 1086-1096 (2019)
[40] Zhang, R. Y., Sojoudi, S., Lavaei, J.: Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery. J. Mach. Lear. Res. 20(114), 1-34 (2019)
[41] Zheng, Q. Lafferty, J.: A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. In: Proceedings of the 28th International Conference Neural Information Processing Systems- Volume 1, pp. 109-117 (2015)
[42] Zhu, Z., Li, Q., Tang, G., Wakin, M.B.: Global optimality in low-rank matrix optimization. IEEE Transactions on Signal Processing 66(13), 3614-3628 (2018)
A Acknowledgements
This work was supported by grants from AFOSR, ARO, ONR, and NSF Haixiang Zhang was supported by the Two Sigma Ph.D. Fellowship.
12


Reviews:
[{"review_id": "tsU6o0NYnC", "reviewer": "Reviewer_xgrK", "summary": "This paper considers a novelly proposed problem of matrix sensing over graphs (MSoG), which is a general case of matrix completion and matrix sensing problems. It proposes a novel variant of RIP condition named Ω-RIP condition and analyze the optimization landscape of MSoG problem. With an improved regularizer of the incoherence, it proves that the strict saddle property holds for the MSoG problem with high probability under the incoherence condition and the Ω-RIP condition.", "questions": "1. What is the intuition of the design of incoherence regularizer? Whether and how it contributes to the convenience of the analysis and the improvement of sampling rate bound, compared with other regularizers?\n\n2. Is the theoretic result general enough to applicate in some specific cases such as the landscape of power state estimation? Does the special incoherence regularizer affect the generalization?\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: This paper proposes a novel problem formulation of MSoG, and gives the first theoretical result on the optimization landscape of this problem, which relies on its novelly proposed Ω-RIP condition and incoherence regularizer.\n\nQuality: This paper provides rigorous theoretical analysis and strong theoretical results. The result is well supported by the numerical experiments.\n\nClarity: The logic of this article is rigorous, and the focus and contribution are clear.", "weaknesses": "1. The writing of this paper can be more clear. Taking section 1.3,1.4 as an example, it maybe more well organized to merge the motivating example and problem formulation in one section, the description of motivating example can be more tidy, and the theoretical result can be delayed to the section 2 after the presentation of  Ω-RIP condition. The nesting problem also exists in the presentation of numerical result. \n\n2. The applications of MSoG problem can be stated more detailedly. For example, it will be more motivated to detailedly model the power state estimation as one case of MSoG problem. \n\n3. The intuitions and high-level ideas of the formulation and analysis can be more detailed, for example, the intuition of the design of incoherence regularizer and what it contributes to the convenience of the analysis. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **The writing of this paper can be more clear:** we would like to thank the reviewer for the constructive comment. We will follow the reviewer's suggestion to revise the presentation of the paper.\n\n\n2. **Application of MSoG problem:** please see the \"application of MSoG problem\" section in the global response.\n\n\n3. **The intuitions and high-level ideas of the formulation and analysis:** we would like to thank the reviewer for the helpful comment. Let $\\mathcal{R}\\subset \\mathbb{R}^{n\\times r}$ be the set of $U$ such that $\\|e_i^T U\\|_F = O(\\alpha)$ for all $i$. The intuition behind the design of the incoherence regularizer is to ensure that every $\\epsilon$-approximate first-order critical point of problem (12) must lie in set $\\mathcal{R}$. More specifically, the regularizer ensures that (i) outside $\\mathcal{R}$, the gradient of the regularizer is large enough such that any $\\epsilon$-approximate first-order critical point of problem (12) must lie in $\\mathcal{R}$, (ii) the regularizer, and thus its Hessian matrix, has a sufficiently small contribution to the objective function of problem (12) in $\\mathcal{R}$ and (iii) the regularizer is twice differentiable. Please see Lemmas 1-2 for point (i) and Lemma 5 for point (ii). Therefore, using points (i) and (ii), we know that every $\\epsilon$-approximate first-order critical point $U$ of problem (12) must lie in $\\mathcal{R}$ and the landscape around $U$ can be approximated by that of the first term in the objective function (namely, $(1/p) \\cdot h(U)$). Now, it remains show that $h(U)$ has a benign landscape in $\\mathcal{R}$, which we established by a proof that is similar but considerably more complicated than existing proofs. We will include a more detailed description of high-level ideas behind the proofs and the design of the regularizer in the revised paper.\n\n4. **Application to the power state estimation problem:** please see the \"application of MSoG problem\" and the \"numerical results\" sections in the global response for the theoretical discussion and the numerical results of the power state estimation problem, respectively.\n\n5. **Does the special incoherence regularizer affect the generalization:** we would like to thank the reviewer for proposing the question. Since the regularizer can be evaluated in closed-form, our results can be applied to the power state estimation problem as long as the parameters $\\alpha$ and $\\lambda$ can be suitably chosen. In addition, we note that most existing works on matrix completion utilized the regularizer in problem (8), which has a similar form as our new regularizer and also faces the problem of choosing the parameters $\\alpha$ and $\\lambda$."}, {"review_id": "24K7TF3U17", "reviewer": "Reviewer_do7X", "summary": "This paper introduces the matrix sensing over graphs (MSoG) problem, which encompasses matrix sensing and matrix completion problems. The paper proposes a non-convex regularized optimization method for this new problem and provides theoretical guarantees for its solvability using the gradient descent algorithm. The theoretical guarantees rely on the incoherence condition and a modified RIP condition introduced in the paper. The paper demonstrates that the suggested method can achieve improved sample complexity compared to existing results in the matrix completion problem.", "questions": "* Why is $c$ multiplied by the threshold in line 262? It seems unnecessary and could affect the experimental result.\n* In Theorem 3, it seems peculiar that the bound on $\\gamma$ decreases as $\\sigma^*_r$ increases. Shouldn't $\\gamma$ increase as $\\sigma^*_r$ increases to better avoid saddle points? Please clarify if I have misunderstood something.\n", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The paper presents a new framework that includes existing matrix sensing and matrix completion problems.\n* The paper introduces a new incoherence regularizer and provides theoretical guarantees for it.", "weaknesses": "* The problem is restricted to cases where the true unknown matrix is positive semidefinite.\n* The presentation is not very reader-friendly. Some notations are used without introduction, such as the condition number in equation (9) and tensor multiplication in the equation following line 246. Additionally, the use of examples defined in Section 3.2 but presented in Section 2 makes it difficult to follow the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **The problem is restricted to cases where the true unknown matrix is positive semi-definite:** we would like to thank the reviewer for pointing out this limitation. In existing literature, there are two different formulations of the matrix completion problem: the positive semi-definite (PSD) case and the asymmetric case. Our work focused on the PSD case, which is formulated as problem (8) for matrix completion and problem (12) for MSoG. In the asymmetric case, the ground truth matrix $M^* \\in \\mathbb{R}^{m\\times n} $ is still assumed to be rank-$r$ but is not required to be PSD. Using the Burer-Monteiro factorization approach, the asymmetric MSoG problem can be formulated as\n$$ \\min_{U\\in\\mathbb{R}^{m\\times r}, V\\in\\mathbb{R}^{n\\times r}}~ \\frac{1}{p} f[(UV^T)_\\Omega;M^*_\\Omega] + \\phi \\|U^TU - V^TV\\|_F^2 + g_1(U) + g_2(V), $$\n\nwhere we define \n\n$$ \ng_{1}(U) := \\sum_{i\\in[m]} \\lambda_1 \\int_{-1}^{1} \\left[ \\left( \\|| e_{i}^{T} U \\||F  + \\alpha_1 y - 10\\alpha_1 \\right)_{+} + 9\\alpha_1 \\right]^4 \\left(1 - |y|\\right)~ dy,\n$$\n\n$$\ng_{2}(U) := \\sum_{i\\in[m]} \\lambda_2 \\int_{-1}^{1} \\left[ \\left( \\|| e_{i}^{T} U \\||F  + \\alpha_2 y - 10\\alpha_2 \\right)_{+} + 9\\alpha_2 \\right]^4 \\left(1 - |y|\\right)~ dy,\n$$\n\nand $\\alpha_1, \\alpha_2, \\lambda_1, \\lambda_2, \\phi > 0$ are constants. \n\nFirst, we note that there are many real-world applications of the MSoG problem that possess a PSD ground truth matrix. For example, the power state estimation problem can be formulated as a PSD MSoG problem. Therefore, a large number of works on the matrix completion problem also focused on the PSD case; see, for example, [17, 18].\n\nAdditionally, although the asymmetric case is more general than the PSD case, the results of the PSD case can be directly extended to the asymmetric case. To be more concrete, suppose that the ground truth matrix can be decomposed into $M^* = U^*(V^*)^T$, where matrices $U^* \\in\\mathbb{R}^{m\\times r}$ and $V^* \\in\\mathbb{R}^{n\\times r}$. We define the matrices\n$$ W^* := \\left(\\begin{array}{cc} U^* \\\\ V^* \\end{array}\\right) \\in \\mathbb{R}^{(m + n) \\times r},\\quad W := \\left(\\begin{array}{cc} U \\\\ V \\end{array}\\right) \\in \\mathbb{R}^{(m + n) \\times r}. $$\nSince\n$$\nWW^T = \\left(\\begin{array}{cc} UU^T & UV^T \\\\ VU^T & VV^T \\end{array}\\right),\\quad \\|U^TU - V^TV\\|_F^2 = \\mathrm{tr}(UU^T\\cdot UU^T) + \\mathrm{tr}(VV^T \\cdot VV^T) - 2\\mathrm{tr}[UV^T \\cdot (UV^T)^T],\n$$\nthe objective function of the asymmetric MSoG problem can be written as a function of $W$ and $W^*$. More importantly, the loss function term $f[(UV^T)_\\Omega;M^*_\\Omega]$ can be written as a function of $WW^T$ and $W^*(W^*)^T$, which are both rank-$r$ PSD matrices. Therefore, the asymmetric MSoG problem can be formulated as a PSD MSoG problem with variable $W$ and ground truth matrix $W^*(W^*)^T$. Then, by a similar analysis as Appendix B of [38] and Appendix B of [17], the theoretical results in Theorem 3 can be directly extended to the asymmetric case with the same bound on $\\delta$ and $p$ up to a constant. We will include the rigorous analysis of the asymmetric case in the revised paper.\n\n\n2. **The presentation is not very reader-friendly:** we would like to thank the reviewer for the constructive comment. We will follow the reviewer's comment to revise the presentation of the paper.\n\n3. **The threshold in line 262:** we would like to thank the reviewer for pointing out this issue. Following the reviewer's suggestion, we have changed the threshold to 1e-3 and re-implemented the gradient descent algorithm. The updated results are included in the PDF file. Although the success rates are slightly different due to the randomness of the initialization, we can observe exactly the same pattern as the original experiment. We are happy to share the reproducible code after the review process.\n\n4. **Relation between $\\gamma$ and $\\sigma_{r}^{*}$:** we would like to thank the reviewer for pointing out the point. We note that the small constant $\\epsilon$ may also depend on $\\sigma_r^*$. Therefore, it is hard to estimate the relation between $\\gamma$ and $\\sigma_{r}^{*}$ from Theorem 3. A similar bound is also derived in Theorem 4 of [17].\n\n\nSince our response is able to resolve all of the reviewer's concerns, we hope that the reviewer could kindly consider increasing the rating."}, {"review_id": "aCWz7g8Ta1", "reviewer": "Reviewer_jSiy", "summary": "In this work, the author introduced a problem which they call matrix sensing over graphs. It is sort of a generalized version of PSD matrix completion problem. To fit in the new problem formulation, the author introduced a RIP type condition and showed that it characterizes the problem complexity. The major contribution of this work is that by properly defining a regularizer and under low incoherence condition, the author is able to show that strict saddle property holds for the problem with high probability which implies that the solution of saddle avoiding method converges to the global minimizer. By constructing a counterexample, the author showed that the bound achieved is tight up to a constant factor.", "questions": "1. For the sampling rate, I noticed that the term associated with rank is $r^3$. I am wondering is there any chance that this can be reduced to $r$. If not, what is the major challenge here.\n\n2. Another questions is that what if $M^*$ is not PSD. Can you achieve similar results?", "limitations": "Please see the weakness section.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Overall, I think the introduced problem is interesting in theory:\n\n1. The author did a good job comparing the existing results/conditions of matrix sensing problem with results they introduced. This helped the reviewer to easily understand their intuition behind their ideas;\n\n2. Given the tightness of the bounds achieved, I think the theoretical results are also strong.", "weaknesses": "As a major weakness, I think the motivation of this work lacks support of applications. I understand it is a theory paper, but it is always good to have some story behind it, especially when the problem formulation is introduced as new and some of the major methods are similar to that in [38]. \n\nOn the other hand, some of the claims in the paper is not so accurate. For instance, the matrix completion problem does not require $M^*$ to be PSD. In some matrix sensing problems, observations come with noise. So the problem studied in this work is not a general version of matrix completion or matrix sensing as claimed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **This work lacks support of applications:** please see the \"Application of MSoG problem\" section in the global response.\n\n2. **Generalization to the case when $M^*$ is not PSD:** we would like to thank the reviewer for the insightful comment. Please see our response point 1 to Reviewer do7X for the discussion on the generalization to the asymmetric (non-PSD) case.\n\n3. **Observations come with noise:** we would like to thank the reviewer for pointing out this issue. We agree with the reviewer that in real-world applications, the observations often come with noise. However, the analysis for the noiseless case is also important in the sense that it can provide insights into the analysis for the noisy case. With a suitable assumption on the noise, it is common that the proofs of the noiseless case can be extended to the noisy case with minor modifications; see the analysis of the noisy matrix sensing problem in the following paper for a straightforward pathway to go from the noise-free case to the noisy case:\n\n\t>Ma, Z., Bi, Y., Lavaei, J., & Sojoudi, S. (2023). Geometric Analysis of Noisy Low-Rank Matrix Recovery in the Exact Parametrized and the Overparametrized Regimes. INFORMS Journal on Optimization.\n\n\tTherefore, although our work focused on the noiseless case, we expect that similar results will hold for the noisy case. We numerically verify this claim for the power state estimation problem in the global response, where the observations are generated with noise.\n\n4. **Relation to [38]:** we would like to thank the reviewer for pointing out this related work. Although this work considers a similar topic as [38], the problem formulation of this work is significantly more general than that in [38]. More specifically, the work [38] only considered the matrix sensing problem, namely, the case when the sampling rate p is equal to 1. Our work is able to deal with the more general case when the sampling rate is (considerably) smaller than 1. As a result, we need to include the novel incoherence regularizer in the objective function and we need to use different techniques in the proofs. We will include a more detailed comparison to [38] in the revised paper.\n\n5. **The cubic dependence of the sampling rate on $r$:** we would like to thank the reviewer for the helpful comment. The $r^3$ dependence in the sampling rate is inevitable using our current proofs. The major challenge is in the concentration inequality in the proof of Lemma 4. The sampling rate needs to be large enough to guarantee that $\\|X_\\Omega\\|_F^2$ is close to $p\\|X\\|_F^2$ for certain matrix $X$. Moreover, to the best of authors' knowledge, for the matrix completion problem via the Burer-Monteiro factorization, the best dependence of the sampling rate on $r$ is $r^2$, which is derived in [13]. However, their results contain a much higher order of dependence on the condition number $\\kappa^*$, and the MSoG problem is more general than the matrix completion problem and their results cannot be directly applied to the MSoG problem. We will include a more detailed discussion in the revised paper.\n\n\nSince our response is able to resolve all of the reviewer's concerns, we hope that the reviewer could kindly consider increasing the rating."}, {"review_id": "cSBO9kD9GF", "reviewer": "Reviewer_S3ob", "summary": "This work is novel in a sense of studying matrix sensing over graphs - and provides the first theoretical results on the optimization landscape of the MSoG problem - and intruduce a condition to characterize the optimization complexity", "questions": "-", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Its a theoretical work and ideas are nice, and it generalize the matrix completion problem and builds the necessary theory for it such as \\Omega-Rip condition. The matthematical analysis seem to be complete", "weaknesses": "real life applications and more experiments \n\n** after rebuttal - i will change my score to 6- but it would be nice to show experiments / numerical results on Power State Estimation problem contained in the paper to argue the applicability better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Real life applications and more experiments: we would like to thank the reviewer for the comment. We discussed the power state estimation problem and the numerical results the \"application of MSoG problem\" and the \"numerical results\" sections in the global response, respectively. \n\nSince our response is able to resolve all of the reviewer's concerns, we hope that the reviewer could kindly consider increasing the rating."}]

Author rebuttal:
1. **Application of MSoG problem:** we show that the power state estimation problem [24,39] can be formulated as the MSoG problem (12). This is the most important data-analysis problem for power systems and it is solved every 5-15 minutes in practice using heuristic methods with little theoretical guarantees. Several major blackouts were attributed to the failure of solving this problem. Consider an $N$-bus power system associated with an undirected graph $G=(V, E)$, where $V=\{1,\dots,N\}$ is the set of nodes (buses) and $E \subset V\times V$ is the set of edges (lines). An edge $(k, \ell)$ belongs to $E$ if and only if there is a line connecting buses $k$ and $\ell$. The state of the power system is characterized by the voltage phasors $ v \in \mathbb{C}^N$. Our goal is to recover the voltage phasors via measurements on the voltage magnitude and the active power flow over each line. Suppose that $v = x + \mathbf{i} y$ for $x,y\in\mathbb{R}^N$. Define
$$ z := \left( \begin{array}{cc} x \\ y \end{array} \right) \in \mathbb{R}^{2N}. $$
- For each bus $k$, the voltage magnitude is defined as $|v_k|^2$, where the magnitude for a complex number $v_k = x_k + \mathbf{i}y_k$ is defined as $|v_k|^2 := x_k^2 + y_k^2$. The voltage magnitude can be written as:
$$ |v_k|^2 = z^T(e_ke_k^T + e_{N+k}e_{N+k}^T) z, $$
where $e_k$ is the $k$-th standard basis of $\mathbb{R}^N$.

- For each line $(k,\ell) \in E$, let $Y_{k\ell}\in\mathbb{C}$ be the admittance of the line. The active power flow from bus $k$ to bus $\ell$ is 
$$ p_{k\ell} = \mathrm{Re}\left( v_k(v_k - v_\ell)^*Y_{k\ell}^* \right), $$
where $z^*$ is the conjugate of complex number $z$. We observe the active power flows $p_{k\ell}$ and $p_{\ell k}$ for all lines $(k,\ell)\in E$. Denote $Y_{k\ell} := P_{k\ell} + \mathbf{i} Q_{k\ell}$ for $P_{k\ell},Q_{k\ell}\in\mathbb{R}$ for all $(k,\ell) \in E$. Then, the active power flow is equal to

$$ p_{k\ell} = z^T\left[ P_{k\ell} \left( e_ke_k^T - e_ke_\ell^T + e_{N+k}e_{N+k}^T - e_{N+k}e_{N+\ell}^T \right)  + Q_{k\ell} \left( e_ke_{N+\ell}^T - e_\ell e_{N+k}^T \right) \right]z. $$

Therefore, these observations can be written as the quadratic form $z M_j z^T$ for matrices $M_1,\dots,M_m\in\mathbb{R}^{2N\times 2N}$, where $m=N+2|E|$ is the number of observations. For each sensing matrix $M_j$, only the diagonal entries and $(k,\ell),(k,\ell+N),(k+N,\ell),(k+N,\ell+N)$ entries for $(k,\ell)\in E$ may be nonzero. In addition, we fix $y_1 = z_{N + 1} = 0$ since a unitary transformation on $v=x+\mathbf{i}y$ will not change the loss function. As a result, the problem is a $(2N-1)$-dimensional rank-$1$ MSoG problem:
$$ \min_{w\in\mathbb{R}^{2N}}~ \sum_{j=1}^m \left\langle M_j, ww^T - zz^T \right\rangle^2,\quad \mathrm{s.t.}~ w_{N+1} = 0. $$
In the numerical results section, we empirically verify that the $(\delta, E)$-$RIP_{2,2}$ condition holds for this power state estimation problem. In practice, the power state estimation problem is solved via local search methods. We provide the first mathematical guarantee on the global convergence of such methods.

2. **Numerical results:** given the number of buses $N$, the power network $G=(V,E)$ is randomly generated by the Erdos-Renyi random graph model with parameter $p\in(0,1]$. The voltage at node $k$ is given by $v_k = x_k + \mathbf{i}y_k$, where $x_k$ and $y_k$ are independent standard normal random variables and $y_1 = 0$. For each line $(k,\ell) \in E$, the admittance of the line $Y_{k\ell}$ is $P_{k\ell} + \mathbf{i} Q_{k\ell}$, where $P_{k\ell}$ and $Q_{k\ell}$ is uniformly randomly chosen from $[0,0.1]$ and $[0.9, 1]$, respectively. We first empirically verify that the $(\delta, E)$-$RIP_{2,2}$ condition holds for this example. We randomly generate $10^4$ rank-$2$ directions $K\in\mathbb{R}^{2N\times 2N}$ and check the curvature of the Hessian matrix of the loss function along direction $K$. Suppose that the maximal and the minimal curvature is $C$ and $c$, respectively. Then, the RIP constant can be estimated to be $\delta \approx (C+c) / (C-c)$. For number of buses $N=25,50,100$ and parameter $p=0.1, 0.25, 0.5, 1.0$, we independently generate $100$ examples and estimate the RIP constant for each example. The maximum of the estimated RIP constant is summarized in the following table. We can see that the $(\delta, E)$-$RIP_{2,2}$ condition holds for all cases and with high probability, the constant is smaller for larger $N$ or larger $p$. Therefore, we expect the RIP constant to be smaller than $1/16$ for larger-scale problems and our theory applies.

| N    			| 25 		| 50 		| 100		|
| -------- 		| ------- 	| ------- 	| ------- 	|
| **p = 0.1**	| 0.81    	| 0.61		| 0.43		|
| **p = 0.25**	| 0.75    	| 0.56		| 0.41		|
| **p = 0.5**	| 0.72    	| 0.55		| 0.39		|
| **p = 1.0**	| 0.69    	| 0.53		| 0.39		|

Next, we apply the gradient descent algorithm with random initialization to solve the power state estimation problem. The initialization point $w_0$ obeys the standard normal distribution and the step size is $0.001$. We say the algorithm successfully finds the global solution $zz^T$ if the test error $\|ww^T - zz^T\|$ is smaller than $10^{-3}$ within $10^4$ iterations. We consider the same choices of $N$ and $p$. For each case, we generate $10$ independent experiments and count the success rate over all experiments. We summarize the success rates in the following table. We can see that the success rate grows with parameter $p$ and estimated RIP constant $\delta$.

| N    			| 25 		| 50 		| 100		|
| -------- 		| ------- 	| ------- 	| ------- 	|
| **p = 0.1**	| 0.0    	| 0.0		| 0.5		|
| **p = 0.25**	| 0.1    	| 0.5		| 0.8		|
| **p = 0.5**	| 0.7    	| 0.7		| 0.9		|
| **p = 1.0**	| 0.8    	| 1.0		| 1.0		|

Due to the time limit, we are not able to consider larger problems in the rebuttal. We will include the discussion of the power state estimation problem, the reproducible code and the numerical results for larger problems in the revised paper.

Meta-review: The paper contains good contributions to both the theory and applications of the MSoG problem. When preparing the camera-ready version, please incorporate the reviewers' comments, particularly on improving the exposition of the technical results.
Decision: Accept (poster)