Lemma D.11 ensures that there exists a constant $C''_{lLea}$ depending only on $c_l, c_L, c_e, c_a$ such that $\|F_{SS} - R_\sigma\|_2 \le C''_{lLea} \sqrt{n \log(n)}$. Since $R_\sigma$ has the same eigenvalues as $R$, it follows from Weyl's inequality (see e.g. [39, page 45]) that

$$|\lambda_i^{*(S)} - \lambda_i| \le \|F_{SS} - R_\sigma\|_{op} \le \|F_{SS} - R_\sigma\|_2 \le C''_{lLea} \sqrt{n \log(n)}, \quad (71)$$

for all $i = 0, \dots, n_0 - 1$.

If the constant $C_{lLea}$ in (68) is chosen as $4C''_{lLea}$ where $C''_{lLea}$ is introduced in (71), it follows that

$$\begin{aligned} \lambda_0 - \lambda_1 &\ge (\lambda_0^{*(S)} - \lambda_1^{*(S)}) - (\lambda_0^{*(S)} - \lambda_0) - (\lambda_1 - \lambda_1^{*(S)}) \\ &\ge (C_{lLea} - 2C''_{lLea}) \sqrt{n \log(n)} \\ &\ge \frac{C_{lLea}}{2} \sqrt{n \log(n)}, \end{aligned} \quad (72)$$

and similarly,

$$\lambda_2 - \lambda_3 \ge (\lambda_2^{*(S)} - \lambda_3^{*(S)}) - (\lambda_2^{*(S)} - \lambda_2) - (\lambda_3 - \lambda_3^{*(S)}) \ge \frac{C_{lLea}}{2} \sqrt{n \log(n)}.$$

Since the eigenvectors $(\sqrt{2/n_0})\mathbf{u}^{(1)}$ and $(\sqrt{2/n_0})\mathbf{v}^{(1)}$ of $R$ are orthonormal (see Lemma D.12 below), the vectors $(\sqrt{2/n_0})\mathbf{u}_\sigma^{(1)}$ and $(\sqrt{2/n_0})\mathbf{v}_\sigma^{(1)}$ are orthonormal eigenvectors of $R_\sigma$, with the same eigenvalue $\lambda_1 = \lambda_2 = \alpha_1$.

**Lemma D.12.** The vectors $(\sqrt{2/n_0})\mathbf{u}^{(1)}$ and $(\sqrt{2/n_0})\mathbf{v}^{(1)}$ are orthonormal.

Next, we state a variant of Davis-Kahan perturbation bound [42, see Theorem 2].

**Lemma D.13 (Davis-Kahan).** Let $M, \hat{M} \in \mathbb{R}^{n_0 \times n_0}$ be two symmetric matrices, with eigenvalues $\lambda_0 \ge \dots \ge \lambda_{n_0-1}$ and $\hat{\lambda}_0 \ge \dots \ge \hat{\lambda}_{n_0-1}$ respectively. Fix $0 \le r \le s \le n_0-1$ and assume that $(\lambda_{r-1}-\lambda_r)\wedge(\lambda_s-\lambda_{s+1}) > 0$, where $\lambda_{-1} = \infty$ and $\lambda_n = -\infty$. Let $d = s-r+1$, and let $\mathbf{V} = (\mathbf{v}_r, \mathbf{v}_{r+1}, \dots, \mathbf{v}_s) \in \mathbb{R}^{n_0 \times d}$ and $\hat{\mathbf{V}} = (\hat{\mathbf{v}}_r, \hat{\mathbf{v}}_{r+1}, \dots, \hat{\mathbf{v}}_s) \in \mathbb{R}^{n_0 \times d}$ have orthonormal columns satisfying $M\mathbf{v}_j = \lambda_j \mathbf{v}_j$ and $\hat{M}\hat{\mathbf{v}}_j = \hat{\lambda}_j \hat{\mathbf{v}}_j$ for $j = r, r+1, \dots, s$. Then, there exists an orthogonal matrix $Q \in \mathbb{R}^{d \times d}$ such that

$$\|\hat{\mathbf{V}}Q - \mathbf{V}\|_2 \le \sqrt{8d} \frac{\|\hat{M} - M\|_{op}}{(\lambda_{r-1} - \lambda_r) \wedge (\lambda_s - \lambda_{s+1})}.$$

The assumptions of Lemma D.13 are therefore fulfilled for the orthonormal eigenvectors $(\sqrt{2/n_0})\mathbf{u}_\sigma^{(1)}$ and $(\sqrt{2/n_0})\mathbf{v}_\sigma^{(1)}$ and the positive spectral gaps $(\lambda_0 - \lambda_1) \wedge (\lambda_2 - \lambda_3) > 0$. Hence, for $\hat{\mathbf{x}}_S^{\text{VSA}}$ and $\mathbf{x}_S^{**} = (\mathbf{u}_\sigma^{(1)}, \mathbf{v}_\sigma^{(1)})^T$ in $\mathbb{R}^{2 \times n}$, Lemma D.13 entails

$$\sqrt{\frac{2}{n_0}} \|Q \hat{\mathbf{x}}_S^{\text{VSA}} - \mathbf{x}_S^{**}\|_2 \lesssim \frac{\|A_{S,S} - R_\sigma\|_{op}}{(\lambda_0 - \lambda_1) \wedge (\lambda_2 - \lambda_3)}.$$

for some $Q \in \mathcal{O}$.
It remains to control $||A_{S,S} - R_{\sigma}||_{op}$ and the spectral gap. Since $A_{ii} = 0$ for all $i$ (by convention), we introduce the matrix $F_{SS}^{(0)}$ such that $F_{ii}^{(0)} = 0$ for all $i$, and $F_{ij}^{(0)} = F_{ij}$ for all $i \neq j$.

$$ \|A_{SS} - R_{\sigma}\|_{op} \le \|A_{SS} - F_{SS}^{(0)}\|_{op} + \|F_{SS}^{(0)} - F_{SS}\|_{op} + \|F_{SS} - R_{\sigma}\|_{2}, \quad (73) $$

using the triangular inequality and the fact that the operator norm is smaller than the Frobenius norm. The second term $\|F_{SS}^{(0)} - F_{SS}\|_{op}$ is smaller than 1 since $F_{SS} - F_{SS}^{(0)}$ is the diagonal matrix with diagonal coefficients $f(x_i^*, x_i^*) \le 1$, the last inequality coming from $f \in \mathcal{BL}[c_l, c_L, c_e]$. To control the operator norm of the noise matrix, we shall use the following result [40, Corollary 4.4.8]. See the same reference for the definition of sub-Gaussian norms $||\cdot||_{\psi_2}$.

**Lemma D.14** (norm of symmetric matrices with sub-gaussian entries). Let $A$ be an $n_0 \times n_0$ symmetric random matrix whose entries $A_{ij}$ on and above the diagonal are independent mean-zero sub-gaussian random variables. Then, for any $t > 0$, we have

$$ \|A\|_{op} \le CK(\sqrt{n} + t) $$

with probability at least $1 - 4e^{-t^2}$. Here $K = \max_{i,j} \|A_{i,j}\|_{\psi_2}$.

Applying the above lemma with $t = C\sqrt{\log(n)}$ (for a large enough numerical constant $C$) to the difference $A_{SS} - F_{SS}^{(0)}$, we obtain $\|A_{SS} - F_{SS}^{(0)}\|_{op} \lesssim \sqrt{n}$ with probability higher than $1 - 1/n^2$.

Together with Lemma D.11 and the bound (73), we deduce that $\|A_{SS} - R_{\sigma}\|_{op} \le C_{lLea}\sqrt{n\log(n)}$, so that

$$ \|Q\hat{\mathbf{x}}_{S}^{\text{VSA}} - \mathbf{x}_{S}^{**}\|_{2} \le C_{lLea} \frac{n\sqrt{\log(n)}}{(\lambda_{0} - \lambda_{1}) \wedge (\lambda_{2} - \lambda_{3})} . $$

Then, we deduce from the Cauchy-Schwarz inequality that

$$ \min_{Q' \in \mathcal{O}} \|\hat{\mathbf{x}}_{S}^{\text{VSA}} - Q' \mathbf{x}_{S}^{**}\|_{1} \le \|Q \hat{\mathbf{x}}_{S}^{\text{VSA}} - \mathbf{x}_{S}^{**}\|_{1} \le C_{lLea} \frac{n \sqrt{n \log(n)}}{(\lambda_{0} - \lambda_{1}) \wedge (\lambda_{2} - \lambda_{3})} . $$

The bounds (68) and (71) for $C_{lLea} = 4C_{lLea}''$ allow us to replace the above spectral gaps by $(\lambda_0^{*(S)} - \lambda_1^{*(S)}) \wedge (\lambda_2^{*(S)} - \lambda_3^{*(S)})$. Finally, by (69) and the equivalence between the distance $d$ in $\mathcal{C}$ and the $l^1$-norm in $\mathbb{R}^2$, we have $\min_{Q \in \mathcal{O}} \|\mathbf{x}_S^* - Q\mathbf{x}_S^{**}\|_1 \le C_a \sqrt{n \log(n)}$. Since $\lambda_0 \le n$ (all the entries of $F_{SS}$ belong to $[0, 1]$), we then deduce from the triangular inequality that

$$ \min_{Q \in \mathcal{O}} \|\hat{\mathbf{x}}_{S}^{\text{VSA}} - Q\mathbf{x}_{S}^{*}\|_{1} \le C'_{lLea} \frac{n\sqrt{n\log(n)}}{(\lambda_{0}^{*(S)} - \lambda_{1}^{*(S)}) \wedge (\lambda_{2}^{*(S)} - \lambda_{3}^{*(S)})} . $$

Proposition D.1 is proved. $\square$
### D.4.3. Proofs of technical lemmas

**Proof of Lemma D.11.** In this proof, we replace the notation $F_{SS}$ by $F_{(x_S^*, f)}$ for clarity. Since the vector $x_S^*$ satisfies (57), there exists $x_S \in \Pi_{n_0}$ such that the following inequality holds

$$d_{\infty}(\mathbf{x}_S^*, \mathbf{x}_S) \le C_a \sqrt{\log(n)/n}. \quad (74)$$

Combining this with the bi-Lipschitz condition (5), we get $\max_{ij \in [n_0]} |f(x_i^*, x_j^*) - f(x_i, x_j)| \le C_{Lea} \sqrt{\log(n)/n}$, that is,

$$\|F_{(x_S^*, f)} - F_{(x_S, f)}\|_{\infty} \le C_{Lea} \sqrt{\frac{\log(n)}{n}}, \quad (75)$$

for the matrices $F_{(x_S^*, f)} := [f(x_i^*, x_j^*)]_{i,j \in [n_0]}$ and $F_{(x_S, f)} := [f(x_i, x_j)]_{i,j \in [n_0]}$.

Recall that $S = \{1, \dots, n_0\}$ for the ease of exposition. Let $\tau$ be some permutation that orders $x_S = (x_1, \dots, x_{n_0})$ on the unit sphere, that is, such that $x_{\tau(1)}, \dots, x_{\tau(n_0)}$ is ordered. Then, one can observe that the matrix $F_{(x_S, f), \tau}$ is symmetric circulant since $f$ is a symmetric function which satisfies the geometric condition (23) with respect to the geodesic distance $d$ on the unit sphere $C$.

The matrix $F_{(x_S, f), \tau}$ is therefore defined by a single vector $\mathbf{a}$ of size $n_0$ as in Definition D.8 of circulant matrices. This vector satisfies $a_s = g(2\pi s/n_0)$ for $s = 0, \dots, \lfloor n_0/2 \rfloor$, where we recall that $g(d(x, y)) = f(x, y)$ in the geometric setting. From the Lipschitz condition (6), we deduce that $\mathbf{a}$ satisfies some kind of weak non-increasing condition, that is $a_t \ge a_s \ge 0$ for all $0 \le t < s \le \lfloor n_0/2 \rfloor$ such that $s - t \ge C_{le} \sqrt{n \log(n)}$.

From the bi-Lipschitz condition (5), it is easy to see that $\mathbf{a}$ can be uniformly approximated by a non-increasing vector $\mathbf{a}'$ such that $\max_j |a_j - a_j'| \le C_{lLe} \sqrt{\log(n)/n}$. Denoting $R$ the circulant circular R-matrix based on the vector $\mathbf{a}'$, this means that $\max_{ij} |R_{ij} - f(x_{\tau(i)}, x_{\tau(j)})| \le C_{lLe} \sqrt{\log(n)/n}$. Hence,

$$\|F_{(x_S, f)} - R_{\tau^{-1}}\|_{\infty} = \|F_{(x_S, f), \tau} - R\|_{\infty} \le C_{lLe} \sqrt{\frac{\log(n)}{n}}.$$

The first result of Lemma D.11 is a consequence of (75) and the last display, setting $\sigma = \tau^{-1}$.

Next, by definition of $\tau$, the vector $(x_S)_{\sigma^{-1}} = (x_S)_{\tau}$ is ordered, and it therefore equals any other ordered vector in $\Pi_{n_0}$ up to an orthogonal transformation. Hence, we have $[(x_S)_{\sigma^{-1}}]_i = Q(u_i^{(1)}, v_i^{(1)})$ for some orthogonal transformation $Q$ in $\mathbb{R}^2$, by definition of $\mathbf{u}^{(1)}$ and $\mathbf{v}^{(1)}$. Equivalently, we have $(x_S)_i = Q((\mathbf{u}_\sigma^{(1)})_i, (\mathbf{v}_\sigma^{(1)})_i)$. Then, we conclude again from (74) that the vector $x_S^* := (\mathbf{u}_\sigma^{(1)}, \mathbf{v}_\sigma^{(1)})$ satisfies the second result of the lemma. $\square$

**Proof of Lemma D.12.** Since $\sum_{k=0}^{n_0-1} e^{i4\pi k/n_0} = 0$, we have $\sum_{k=0}^{n_0-1} \cos(4\pi k/n_0) = 0$ and $\sum_{k=0}^{n_0-1} \sin(4\pi k/n_0) = 0$. Then, combining with the trigonometric formu-
las, $\cos(2x) = 2 \cos^2(x) - 1$, and $\sin(2x) = 2 \cos(x) \sin(x)$, we get

$$ \begin{aligned} \|\mathbf{u}^{(1)}\|_{2}^{2} &= \sum_{k=0}^{n_0-1} \cos^2(2\pi k / n_0) = \frac{n_0}{2}, && (76) \\ \langle \mathbf{u}^{(1)}, \mathbf{v}^{(1)} \rangle &= \sum_{k=0}^{n_0-1} \cos(2\pi k / n_0) \sin(2\pi k / n_0) = 0. \end{aligned} $$

Besides, $\|\mathbf{u}^{(1)}\|_{2}^{2} + \|\mathbf{v}^{(1)}\|_{2}^{2} = n_0$ since $(u_i^{(1)}, v_i^{(1)})$ for any $i \in [n_0]$ is a point of the unit sphere $C$. The combination with (76) leads to $\|\mathbf{v}^{(1)}\|_{2}^{2} = n_0/2$. $\square$

### D.5. Proof of Lemma 4.2

Similarly to the proof of Lemma D.11, we consider a vector $\mathbf{x} \in \Pi_n$ achieving $d_{\infty}(\mathbf{x}^*, \mathbf{x}) = d_{\infty}(\mathbf{x}^*, \Pi_n) \le C_a \sqrt{\log(n)/n}$. By the Bi-Lipschitz condition, the matrices $F_{\mathbf{x}^*,f}$ and $F_{\mathbf{x},f}$ satisfy

$$ \|F_{\mathbf{x},f} - F_{\mathbf{x}^*,f}\|_{\infty} \le C_{\text{Lea}} \sqrt{\frac{\log(n)}{n}}. $$

Since $f$ is geometric and $\mathbf{x}$ belongs to $\Pi_n$, it follows that, up to a permutation, $F_{\mathbf{x},f}$ is a symmetric circulant matrix associated to the vector $a_j = g(j \frac{2\pi}{n})$ for $j = 0, \dots, \lfloor \frac{n}{2} \rfloor$. It then follows from Lemma D.9, that the eigenvalues of $F_{\mathbf{x},f}$ are equal to the discrete Fourier transform $\mathcal{F}_{m,n}(g)$ of $g$.

The sequence $(a_j)$, for $j = 0, \dots, \lfloor \frac{n}{2} \rfloor$ is not non-increasing because the function $g$ is not exactly decreasing with respect to the distance. Still, arguing as in the proof of Lemma D.11, we can build an non-increasing sequence $\mathbf{a}'$ satisfying $\max_j |a_j - a'_j| \le C_{lLea} \sqrt{\log(n)/n}$. The eigenvalues of the corresponding circulant and circular $R$-matrix $R$ are also given by Lemma D.9. We denote them $\alpha_0, \alpha_1, \dots, \alpha_{\lfloor n/2 \rfloor}$. It follows from the definition of the Fourier transform that

$$ |\mathcal{F}_{m,n}(g) - \alpha_m| \le C_{lLea} \sqrt{n \log(n)}, \quad 0 \le m \le \lfloor \frac{n}{2} \rfloor. $$

Hence, the gaps in the Fourier transform $\Phi_1 = \mathcal{F}_{0,n}(g) - \mathcal{F}_{1,n}(g)$ and $\Phi_2 = \min_{j=2,\dots,\lfloor n/2 \rfloor} \mathcal{F}_{1,n}(g) - \mathcal{F}_{j,n}(g)$ satisfy

$$ |\Phi_1 - (\alpha_0 - \alpha_1)| \vee |\Phi_2 - \min_{m=2,\dots,\lfloor \frac{n}{2} \rfloor} (\alpha_1 - \alpha_m)| \le C_{lLea} \sqrt{n \log(n)}. $$

To conclude, it remains to prove that

$$ \begin{aligned} |(\alpha_0 - \alpha_1) - \Delta_1| &\le C'_{lLea} \sqrt{n \log(n)}; && (77) \\ \left| \min_{m=2,\dots,\lfloor \frac{n}{2} \rfloor} (\alpha_1 - \alpha_m) - \Delta_2 \right| &\le C'_{lLea} \sqrt{n \log(n)}. && \end{aligned} $$
By Lemma D.10, we have $\alpha_0 > \alpha_1 \ge \max_{j=2,...,\lfloor n/2 \rfloor} \alpha_j$. Hence, if we denote $\lambda_0 \ge \lambda_1 \dots \ge \lambda_{n-1}$ the ordered eigenvalues of $R$ we have

$$ \lambda_0 = \alpha_0 \ge \lambda_1 = \alpha_1 \ge \lambda_2 = \alpha_1 \ge \lambda_3, \qquad (78) $$

where $\lambda_3 = \max\{\alpha_2, \dots, \alpha_{\lfloor n/2 \rfloor}\}$. By definition of $\mathbf{a}'$ and $\mathbf{x}$, there exists a permutation $\tau$ of $[n]$ such that

$$ \|F_{\mathbf{x}^*,f} - R_{\tau}\|_{\infty} \le C_{lLea} \sqrt{\frac{\log(n)}{n}}, $$

which implies that $\|F_{\mathbf{x}^*,f} - R_{\tau}\|_{op} \le \|F_{\mathbf{x}^*,f} - R_{\tau}\|_2 \le C_{lLea} \sqrt{n \log(n)}$. Denoting $\lambda_0^* \ge \lambda_1^* \ge \lambda_2^* \ge \dots$ the ordered eigenvalues of $F_{\mathbf{x}^*,f}$, we deduce from Weyl's inequality that

$$ \max_{j=0,...,n-1} |\lambda_j^* - \lambda_j| \le C_{lLea} \sqrt{n \log(n)}. $$

Together with (78), we deduce that $\Delta_1 = \lambda_0^* - \lambda_1^*$ and $\Delta_2 = \lambda_2^* - \lambda_3^*$ satisfy (77) which concludes the proof.

### D.6. Proof of Corollary 4.3 (spectral gap for affine functions)

We will show that, for $n$ large enough, the gaps in the Fourier $\Phi_1 := \mathcal{F}_{0,n}(g) - \mathcal{F}_{1,n}(g)$ and $\Phi_2 := \min_{j=2,...,\lfloor n/2 \rfloor} \mathcal{F}_{1,n}(g) - \mathcal{F}_{j,n}(g)$ are at least of the order of $n$. Corollary 4.3 will then follow directly from Theorem 4.1 and Lemma 4.2. Recall that the $m$-th coefficient Fourier transform is defined as

$$ \mathcal{F}_{m,n}(g) = \sum_{j=0}^{n-1} g\left(j\frac{2\pi}{n}\right) \cos\left(j\frac{2\pi m}{n}\right). $$

For simplicity, we only consider the case where $n$ is odd – the case of even $n$ being similar. Let $n = 2p+1$ with $p \ge 2$. Using the fact that $g(x) = 1 - x/(2\pi)$, we get

$$ \mathcal{F}_{m,n}(g) = 1 + 2 \sum_{j=1}^{p} \left(1 - \frac{j}{n}\right) \cos\left(j \frac{2\pi m}{n}\right), \quad m = 0, \dots, p. \qquad (79) $$

For convenience, $\mathcal{F}_{m,n}(g)$ is denoted by $\alpha_m$ in the sequel. Let us show that, for $n$ large enough, $(\alpha_0 - \alpha_1) \gtrsim n$ and $\min_{m \ge 2}(\alpha_1 - \alpha_m) \gtrsim n$. For $m = 0$,

$$ \alpha_0 = 1 + 2p - \frac{2}{n} \sum_{j=1}^{p} j = 1 + 2p - \frac{p(p+1)}{n} = n - \frac{(n-1)(n+1)}{4n} = \frac{3n}{4} + \frac{1}{4n}. \quad (80) $$

For $m \ge 1$, we can still work out explicitly $\alpha_m$.

$$ \alpha_m = -2 \sum_{j=0}^{p} \frac{j}{n} \cos \left( j \frac{2\pi m}{n} \right) = -\frac{2}{n} \operatorname{Re} \left[ \sum_{j=1}^{p} j e^{i j 2\pi m / n} \right] \quad (81) $$
$$ = -\frac{2}{n} \mathrm{Re} \left[ -\iota f' \left( \frac{2\pi m}{n} \right) \right], $$

where the function $f$ is defined as $f(x) := \sum_{j=0}^{p} e^{i\ell jx} = \frac{e^{i(p+1)x}-1}{e^{i x}-1}$ for $x \in (0, \pi)$. We work out $f'(x)$:

$$ \begin{aligned} -\iota f'(x) &= \frac{(p+1)e^{i(p+1)x}(e^{i\ell x}-1) - e^{i\ell x}(e^{i(p+1)x}-1)}{(e^{i\ell x}-1)^2} \\ &= -\frac{(p+1)e^{i\ell p x}(e^{i\ell x}-1) - (e^{i\ell(p+1)x}-1)}{4 \sin^2(x/2)}, \\ &= -\iota \frac{(p+1)e^{i\ell(p+\frac{1}{2})x} \sin(\frac{x}{2}) - e^{i\ell\frac{p+1}{2}x} \sin(\frac{p+1}{2}x)}{2 \sin^2(x/2)}, \end{aligned} $$

where the second line follows from $(e^{i\ell x} - 1)^2 = -4 \sin^2(x/2)e^{i\ell x}$. Hence,

$$ \mathrm{Re}[-\iota f'(x)] = \frac{(p+1) \sin\left((p+\frac{1}{2})x\right) \sin\left(\frac{x}{2}\right) - \sin^2\left(\frac{p+1}{2}x\right)}{2 \sin^2(x/2)}. $$

Taking $x_m = \frac{2\pi m}{n}$, the first term of the numerator is equal to zero since $\sin((p+\frac{1}{2})x_m) = \sin(\pi m) = 0$. Then, combining the above with (81) yields

$$ \alpha_m = -\frac{2}{n} \mathrm{Re} \left[ -\iota f' \left( \frac{2\pi m}{n} \right) \right] = \frac{\sin^2\left(\frac{p+1}{2}x_m\right)}{n \sin^2\left(\frac{\pi m}{n}\right)}. $$

Since $\frac{p+1}{2}x_m = m\frac{\pi}{2} + m\frac{\pi}{2n}$,

$$ \alpha_m = \begin{cases} \frac{\cos^2\left(\frac{m\pi}{2n}\right)}{n \sin^2\left(\frac{n\pi}{2n}\right)} & \text{if } m \text{ is odd,} \\ \frac{\sin^2\left(\frac{m\pi}{2n}\right)}{n \sin^2\left(\frac{n\pi}{2n}\right)} & \text{if } m \text{ is even.} \end{cases} $$

Hence, the sequence of eigenvalues with odd indices is decreasing:

$$ \alpha_1 > \alpha_3 > \alpha_5 > \dots > \dots, $$

since the fraction $\cos^2(m\pi/2n)/\sin^2(\pi m/n)$ decreases with $m \in [p]$. In the (re-maining) case of even indices, the numerator can be upper bounded as follows: $\sin^2(m\pi/2n) \le \sin^2(\pi/4) \le \min_{k \in [p]} \cos^2(k\pi/2n)$, which leads to $\alpha_{2r} \le \alpha_{2r-1}$ for all $r = 1, \dots, \lfloor p/2 \rfloor$.

In other words, each eigenvalue of even index is upper bounded by the previous eigenvalue. In light of this, we only need to prove that, for $n$ large enough,

$$ (\alpha_0 - \alpha_1) \wedge (\alpha_1 - \alpha_2) \wedge (\alpha_1 - \alpha_3) \gtrsim n. $$

From (80), we deduce that $\alpha_0$ is equivalent to $3n/4$. Besides, we deduce from the explicit form of $\alpha_m$ in the general case that $\alpha_1, \alpha_2$, and $\alpha_3$ are respectively equivalent to $n/\pi^2$, $1/(4n)$, and $n/(4\pi^2)$. This completes the proof. $\square$
### D.7. Proof of Proposition 4.4

For the first inequality of the proposition, the proof is the same as for Proposition D.1, after replacing $\hat{x}_S^{VSA}$, $x_S^*$, $A_{SS}$ respectively by $\hat{x}^{VSA}$, $x^*$, A. The second inequality of the proposition follows from Lemma 4.2. □

## Appendix E: Probabilistic inequalities

We recall Hoeffding inequality for hypergeometric distributions.

**Lemma E.1.** For $N \ge 1$, $p \in [0, 1]$ and $n \ge N$, let X be a hypergeometric random variable with parameters $(N, p, n)$. Then, for all $t > 0$,

$$ \mathbb{P} \left( |X - Np| \ge \sqrt{\frac{Nt}{2}} \right) \le 2e^{-t}. \qquad (82) $$

## References

[1] ARIAS-CASTRO, E., JAVANMARD, A. and PELLETIER, B. (2020). Perturbation bounds for procrustes, classical scaling, and trilateration, with applications to manifold learning. *Journal of Machine Learning Research* **21** 15–1. MR4071198

[2] ATHREYA, A., TANG, M., PARK, Y. and PRIEBE, C. E. (2021). On estimation and inference in latent structure random graphs. *Statistical Science* **36** 68–88. MR4194204

[3] ATKINS, J. E., BOMAN, E. G. and HENDRICKSON, B. (1998). A spectral algorithm for seriation and the consecutive ones problem. *SIAM Journal on Computing* **28** 297–310. MR1630473

[4] BALLINGER, T. P. and WILCOX, N. T. (1997). Decisions, error and heterogeneity. *The Economic Journal* **107** 1090–1105. https://doi.org/10.1111/j.1468-0297.1997.tb00009.x

[5] BARNARD, S. T., POTHEN, A. and SIMON, H. (1995). A spectral algorithm for envelope reduction of sparse matrices. *Numerical linear algebra with applications* **2** 317–334. MR1349276

[6] BRADLEY, R. A. and TERRY, M. E. (1952). Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons. *Biometrika* **39** 324–345. MR0070925

[7] CHEN, K. and LEI, J. (2018). Network cross-validation for determining the number of communities in network data. *Journal of the American Statistical Association* **113** 241–251. MR3803461

[8] CHEN, Y., FAN, J., MA, C. and WANG, K. (2019). Spectral method and regularized MLE are both optimal for top-K ranking. *The Annals of Statistics* **47** 2204–2235. MR3953449

[9] CHEN, Y. and SUH, C. (2015). Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons. In *Proceedings of the 32nd International Con-
ference on Machine Learning (F. BACH and D. BLEI, eds.). *Proceedings of Machine Learning Research* **37** 371–380. PMLR, Lille, France.

[10] COIFMAN, R. R., SHKOLNISKY, Y., SIGWORTH, F. J. and SINGER, A. (2008). Graph Laplacian Tomography From Unknown Random Projections. *IEEE Transactions on Image Processing* **17** 1891–1899. MR2517273

[11] DE CASTRO, Y., LACOUR, C. and NGOC, T. M. P. (2017). Adaptive estimation of nonparametric geometric graphs. arXiv preprint arXiv:1708.02107. MR4165265

[12] DIACONIS, P. and JANSON, S. (2007). Graph limits and exchangeable random graphs. arXiv preprint arXiv:0712.2749. MR2463439

[13] DIAZ, J., MCDIARMID, C. and MITSCHE, D. (2020). Learning random points from geometric graphs or orderings. *Random Structures & Algorithms* **57** 339–370. MR4129724

[14] ELSON, J., KARP, R. M., PAPADIMITRIOU, C. H. and SHENKER, S. (2004). Global Synchronization in Sensornets. In *LATIN 2004: Theoretical Informatics* (M. FARACH-COLTON, ed.) 609–624. Springer Berlin Heidelberg, Berlin, Heidelberg. MR2095234

[15] FOGEL, F., JENATTON, R., BACH, F. and D'ASPREMONT, A. (2013). Convex relaxations for permutation problems. In *Advances in Neural Information Processing Systems* 1016–1024. MR3418224

[16] FULKERSON, D. and GROSS, O. (1965). Incidence matrices and interval graphs. *Pacific journal of mathematics* **15** 835–855. MR0186421

[17] GAO, C., MA, Z., ZHANG, A. Y. and ZHOU, H. H. (2017). Achieving optimal misclassification proportion in stochastic block models. *The Journal of Machine Learning Research* **18** 1980–2024. MR3687603

[18] GAO, C. and ZHANG, A. Y. (2019). Iterative algorithm for discrete structure recovery. arXiv preprint arXiv:1911.01018.

[19] GAO, C. and ZHANG, A. Y. (2020). Exact Minimax Estimation for Phase Synchronization. arXiv preprint arXiv:2010.04345. MR4346085

[20] GARRIGA, G. C., JUNTTILA, E. and MANNILA, H. (2011). Banded structure in binary matrices. *Knowledge and information systems* **28** 197–226.

[21] GILBERT, E. N. (1961). Random Plane Networks. *Journal of the Society for Industrial and Applied Mathematics* **9** 533–543. MR0132566

[22] GIRIDHAR, A. and KUMAR, P. R. (2006). Distributed Clock Synchronization over Wireless Networks: Algorithms and Analysis. In *Proceedings of the 45th IEEE Conference on Decision and Control* 4915–4920.

[23] GRAY, R. M. (2006). *Toeplitz and circulant matrices: A review*. now publishers inc.

[24] HOFF, P. D., RAFTERY, A. E. and HANDCOCK, M. S. (2002). Latent space approaches to social network analysis. *Journal of the american Statistical association* **97** 1090–1098. MR1951262

[25] JANSSEN, J. and SMITH, A. (2020). Reconstruction of Line-Embeddings of Graphons. arXiv preprint arXiv:2007.06444. MR4361745

[26] LEI, J. and ZHU, L. (2014). A generic sample splitting approach for refined community recovery in stochastic block models. arXiv preprint arXiv:1411.1469. MR3701502
[27] LOVÁSZ, L. (2012). *Large networks and graph limits* **60**. American Mathematical Soc. MR3012035

[28] LYZINSKI, V., TANG, M., ATHREYA, A., PARK, Y. and PRIEBE, C. E. (2017). Community Detection and Classification in Hierarchical Stochastic Blockmodels. *IEEE Transactions on Network Science and Engineering* **4** 13–26. MR3625952

[29] NEGAHBAN, S., OH, S. and SHAH, D. (2017). Rank Centrality: Ranking from Pairwise Comparisons. *Operations Research* **65** 266–287. MR3613103

[30] PENROSE, M. (2003). *Random geometric graphs* **5**. Oxford university press. MR1986198

[31] QUEYRANNE, M. (1986). Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems. *Operations Research Letters* **4** 231–234. https://doi.org/10.1016/0167-6377(86)90007-6 MR0829886

[32] RECANATI, A., BRÜLS, T. and D'ASPREMONT, A. (2017). A spectral algorithm for fast de novo layout of uncorrected long nanopore reads. *Bioinformatics* **33** 3188–3194.

[33] RECANATI, A., KERDREUX, T. and D'ASPREMONT, A. (2018). Reconstructing Latent Orderings by Spectral Clustering. arXiv preprint arXiv:1807.07122.

[34] ROBINSON, W. S. (1951). A Method for Chronologically Ordering Archaeological Deposits. *American Antiquity* **16** 293–301.

[35] SAHNI, S. and GONZALEZ, T. (1976). P-Complete Approximation Problems. *J. ACM* **23** 555–565. MR0408313

[36] SHAH, N., BALAKRISHNAN, S., GUNTUBOYINA, A. and WAINWRIGHT, M. (2016). Stochastically transitive models for pairwise comparisons: Statistical and computational issues. In *International Conference on Machine Learning* 11–20. MR3604649

[37] SINGER, A. (2011). Angular synchronization by eigenvectors and semidefinite programming. *Applied and computational harmonic analysis* **30** 20–36. MR2737931

[38] SUSSMAN, D. L., TANG, M. and PRIEBE, C. E. (2013). Consistent latent position estimation and vertex classification for random dot product graphs. *IEEE transactions on pattern analysis and machine intelligence* **36** 48–57.

[39] TAO, T. (2012). *Topics in random matrix theory* **132**. American Mathematical Soc. MR2906465

[40] VERSHYNIN, R. (2018). *High-dimensional probability: An introduction with applications in data science* **47**. Cambridge university press. MR3837109

[41] YU, B. (1997). Assouad, Fano, and le Cam. In *Festschrift for Lucien Le Cam* 423–435. Springer. MR1462963

[42] YU, Y., WANG, T. and SAMWORTH, R. J. (2015). A useful variant of the Davis–Kahan theorem for statisticians. *Biometrika* **102** 315–323. MR3371006

[43] ZHANG, A. Y. and ZHOU, H. H. (2016). Minimax rates of community detection in stochastic block models. *The Annals of Statistics* **44** 2252–2280. MR3546450