Proof. This proof is an example of an \(\varepsilon \)-net argument. We need to control \(\langle Ax, y \rangle \) for all vectors \(x\) and \(y\) on the unit sphere. To this end, we will discretize the sphere using a net (approximation step), establish a tight control of \(\langle Ax, y \rangle \) for fixed vectors \(x\) and \(y\) from the net (concentration step), and finish by taking a union bound over all \(x\) and \(y\) in the net.
Step 1: Approximation. Choose \(\varepsilon = 1/4\). We can find an \(\varepsilon \)-net \(N\) of the sphere \(S^{n-1}\) and an \(\varepsilon \)-net \(M\) of the sphere \(S^{m-1}\) with cardinalities \[ |N| \leq 9^n \quad \text {and} \quad |M| \leq 9^m. \] The operator norm of \(A\) can be bounded using these nets as follows: \[ \|A\| \leq 2 \max _{x \in N, \, y \in M} \langle Ax, y \rangle . \] Step 2: Concentration. Fix \(x \in N\) and \(y \in M\). Then the quadratic form \[ \langle Ax, y \rangle = \sum _{i=1}^n \sum _{j=1}^m A_{ij} x_i y_j \] is a sum of independent, sub-Gaussian random variables. The sum is sub-Gaussian, and \begin{align*} \|\langle Ax, y \rangle \|_{\psi _2}^2 &\leq C \sum _{i=1}^n \sum _{j=1}^m \|A_{ij} x_i y_j\|_{\psi _2}^2 \leq C K^2 \sum _{i=1}^n \sum _{j=1}^m x_i^2 y_j^2 \\ &= C K^2 \!\left ( \sum _{i=1}^n x_i^2 \right ) \!\left ( \sum _{j=1}^m y_j^2 \right ) = C K^2. \end{align*}

We can restate this as the tail bound \[ \mathbb {P}\{\langle Ax, y \rangle \geq u\} \leq 2 \exp (-c u^2 / K^2), \qquad u \geq 0. \] Step 3: Union bound. Next, we unfix \(x\) and \(y\) using a union bound. Suppose the event \(\max _{x \in N, y \in M} \langle Ax, y \rangle \geq u\) occurs. Then there exist \(x \in N\) and \(y \in M\) such that \(\langle Ax, y \rangle \geq u\). Thus the union bound yields \[ \mathbb {P}\!\left \{ \max _{x \in N, \, y \in M} \langle Ax, y \rangle \geq u \right \} \leq \sum _{x \in N, \, y \in M} \mathbb {P}\{\langle Ax, y \rangle \geq u\}. \] Using the tail bound and the size estimates on \(N\) and \(M\), we bound the probability above by \[ 9^{n + m} \cdot 2 \exp (-c u^2 / K^2). \] Choose \[ u = C K (\sqrt {n} + \sqrt {m} + t). \] Then \(u^2 \geq C^2 K^2 (n + m + t^2)\), and if the constant \(C\) is chosen sufficiently large, the exponent is large enough, say \(c u^2 / K^2 \geq 3(n + m) + t^2\). Thus \[ \mathbb {P}\!\left \{ \max _{x \in N, \, y \in M} \langle Ax, y \rangle \geq u \right \} \leq 9^{n+m} \cdot 2 \exp (-3(n+m) - t^2) \leq 2 \exp (-t^2). \] Finally, combining this with the bound from Step 1, we conclude that \[ \mathbb {P}\{\|A\| \geq 2u\} \leq 2 \exp (-t^2). \] Recalling our choice of \(u\), we complete the proof. □

Proof. We will prove the stronger conclusion using an \(\varepsilon \)-net argument. This will be similar to the proof for sub-Gaussian matrices, but we now use Bernstein’s concentration inequality instead of Hoeffding’s.
Step 1: Approximation. We can find a \(\tfrac {1}{4}\)-net \(N\) of the unit sphere \(S^{n-1}\) with cardinality \(|N| \leq 9^n\). The operator norm can be evaluated on \(N\): \[ \left \| \frac {1}{m} A^\top A - I_n \right \| \leq 2 \max _{x \in N} \left | \left \langle \!\left ( \frac {1}{m} A^\top A - I_n \right ) x, x \right \rangle \right | = 2 \max _{x \in N} \left | \frac {1}{m} \|Ax\|_2^2 - 1 \right |. \] To complete the proof it suffices to show that, with the required probability, \[ \max _{x \in N} \left | \frac {1}{m} \|Ax\|_2^2 - 1 \right | \leq \frac {\varepsilon }{2} \quad \text {where} \quad \varepsilon := K^2 \max (\delta , \delta ^2). \] Step 2: Concentration. Fix \(x \in S^{n-1}\) and express \(\|Ax\|_2^2\) as a sum of independent random variables: \[ \|Ax\|_2^2 = \sum _{i=1}^m \langle A_i, x \rangle ^2 =: \sum _{i=1}^m X_i^2, \] where \(A_i\) denote the rows of \(A\). By assumption, \(A_i\) are independent, isotropic, and sub-Gaussian random vectors with \(\|A_i\|_{\psi _2} \leq K\). Thus \(X_i = \langle A_i, x \rangle \) are independent sub-Gaussian random variables with \(\mathbb {E} X_i^2 = 1\) and \(\|X_i\|_{\psi _2} \leq K\). Therefore \(X_i^2 - 1\) are independent, mean-zero, sub-exponential random variables with \[ \|X_i^2 - 1\|_{\psi _1} \leq C K^2. \] Thus we can use Bernstein’s inequality and obtain \begin{align*} \mathbb {P}\!\left \{ \left | \frac {1}{m} \|Ax\|_2^2 - 1 \right | \geq \frac {\varepsilon }{2} \right \} &= \mathbb {P}\!\left \{ \left | \frac {1}{m} \sum _{i=1}^m X_i^2 - 1 \right | \geq \frac {\varepsilon }{2} \right \} \\ &\leq 2 \exp \!\left [ -c_1 \min \!\left ( \frac {\varepsilon ^2}{K^4}, \frac {\varepsilon }{K^2} \right ) m \right ] \\ &= 2 \exp \!\left [ -c_1 \delta ^2 m \right ] && \text {(since $\varepsilon / K^2 = \max (\delta , \delta ^2)$)} \\ &\leq 2 \exp \!\left [ -c_1 C^2 (n + t^2) \right ]. \end{align*}

The last bound follows from the definition of \(\delta \) and the inequality \((a + b)^2 \geq a^2 + b^2\) for \(a, b \geq 0\).
Step 3: Union bound. Now we can unfix \(x \in N\) using a union bound. Recalling that \(N\) has cardinality bounded by \(9^n\), we obtain \[ \mathbb {P}\!\left \{ \max _{x \in N} \left | \frac {1}{m} \|Ax\|_2^2 - 1 \right | \geq \frac {\varepsilon }{2} \right \} \leq 9^n \cdot 2 \exp \!\left [ -c_1 C^2 (n + t^2) \right ] \leq 2 \exp (-t^2) \] if we chose the absolute constant \(C\) large enough. As we noted in Step 1, this completes the proof. □

Proof. We directly apply Lieb’s theorem: \(f(A) = \mathrm {tr}(\exp (H + \log A))\) is a convex function on the space of matrices of the same size as \(A\). By Jensen’s inequality: \[ \mathbb {E}\left [\mathrm {tr}\left (\exp \left (\sum _{i=1}^n \theta X_i\right )\right )\right ] \leq \mathrm {tr}\left (\exp \left (\sum _{i=1}^n \log \mathbb {E} e^{\theta X_i}\right )\right ) \] Using a Markov-like relaxation technique, we obtain the following concentration inequality for the largest eigenvalue: \begin{equation} P(\lambda _{\max }(Y) \geq t) \leq \inf _{\theta \geq 0} \mathrm {tr}\left (\exp \left (\sum _{i=1}^n \log \mathbb {E} e^{\theta X_i}\right )\right ) e^{-\theta t} \end{equation} We next estimate the log moment generating function \(\mathbb {E} e^{\theta X_i}\). From the condition \(\|X_i\|_{op} \leq b\), we have: \[ e^{\theta X} = 1 + \theta X + X^T f(X) X \preceq 1 + \theta X + f(b) X^2 \] where: \[ f(b) = \frac {e^{\theta b} - 1 - b}{b^2} = \sum _{k=2}^{\infty } \frac {(\theta b)^{k-2}}{3^{k-2}} \cdot \frac {\theta ^2}{2} \leq \frac {\frac {\theta ^2}{2}}{1 - \frac {\theta b}{3}} \] Therefore: \begin{equation} \log \mathbb {E} e^{\theta X} \leq \frac {\frac {\theta ^2}{2}}{1 - \frac {\theta b}{3}} \mathbb {E} X^2 \end{equation} Finally, combining (12), (13) and the conditions: \[ P(\lambda _{\max }(Y) \geq t) \leq \inf _{\theta \geq 0} \mathrm {tr}\left (\exp \left (\frac {\frac {\theta ^2}{2}}{1 - \frac {\theta b}{3}} \sum _{i=1}^n \mathbb {E} X_i^2\right )\right ) e^{-\theta t} \] \[ \leq \inf _{0 \leq \theta < \frac {3}{b}} d \exp \left (\frac {\frac {\theta ^2}{2}}{1 - \frac {\theta b}{3}} \sigma ^2\right ) e^{-\theta t} \] \[ \leq d \exp \left (\frac {-t^2/2}{\sigma ^2 + bt/3}\right ) \quad \left (\text {choosing } \theta = \frac {t}{\sigma ^2 + \frac {bt}{3}}\right ) \] Therefore: \[ P\left (\left \|\sum _i X_i\right \|_{op} \geq t\right ) \leq 2d \exp \left (\frac {-t^2/2}{\sigma ^2 + bt/3}\right ) \] □

Proof. Since \(\hat {A}\) is the optimal solution of the semidefinite program, plugging it into (8) we have: \begin{equation} \left \langle A - \frac {p+q}{2}, \hat {A} \right \rangle \geq \left \langle A - \frac {p+q}{2}, A^* \right \rangle \end{equation} \begin{equation} \implies 0 \geq \left \langle A - \frac {p+q}{2}, A^* - \hat {A} \right \rangle \geq \langle A - \mathbb {E}A, A^* - \hat {A} \rangle + \left \langle \mathbb {E}A - \frac {p+q}{2}, A^* - \hat {A} \right \rangle \end{equation} We estimate the two terms separately: \begin{equation} \left \langle \mathbb {E}A - \frac {p+q}{2}, A^* - \hat {A} \right \rangle \leq \frac {p-q}{2} \sum _{i,j} |A^*_{i,j} - \hat {A}_{i,j}| = \frac {p-q}{2} \|A^* - \hat {A}\|_1 \end{equation} Combining (14), (15) and applying Grothendieck’s Inequality: \begin{equation} \frac {p-q}{2} \|A^* - \hat {A}\|_1 \leq \langle A - \mathbb {E}A, \hat {A} - A^* \rangle \end{equation} \begin{equation} \langle A - \mathbb {E}A, \hat {A} - A^* \rangle \leq |\langle A - \mathbb {E}A, \hat {A} \rangle | + |\langle A - \mathbb {E}A, A^* \rangle | \end{equation} \begin{equation} |\langle A - \mathbb {E}A, \hat {A} \rangle | + |\langle A - \mathbb {E}A, A^* \rangle | \leq 2 \max _{Y_{ii}=1,\, Y \succeq 0} |\langle A - \mathbb {E}A, Y \rangle | \end{equation} \begin{equation} 2 \max _{Y_{ii}=1,\, Y \succeq 0} |\langle A - \mathbb {E}A, Y \rangle | \leq 2K \max _{x, y \in \{\pm 1\}^n} \left | \sum _{i,j} (A_{ij} - \mathbb {E}A_{ij}) x_i y_j \right | \end{equation} Looking at (19), this is a sum of \(n^2\) independent random variables. We treat it as \(n^2\) matrices of size \(1 \times 1\) and apply Lemma 1. Let \(Z_{ij} = (A_{ij} - \mathbb {E}A_{ij}) x_i y_j\), \(Z = \sum _{i,j} Z_{ij}\), \(\|Z_{ij}\|_{op} = |Z_{ij}| \leq 1\), \(\mathrm {var}(Z_{ij}) \leq p(1-p) \leq p\): \begin{equation*} P(|Z| \geq t) \leq 2 \exp \left (-\frac {t^2}{pn^2 + t/3}\right ) \leq 2 \exp \left (-\frac {ct^2}{pn^2 + t}\right ) \end{equation*} Taking a union bound over all \(i, j\), we obtain: \begin{equation*} P\left ( \max _{(x,y) \in \{\pm 1\}^n \times \{\pm 1\}^n} \left | \sum _{i,j} (A_{ij} - \mathbb {E}A_{ij}) x_i y_j \right | \geq t \right ) \leq 2 \exp \left (-\frac {ct^2}{pn^2 + t}\right ) 4^n \end{equation*} We choose \(t\) sufficiently large: \(t = c(\sqrt {pn^3} + n)\), so that the right-hand side is \(\geq (2e)^{-n}\) for a sufficiently large constant \(c\). Therefore, with probability \(\geq 1 - (2e)^{-n}\): \begin{equation*} \max _{(x,y) \in \{\pm 1\}^n \times \{\pm 1\}^n} \left | \sum _{i,j} (A_{ij} - \mathbb {E}A_{ij}) x_i y_j \right | \lesssim \sqrt {pn^3} + n \lesssim \sqrt {pn^3} \end{equation*} Combining (16), (20) and applying the lemma: \begin{equation*} \frac {p-q}{2} \|A^* - \hat {A}\|_1 \lesssim \sqrt {pn^3} \end{equation*} That is: \begin{equation*} \frac {1}{n^2} \|A^* - \hat {A}\|_1 \lesssim \sqrt {\frac {p}{(p-q)^2 n}} \end{equation*} □