# Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs

Faniriana Rakoto Endor, Irène Waldspurger

► To cite this version:

Faniriana Rakoto Endor, Irène Waldspurger. Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs. SIAM Journal on Optimization, In press. hal-04797879

HAL Id: hal-04797879

https://hal.science/hal-04797879v1

Submitted on 22 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs

Faniriana Rakoto Endor*; Irène Waldspurger†

CNRS (UMR 7534), Université Paris Dauphine, Inria Mokaplan

## Abstract

We consider MaxCut-type semidefinite programs (SDP) which admit a low rank solution. To numerically leverage the low rank hypothesis, a standard algorithmic approach is the Burer-Monteiro factorization, which allows to significantly reduce the dimensionality of the problem at the cost of its convexity. We give a sharp condition on the conditioning of the Laplacian matrix associated with the SDP under which any second-order critical point of the non-convex problem is a global minimizer. By applying our theorem, we improve on recent results about the correctness of the Burer-Monteiro approach on $Z_2$-synchronization problems.

# 1 Introduction

## 1.1 Presentation of the problem

Semidefinite programs (SDP) are optimization tools that allow the solving and modeling of a variety of problems across applied sciences. A number of problems admits a SDP formulation in combinatorial optimization [Goemans and Williamson, 1995], machine learning

<footnote>* rakotoendor@ceremade.dauphine.fr</footnote>

<footnote>† waldspurger@ceremade.dauphine.fr</footnote>
and data sciences [Lanckriet et al., 2004], statistics and signal processing [Candès, Strohmer, and Voroninski, 2013]. In this paper, we are interested in so-called *MaxCut-type* SDPs:

$$ 
\begin{array}{ll}
\min_{X \in \mathbb{S}^{n \times n}} & - \langle C, X \rangle \\
\text{s.t.} & X \succeq 0 \\
\text{diag}(X) = & \mathbf{1}_n,
\end{array}
\qquad (\text{SDP})
$$

where the operator diag : $\mathbb{R}^{n \times n} \to \mathbb{R}^n$ extracts the diagonal of a square matrix, $\mathbf{1}_n = (1 \dots 1)^T \in \mathbb{R}^n$ and the symmetric matrix $C \in \mathbb{R}^{n \times n}$ is called the *cost matrix*. SDP of this form are especially known to provide precise convex relaxations of MaxCut problems from graph optimization [Goemans and Williamson, 1995]. They can also model problems such as group synchronization, phase retrieval and the Kuramoto model, for particular choices of the cost matrix $C$. Several general methods exist to numerically solve problem (SDP), but they scale poorly with $n$. For instance, interior-point solvers require $O(n^3)$ computations per iteration and $O(n^2)$ to store the variable [Benson, Ye, and Zhang, 2000].

To reduce the computational complexity of solvers, one must exploit the specific properties of the problem at hand, if any. For instance, it may be known in advance that the solution to (SDP) is low-rank: [Pataki, 1998] guarantees that there exists a solution with rank bounded by $\sqrt{2n} + O(1)$ and, when (SDP) is the relaxation of a combinatorial problem, the optimal rank is often much less (see for instance [Candès, Strohmer, and Voroninski, 2013] for a theoretical justification in a particular case, [Journée, Bach, Absil, and Sepulchre, 2010] for a numerical investigation). In this case, it is possible to tackle the problem using its so-called *Burer-Monteiro factorization*. The principle is to factor the variable as $X = VV^T$, for $V \in \mathbb{R}^{n \times p}$, where $p \in \mathbb{N}$ is larger or equal to the rank of the sought solution, and much smaller than $n$. Then, one optimizes over $V$, instead of directly over $X$.

$$ 
\begin{array}{ll}
\min_{V \in \mathbb{R}^{n \times p}} & - \langle C, VV^T \rangle \\
\text{s.t.} & \text{diag}(VV^T) = \mathbf{1}_n.
\end{array}
\qquad (\text{Burer-Monteiro})
$$

The factorized problem reduces the number of variables to $np$ instead of the $O(n^2)$ variables of the initial problem which is computationally advantageous
when $p \ll n$. However, the convexity is lost, so standard solvers are not guaranteed to reach the solution. Still, in practice, solvers oftentimes converge to a global solution $V \in \mathbb{R}^{n \times p}$ of the factorized problem, for which $X = VV^T$ solves the initial problem.

## 1.2 Prior work and our contribution

The main explanation proposed in the literature for the success of standard algorithms at solving (Burer-Monteiro) has been the benign non-convexity of the optimization landscape: it may be that all second-order critical points of (Burer-Monteiro) are global minimizers. Since standard algorithms typically find a second-order critical point [Lee, Panageas, Piliouras, Simchowitz, Jordan, and Recht, 2019], they consequently find a global minimizer.

Literature suggests that, the greater $p$ is, the more likely it is that the landscape is benign. More precisely, when $p \ge \sqrt{2n} + O(1)$, the landscape of the factorized problem is benign for almost all cost matrices $C$ [Boumal, Voroninski, and Bandeira, 2020]. This property is even true for all cost matrices if $p > \frac{n}{2}$ [Boumal, Voroninski, and Bandeira, 2020, Cor. 5.11], while it can fail for a zero Lebesgue measure subset of cost matrices if $\sqrt{2n} + O(1) \le p \le \frac{n}{2}$ [O'Carroll, Srinivas, and Vijayaraghavan, 2022]. However, when $p \le \sqrt{2n} + O(1)$, there is a subset of cost matrices $C$ of positive Lebesgue measure for which (Burer-Monteiro) admits non-optimal critical points [Waldspurger and Waters, 2020] (with a gap to the optimal value scaling in $O(1/p)$) [Mei, Misiakiewicz, Montanari, and Oliveira, 2017], but strictly positive).

Nonetheless, in practice, standard algorithms seem to find a solution of (Burer-Monteiro) below the threshold $\sqrt{2n}$, suggesting that, maybe, the set of cost matrices with a non-optimal critical point is small, and “typical” cost matrices do not belong to it. Therefore, researchers have tried to find properties on $C$ guaranteeing that $C$ is not in this bad set, focusing for the moment on the setting where the minimizer of (SDP) has rank 1. The articles [McRae and Boumal, 2024] and [McRae, Abdalla, Bandeira, and Boumal, 2024] discuss matrices $C$ with a specific structure, motivated by synchronization problems. They prove that the landscape of (Burer-Monteiro) is benign under conditions which involve eigenvalues of the subcomponents of $C$. [Ling, 2023] considers general matrices $C$ and shows that the landscape is benign if the condition number of the associated Laplacian matrix is smaller
than $\frac{p-1}{2}$. For important instances of (SDP) (mainly $\mathbb{Z}_2$-synchronization with additive Gaussian noise and multiplicative Bernoulli noise), these recent results show that standard algorithms, applied to (Burer-Monteiro), retrieve the rank 1 solution under close to optimal conditions.

**Main result** Our main result is a sufficient condition on the condition number of a certain matrix related to (SDP) which ensures that the landscape of (Burer-Monteiro) is benign. This tightens the result of [Ling, 2023]: we show that if the condition number of the Laplacian matrix associated with $C$ is less than $p$ (instead of $\frac{p-1}{2}$ in [Ling, 2023]), then the landscape of (Burer-Monteiro) is benign. Furthermore, we show that this bound is essentially optimal. Finally, by applying our theorem to $\mathbb{Z}_2$-synchronization, we also improve on the applications of [McRae, Abdalla, Bandeira, and Boumal, 2024] and [Ling, 2023].

## 1.3 Structure of the paper

In section 2, we present our main result and, in section 3, its application to $\mathbb{Z}_2$-synchronization with additive Gaussian noise and Bernoulli noise. In section 4 we provide the proof of the main theorem, without the technical details that we leave for the appendix.

## 1.4 Notation

Throughout this paper, $\mathbb{S}^{n \times n}$ is the set of symmetric $n \times n$ matrices. We write $X \succeq 0$ if $X$ is a positive semidefinite matrix. For a matrix $X \in \mathbb{R}^{n \times n}$, when it makes sense, $\lambda_1(X) \le \lambda_2(X) \le \cdots \le \lambda_n(X)$ are the eigenvalues of $X$ in ascending order. For matrices $X, Y \in \mathbb{R}^{n \times m}$, $\langle X, Y \rangle = \text{Tr}(X^T Y)$ is the standard inner product on $\mathbb{R}^{n \times m}$, $X \odot Y$ is the entry-wise or Hadamard product, $\|X\|_F = \sqrt{\langle X, X \rangle}$ is the Frobenius norm on $\mathbb{R}^{n \times m}$, $X_i: \in \mathbb{R}^m$ is the $i$-th row of $X$ and $X_{;j} \in \mathbb{R}^n$ is the $j$-th column of $X$. For $X \in \mathbb{R}^{n \times m}$, $\|X\|$ is the spectral or $\ell_2$ operator norm of $X$ and $\|X\|_\infty$ is the $\ell_\infty$-norm of $X$ i.e. the maximum entry in absolute value. The operator ddiag : $\mathbb{R}^{n \times n} \to \mathbb{S}^{n \times n}$ zeroes out all the non diagonal entries of a matrix and for any vector $x \in \mathbb{R}^n$, diag($x$) $\in \mathbb{S}^{n \times n}$ is the diagonal matrix with the coordinates of $x$ on the diagonal. For any $x, y \in \mathbb{R}$ the notation $x \lesssim y$ means that there exists a constant $C > 0$ that does not depend on any parameter, such that $x \le Cy$. For any vector $x \in \mathbb{R}^n$, $\|x\|$ is the Euclidean norm of $x$, $\mathbf{1}_n = (1 \dots 1)^T \in \mathbb{R}^n$.
## 2 Main result

Problem (Burer-Monteiro) can be seen as minimizing a function over the product of spheres

$$ \begin{aligned} \{V \in \mathbb{R}^{n \times p}, \operatorname{diag}(VV^T) = \mathbf{1}_n\} &= \{V \in \mathbb{R}^{n \times p}, \|V_1\| = \cdots = \|V_n\| = 1\} \\ &= (\mathbb{S}^{p-1})^n. \end{aligned} $$

The set $(\mathbb{S}^{p-1})^n$ can be endowed with the Riemannian structure inherited from that of $\mathbb{R}^{n \times p}$. It is then a Riemannian manifold.

**Definition 2.1.** Let $\mathcal{M}$ be a Riemannian manifold and $f: \mathcal{M} \to \mathbb{R}$ a twice-differentiable function. For any $x \in \mathcal{M}$, we say that

* $x$ is a first-order critical point if $\nabla f(x) = 0$, where $\nabla f(x)$ is the Riemannian gradient of $f$ at $x$ (which belongs to the tangent space $T_x \mathcal{M}$);

* $x$ is a second-order critical point (SOCP) if $\nabla f(x) = 0$ and Hess $f(x) \succeq 0$, where Hess $f(x)$ is the Riemannian Hessian of $f$ at $x$ (which is a bilinear map on $T_x \mathcal{M}$).

More detailed explanations of these concepts can be found in [Absil, 2008] or [Boumal, 2023].

To set up the statement of the theorem, let $x \in \{\pm 1\}^n$ be a binary vector. An important quantity associated with problem (SDP) is the Laplacian matrix, defined as

$$ L = \operatorname{ddiag}(Cxx^T) - C. \qquad (1) $$

Note that, by construction, $Lx = 0$. Standard duality theory shows that $xx^T$ is a (rank 1) solution to (SDP) if $L \succeq 0$; this solution is unique if, in addition, $\lambda_2(L) > 0$.

Our theorem gives a sufficient condition on the condition number $\frac{\lambda_n(L)}{\lambda_2(L)}$ of the Laplacian matrix under which all SOCP of (Burer-Monteiro) are optimal.

**Theorem 2.2.** Fix a cost matrix $C \in \mathbb{S}^{n \times n}$ and a binary vector $x \in \{\pm 1\}^n$. Assume that $L \succeq 0$ and $\lambda_2(L) > 0$. If

$$ p > \frac{\lambda_n(L)}{\lambda_2(L)}, $$

then any second-order critical point $V$ of (Burer-Monteiro) is a global minimizer, i.e. $VV^T = xx^T$.
In particular, if the condition number of the Laplacian matrix is upper bounded by $p$, then standard optimization algorithms converge to a global minimum of the factorized problem. This result is purely deterministic and holds for a variety of cost matrices $C$ without assumption on their structure. It improves on [Ling, 2023, Theorem 2.1], which reads as follows.

**Theorem ([Ling, 2023]).** Under the same assumptions as in theorem 2.2, assume that

$$p \geq \frac{2\lambda_n(\mathbf{L})}{\lambda_2(\mathbf{L})} + 1.$$

Then all second-order critical points of (Burer-Monteiro) are optimal.

Our results are similar in nature but the proofs are quite different Moreover, our bound is optimal in the sense of the following property, the proof of which can be found in the appendix A.1.

**Proposition 2.3.** Let $p \geq 2$ and $n \geq 6p$. If $n$ or $p$ is even, there exist $C \in \mathbb{S}^{n \times n}$, $\mathbf{x} \in \{\pm 1\}^n$ satisfying the assumptions of theorem 2.2 such that $\frac{\lambda_n(\mathbf{L})}{\lambda_2(\mathbf{L})} = p$ and problem (Burer-Monteiro) admits a non optimal second-order critical point.

# 3 Application

## 3.1 $\mathbb{Z}_2$-synchronization with additive Gaussian noise

Here, we consider the $\mathbb{Z}_2$-synchronization problem with additive Gaussian noise which consists in reconstructing a binary vector $\mathbf{x}$ with coordinates $x_1, \dots, x_n \in \{\pm 1\}$ from noisy measurements $x_i x_j + \sigma W_{ij}$ where $W_{ij} = W_{ji} \sim \mathcal{N}(0, 1)$, $W_{ii} = 0$ and $\sigma > 0$. This problem admits a relaxation of the form (SDP) with cost matrix

$$C = \mathbf{x}\mathbf{x}^T + \sigma W. \qquad (2)$$

[Bandeira, 2018] shows that this SDP relaxation retrieves the rank 1 matrix $\mathbf{x}\mathbf{x}^T$ when $\sigma < \sqrt{\frac{n}{(2+\varepsilon)\log n}}$ (for any $\varepsilon > 0$), and explains that, for larger values of $\sigma$, no algorithm is expected to succeed. Using our theorem 2.2, we can show that the more tractable Burer-Monteiro factorization reaches the same threshold up to a multiplicative factor which goes to 1 when $p$ becomes large.
**Corollary 3.1.** We consider the $Z_2$-synchronization problem with Gaussian noise, where the cost matrix is defined by (2). For any $\varepsilon > 0$ and large enough $n$, if

$$ \sigma < \frac{p-1}{p+1} \sqrt{\frac{n}{(2+\varepsilon) \log n}}, \qquad (3) $$

then all second-order critical points of (Burer-Monteiro) are optimal with probability at least $1 - n^{-\varepsilon/4} - 4e^{-n}$.

This corollary is proved in A.2. It improves on [Ling, 2023, corollary 2.4], which reads as follows.

**Corollary ([Ling, 2023]).** Under the same conditions as corollary 3.1, if

$$ \sigma < \frac{p-3}{4(p+1)} \sqrt{\frac{n}{\log n}}, $$

then all SOCP of the factorized problem (Burer-Monteiro) are optimal with high probability.

Indeed, our result holds for $p$ as small as 2 whereas theirs needs $p \ge 4$. In the large $p$ limit, our bound is better by a constant multiplicative factor. We also improve on [McRae, Abdalla, Bandeira, and Boumal, 2024, Corollary 1].

**Corollary ([McRae, Abdalla, Bandeira, and Boumal, 2024]).** For $n \ge 2$, $\varepsilon > 0$, if the noise level of cost matrix (2) satisfies

$$ \sigma \le \frac{p-3}{p-1} \sqrt{\frac{n}{(2+\varepsilon) \log n}}, $$

then all second-order critical points of (Burer-Monteiro) are optimal with probability $\to 1$ as $n \to \infty$.

The improvement lies in the fact that our result does no prohibit us from taking $p$ as small as 2. The proof is built upon tools used both in [Ling, 2023] and [McRae, Abdalla, Bandeira, and Boumal, 2024].

## 3.2 $Z_2$-synchronization with Bernoulli noise

The problem of $Z_2$-synchronization with Bernoulli noise consists in recovering a binary vector $\boldsymbol{x} \in \{\pm 1\}^n$ from its pairwise observations $x_i x_j$, where the
sign of $x_ix_j$ is flipped with probability $\frac{1-\delta}{2}$, for some $0 < \delta \le 1$. In other words, when $\delta$ is close to 1, the signs are not flipped and when $\delta$ is close to 0, the observations are often corrupted. This leads to a problem of the form (SDP), with

$$ C_{ij} = \begin{cases} x_ix_j & \text{with probability } \frac{1+\delta}{2} \text{ if } i \neq j, \\ -x_ix_j & \text{with probability } \frac{1-\delta}{2} \text{ if } i \neq j, \\ 0 & \text{if } i = j. \end{cases} \quad (4) $$

Our result gives a condition on $\delta$ under which the landscape of the factorized problem (Burer-Monteiro) is benign.

**Corollary 3.2.** We consider the $\mathbb{Z}_2$-synchronization problem with Bernoulli noise of parameter $0 < \delta \le 1$, where the cost matrix is defined by (4). For any $\varepsilon > 0$ and large enough $n$, if

$$ \delta > \frac{p+1}{p-1} \sqrt{\frac{(2+\varepsilon) \log n}{n}}, \quad (5) $$

then all second-order critical points of (Burer-Monteiro) are optimal with probability at least $1 - n^{-3} - n^{-\frac{\varepsilon}{3}}$.

The proof of this corollary is in A.2. This corollary is an improvement on [McRae, Abdalla, Bandeira, and Boumal, 2024, Theorem 2] in the case where the observations $x_ix_j$ are complete. This theorem reads as follows.

**Theorem** ([McRae, Abdalla, Bandeira, and Boumal, 2024]). Consider the $\mathbb{Z}_2$-synchronization problem with Bernoulli noise for some $0 < \delta \le 1$. Assume that $p \ge 4$ and there exists some $\varepsilon > 0$ such that

$$ \delta > \frac{p-1}{p-3} \sqrt{\frac{(2+\varepsilon) \log n}{n}} $$

Then, with probability $\to 1$ as $n \to \infty$, all second-order points of the factorized problem (Burer-Monteiro) with cost matrix as in (4) are optimal.

First of all, our result does not prevent us from taking $p$ as small as 2. Furthermore, our bound on $\delta$ is better in the regime when $p$ stays constant, but $n$ is large. Our proof of this theorem builds on ideas found in [Ling, 2023] and [McRae, Abdalla, Bandeira, and Boumal, 2024].
# 4 Proof of the main theorem

Throughout the proof, we fix a symmetric cost matrix $C \in \mathbb{S}^{n \times n}$, $x \in \{\pm 1\}^n$ such that the associated Laplacian matrix $L = \text{ddiag}(Cx x^T) - C$ is positive semidefinite and $\lambda_2(L) > 0$.

Moreover, we assume without loss of generality that $x = \mathbf{1}_n$ so that the rank one solution of (SDP) is $X_* = \mathbf{1}_n \mathbf{1}_n^T$ and a solution of the factorized problem is $V_* = \frac{1}{\sqrt{p}} \mathbf{1}_n \mathbf{1}_n^T$. Indeed, if the solution of (SDP) is $x x^T$, then the solutions of the factorized problem are all vectors of the form $V_* = x z^T$ for $z \in \mathbb{S}^{p-1}$ a unit vector. However, the change of variable $V \mapsto \text{diag}(x)V$ does not affect the landscape of the factorized problem and changes solutions into $V_* = \mathbf{1}_n z^T$. We refer to [McRae and Boumal, 2024] for more information on this change of variable.

Furthermore, note that due to the diagonal constraint, changing the diagonal of the cost matrix does not change the landscape of the problems. As such, we can replace the cost matrix $C$ with

$$C - \text{diag}(C \mathbf{1}_n) = -L$$

and study the problem

$$ \begin{array}{ll} \min_{X \in \mathbb{S}^{n \times n}} & \langle L, X \rangle \\ \text{s.t.} & X \succeq 0 \\ & \text{diag}(X) = \mathbf{1}_n, \end{array} \qquad (6) $$

and its factorized form

$$ \begin{array}{ll} \min_{V \in \mathbb{R}^{n \times p}} & \langle L, VV^T \rangle \\ \text{s.t.} & \text{diag}(VV^T) = \mathbf{1}_n. \end{array} \qquad (7) $$

Similar changes were made in the proofs of [McRae and Boumal, 2024]. Note that, we have by assumption $L \succeq 0$, $L \mathbf{1}_n = 0$ and $\lambda_2(L) > 0$.

## 4.1 Formulas for the gradient and Hessian

Before proving theorem 2.2, we provide explicit formulas for the Riemannian gradient and Hessian of the cost function of (7). First, recall that the tangent space of the manifold $(\mathbb{S}^{p-1})^n$ at $V$ is

$$T_V(\mathbb{S}^{p-1})^n = \{ \dot{V} \in \mathbb{R}^{n \times p} : \text{diag}(\dot{V}V^T) = 0 \},$$
Let $P_{T_V} : \mathbb{R}^{n \times p} \to T_V(\mathbb{S}^{p-1})^n$ be the orthogonal projection onto the tangent space, i.e. $P_V(X) = X - \text{diag}(XV^T)V$ for $X \in \mathbb{R}^{n \times p}$.

The gradient of the objective function in (Burer-Monteiro) at a point $V \in (\mathbb{S}^{p-1})^n$ is

$$2 (\mathbf{L} - \text{diag}(\mathbf{L}V\mathbf{V}^T)) V. \qquad (8)$$

In particular, $V$ is first-order critical if and only if $(\mathbf{L} - \text{diag}(\mathbf{L}V\mathbf{V}^T))V = 0$.

The Hessian at $V$ is

$$\text{Hess}_V : \dot{V} \in T_V(\mathbb{S}^{p-1})^n \mapsto 2P_{T_V}((\mathbf{L} - \text{diag}(\mathbf{L}V\mathbf{V}^T))\dot{V}) \quad (9)$$

If $V$ is first-order critical, it is second-order critical if and only if $\text{Hess}_V$ is positive semidefinite. As $P_{T_V}$ is self-adjoint, that is equivalent to the fact that for all $\dot{V} \in T_V(\mathbb{S}^{p-1})^n$,

$$\langle \text{Hess}_V(\dot{V}), \dot{V} \rangle = 2 \langle (\mathbf{L} - \text{diag}(\mathbf{L}V\mathbf{V}^T)) \dot{V}, \dot{V} \rangle \geq 0.$$

## 4.2 Variational formulation

We prove the contrapositive of the main theorem : if $V$ is a non optimal SOCP then the condition number of the Laplacian matrix is at least $p$. Let us fix $V \in (\mathbb{S}^{p-1})^n$ which is second-order critical, but not optimal for (7), i.e. $VV^T \neq \mathbf{1}_n \mathbf{1}_n^T$.

We denote $v_1, \dots, v_p$ the columns of $V$. If we multiply $V$ by a suitable orthogonal $p \times p$ matrix (which does not change the fact that $V$ is second-order critical for (7)), we can assume that $\langle v_1, \mathbf{1}_n \rangle \geq 0$ and $\langle v_k, \mathbf{1}_n \rangle = 0$ for all $k \geq 2$. This is summarized by the following assumption.

**Assumption 4.1.** For $i = 2, \dots, n$, $(V^T \mathbf{1}_n)_i = \langle v_i, \mathbf{1}_n \rangle = 0$. Moreover, $\langle v_1, \mathbf{1}_n \rangle \geq 0$. In particular,

$$\|V^T \mathbf{1}_n\| = \langle v_1, \mathbf{1}_n \rangle \leq \|v_1\| \|\mathbf{1}_n\| \leq n.$$

Showing that the condition number satisfies $\frac{\lambda_n(\mathbf{L})}{\lambda_2(\mathbf{L})} \geq p$ can be recast as showing that the value of the following optimization problem is at least $p$:
$$
\begin{array}{ll}
\inf_{(L,\mu) \in \mathbb{S}^{n \times n} \times \mathbb{R}^n} & \frac{\lambda_n(L)}{\lambda_2(L)} \\
\text{s.t.} & L \succeq 0, \\
& L \mathbf{1}_n = 0, \\
& \lambda_2(L) > 0, \\
& (L - \operatorname{diag}(\mu))V = 0, \\
& \langle (L - \operatorname{diag}(\mu))\dot{V}, \dot{V} \rangle \ge 0 \text{ for all } \dot{V} \in T_V(\mathbb{S}^{p-1})^n.
\end{array}
\qquad (10)
$$

Indeed, the point $(\mathbf{L}, \hat{\mu})$, with $\hat{\mu} = \operatorname{diag}(\mathbf{L}V\mathbf{V}^T)$ is feasible for the above problem since $V$ is a second-order point of (7). Hence, the condition number of $\mathbf{L}$ is greater than or equal to the optimal value of problem (10).

Note that the first three constraints represent the fact that the semidef-
inite relaxation admits a rank 1 solution and the last two, the first and
second-order optimality conditions on $V$. Problem (10) is not convex, but
we will see that it has the same optimal value as a convex problem.

First, define the set $K$ as the smallest convex cone containing $\{\dot{V}\dot{V}^T, \dot{V} \in T_V(\mathbb{S}^{p-1})^n\}$. The last constraint of problem (10) is equivalent to $\operatorname{diag}(\mu)-L \in K^\circ$, where $K^\circ$ is the polar cone of $K$:

$$
K^{\circ} = \{ M \in \mathbb{S}^{n \times n} : \langle M, N \rangle \le 0 \text{ for all } N \in K \}.
$$

Now, consider the following convex minimization problem:

$$
\begin{array}{ll}
\inf_{(L,\mu) \in \mathbb{S}^{n \times n} \times \mathbb{R}^n} & \lambda_n(P_{\perp}LP_{\perp}) \\
\text{s.t.} & P_{\perp}LP_{\perp} \succeq P_{\perp}, \\
& (P_{\perp}LP_{\perp} - \operatorname{diag}(\mu))V = 0, \\
& \operatorname{diag}(\mu) - P_{\perp}LP_{\perp} \in K^{\circ},
\end{array}
\qquad \text{(Primal)}
$$

where $P_{\perp} = I_n - n^{-1} \mathbf{1}_n \mathbf{1}_n^T$ is the projection matrix on the space orthogonal
to $\mathbf{1}_n$. We have the following two lemmas, whose proofs can be found in A.3.

**Lemma 4.2.** *Problem (10) and problem (Primal) have the same optimal value.*
**Lemma 4.3.** The dual problem of (Primal) is

$$
\begin{array}{ll}
\sup_{(W,Z,H) \in \mathbb{R}^{n \times p} \times \mathbb{S}^{n \times n} \times \mathbb{S}^{n \times n}} & \langle Z, P_{\perp} \rangle \qquad (\text{Dual}) \\
\text{s.t.} & Z \succeq 0, \\
& H \in K, \\
& \operatorname{diag}(WV^T) = \operatorname{diag}(H), \\
& M = P_{\perp} \left( Z + H - \frac{1}{2} (WV^T + VW^T) \right) P_{\perp}, \\
& M \succeq 0, \\
& \operatorname{Tr}(M) \le 1.
\end{array}
$$

By duality, to show that the optimal value of (Primal) is at least $p$, it suffices to exhibit a dual certificate, i.e. a point feasible for (Dual) for which $\langle Z, P_{\perp} \rangle \ge p$.

**4.3 Choice of the dual certificate**

In the following, we aim to find an adequate dual certificate ($W_*, Z_*, H_*$). A
natural choice for $Z_*$ (which ensures $\langle Z_*, P_\perp \rangle = p$) is

$$
Z_* \stackrel{\text{def}}{=} \frac{p}{\langle P_{\perp}, VV^T \rangle} VV^T.
$$

Note that, since $VV^T$ is not colinear to $\mathbf{1}_n \mathbf{1}_n^T$, $\langle P_\perp, VV^T \rangle > 0$ so $Z_*$ is well defined.

To find an adequate $H_*$, denote $e_1, \dots, e_p \in \mathbb{R}^p$ the elements of the canonical basis and observe that for all $i = 1, \dots, p$,

$$
T_i \stackrel{\text{def}}{=} \mathbf{1}_n e_i^T - \operatorname{diag}(Ve_i)V \in T_V(\mathbb{S}^{p-1})^n.
$$

Indeed, $\operatorname{diag}(T_i V^T) = v_i - v_i = 0$.

Therefore, the following matrix belongs to K:

$$
\begin{align*}
\sum_{i=1}^{p} T_i T_i^T &= \sum_{i=1}^{p} (\mathbf{1}_n e_i^T - \operatorname{diag}(Ve_i)V) (\mathbf{1}_n e_i^T - \operatorname{diag}(Ve_i)V)^T \\
&= \sum_{i=1}^{p} (\mathbf{1}_n \mathbf{1}_n^T - \operatorname{diag}(Ve_i)(Ve_i) \mathbf{1}_n^T - \mathbf{1}_n (Ve_i)^T \operatorname{diag}(Ve_i))
\end{align*}
$$
$$
\begin{align*}
&+ \mathrm{diag}(Ve_i)VV^T \mathrm{diag}(Ve_i)) \\
&= p \mathbf{1}_n \mathbf{1}_n^T - \left(\sum_{i=1}^p (Ve_i)^{\odot 2}\right) \mathbf{1}_n^T - \mathbf{1}_n \left(\sum_{i=1}^p (Ve_i)^{\odot 2}\right)^T \\
&\quad + VV^T \odot \sum_{i=1}^p Ve_i e_i^T V \\
&= (p-2) \mathbf{1}_n \mathbf{1}_n^T + (VV^T)^{\odot 2}.
\end{align*}
$$

As a consequence, we can choose $H_*$ of the form

$$
H_* \stackrel{\text{def}}{=} \beta((p-2) \mathbf{1}_n \mathbf{1}_n^T + (VV^T)^{\odot 2}) \text{ for some } \beta \ge 0. \quad (11)
$$

This particular form of $H_*$ can also be found in [McRae and Boumal, 2024]
and [Ling, 2023], although the proof there follows a different path from ours,
as it does not explicitely consider problem (Primal) and its dual.

There is no straightforward choice for $W_*$.
A natural one would be $W_* = \beta(p-1)V$ as it would satisfy the diagonal constraint:

$$
\begin{align*}
\mathrm{diag}(W_* V^T) &= \beta(p-1) \mathbf{1}_n \\
&= \beta((p-2) \mathbf{1}_n + \mathrm{diag}((VV^T)^{\odot 2})) \\
&= \mathrm{diag}(H_*).
\end{align*}
$$

However, numerical experiments suggest that it does not work. Fortunately,
this can be corrected by adding to $\beta(p-1)V$ a matrix proportional to $W'_* =$
$\mathbf{1}_n \mathbf{1}_n^T V + \varepsilon$, for some $\varepsilon \in \mathbb{R}^{n \times p}$ chosen so that $\mathrm{diag}(W'_*V^T) = 0$. We choose
$\varepsilon = -\mathrm{diag}(VV^T \mathbf{1}_n)V$ (so that $W'_* = P_{TV}(\mathbf{1}_n \mathbf{1}_n^T V)$). Under assumption 4.1,

$$
W'_{*} = \langle v_1, \mathbf{1}_n \rangle (\mathbf{1}_n e_1 - \mathrm{diag}(v_1) V),
$$

which suggests the choice

$$
W_* = \beta(p-1)V + \delta(\mathbf{1}_n e_1 - \mathrm{diag}(v_1)V) \text{ for some } \delta \in \mathbb{R}. \quad (12)
$$

4.4 Constraints

The goal now is to find $\beta, \delta$ such that the dual certificate $(W_*, Z_*, H_*)$ defined
in the previous subsection satisfies the constraints of problem (Dual) and
$\langle Z_*, P_\perp \rangle \ge p$.
The definition of $Z_*$ immediately implies

$$ \langle Z_*, P_\perp \rangle = p \text{ and } Z_* \succeq 0. $$

Furthermore, $H_*$ defined in (11) is in $K$ if $\beta \ge 0$, and the definition of $W_*$ ensures that the equality $\mathrm{diag}(W_*V^T) = \mathrm{diag}(H_*)$ holds true. Therefore, we only have to find $\beta, \delta$ such that

$$ \beta \ge 0 \qquad (13a) $$

$$ M_* \succeq 0 \qquad (13b) $$

$$ \mathrm{Tr}(M_*) \le 1, \qquad (13c) $$

where of course $M_* = P_\perp(Z_* + H_* - \frac{1}{2}(W_*V^T + VV^T_*))P_\perp$.

For the positive semidefiniteness of $M_*$, we have the following lemma, proved in A.3.

**Lemma 4.4.** Under assumption 4.1, if $\beta \ge 0$, $M_*$ is positive semidefinite if

$$ \left( \frac{p}{2(p-1) \langle P_{\perp}, VV^T \rangle} \right)^2 \ge \left( \beta - \frac{p}{2(p-1) \langle P_{\perp}, VV^T \rangle} \right)^2 + \left( \frac{\delta}{2\sqrt{p-1}} \right)^2. \qquad (14) $$

Now, the trace of $M_*$ is given by

$$ \begin{aligned} \mathrm{Tr}(M_*) &= \mathrm{Tr}(P_\perp Z_*) + \mathrm{Tr}(P_\perp H_*) - \mathrm{Tr}(P_\perp W_* V^T) \\ &= p + \beta \langle P_\perp, (VV^T)^{\odot 2} \rangle - \mathrm{Tr}(P_\perp(\beta(p-1)VV^T - \delta \mathrm{diag}(v_1)VV^T)) \\ &= \beta \langle P_\perp, (VV^T)^{\odot 2} - (p-1)VV^T \rangle + \delta \langle P_\perp, \mathrm{diag}(v_1)VV^T \rangle + p. \end{aligned} $$

We must therefore find $\beta \ge 0$ and $\delta$ satisfying equation (14) such that

$$ t_1\beta + \frac{t_2\delta}{2\sqrt{p-1}} \ge p-1, \qquad (15) $$

$$ \text{where } t_1 = \langle P_\perp, (p-1)VV^T - (VV^T)^{\odot 2} \rangle \\ \text{and } t_2 = -2\sqrt{p-1} \langle P_\perp, \mathrm{diag}(v_1)VV^T \rangle. $$

We set

$$ \beta = \frac{p}{2(p-1) \langle P_{\perp}, VV^T \rangle} \left( 1 + \frac{t_1}{\sqrt{t_1^2 + t_2^2}} \right), $$
$$ \delta = \frac{p}{\sqrt{p-1} \langle P_{\perp}, VV^T \rangle} \frac{t_2}{\sqrt{t_1^2 + t_2^2}} $$

With this definition, equation (14) is true. It remains to show that equation (15) is also true, which is equivalent to

$$ \sqrt{t_1^2 + t_2^2} \ge \frac{2(p-1)^2 \langle P_{\perp}, VV^T \rangle}{p} - t_1. $$

This inequality is true if $t_1^2 + t_2^2 \ge \left( \frac{2(p-1)^2 \langle P_{\perp}, VV^T \rangle}{p} - t_1 \right)^2$, that is, if

$$ \langle P_{\perp}, \operatorname{diag}(v_1)VV^T \rangle^2 + \frac{(p-1)^2}{p^2} \langle P_{\perp}, VV^T \rangle^2 - \frac{p-1}{p} \langle P_{\perp}, VV^T \rangle \langle P_{\perp}, (VV^T)^{\odot 2} \rangle \ge 0. \quad (16) $$

We observe that

$$ \begin{aligned} \langle P_{\perp}, (VV^T)^{\odot 2} \rangle &= \left\langle I_n - \frac{1}{n} \mathbf{1}_n \mathbf{1}_n^T, (VV^T)^{\odot 2} \right\rangle \\ &= n - \frac{\|VV^T\|_F^2}{n} \end{aligned} \quad (17) $$

$$ = n - \frac{\sum_{i,j=1}^{p} \langle v_i, v_j \rangle^2}{n} $$

$$ \le n - \frac{\sum_{i=1}^{p} \|v_i\|^4}{n} $$

$$ = n - \frac{\|v_1\|^4}{n} - \frac{\sum_{i=2}^{p} \|v_i\|^4}{n} $$

$$ \le n - \frac{\|v_1\|^4}{n} - \frac{(\sum_{i=2}^{p} \|v_i\|^2)^2}{n(p-1)} \quad (18) $$

$$ = n - \frac{\|v_1\|^4}{n} - \frac{(n - \|v_1\|^2)^2}{n(p-1)}. \quad (19) $$

At line (17), we used $\operatorname{diag}(VV^T) = \mathbf{1}_n$. At line (18), we used Cauchy-Schwarz and, at line (19), we used that $\sum_{i=1}^p \|v_i\|^2 = \|V\|_F^2 = \operatorname{Tr}(\operatorname{diag}(VV^T)) = n$.
In addition, from assumption 4.1,

$$ \begin{aligned} \langle P_{\perp}, VV^T \rangle &= \left\langle I_n - \frac{1}{n} \mathbf{1}_n \mathbf{1}_n^T, VV^T \right\rangle \\ &= n - \frac{\langle v_1, \mathbf{1}_n \rangle^2}{n}, \end{aligned} $$

and

$$ \begin{aligned} \langle P_{\perp}, \operatorname{diag}(v_1)VV^T \rangle &= \langle \operatorname{diag}(v_1), VV^T \rangle - \frac{1}{n} \langle \mathbf{1}_n \mathbf{1}_n^T, \operatorname{diag}(v_1)VV^T \rangle \\ &= \langle v_1, \operatorname{diag}(VV^T) \rangle - \frac{1}{n} \langle v_1, VV^T \mathbf{1}_n \rangle \\ &= \langle v_1, \mathbf{1}_n \rangle \left( 1 - \frac{\|v_1\|^2}{n} \right). \end{aligned} $$

We combine the last three equations. They show that the left-hand side of equation (16) can be lower bounded by

$$ \begin{aligned} & \langle v_1, \mathbf{1}_n \rangle^2 \left(1 - \frac{\|v_1\|^2}{n}\right)^2 + \frac{(p-1)^2}{p^2} \left(n - \frac{\langle v_1, \mathbf{1}_n \rangle^2}{n}\right)^2 \\ & - \frac{p-1}{p} \left(n - \frac{\langle v_1, \mathbf{1}_n \rangle^2}{n}\right) \left(n - \frac{\|v_1\|^4}{n} - \frac{(n - \|v_1\|^2)^2}{n(p-1)}\right) \\ & = \|v_1\|^4 - \frac{2}{p} \left( \frac{p-1}{n} \langle v_1, \mathbf{1}_n \rangle^2 + n \right) \|v_1\|^2 \\ & + \frac{1}{p^2} \left( \frac{(p-1)^2}{n^2} \langle v_1, \mathbf{1}_n \rangle^4 + 2(p-1) \langle v_1, \mathbf{1}_n \rangle^2 + n^2 \right) \\ & = \left( \|v_1\|^2 - \frac{1}{p} \left( n + \frac{p-1}{n} \langle v_1, \mathbf{1}_n \rangle^2 \right) \right)^2 \\ & \ge 0. \end{aligned} $$

Equation (16) is therefore true, which concludes.

**Acknowledgements** The authors would like to thank Antonin Chambolle for helpful discussions and feedback for this work. Faniriana Rakoto Endor and Irène Waldspurger have been supported by the French government under management of Agence Nationale de la Recherche as part of the “Investissements d’avenir” program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute).
# A Technical lemmas

## A.1 Proofs of section 2

*Proof of proposition 2.3.* Let us set $\boldsymbol{x} = \mathbf{1}_n$ and let $V \in (\mathbb{S}^{p-1})^n$ be such that

$$V^T \mathbf{1}_n = 0, \qquad (20)$$

$$V^T V = \frac{n}{p} I_p, \qquad (21)$$

$$\langle v_i \odot v_j \odot v_k, \mathbf{1}_n \rangle = 0, \text{ for all } 1 \le i,j,k \le p, \qquad (22)$$

where the $v_i$'s are the columns of $V$. Such matrices $V$ exist at least when $p$ is even or $n$ is; an example is provided at the end of the proof. Now, set

$$C = -(P_V + pP_{V\perp} - pP_1),$$

where $P_V = \frac{p}{n}VV^T$ is the orthogonal projector onto $\text{Range}(V)$, $P_{V\perp} = I_n - \frac{p}{n}VV^T$ the projector onto $\text{Range}(V)^\perp$ and $P_1 = \frac{1}{n}\mathbf{1}_n\mathbf{1}_n^T$ the projector onto $\mathbb{R}\mathbf{1}_n$.

Since $C\mathbf{1}_n = 0$, the Laplacian matrix is $\mathbf{L} = -C = P_V + pP_{V\perp} - pP_1$. Its eigenvalues are 0 (with eigenspace $\mathbb{R}\mathbf{1}_n$), 1 (with eigenspace $\text{Range}(V)$) and $p$ (with eigenspace $(\text{Range}(V) \oplus \mathbb{R}\mathbf{1}_n)^\perp$). Therefore, $\mathbf{L} \succeq 0$, $\lambda_2(\mathbf{L}) > 0$ and its condition number is $p$.

Using (8) and (9), $V$ is second-order optimal if

$$SV = 0, \\ \langle \text{Hess}_V(\dot{V}), \dot{V} \rangle = 2 \langle SV, \dot{V} \rangle \ge 0, \forall \dot{V} \in T_V(\mathbb{S}^{p-1})^{2p}, \qquad (23)$$

where

$$S \stackrel{\text{def}}{=} \mathbf{L} - \text{diag}(\mathbf{L}VV^T) = \mathbf{L} - I_n = (p-1)P_{V\perp} - pP_{\mathbf{1}_n}.$$

It is clear that with this choice of $C$, $LV = V$, hence $SV = 0$. It remains to show that the Hessian is positive semidefinite at $V$. The difficulty stems from the fact that $S$ has a negative eigenvalue: $S\mathbf{1}_n = -\mathbf{1}_n$. We first exhibit a subspace of $T_V(\mathbb{S}^{p-1})^n$ included in $\text{Ker } \text{Hess}_V$. Then, we prove equation (23) by decomposing $\dot{V}$ onto the kernel and its orthogonal.

Note that any matrix of the form

$$\text{diag}(Va)V - \mathbf{1}_n a^T, \qquad (24)$$
with $a \in \mathbb{R}^p$, belongs to $T_V(\mathbb{S}^{p-1})^n$ and to the kernel of $Hess_V$. Indeed, for any $a \in \mathbb{R}^p$,

$$ 
\begin{aligned}
\frac{1}{2} \mathrm{Hess}_V (\mathrm{diag}(Va)V - \mathbf{1}_n a^T) &= P_{TV} (S(\mathrm{diag}(Va)V - \mathbf{1}_n a^T)) \\
&= P_{TV} \left( -\frac{p(p-1)}{n} VV^T \mathrm{diag}(Va)V \right) \\
&\quad + P_{TV} \underbrace{(p-1) \mathrm{diag}(Va)V}_{\in (T_V(\mathbb{S}^{p-1})^n)^\perp} \\
&\quad - P_{TV} ((p-1) \mathbf{1}_n a^T) \\
&\quad - P_{TV} \left( \frac{p}{n} \mathbf{1}_n \mathbf{1}_n^T \mathrm{diag}(Va)V - p \mathbf{1}_n a^T \right) \\
&= P_{TV} \left( -\frac{p(p-1)}{n} VV^T \mathrm{diag}(Va)V \right) \\
&\quad + P_{TV} \left( \mathbf{1}_n a^T - \frac{p}{n} \mathbf{1}_n a^T \underbrace{V^T V}_{= \frac{n}{p} I_n} \right) \\
&= - \left( \frac{p(p-1)}{n} \right) P_{TV} (VV^T \mathrm{diag}(Va)V).
\end{aligned}
$$

For $1 \le j, k \le p$, we have

$$ (V^T \mathrm{diag}(Va)V)_{jk} = \sum_{i=1}^{p} a_i \underbrace{\langle v_i \odot v_j \odot v_k, \mathbf{1}_n \rangle}_{=0} = 0, $$

hence $V^T \mathrm{diag}(Va)V = 0$, and $\mathrm{Hess}_V (\mathrm{diag}(Va)V - \mathbf{1}_n a^T) = 0$.

Let us fix $\dot{V} \in T_V(\mathbb{S}^{p-1})^n$. It can be decomposed as $\dot{V} = X + Y$, for some $X, Y \in T_V(\mathbb{S}^{p-1})^n$ such that $X \in \ker \mathrm{Hess}_V$ and $Y \in (\ker \mathrm{Hess}_V)^\perp$. Since $Y$ is orthogonal to the kernel of $\mathrm{Hess}_V$, it is orthogonal to any matrix of the form (24). Therefore, for any $a \in \mathbb{R}^p$,

$$ 
\begin{aligned}
0 &= \langle \mathrm{diag}(Va)V - \mathbf{1}_n a^T, Y \rangle \\
&= \langle Va, \mathrm{diag}(YV^T) \rangle - \langle \mathbf{1}_n a^T, Y \rangle \\
&= - \langle \mathbf{1}_n a^T, Y \rangle \qquad (\text{since } Y \in T_V(\mathbb{S}^{p-1})^n) \\
&= - \langle a^T, \mathbf{1}_n^T Y \rangle,
\end{aligned}
$$

which implies that $\mathbf{1}_n^T Y = 0$. Hence, it holds that

$$ SY = (P_V + pP_{V^\perp} - I_n)Y - \frac{p}{n} \mathbf{1}_n \mathbf{1}_n^T Y = (P_V + pP_{V^\perp} - I_n)Y. $$
Finally,

$$
\begin{align*}
\langle \text{Hess}_V(\dot{V}), \dot{V} \rangle &= \overbrace{\langle \text{Hess}_V(X), X \rangle}^{=0} + \overbrace{\langle \text{Hess}_V(X), Y \rangle}^{=0} + \overbrace{\langle \text{Hess}_V(Y), Y \rangle}^{2\langle SY, Y \rangle} \\
&= 2 \langle (P_V + p P_{V\perp} - I_n)Y, Y \rangle \\
&= 2(p-1) \langle P_{V\perp}Y, Y \rangle \\
&\ge 0.
\end{align*}
$$

To conclude, we show the existence of V satisfying equations (20), (21)
and (22). For instance, when p is even, for any $j \in \{1, \dots, \frac{p}{2}\}$ and $i \in$
$\{1, \dots, n\}$, we can set

$$
V_{i,2j-1} = \sqrt{\frac{2}{p}} \cos \left( \frac{2\pi m_j}{n} (i-1) \right) \quad \text{and} \quad V_{i,2j} = \sqrt{\frac{2}{p}} \sin \left( \frac{2\pi m_j}{n} (i-1) \right),
$$

where $m_j = 3j - 2$. All three equations can be proved using similar computations. Let us for instance establish equality (22) in the case where $i, j, k$ are odd. We have

$$
\begin{align*}
\langle v_i \odot v_j \odot v_k, \mathbf{1}_n \rangle &= \left(\frac{2}{p}\right)^{\frac{3}{2}} \sum_{l=0}^{n-1} \cos\left(\frac{2\pi m_i}{n}l\right) \cos\left(\frac{2\pi m_j}{n}l\right) \cos\left(\frac{2\pi m_k}{n}l\right) \\
&= \frac{1}{\sqrt{2p^3}} \sum_{l=0}^{n-1} \cos\left(\frac{2\pi}{n}(m_i + m_j + m_k)l\right) \\
&\quad + \cos\left(\frac{2\pi}{n}(m_i + m_j - m_k)l\right) \\
&\quad + \cos\left(\frac{2\pi}{n}(m_i - m_j + m_k)l\right) \\
&\quad + \cos\left(\frac{2\pi}{n}(m_i - m_j - m_k)l\right).
\end{align*}
$$

This sum is zero because one can check that, for any $\epsilon_j, \epsilon_k \in \{\pm 1\}$, $m_i + \epsilon_j m_j + \epsilon_k m_k \neq 0$[$n$].

If *p* is odd but *n* is even, we can make the same construction for the first
*p* − 1 columns of *V* and add one last column whose entries alternate between
−√(1/*p*) and √(1/*p*).

<figure><img src="image_2.png" /></figure>
## A.2 Proofs of section 3

*Proof of Corollary 3.1.* The Laplacian matrix of C defined in (2) is

$$ \mathbf{L} = n(I_n - n^{-1}\mathbf{x}\mathbf{x}^T) + \sigma(\mathrm{diag}(W\mathbf{x}\mathbf{x}^T) - W). $$

Define the following matrix:

$$ \mathbf{L}^W = \mathrm{diag}(W\mathbf{x}\mathbf{x}^T) - W. $$

Since $I_n - n^{-1}\mathbf{x}\mathbf{x}^T$ is the orthogonal projector on the orthogonal space of $\mathbf{x}$, its eigenvalues are 0 (with multiplicity 1) and 1 (with multiplicity $n-1$).

Therefore, using Weyl's inequality,

$$ \lambda_n(\mathbf{L}) \le n + \sigma \|\mathbf{L}^W\|, $$

$$ \lambda_2(\mathbf{L}) \ge n - \sigma \|\mathbf{L}^W\|. $$

We need to upper bound $\|\mathbf{L}^W\|$. The triangular inequality gives

$$ \|\mathbf{L}^W\| \le \|W\mathbf{x}\|_{\infty} + \|W\|. $$

Moreover, for all $\varepsilon' > 0$, it holds that

$$ \|W\mathbf{x}\|_{\infty} \le \sqrt{(2 + \varepsilon')n \log n}, \quad (25) $$

with probability at least $1 - n^{-\varepsilon'/2}$. Indeed, note that, for all $i \le n$, $(W\mathbf{x})_i \sim \mathcal{N}(0, n - 1)$. Therefore, from [Vershynin, 2018, Prop 2.1.2], for all $t > 0$,

$$ \mathbb{P}(|(W\mathbf{x})_i| > t) \le \sqrt{\frac{2(n-1)}{\pi} \frac{e^{-\frac{t^2}{2(n-1)}}}{t}}. $$

Applying a union bound and taking $t = \sqrt{(2 + \varepsilon')n \log n}$ yields (25). Moreover, it is also true that, with probability at least $1 - 4e^{-n}$,

$$ \|W\| \le c_0 \sqrt{n}, $$

for some universal constant $c_0 > 0$. This is an immediate consequence of [Vershynin, 2018, Corollary 4.3.6]. Therefore, for any $\varepsilon > 0$, it holds with probability at least $1 - n^{-\varepsilon/4} - 4e^{-n}$ that

$$ \|\mathbf{L}^W\| \le \sqrt{(2 + \frac{\varepsilon}{2}) n \log n} + c_0 \sqrt{n} $$
$$ \leq \sqrt{(2 + \varepsilon) n \log n} \quad (\text{for } n \text{ large enough}). $$

Then, with the same probability,

$$ \sigma < \frac{p-1}{p+1} \sqrt{\frac{n}{(2+\varepsilon)\log n}} \iff \frac{n + \sigma \sqrt{(2+\varepsilon)n \log n}}{n - \sigma \sqrt{(2+\varepsilon)n \log n}} < p \\ \implies \frac{\lambda_n(\mathbf{L})}{\lambda_2(\mathbf{L})} < p. $$

Furthermore, since $\lambda_2(\mathbf{L}) \ge n - \sigma\sqrt{(2+\varepsilon)n \log n}$, it is true that $\lambda_2(\mathbf{L}) > 0$ and $\mathbf{L} \succeq 0$ for $n$ large enough, with probability at least $1 - n^{-\varepsilon/4} - 4e^{-n}$. The conclusion follows from theorem 2.2. $\square$

*Proof of corollary 3.2.* Let $\varepsilon > 0$ be fixed. We can assume without loss of generality that the vector we want to reconstruct is $\mathbf{x} = \mathbf{1}_n$ (see section 4 for more details). The Laplacian matrix is

$$ \mathbf{L} = \operatorname{diag}(C \mathbf{1}_n) - C. $$

Note that $\mathbf{L}$ can be decomposed as a principal term and a noise term as follows:

$$ \begin{aligned} \mathbf{L} &= \mathbb{E}(\mathbf{L}) + (\mathbf{L} - \mathbb{E}(\mathbf{L})) \\ &= \underbrace{\delta(nI_n - \mathbf{1}_n \mathbf{1}_n^T)}_{\text{principal term}} + \underbrace{(\mathbf{L} - \mathbb{E}(\mathbf{L}))}_{\text{noise term}}. \end{aligned} $$

Therefore, using Weyl's inequality yields

$$ \begin{aligned} \lambda_n(\mathbf{L}) &\le \delta n + \|\mathbf{L} - \mathbb{E}(\mathbf{L})\|, \\ \lambda_2(\mathbf{L}) &\ge \delta n - \|\mathbf{L} - \mathbb{E}(\mathbf{L})\|. \end{aligned} $$

In particular, as soon as $\|\mathbf{L} - \mathbb{E}(\mathbf{L})\| < \delta n$, $\lambda_2(\mathbf{L}) > 0$ and

$$ \frac{\lambda_n(\mathbf{L})}{\lambda_2(\mathbf{L})} \le \frac{\delta n + \|\mathbf{L} - \mathbb{E}(\mathbf{L})\|}{\delta n - \|\mathbf{L} - \mathbb{E}(\mathbf{L})\|}, $$

so that, from theorem 2.2, all second-order critical points are global minimizers if the right-hand side of the above is below $p$.

Note that

$$ \|\mathbf{L} - \mathbb{E}(\mathbf{L})\| \le \|\operatorname{diag}(C \mathbf{1}_n) - \delta(n-1)I_n\| + \|C - \delta(\mathbf{1}_n \mathbf{1}_n^T - I_n)\|. $$
For $1 \le i \le n$, we have the following equality:

$$ (\mathrm{diag}(C \mathbf{1}_n) - \delta(n-1))_{ii} = \sum_{j \ne i} (C_{ij} - \delta). $$

Let $h(u) = (1+u)\log(1+u) - u = \frac{u^2}{2}(1+o_{u \to 0}(1))$. Using Bennett's inequality, we get for $t \ge 0$

$$ \begin{aligned} \mathbb{P}\left(\left|\sum_{j \ne i} (C_{ij} - \delta)\right| > t\right) &\le 2 \exp\left(-\frac{(n-1)(1-\delta)}{1+\delta} h\left(\frac{t}{(n-1)(1-\delta)}\right)\right) \\ &\le 2 \exp\left(-\left(\frac{n-1}{1+\delta}\right) h\left(\frac{t}{n-1}\right)\right). \end{aligned} $$

The second inequality is true because $h$ is convex and $h(0) = 0$, so $ah(x/a) \ge h(x)$ for all $x \ge 0, a \in ]0; 1]$. We set $t = \sqrt{(2+\varepsilon')(1+\delta)n \log n}$ for some $\varepsilon' < \frac{\varepsilon}{2}$. Observe that $\frac{t}{n-1} \to 0$ when $n \to +\infty$, so $h(\frac{t}{n-1}) = \frac{t^2}{2n^2}(1+o(1))$ and

$$ \mathbb{P}\left(\left|\sum_{j \ne i} (C_{ij} - \delta)\right| > \sqrt{(2+\varepsilon')(1+\delta)n \log n}\right) \le 2n^{-(1+\varepsilon'/2)(1+o_{n \to \infty}(1))}. $$

Therefore, using a union bound, we get

$$ \mathbb{P}\left(\|\mathrm{diag}(C \mathbf{1}_n) - \delta(n-1)I_n\| \le \sqrt{(2+\varepsilon')(1+\delta)n \log n}\right) \ge 1-2n^{-(\varepsilon'/2+o(1))}. $$

Moreover, from [McRae, Abdalla, Bandeira, and Boumal, 2024, Lemma 2], with probability at least $1 - n^{-3}$,

$$ \|C - \delta(\mathbf{1}_n \mathbf{1}_n^T - I_n)\| \lesssim \sqrt{n}, $$

This bound is negligible in front of $\sqrt{n \log n}$, for $n$ large enough, so that

$$ \|\mathbf{L} - \mathbb{E}(\mathbf{L})\| < \sqrt{(2+2\varepsilon')(1+\delta)n \log n}, $$

with probability at least $1 - n^{-3} - 2n^{-\frac{\varepsilon'}{3}}$. Therefore, we get the desired result if

$$ \frac{\delta n + \sqrt{(2+2\varepsilon')(1+\delta)n \log n}}{\delta n - \sqrt{(2+2\varepsilon')(1+\delta)n \log n}} < p \iff \delta > \frac{1 + \sqrt{1 + 4 \left(\frac{p-1}{p+1}\right)^2 \frac{n}{(2+2\varepsilon') \log n}}}{2 \left(\frac{p-1}{p+1}\right)^2 \frac{n}{(2+2\varepsilon') \log n}}. $$
In the regime when $n$ is large, recalling that $\varepsilon > 2\varepsilon'$, this is implied by

$$ \delta > \frac{p+1}{p-1} \sqrt{\frac{(2+\varepsilon) \log n}{n}}. $$

<figure><img src="image_3.png" /></figure>

## A.3 Proofs of section 4

*Proof of lemma 4.2.* Let $(L, \mu)$ be a solution of (Primal). Since $P_{\perp}LP_{\perp} \geq P_{\perp}$ it holds that $\lambda_2(P_{\perp}LP_{\perp}) \geq 1$, therefore $\frac{\lambda_n(P_{\perp}LP_{\perp})}{\lambda_2(P_{\perp}LP_{\perp})} \leq \lambda_n(P_{\perp}LP_{\perp})$. Since $(P_{\perp}LP_{\perp}, \mu)$ is feasible for (10), the optimal value of (10) is less than that of (Primal).

Now, let $(L, \mu)$ be feasible for (10) and define

$$ (L', \mu') = \left( \frac{L}{\lambda_2(L)}, \frac{\mu}{\lambda_2(L)} \right), $$

which is feasible for (Primal). The last two constraints of (Primal) are easily verified. For the first constraint, note that $\text{Ker}(L) = \mathbf{1}_n$; therefore, for all $x \in \mathbb{R}^n$, $P_{\perp}x$ is the projection of $x$ onto the orthogonal of $\text{Ker}(L)$, and $\|Lx\|^2 \geq \lambda_2(L) \|P_{\perp}x\|^2$. This implies that $P_{\perp}L'P_{\perp} \geq P_{\perp}$. Thus we have

$$ \text{Opt (Primal)} \leq \lambda_n(L') = \frac{\lambda_n(L)}{\lambda_2(L)}. $$

By minimizing both sides of the inequality for all $L$ feasible for (10), we get

$$ \text{Opt (Primal)} \leq \text{Opt (10)}. $$

<figure><img src="image_4.png" /></figure>

*Proof of lemma 4.3.* First, we first incorporate the constraints into the cost function and problem (Primal) becomes

$$ \begin{aligned} \inf_{(L, \mu) \in \mathbb{S}^{n \times n} \times \mathbb{R}^n} & \lambda_n(P_{\perp}LP_{\perp}) + \sup_{Z \succeq 0} \langle P_{\perp}LP_{\perp} - P_{\perp}, Z \rangle \\ & + \sup_{W \in \mathbb{R}^{n \times p}} \langle (P_{\perp}LP_{\perp} - \text{diag}(\mu))V, W \rangle \\ & + \sup_{H \in \mathcal{K}} \langle \text{diag}(\mu) - P_{\perp}LP_{\perp}, H \rangle. \end{aligned} $$
To lighten notations, define the constraint set $\mathcal{C}$ as :

$$ \mathcal{C} = \{ (W, Z, H) \in \mathbb{R}^{n \times p} \times \mathbb{S}^{n \times n} \times \mathbb{S}^{n \times n} : Z \succeq 0 \text{ and } H \in K \}. $$

We symmetrize and simplify the previous expression of problem (Primal). We get that it is equal to

$$ \inf_{(L, \mu) \in \mathbb{S}^{n \times n} \times \mathbb{R}^n} \lambda_n(P_{\perp} LP_{\perp}) \\ + \sup_{(W, Z, H) \in \mathcal{C}} - \left\langle P_{\perp} \left( Z + H - \frac{WV^T + VW^T}{2} \right) P_{\perp}, L \right\rangle \\ + \langle P_{\perp}, Z \rangle + \langle \operatorname{diag}(\mu), H - WV^T \rangle. $$

By inverting the inf and the sup we get

Opt (Primal)

$$ \begin{aligned} & \geq \sup_{(W, Z, H) \in \mathcal{C}} \langle P_{\perp}, Z \rangle \\ & + \inf_{L \in \mathbb{S}^{n \times n}} \lambda_n(P_{\perp} LP_{\perp}) - \left\langle P_{\perp} \left( Z + H - \frac{WV^T + VW^T}{2} \right) P_{\perp}, L \right\rangle \quad (26) \\ & + \inf_{\mu \in \mathbb{R}^n} \langle \operatorname{diag}(\mu), H - WV^T \rangle. \end{aligned} $$

The next step is to rewrite the last two terms of the right hand side of inequality (26) as characteristic functions of convex sets. Note that

$$ \inf_{\mu \in \mathbb{R}^n} \langle \operatorname{diag}(\mu), H - WV^T \rangle = \begin{cases} 0 & \text{if } \operatorname{diag}(H) = \operatorname{diag}(WV^T) \\ -\infty & \text{otherwise.} \end{cases} $$

Moreover, by letting $M = P_{\perp} \left(Z + H - \frac{WV^T + VW^T}{2}\right) P_{\perp}$, we have

$$ \inf_{L \in \mathbb{S}^{n \times n}} \lambda_n(P_{\perp} LP_{\perp}) - \langle M, L \rangle = \begin{cases} 0 & \text{if } M \succeq 0 \text{ and } \operatorname{Tr}(M) \le 1, \\ -\infty & \text{otherwise.} \end{cases} $$

To see this, assume first that $M$ is not positive semidefinite. Therefore, we can write the eigendecomposition of $M$ as $M = \sum_{i=1}^n \rho_i u_i u_i^T$ with $\rho_1 = 0$ and $u_1 = \frac{1}{\sqrt{n}}$ (since $\mathbf{1}_n$ belongs to the kernel of $M$) and $\rho_2 < 0$. Take $L_x = x u_2 u_2^T$, with $x < 0$. By noting that $P_{\perp} L_x P_{\perp} = L_x$, we have

$$ \lambda_n(P_{\perp} L_x P_{\perp}) - \langle M, L_x \rangle = -x \rho_2 \|u_2\|^2 \xrightarrow{x \to -\infty} -\infty. $$
Now, assume that Tr($M$) > 1 and take $L_y = yI_n$ with $y > 0$. We have

$$ \lambda_n(P_{\perp}L_yP_{\perp}) - \langle M, L_y \rangle = y(1 - \mathrm{Tr}(M)) \xrightarrow{y \to \infty} -\infty. $$

Finally, assume that $M \succeq 0$ and Tr($M$) $\leq 1$. It is always true that for any symmetric matrix $L$, $P_{\perp}LP_{\perp} \leq \lambda_n(P_{\perp}LP_{\perp})I_n$. Therefore, since $M \succeq 0$, we have

$$ \begin{aligned} \langle P_{\perp}LP_{\perp}, M \rangle &\leq \langle \lambda_n(P_{\perp}LP_{\perp})I_n, M \rangle \\ &= \lambda_n(P_{\perp}LP_{\perp}) \mathrm{Tr}(M). \end{aligned} $$

Using the fact that Tr($M$) $\leq 1$ and $\langle P_{\perp}LP_{\perp}, M \rangle = \langle L, M \rangle$, we get that $\lambda_n(P_{\perp}LP_{\perp}) - \langle M, L \rangle \geq 0$ and the bound is reached for $L = 0$. To conclude, the right hand side of inequality (26) becomes

$$ \begin{array}{ll} \sup_{(W,Z,H) \in \mathcal{C}} & \langle Z, P_{\perp} \rangle \\ \text{s.t.} & \mathrm{diag}(WV^T) = \mathrm{diag}(H) \\ & M = P_{\perp} \left( Z + H - \frac{1}{2} (WV^T + VW^T) \right) P_{\perp} \\ & M \succeq 0 \\ & \mathrm{Tr}(M) \leq 1. \end{array} $$

□

*Proof of lemma 4.4.* Let us assume that $\beta \geq 0$. We define

$$ S = \left( \frac{\frac{p}{\langle P_{\perp}, VV^T \rangle} - (p-1)\beta}{\frac{\delta}{2}} \quad \frac{\frac{\delta}{2}}{\beta} \right) $$

and, for each $k = 1, \dots, p$,

$$ M_k = (v_k \quad v_1 \odot v_k) \in \mathbb{R}^{n \times 2}. $$

We show that, if equation (14) holds, then $M_* \succeq 0$. We have

$$ \begin{aligned} M_* &= P_{\perp} \left( Z_* + H_* - \frac{1}{2} (W_* V^T + V W_*^T) \right) P_{\perp} \\ &= P_{\perp} \left( \left( \frac{p}{\langle P_{\perp}, VV^T \rangle} - (p-1)\beta \right) VV^T + \beta (VV^T)^{\odot 2} \right) \end{aligned} $$
$$
\begin{align*}
&+ \frac{\delta}{2}(\operatorname{diag}(v_1)VV^T + VV^T \operatorname{diag}(v_1))\bigg)P_{\perp} \\
&= P_{\perp} \left( \left( \frac{p}{\langle P_{\perp}, VV^T \rangle} - (p-1)\beta \right) \left( \sum_{k=1}^{p} v_k v_k^T \right) \right. \\
&\qquad \left. + \beta \left( \sum_{k,k'=1}^{p} (v_k \odot v_{k'})(v_k \odot v_{k'})^T \right) \right. \\
&\qquad \left. + \frac{\delta}{2} \left( \sum_{k=1}^{p} (v_1 \odot v_k)v_k^T + v_k(v_1 \odot v_k)^T \right) \right) P_{\perp} \\
&\stackrel{(a)}{\succeq} P_{\perp} \left( \left( \frac{p}{\langle P_{\perp}, VV^T \rangle} - (p-1)\beta \right) \left( \sum_{k=1}^{p} v_k v_k^T \right) \right. \\
&\qquad \left. + \beta \left( \sum_{k=1}^{p} (v_1 \odot v_k)(v_1 \odot v_k)^T \right) \right. \\
&\qquad \left. + \frac{\delta}{2} \left( \sum_{k=1}^{p} (v_1 \odot v_k)v_k^T + v_k(v_1 \odot v_k)^T \right) \right) P_{\perp} \\
&= P_{\perp} \left( \sum_{k=1}^{p} M_k SM_k^T \right) P_{\perp}.
\end{align*}
$$

Inequality (a) is true because $\beta(v_k \odot v_{k'})(v_k \odot v_{k'})^T \succeq 0$ for all $k, k'$.

Therefore, if $S \succeq 0$, then $M_k SM_k^T \succeq 0$ for all $k$, hence $M_* \succeq 0$. This condition is fulfilled if all principal minors of $S$ are nonnegative, that is

$$0 \le \frac{p}{\langle P_{\perp}, VV^T \rangle} - (p-1)\beta, \qquad (27a)$$

$$0 \le \beta, \qquad (27b)$$

$$0 \le \det(S) = \beta \left( \frac{p}{\langle P_{\perp}, VV^T \rangle} - (p-1)\beta \right) - \frac{\delta^2}{4}. \qquad (27c)$$

Equation (27b) is true by assumption, and (27a) is implied by (27c). Indeed, if equation (27a) is not true, then

$$\beta > \frac{p}{(p-1)\langle P_{\perp}, VV^T \rangle} > 0,$$

so

$$\beta \left( \frac{p}{\langle P_{\perp}, VV^T \rangle} - (p-1)\beta \right) < 0 \le \frac{\delta^2}{4},$$
and (27c) is not true either. Therefore, if equation (27c) is true, then (27a)
is also true and $M_* \succeq 0$. This equation is equivalent to (14). $\square$

References

P-A Absil. *Optimization algorithms on matrix manifolds*. Princeton University Press, 2008.

Afonso S Bandeira. Random laplacian matrices and convex relaxations. *Foundations of Computational Mathematics*, 18:345–379, 2018.

Steven J Benson, Yinyu Ye, and Xiong Zhang. Solving large-scale sparse semidefinite programs for combinatorial optimization. *SIAM Journal on Optimization*, 10(2):443–461, 2000.

Nicolas Boumal. *An introduction to optimization on smooth manifolds*. Cambridge University Press, 2023.

Nicolas Boumal, Vladislav Voroninski, and Afonso S Bandeira. Deterministic guarantees for burer-monteiro factorizations of smooth semidefinite programs. *Communications on Pure and Applied Mathematics*, 73(3): 581–608, 2020.

Emmanuel J Candès, Thomas Strohmer, and Vladislav Voroninski. Phaselift: exact and stable signal recovery from magnitude measurements via convex programming. *Communications on Pure and Applied Mathematics*, 66(8): 1241–1274, 2013.

Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. *Journal of the ACM (JACM)*, 42(6):1115–1145, 1995.

M. Journée, F. Bach, P.-A. Absil, and R. Sepulchre. Low-rank optimization on the cone of positive semidefinite matrices. *SIAM Journal on Optimization*, 20(5):2327–2351, 2010.

Gert RG Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I Jordan. Learning the kernel matrix with semidefinite programming. *Journal of Machine learning research*, 5(Jan):27–72, 2004.
J. D. Lee, I. Panageas, G. Piliouras, M. Simchowitz, M. I. Jordan, and B. Recht. First-order methods almost always avoid strict saddle points. *Mathematical programming*, 176:311–337, 2019.

Shuyang Ling. Local geometry determines global landscape in low-rank factorization for synchronization. arXiv preprint arXiv:2311.18670, 2023.

Andrew D McRae and Nicolas Boumal. Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs. SIAM Journal on Optimization, 34(2):1427–1454, 2024.

Andrew D McRae, Pedro Abdalla, Afonso S Bandeira, and Nicolas Boumal. Nonconvex landscapes for $Z_2$ synchronization and graph clustering are benign near exact recovery thresholds. arXiv preprint arXiv:2407.13407, 2024.

Song Mei, Theodor Misiakiewicz, Andrea Montanari, and Roberto Imbuzeiro Oliveira. Solving sdps for synchronization and max-cut problems via the grothendieck inequality. In Annual Conference Computational Learning Theory, 2017. URL https://api.semanticscholar.org/CorpusID:6039962.

Liam O'Carroll, Vaidehi Srinivas, and Aravindan Vijayaraghavan. The burer-monteiro sdp method can fail even above the barvinok-pataki bound. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022*, Advances in Neural Information Processing Systems. Neural information processing systems foundation, 2022.

Gábor Pataki. On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Mathematics of Operations Research, 23(2):339–358, 1998. ISSN 0364765X, 15265471. URL http://www.jstor.org/stable/3690515.

Roman Vershynin. *High-dimensional probability: An introduction with applications in data science*, volume 47. Cambridge university press, 2018.

Irène Waldspurger and Alden Waters. Rank optimality for the burer-monteiro factorization. SIAM J. Optim., 30(3):2577–2602, 2020. doi: 10.1137/19M1255318. URL https://doi.org/10.1137/19M1255318.