retrieval (Candès et al., 2013), computer vision (Tomasi and Kanade, 1992; Özyeşil et al., 2017) and sensor network localization (Cucuringu et al., 2012a) to name a few.

More formally, let us assume for simplicity that $r = O(1)$ and the SVD of $C = \sum_{i \in [r]} \sigma_i u_i v_i^T$ satisfies

$$ \|u_i\|_{\infty} \le \sqrt{\frac{\mu}{n_1}}, \quad \|v_i\|_{\infty} \le \sqrt{\frac{\mu}{n_2}}; \quad \forall i, j, \qquad (6.1) $$

for some $\mu \ge 1$. Here, $\mu$ is a coherence parameter which measures how spread out the entries of $u_i, v_i$ are - the smaller the value of $\mu$, the better. Say we observe $m$ entries of $C$ on a subset $\Omega \subset [n_1] \times [n_2]$, sampled uniformly at random. Denoting $P_{\Omega}: \mathbb{R}^{n_1 \times n_2} \to \mathbb{R}^{n_1 \times n_2}$ to be the projection operator on $\Omega$, it was shown in Candès and Tao (2010) that the solution $\hat{C}$ of

$$ \min \|X\|_* \quad \text{s.t} \quad P_{\Omega}(X) = P_{\Omega}(C) \qquad (6.2) $$

equals $C$ with high probability, provided $m = \Omega(\mu^4 n \log^2 n)$. The nuclear norm minimization problem (6.2) is a SDP and hence can be solved in polynomial time using, for eg., interior point methods. In fact, the result holds under a different Bernoulli sampling model too, wherein each entry of $M$ is observed independently with a certain probability (Candès and Recht, 2009, Section 4.1). Moreover, say that the observations are noisy, i.e, we observe

$$ Y_{i,j} = C_{i,j} + Z_{i,j}; \quad (i, j) \in \Omega \Leftrightarrow P_{\Omega}(Y) = P_{\Omega}(C) + P_{\Omega}(Z), $$

where $Z$ is the noise matrix. Say $\|P_{\Omega}(Z)\|_F \le \delta$. Then, it was shown in Candès and Plan (2010) (under certain additional conditions) that the solution of

$$ \min \|X\|_* \quad \text{s.t} \quad \|P_{\Omega}(X) - P_{\Omega}(Y)\|_F \le \delta, \qquad (6.3) $$

is stable, i.e., the estimation error $\|\hat{C} - C\|_F$ is bounded by a term proportional to $\delta$.

In our setting, we observe (noisy versions of) a subset of the entries of the $n \times n$ matrix $C = re^T - er^T$ where each off-diagonal entry of $C$ is revealed with probability $p$. Since $C$ has rank 2, it is natural to consider estimating $C$ via matrix completion as a preprocessing step, and then subsequently applying SVD-RS or SVD-NRS on the obtained estimate of $C$ for recovering the underlying ranks and scores. In order to understand the sample complexity for successful matrix completion, we need to express $\mu$ defined in (6.1) in terms of the score vector $r$. To this end, we see from Lemma 11 that

$$ \|u_2\|_{\infty}, \|v_1\|_{\infty} = \frac{\|r - \alpha e\|_{\infty}}{\|r - \alpha e\|_2} \le \frac{M - \alpha}{\|r - \alpha e\|_2}, $$

and $\|u_1\|_{\infty}, \|v_2\|_{\infty} = 1/\sqrt{n}$. Hence it follows that

$$ \mu = \max \left\{ \frac{(M - \alpha)\sqrt{n}}{\|r - \alpha e\|_2}, 1 \right\}. $$

In order to get a sense of the scaling of $\mu$, consider the setting $r_i = i$. As seen before, we then have $\|r - \alpha e\|_2 = \Theta(n^{3/2})$, $M = n$, and $\alpha = \Theta(n)$. This in turn implies that $\mu = \Theta(1)$ which is the ideal scenario for matrix completion. In our numerical experiments,
we rely on the TFOCS software library (Becker et al.), that allows for construction of first-order methods for a variety of convex optimization problems (Becker et al., 2011). In our implementation, we also set the diagonal entries of X to be equal to zero since the same is true for C. We do not enforce the skew-symmetry constraints $X_{ij} = -X_{ji}$ for $(i, j) \in \Omega$, so the solution $\hat{C}$ to C is not guaranteed to be skew-symmetric. Instead, we output $\frac{\hat{C}-\hat{C}^T}{2}$ as the final (skew-symmetric) estimate obtained from the preprocessing step. Note that since $C^T = -C$, we have

$$ \left\| \frac{\hat{C} - \hat{C}^T}{2} - C \right\|_F = \left\| \frac{\hat{C} - \hat{C}^T - C + C^T}{2} \right\|_F \le \|C - \hat{C}\|_F. $$

**Remark 20** Note that in the setting of matrix completion, we perform the scaling recovery procedure outlined in Section 3.2 as follows. We build the matrix $\Pi$ from equation (3.2) by only consider the entries/edges $\{i, j\} \in E$ from the original measurement graph G, and do not include the entries filled in during the matrix completion step.

Finally, we end with a motivating discussion for the applicability of the matrix completion approach in the setting of ranking from pairwise comparisons. The recent work of Udell and Townsend (2019) provides a compelling argument on why big data matrices are approximately low-rank. The authors consider a simple generative model for matrices, assuming that each row or column is associated to a (possibly high dimensional) bounded latent variable, with the individual matrix entries being generated by applying a piecewise analytic function to these latent variables. While the initial resulting matrices are typically full rank, the authors show that one can approximate every entry of an $m \times n$ matrix drawn from the above model to within a fixed absolute error by a low-rank matrix whose rank grows as $O(\log(m + n))$. In other words, any sufficiently large matrix from such a latent variable model can be approximated by a low-rank matrix (up to a small entrywise error). The paradigm that “nice latent variables models are of log-rank” (Udell and Townsend, 2019) is also applicable in the ranking setting, where one assumes that the final ranking (or skill) of each player varies smoothly as a function of covariate information, which is typically available in many real world applications. For example, in sport or clinical data, covariates may provide additional information about both the ranked players and the rankers/judges, which can overall lead to better aggregated results.

## 7. Numerical Experiments

We compare the performance of Algorithm 1 SVD-RS (SVD in the figure legends for brevity) and Algorithm 2 SVD-NRS (SVD-N in the figure legends) with that of seven other algorithms from the literature, namely ROWSUM RANKING (RSUM) (Gleich and Lim, 2011), LEAST-SQUARES-RANK (LS) as considered in Cucuringu (2016), SERIAL-RANK (SER) (Fogel et al., 2016), SPRING-RANK (SPR) (De Bacco et al., 2018), BRADLEY-TERRY (BTL) (Bradley and Terry, 1952), PAGE-RANK (PGR) (Page et al., 1998), and SYNC-RANK (SYNC) (Cucuringu, 2016). We refer the reader to Section 2.2 for a brief survey of the ranking literature, including the above algorithms. We compare the performance of all algorithms on synthetic data in Section 7.1, and on real data in Section 7.2. We
we rely on the TFOCS software library (Becker et al.), that allows for construction of first-order methods for a variety of convex optimization problems (Becker et al., 2011). In our implementation, we also set the diagonal entries of $X$ to be equal to zero since the same is true for $C$. We do not enforce the skew-symmetry constraints $X_{ij} = -X_{ji}$ for $(i, j) \in \Omega$, so the solution $\hat{C}$ to $C$ is not guaranteed to be skew-symmetric. Instead, we output $\frac{\hat{C}-\hat{C}^T}{2}$ as the final (skew-symmetric) estimate obtained from the preprocessing step. Note that since $C^T = -C$, we have

$$ \left\| \frac{\hat{C} - \hat{C}^T}{2} - C \right\|_F = \left\| \frac{\hat{C} - \hat{C}^T - C + C^T}{2} \right\|_F \le \|C - \hat{C}\|_F. $$

**Remark 20** Note that in the setting of matrix completion, we perform the scaling recovery procedure outlined in Section 3.2 as follows. We build the matrix $\Pi$ from equation (3.2) by only consider the entries/edges $\{i, j\} \in E$ from the original measurement graph $G$, and do not include the entries filled in during the matrix completion step.

Finally, we end with a motivating discussion for the applicability of the matrix completion approach in the setting of ranking from pairwise comparisons. The recent work of Udell and Townsend (2019) provides a compelling argument on why big data matrices are approximately low-rank. The authors consider a simple generative model for matrices, assuming that each row or column is associated to a (possibly high dimensional) bounded latent variable, with the individual matrix entries being generated by applying a piecewise analytic function to these latent variables. While the initial resulting matrices are typically full rank, the authors show that one can approximate every entry of an $m \times n$ matrix drawn from the above model to within a fixed absolute error by a low-rank matrix whose rank grows as $O(\log(m + n))$. In other words, any sufficiently large matrix from such a latent variable model can be approximated by a low-rank matrix (up to a small entrywise error). The paradigm that “nice latent variables models are of log-rank” (Udell and Townsend, 2019) is also applicable in the ranking setting, where one assumes that the final ranking (or skill) of each player varies smoothly as a function of covariate information, which is typically available in many real world applications. For example, in sport or clinical data, covariates may provide additional information about both the ranked players and the rankers/judges, which can overall lead to better aggregated results.

## 7. Numerical Experiments

We compare the performance of Algorithm 1 SVD-RS (SVD in the figure legends for brevity) and Algorithm 2 SVD-NRS (SVD-N in the figure legends) with that of seven other algorithms from the literature, namely ROWSUM RANKING (RSUM) (Gleich and Lim, 2011), LEAST-SQUARES-RANK (LS) as considered in Cucuringu (2016), SERIAL-RANK (SER) (Fogel et al., 2016), SPRING-RANK (SPR) (De Bacco et al., 2018), BRADLEY-TERRY (BTL) (Bradley and Terry, 1952), PAGE-RANK (PGR) (Page et al., 1998), and SYNC-RANK (SYNC) (Cucuringu, 2016). We refer the reader to Section 2.2 for a brief survey of the ranking literature, including the above algorithms. We compare the performance of all algorithms on synthetic data in Section 7.1, and on real data in Section 7.2. We
consider a variety of performance metrics summarized further below, altogether highlighting
the competitiveness of our proposed SVD-based algorithms with that of state-of-the-art
methods.

7.1 Synthetic data

This section details the outcomes of synthetic numerical experiments, under the ERO model,
where the measurement graph is Erdős-Rényi and the noise comes in the form of outliers
from a uniform distribution.

We consider two sets of experiments, a first one where the strengths $r_i$ are uniformly
distributed in $[0, 1]$, and a second one where they are Gamma distributed with shape pa-
rameter $a = 0.5$ and scale parameter $b = 1$. This choice of parameters for the Gamma
distribution leads to a skewed distribution of player strengths, and subsequently a skewed
distribution of node degrees, which is a setting realistic in practice but known to be chal-
lenging for spectral methods. We fix the number of nodes ($n$), and vary the edge density
($p$), and noise level ($\gamma$) as follows.

We broadly consider two main experimental settings.

* In Figure 2 (uniform scores) and Figure 3 (Gamma scores) we consider a synthetic model with $n = 1000$, with sparsity parameters $p = 0.05$ (column 1) and $p = 1$ (column 3). For the $p = 0.05$ scenario, we also show the results after running all algorithms on top of a reprocessing step that applies low-rank matrix completion (column 2).

* In Figure 4 (uniform scores) and Figure 5 (Gamma scores), we consider a synthetic model with $n = 3000$, and sparsity parameter $p \in \{0.01, 0.05, 0.1\}$, indexing the columns.

Across all the above experiments, we consider three different performance metrics, as we vary the noise level $\gamma$ on the x-axis. Whenever ground truth is available, we plot in the top row of Figures 2, 3, 4, 5 the *Kendall Distance* between the recovered strength vector $\hat{r}$ and the ground truth $r$, for different noise levels $\gamma$. The Kendall distance counts the number of pairs of candidates that are ranked in different order (flips), in the original ranking versus the recovered one. The middle row of each Figure plots the *Correlation Score*, computed as the Pearson correlation between the ground truth $r$ and the recovered $\hat{r}$. Finally, the bottom row in each Figure plots the *RMSE* error, defined as $\sqrt{\frac{1}{n}||r - \hat{r}||_2^2}$, after having centered $r$ and $\hat{r}$. Note that the low-rank matrix completion is illustrated in the middle column of Figures 2 and 3.

**Performance comparison.** For the remainder of this section, we compare and contrast
the performance of our algorithms with that of the other methods, across four synthetic
data sets, detailed below.

* In Figure 2 (uniform scores with $n = 1000$): in the setting $p = 0.05$, our methods perform better than SER but are in general outperformed by the other methods in terms of Kendall Distance (KD) and Correlation Score (CS) (except at very low levels of noise), and they perform on par with all the methods in terms of RMSE (in particular for $\gamma > 0.30$ our methods outperform SER, PGR, BTL, and SPR). After the matrix completion step, both SVD and SVD-N outperform all other methods except LS and RSUM in terms of
consider a variety of performance metrics summarized further below, altogether highlighting
the competitiveness of our proposed SVD-based algorithms with that of state-of-the-art
methods.

7.1 Synthetic data

This section details the outcomes of synthetic numerical experiments, under the ERO model,
where the measurement graph is Erdős-Rényi and the noise comes in the form of outliers
from a uniform distribution.

We consider two sets of experiments, a first one where the strengths $r_i$ are uniformly
distributed in $[0, 1]$, and a second one where they are Gamma distributed with shape pa-
rameter $a = 0.5$ and scale parameter $b = 1$. This choice of parameters for the Gamma
distribution leads to a skewed distribution of player strengths, and subsequently a skewed
distribution of node degrees, which is a setting realistic in practice but known to be chal-
lenging for spectral methods. We fix the number of nodes ($n$), and vary the edge density
($p$), and noise level ($\gamma$) as follows.

We broadly consider two main experimental settings.

* In Figure 2 (uniform scores) and Figure 3 (Gamma scores) we consider a synthetic model with $n = 1000$, with sparsity parameters $p = 0.05$ (column 1) and $p = 1$ (column 3). For the $p = 0.05$ scenario, we also show the results after running all algorithms on top of a reprocessing step that applies low-rank matrix completion (column 2).

* In Figure 4 (uniform scores) and Figure 5 (Gamma scores), we consider a synthetic model with $n = 3000$, and sparsity parameter $p \in \{0.01, 0.05, 0.1\}$, indexing the columns.

Across all the above experiments, we consider three different performance metrics, as we vary the noise level $\gamma$ on the x-axis. Whenever ground truth is available, we plot in the top row of Figures 2, 3, 4, 5 the *Kendall Distance* between the recovered strength vector $\hat{r}$ and the ground truth $r$, for different noise levels $\gamma$. The Kendall distance counts the number of pairs of candidates that are ranked in different order (flips), in the original ranking versus the recovered one. The middle row of each Figure plots the *Correlation Score*, computed as the Pearson correlation between the ground truth $r$ and the recovered $\hat{r}$. Finally, the bottom row in each Figure plots the *RMSE* error, defined as $\sqrt{\frac{1}{n}||r - \hat{r}||_2^2}$, after having centered $r$ and $\hat{r}$. Note that the low-rank matrix completion is illustrated in the middle column of Figures 2 and 3.

**Performance comparison.** For the remainder of this section, we compare and contrast
the performance of our algorithms with that of the other methods, across four synthetic
data sets, detailed below.

* In Figure 2 (uniform scores with $n = 1000$): in the setting $p = 0.05$, our methods perform better than SER but are in general outperformed by the other methods in terms of Kendall Distance (KD) and Correlation Score (CS) (except at very low levels of noise), and they perform on par with all the methods in terms of RMSE (in particular for $\gamma > 0.30$ our methods outperform SER, PGR, BTL, and SPR). After the matrix completion step, both SVD and SVD-N outperform all other methods except LS and RSUM in terms of
RMSE, to which they are comparable (visually indistinguishable) up until $\gamma < 0.50$, and only slightly outperformed for higher noise. In terms of KD and CS, our two SVD-based algorithms perform on par with most other methods, and clearly outperform both SER and PGR. Finally, for the complete graph case $p = 1$, our methods perform at the top of the rankings in terms of KD, CS, and RMSE, and are only matched in performance or slightly outperformed depending on the noise regime, by SYNC, LS, and RSUM.

* In Figure 3 (Gamma scores with $n = 1000$): for the very sparse regime SYNC clearly outperforms all other methods, with the SVD-based methods outperforming only SER. After the matrix completion step, our proposed algorithms outperform all other methods except LS and RSUM. For the complete graph case, SYNC is by far the winner in terms of KD, with the remaining methods performing comparably, except PGR. In terms of RMSE, our methods perform best along with LS and RSUM, and clearly outperform SYNC, SPR, PGR, BTL and SER.

* In Figure 4 (uniform scores with $n = 3000$): for $p = 0.01$ there is very clear ordering of the methods, mostly consistent across all three performance metrics. We observe that SYNC, SPR, RSUM, and LS, are the top three best performing methods, followed by BTL, PGR, SVD, SVD-N, and SER. At slightly higher edge density $p = 0.05$, our SVD methods perform better than SER, PGR, and BTL, for the first part of the noise spectrum, while in terms of RMSE, SVD and SVD-N clearly outperform SER, PGR, BTL, SPR, and SYNC, and are surpassed only by LS and RSUM. The relative performance is similar for $p = 0.10$.

* Finally, we comment on the results from Figure 5 (Gamma scores with $n = 3000$): for $p = 0.01$, SYNC is the clear winner in terms of KD, CS, and RMSE, while SER, SVD and SVD-N are at the bottom of the ranking. The relative ordering is roughly preserved for higher edge densities, with the comment that SER is clearly the worst performer, while SYNC is by far the most accurate method, especially in terms of KD, where it outperforms all other methods by a large margin.

## 7.2 Real data

We also apply all ranking algorithms to a variety of real world networks, and measure the performance of the outcome by the number of upsets in the final ranking, computed with respect to the given pairwise measurements. To this end, we consider two types of upsets, as detailed below. Let $\hat{r}_i$ denote the estimated score of item $i$ as computed by the method of choice. Note that higher values of $\hat{r}_i$ correspond to higher ranks, meaning stronger players or more preferred items. Next, we construct the induced (possibly incomplete) matrix of estimated/denoised pairwise rank-offssets

$$ \hat{R}_{ij} = \begin{cases} \hat{r}_i - \hat{r}_j; & \text{if } \{i, j\} \in E \\ 0; & \text{if } (i, j) \notin E, \end{cases} $$

with $\hat{R}_{ij} > 0$ denoting that the rank of player $i$ is higher than the rank of player $j$. To measure the accuracy of a proposed reconstruction, we rely on the following two metrics.
RMSE, to which they are comparable (visually indistinguishable) up until $\gamma < 0.50$, and only slightly outperformed for higher noise. In terms of KD and CS, our two SVD-based algorithms perform on par with most other methods, and clearly outperform both SER and PGR. Finally, for the complete graph case $p = 1$, our methods perform at the top of the rankings in terms of KD, CS, and RMSE, and are only matched in performance or slightly outperformed depending on the noise regime, by SYNC, LS, and RSUM.

* In Figure 3 (Gamma scores with $n = 1000$): for the very sparse regime SYNC clearly outperforms all other methods, with the SVD-based methods outperforming only SER. After the matrix completion step, our proposed algorithms outperform all other methods except LS and RSUM. For the complete graph case, SYNC is by far the winner in terms of KD, with the remaining methods performing comparably, except PGR. In terms of RMSE, our methods perform best along with LS and RSUM, and clearly outperform SYNC, SPR, PGR, BTL and SER.

* In Figure 4 (uniform scores with $n = 3000$): for $p = 0.01$ there is very clear ordering of the methods, mostly consistent across all three performance metrics. We observe that SYNC, SPR, RSUM, and LS, are the top three best performing methods, followed by BTL, PGR, SVD, SVD-N, and SER. At slightly higher edge density $p = 0.05$, our SVD methods perform better than SER, PGR, and BTL, for the first part of the noise spectrum, while in terms of RMSE, SVD and SVD-N clearly outperform SER, PGR, BTL, SPR, and SYNC, and are surpassed only by LS and RSUM. The relative performance is similar for $p = 0.10$.

* Finally, we comment on the results from Figure 5 (Gamma scores with $n = 3000$): for $p = 0.01$, SYNC is the clear winner in terms of KD, CS, and RMSE, while SER, SVD and SVD-N are at the bottom of the ranking. The relative ordering is roughly preserved for higher edge densities, with the comment that SER is clearly the worst performer, while SYNC is by far the most accurate method, especially in terms of KD, where it outperforms all other methods by a large margin.

## 7.2 Real data

We also apply all ranking algorithms to a variety of real world networks, and measure the performance of the outcome by the number of upsets in the final ranking, computed with respect to the given pairwise measurements. To this end, we consider two types of upsets, as detailed below. Let $\hat{r}_i$ denote the estimated score of item $i$ as computed by the method of choice. Note that higher values of $\hat{r}_i$ correspond to higher ranks, meaning stronger players or more preferred items. Next, we construct the induced (possibly incomplete) matrix of estimated/denoised pairwise rank-offsets

$$ \hat{R}_{ij} = \begin{cases} \hat{r}_i - \hat{r}_j; & \text{if } \{i, j\} \in E \\ 0; & \text{if } (i, j) \notin E, \end{cases} $$

with $\hat{R}_{ij} > 0$ denoting that the rank of player $i$ is higher than the rank of player $j$. To measure the accuracy of a proposed reconstruction, we rely on the following two metrics.
<figure><img src="image_5.png" /><figcaption>Figure 2: Performance statistics in terms of Kendall distance (top row; lower is better), correlation score (middle row; higher is better), and RMSE (bottom row; lower is better), for synthetic data with scores generated from a **Uniform** distribution with $n = 1000$. The first and third columns pertain to the case of sparsity $p = 0.05$, respectively $p = 1$, without the matrix completion step, while the middle column, for $p = 0.05$, employs a matrix-completion preprocessing step. Results are averaged over 20 runs.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 2: Performance statistics in terms of Kendall distance (top row; lower is better), correlation score (middle row; higher is better), and RMSE (bottom row; lower is better), for synthetic data with scores generated from a **Uniform** distribution with $n = 1000$. The first and third columns pertain to the case of sparsity $p = 0.05$, respectively $p = 1$, without the matrix completion step, while the middle column, for $p = 0.05$, employs a matrix-completion preprocessing step. Results are averaged over 20 runs.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 3: Performance statistics in terms of Kendall distance (top row), correlation score (middle row), and RMSE (bottom row), for synthetic data with scores generated from a **Gamma** distribution with $n = 1000$. The first and third columns pertain to the case of sparsity $p = 0.05$, respectively $p = 1$ without the matrix completion step, while the middle column, for $p = 0.05$, employs a matrix-completion preprocessing step. Results are averaged over 20 runs.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 3: Performance statistics in terms of Kendall distance (top row), correlation score (middle row), and RMSE (bottom row), for synthetic data with scores generated from a **Gamma** distribution with $n = 1000$. The first and third columns pertain to the case of sparsity $p = 0.05$, respectively $p = 1$ without the matrix completion step, while the middle column, for $p = 0.05$, employs a matrix-completion preprocessing step. Results are averaged over 20 runs.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 4: Performance statistics in terms of Kendall distance (top row), correlation score (middle row), and RMSE (bottom row), for synthetic data with scores generated by a **Uniform** distribution with $n = 3000$, and sparsity $p \in \{0.01, 0.05, 0.1\}$, without the matrix completion preprocessing step. Note that $\log(3000)/3000 \approx 0.00267$. Results are averaged over 20 runs.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 4: Performance statistics in terms of Kendall distance (top row), correlation score (middle row), and RMSE (bottom row), for synthetic data with scores generated by a **Uniform** distribution with $n = 3000$, and sparsity $p \in \{0.01, 0.05, 0.1\}$, without the matrix completion preprocessing step. Note that $\log(3000)/3000 \approx 0.00267$. Results are averaged over 20 runs.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 5: Performance statistics in terms of Kendall distance (top row), correlation score (middle row), and RMSE (bottom row), for synthetic data with scores generated by a **Gamma** distribution with *n* = 3000, and sparsity *p* ∈ {0.01, 0.05, 0.1}, without the matrix completion preprocessing step. Note that log(3000)/3000 = 0.00267. Results are averaged over 20 runs.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 5: Performance statistics in terms of Kendall distance (top row), correlation score (middle row), and RMSE (bottom row), for synthetic data with scores generated by a **Gamma** distribution with $n = 3000$, and sparsity $p \in \{0.01, 0.05, 0.1\}$, without the matrix completion preprocessing step. Note that $\log(3000)/3000 \approx 0.00267$. Results are averaged over 20 runs.</figcaption></figure>
First, we use the popular metric

$$ \text{Number of upsets} = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1_{\{\text{sign}(R_{ij}\hat{R}_{ij})=-1\}}, \qquad (7.1) $$

which counts the number of *upsets* (lower is better), i.e., the number of disagreeing ordered comparisons. It contributes a +1 to the summation whenever the ordering in the provided data contradicts the ordering in the induced ranking. Next, we define a weighted version of the upset criterion (lower is better) between the given rank comparison data, and the one induced by the recovered solution

$$ \text{Weighted upsets} = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} |R_{ij} - \hat{R}_{ij}|. \qquad (7.2) $$

For ease of visualization and comparison, in all the barplot figures shown in this section, we color in red (resp. blue) the outcomes attained by SVD (resp. SVD-N). For brevity, for each real data set, we primarily comment on the performance of the two SVD-based methods relative to the other seven methods. We compare performance both before and after the matrix completion step. In each scenario, we compute the above two performance metrics, hence the four columns in the five Figures 6, 8, 9, 10, 11 corresponding to the five real data sets we consider.

**NCAA College Basketball.** Our first and most comprehensive real data set comes from sports, and contains the outcomes of NCAA College Basketball matches during the regular season, for the years 1985 - 2014. Each separate season provided a pairwise comparison matrix on which we evaluate all algorithms. This data set can essentially be construed as 30 separate problem instances. The input matrix corresponding to each season contains the point difference of the direct match between a pair of teams. If the same pair of teams played multiple matches against each other, the point differences are added up. The resulting pairwise comparison matrix is thus skew-symmetric by construction.

The experimental results shown in the left column of Figure 6 pertain to the setting without the matrix completion step, while the right column compares the outcome of all methods after the low-rank matrix completion pre-processing step. The first row shows performance in terms of the number of upsets across time for each season, while the barplot in the second row shows the average attained by all methods across all seasons. Before matrix completion, SVD-N and SVD are ranked 6th, respectively 8th, while after matrix completion, they are ranked 6th, respectively 7th, out of the 9 algorithms considered. The third and fourth row depict similar results, but the performance metric used is the weighted upsets, which is shown on a log scale for ease of visualization, primarily due to the poor performance of BTL, which would otherwise distort the y-axis. In this case, SVD-N and SVD are ranked 5th, respectively 6th, while after matrix completion, they are ranked 4th, respectively 5th, out of 9 methods, visibly outperforming the rest of the methods, and attaining a comparable performance to that of the top three methods.

The heatmaps shown in the top row of Figure 7 contain the pairwise correlations between the rankings attained by all methods over the 30 seasons. In other words, for any pair of methods, we compute the correlation between the respective rankings attained in each
First, we use the popular metric

$$ \text{Number of upsets} = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1_{\{\text{sign}(R_{ij}\hat{R}_{ij})=-1\}}, \qquad (7.1) $$

which counts the number of *upsets* (lower is better), i.e., the number of disagreeing ordered comparisons. It contributes a +1 to the summation whenever the ordering in the provided data contradicts the ordering in the induced ranking. Next, we define a weighted version of the upset criterion (lower is better) between the given rank comparison data, and the one induced by the recovered solution

$$ \text{Weighted upsets} = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} |R_{ij} - \hat{R}_{ij}|. \qquad (7.2) $$

For ease of visualization and comparison, in all the barplot figures shown in this section, we color in red (resp. blue) the outcomes attained by SVD (resp. SVD-N). For brevity, for each real data set, we primarily comment on the performance of the two SVD-based methods relative to the other seven methods. We compare performance both before and after the matrix completion step. In each scenario, we compute the above two performance metrics, hence the four columns in the five Figures 6, 8, 9, 10, 11 corresponding to the five real data sets we consider.

**NCAA College Basketball.** Our first and most comprehensive real data set comes from sports, and contains the outcomes of NCAA College Basketball matches during the regular season, for the years 1985 - 2014. Each separate season provided a pairwise comparison matrix on which we evaluate all algorithms. This data set can essentially be construed as 30 separate problem instances. The input matrix corresponding to each season contains the point difference of the direct match between a pair of teams. If the same pair of teams played multiple matches against each other, the point differences are added up. The resulting pairwise comparison matrix is thus skew-symmetric by construction.

The experimental results shown in the left column of Figure 6 pertain to the setting without the matrix completion step, while the right column compares the outcome of all methods after the low-rank matrix completion pre-processing step. The first row shows performance in terms of the number of upsets across time for each season, while the barplot in the second row shows the average attained by all methods across all seasons. Before matrix completion, SVD-N and SVD are ranked 6th, respectively 8th, while after matrix completion, they are ranked 6th, respectively 7th, out of the 9 algorithms considered. The third and fourth row depict similar results, but the performance metric used is the weighted upsets, which is shown on a log scale for ease of visualization, primarily due to the poor performance of BTL, which would otherwise distort the y-axis. In this case, SVD-N and SVD are ranked 5th, respectively 6th, while after matrix completion, they are ranked 4th, respectively 5th, out of 9 methods, visibly outperforming the rest of the methods, and attaining a comparable performance to that of the top three methods.

The heatmaps shown in the top row of Figure 7 contain the pairwise correlations between the rankings attained by all methods over the 30 seasons. In other words, for any pair of methods, we compute the correlation between the respective rankings attained in each
season, which we then average over the entire set of 30 seasons. To the best of our knowledge, such a correlation study has not been performed in the literature, and provides insights on the potentially different latent rankings inherent in each data set, while still minimizing the number of upsets. SYNC, the best performing method in terms of the number of upsets, has a comparable performance to BTL, and a correlation of 86%. PGR and SVD-N attain a comparable number of upsets, but their Kendall score correlation is only 70%. The bottom barplot of the same Figure 7 show the average correlation of each of the methods, highlighting that SPR, LS and BTL yield the most correlated rankings with the other methods. A similar correlation analysis is performed on all rankings algorithms after the low-rank matrix completion step, which reveals a number of clusters. As expected, SVD and SVD-N produce very related rankings to each others, and similarly for RSUM and LS, and finally, SPR and BTL.

**Animal dominance network.** Our second real world example is a set of two networks of animal dominance among captive monk parakeets (Hobson and DeDeo, 2015). The input matrix $H$ is skew-symmetric, with $H_{ij}$ denoting the number of net aggressive wins of animal $i$ toward animal $j$. The study covers two groups (of 21, respectively, 19 individuals), and spans across four quarters. We follow the same approach as in De Bacco et al. (2018), and only tested the algorithms on Quarters 3 and 4, based on guidance from the behavioral ecologist who collected and analyzed the data. Since the animals did not know each other well at the start of the experiment, the hierarchies were still in the transient process of forming. Figure 8 compares performance in terms of the number of upsets and weighted upsets, with and without the matrix completion step. Overall, we observe that SVD-N outperforms SVD, and the two methods typically rank halfway in the performance ranking, except in the leftmost column, where SVD performs worst.

**Faculty hiring networks.** Our next example covers three North American academic hiring networks, that track the flow of academics between universities (Clauset et al., 2015). The flow is captured in a directed graph with adjacency matrix $A$, such that $A_{ij}$ is the number of faculty at university $j$ who received their doctorate from university $i$. We then consider the skew symmetric matrix $H = A - A^T$, capturing the net flow of faculty between a pair of institutions. Figure 9 shows the number of upsets attained by each algorithm, for three different disciplines: (a) Computer Science ($n = 206$), (b) Business ($n = 113$) and (c) History ($n = 145$), before and after the matrix completion step, for both upsets criteria. Again, we observe that SVD-N outperforms SVD. Furthermore, SVD-N typically ranks in the top half of the rankings, and for the case of weighted upsets after the matrix completion step, it is the best performer for the Business and History fields, and second best in Computer Science.

**Microsoft Halo 2 Tournament.** Our third experiment was performed on a real data set of game outcomes collected during the Beta testing period for the Xbox game^4 Halo 2. The graph has a total of $n = 606$ players, and 6227 head-to-head games. After removing the low-degree nodes, i.e., players who have played less than 3 games, we arrive at a graph with $n = 535$ nodes and 6109 edges, with an average degree of roughly 23. The skew-symmetric pairwise comparison matrix $H$ captures the net number of wins of player $i$ over

<footnote>^4Credits for using the Halo 2 Beta data set are given to Microsoft Research Ltd. and Bungie.</footnote>
season, which we then average over the entire set of 30 seasons. To the best of our knowledge, such a correlation study has not been performed in the literature, and provides insights on the potentially different latent rankings inherent in each data set, while still minimizing the number of upsets. SYNC, the best performing method in terms of the number of upsets, has a comparable performance to BTL, and a correlation of 86%. PGR and SVD-N attain a comparable number of upsets, but their Kendall score correlation is only 70%. The bottom barplot of the same Figure 7 show the average correlation of each of the methods, highlighting that SPR, LS and BTL yield the most correlated rankings with the other methods. A similar correlation analysis is performed on all rankings algorithms after the low-rank matrix completion step, which reveals a number of clusters. As expected, SVD and SVD-N produce very related rankings to each others, and similarly for RSUM and LS, and finally, SPR and BTL.

**Animal dominance network.** Our second real world example is a set of two networks of animal dominance among captive monk parakeets (Hobson and DeDeo, 2015). The input matrix $H$ is skew-symmetric, with $H_{ij}$ denoting the number of net aggressive wins of animal $i$ toward animal $j$. The study covers two groups (of 21, respectively, 19 individuals), and spans across four quarters. We follow the same approach as in De Bacco et al. (2018), and only tested the algorithms on Quarters 3 and 4, based on guidance from the behavioral ecologist who collected and analyzed the data. Since the animals did not know each other well at the start of the experiment, the hierarchies were still in the transient process of forming. Figure 8 compares performance in terms of the number of upsets and weighted upsets, with and without the matrix completion step. Overall, we observe that SVD-N outperforms SVD, and the two methods typically rank halfway in the performance ranking, except in the leftmost column, where SVD performs worst.

**Faculty hiring networks.** Our next example covers three North American academic hiring networks, that track the flow of academics between universities (Clauset et al., 2015). The flow is captured in a directed graph with adjacency matrix $A$, such that $A_{ij}$ is the number of faculty at university $j$ who received their doctorate from university $i$. We then consider the skew symmetric matrix $H = A - A^T$, capturing the net flow of faculty between a pair of institutions. Figure 9 shows the number of upsets attained by each algorithm, for three different disciplines: (a) Computer Science ($n = 206$), (b) Business ($n = 113$) and (c) History ($n = 145$), before and after the matrix completion step, for both upsets criteria. Again, we observe that SVD-N outperforms SVD. Furthermore, SVD-N typically ranks in the top half of the rankings, and for the case of weighted upsets after the matrix completion step, it is the best performer for the Business and History fields, and second best in Computer Science.

**Microsoft Halo 2 Tournament.** Our third experiment was performed on a real data set of game outcomes collected during the Beta testing period for the Xbox game^4 Halo 2. The graph has a total of $n = 606$ players, and 6227 head-to-head games. After removing the low-degree nodes, i.e., players who have played less than 3 games, we arrive at a graph with $n = 535$ nodes and 6109 edges, with an average degree of roughly 23. The skew-symmetric pairwise comparison matrix $H$ captures the net number of wins of player $i$ over

<footnote>^4Credits for using the Halo 2 Beta data set are given to Microsoft Research Ltd. and Bungie.</footnote>
<figure><img src="image_9.png" /><figcaption>Figure 6: Comparison of the algorithms for the NCAA College Basketball data set (1984 - 2014), before (left column) and after (right column) the matrix completion step. We analyze 30 measurement graph instances, one for each season, and estimate rankings for each problem instance, for all the algorithms we considered. The first row shows the number of upsets for each season, and the second row displays the averages across all the seasons. Similar plots are shown in the third and fourth row, but this time we compare performance in terms of weighted upsets. The heatmaps in the fifth row show the average (across seasons) correlation between the rankings estimated by each pair of methods, with the average correlation degree depicted in the bottom row.</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Figure 6: Comparison of the algorithms for the NCAA College Basketball data set (1984 - 2014), before (left column) and after (right column) the matrix completion step. We analyze 30 measurement graph instances, one for each season, and estimate rankings for each problem instance, for all the algorithms we considered. The first row shows the number of upsets for each season, and the second row displays the averages across all the seasons. Similar plots are shown in the third and fourth row, but this time we compare performance in terms of weighted upsets. The heatmaps in the fifth row show the average (across seasons) correlation between the rankings estimated by each pair of methods, with the average correlation degree depicted in the bottom row.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 7: Comparison of the algorithms for the NCAA College Basketball data set (1984 - 2014), before (left column) and after (right column) the matrix completion step. The heatmaps in the first row show the average (across seasons) correlation between the rankings estimated by each pair of methods, with the average correlation degree depicted in the bottom row.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 7: Comparison of the algorithms for the NCAA College Basketball data set (1984 - 2014), before (left column) and after (right column) the matrix completion step. The heatmaps in the first row show the average (across seasons) correlation between the rankings estimated by each pair of methods, with the average correlation degree depicted in the bottom row.</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Figure 8: Performance comparison in the animal dominance networks, for two groups in Quarters 3-4, thus a total of four networks altogether. We compare both in terms of the number of upsets (first two columns) and weighted upsets (last two columns). The results without the matrix completion step pertain to the first and third columns, while columns two and four show results obtained after a low-rank matrix completion preprocessing step.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 9: Performance comparison in the faculty hiring networks, for three networks corresponding to different fields. We compare both in terms of the number of upsets (first two columns) and weighted upsets (last two columns). The results without the matrix completion step pertain to the first and third columns, while columns two and four show results obtained after a low-rank matrix completion preprocessing step.</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Figure 8: Performance comparison in the animal dominance networks, for two groups in Quarters 3-4, thus a total of four networks altogether. We compare both in terms of the number of upsets (first two columns) and weighted upsets (last two columns). The results without the matrix completion step pertain to the first and third columns, while columns two and four show results obtained after a low-rank matrix completion preprocessing step.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 9: Performance comparison in the faculty hiring networks, for three networks corresponding to different fields. We compare both in terms of the number of upsets (first two columns) and weighted upsets (last two columns). The results without the matrix completion step pertain to the first and third columns, while columns two and four show results obtained after a low-rank matrix completion preprocessing step.</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Figure 10: Recovery results for the Microsoft Halo Tournament data set, both in terms of the number of upsets (first two columns) and weighted upsets (last two columns). Columns one and three show results without the matrix completion step, while columns two and four show results obtained after a low-rank matrix completion preprocessing step.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 11: Performance comparison for the Premier League data set, for four seasons during 2009-2013. We compare both in terms of the number of upsets (first two columns) and weighted upsets (last two columns). Recovery performance after the matrix completion step is shown in columns two and four, while columns one and three do not rely on matrix completion.</figcaption></figure>

player *j*. In this example illustrated in Figure 10, SVD-N outperforms SVD in three out of four instances, and the two methods are always ranked in the interval 5-7 out of the 9 algorithms considered.

**Premier League.** Our final real example is a Premier League data set, with four seasons (2009-2013), shown in Figure 11. The skew-symmetric pairwise comparison matrix *H* captures the net goal difference accrued in the two matches each pair of teams played against each other (home and away games). Across all the experimental setups considered and the different performance metrics, SVD-N outperforms SVD in 12 out of 16 rankings shown in Figure 11, and the two methods typically score in the top half best performing methods. Furthermore, SVD-N comes first in three instances. Note that Tsokos et al. (2019) also considers a subset of the same ranking methods in the context of football matches.
<figure><img src="image_13.png" /><figcaption>Figure 10: Recovery results for the Microsoft Halo Tournament data set, both in terms of the number of upsets (first two columns) and weighted upsets (last two columns). Columns one and three show results without the matrix completion step, while columns two and four show results obtained after a low-rank matrix completion preprocessing step.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 11: Performance comparison for the Premier League data set, for four seasons during 2009-2013. We compare both in terms of the number of upsets (first two columns) and weighted upsets (last two columns). Recovery performance after the matrix completion step is shown in columns two and four, while columns one and three do not rely on matrix completion.</figcaption></figure>

player *j*. In this example illustrated in Figure 10, SVD-N outperforms SVD in three out of four instances, and the two methods are always ranked in the interval 5-7 out of the 9 algorithms considered.

**Premier League.** Our final real example is a Premier League data set, with four seasons (2009-2013), shown in Figure 11. The skew-symmetric pairwise comparison matrix *H* captures the net goal difference accrued in the two matches each pair of teams played against each other (home and away games). Across all the experimental setups considered and the different performance metrics, SVD-N outperforms SVD in 12 out of 16 rankings shown in Figure 11, and the two methods typically score in the top half best performing methods. Furthermore, SVD-N comes first in three instances. Note that Tsokos et al. (2019) also considers a subset of the same ranking methods in the context of football matches.
## 8. Conclusion and future directions

This paper considered the problems of ranking and time synchronization given a subset of noisy pairwise comparisons, and proposed an SVD-based algorithmic pipeline to solve both tasks.

We analyzed the robustness of SVD-RS in the form of $\ell_2$ and $\ell_\infty$ recovery guarantees for the score vector $r$, against sampling sparsity and noise perturbation, using tools from matrix perturbation and random matrix theory. The $\ell_\infty$ analysis of SVD-RS leads to guarantees for rank recovery in terms of the maximum displacement error with respect to the ground truth. We also introduced SVD-NRS, a normalized version of SVD-RS, and provided $\ell_2$ recovery guarantees for the score vector $r$.

We have augmented our theoretical analysis with a comprehensive set of numerical experiments on both synthetic and real data (five different real data sets, which altogether contained 42 distinct problem instances/comparison graphs), showcasing the competitiveness of our approach when compared to other seven algorithms from the literature. In particular, SVD-NRS was shown to perform particularly well on many of the real data sets, often ranking in the top three algorithms in terms of performance, out of the nine algorithms considered.

There are several avenues for future work. An interesting direction pertains to extending our analysis to the setting of very sparse graphs, with $p$ on the order of $1/n$, by leveraging recent regularization techniques as introduced in Joseph and Yu (2016) and Le et al. (2015). Analysis of other, perhaps more realistic, noise models would also be of interest (such as the multiplicative noise models), as well as obtaining theoretical guarantees for the pipeline with low-rank matrix completion as a pre-processing step. Extending this work to the problem of ranking and synchronization in the heterogeneous setting, as recently explored in Cucuringu and Tyagi (2020) is another interesting direction, well motivated by real-world applications.

## Acknowledgments

A.A. is at the Département d'informatique de l'ENS, École Normale Supérieure, UMR CNRS 8548, PSL Research University, 75005 Paris, France, and INRIA, and would like to acknowledge support from the ML and Optimisation joint research initiative with the fonds AXA pour la recherche, and Kamet Ventures, as well as a Google focused award. A part of this work was done while H.T. was affiliated to The Alan Turing Institute, London, and the School of Mathematics, University of Edinburgh. M.C. and H.T. also acknowledge support from the EPSRC grant EP/N510129/1 at The Alan Turing Institute.

## References

* Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal. Accelerated spectral ranking. In *Proceedings of the 35th International Conference on Machine Learning*, volume 80, pages 70–79, 2018.
## 8. Conclusion and future directions

This paper considered the problems of ranking and time synchronization given a subset of noisy pairwise comparisons, and proposed an SVD-based algorithmic pipeline to solve both tasks.

We analyzed the robustness of SVD-RS in the form of $\ell_2$ and $\ell_\infty$ recovery guarantees for the score vector $r$, against sampling sparsity and noise perturbation, using tools from matrix perturbation and random matrix theory. The $\ell_\infty$ analysis of SVD-RS leads to guarantees for rank recovery in terms of the maximum displacement error with respect to the ground truth. We also introduced SVD-NRS, a normalized version of SVD-RS, and provided $\ell_2$ recovery guarantees for the score vector $r$.

We have augmented our theoretical analysis with a comprehensive set of numerical experiments on both synthetic and real data (five different real data sets, which altogether contained 42 distinct problem instances/comparison graphs), showcasing the competitiveness of our approach when compared to other seven algorithms from the literature. In particular, SVD-NRS was shown to perform particularly well on many of the real data sets, often ranking in the top three algorithms in terms of performance, out of the nine algorithms considered.

There are several avenues for future work. An interesting direction pertains to extending our analysis to the setting of very sparse graphs, with $p$ on the order of $1/n$, by leveraging recent regularization techniques as introduced in Joseph and Yu (2016) and Le et al. (2015). Analysis of other, perhaps more realistic, noise models would also be of interest (such as the multiplicative noise models), as well as obtaining theoretical guarantees for the pipeline with low-rank matrix completion as a pre-processing step. Extending this work to the problem of ranking and synchronization in the heterogeneous setting, as recently explored in Cucuringu and Tyagi (2020) is another interesting direction, well motivated by real-world applications.

## Acknowledgments

A.A. is at the Département d'informatique de l'ENS, École Normale Supérieure, UMR CNRS 8548, PSL Research University, 75005 Paris, France, and INRIA, and would like to acknowledge support from the ML and Optimisation joint research initiative with the fonds AXA pour la recherche, and Kamet Ventures, as well as a Google focused award. A part of this work was done while H.T. was affiliated to The Alan Turing Institute, London, and the School of Mathematics, University of Edinburgh. M.C. and H.T. also acknowledge support from the EPSRC grant EP/N510129/1 at The Alan Turing Institute.

## References

* Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal. Accelerated spectral ranking. In *Proceedings of the 35th International Conference on Machine Learning*, volume 80, pages 70–79, 2018.
Afonso S. Bandeira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. *Ann. Probab.*, 44(4):2479–2506, 2016.

Stephen R Becker, Emmanuel J Candès, and Michael C Grant. TFOCS: Templates for First-Order Conic Solvers. URL https://github.com/cvxr/TFOCS.

Stephen R Becker, Emmanuel J Candès, and Michael C Grant. Templates for convex cone problems with applications to sparse signal recovery. *Mathematical programming computation*, 3(3):165, 2011.

R. Bhatia. *Matrix Analysis*. Springer New York, 1996.

Stéphane Boucheron, Gabor Lugosi, and Pascal Massart. *Concentration inequalities: a non asymptotic theory of independence*. Oxford University Press, 2013.

R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. *Biometrika*, pages 324–345, 1952.

E. J. Candes and Y. Plan. Matrix completion with noise. *Proceedings of the IEEE*, 98(6):925–936, 2010.

E. J. Candes and T. Tao. The power of convex relaxation: Near-optimal matrix completion. *IEEE Transactions on Information Theory*, 56(5):2053–2080, 2010.

E. J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. *IEEE Transactions on Information Theory*, 52(2):489–509, 2006.

E. J. Candès, Y. C. Eldar, T. Strohmer, and V. Voroninski. Phase retrieval via matrix completion. *SIAM Journal on Imaging Sciences*, 6(1):199–225, 2013.

E.J. Candes and T. Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? *IEEE Transactions on Information Theory*, 52(12):5406 – 5425, 2006.

Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. *Foundations of Computational Mathematics*, 9(6):717, 2009.

Aaron Clauset, Samuel Arbesman, and Daniel B Larremore. Systematic inequality and hierarchy in faculty hiring networks. *Science Advances*, 1(1):e1400005, 2015.

A. H. Copeland. A “reasonable” social welfare function. In *In Seminar on Mathematics in Social Sciences, University of Michigan*, 1951.

M. Cucuringu. Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization. *IEEE Transactions on Network Science and Engineering*, 3(1):58–79, 2016.

Mihai Cucuringu and Hemant Tyagi. An extension of the angular synchronization problem to the heterogeneous setting. *arXiv:2012.14932*, 2020.
Afonso S. Bandeira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. *Ann. Probab.*, 44(4):2479–2506, 2016.

Stephen R Becker, Emmanuel J Candès, and Michael C Grant. TFOCS: Templates for First-Order Conic Solvers. URL https://github.com/cvxr/TFOCS.

Stephen R Becker, Emmanuel J Candès, and Michael C Grant. Templates for convex cone problems with applications to sparse signal recovery. *Mathematical programming computation*, 3(3):165, 2011.

R. Bhatia. *Matrix Analysis*. Springer New York, 1996.

Stéphane Boucheron, Gabor Lugosi, and Pascal Massart. *Concentration inequalities: a non asymptotic theory of independence*. Oxford University Press, 2013.

R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. *Biometrika*, pages 324–345, 1952.

E. J. Candès and Y. Plan. Matrix completion with noise. *Proceedings of the IEEE*, 98(6): 925–936, 2010.

E. J. Candès and T. Tao. The power of convex relaxation: Near-optimal matrix completion. *IEEE Transactions on Information Theory*, 56(5):2053–2080, 2010.

E. J. Candès, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. *IEEE Transactions on Information Theory*, 52(2):489–509, 2006.

E. J. Candès, Y. C. Eldar, T. Strohmer, and V. Voroninski. Phase retrieval via matrix completion. *SIAM Journal on Imaging Sciences*, 6(1):199–225, 2013.

E.J. Candès and T. Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? *IEEE Transactions on Information Theory*, 52(12):5406 – 5425, 2006.

Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. *Foundations of Computational Mathematics*, 9(6):717, 2009.

Aaron Clauset, Samuel Arbesman, and Daniel B Larremore. Systematic inequality and hierarchy in faculty hiring networks. *Science Advances*, 1(1):e1400005, 2015.

A. H. Copeland. A “reasonable” social welfare function. In *In Seminar on Mathematics in Social Sciences, University of Michigan*, 1951.

M. Cucuringu. Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization. *IEEE Transactions on Network Science and Engineering*, 3(1):58–79, 2016.

Mihai Cucuringu and Hemant Tyagi. An extension of the angular synchronization problem to the heterogeneous setting. *arXiv:2012.14932*, 2020.
Mihai Cucuringu, Yaron Lipman, and Amit Singer. Sensor network localization by eigenvec-
tor synchronization over the Euclidean group. *ACM Trans. Sen. Netw.*, 8(3):19:1–19:42,
2012a.

Mihai Cucuringu, Amit Singer, and David Cowburn. Eigenvector synchronization, graph rigidity and the molecule problem. *Information and Inference*, 1(1):21–67, 2012b.

Onkar Dalal, Srinivasan H Sengemedu, and Subhajit Sanyal. Multi-objective ranking of comments on web. In *Proceedings of the 21st International Conference on World Wide Web*, pages 419–428. ACM, 2012.

Mark A Davenport, Yaniv Plan, Ewout Van Den Berg, and Mary Wootters. 1-bit matrix completion. *Information and Inference: A Journal of the IMA*, 3(3):189–223, 2014.

Caterina De Bacco, Daniel B. Larremore, and Cristopher Moore. A physical model for efficient ranking in networks. *Science Advances*, 4(7), 2018.

Justin Eldridge, Mikhail Belkin, and Yusu Wang. Unperturbed: spectral analysis beyond Davis-Kahan. In *ALT*, 2018.

László Erdős, Antti Knowles, Horng-Tzer Yau, and Jun Yin. Spectral statistics of Erdős-Rényi graphs I: Local semicircle law. *Ann. Probab.*, 41(3B):2279–2375, 2013.

M. Fanuel and J.A.K. Suykens. Deformed Laplacians and spectral ranking in directed networks. *Applied and Computational Harmonic Analysis*, 47(2):397–422, 2017.

F. Fogel, A. d'Aspremont, and M. Vojnovic. Serialrank: Spectral ranking using seriation. In *Advances in Neural Information Processing Systems 27*, pages 900–908, 2014.

Fajwel Fogel, Alexandre d'Aspremont, and Milan Vojnovic. Spectral ranking using seriation. *Journal of Machine Learning Research*, 17(88):1–45, 2016.

A. Giridhar and P. R. Kumar. Distributed clock synchronization over wireless networks: Algorithms and analysis. In *45th IEEE Conference on Decision and Control*, pages 4915–4920, 2006.

David F Gleich and Lek-heng Lim. Rank aggregation via nuclear norm minimization. In *Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining*, pages 60–68. ACM, 2011.

Anil N Hirani, Kaushik Kalyanaraman, and Seth Watts. Least squares ranking on graphs. *arXiv preprint arXiv:1011.1716*, 2010.

Elizabeth A Hobson and Simon DeDeo. Social feedback and the emergence of rank in animal society. *PLoS computational biology*, 11(9):e1004411, 2015.

Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In *Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing*, pages 665–674, 2013.
Mihai Cucuringu, Yaron Lipman, and Amit Singer. Sensor network localization by eigenvec-
tor synchronization over the Euclidean group. *ACM Trans. Sen. Netw.*, 8(3):19:1–19:42,
2012a.

Mihai Cucuringu, Amit Singer, and David Cowburn. Eigenvector synchronization, graph rigidity and the molecule problem. *Information and Inference*, 1(1):21–67, 2012b.

Onkar Dalal, Srinivasan H Sengemedu, and Subhajit Sanyal. Multi-objective ranking of comments on web. In *Proceedings of the 21st International Conference on World Wide Web*, pages 419–428. ACM, 2012.

Mark A Davenport, Yaniv Plan, Ewout Van Den Berg, and Mary Wootters. 1-bit matrix completion. *Information and Inference: A Journal of the IMA*, 3(3):189–223, 2014.

Caterina De Bacco, Daniel B. Larremore, and Cristopher Moore. A physical model for efficient ranking in networks. *Science Advances*, 4(7), 2018.

Justin Eldridge, Mikhail Belkin, and Yusu Wang. Unperturbed: spectral analysis beyond Davis-Kahan. In *ALT*, 2018.

László Erdős, Antti Knowles, Horng-Tzer Yau, and Jun Yin. Spectral statistics of Erdős-Rényi graphs I: Local semicircle law. *Ann. Probab.*, 41(3B):2279–2375, 2013.

M. Fanuel and J.A.K. Suykens. Deformed Laplacians and spectral ranking in directed networks. *Applied and Computational Harmonic Analysis*, 47(2):397–422, 2017.

F. Fogel, A. d'Aspremont, and M. Vojnovic. Serialrank: Spectral ranking using seriation. In *Advances in Neural Information Processing Systems 27*, pages 900–908, 2014.

Fajwel Fogel, Alexandre d'Aspremont, and Milan Vojnovic. Spectral ranking using seriation. *Journal of Machine Learning Research*, 17(88):1–45, 2016.

A. Giridhar and P. R. Kumar. Distributed clock synchronization over wireless networks: Algorithms and analysis. In *45th IEEE Conference on Decision and Control*, pages 4915–4920, 2006.

David F Gleich and Lek-heng Lim. Rank aggregation via nuclear norm minimization. In *Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining*, pages 60–68. ACM, 2011.

Anil N Hirani, Kaushik Kalyanaraman, and Seth Watts. Least squares ranking on graphs. *arXiv preprint arXiv:1011.1716*, 2010.

Elizabeth A Hobson and Simon DeDeo. Social feedback and the emergence of rank in animal society. *PLoS computational biology*, 11(9):e1004411, 2015.

Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In *Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing*, pages 665–674, 2013.
Xiaoye Jiang, Lek-Heng Lim, Yuan Yao, and Yinyu Ye. Statistical ranking and combinatio-
rial Hodge theory. *Mathematical Programming*, 127(1):203–244, 2011.

Antony Joseph and Bin Yu. Impact of regularization on spectral clustering. *Ann. Statist.*, 44(4):1765–1791, 2016.

Zhao Kang, Chong Peng, and Qiang Cheng. Top-n recommender system via matrix com-
pletion. In *Thirtieth AAAI Conference on Artificial Intelligence*, 2016.

R. Karp, J. Elson, D. Estrin, and S. Shenker. Optimal and global time synchronization in sensors. Technical report, Center for Embedded Networked Sensing, University of California, Los Angeles, 2003.

Jérôme Kunegis, Stephan Schmidt, Andreas Lommatzsch, Jürgen Lerner, Ernesto William De Luca, and Sahin Albayrak. Spectral analysis of signed graphs for clustering, prediction and visualization. *SDM*, 10:559–570, 2010.

Can M Le, Elizaveta Levina, and Roman Vershynin. Sparse random graphs: regularization and concentration of the Laplacian. *arXiv preprint arXiv:1502.03049*, 2015.

Tal Levy, Alireza Vahid, and Raja Giryes. Ranking recovery from limited comparisons using low-rank matrix completion. *arXiv preprint arXiv:1806.05419*, 2018.

Ren-Cang Li. On perturbations of matrix pencils with real spectra. *Mathematics of Computation*, 62(205):231–265, 1994.

Andrew K Massimino and Mark A Davenport. One-bit matrix completion for pairwise comparison matrices. In *Proceedings of Workshop on Signal Processing with Adaptive Sparse Structured Representations (SPARS)*, 2013.

Sahand Negahban, Sewoong Oh, and Devavrat Shah. Iterative ranking from pairwise com-
parisons. In *Advances in Neural Information Processing Systems 25*, pages 2474–2482,
2012.

Sahand Negahban, Sewoong Oh, and Devavrat Shah. Rank centrality: Ranking from pair-
wise comparisons. *Operations Research*, 65(1):266–287, 2017.

Sahand Negahban, Sewoong Oh, Kiran K Thekumparampil, and Jiaming Xu. Learning from comparisons and choices. *Journal of Machine Learning Research*, 19:1–95, 2018.

Onur Özyeşil, Vladislav Voroninski, Ronen Basri, and Amit Singer. A survey of structure from motion. *Acta Numerica*, 26:305–364, 2017.

Onur Ozyesil, Nir Sharon, and Amit Singer. Synchronization over Cartan motion groups via contraction. *SIAM Journal on Applied Algebra and Geometry*, 2(2):207–241, 2018.

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. In *Proceedings of the 7th International World Wide Web Conference*, pages 161–172, 1998.
Xiaoye Jiang, Lek-Heng Lim, Yuan Yao, and Yinyu Ye. Statistical ranking and combinatorial Hodge theory. *Mathematical Programming*, 127(1):203–244, 2011.

Antony Joseph and Bin Yu. Impact of regularization on spectral clustering. *Ann. Statist.*, 44(4):1765–1791, 2016.

Zhao Kang, Chong Peng, and Qiang Cheng. Top-n recommender system via matrix completion. In *Thirtieth AAAI Conference on Artificial Intelligence*, 2016.

R. Karp, J. Elson, D. Estrin, and S. Shenker. Optimal and global time synchronization in sensors. Technical report, Center for Embedded Networked Sensing, University of California, Los Angeles, 2003.

Jérôme Kunegis, Stephan Schmidt, Andreas Lommatzsch, Jürgen Lerner, Ernesto William De Luca, and Sahin Albayrak. Spectral analysis of signed graphs for clustering, prediction and visualization. *SDM*, 10:559–570, 2010.

Can M Le, Elizaveta Levina, and Roman Vershynin. Sparse random graphs: regularization and concentration of the Laplacian. *arXiv preprint arXiv:1502.03049*, 2015.

Tal Levy, Alireza Vahid, and Raja Giryes. Ranking recovery from limited comparisons using low-rank matrix completion. *arXiv preprint arXiv:1806.05419*, 2018.

Ren-Cang Li. On perturbations of matrix pencils with real spectra. *Mathematics of Computation*, 62(205):231–265, 1994.

Andrew K Massimino and Mark A Davenport. One-bit matrix completion for pairwise comparison matrices. In *Proceedings of Workshop on Signal Processing with Adaptive Sparse Structured Representations (SPARS)*, 2013.

Sahand Negahban, Sewoong Oh, and Devavrat Shah. Iterative ranking from pairwise comparisons. In *Advances in Neural Information Processing Systems 25*, pages 2474–2482, 2012.

Sahand Negahban, Sewoong Oh, and Devavrat Shah. Rank centrality: Ranking from pairwise comparisons. *Operations Research*, 65(1):266–287, 2017.

Sahand Negahban, Sewoong Oh, Kiran K Thekumparampil, and Jiaming Xu. Learning from comparisons and choices. *Journal of Machine Learning Research*, 19:1–95, 2018.

Onur Özyeşil, Vladislav Voroninski, Ronen Basri, and Amit Singer. A survey of structure from motion. *Acta Numerica*, 26:305–364, 2017.

Onur Ozyesil, Nir Sharon, and Amit Singer. Synchronization over Cartan motion groups via contraction. *SIAM Journal on Applied Algebra and Geometry*, 2(2):207–241, 2018.

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. In *Proceedings of the 7th International World Wide Web Conference*, pages 161–172, 1998.
Arun Rajkumar and Shivani Agarwal. When can we rank well from comparisons of O(n log(n)) non-actively chosen pairs? In *Conference on Learning Theory*, pages 1376–1401, 2016.

A. Singer. Angular synchronization by eigenvectors and semidefinite programming. *Appl. Comput. Harmon. Anal.*, 30(1):20–36, 2011.

A. Singer and H.-T. Wu. Vector diffusion maps and the Connection Laplacian. *Communica- tions on Pure and Applied Mathematics*, 65(8):1067–1144, 2012.

G.W. Stewart and Ji guang Sun. *Matrix Perturbation Theory*. Academic Press, 1990.

L.L. Thurstone. A law of comparative judgement. *Psychological Review*, 34:278–286, 1927.

Carlo Tomasi and Takeo Kanade. Shape and motion from image streams under orthography: a factorization method. *International Journal of Computer Vision*, 9(2):137–154, 1992.

Lloyd N. Trefethen and David Bau. *Numerical Linear Algebra*. SIAM, 1997. ISBN 0898713617.

Alkeos Tsokos, Santhosh Narayanan, Ioannis Kosmidis, Gianluca Baio, Mihai Cucuringu, Gavin Whitaker, and Franz Király. Modeling outcomes of soccer matches. *Machine Learning*, 108(1):77–95, 2019.

M. Udell and A. Townsend. Why are big data matrices approximately low rank? *SIAM Journal on Mathematics of Data Science*, 1(1):144–160, 2019. doi: 10.1137/18M1183480.

Maksims N. Volkovs and Richard S. Zemel. New learning methods for supervised and unsupervised preference aggregation. *J. Mach. Learn. Res.*, 15(1):1135–1176, 2014.

Per-Åke Wedin. Perturbation bounds in connection with singular value decomposition. *BIT Numerical Mathematics*, 12(1):99–111, Mar 1972.

Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller dif- ferentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). *Mathematische Annalen*, 71(4):441–479, 1912.

D. Yang and M. B. Wakin. Modeling and recovering non-transitive pairwise compari-
son matrices. In *2015 International Conference on Sampling Theory and Applications (SampTA)*, pages 39–43, 2015.

Guangnan Ye, Dong Liu, I-Hong Jhuo, and Shih-Fu Chang. Robust late fusion with rank minimization. In *2012 IEEE Conference on Computer Vision and Pattern Recognition*, pages 3021–3028, 2012.
Arun Rajkumar and Shivani Agarwal. When can we rank well from comparisons of O(n log(n)) non-actively chosen pairs? In *Conference on Learning Theory*, pages 1376–1401, 2016.

A. Singer. Angular synchronization by eigenvectors and semidefinite programming. *Appl. Comput. Harmon. Anal.*, 30(1):20–36, 2011.

A. Singer and H.-T. Wu. Vector diffusion maps and the Connection Laplacian. *Communica- tions on Pure and Applied Mathematics*, 65(8):1067–1144, 2012.

G.W. Stewart and Ji guang Sun. *Matrix Perturbation Theory*. Academic Press, 1990.

L.L. Thurstone. A law of comparative judgement. *Psychological Review*, 34:278–286, 1927.

Carlo Tomasi and Takeo Kanade. Shape and motion from image streams under orthography: a factorization method. *International Journal of Computer Vision*, 9(2):137–154, 1992.

Lloyd N. Trefethen and David Bau. *Numerical Linear Algebra*. SIAM, 1997. ISBN 0898713617.

Alkeos Tsokos, Santhosh Narayanan, Ioannis Kosmidis, Gianluca Baio, Mihai Cucuringu, Gavin Whitaker, and Franz Király. Modeling outcomes of soccer matches. *Machine Learning*, 108(1):77–95, 2019.

M. Udell and A. Townsend. Why are big data matrices approximately low rank? *SIAM Journal on Mathematics of Data Science*, 1(1):144–160, 2019. doi: 10.1137/18M1183480.

Maksims N. Volkovs and Richard S. Zemel. New learning methods for supervised and unsupervised preference aggregation. *J. Mach. Learn. Res.*, 15(1):1135–1176, 2014.

Per-Åke Wedin. Perturbation bounds in connection with singular value decomposition. *BIT Numerical Mathematics*, 12(1):99–111, Mar 1972.

Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller dif- ferentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). *Mathematische Annalen*, 71(4):441–479, 1912.

D. Yang and M. B. Wakin. Modeling and recovering non-transitive pairwise compari-
son matrices. In *2015 International Conference on Sampling Theory and Applications (SampTA)*, pages 39–43, 2015.

Guangnan Ye, Dong Liu, I-Hong Jhuo, and Shih-Fu Chang. Robust late fusion with rank minimization. In *2012 IEEE Conference on Computer Vision and Pattern Recognition*, pages 3021–3028, 2012.
## Appendix A. Matrix perturbation analysis

Let $A, \tilde{A} \in \mathbb{C}^{m \times n}$ where we assume $m \ge n$ w.l.o.g. Let

$$ \sigma_1(A) \ge \dots \ge \sigma_n(A), \quad \sigma_1(\tilde{A}) \ge \dots \ge \sigma_n(\tilde{A}) $$

denote the singular values of $A$ and $\tilde{A}$ respectively, and denote $E = \tilde{A} - A$.

To begin with, we would like to quantify the perturbation of the singular values of $\tilde{A}$ with respect to those of $A$. Weyl's inequality (Weyl, 1912) is a very useful result in this regard.

**Theorem 21 (Weyl's inequality (Weyl, 1912))** It holds that

$$ |\sigma_i(\tilde{A}) - \sigma_i(A)| \le \|E\|_2, \quad i = 1, \dots, n. $$

Next, let us write the singular value decomposition of $A$ as

$$ A = [U_1 \ U_2 \ U_3] \begin{bmatrix} \Sigma_1 & 0 \\ 0 & \Sigma_2 \\ 0 & 0 \end{bmatrix} [V_1 \ V_2]^*, $$

and the same for $\tilde{A}$ (conformal partition) so that

$$ \tilde{A} = [\tilde{U}_1 \ \tilde{U}_2 \ \tilde{U}_3] \begin{bmatrix} \tilde{\Sigma}_1 & 0 \\ 0 & \tilde{\Sigma}_2 \\ 0 & 0 \end{bmatrix} [\tilde{V}_1 \ \tilde{V}_2]^*. $$

We will like to quantify the perturbation of $\mathcal{R}(U_1), \mathcal{R}(V_1)$, this is given precisely by Wedin's theorem (Wedin, 1972). Before introducing the theorem, we need some definitions. Let $U, \tilde{U} \in \mathbb{C}^{n \times k}$ (for $k \le n$) have orthonormal columns respectively and let $\sigma_1 \ge \dots \ge \sigma_k$ denote the singular values of $U^*\tilde{U}$. Then the $k$ canonical angles between $\mathcal{R}(U), \mathcal{R}(\tilde{U})$ are defined as $\theta_i := \cos^{-1}(\sigma_i)$ for $1 \le i \le k$, with each $\theta_i \in [0, \pi/2]$. It is usual to define $k \times k$ diagonal matrices $\Theta(\mathcal{R}(U), \mathcal{R}(\tilde{U})) := \text{diag}(\theta_1, \dots, \theta_k)$ and $\sin \Theta(\mathcal{R}(U), \mathcal{R}(\tilde{U})) := \text{diag}(\sin \theta_1, \dots, \sin \theta_k)$. Denoting $||| \cdot |||$ to be any unitarily invariant norm (Frobenius, spectral, etc.), it is useful to know that the following relation holds (see for eg., (Li, 1994, Lemma 2.1), (Stewart and guang Sun, 1990, Corollary I.5.4)).

$$ ||| \sin \Theta(\mathcal{R}(U), \mathcal{R}(\tilde{U})) ||| = |||(I - \tilde{U}\tilde{U}^*)U ||| $$

Let $\Phi$ be the matrix of canonical angles between $\mathcal{R}(U_1), \mathcal{R}(\tilde{U}_1)$ and let $\Theta$ be the matrix of canonical angles between $\mathcal{R}(V_1), \mathcal{R}(\tilde{V}_1)$.

**Theorem 22 (Wedin, 1972)** Suppose that there are numbers $\alpha, \delta > 0$ such that

$$ \min \sigma(\tilde{\Sigma}_1) \ge \alpha + \delta \quad \text{and} \quad \max \sigma(\Sigma_2) \le \alpha. \qquad (A.1) $$

Then,

$$ \max \{\|\sin \Theta\|_2, \|\sin \Phi\|_2\} \le \frac{\|E\|_2}{\delta}. $$

Note that due to (A.1) the bounds are restricted to subspaces corresponding to the largest singular values. But one can derive bounds on $\max \{\|\sin \Theta\|_F, \|\sin \Phi\|_F\}$ without this restriction (see for eg. (Stewart and guang Sun, 1990, Theorem 4.1)).
## Appendix A. Matrix perturbation analysis

Let $A, \tilde{A} \in \mathbb{C}^{m \times n}$ where we assume $m \ge n$ w.l.o.g. Let

$$ \sigma_1(A) \ge \dots \ge \sigma_n(A), \quad \sigma_1(\tilde{A}) \ge \dots \ge \sigma_n(\tilde{A}) $$

denote the singular values of $A$ and $\tilde{A}$ respectively, and denote $E = \tilde{A} - A$.

To begin with, we would like to quantify the perturbation of the singular values of $\tilde{A}$ with respect to those of $A$. Weyl's inequality (Weyl, 1912) is a very useful result in this regard.

**Theorem 21 (Weyl's inequality (Weyl, 1912))** It holds that

$$ |\sigma_i(\tilde{A}) - \sigma_i(A)| \le \|E\|_2, \quad i = 1, \dots, n. $$

Next, let us write the singular value decomposition of $A$ as

$$ A = [U_1 \ U_2 \ U_3] \begin{bmatrix} \Sigma_1 & 0 \\ 0 & \Sigma_2 \\ 0 & 0 \end{bmatrix} [V_1 \ V_2]^*, $$

and the same for $\tilde{A}$ (conformal partition) so that

$$ \tilde{A} = [\tilde{U}_1 \ \tilde{U}_2 \ \tilde{U}_3] \begin{bmatrix} \tilde{\Sigma}_1 & 0 \\ 0 & \tilde{\Sigma}_2 \\ 0 & 0 \end{bmatrix} [\tilde{V}_1 \ \tilde{V}_2]^*. $$

We will like to quantify the perturbation of $\mathcal{R}(U_1), \mathcal{R}(V_1)$, this is given precisely by Wedin's theorem (Wedin, 1972). Before introducing the theorem, we need some definitions. Let $U, \tilde{U} \in \mathbb{C}^{n \times k}$ (for $k \le n$) have orthonormal columns respectively and let $\sigma_1 \ge \dots \ge \sigma_k$ denote the singular values of $U^*\tilde{U}$. Then the $k$ canonical angles between $\mathcal{R}(U), \mathcal{R}(\tilde{U})$ are defined as $\theta_i := \cos^{-1}(\sigma_i)$ for $1 \le i \le k$, with each $\theta_i \in [0, \pi/2]$. It is usual to define $k \times k$ diagonal matrices $\Theta(\mathcal{R}(U), \mathcal{R}(\tilde{U})) := \text{diag}(\theta_1, \dots, \theta_k)$ and $\sin \Theta(\mathcal{R}(U), \mathcal{R}(\tilde{U})) := \text{diag}(\sin \theta_1, \dots, \sin \theta_k)$. Denoting $||| \cdot |||$ to be any unitarily invariant norm (Frobenius, spectral, etc.), it is useful to know that the following relation holds (see for eg., (Li, 1994, Lemma 2.1), (Stewart and guang Sun, 1990, Corollary I.5.4)).

$$ ||| \sin \Theta(\mathcal{R}(U), \mathcal{R}(\tilde{U})) ||| = |||(I - \tilde{U}\tilde{U}^*)U ||| $$

Let $\Phi$ be the matrix of canonical angles between $\mathcal{R}(U_1), \mathcal{R}(\tilde{U}_1)$ and let $\Theta$ be the matrix of canonical angles between $\mathcal{R}(V_1), \mathcal{R}(\tilde{V}_1)$.

**Theorem 22 (Wedin, 1972)** Suppose that there are numbers $\alpha, \delta > 0$ such that

$$ \min \sigma(\tilde{\Sigma}_1) \ge \alpha + \delta \quad \text{and} \quad \max \sigma(\Sigma_2) \le \alpha. \qquad (A.1) $$

Then,

$$ \max \{\|\sin \Theta\|_2, \|\sin \Phi\|_2\} \le \frac{\|E\|_2}{\delta}. $$

Note that due to (A.1) the bounds are restricted to subspaces corresponding to the largest singular values. But one can derive bounds on $\max \{\|\sin \Theta\|_F, \|\sin \Phi\|_F\}$ without this restriction (see for eg. (Stewart and guang Sun, 1990, Theorem 4.1)).
# Appendix B. Useful concentration inequalities

We outline here some useful concentration inequalities that are used in our proofs.

## B.1 Spectral norm of random symmetric matrices

We will make use of the following result for bounding the spectral norm of random symmetric matrices with independent, centered and bounded entries.

**Theorem 23 (Bandeira and van Handel, 2016, Corollary 3.12, Remark 3.13)** Let $X$ be an $n \times n$ symmetric matrix whose entries $X_{ij}$ ($i \le j$) are independent, centered random variables. There there exists for any $0 < \varepsilon \le 1/2$ a universal constant $c_\varepsilon$ such that for every $t \ge 0$,

$$ \mathbb{P}(\|X\|_2 \ge (1 + \varepsilon)2\sqrt{2}\tilde{\sigma} + t) \le n \exp\left(-\frac{t^2}{c_\varepsilon \tilde{\sigma}_*^2}\right) \quad (B.1) $$

where

$$ \tilde{\sigma} := \max_i \sqrt{\sum_j \mathbb{E}[X_{ij}^2]}, \quad \tilde{\sigma}_* := \max_{i,j} \|X_{ij}\|_{\infty}. $$

Note that it suffices to employ upper bound estimates on $\tilde{\sigma}$, $\tilde{\sigma}_*$ in (B.1).

## B.2 Bernstein inequality

**Theorem 24 (Boucheron et al., 2013, Corollary 2.11)** Let $X_1, \dots, X_n$ be independent random variables with $|X_i| \le b$ for all $i$, and $v = \sum_{i=1}^n \mathbb{E}[X_i^2]$. Then for any $t \ge 0$,

$$ \mathbb{P}\left(\left|\sum_{i=1}^{n}(X_i - \mathbb{E}[X_i])\right| \ge t\right) \le 2 \exp\left(-\frac{t^2}{2\left(v + \frac{bt}{3}\right)}\right). $$

## B.3 Product of a random matrix (raised to a power) and a fixed vector

Given a random symmetric matrix $X$ with independent entries on and above the diagonal, and a fixed vector $u$, (Eldridge et al., 2018, Theorem 15) provided an upper tail bound for $|(X^k u)_i|$. The proof technique therein followed that of Erdős et al. (2013). In fact, the proof goes through even if $X$ is a random skew-symmetric matrix, the version stated below is for such matrices.

**Theorem 25 (Eldridge et al., 2018, Theorem 15)** Let $X$ be an $n \times n$ skew-symmetric and centered random matrix. Let $u \in \mathbb{R}^n$ be a fixed vector with $\|u\|_{\infty} = 1$. Choose $\xi > 1$, $0 < \kappa < 1$ and define $\mu = \frac{2}{\kappa+1}$. If $\mathbb{E}[|X_{ij}|^m] \le 1/n$ for all $m \ge 2$, $1 \le i, j \le n$ and $k \le \frac{\kappa}{8}(\log n)^{2\xi}$, then we have for any given $l \in [n]$ that

$$ \mathbb{P}(|(X^k u)_l| \ge (\log n)^{k\xi}) \le n^{-\frac{1}{4}(\log \mu n)^{\xi-1}(\log \mu e)^{-\xi}}. $$
# Appendix B. Useful concentration inequalities

We outline here some useful concentration inequalities that are used in our proofs.

## B.1 Spectral norm of random symmetric matrices

We will make use of the following result for bounding the spectral norm of random symmetric matrices with independent, centered and bounded entries.

**Theorem 23 (Bandeira and van Handel, 2016, Corollary 3.12, Remark 3.13)** Let $X$ be an $n \times n$ symmetric matrix whose entries $X_{ij}$ ($i \le j$) are independent, centered random variables. There there exists for any $0 < \varepsilon \le 1/2$ a universal constant $c_\varepsilon$ such that for every $t \ge 0$,

$$ \mathbb{P}(\|X\|_2 \ge (1 + \varepsilon)2\sqrt{2}\tilde{\sigma} + t) \le n \exp\left(-\frac{t^2}{c_\varepsilon \tilde{\sigma}_*^2}\right) \quad (B.1) $$

where

$$ \tilde{\sigma} := \max_i \sqrt{\sum_j \mathbb{E}[X_{ij}^2]}, \quad \tilde{\sigma}_* := \max_{i,j} \|X_{ij}\|_{\infty}. $$

Note that it suffices to employ upper bound estimates on $\tilde{\sigma}, \tilde{\sigma}$ in (B.1).

## B.2 Bernstein inequality

**Theorem 24 (Boucheron et al., 2013, Corollary 2.11)** Let $X_1, \dots, X_n$ be independent random variables with $|X_i| \le b$ for all $i$, and $v = \sum_{i=1}^n \mathbb{E}[X_i^2]$. Then for any $t \ge 0$,

$$ \mathbb{P}\left(\left|\sum_{i=1}^n (X_i - \mathbb{E}[X_i])\right| \ge t\right) \le 2 \exp\left(-\frac{t^2}{2\left(v + \frac{bt}{3}\right)}\right). $$

## B.3 Product of a random matrix (raised to a power) and a fixed vector

Given a random symmetric matrix $X$ with independent entries on and above the diagonal, and a fixed vector $u$, (Eldridge et al., 2018, Theorem 15) provided an upper tail bound for $|(X^k u)_i|$. The proof technique therein followed that of Erdős et al. (2013). In fact, the proof goes through even if $X$ is a random skew-symmetric matrix, the version stated below is for such matrices.

**Theorem 25 (Eldridge et al., 2018, Theorem 15)** Let $X$ be an $n \times n$ skew-symmetric and centered random matrix. Let $u \in \mathbb{R}^n$ be a fixed vector with $\|u\|_{\infty} = 1$. Choose $\xi > 1$, $0 < \kappa < 1$ and define $\mu = \frac{2}{\kappa+1}$. If $\mathbb{E}[|X_{ij}|^m] \le 1/n$ for all $m \ge 2$, $1 \le i, j \le n$ and $k \le \frac{\kappa}{8}(\log n)^{2\xi}$, then we have for any given $l \in [n]$ that

$$ \mathbb{P}(|(X^k u)_l| \ge (\log n)^{k\xi}) \le n^{-\frac{1}{4}(\log_\mu n)^{\xi-1}(\log_\mu e)^{-\xi}}. $$
# Appendix C. Proof of Theorem 5

## C.1 Proof of Lemma 11

We begin by noting that for $\alpha = \frac{r^T e}{n}$, $\langle e, r - \alpha e \rangle = 0$ and so $u_1, u_2$ (similarly $v_1, v_2$) are orthogonal. Moreover, $u_1, u_2, v_1, v_2$ also have unit $\ell_2$ norm. Finally, we note that

$$u_1 v_1^T + u_2 v_2^T = \frac{1}{\sqrt{n} \|r - \alpha e\|_2} [-e(r - \alpha e)^T + (r - \alpha e)e^T] = \frac{1}{\sqrt{n} \|r - \alpha e\|_2} [\underbrace{re^T - er^T}_{C}],$$

which completes the proof.

## C.2 Proof of Lemma 12

We begin by considering the second moment of $S_{ij}$ for $i < j$. Note that $\mathbb{E}[N_{ij}] = 0$ and $\mathbb{E}[N_{ij}^2] = M^2/3$. We thus obtain

$$\begin{aligned}
\mathbb{E}[(S)_{ij}^2] &= \eta p(1 - \eta p)^2 (r_i - r_j)^2 + (1 - \eta)p\mathbb{E}[N_{ij} - \eta p(r_i - r_j)]^2 + (1 - p)(r_i - r_j)^2 \eta^2 p^2 \\
&= \eta p(1 - \eta p)^2 (r_i - r_j)^2 + (1 - \eta)p\left[\frac{M^2}{3} + \eta^2 p^2 (r_i - r_j)^2\right] + (1 - p)(r_i - r_j)^2 \eta^2 p^2
\end{aligned}$$

which together with $(r_i - r_j)^2 \le M^2$ yields

$$\begin{aligned}
\mathbb{E}[(S)_{ij}^2] &\le \eta p(1 - \eta p)^2 M^2 + (1 - \eta)p\left[\frac{M^2}{3} + \eta^2 p^2 M^2\right] + (1 - p)\eta^2 p^2 M^2 \\
&= [\eta p(1 - \eta p)^2 + (1 - \eta)p\left(\frac{1}{3} + \eta^2 p^2\right) + (1 - p)\eta^2 p^2] M^2 \\
&\le \left(\eta p + \frac{4}{3}p + \eta^2 p^2 \le \frac{10}{3}p\right) M^2 = \frac{10p}{3}M^2.
\end{aligned}
\quad (C.1)$$

We thus have that $\mathbb{E}[(S)_{ij}^2] \le \frac{10p}{3}M^2$ for $i < j$; the same bound holds for $i > j$ as well. Hence we can bound the quantities $\tilde{\sigma}, \tilde{\sigma}_*$ defined in Theorem 23 as follows.

$$\begin{aligned}
\tilde{\sigma} &:= \max_i \sqrt{\sum_j \mathbb{E}[(\tilde{S})_{ij}^2]} \le \sqrt{\frac{10p}{3}nM^2} = M\sqrt{\frac{10p}{3}n}, \\
\tilde{\sigma}_* &:= \max_{i,j} \|(\tilde{S})_{ij}\|_{\infty} \le 2M.
\end{aligned}$$

Then by invoking Theorem 23, we obtain for any given $t \ge 0$, $0 < \varepsilon \le 1/2$ that

$$\begin{aligned}
\mathbb{P}(\|\tilde{S}\|_2 \ge (1 + \varepsilon)2\sqrt{2}M\sqrt{\frac{10p}{3}}n + t) &\le \mathbb{P}(\|\tilde{S}\|_2 \ge (1 + \varepsilon)2\sqrt{2}\tilde{\sigma} + t) \\
&\le 2n \exp\left(\frac{-t^2}{c_{\varepsilon}\sigma_*^2}\right) \le 2n \exp\left(\frac{-t^2}{4c_{\varepsilon}M^2}\right),
\end{aligned}$$

where $c_{\varepsilon} > 0$ depends only on $\varepsilon$. Plugging $t = 2\sqrt{2}M\sqrt{\frac{10p}{3}}n$ we obtain the stated bound.
# Appendix C. Proof of Theorem 5

## C.1 Proof of Lemma 11

We begin by noting that for $\alpha = \frac{r^T e}{n}$, $\langle e, r - \alpha e \rangle = 0$ and so $u_1, u_2$ (similarly $v_1, v_2$) are orthogonal. Moreover, $u_1, u_2, v_1, v_2$ also have unit $\ell_2$ norm. Finally, we note that

$$u_1 v_1^T + u_2 v_2^T = \frac{1}{\sqrt{n} \|r - \alpha e\|_2} [-e(r - \alpha e)^T + (r - \alpha e)e^T] = \frac{1}{\sqrt{n} \|r - \alpha e\|_2} [\underbrace{re^T - er^T}_{C}],$$

which completes the proof.

## C.2 Proof of Lemma 12

We begin by considering the second moment of $S_{ij}$ for $i < j$. Note that $\mathbb{E}[N_{ij}] = 0$ and $\mathbb{E}[N_{ij}^2] = M^2/3$. We thus obtain

$$\begin{aligned}
\mathbb{E}[(S)_{ij}^2] &= \eta p(1 - \eta p)^2 (r_i - r_j)^2 + (1 - \eta)p\mathbb{E}[N_{ij} - \eta p(r_i - r_j)]^2 + (1 - p)(r_i - r_j)^2 \eta^2 p^2 \\
&= \eta p(1 - \eta p)^2 (r_i - r_j)^2 + (1 - \eta)p \left[ \frac{M^2}{3} + \eta^2 p^2 (r_i - r_j)^2 \right] + (1 - p)(r_i - r_j)^2 \eta^2 p^2
\end{aligned}$$

which together with $(r_i - r_j)^2 \le M^2$ yields

$$\begin{aligned}
\mathbb{E}[(S)_{ij}^2] &\le \eta p(1 - \eta p)^2 M^2 + (1 - \eta)p \left[ \frac{M^2}{3} + \eta^2 p^2 M^2 \right] + (1 - p)\eta^2 p^2 M^2 \\
&= [\eta p(1 - \eta p)^2 + (1 - \eta)p \left( \frac{1}{3} + \eta^2 p^2 \right) + (1 - p)\eta^2 p^2] M^2 \\
&\le \left( \eta p + \frac{4}{3}p + \eta^2 p^2 \le \frac{10}{3}p \right) M^2 = \frac{10p}{3}M^2.
\end{aligned}
\quad (C.1)$$

We thus have that $\mathbb{E}[(S)_{ij}^2] \le \frac{10p}{3}M^2$ for $i < j$; the same bound holds for $i > j$ as well. Hence we can bound the quantities $\tilde{\sigma}, \tilde{\sigma}_*$ defined in Theorem 23 as follows.

$$\begin{aligned}
\tilde{\sigma} &:= \max_i \sqrt{\sum_j \mathbb{E}[(\tilde{S})_{ij}^2]} \le \sqrt{\frac{10p}{3}nM^2} = M\sqrt{\frac{10p}{3}n}, \\
\tilde{\sigma}_* &:= \max_{i,j} ||(\tilde{S})_{ij}||_\infty \le 2M.
\end{aligned}$$

Then by invoking Theorem 23, we obtain for any given $t \ge 0$, $0 < \varepsilon \le 1/2$ that

$$\begin{aligned}
\mathbb{P}(\|\tilde{S}\|_2 \ge (1 + \varepsilon)2\sqrt{2}M\sqrt{\frac{10p}{3}}n + t) &\le \mathbb{P}(\|\tilde{S}\|_2 \ge (1 + \varepsilon)2\sqrt{2}\tilde{\sigma} + t) \\
&\le 2n \exp\left(\frac{-t^2}{c_\varepsilon \sigma_*^2}\right) \le 2n \exp\left(\frac{-t^2}{4c_\varepsilon M^2}\right),
\end{aligned}$$

where $c_\varepsilon > 0$ depends only on $\varepsilon$. Plugging $t = 2\sqrt{2}M\sqrt{\frac{10p}{3}}n$ we obtain the stated bound.
### C.3 Proof of Lemma 13

Note that Weyl's inequality (Weyl, 1912) (see Theorem 21) for singular value perturbation readily yields

$$ \sigma_i(H) \in [\sigma_i(\eta p C) \pm \Delta], \quad \forall i = 1, \dots, n. $$

In particular, using the expressions for $\sigma_1(C)$, $\sigma_2(C)$ from Lemma 11, we have that

$$ \begin{aligned} \sigma_1(H), \sigma_2(H) &\geq \eta p \sqrt{n} \|r - \alpha e\|_2 - \Delta, \\ \sigma_3(H), \dots, \sigma_n(H) &\leq \Delta. \end{aligned} $$

Then using Wedin's bound for perturbation of singular subspaces (Wedin, 1972) (see Theorem 22), we obtain

$$ \| \sin \Theta(\mathcal{R}(\hat{U}), \mathcal{R}(U)) \|_2 = \|(I - \hat{U}\hat{U}^T)U\|_2 \leq \frac{\Delta}{\eta p \sqrt{n} \|r - \alpha e\|_2 - \Delta} (= \delta), $$

provided $\Delta < \eta p \sqrt{n} \|r - \alpha e\|_2$ holds.

### C.4 Proof of Lemma 14

To begin with, note that $\bar{u}_1 = \hat{U}\hat{U}^T u_1$ is the orthogonal projection of $u_1$ on $\mathcal{R}(\hat{U})$. A unit vector orthogonal to $\bar{u}_1$ and lying in $\mathcal{R}(\hat{U})$ is given by

$$ \tilde{u}_2 = \frac{1}{\|\bar{u}_1\|_2} \hat{U} \left[ \begin{array}{c} \mp \langle \hat{u}_2, \bar{u}_1 \rangle \\ \pm \langle \hat{u}_1, \bar{u}_1 \rangle \end{array} \right]. $$

Denoting $\bar{u}_2$ to be the orthogonal projection of $u_2$ on $\mathcal{R}(\hat{U})$, we can decompose $\langle \tilde{u}_2, u_2 \rangle$ as

$$ \langle \tilde{u}_2, u_2 \rangle = \langle \tilde{u}_2, u_2 - \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle + \langle \tilde{u}_2, \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle, $$

which leads to

$$ |\langle \tilde{u}_2, u_2 \rangle| \geq |\langle \tilde{u}_2, \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle| - |\langle \tilde{u}_2, u_2 - \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle|. \quad (C.2) $$

We will now bound the two terms in the RHS of (C.2) starting with the first term.

**Lower bounding the first term in RHS of (C.2).** Since $\langle \hat{u}_2, \bar{u}_1 \rangle = \langle \hat{u}_2, u_1 \rangle$, $\langle \hat{u}_1, \bar{u}_1 \rangle = \langle \hat{u}_1, u_1 \rangle$, we obtain

$$ \begin{aligned} \langle \tilde{u}_2, \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle &= \frac{u_2^T}{\|\bar{u}_1\|_2 \|\bar{u}_2\|_2} \hat{U} \underbrace{\hat{U}^T \hat{U}}_I \left[ \begin{array}{c} \mp \langle \hat{u}_2, \bar{u}_1 \rangle \\ \pm \langle \hat{u}_1, \bar{u}_1 \rangle \end{array} \right] \\ &= \frac{1}{\|\bar{u}_1\|_2 \|\bar{u}_2\|_2} [\mp \langle u_2, \hat{u}_1 \rangle \langle \hat{u}_2, u_1 \rangle \pm \langle u_2, \hat{u}_2 \rangle \langle \hat{u}_1, u_1 \rangle] \\ &= \frac{1}{\|\bar{u}_1\|_2 \|\bar{u}_2\|_2} [\pm \det(U^T \hat{U})]. \end{aligned} $$

Recall the definition of $\delta$ in (5.2). The following simple claims will be useful for us.

**Claim 1** With $\delta$ as defined in (5.2) we have $|\det(U^T \hat{U})| \geq 1 - \delta^2$.
### C.3 Proof of Lemma 13

Note that Weyl's inequality (Weyl, 1912) (see Theorem 21) for singular value perturbation readily yields

$$ \sigma_i(H) \in [\sigma_i(\eta p C) \pm \Delta], \quad \forall i = 1, \dots, n. $$

In particular, using the expressions for $\sigma_1(C)$, $\sigma_2(C)$ from Lemma 11, we have that

$$ \begin{aligned} \sigma_1(H), \sigma_2(H) &\geq \eta p \sqrt{n} \|r - \alpha e\|_2 - \Delta, \\ \sigma_3(H), \dots, \sigma_n(H) &\leq \Delta. \end{aligned} $$

Then using Wedin's bound for perturbation of singular subspaces (Wedin, 1972) (see Theorem 22), we obtain

$$ \| \sin \Theta(\mathcal{R}(\hat{U}), \mathcal{R}(U)) \|_2 = \|(I - \hat{U}\hat{U}^T)U\|_2 \leq \frac{\Delta}{\eta p \sqrt{n} \|r - \alpha e\|_2 - \Delta} (= \delta), $$

provided $\Delta < \eta p \sqrt{n} \|r - \alpha e\|_2$ holds.

### C.4 Proof of Lemma 14

To begin with, note that $\bar{u}_1 = \hat{U}\hat{U}^T u_1$ is the orthogonal projection of $u_1$ on $\mathcal{R}(\hat{U})$. A unit vector orthogonal to $\bar{u}_1$ and lying in $\mathcal{R}(\hat{U})$ is given by

$$ \tilde{u}_2 = \frac{1}{\|\bar{u}_1\|_2} \hat{U} \begin{bmatrix} \mp \langle \hat{u}_2, \bar{u}_1 \rangle \\ \pm \langle \hat{u}_1, \bar{u}_1 \rangle \end{bmatrix}. $$

Denoting $\bar{u}_2$ to be the orthogonal projection of $u_2$ on $\mathcal{R}(\hat{U})$, we can decompose $\langle \tilde{u}_2, u_2 \rangle$ as

$$ \langle \tilde{u}_2, u_2 \rangle = \langle \tilde{u}_2, u_2 - \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle + \langle \tilde{u}_2, \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle, $$

which leads to

$$ |\langle \tilde{u}_2, u_2 \rangle| \geq |\langle \tilde{u}_2, \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle| - |\langle \tilde{u}_2, u_2 - \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle|. \quad (C.2) $$

We will now bound the two terms in the RHS of (C.2) starting with the first term.

**Lower bounding the first term in RHS of (C.2).** Since $\langle \hat{u}_2, \bar{u}_1 \rangle = \langle \hat{u}_2, u_1 \rangle$, $\langle \hat{u}_1, \bar{u}_1 \rangle = \langle \hat{u}_1, u_1 \rangle$, we obtain

$$ \begin{aligned} \langle \tilde{u}_2, \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle &= \frac{u_2^T}{\|\bar{u}_1\|_2 \|\bar{u}_2\|_2} \hat{U} \underbrace{\hat{U}^T \hat{U}}_I \begin{bmatrix} \mp \langle \hat{u}_2, \bar{u}_1 \rangle \\ \pm \langle \hat{u}_1, \bar{u}_1 \rangle \end{bmatrix} \\ &= \frac{1}{\|\bar{u}_1\|_2 \|\bar{u}_2\|_2} [\mp \langle u_2, \hat{u}_1 \rangle \langle \hat{u}_2, u_1 \rangle \pm \langle u_2, \hat{u}_2 \rangle \langle \hat{u}_1, u_1 \rangle] \\ &= \frac{1}{\|\bar{u}_1\|_2 \|\bar{u}_2\|_2} [\pm \det(U^T \hat{U})]. \end{aligned} $$

Recall the definition of $\delta$ in (5.2). The following simple claims will be useful for us.

**Claim 1** With $\delta$ as defined in (5.2) we have $|\det(U^T \hat{U})| \geq 1 - \delta^2$.
**Proof** Since $U^T\hat{U}$ is a $2 \times 2$ matrix, we have that

$$|\det(U^T\hat{U})| \geq \sigma_{min}^2(U^T\hat{U}) = 1 - \|\sin\Theta(\mathcal{R}(\hat{U}), \mathcal{R}(U))\|_2^2 \geq 1 - \delta^2.$$

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

**Claim 2** It holds that $\|\bar{u}_1 - u_1\|_2, \|\bar{u}_2 - u_2\|_2 \leq \delta$.

**Proof** We will only show the bound for $\|\bar{u}_1 - u_1\|_2$ as an identical argument holds for bounding $\|\bar{u}_2 - u_2\|_2$. Using the facts $\bar{u}_1 = \hat{U}\hat{U}u_1$ and $u_1 = UU^T u_1$, we obtain

$$\|u_1 - \bar{u}_1\|_2 = \|(I - \hat{U}\hat{U}^T)u_1\|_2 = \|(I - \hat{U}\hat{U}^T)UU^T u_1\|_2 \leq \|(I - \hat{U}\hat{U}^T)UU^T\|_2 = \|(I - \hat{U}\hat{U}^T)U\|_2 \leq \delta$$

where the last inequality follows from (5.2).

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

Using Claims 1, 2 we can lower bound the first term in RHS of (C.2) as follows.

$$\left| \langle \tilde{u}_2, \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle \right| \geq \frac{1 - \delta^2}{(1 + \delta)^2} = \frac{1 - \delta}{1 + \delta} = 1 - \frac{2\delta}{1 + \delta} \geq 1 - 2\delta. \quad (C.3)$$

**Upper bounding the second term in RHS of (C.2).** We can do this as follows.

$$\begin{align*}
\left| \langle \tilde{u}_2, u_2 - \frac{\bar{u}_2}{\|\bar{u}_2\|_2} \rangle \right| &\le \|u_2 - \frac{\bar{u}_2}{\|\bar{u}_2\|_2}\|_2 \quad \text{(Cauchy-Schwartz and since } \|\tilde{u}_2\|_2 = 1) \\
&= \|u_2 - \bar{u}_2 + \bar{u}_2 - \frac{\bar{u}_2}{\|\bar{u}_2\|_2}\|_2 \\
&\le \|u_2 - \bar{u}_2\|_2 + \|\bar{u}_2 - \frac{\bar{u}_2}{\|\bar{u}_2\|_2}\|_2 \\
&\le \delta + \left| 1 - \frac{1}{\|\bar{u}_2\|_2} \right| \quad \text{(Using Claim 2)} \\
&= \delta + \frac{\|\bar{u}_2\|_2 - 1}{\|\bar{u}_2\|_2} \\
&\le \delta + \frac{\delta}{1 - \delta} \quad \text{(since } \|\bar{u}_2\|_2 \in [1 - \delta, 1 + \delta] \text{ from Claim 2)} \\
&\le 3\delta \quad \text{(whenever } \delta \le 1/2). \tag{C.4}
\end{align*}$$

Altogether, we conclude that if $\delta \leq 1/2$ then using (C.3), (C.4) in (C.2), we obtain

$$|\langle \tilde{u}_2, u_2 \rangle| \geq 1 - 5\delta,$$

and consequently, there exists $\beta \in \{-1, 1\}$ such that

$$\|\tilde{u}_2 - \beta u_2\|_2^2 = 2 - 2\langle \tilde{u}_2, \beta u_2 \rangle \leq 10\delta. \quad (C.5)$$
**Proof** Since $U^T \hat{U}$ is a $2 \times 2$ matrix, we have that

$$ \left| \det(U^T \hat{U}) \right| \geq \sigma_{\min}^2 (U^T \hat{U}) = 1 - \| \sin \Theta(\mathcal{R}(\hat{U}), \mathcal{R}(U)) \|_2^2 \geq 1 - \delta^2. $$

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

**Claim 2** It holds that $\|\bar{u}_1 - u_1\|_2, \|\bar{u}_2 - u_2\|_2 \leq \delta$.

**Proof** We will only show the bound for $\|\bar{u}_1 - u_1\|_2$ as an identical argument holds for bounding $\|\bar{u}_2 - u_2\|_2$. Using the facts $\bar{u}_1 = \hat{U}\hat{U}u_1$ and $u_1 = UU^T u_1$, we obtain

$$ \|u_1 - \bar{u}_1\|_2 = \|(I - \hat{U}\hat{U}^T)u_1\|_2 = \|(I - \hat{U}\hat{U}^T)UU^T u_1\|_2 \le \|(I - \hat{U}\hat{U}^T)UU^T\|_2 = \|(I - \hat{U}\hat{U}^T)U\|_2 \le \delta $$

where the last inequality follows from (5.2).

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

Using Claims 1, 2 we can lower bound the first term in RHS of (C.2) as follows.

$$ \left| \langle \tilde{u}_2, \frac{\bar{u}_2}{||\bar{u}_2||_2} \rangle \right| \geq \frac{1 - \delta^2}{(1 + \delta)^2} = \frac{1 - \delta}{1 + \delta} = 1 - \frac{2\delta}{1 + \delta} \geq 1 - 2\delta. \quad (C.3) $$

**Upper bounding the second term in RHS of (C.2).** We can do this as follows.

$$ \begin{aligned} \left| \langle \tilde{u}_2, u_2 - \frac{\bar{u}_2}{||\bar{u}_2||_2} \rangle \right| &\le \|u_2 - \frac{\bar{u}_2}{||\bar{u}_2||_2}\|_2 && (\text{Cauchy-Schwartz and since } \|\tilde{u}_2\|_2 = 1) \\ &= \|u_2 - \bar{u}_2 + \bar{u}_2 - \frac{\bar{u}_2}{||\bar{u}_2||_2}\|_2 \\ &\le \|u_2 - \bar{u}_2\|_2 + \|\bar{u}_2 - \frac{\bar{u}_2}{||\bar{u}_2||_2}\|_2 \\ &\le \delta + \left| 1 - \frac{1}{||\bar{u}_2||_2} \right| && (\text{Using Claim 2}) \\ &= \delta + \frac{\|\bar{u}_2\|_2 - 1}{||\bar{u}_2||_2} \\ &\le \delta + \frac{\delta}{1 - \delta} && (\text{since } \|\bar{u}_2\|_2 \in [1 - \delta, 1 + \delta] \text{ from Claim 2}) \\ &\le 3\delta && (\text{whenever } \delta \le 1/2). \end{aligned} \quad (C.4) $$

Altogether, we conclude that if $\delta \le 1/2$ then using (C.3), (C.4) in (C.2), we obtain

$$ \left| \langle \tilde{u}_2, u_2 \rangle \right| \ge 1 - 5\delta, $$

and consequently, there exists $\beta \in \{-1, 1\}$ such that

$$ \|\tilde{u}_2 - \beta u_2\|_2^2 = 2 - 2\langle \tilde{u}_2, \beta u_2 \rangle \le 10\delta. \quad (C.5) $$
# Appendix D. Proof of Lemmas from Section 5.2

## D.1 Proof of Lemma 15

**Proof** Recall from the proof of Lemma 14 that

$$ \tilde{u}_2 = \frac{1}{\|\bar{u}_1\|_2} \hat{U} \begin{bmatrix} \mp \langle \hat{u}_2, \bar{u}_1 \rangle \\ \pm \langle \hat{u}_1, \bar{u}_1 \rangle \end{bmatrix} = \frac{1}{\|\bar{u}_1\|_2} \hat{U} \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} \hat{U}^T \bar{u}_1 = \frac{1}{\|\bar{u}_1\|_2} \hat{U} \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} \hat{U}^T u_1, \qquad (D.1) $$

where the last equality follows from the fact $\langle \hat{u}_2, \bar{u}_1 \rangle = \langle \hat{u}_2, u_1 \rangle$, $\langle \hat{u}_1, \bar{u}_1 \rangle = \langle \hat{u}_1, u_1 \rangle$. Let $O$ be any $2 \times 2$ orthogonal matrix, clearly, $UO$ also corresponds to the two largest left singular vectors of $E[H]$ (since $\sigma_1(E[H]) = \sigma_2(E[H])$). Denote $P = \hat{U} - UO$. Plugging in (D.1), we obtain

$$ \begin{aligned} \tilde{u}_2 &= \frac{1}{\|\bar{u}_1\|_2} \hat{U} \underbrace{\begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix}}_{D} \hat{U}^T \bar{u}_1 [O^T U^T + P] u_1 \\ &= \pm \det(O) u_2 + \underbrace{\frac{1}{\|\bar{u}_1\|_2} U O D P^T u_1}_{w_1} + \underbrace{\frac{1}{\|\bar{u}_1\|_2} P D O^T U^T u_1}_{w_2} + \underbrace{\frac{1}{\|\bar{u}_1\|_2} P D P^T u_1}_{w_3} \\ &\Rightarrow \|\tilde{u}_2\mp \det(O) u_2\|_{\infty} \le \|w_1\|_{\infty} + \|w_2\|_{\infty} + \|w_3\|_{\infty}. \end{aligned} \qquad (D.2) $$

Denoting

$$ P = [p_1 \ p_2], \quad O = \begin{bmatrix} o_{11} & o_{12} \\ o_{21} & o_{22} \end{bmatrix} $$

we will now bound $\|w_1\|_{\infty}, \|w_2\|_{\infty}, \|w_3\|_{\infty}$.

To begin with,

$$ \begin{aligned} w_1 &= \frac{1}{\|\bar{u}_1\|_2} [u_1 \ u_2] O \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} \begin{bmatrix} \langle p_1, u_1 \rangle \\ \langle p_2, u_1 \rangle \end{bmatrix} \\ &= \frac{1}{\|\bar{u}_1\|_2} [u_1 \ u_2] O \begin{bmatrix} \mp \langle p_2, u_1 \rangle \\ \pm \langle p_1, u_1 \rangle \end{bmatrix} \\ &= \frac{1}{\|\bar{u}_1\|_2} [u_1 \ u_2] \begin{bmatrix} \mp o_{11} \langle p_2, u_1 \rangle \pm o_{12} \langle p_1, u_1 \rangle \\ \mp o_{21} \langle p_2, u_1 \rangle \pm o_{22} \langle p_1, u_1 \rangle \end{bmatrix} \\ &\Rightarrow \|w_1\|_{\infty} \le \frac{1}{\|\bar{u}_1\|_2} \left[ (|\langle p_2, u_1 \rangle| + |\langle p_1, u_1 \rangle|)(\|u_1\|_{\infty} + \|u_2\|_{\infty}) \right]. \end{aligned} \qquad (D.3) $$

Clearly, $\|u_1\|_{\infty} = \frac{1}{\sqrt{n}}$ and $\|u_2\|_{\infty} \le \frac{M-\alpha}{\|r-\alpha e\|_2}$. Using Hölder's inequality,

$$ |\langle p_i, u_1 \rangle| \le \|P\|_{\max} \|u\|_1 = \|P\|_{\max} \sqrt{n}; \quad i = 1, 2. $$

Moreover, from Claim 2, we know that $\|\bar{u}_1\|_2 \ge 1 - \delta$ where we recall $\delta$ defined in (5.2). We saw in (5.3) that $\Delta \le \frac{\eta p \|r-\alpha e\|_2 \sqrt{n}}{3} \Leftrightarrow \delta \le 1/2$, which implies $\|\bar{u}_1\|_2 \ge 1/2$. Plugging these bounds in (D.3), we obtain

$$ \|w_1\|_{\infty} \le 4 \|P\|_{\max} \left( 1 + \frac{\sqrt{n}(M-\alpha)}{\|r-\alpha e\|_2} \right). \qquad (D.4) $$
# Appendix D. Proof of Lemmas from Section 5.2

## D.1 Proof of Lemma 15

**Proof** Recall from the proof of Lemma 14 that

$$ \tilde{u}_2 = \frac{1}{\|\bar{u}_1\|_2} \hat{U} \begin{bmatrix} \mp \langle \hat{u}_2, \bar{u}_1 \rangle \\ \pm \langle \hat{u}_1, \bar{u}_1 \rangle \end{bmatrix} = \frac{1}{\|\bar{u}_1\|_2} \hat{U} \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} \hat{U}^T \bar{u}_1 = \frac{1}{\|\bar{u}_1\|_2} \hat{U} \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} \hat{U}^T u_1, \qquad (D.1) $$

where the last equality follows from the fact $\langle \hat{u}_2, \bar{u}_1 \rangle = \langle \hat{u}_2, u_1 \rangle$, $\langle \hat{u}_1, \bar{u}_1 \rangle = \langle \hat{u}_1, u_1 \rangle$. Let $O$ be any $2 \times 2$ orthogonal matrix, clearly, $UO$ also corresponds to the two largest left singular vectors of $E[H]$ (since $\sigma_1(E[H]) = \sigma_2(E[H])$). Denote $P = \hat{U} - UO$. Plugging in (D.1), we obtain

$$ \begin{aligned} \tilde{u}_2 &= \frac{1}{\|\bar{u}_1\|_2} \hat{U} \underbrace{\begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix}}_{D} \hat{U}^T \bar{u}_1 [O^T U^T + P] u_1 \\ &= \pm \det(O) u_2 + \underbrace{\frac{1}{\|\bar{u}_1\|_2} U O D P^T u_1}_{w_1} + \underbrace{\frac{1}{\|\bar{u}_1\|_2} P D O^T U^T u_1}_{w_2} + \underbrace{\frac{1}{\|\bar{u}_1\|_2} P D P^T u_1}_{w_3} \\ &\Rightarrow \|\tilde{u}_2\mp \det(O) u_2\|_{\infty} \le \|w_1\|_{\infty} + \|w_2\|_{\infty} + \|w_3\|_{\infty}. \end{aligned} \qquad (D.2) $$

Denoting

$$ P = [p_1 \ p_2], \quad O = \begin{bmatrix} o_{11} & o_{12} \\ o_{21} & o_{22} \end{bmatrix} $$

we will now bound $\|w_1\|_{\infty}, \|w_2\|_{\infty}, \|w_3\|_{\infty}$.

To begin with,

$$ \begin{aligned} w_1 &= \frac{1}{\|\bar{u}_1\|_2} [u_1 \ u_2] O \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} \begin{bmatrix} \langle p_1, u_1 \rangle \\ \langle p_2, u_1 \rangle \end{bmatrix} \\ &= \frac{1}{\|\bar{u}_1\|_2} [u_1 \ u_2] O \begin{bmatrix} \mp \langle p_2, u_1 \rangle \\ \pm \langle p_1, u_1 \rangle \end{bmatrix} \\ &= \frac{1}{\|\bar{u}_1\|_2} [u_1 \ u_2] \begin{bmatrix} \mp o_{11} \langle p_2, u_1 \rangle \pm o_{12} \langle p_1, u_1 \rangle \\ \mp o_{21} \langle p_2, u_1 \rangle \pm o_{22} \langle p_1, u_1 \rangle \end{bmatrix} \\ &\Rightarrow \|w_1\|_{\infty} \le \frac{1}{\|\bar{u}_1\|_2} \left[ (|\langle p_2, u_1 \rangle| + |\langle p_1, u_1 \rangle|)(\|u_1\|_{\infty} + \|u_2\|_{\infty}) \right]. \end{aligned} \qquad (D.3) $$

Clearly, $\|u_1\|_{\infty} = \frac{1}{\sqrt{n}}$ and $\|u_2\|_{\infty} \le \frac{M-\alpha}{\|r-\alpha e\|_2}$. Using Hölder's inequality,

$$ |\langle p_i, u_1 \rangle| \le \|P\|_{\max} \|u\|_1 = \|P\|_{\max} \sqrt{n}; \quad i = 1, 2. $$

Moreover, from Claim 2, we know that $\|\bar{u}_1\|_2 \ge 1 - \delta$ where we recall $\delta$ defined in (5.2). We saw in (5.3) that $\Delta \le \frac{\eta p \|r-\alpha e\|_2 \sqrt{n}}{3} \Leftrightarrow \delta \le 1/2$, which implies $\|\bar{u}_1\|_2 \ge 1/2$. Plugging these bounds in (D.3), we obtain

$$ \|w_1\|_{\infty} \le 4 \|P\|_{\max} \left( 1 + \frac{\sqrt{n}(M-\alpha)}{\|r-\alpha e\|_2} \right). \qquad (D.4) $$
Next, we can bound $||w_2||_\infty$ as follows.

$$ 
\begin{aligned}
w_2 &= \frac{1}{||\bar{u}_1||_2} [p_1 \ p_2] \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} O^T \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\
&= \frac{1}{||\bar{u}_1||_2} [p_1 \ p_2] \begin{bmatrix} \mp o_{12} \\ \pm o_{11} \end{bmatrix} \\
\Rightarrow ||w_2||_\infty &\le \frac{2||P||_{\max}}{||\bar{u}_1||_2} \le 4||P||_{\max}
\end{aligned} 
\quad (D.5) $$

since $\Delta \le \frac{\eta p ||r - \alpha e||_2 \sqrt{n}}{3}$.

We now bound $||w_3||_\infty$.

$$ 
\begin{aligned}
w_3 &= \frac{1}{||\bar{u}_1||_2} [p_1 \ p_2] \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} \begin{bmatrix} \langle p_1, u_1 \rangle \\ \langle p_2, u_1 \rangle \end{bmatrix} \\
&= \frac{1}{||\bar{u}_1||_2} [p_1 \ p_2] \begin{bmatrix} \mp \langle p_2, u_1 \rangle \\ \pm \langle p_1, u_1 \rangle \end{bmatrix} \\
\Rightarrow ||w_3||_\infty &\le \frac{1}{||\bar{u}_1||_2} (|\langle p_2, u_1 \rangle| + |\langle p_1, u_1 \rangle|) ||P||_{\max} \\
&\le 4 ||P||_{\max}^2 ||u_1||_1 = 4 \sqrt{n} ||P||_{\max}^2 \quad (\text{since } \Delta \le \frac{\eta p ||r - \alpha e||_2 \sqrt{n}}{3} \text{ and using Hölder's inequality}).
\end{aligned} 
\quad (D.6) $$

Plugging (D.4), (D.5), (D.6) in (D.2), we obtain

$$ 
\begin{aligned}
||\tilde{u}_2 \mp \det(O) u_2||_\infty &\le 4||P||_{\max} \left(2 + \frac{\sqrt{n}(M-\alpha)}{||r-\alpha e||_2}\right) + 4\sqrt{n}||P||_{\max}^2 \\
&= 4||\hat{U} - UO||_{\max} \left(2 + \frac{\sqrt{n}(M-\alpha)}{||r-\alpha e||_2}\right) + 4\sqrt{n}||\hat{U} - UO||_{\max}^2.
\end{aligned} 
$$

The above bound is true for any orthogonal matrix $O$, it is not difficult to see that there exists an orthogonal matrix $O = O^*$ such that $\hat{U}$ is “aligned” with $UO^*$. Indeed, for any orthogonal $O$, we first obtain via triangle inequality that

$$ 
\|\hat{U} - UO\|_2 \le \|(I - UU^T)\hat{U}\|_2 + \|UU^T\hat{U} - UO\|_2 = \|\sin\Theta(\mathcal{R}(U), \mathcal{R}(\hat{U}))\|_2 + \|U^T\hat{U} - O\|_2. 
\quad (D.7) $$

Denoting $\tilde{U}\tilde{D}\tilde{V}^T$ to be the SVD of $U^T\hat{U}$, we choose $O = O^* = \tilde{U}\tilde{V}^T$ (so $O^*$ is orthogonal). Denoting $\theta_p$ to be the principal angle between $\mathcal{R}(U)$, $\mathcal{R}(\hat{U})$, we obtain

$$ ||U^T \hat{U} - O^*||_2 = ||I - \tilde{D}||_2 = 1 - \cos \theta_p \le \sin \theta_p = ||\sin \Theta(\mathcal{R}(U), \mathcal{R}(\hat{U}))||_2. $$

Plugging this in (D.7) leads to

$$ 
\begin{aligned}
||\hat{U} - UO^*||_2 &\le 2||\sin\Theta(\mathcal{R}(U), \mathcal{R}(\hat{U}))||_2 \\
&\le \frac{2\Delta}{\eta p \sqrt{n} ||r - \alpha e||_2 - \Delta} \quad (\text{see proof of Lemma 13}) \\
&\le \frac{3\Delta}{\eta p \sqrt{n} ||r - \alpha e||_2} \quad (\text{since } \Delta \le \frac{\eta p ||r - \alpha e||_2 \sqrt{n}}{3})
\end{aligned} 
$$
Next, we can bound $||w_2||_\infty$ as follows.

$$ 
\begin{aligned}
w_2 &= \frac{1}{||\bar{u}_1||_2} [p_1 \ p_2] \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} O^T \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\
&= \frac{1}{||\bar{u}_1||_2} [p_1 \ p_2] \begin{bmatrix} \mp o_{12} \\ \pm o_{11} \end{bmatrix} \\
\Rightarrow ||w_2||_\infty &\le \frac{2||P||_{\max}}{||\bar{u}_1||_2} \le 4||P||_{\max} \qquad (D.5)
\end{aligned}
$$

since $\Delta \le \frac{\eta p ||r - \alpha e||_2 \sqrt{n}}{3}$.

We now bound $||w_3||_\infty$.

$$ 
\begin{aligned}
w_3 &= \frac{1}{||\bar{u}_1||_2} [p_1 \ p_2] \begin{bmatrix} 0 & \mp 1 \\ \pm 1 & 0 \end{bmatrix} \begin{bmatrix} \langle p_1, u_1 \rangle \\ \langle p_2, u_1 \rangle \end{bmatrix} \\
&= \frac{1}{||\bar{u}_1||_2} [p_1 \ p_2] \begin{bmatrix} \mp \langle p_2, u_1 \rangle \\ \pm \langle p_1, u_1 \rangle \end{bmatrix} \\
\Rightarrow ||w_3||_\infty &\le \frac{1}{||\bar{u}_1||_2} (|\langle p_2, u_1 \rangle| + |\langle p_1, u_1 \rangle|) ||P||_{\max} \\
&\le 4 ||P||_{\max}^2 ||u_1||_1 = 4 \sqrt{n} ||P||_{\max}^2 \quad (\text{since } \Delta \le \frac{\eta p ||r - \alpha e||_2 \sqrt{n}}{3} \text{ and using Hölder's inequality}). \qquad (D.6)
\end{aligned}
$$

Plugging (D.4), (D.5), (D.6) in (D.2), we obtain

$$ 
\begin{aligned}
||\tilde{u}_2 \mp \det(O) u_2||_\infty &\le 4||P||_{\max} \left(2 + \frac{\sqrt{n}(M-\alpha)}{||r-\alpha e||_2}\right) + 4\sqrt{n}||P||_{\max}^2 \\
&= 4||\hat{U} - UO||_{\max} \left(2 + \frac{\sqrt{n}(M-\alpha)}{||r-\alpha e||_2}\right) + 4\sqrt{n}||\hat{U} - UO||_{\max}^2.
\end{aligned}
$$

The above bound is true for any orthogonal matrix $O$, it is not difficult to see that there exists an orthogonal matrix $O = O^*$ such that $\hat{U}$ is “aligned” with $UO^*$. Indeed, for any orthogonal $O$, we first obtain via triangle inequality that

$$ 
\|\hat{U} - UO\|_2 \le \|(I - UU^T)\hat{U}\|_2 + \|UU^T\hat{U} - UO\|_2 = \|\sin\Theta(\mathcal{R}(U), \mathcal{R}(\hat{U}))\|_2 + \|U^T\hat{U} - O\|_2. \qquad (D.7)
$$

Denoting $\tilde{U}\tilde{D}\tilde{V}^T$ to be the SVD of $U^T\hat{U}$, we choose $O = O^* = \tilde{U}\tilde{V}^T$ (so $O^*$ is orthogonal). Denoting $\theta_p$ to be the principal angle between $\mathcal{R}(U), \mathcal{R}(\hat{U})$, we obtain

$$ ||U^T\hat{U} - O^*||_2 = ||I - \tilde{D}||_2 = 1 - \cos \theta_p \le \sin \theta_p = ||\sin \Theta(\mathcal{R}(U), \mathcal{R}(\hat{U}))||_2. $$

Plugging this in (D.7) leads to

$$ 
\begin{aligned}
||\hat{U} - UO^*||_2 &\le 2||\sin\Theta(\mathcal{R}(U), \mathcal{R}(\hat{U}))||_2 \\
&\le \frac{2\Delta}{\eta p \sqrt{n} ||r - \alpha e||_2 - \Delta} \quad (\text{see proof of Lemma 13}) \\
&\le \frac{3\Delta}{\eta p \sqrt{n} ||r - \alpha e||_2} \quad (\text{since } \Delta \le \frac{\eta p ||r - \alpha e||_2 \sqrt{n}}{3})
\end{aligned}
$$
<figure><img src="image_17.png" /></figure>

## D.2 Proof of Lemma 16

### Proof

1. (Bounding $\|E_1\|_{\max}$) Denoting $(\hat{U} - UO^*)_i$ to be the $i^{th}$ column of $\hat{U} - UO^*$, we note that

$$
\begin{align*}
E_1 &= -\mathbb{E}[H]^2(\hat{U} - UO^*)\hat{\Sigma}^{-2} \\
&= \sigma^2 UU^T (\hat{U}^T - UO^*)\hat{\Sigma}^{-2} \\
&= (u_1 u_1^T + u_2 u_2^T) \left[ (\hat{U} - UO^*)_1 \frac{\hat{\sigma}_1^2}{\hat{\sigma}_1^2} \quad (\hat{U} - UO^*)_2 \frac{\hat{\sigma}_2^2}{\hat{\sigma}_2^2} \right] \\
&= \left[ u_1 \langle u_1, (\hat{U} - UO^*)_1 \rangle \frac{\hat{\sigma}_1^2}{\hat{\sigma}_1^2} + u_2 \langle u_2, (\hat{U} - UO^*)_1 \rangle \frac{\hat{\sigma}_2^2}{\hat{\sigma}_2^2} \quad u_1 \langle u_1, (\hat{U} - UO^*)_2 \rangle \frac{\hat{\sigma}_1^2}{\hat{\sigma}_1^2} + u_2 \langle u_2, (\hat{U} - UO^*)_2 \rangle \frac{\hat{\sigma}_2^2}{\hat{\sigma}_2^2} \right]
\end{align*}
$$

For the $i^{th}$ entry in the first column ($i = 1, \dots, n$), we have that

$$
\left| u_{1,i} \langle u_1, (\hat{U} - UO^*)_1 \rangle \frac{\sigma^2}{\hat{\sigma}_1^2} + u_{2,i} \langle u_2, (\hat{U} - UO^*)_1 \rangle \frac{\sigma^2}{\hat{\sigma}_1^2} \right| \le \|u_1\|_{\infty} \underbrace{\|(\hat{U} - UO^*)_1\|_2}_{\le \|\hat{U} - UO^*\|_2} \frac{\sigma^2}{\hat{\sigma}_1^2} + \|u_2\|_{\infty} \underbrace{\|(\hat{U} - UO^*)_1\|_2}_{\le \|\hat{U} - UO^*\|_2} \frac{\sigma^2}{\hat{\sigma}_1^2}.
$$

Since $\|u_1\|_{\infty} = \frac{1}{\sqrt{n}}$, $\|u_2\|_{\infty} \le \frac{M-\alpha}{\|r-\alpha e\|_2}$, and $\hat{\sigma}_1 \ge \sigma - \Delta \ge \frac{2\sigma}{3}$, we obtain

$$
\begin{align*}
& \left| u_{1,i} \langle u_1, (\hat{U} - UO^*)_1 \rangle \frac{\sigma^2}{\hat{\sigma}_1^2} + u_{2,i} \langle u_2, (\hat{U} - UO^*)_1 \rangle \frac{\sigma^2}{\hat{\sigma}_1^2} \right| \\
& \le \frac{9}{4} \|\hat{U} - UO^*\|_2 \left( \frac{1}{\sqrt{n}} + \frac{M-\alpha}{\|r-\alpha e\|_2} \right) \\
& \le \frac{27\Delta}{4\sigma} \left( \frac{1}{\sqrt{n}} + \frac{M-\alpha}{\|r-\alpha e\|_2} \right)
\end{align*}
$$

where in the last inequality, we used $\|\hat{U} - UO^*\|_2 \le \frac{3\Delta}{\sigma}$ (from Lemma 15). The same entry-wise bound holds for the second column, leading to the stated bound on $\|E_1\|_{\max}$.

2. (Bounding $\|E_2\|_{\max}$) Denoting the $(i,j)^{th}$ entry of $O^*$ by $o_{ij}^*$, we have that

$$
\begin{align*}
E_2 &= \mathbb{E}[H]^2 UO^* (\sigma^{-2} I - \hat{\Sigma}^{-2}) \\
&= -UU^T \sigma^2 (UO^*) \begin{bmatrix} \sigma^{-2} - \hat{\sigma}_1^{-2} & 0 \\ 0 & \sigma^{-2} - \hat{\sigma}_2^{-2} \end{bmatrix} \\
&= -\sigma^2 \left[ (\sigma^{-2} - \hat{\sigma}_1^{-2})(u_1 o_{11}^* + u_2 o_{21}^*) \quad (\sigma^{-2} - \hat{\sigma}_2^{-2})(u_1 o_{12}^* + u_2 o_{22}^*) \right].
\end{align*}
$$
<figure><img src="image_17.png" /></figure>

## D.2 Proof of Lemma 16

### Proof

1. (Bounding $\|E_1\|_{\max}$) Denoting $(\hat{U} - UO^*)_i$ to be the $i^{th}$ column of $\hat{U} - UO^*$, we note that

$$ 
\begin{aligned}
E_1 &= -\mathbb{E}[H]^2(\hat{U} - UO^*)\hat{\Sigma}^{-2} \\
&= \sigma^2 UU^T(\hat{U}^T - UO^*)\hat{\Sigma}^{-2} \\
&= (u_1u_1^T + u_2u_2^T) \left[ (\hat{U} - UO^*)_1 \frac{\hat{\sigma}_1^2}{\hat{\sigma}_1^2} + (\hat{U} - UO^*)_2 \frac{\hat{\sigma}_2^2}{\hat{\sigma}_2^2} \right] \\
&= \left[ u_1\langle u_1, (\hat{U} - UO^*)_1 \rangle \frac{\hat{\sigma}_1^2}{\hat{\sigma}_1^2} + u_2\langle u_2, (\hat{U} - UO^*)_1 \rangle \frac{\hat{\sigma}_2^2}{\hat{\sigma}_2^2} \quad u_1\langle u_1, (\hat{U} - UO^*)_2 \rangle \frac{\hat{\sigma}_1^2}{\hat{\sigma}_1^2} + u_2\langle u_2, (\hat{U} - UO^*)_2 \rangle \frac{\hat{\sigma}_2^2}{\hat{\sigma}_2^2} \right]
\end{aligned}
$$

For the $i^{th}$ entry in the first column ($i = 1, \dots, n$), we have that

$$ 
\begin{aligned}
& \left| u_{1,i}\langle u_1, (\hat{U} - UO^*)_1 \rangle \frac{\hat{\sigma}_1^2}{\hat{\sigma}_1^2} + u_{2,i}\langle u_2, (\hat{U} - UO^*)_1 \rangle \frac{\hat{\sigma}_2^2}{\hat{\sigma}_2^2} \right| \\
& \le \|u_1\|_{\infty} \underbrace{\|(\hat{U} - UO^*)_1\|_2}_{\le \|\hat{U} - UO^*\|_2} \frac{\hat{\sigma}_1^2}{\hat{\sigma}_1^2} + \|u_2\|_{\infty} \underbrace{\|(\hat{U} - UO^*)_1\|_2}_{\le \|\hat{U} - UO^*\|_2} \frac{\hat{\sigma}_2^2}{\hat{\sigma}_2^2}.
\end{aligned}
$$

Since $\|u_1\|_{\infty} = \frac{1}{\sqrt{n}}$, $\|u_2\|_{\infty} \le \frac{M-\alpha}{\|r-\alpha e\|_2}$, and $\hat{\sigma}_1 \ge \sigma - \Delta \ge \frac{2\sigma}{3}$, we obtain

$$ 
\begin{aligned}
& \left| u_{1,i}\langle u_1, (\hat{U} - UO^*)_1 \rangle \frac{\hat{\sigma}_1^2}{\hat{\sigma}_1^2} + u_{2,i}\langle u_2, (\hat{U} - UO^*)_1 \rangle \frac{\hat{\sigma}_2^2}{\hat{\sigma}_2^2} \right| \\
& \le \frac{9}{4} \|\hat{U} - UO^*\|_2 \left( \frac{1}{\sqrt{n}} + \frac{M-\alpha}{\|r-\alpha e\|_2} \right) \\
& \le \frac{27\Delta}{4\sigma} \left( \frac{1}{\sqrt{n}} + \frac{M-\alpha}{\|r-\alpha e\|_2} \right)
\end{aligned}
$$

where in the last inequality, we used $\|\hat{U} - UO^*\|_2 \le \frac{3\Delta}{\sigma}$ (from Lemma 15). The same entry-wise bound holds for the second column, leading to the stated bound on $\|E_1\|_{\max}$.

2. (Bounding $\|E_2\|_{\max}$) Denoting the $(i,j)^{th}$ entry of $O^*$ by $o_{ij}^*$, we have that

$$ 
\begin{aligned}
E_2 &= \mathbb{E}[H]^2 UO^* (\sigma^{-2}I - \hat{\Sigma}^{-2}) \\
&= -UU^T \sigma^2 (UO^*) \begin{bmatrix} \sigma^{-2} - \hat{\sigma}_1^{-2} & 0 \\ 0 & \sigma^{-2} - \hat{\sigma}_2^{-2} \end{bmatrix} \\
&= -\sigma^2 \left[ (\sigma^{-2} - \hat{\sigma}_1^{-2})(u_1o_{11}^* + u_2o_{21}^*) \quad (\sigma^{-2} - \hat{\sigma}_2^{-2})(u_1o_{12}^* + u_2o_{22}^*) \right].
\end{aligned}
$$
Hence the $i^{th}$ entry of the first column can be bounded as follows.

$$ 
\begin{aligned}
\sigma^2 |\sigma^{-2} - \hat{\sigma}_1^{-2}| |u_{1,i}o_{11}^* + u_{2,i}o_{12}^*| &\le \frac{\Delta(2\sigma + \Delta)}{(\sigma - \Delta)^2} (\|u_1\|_{\infty} + \|u_2\|_{\infty}) \quad (\text{using } |\hat{\sigma}_1 - \sigma| \le \Delta) \\
&\le \frac{21\Delta}{4\sigma} \left( \frac{1}{\sqrt{n}} + \frac{M - \alpha}{\|r - \alpha e\|_2} \right) \quad (\text{using } \Delta \le \frac{\sigma}{3}).
\end{aligned}
$$

The same entry-wise bound holds for the second column, leading to the stated bound on $\|E_2\|_{\max}$.

3. (Bounding $\|E_3\|_{\max}$) We have that

$$ 
\begin{aligned}
E_3 &= -\mathbb{E}[H]Z\hat{U}\hat{\Sigma}^{-2} \\
&= -\sigma(u_1v_1^T + u_2v_2^T)Z[\hat{\sigma}_1^{-2}\hat{u}_1 \quad \hat{\sigma}_2^{-2}\hat{u}_2] \\
&= -\sigma[u_1\langle v_1, Z\hat{u}_1\rangle\hat{\sigma}_1^{-2} + u_2\langle v_2, Z\hat{u}_1\rangle\hat{\sigma}_1^{-2} \quad u_1\langle v_1, Z\hat{u}_2\rangle\hat{\sigma}_2^{-2} + u_2\langle v_2, Z\hat{u}_2\rangle\hat{\sigma}_2^{-2}].
\end{aligned}
$$

The $i^{th}$ entry of the first column can be bounded as follows.

$$ 
\begin{aligned}
\sigma |u_{1,i}\langle v_1, Z\hat{u}_1\rangle\hat{\sigma}_1^{-2} + u_{2,i}\langle v_2, Z\hat{u}_1\rangle\hat{\sigma}_1^{-2}| &\le \frac{\sigma}{\hat{\sigma}_1^2}(\|u_1\|_{\infty}|\langle v_1, Z\hat{u}_1\rangle| + \|u_2\|_{\infty}|\langle v_2, Z\hat{u}_1\rangle|) \\
&\le \frac{\sigma}{\hat{\sigma}_1^2}\|Z\|_2 \left( \frac{1}{\sqrt{n}} + \frac{M - \alpha}{\|r - \alpha e\|_2} \right) \quad (\text{using Cauchy-Schwarz}) \\
&\le \frac{9\Delta}{4\sigma} \left( \frac{1}{\sqrt{n}} + \frac{M - \alpha}{\|r - \alpha e\|_2} \right) \quad (\text{using } \hat{\sigma}_1 \ge 2\sigma/3).
\end{aligned}
$$

The same entry-wise bound holds for the second column, leading to the stated bound on $\|E_3\|_{\max}$.

4. (Bounding $\|E_4\|_{\max}$) We have that

$$ 
\begin{aligned}
E_4 &= Z\mathbb{E}[H]\hat{U}\hat{\Sigma}^{-2} = \sigma Z(u_1v_1^T + u_2v_2^T)[\hat{\sigma}_1^{-2}\hat{u}_1 \quad \hat{\sigma}_2^{-2}\hat{u}_2] \\
&= \sigma \left[ Z u_1 \frac{v_1^T \hat{u}_1}{\hat{\sigma}_1^2} + Z u_2 \frac{v_2^T \hat{u}_1}{\hat{\sigma}_1^2} \quad Z u_1 \frac{v_1^T \hat{u}_2}{\hat{\sigma}_2^2} + Z u_2 \frac{v_2^T \hat{u}_2}{\hat{\sigma}_2^2} \right].
\end{aligned}
$$

The magnitude of the $i^{th}$ entry of the first column can be bounded as

$$ 
\begin{aligned}
\frac{\sigma}{\hat{\sigma}_1^2} |(v_1^T \hat{u}_1)(Z u_1)_i + (v_2^T \hat{u}_1)(Z u_2)_i| &\le \frac{\sigma}{\hat{\sigma}_1^2} (\|Z u_1\|_{\infty} + \|Z u_2\|_{\infty}) \quad (\text{Using Cauchy-Schwarz}) \\
&\le \frac{9}{4\sigma} (\|Z u_1\|_{\infty} + \|Z u_2\|_{\infty}) \quad (\text{using } \hat{\sigma}_1 \ge 2\sigma/3).
\end{aligned}
$$

The same entry-wise bound holds for the second column, leading to the stated bound on $\|E_4\|_{\max}$.

5. (Bounding $\|E_5\|_{\max}$) We can write

$$ E_5 = Z^2 \hat{U} \hat{\Sigma}^{-2} = Z^2 (\hat{U} - UO^*) \hat{\Sigma}^{-2} + Z^2 (UO^*) \hat{\Sigma}^{-2} $$
Hence the $i^{th}$ entry of the first column can be bounded as follows.

$$ 
\begin{aligned}
\sigma^2 |\sigma^{-2} - \hat{\sigma}_1^{-2}| |u_{1,i}o_{11}^* + u_{2,i}o_{12}^*| &\le \frac{\Delta(2\sigma + \Delta)}{(\sigma - \Delta)^2} (\|u_1\|_{\infty} + \|u_2\|_{\infty}) \quad (\text{using } |\hat{\sigma}_1 - \sigma| \le \Delta) \\
&\le \frac{21\Delta}{4\sigma} \left( \frac{1}{\sqrt{n}} + \frac{M - \alpha}{\|r - \alpha e\|_2} \right) \quad (\text{using } \Delta \le \frac{\sigma}{3}).
\end{aligned}
$$

The same entry-wise bound holds for the second column, leading to the stated bound on $\|E_2\|_{\max}$.

3. (Bounding $\|E_3\|_{\max}$) We have that

$$ 
\begin{aligned}
E_3 &= -\mathbb{E}[H]Z\hat{U}\hat{\Sigma}^{-2} \\
&= -\sigma(u_1v_1^T + u_2v_2^T)Z[\hat{\sigma}_1^{-2}\hat{u}_1 \quad \hat{\sigma}_2^{-2}\hat{u}_2] \\
&= -\sigma[u_1\langle v_1, Z\hat{u}_1\rangle\hat{\sigma}_1^{-2} + u_2\langle v_2, Z\hat{u}_1\rangle\hat{\sigma}_1^{-2} \quad u_1\langle v_1, Z\hat{u}_2\rangle\hat{\sigma}_2^{-2} + u_2\langle v_2, Z\hat{u}_2\rangle\hat{\sigma}_2^{-2}].
\end{aligned}
$$

The $i^{th}$ entry of the first column can be bounded as follows.

$$ 
\begin{aligned}
\sigma |u_{1,i}\langle v_1, Z\hat{u}_1\rangle\hat{\sigma}_1^{-2} + u_{2,i}\langle v_2, Z\hat{u}_1\rangle\hat{\sigma}_1^{-2}| &\le \frac{\sigma}{\hat{\sigma}_1^2}(\|u_1\|_{\infty}|\langle v_1, Z\hat{u}_1\rangle| + \|u_2\|_{\infty}|\langle v_2, Z\hat{u}_1\rangle|) \\
&\le \frac{\sigma}{\hat{\sigma}_1^2}\|Z\|_2 \left( \frac{1}{\sqrt{n}} + \frac{M - \alpha}{\|r - \alpha e\|_2} \right) \quad (\text{using Cauchy-Schwarz}) \\
&\le \frac{9\Delta}{4\sigma} \left( \frac{1}{\sqrt{n}} + \frac{M - \alpha}{\|r - \alpha e\|_2} \right) \quad (\text{using } \hat{\sigma}_1 \ge 2\sigma/3).
\end{aligned}
$$

The same entry-wise bound holds for the second column, leading to the stated bound on $\|E_3\|_{\max}$.

4. (Bounding $\|E_4\|_{\max}$) We have that

$$ 
\begin{aligned}
E_4 &= Z\mathbb{E}[H]\hat{U}\hat{\Sigma}^{-2} = \sigma Z(u_1v_1^T + u_2v_2^T)[\hat{\sigma}_1^{-2}\hat{u}_1 \quad \hat{\sigma}_2^{-2}\hat{u}_2] \\
&= \sigma \left[ Z u_1 \frac{v_1^T \hat{u}_1}{\hat{\sigma}_1^2} + Z u_2 \frac{v_2^T \hat{u}_1}{\hat{\sigma}_1^2} \quad Z u_1 \frac{v_1^T \hat{u}_2}{\hat{\sigma}_2^2} + Z u_2 \frac{v_2^T \hat{u}_2}{\hat{\sigma}_2^2} \right].
\end{aligned}
$$

The magnitude of the $i^{th}$ entry of the first column can be bounded as

$$ 
\begin{aligned}
\frac{\sigma}{\hat{\sigma}_1^2} |(v_1^T \hat{u}_1)(Z u_1)_i + (v_2^T \hat{u}_1)(Z u_2)_i| &\le \frac{\sigma}{\hat{\sigma}_1^2} (\|Z u_1\|_{\infty} + \|Z u_2\|_{\infty}) \quad (\text{Using Cauchy-Schwarz}) \\
&\le \frac{9}{4\sigma} (\|Z u_1\|_{\infty} + \|Z u_2\|_{\infty}) \quad (\text{using } \hat{\sigma}_1 \ge 2\sigma/3).
\end{aligned}
$$

The same entry-wise bound holds for the second column, leading to the stated bound on $\|E_4\|_{\max}$.

5. (Bounding $\|E_5\|_{\max}$) We can write

$$ E_5 = Z^2 \hat{U} \hat{\Sigma}^{-2} = Z^2 (\hat{U} - UO^*) \hat{\Sigma}^{-2} + Z^2 (UO^*) \hat{\Sigma}^{-2} $$
which in turn implies $||E_5||_{\max} \le ||Z^2(\hat{U} - UO^*)\hat{\Sigma}^{-2}||_{\max} + ||Z^2(UO^*)\hat{\Sigma}^{-2}||_{\max}$. We will now bound these terms individually, below. To begin with,

$$
\begin{align*}
\|Z^2(\hat{U} - UO^*)\hat{\Sigma}^{-2}\|_{\max} &\le \|Z^2(\hat{U} - UO^*)\hat{\Sigma}^{-2}\|_2 \\
&\le \Delta^2 \|\hat{U} - UO^*\|_2 \|\hat{\Sigma}^{-2}\|_2 \quad (\text{sub-multiplicativity of } \|\cdot\|_2) \\
&\le \frac{3\Delta^3}{\sigma} \|\hat{\Sigma}^{-2}\|_2 \quad (\text{from Lemma 15}) \\
&\le \frac{27\Delta^3}{4\sigma^3} \quad (\text{using } \hat{\sigma}_i \ge 2\sigma/3).
\end{align*}
$$

Additionally, denoting $O^* = [o_1^* \ o_2^*]$, we can write

$$
Z^2(UO^*)\hat{\Sigma}^{-2} = \underbrace{[Z^2 u_1 \ Z^2 u_2]}_{\tilde{A}} [\hat{\sigma}_1^{-2} o_1^* \ \hat{\sigma}_2^{-2} o_2^*] = [\hat{\sigma}_1^{-2} \tilde{A} o_1^* \ \hat{\sigma}_2^{-2} \tilde{A} o_2^*]
$$

which in turn implies

$$
\begin{align*}
\|Z^2(UO^*)\hat{\Sigma}^{-2}\|_{\max} &\le \max \left\{ \frac{\|\tilde{A}o_1^*\|_{\infty}}{\hat{\sigma}_1^2}, \frac{\|\tilde{A}o_2^*\|_{\infty}}{\hat{\sigma}_2^2} \right\} \\
&\le \frac{9}{4\sigma^2} \max \left\{ \|\tilde{A}o_1^*\|_{\infty}, \|\tilde{A}o_2^*\|_{\infty} \right\} \quad (\text{using } \hat{\sigma}_i \ge 2\sigma/3) \\
&\le \frac{9}{4\sigma^2} (\|Z^2u_1\|_{\infty} + \|Z^2u_2\|_{\infty}).
\end{align*}
$$

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

D.3 Proof of Lemma 17

Proof

1. For a fixed $i$, consider $\sum_{j=1}^n Z_{ij}u_{1j}$ which is a sum of independent random variables. From the definition of $Z_{ij}$, we can see that $|Z_{ij}u_{1j}| \le \frac{2M}{\sqrt{n}}$ for each $j$. Moreover, $\mathbb{E}[(Z_{ij}u_{1j})^2] = \frac{1}{n}\mathbb{E}[Z_{ij}^2] \le \frac{10pM^2}{3n}$ where the last inequality was shown in the proof of Lemma 12 (see (C.1)). Hence $\sum_{i=1}^n \mathbb{E}[(Z_{ij}u_{1j})^2] \le \frac{10pM^2}{3}$ and it follows from Bernstein's inequality (see Theorem B.2) and the union bound that

$$
\mathbb{P}(\|Z u_1\|_{\infty} \ge t) \le 2n \exp \left( - \frac{3t^2}{20pM^2 + \frac{4tM}{\sqrt{n}}} \right). \quad (\text{D.8})
$$

We want to choose $t$ such that

$$
3t^2 \ge 2 \log n \left( 20pM^2 + \frac{4tM}{\sqrt{n}} \right) \Leftrightarrow 3t^2 - 40pM^2 \log n - \frac{8tM \log n}{\sqrt{n}} \ge 0. \quad (\text{D.9})
$$

Since $t \ge 0$, the above inequality is achieved iff

$$
t \ge \frac{\frac{8M \log n}{\sqrt{n}} + \sqrt{\frac{64M^2 \log^2 n}{n} + 480pM^2 \log n}}{6}. \quad (\text{D.10})
$$
which in turn implies $||E_5||_{\max} \le ||Z^2(\hat{U} - UO^*)\hat{\Sigma}^{-2}||_{\max} + ||Z^2(UO^*)\hat{\Sigma}^{-2}||_{\max}$. We will now bound these terms individually, below. To begin with,

$$ \begin{aligned} ||Z^2(\hat{U} - UO^*)\hat{\Sigma}^{-2}||_{\max} & \le ||Z^2(\hat{U} - UO^*)\hat{\Sigma}^{-2}||_2 \\ & \le \Delta^2 ||\hat{U} - UO^*||_2 ||\hat{\Sigma}^{-2}||_2 \quad (\text{sub-multiplicativity of } ||\cdot||_2) \\ & \le \frac{3\Delta^3}{\sigma} ||\hat{\Sigma}^{-2}||_2 \quad (\text{from Lemma 15}) \\ & \le \frac{27\Delta^3}{4\sigma^3} \quad (\text{using } \hat{\sigma}_i \ge 2\sigma/3). \end{aligned} $$

Additionally, denoting $O^* = [o_1^* o_2^*]$, we can write

$$ Z^2(UO^*)\hat{\Sigma}^{-2} = \underbrace{[Z^2 u_1 \quad Z^2 u_2]}_{\tilde{A}} [\hat{\sigma}_1^{-2} o_1^* \quad \hat{\sigma}_2^{-2} o_2^*] = [\hat{\sigma}_1^{-2} \tilde{A} o_1^* \quad \hat{\sigma}_2^{-2} \tilde{A} o_2^*] $$

which in turn implies

$$ \begin{aligned} ||Z^2(UO^*)\hat{\Sigma}^{-2}||_{\max} & \le \max \left\{ \frac{\|\tilde{A}o_1^*\|_{\infty}}{\hat{\sigma}_1^2}, \frac{\|\tilde{A}o_2^*\|_{\infty}}{\hat{\sigma}_2^2} \right\} \\ & \le \frac{9}{4\sigma^2} \max \left\{ \|\tilde{A}o_1^*\|_{\infty}, \|\tilde{A}o_2^*\|_{\infty} \right\} \quad (\text{using } \hat{\sigma}_i \ge 2\sigma/3) \\ & \le \frac{9}{4\sigma^2} (\|Z^2u_1\|_{\infty} + \|Z^2u_2\|_{\infty}). \end{aligned} $$

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

## D.3 Proof of Lemma 17

### Proof

1. For a fixed $i$, consider $\sum_{j=1}^n Z_{ij}u_{1j}$ which is a sum of independent random variables. From the definition of $Z_{ij}$, we can see that $|Z_{ij}u_{1j}| \le \frac{2M}{\sqrt{n}}$ for each $j$. Moreover, $\mathbb{E}[(Z_{ij}u_{1j})^2] = \frac{1}{n}\mathbb{E}[Z_{ij}^2] \le \frac{10pM^2}{3n}$ where the last inequality was shown in the proof of Lemma 12 (see (C.1)). Hence $\sum_{i=1}^n \mathbb{E}[(Z_{ij}u_{1j})^2] \le \frac{10pM^2}{3}$ and it follows from Bernstein's inequality (see Theorem B.2) and the union bound that

$$ \mathbb{P}(\|Zu_1\|_{\infty} \ge t) \le 2n \exp \left( - \frac{3t^2}{20pM^2 + \frac{4tM}{\sqrt{n}}} \right). \quad (\text{D.8}) $$

We want to choose $t$ such that

$$ 3t^2 \ge 2 \log n \left( 20pM^2 + \frac{4tM}{\sqrt{n}} \right) \Leftrightarrow 3t^2 - 40pM^2 \log n - \frac{8tM \log n}{\sqrt{n}} \ge 0. \quad (\text{D.9}) $$

Since $t \ge 0$, the above inequality is achieved iff

$$ t \ge \frac{\frac{8M \log n}{\sqrt{n}} + \sqrt{\frac{64M^2 \log^2 n}{n} + 480pM^2 \log n}}{6}. \quad (\text{D.10}) $$
Hence if

$$ \frac{64M^2 \log^2 n}{n} \le 480pM^2 \log n \Leftrightarrow p \ge \frac{2 \log n}{15n} $$

holds, then the RHS of (D.10) is upper bounded by

$$ \frac{\frac{8M \log n}{\sqrt{n}} + \sqrt{960pM^2 \log n}}{6} \le \frac{\frac{8M \log n}{\sqrt{2} \log n} \sqrt{15p} + 8M \sqrt{15p} \log n}{6} = \frac{2\sqrt{2} + 4}{3} M \sqrt{15p} \log n. $$

Therefore if $t \ge \frac{2\sqrt{2}+4}{3} M \sqrt{15p} \log n$ is satisfied, then it implies that (D.9) holds. Hence plugging $t = \frac{2\sqrt{2}+4}{3} M \sqrt{15p} \log n$ in (D.8) leads to the statement of the Lemma.

2. For a fixed $i$, consider now $\sum_{j=1}^n Z_{ij}u_{2j}$ which is also a sum of independent random variables. One can verify that $|Z_{ij}u_{2j}| \le 2M\sqrt{B}$ for each $j$, with $B$ as defined in the Lemma. Moreover, $\mathbb{E}[(Z_{ij}u_{2j})^2] \le B\mathbb{E}[Z_{ij}^2] \le \frac{10pM^2B}{3}$ (see (C.1)) and hence, $\sum_{i=1}^n \mathbb{E}[(Z_{ij}u_{2j})^2] \le \frac{10pM^2Bn}{3}$ and it follows from Bernstein's inequality (see Theorem B.2) and the union bound that

$$ \mathbb{P}(\|Zu_2\|_{\infty} \ge t) \le 2n \exp \left( - \frac{3t^2}{20pM^2Bn + 4t\sqrt{BM}} \right). \quad (D.11) $$

Proceeding identically as before, the reader is invited to verify that if $p \ge \frac{2\log n}{15n}$, then the stated bound on $\|Zu_2\|_{\infty}$ is obtained by plugging $t = \frac{2\sqrt{2}+4}{3} M \sqrt{15p} \log n$ in (D.11).

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

## D.4 Proof of Lemma 18

### Proof

1. For a given $l \in [n]$, we can write

$$ \begin{aligned} |(Z^2 u_1)_l| &= \|u_1\|_{\infty} \left| (Z^2 \underbrace{\frac{u_1}{\|u_1\|_{\infty}}}_{\tilde{u}_1})_l \right| \\ &= \frac{1}{\sqrt{n}} |(Z^2 \tilde{u}_1)_l| \quad (\text{with } \|\tilde{u}_1\|_{\infty} = 1) \\ &= \frac{\phi^2}{\sqrt{n}} |((Z/\phi)^2 \tilde{u}_1)_l| \end{aligned} \quad (D.12) $$
Hence if

$$ \frac{64M^2 \log^2 n}{n} \le 480pM^2 \log n \Leftrightarrow p \ge \frac{2 \log n}{15n} $$

holds, then the RHS of (D.10) is upper bounded by

$$ \frac{\frac{8M \log n}{\sqrt{n}} + \sqrt{960pM^2 \log n}}{6} \le \frac{\frac{8M \log n}{\sqrt{2} \log n} \sqrt{15p} + 8M \sqrt{15p} \log n}{6} = \frac{2\sqrt{2} + 4}{3} M \sqrt{15p} \log n. $$

Therefore if $t \ge \frac{2\sqrt{2}+4}{3} M \sqrt{15p} \log n$ is satisfied, then it implies that (D.9) holds. Hence plugging $t = \frac{2\sqrt{2}+4}{3} M \sqrt{15p} \log n$ in (D.8) leads to the statement of the Lemma.

2. For a fixed $i$, consider now $\sum_{j=1}^n Z_{ij}u_{2j}$ which is also a sum of independent random variables. One can verify that $|Z_{ij}u_{2j}| \le 2M\sqrt{B}$ for each $j$, with $B$ as defined in the Lemma. Moreover, $\mathbb{E}[(Z_{ij}u_{2j})^2] \le B\mathbb{E}[Z_{ij}^2] \le \frac{10pM^2B}{3}$ (see (C.1)) and hence, $\sum_{i=1}^n \mathbb{E}[(Z_{ij}u_{2j})^2] \le \frac{10pM^2Bn}{3}$ and it follows from Bernstein's inequality (see Theorem B.2) and the union bound that

$$ \mathbb{P}(\|Zu_2\|_{\infty} \ge t) \le 2n \exp \left( - \frac{3t^2}{20pM^2Bn + 4t\sqrt{BM}} \right). \quad (D.11) $$

Proceeding identically as before, the reader is invited to verify that if $p \ge \frac{2\log n}{15n}$, then the stated bound on $\|Zu_2\|_{\infty}$ is obtained by plugging $t = \frac{2\sqrt{2}+4}{3} M \sqrt{15p} \log n$ in (D.11).

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

## D.4 Proof of Lemma 18

### Proof

1. For a given $l \in [n]$, we can write

$$ \begin{aligned} |(Z^2 u_1)_l| &= \|u_1\|_{\infty} \left| (Z^2 \underbrace{\frac{u_1}{\|u_1\|_{\infty}}}_{\tilde{u}_1})_l \right| \\ &= \frac{1}{\sqrt{n}} |(Z^2 \tilde{u}_1)_l| \quad (\text{with } \|\tilde{u}_1\|_{\infty} = 1) \\ &= \frac{\phi^2}{\sqrt{n}} |((Z/\phi)^2 \tilde{u}_1)_l| \end{aligned} \quad (D.12) $$
for any $\phi > 0$. For any integer $m \ge 2$, and $1 \le i, j \le n$, we have that

$$ 
\begin{aligned}
\mathbb{E}\left[\left(\frac{|Z_{ij}|}{\phi}\right)^m\right] &= \frac{1}{\phi^m} [\eta p |r_i - r_j|^m (1 - \eta p)^m + (1 - \eta)p \mathbb{E}[|N_{ij} - \eta p(r_i - r_j)|^m] + (1 - p) |\eta p(r_i - r_j)|^m] \\
&\le \frac{1}{\phi^m} [\eta p M^m + p(2M)^m + (\eta p)^m M^m] \\
&\le \frac{1}{\phi^m} [2^{m+1} p M^m].
\end{aligned}
$$

Setting $\phi = 2^{3/2} \sqrt{pn} M$ leads to

$$ \mathbb{E}\left[\left(\frac{|Z_{ij}|}{\phi}\right)^m\right] \le \frac{2^{m+1}pM^m}{(2)^{3m/2}p^{m/2}M^m n^{m/2}} = \frac{1}{2^{\frac{m}{2}-1}} \frac{1}{p^{\frac{m}{2}-1}} \frac{1}{n^{\frac{m}{2}}}. $$

It is easy to check that $p \ge \frac{1}{2n}$ implies $\mathbb{E}\left[\left(\frac{|Z_{ij}|}{\phi}\right)^m\right] \le 1/n$. Therefore invoking Theorem 25 for $k=2$, we obtain for the stated choices of $\xi, \mu, \kappa$ that $|((Z/\phi)^2 \tilde{u}_1)_t| \le (\log n)^{2\xi}$ holds with probability at least $1 - n^{-\frac{1}{4}(\log_\mu n)^{\xi-1}(\log_\mu e)^{-\xi}}$. Plugging this in (D.12) with the expression for $\phi$, and using the union bound, we obtain the statement of the Lemma.

2. The steps are identical to those above, with the only difference being $\|u_2\|_{\infty} = \frac{M-\alpha}{\|r-\alpha e\|_2}$. ■

# Appendix E. Proofs of Lemmas from Section 5.5

## E.1 Proof of Lemma 19

Note that $\bar{D}_{ii} = \sum_{j=1}^n |H_{ij}|$ is the sum of independent random variables, where $|H_{ij}| \le M$ $\forall i, j$. Moreover,

$$ \sum_{j=1}^{n} \mathbb{E}[|H_{ij}|^2] = \eta p \sum_{j=1}^{n} (r_i - r_j)^2 + (1 - \eta) \frac{npM}{2} \le \eta pnM^2 + (1 - \eta)np \frac{M}{2} = npA(\eta, M). $$

Invoking Bernstein's inequality, it follows for any given $i$ and $t \ge 0$ that

$$ \mathbb{P}(|\bar{D}_{ii} - \mathbb{E}[\bar{D}_{ii}]| \ge t) \le 2 \exp \left( - \frac{t^2}{2(npA(\eta, M) + \frac{Mt}{3})} \right). $$

In order to get a high probability bound, we require $t^2 \ge 4 \log n (npA(\eta, M) + \frac{Mt}{3})$. Since $t \ge 0$, this is equivalent to saying that

$$ t \ge \frac{\frac{4M}{3} \log n + \sqrt{\left(\frac{4M}{3} \log n\right)^2 + 16pn \log n A(\eta, M)}}{2}. \quad (E.1) $$
for any $\phi > 0$. For any integer $m \ge 2$, and $1 \le i, j \le n$, we have that

$$ 
\begin{aligned}
\mathbb{E}\left[\left(\frac{|Z_{ij}|}{\phi}\right)^m\right] &= \frac{1}{\phi^m} [\eta p |r_i - r_j|^m (1 - \eta p)^m + (1 - \eta)p \mathbb{E}[|N_{ij} - \eta p(r_i - r_j)|^m] + (1 - p) |\eta p(r_i - r_j)|^m] \\
&\le \frac{1}{\phi^m} [\eta p M^m + p(2M)^m + (\eta p)^m M^m] \\
&\le \frac{1}{\phi^m} [2^{m+1} p M^m].
\end{aligned}
$$

Setting $\phi = 2^{3/2} \sqrt{pn} M$ leads to

$$ \mathbb{E}\left[\left(\frac{|Z_{ij}|}{\phi}\right)^m\right] \le \frac{2^{m+1}pM^m}{(2)^{3m/2}p^{m/2}M^m n^{m/2}} = \frac{1}{2^{\frac{m}{2}-1}} \frac{1}{p^{\frac{m}{2}-1}} \frac{1}{n^{\frac{m}{2}}}. $$

It is easy to check that $p \ge \frac{1}{2n}$ implies $\mathbb{E}\left[\left(\frac{|Z_{ij}|}{\phi}\right)^m\right] \le 1/n$. Therefore invoking Theorem 25 for $k = 2$, we obtain for the stated choices of $\xi, \mu, \kappa$ that $|((Z/\phi)^2 \tilde{u}_1)_t| \le (\log n)^{2\xi}$ holds with probability at least $1 - n^{-\frac{1}{4}(\log \mu n)^{\xi-1}(\log \kappa e)^{-\xi}}$. Plugging this in (D.12) with the expression for $\phi$, and using the union bound, we obtain the statement of the Lemma.

2. The steps are identical to those above, with the only difference being $\|u_2\|_{\infty} = \frac{M-\alpha}{\|r-\alpha e\|_2}$. ■

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

# Appendix E. Proofs of Lemmas from Section 5.5

## E.1 Proof of Lemma 19

Note that $\bar{D}_{ii} = \sum_{j=1}^n |H_{ij}|$ is the sum of independent random variables, where $|H_{ij}| \le M$ $\forall i, j$. Moreover,

$$ \sum_{j=1}^{n} \mathbb{E}[|H_{ij}|^2] = \eta p \sum_{j=1}^{n} (r_i - r_j)^2 + (1 - \eta) \frac{npM}{2} \le \eta pnM^2 + (1 - \eta)np \frac{M}{2} = npA(\eta, M). $$

Invoking Bernstein's inequality, it follows for any given $i$ and $t \ge 0$ that

$$ \mathbb{P}(|\bar{D}_{ii} - \mathbb{E}[\bar{D}_{ii}]| \ge t) \le 2 \exp \left( - \frac{t^2}{2(npA(\eta, M) + \frac{Mt}{3})} \right). $$

In order to get a high probability bound, we require $t^2 \ge 4 \log n (npA(\eta, M) + \frac{Mt}{3})$. Since $t \ge 0$, this is equivalent to saying that

$$ t \ge \frac{\frac{4M}{3} \log n + \sqrt{\left(\frac{4M}{3} \log n\right)^2 + 16pn \log n A(\eta, M)}}{2}. \quad (E.1) $$
If $(\frac{4M}{3} \log n)^2 \le 6pn \log nA(\eta, M)$ or equivalently $p \ge \frac{M^2}{9A(\eta, M)} \frac{\log n}{n}$, then the RHS of (E.1) is bounded by

$$ \sqrt{16pn \log nA(\eta, M)} \frac{\sqrt{2} + 1}{2} = 2(\sqrt{2} + 1) \sqrt{pn \log n} \sqrt{A(\eta, M)}. $$

Hence taking $t = 2(\sqrt{2} + 1)\sqrt{pn \log n} \sqrt{A(\eta, M)}$ and applying the union bound, we obtain the statement of the Lemma.
If $(\frac{4M}{3} \log n)^2 \le 6pn \log nA(\eta, M)$ or equivalently $p \ge \frac{M^2}{9A(\eta, M)} \frac{\log n}{n}$, then the RHS of (E.1) is bounded by

$$ \sqrt{16pn \log nA(\eta, M)} \frac{\sqrt{2} + 1}{2} = 2(\sqrt{2} + 1) \sqrt{pn \log n} \sqrt{A(\eta, M)}. $$

Hence taking $t = 2(\sqrt{2} + 1)\sqrt{pn \log n} \sqrt{A(\eta, M)}$ and applying the union bound, we obtain the statement of the Lemma.