# Optimal and algorithmic norm regularization of random matrices

Vishesh Jain  Simons Institute for the Theory of Computing, Berkeley, CA
94720, USA<EMAIL_ADDRESS>,  Ashwin Sah  and  Mehtaab Sawhney
Department of Mathematics, Massachusetts Institute of Technology, Cambridge,
MA 02139, USA<EMAIL_ADDRESS>
###### Abstract.

Let $A$ be an $n\times n$ random matrix whose entries are i.i.d. with mean $0$
and variance $1$. We present a deterministic polynomial time algorithm which,
with probability at least $1-2\exp(-\Omega(\epsilon n))$ in the choice of $A$,
finds an $\epsilon n\times\epsilon n$ sub-matrix such that zeroing it out
results in $\widetilde{A}$ with

$\lVert\widetilde{A}\rVert=O(\sqrt{n/\epsilon}).$

Our result is optimal up to a constant factor and improves previous results of
Rebrova and Vershynin, and Rebrova. We also prove an analogous result for $A$
a symmetric $n\times n$ random matrix whose upper-diagonal entries are i.i.d.
with mean $0$ and variance $1$.

##  1\. Introduction

Recall that the operator norm of an $n\times n$ real-valued matrix $A$ is
defined as

$\lVert A\rVert:=\sup_{x\in\mathbb{S}^{n-1}}\lVert Ax\rVert_{2},$

where $\lVert\cdot\rVert_{2}$ denotes the Euclidean norm and
$\mathbb{S}^{n-1}$ denotes the unit sphere in $\mathbb{R}^{n}$. The operator
norm is a fundamental quantity of interest in the non-asymptotic theory of
random matrices (see, e.g., [8] and the references therein). A classical
result of Bai, Krishnaiah, and Yin [12] shows that if the entries of an
$n\times n$ random matrix $A$ are i.i.d. random variables with $0$ mean, unit
variance, and bounded fourth moment, then

$\lVert A\rVert=(2+o(1))\sqrt{n}.$

The finite fourth moment hypothesis is sharp in the sense that for a sequence
of $n\times n$ random matrices $A_{n}$ with entries that are i.i.d. random
variables with mean $0$, unit variance, and infinite fourth moment, Bai,
Silverstein, and Yin [12] showed that

$\limsup\frac{\lVert A\rVert}{\sqrt{n}}=\infty\text{ almost surely.}$

Motivated by works of Feige and Ofek [2] and Le, Levina, and Vershynin [4] on
the regularization of the norm of adjacency matrices of random graphs, Rebrova
and Vershynin [7] asked whether enforcing the bound $\lVert
A\rVert=O(\sqrt{n})$ is a “local problem” or a “global problem”. Specifically,
they considered an $n\times n$ random matrix $A$ with i.i.d. entries and asked
what assumptions (if any) on the distribution of the entries guarantees that,
with high probability, $\lVert\widetilde{A}\rVert=O(\sqrt{n})$ for some matrix
$\widetilde{A}$ obtained by modifying $A$ on a small sub-matrix. They showed
[7, Theorem 1.3] that this is not possible if the distribution has either non-
zero mean or infinite variance; in other words, in this case, there is a
“global problem”. On the other hand, they showed that if the distribution has
zero mean and bounded variance, then the problem is “local”.

######  Theorem 1.1 ([7, Theorem 1.1]).

Consider an $n\times n$ random matrix $A$ with i.i.d. entries that have zero
mean and unit variance. There exist absolute constants $C_{\ref{thm:iid-norm-
regularization}},c_{\ref{thm:iid-norm-regularization}}>0$ such that for any
$\epsilon\in(0,1/2]$, with probability at least $1-2\exp(-c_{\ref{thm:iid-
norm-regularization}}\epsilon n)$, there exists an $\epsilon n\times\epsilon
n$ sub-matrix of $A$ such that replacing all of its entries with zero gives a
matrix $\widetilde{A}$ with

$\lVert\widetilde{A}\rVert\leq C_{\ref{thm:iid-norm-
regularization}}\frac{\log\epsilon^{-1}}{\sqrt{\epsilon}}\sqrt{n}.$

The work of Rebrova and Vershynin [7] leaves open several natural questions.

###  1.1. Optimal norm regularization

Let $\epsilon\in(0,1/10)$. It is easily seen [7, Remark 1.2] that for the
$n\times n$ random matrix $A$ whose entries are i.i.d. random variables taking
the values $0$ with probability $1-(2\epsilon/n)$ and
$\pm\sqrt{n/(2\epsilon)}$ with probability $\epsilon/n$ each, with probability
at least $1-2\exp(-c^{\prime}\epsilon n)$,

$\lVert\widetilde{A}\rVert\gtrsim\sqrt{\frac{n}{\epsilon}}$

for every matrix $\widetilde{A}$ obtained by modifying $A$ on a $c\epsilon
n\times c\epsilon n$ matrix. Here, $c,c^{\prime}>0$ are absolute constants.
This example shows that the dependence of the bound on
$\lVert\widetilde{A}\rVert$ in Theorem 1.1 is optimal up to a possible factor
of $\log\epsilon^{-1}$. In [7, Section 11], Rebrova and Vershynin asked
whether this factor of $\log\epsilon^{-1}$ is necessary. We show that it is
not, thereby obtaining a result which is optimal up to constants.

######  Theorem 1.2.

Consider an $n\times n$ random matrix $A$ with i.i.d. entries that have zero
mean and unit variance. There exist absolute constants $C_{\ref{thm:optimal-
iid-norm-regularization}},c_{\ref{thm:optimal-iid-norm-regularization}}>0$
such that for any $\epsilon\in(0,1/2]$, with probability at least
$1-2\exp(-c_{\ref{thm:optimal-iid-norm-regularization}}\epsilon n)$, there
exists an $\epsilon n\times\epsilon n$ sub-matrix of $A$ such that replacing
all of its entries with zero gives a matrix $\widetilde{A}$ with

$\lVert\widetilde{A}\rVert\leq C_{\ref{thm:optimal-iid-norm-
regularization}}\sqrt{\frac{n}{\epsilon}}.$

###  1.2. Norm regularization of random symmetric matrices

The regularization results in [2, 4] were proved for adjacency matrices of
random graphs, whereas the main result of [7] holds only for random matrices
with i.i.d. entries. Answering a question in [7, Section 11], our next result
provides a symmetric counterpart of Theorem 1.2.

######  Theorem 1.3.

Consider an $n\times n$ random symmetric matrix $A$ with i.i.d. entries on and
above the diagonal that have zero mean and unit variance. There exist absolute
constants $C_{\ref{thm:sym-norm-regularization}},c_{\ref{thm:sym-norm-
regularization}}>0$ such that for any $\epsilon\in(0,1/2]$, with probability
at least $1-2\exp(-c_{\ref{thm:sym-norm-regularization}}\epsilon n)$, there
exists an $\epsilon n\times\epsilon n$ sub-matrix of $A$ such that replacing
all of its entries with zero gives a matrix $\widetilde{A}$ with

$\lVert\widetilde{A}\rVert\leq C_{\ref{thm:sym-norm-
regularization}}\sqrt{\frac{n}{\epsilon}}.$

######  Remark.

The symmetric version of the example given above shows that the dependence of
the bound on $\lVert\widetilde{A}\rVert$ is optimal in terms of $\epsilon$.
Also, one can allow for the diagonals to be arbitrary independent random
variables with zero mean and unit variance; this is a straightforward
modification of the proof and we leave the details to the interested reader.

###  1.3. Constructive norm regularization

The norm regularization result of Rebrova and Vershynin (Theorem 1.1) is only
an existential result and does not provide a way to efficiently find an
appropriate $\epsilon n\times\epsilon n$ sub-matrix to zero out. In contrast,
the regularization procedures of [2, 4] are algorithmic in nature. In [7,
Section 11], Rebrova and Vershynin asked whether one can obtain an explicit
description of an $\epsilon n\times\epsilon n$ matrix whose removal
regularizes the norm.

This question was the focus of the work of Rebrova [6] who showed [6,
Corollary 1.3] that for an $n\times n$ random matrix $A$ with i.i.d. entries
having a symmetric distribution and unit variance, for any
$\epsilon\in(0,1/2]$, and for any $r\geq 1$, there is a deterministic,
polynomial time algorithm to zero out an $\epsilon n\times\epsilon n$ sub-
matrix in order to obtain $\widetilde{A}$ satisfying

$\lVert\widetilde{A}\rVert\lesssim r^{3/2}\cdot\sqrt{\log\log
n\cdot\log\epsilon^{-1}}\cdot\sqrt{\frac{n}{\epsilon}}$

such that the algorithm succeeds with probability $1-n^{0.1-r}$ (in the choice
of $A$). Compared to the existential regularization results for i.i.d.
matrices discussed earlier, this result requires that the common distribution
of the entries is symmetric (as opposed to only mean $0$), loses an additional
factor of $\sqrt{\log\log n\cdot\log\epsilon^{-1}}$ in the bound on
$\lVert\widetilde{A}\rVert$, and moreover, the failure probability (over the
choice of $A$) of the regularization procedure is much larger than for the
existential results.

Our final result remedies these shortcomings, thereby providing constructive
versions of Theorems 1.2 and 1.3

######  Theorem 1.4.

The $\epsilon n\times\epsilon n$ matrices guaranteed in Theorems 1.2 and 1.3
can be found via a deterministic polynomial time algorithm which is guaranteed
to succeed with probability at least $1-2\exp(-c_{\ref{thm:algorithmic-norm-
regularization}}\epsilon n)$ _(_ in the choice of $A$_)_. Here,
$c_{\ref{thm:algorithmic-norm-regularization}}>0$ is an absolute constant.

###  1.4. Organization

As in [7], we follow the natural high-level strategy of decomposing $A$ into a
number of parts based on the magnitude of the entries as well as controlling
the operator norm of the part with the smallest entries using a version of the
Grothendieck-Pietsch factorization theorem. Section 4 contains our treatment
of “medium entries” and “large entries” while Section 2 and Section 3.1
contains our treatment of “small entries”. Finally, these results are combined
in Section 5 to prove Theorems 1.2, 1.3 and 1.4.

###  1.5. Notation

Given an $n\times n$ matrix $A$ and a subset $J\subseteq[n]$, we let $A_{J}$
denote the matrix obtained from $A$ by zeroing out the columns $J^{c}$. Given
an $n\times n$ matrix $A$ and a subset $S\subseteq[n]\times[n]$, we denote by
$A_{S}$ the matrix obtained from $A$ by zeroing out all entries not in $S$.

For the sake of uniformity in our arguments, we will deduce all statements for
$n\times n$ random matrices with i.i.d. entries above the diagonal and $0$ on
and below the diagonal. For brevity, we will refer to such matrices as i.i.d.
random upper triangular matrices and will typically denote them by $T$.

###  1.6. Acknowledgements

We thank Liza Rebrova for useful discussions.

##  2\. Controlling $2\to\infty$ norm

As in [7], we begin by regularizing $\lVert\cdot\rVert_{2\to\infty}$ for the
“small” part of the matrix.

######  Proposition 2.1.

Let $\epsilon\in(0,1/2)$. Consider an $n\times n$ upper triangular matrix $T$
with i.i.d. entries satisfying $\mathbb{E}T_{ij}^{2}\leq 1$ and
$|T_{ij}|\leq\sqrt{n/\log\epsilon^{-1}}$ almost surely. There exist absolute
constants $C_{\ref{lem:sym-2->infty}},c_{\ref{lem:sym-2->infty}}>0$ such that
with probability at least $1-2\exp(-c_{\ref{lem:sym-2->infty}}\epsilon n)$,
there is a subset $J\subseteq[n]$ with $|J|\leq
C_{\ref{lem:sym-2->infty}}\epsilon n$ for which

$\lVert T_{J^{c}}\rVert_{2\to\infty}\leq C_{\ref{lem:sym-2->infty}}\sqrt{n}.$

Furthermore, this set can be found algorithmically without access to the
underlying distribution.

Compared to [7, Lemma 5.1], the above proposition is valid for i.i.d. upper
triangular matrices (as opposed to only i.i.d. matrices) and does not lose a
factor of $\sqrt{\log\epsilon^{-1}}$ in the bound on
$\lVert\cdot\rVert_{2\to\infty}$, although this comes at the cost of
restricting the bound on $|T_{ij}|$ by a corresponding factor of
$1/\sqrt{\log{\epsilon^{-1}}}$.

The key step in the proof of Proposition 2.1 is the following, which is
closely related to [7, Theorem 4.2].

######  Lemma 2.2.

Let $\epsilon\in(0,1/2)$ and let $\xi\in[0,n/\log\epsilon^{-1}]$ be such that
$\mathbb{E}\xi\leq 1$. Let $X_{1},\ldots,X_{n}$ as well as
$Y_{1},\ldots,Y_{n^{2}/8}$ be independent samples of $\xi$. There exist
absolute constants $C_{\ref{prop:damping-sum}},c_{\ref{prop:damping-sum}}>0$
for which the following holds. For all $n\geq C_{\ref{prop:damping-
sum}}\log\epsilon^{-1}$, there exist random variables
$W_{1},\ldots,W_{n}\in[0,1]$ depending only on
$X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{n^{2}/8}$ (and not the distribution of
$\xi$) such that with probability at least $1-2\exp(-c_{\ref{prop:damping-
sum}}n\log\epsilon^{-1})$ over $Y_{1},\ldots,Y_{n^{2}/8}$, we have

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\sum_{j=1}^{n}W_{j}X_{j}\leq
C_{\ref{prop:damping-sum}}n\quad\text{ almost surely over
}X_{1},\dots,X_{n},\text{ and}$
$1\leq\mathbb{E}_{X_{1},\ldots,X_{n}}\bigg{(}\prod_{i=1}^{n}W_{i}\bigg{)}^{-1}\leq
1+\epsilon.$

###### Proof.

Let $K=1/\log\epsilon^{-1}$ so that $\xi\in[0,Kn]$ and $n=\Omega(1/K)$. Let
$t=\lceil\log_{2}(Kn)\rceil$. Let $q_{-1}=q_{0}=0,q_{t+1}=Kn$, and for
$k\in[t]$, let

$q_{k}=\sup\\{r\geq 0:\mathbb{P}[\xi\geq r]\geq 2^{-k}\\}.$

Let $\widehat{\mathbb{P}}$ denote the empirical measure generated by
$Y_{1},\dots,Y_{n^{2}/8}$. Let $\widehat{q}_{0}=0,\widehat{q}_{t+1}=2Kn$, and
for $k\in[t]$, let

$\widehat{q}_{k}=\sup\\{r\geq
0:\widehat{\mathbb{P}}\left[[r,\infty)\right]\geq 2^{-k}\\}.$

Let $\mathcal{G}$ denote the event, measurable with respect to
$Y_{1},\dots,Y_{n^{2}/8}$, that

$q_{k-1}\leq\widehat{q}_{k}\leq q_{k+1}\quad\forall k\in[t].$

Then, it follows from a staightforward application of the Chernoff bound and
the union bound that

$\mathbb{P}_{Y_{1},\dots,Y_{n^{2}/8}}[\mathcal{G}]\geq
1-\sum_{k=1}^{t}\exp\left(-\Omega\left(\frac{n^{2}}{2^{k}}\right)\right)\geq
1-2\exp(-\Omega(n/K)).$

Now, fix a realisation of $Y_{1},\dots,Y_{n^{2}/8}$ and the associated
quantities $\widehat{q}_{0},\dots,\widehat{q}_{t+1}$. Let $k_{0}=0$ and
inductively define

$k_{i+1}=\max\\{k_{i}+1,\max\\{j\in(k_{i},{t+1}]:\widehat{q}_{j}<2\widehat{q}_{k_{i}}\\}\\}.$

Here, the maximum of the empty set is $-\infty$. Let $\ell$ denote the first
index for which $k_{\ell}=t+1$. Note that for all
$i\in\\{0,1,\dots,\ell-1\\}$,

$2^{-k_{i}}\widehat{q}_{k_{i+1}}\lesssim
2^{-k_{i}}\widehat{q}_{k_{i}}+2^{-k_{i+1}}\widehat{q}_{k_{i+1}}.$

Let $L\geq 1$ be a sufficiently large absolute constant to be specified later.
For a realisation of $X_{1},\dots,X_{n}$ and for $i\in\\{0,1,\dots,\ell-1\\}$,
let

$\nu_{i}=\\#\\{j\in[n]:X_{j}\in[\widehat{q}_{k_{i}},\widehat{q}_{k_{i+1}})\\}\text{
and }w_{i}=\min\left(1,\frac{L2^{-k_{i}}n}{\nu_{i}}\right).$

Also, for $j\in[n]$, we let $i(j)$ denote the unique (by construction) index
$i\in\\{0,1,\dots\ell-1\\}$ for which
$X_{j}\in[\widehat{q}_{k_{i}},\widehat{q}_{k_{i+1}})$. For $j\in[n]$ and
$i\in\\{0,1,\dots,\ell-1\\}$, let

$W_{j}=w_{i(j)}\text{ and }Z_{i}=\prod_{j:i(j)=i}W_{j}^{-1}.$

Then, on the event $\mathcal{G}$, we have

$\displaystyle\sum_{j=1}^{n}W_{j}X_{j}$
$\displaystyle=\sum_{i=0}^{\ell-1}\sum_{j:i(j)=i}W_{j}X_{j}\leq\sum_{i=0}^{\ell-1}Ln\cdot
2^{-k_{i}}\widehat{q}_{k_{i+1}}\lesssim\sum_{k=0}^{t+1}Ln\cdot
2^{-k}\widehat{q}_{k}$ $\displaystyle\lesssim Ln+\sum_{k=1}^{t}Ln\cdot
2^{-k}q_{k+1}\lesssim Ln\left(1+\mathbb{E}\xi\right)\lesssim Ln.$

Moreover, on the event $\mathcal{G}$, we have for any
$i\in\\{0,1,\dots,\ell-1\\}$ that

$\displaystyle\mathbb{E}_{X_{1},\dots,X_{n}}[Z_{i}]$ $\displaystyle\leq
1+\mathbb{E}\left[\left(\frac{\nu_{i}}{L2^{-k_{i}}n}\right)^{\nu_{i}}\mathbbm{1}_{\nu_{i}>L2^{-k_{i}}n}\right]$
$\displaystyle\leq
1+\sum_{s>L2^{-k_{i}}n}\left(\frac{s}{L2^{-k_{i}}n}\right)^{s}\mathbb{P}[\nu_{i}=s]$
$\displaystyle\leq
1+\sum_{s>L2^{-k_{i}}n}\left(\frac{s}{L2^{-k_{i}}n}\right)^{s}\binom{n}{s}\mathbb{P}[\xi\geq\widehat{q}_{k_{i}}]^{s}$
$\displaystyle\leq
1+\sum_{s>L2^{-k_{i}}n}\left(\frac{e}{L2^{-k_{i}}}\right)^{s}\mathbb{P}[\xi\geq
q_{k_{i}-1}]^{s}$ $\displaystyle\leq
1+\sum_{s>L2^{-k_{i}}n}\left(\frac{4e}{L}\right)^{s}\leq\exp\left(2\left(\frac{8e}{L}\right)^{\frac{Ln}{2^{2+k_{i}}}}\right),$

for a sufficiently large absolute constant $L$. Then, since the random
variables $|\nu_{0}|,\dots,|\nu_{\ell-1}|$ are negatively associated and since
$Z_{i}$ is an increasing function of $|\nu_{i}|$, it follows that

$\displaystyle\mathbb{E}_{X_{1},\dots,X_{n}}\left[\prod_{j=1}^{n}W_{j}^{-1}\right]$
$\displaystyle=\mathbb{E}\left[\prod_{i=0}^{\ell-1}Z_{i}\right]\leq\prod_{i=0}^{\ell-1}\mathbb{E}[Z_{i}]$
$\displaystyle\leq\exp\left(2\left(\frac{8e}{L}\right)^{L/(8K)}\right)\leq
1+\epsilon$

for a sufficiently large absolute constant $L$, where the final inequality
uses that $K=1/\log\epsilon^{-1}$. ∎

We can now quickly deduce Proposition 2.1.

###### Proof of Proposition 2.1.

We may assume that $n=\Omega(\epsilon^{-1})$ as otherwise, the desired
probability bound is negative. Moreover, by adding an extra row and column of
zeros (if necessary), we may assume that $n$ is even. Recall that the diagonal
entries of $T$ are $0$. Consider the $n/2\times n/2$ matrices

$N_{ij}=T_{i,n/2+j},\text{ and }$
$N^{\prime}_{ij}=\begin{cases}T_{i+n/2,j+n/2}&\text{ if }j>i\text{ and
}i<n/2\\\ T_{n/2-i,n/2-j+1}&\text{ if }j\leq i\text{ and }i<n/2\\\ 0&\text{ if
}i=n/2.\end{cases}$

Then, it is straightforward to see that if we can find $O(\epsilon n)$ columns
in $N$ and $N^{\prime}$ to zero-out such that the resulting matrices have
$\lVert\cdot\rVert_{2\to\infty}$ norm $O(\sqrt{n})$, then the same is true for
$T$ and in fact, the choice of columns used for $N$ and $N^{\prime}$
correspond to an obvious choice of columns for $T$.

By taking the union bound, it suffices to show the following: with probability
at least $1-2\exp(-\Omega(n\log{\epsilon^{-1}}))$ over the realisation of
$N^{\prime}$, with probability at least $1-2\exp(-\Omega(\epsilon n))$ over
the realization of $N$, we can algorithmically find a set of $O(\epsilon n)$
columns of $N$ to zero-out such that the resulting matrix has
$\lVert\cdot\rVert_{2\to\infty}$ norm $O(\sqrt{n})$. This follows from a
direct application of Lemma 2.2.

Indeed, we treat the entries $(N^{\prime}_{ij})^{2}$ for $i<n/2$ as the i.i.d.
samples $Y_{1},\dots,Y_{n^{2}/8}$. Then, by Lemma 2.2, with probability at
least $1-2\exp(-\Omega(n\log\epsilon^{-1}))$ over the realization of
$N^{\prime}$, the following holds. For any $i\in[n/2]$, we can find
$W_{i1},\dots,W_{i,n/2}\in[0,1]$ depending only on $N_{i1},\dots,N_{i,n/2}$
and $N^{\prime}$ such that

$\sum_{j=1}^{n/2}W_{ij}N_{ij}^{2}\leq C_{\ref{prop:damping-sum}}n\text{ and }$
$1\leq\mathbb{E}_{N_{i1},\ldots,N_{i,n/2}}\bigg{(}\prod_{j=1}^{n/2}W_{ij}\bigg{)}^{-1}\leq\exp(\epsilon).$

Let

$V_{j}=\prod_{i=1}^{n/2}W_{ij},\quad j\in[n/2].$

Then, $W_{ij}\leq V_{j}$ for all $i\in[n/2]$ so that

$\sum_{j=1}^{n/2}V_{j}N_{ij}^{2}\leq C_{\ref{prop:damping-sum}}n\quad\forall
i\in[n/2]\text{ and }$ (2.1)
$1\leq\mathbb{E}_{N}\bigg{(}\prod_{j=1}^{n/2}V_{j}\bigg{)}^{-1}\leq\exp(\epsilon
n).$ (2.2)

Let $J=\\{j\in[n/2]:V_{j}<e^{-2}\\}$. By 2.2 and Markov’s inequality, it
follows that $|J|\leq\epsilon n$ with probability at least $1-\exp(-\epsilon
n)$ over the choice of $N$. Moreover, by 2.1, it follows that for all
$i\in[n/2]$, $\sum_{j\in J^{c}}N_{ij}^{2}\leq e^{2}\cdot C_{\ref{prop:damping-
sum}}n$, which completes the proof. ∎

##  3\. Controlling $\infty\to 2$ and operator norms

###  3.1. $\infty\to 2$ norm

In this subsection, we will show how to turn a bound on
$\lVert\cdot\rVert_{2\to\infty}$ into a bound on $\lVert\cdot\rVert_{\infty\to
2}$. In contrast to the corresponding step in [7], we will be able to
accomplish this _without_ removing any additional columns, which will be
useful for our algorithmic regularization procedure. The goal of this
subsection is to prove the following Seginer-type [10] result for the
$\lVert\cdot\rVert_{\infty\to 2}$ norm.

######  Proposition 3.1.

Let $T$ be an $n\times n$ upper triangular matrix with i.i.d. entries of mean
$0$ and variance at most $1$. There exists an absolute constant
$C_{\ref{prop:restrictions}}>0$ such that with probability at least
$1-4^{-n}$, the following holds:

$\lVert T_{I}\rVert_{\infty\to 2}\leq
C_{\ref{prop:restrictions}}(\sqrt{n}\lVert T_{I}\rVert_{2\to\infty}+n)\text{
for all }I\subseteq[n],|I|\geq n/2.$

The proof of Proposition 3.1 will be presented at the end of this subsection
following a series of preparatory lemmas. We begin with the following tight
relationship between
$\lVert\cdot\rVert_{2\to\infty},\lVert\cdot\rVert_{\infty\to 2}$, and
$\lVert\cdot\mathbf{1}\rVert_{2}$, proved in [7] for a completely i.i.d.
matrix.

######  Lemma 3.2 ([7, Lemmas 6.3 and 6.4]).

Let $A$ be a random $n\times n$ matrix with i.i.d. entries. Then

$\mathbb{E}\lVert A\rVert_{\infty\to 2}\leq
C_{\ref{lem:concentration-1}}(\sqrt{n}\mathbb{E}\lVert
A\rVert_{2\to\infty}+\mathbb{E}\lVert A\mathbf{1}\rVert_{2}),$

and with probability at least $1-e^{-n}$,

$\lVert A\rVert_{\infty\to 2}\leq
C_{\ref{lem:concentration-1}}(\sqrt{n}\mathbb{E}\lVert
A\rVert_{2\to\infty}+\mathbb{E}\lVert A\mathbf{1}\rVert_{2}).$

We establish an analogous version for random upper triangular matrices with
i.i.d. entries.

######  Lemma 3.3.

Let $T$ be a random upper triangular $n\times n$ matrix with i.i.d. entries,
and let $J$ be a subset of columns with $|J|\geq n/2$. Then with probability
at least $1-2e^{-n}$,

$\lVert T_{J}\rVert_{\infty\to 2}\leq
C_{\ref{lem:concentration-2}}(\sqrt{n}\mathbb{E}\lVert
T_{J}\rVert_{2\to\infty}+\mathbb{E}\lVert T_{J}\mathbf{1}\rVert_{2}).$

During the course of our proof, we will make use of the following estimates
regarding random matrix models of different “shapes”.

######  Lemma 3.4.

Let $R\subseteq S\subseteq[n]\times[n]$. Then

$\mathbb{E}\lVert A_{R}\rVert_{\infty\to 2}\leq 2\mathbb{E}\lVert
A_{S}\rVert_{\infty\to 2}$

and

$\mathbb{E}\lVert A_{R}\mathbf{1}\rVert_{2}\leq 2\mathbb{E}\lVert
A_{S}\mathbf{1}\rVert_{2}.$

###### Proof.

Let $\mu=\mathbb{E}\xi$. We have

$\displaystyle\mathbb{E}\lVert A_{R}\rVert_{\infty\to 2}$
$\displaystyle=\mathbb{E}\lVert A_{R}+\mathbb{E}[A_{S\setminus
R}-\mathbb{E}A_{S\setminus R}]\rVert_{\infty\to 2}$
$\displaystyle\leq\mathbb{E}\lVert A_{R}+A_{S\setminus
R}-\mathbb{E}A_{S\setminus R}\rVert_{\infty\to 2}\leq\mathbb{E}\lVert
A_{S}\rVert_{\infty\to 2}+\lVert\mu\mathbf{1}_{S\setminus R}\rVert_{\infty\to
2}$ $\displaystyle\leq\mathbb{E}\lVert A_{S}\rVert_{\infty\to
2}+\lVert\mu\mathbf{1}_{S}\rVert_{\infty\to 2}=\mathbb{E}\lVert
A_{S}\rVert_{\infty\to 2}+\lVert\mathbb{E}A_{S}\rVert_{\infty\to 2}$
$\displaystyle\leq 2\mathbb{E}\lVert A_{S}\rVert_{\infty\to 2},$

where we have used Jensen’s inequality twice. An analogous proof establishes
the second inequality as well. ∎

We can now prove Lemma 3.3.

###### Proof of Lemma 3.3.

We may write $T_{J}=A_{S}$ for some $S\subseteq[n]\times[n]$, where note that
$S$ contains an $\lfloor n/4\rfloor\times\lfloor n/4\rfloor$ (not necessarily
consecutive) block as a subset. Since zeroing out entries of a matrix cannot
increase the $\lVert\cdot\rVert_{2\to\infty}$ norm, it follows that

$\mathbb{E}\lVert A\rVert_{2\to\infty}\lesssim\mathbb{E}\lVert A_{\lfloor
n/4\rfloor\times\lfloor n/4\rfloor}\rVert_{2\to\infty}\leq\mathbb{E}\lVert
T_{J}\rVert_{2\to\infty}\leq\mathbb{E}\lVert A\rVert_{2\to\infty},$

where the first inequality uses the triangle inequality along with the
previously mentioned fact about zeroing out entries. Moreover, we have

$\mathbb{E}\lVert A\rVert_{\infty\to 2}\lesssim\mathbb{E}\lVert A_{\lfloor
n/4\rfloor\times\lfloor n/4\rfloor}\rVert_{\infty\to
2}\lesssim\mathbb{E}\lVert T_{J}\rVert_{\infty\to 2}\lesssim\mathbb{E}\lVert
A\rVert_{\infty\to 2},$

where the first inequality uses the triangle inequality and Lemma 3.4 and the
subsequent inequalities use Lemma 3.4. Similarly,

$\mathbb{E}\lVert A\mathbf{1}\rVert_{2}\lesssim\mathbb{E}\lVert A_{\lfloor
n/4\rfloor\times\lfloor
n/4\rfloor}\mathbf{1}\rVert_{2}\lesssim\mathbb{E}\lVert
T_{J}\mathbf{1}\rVert_{2}\lesssim\mathbb{E}\lVert A\mathbf{1}\rVert_{2}.$

Next, write $A=T_{J}+A_{S^{\prime}}$ for $S^{\prime}=([n]\times[n])\setminus
S$. Then, for $t\geq 2\mathbb{E}\lVert A_{S^{\prime}}\rVert_{\infty\to 2}$, we
have

$\displaystyle\mathbb{P}[\lVert A\rVert_{\infty\to 2}\geq t]$
$\displaystyle\geq\mathbb{P}[\lVert A_{S^{\prime}}\rVert_{\infty\to 2}\leq
t]\cdot\mathbb{P}[\lVert T_{J}\rVert_{\infty\to 2}\geq 2t]$
$\displaystyle\geq\mathbb{P}[\lVert T_{J}\rVert_{\infty\to 2}\geq 2t]/2,$

where the second line follows from Markov’s inequality. Since

$\mathbb{E}\lVert A_{S^{\prime}}\rVert_{\infty\to 2}\lesssim\mathbb{E}\lVert
A\rVert_{\infty\to 2}\lesssim\sqrt{n}\mathbb{E}\lVert
A\rVert_{2\to\infty}+\mathbb{E}\lVert
A\mathbf{1}\rVert_{2}\lesssim\sqrt{n}\mathbb{E}\lVert
T_{J}\rVert_{2\to\infty}+\mathbb{E}\lVert T_{J}\mathbf{1}\rVert_{2},$

where the first inequality is by Lemma 3.4, the second inequality is by Lemma
3.2, and the third is by the previously established inequalities, we may
choose

$t=C(\sqrt{n}\mathbb{E}\lVert T_{J}\rVert_{2\to\infty}+\mathbb{E}\lVert
T_{J}\mathbf{1}\rVert_{2})$

with $C$ is a large absolute constant guaranteeing that

$t\geq(2+C_{\ref{lem:concentration-1}})\max(\sqrt{n}\mathbb{E}\lVert
A\rVert_{2\to\infty}+\mathbb{E}\lVert A\mathbf{1}\rVert_{2},\mathbb{E}\lVert
A_{S^{\prime}}\rVert_{\infty\to 2}).$

Finally, for such a choice of $C$ and $t$, we have by Lemma 3.2 that

$\mathbb{P}[\lVert T_{J}\rVert_{\infty\to 2}\geq 2t]\leq 2\mathbb{P}[\lVert
A\rVert_{\infty\to 2}\geq t]\leq 2e^{-n},$

as desired. ∎

With the preceding lemma in hand, we can prove the following, which shows that
with at least some exponentially _small_ probability, the
$\lVert\cdot\rVert_{2\to\infty}$ and $\lVert\cdot\rVert_{\infty\to 2}$ norms
of the matrix are already regularized.

######  Lemma 3.5.

Let $T$ be a random upper triangular $n\times n$ matrix with i.i.d. entries of
mean $0$ and variance at most $1$, and let $J$ be a subset of columns with
$|J|\geq n/2$. For any $\delta\in(0,1/2)$,

$\lVert T_{J}\rVert_{2\to\infty}\leq C_{\ref{lem:low-
prob-2}}\delta^{-1}\sqrt{n}\quad\emph{and}\quad\lVert T_{J}\rVert_{\infty\to
2}\leq C_{\ref{lem:low-prob-2}}\delta^{-1}n$

with probability at least $\exp(-\delta^{2}n)/2$.

###### Proof.

The proof is identical to that of [7, Lemma 6.5] with the application of [7,
Lemma 6.4] replaced by Lemma 3.3. ∎

Finally, we need the following symmetrization estimate from [7].

######  Lemma 3.6 (Proof of [7, Lemma 6.1]).

Let $A$ be an $n\times n$ matrix and let $\widetilde{A}$ denote the random
matrix with entries $\widetilde{A}_{ij}=\epsilon_{ij}A_{ij}$, where
$\epsilon_{ij}$ are i.i.d. Rademacher random variables. There exists an
absolute constant $c_{\ref{lem:signs}}>0$ such that for all $t\geq 1$, with
probability at least $1-2^{n}\exp(-c_{\ref{lem:signs}}tn)$,

$\lVert\widetilde{A}\rVert_{\infty\to 2}\leq\sqrt{2tn}\lVert
A\rVert_{2\to\infty}.$

We now have all the ingredients needed to prove Proposition 3.1.

###### Proof of Proposition 3.1.

Fix $I\subseteq[n]$ with $|I|\geq n/2$, let $B=T_{I}$, and let
$\widetilde{B}=B-B^{\prime}$, where $B^{\prime}$ denotes an independent copy
of $T_{I}$. For $t\geq 1$ and $\delta\in(0,1/2)$, let

$\displaystyle\mathcal{E}(t)$
$\displaystyle:=\\{\lVert\widetilde{B}\rVert_{\infty\to
2}\leq\sqrt{2tn}\lVert\widetilde{B}\rVert_{2\to\infty}\\},$
$\displaystyle\mathcal{F}(\delta)$ $\displaystyle:=\\{\lVert
B^{\prime}\rVert_{2\to\infty}\leq C_{\ref{lem:low-
prob-2}}\delta^{-1}\sqrt{n}\wedge\lVert B^{\prime}\rVert_{\infty\to 2}\leq
C_{\ref{lem:low-prob-2}}\delta^{-1}n\\},\quad\text{ and }$
$\displaystyle\mathcal{G}(t,\delta)$ $\displaystyle:=\\{\lVert
B\rVert_{\infty\to 2}\leq 2\sqrt{2tn}\lVert
B\rVert_{2\to\infty}+(2C_{\ref{lem:low-
prob-2}}\delta^{-1}\sqrt{2t}+C_{\ref{lem:low-prob-2}}\delta^{-1})n\\}.$

Then, by the triangle inequality, we have that on the event
$\mathcal{G}(t,\delta)^{c}\cap\mathcal{F}(\delta)$,

$\displaystyle\lVert\widetilde{B}\rVert_{2\to\infty}$ $\displaystyle\leq\lVert
B\rVert_{2\to\infty}+\lVert B^{\prime}\rVert_{2\to\infty}\leq\lVert
B\rVert_{2\to\infty}+C_{\ref{lem:low-prob-2}}\delta^{-1}\sqrt{n},\quad\text{
and }$ $\displaystyle\lVert\widetilde{B}\rVert_{\infty\to 2}$
$\displaystyle\geq\lVert B\rVert_{\infty\to 2}-\lVert
B^{\prime}\rVert_{\infty\to 2}\geq 2\sqrt{2tn}\bigg{(}\lVert
B\rVert_{2\to\infty}+C_{\ref{lem:low-prob-2}}\delta^{-1}\sqrt{n}\bigg{)}.$

In particular, this implies

$\mathcal{G}(t,\delta)^{c}\cap\mathcal{F}(\delta)\subseteq\mathcal{E}^{c}(t).$

Therefore, since $\mathcal{G}(t,\delta)$ and $\mathcal{F}(\delta)$ are
independent, we have

$\mathbb{P}[\mathcal{G}(t,\delta)^{c}]\leq\frac{\mathbb{P}[\mathcal{E}^{c}(t)]}{\mathbb{P}[\mathcal{F}(\delta)]}\leq\frac{2^{n}\exp(-c_{\ref{lem:signs}}tn)}{\exp(-\delta^{2}n)/2},$

where we have used Lemmas 3.6 and 3.5. Finally, choosing
$t=1000/c_{\ref{lem:signs}}$, $\delta=1/4$, and taking the union bound over at
most $2^{n}$ choices of $I$, we obtain the desired conclusion. ∎

###  3.2. Operator norm

Having thus established control over $\lVert\cdot\rVert_{\infty\to 2}$, we can
apply a version of the Grothendieck-Pietsch theorem [5, Proposition 15.11] as
in [4, 7] to establish control over the operator norm.

######  Theorem 3.7.

Let $B$ be a $k\times m$ real matrix and let $\delta>0$. There exists
$J\subseteq[m]$ with $|J|\leq\delta m$ for which

$\lVert B_{J^{c}}\rVert\leq\frac{2}{\sqrt{\delta m}}\lVert B\rVert_{\infty\to
2}.$

Now, applying Propositions 2.1, 3.1 and 3.7 in sequence immediately yields the
following result.

######  Proposition 3.8.

Let $\epsilon\in(0,1/2)$ and consider an $n\times n$ upper triangular matrix
$T$ with i.i.d. mean $0$ entries of variance at most $1$, and such that
$|T_{ij}|\leq\sqrt{n/\log(1/\epsilon)}$ almost surely. Then with probability
at least $1-2\exp(-c_{\ref{prop:almost-surely-bounded}}\epsilon n)$, there is
a subset $J\subseteq[n]$ with $|J|\leq C_{\ref{prop:almost-surely-
bounded}}\epsilon n$ such that

$\lVert T_{J^{c}}\rVert\leq C_{\ref{prop:almost-surely-
bounded}}\sqrt{\frac{n}{\epsilon}}.$

##  4\. Medium and Large Entries

In this section, we handle the “medium” and “large” entries. Let
$\epsilon\in(0,1/2)$, and recall that Proposition 3.8 takes care of those
entries of the matrix $T$ which have absolute value at most
$\sqrt{n/\log\epsilon^{-1}}$. We split the remaining entries of $T$ into three
separate classes:

  * •

$|T_{i,j}|\in\left(\sqrt{n/\log\epsilon^{-1}},\sqrt{n/(\epsilon\log^{2}\epsilon^{-1})}\right]$,

  * •

$|T_{i,j}|\in\left(\sqrt{n/(\epsilon\log^{2}\epsilon^{-1})},5\sqrt{n/\epsilon}\right]$,
and

  * •

$|T_{i,j}|>5\sqrt{n/\epsilon}$.

The first and third classes are handled using arguments similar to [7]. The
second class requires a more intricate argument, and will be considered at the
end of this section.

We will need an elementary lemma from [7] which will allow us to combine
different sub-matrices that we zero out into one.

######  Lemma 4.1 ([7, Lemma 8.7]).

Let $M$ be an $n\times n$ matrix. Let $I,J\subseteq[n]$. Then

$\lVert B-B_{I\times J}\rVert\leq\lVert B_{I^{c}\times[n]}\rVert+\lVert
B_{[n]\times J^{c}}\rVert\leq 2\lVert B\rVert.$

###### Proof.

Indeed,

$\lVert B-B_{I\times J}\rVert\leq\lVert B_{I^{c}\times[n]}\rVert+\lVert
B_{I\times J^{c}}\rVert\leq\lVert B_{I^{c}\times[n]}\rVert+\lVert B_{[n]\times
J^{c}}\rVert\leq 2\lVert B\rVert,$

where the first inequality is the triangle inequality, and the remaining
inequalities use that zeroing out a subset of rows and/or columns cannot
increase the operator norm. ∎

We also require the following bound on the operator norm of the matrix in
terms of the $\ell_{1}$ norms of its rows and columns, due to Schur [9].

######  Lemma 4.2.

For any matrix $A$,

$\lVert A\rVert\leq\lVert A\rVert_{\infty\to 1}^{1/2}\lVert
A^{T}\rVert_{\infty\to 1}^{1/2}.$

Now, we proceed to the treatment of the three classes of entries. The easiest
is the third class, for which the result follows by a straightforward
application of the Chernoff bound.

######  Lemma 4.3 (Modification of [7, Corollary 8.6]).

Let $\epsilon\in(0,1/2]$. Consider an $n\times n$ random matrix upper
triangular matrix $T$ with independent (but not necessarily identically
distributed) entries $T_{ij}$ such that $T_{ij}=0$ or $|T_{ij}|\geq
5\sqrt{n/\epsilon}$, and which satisfy $\mathbb{E}T_{ij}^{2}\leq 1$. Then with
probability $1-\exp(-\epsilon n)$, all nonzero entries of $T$ are contained in
an $\epsilon n\times\epsilon n$ matrix.

######  Remark.

In [7], the above lemma is stated for identically distributed entries but as
can be seen from the proof, this assumption is unnecessary.

Next, we handle entries in the first class. The following lemma, and its proof
(which we include for completeness), are essentially identical to [7,
Proposition 8.4].

######  Lemma 4.4.

Let $\epsilon\in(0,1/2]$. Let $T$ be a random upper triangular $n\times n$
matrix with i.i.d. entries of mean $0$ and variance at most $1$ such that
$T_{ij}=0$ or
$|T_{ij}|\in[\sqrt{n/\log\epsilon^{-1}},\sqrt{n/(\epsilon\log^{2}\epsilon^{-1})}]$
almost surely. With probability at least $1-2\exp(-\epsilon n/4)$ we can zero
out an $\epsilon n\times\epsilon n$ block to obtain $\widetilde{T}$ satisfying

$\lVert\widetilde{T}\rVert\leq C_{\ref{lem:medium-
low}}\sqrt{\frac{n}{\epsilon}}.$

###### Proof.

Let $B_{ij}=\mathbbm{1}_{T_{ij}\neq 0}$. Since the $B_{ij}$ are independent
Bernoulli random variables with mean $p\leq(\log\epsilon^{-1})/n$, it follows
from [7, Corollary 8.2] that with probability at least $1-2\exp(-\epsilon
n/4)$, we can find an $\epsilon n\times\epsilon n$ sub-matrix of $B$ to zero
out so that the rows and columns of the resulting matrix have at most
$O(\log\epsilon^{-1})$ ones each. Since
$|T_{ij}|\leq\sqrt{n/(\epsilon\log^{2}\epsilon^{-1})}$, this shows that we can
find an $\epsilon n\times\epsilon n$ sub-matrix of $T$ to zero out so that the
rows and columns of the resulting matrix have $\ell_{1}$ norm at most
$O(\sqrt{n/\epsilon})$ each. An application of Lemma 4.2 gives the desired
result. ∎

Finally, we handle entries in the second class.

######  Proposition 4.5.

Let $\epsilon\in(0,1/2]$. Let $T$ be a random upper triangular $n\times n$
matrix with i.i.d. entries of mean $0$ and variance at most $1$ such that
$T_{ij}=0$ or
$|T_{ij}|\in[\sqrt{n/(\epsilon\log^{2}\epsilon^{-1})},5\sqrt{n/\epsilon}]$
almost surely. With probability at least $1-2\exp(-c_{\ref{prop:medium-
high}}\epsilon n)$ we can zero out a square sub-matrix of size
$C_{\ref{prop:medium-high}}\epsilon n\times C_{\ref{prop:medium-high}}\epsilon
n$ to obtain $\widetilde{T}$ satisfying

$\lVert\widetilde{T}\rVert\leq C_{\ref{prop:medium-
high}}\sqrt{\frac{n}{\epsilon}}.$

###### Proof.

As always, we can assume $n=\Omega(\epsilon^{-1})$ since otherwise, the target
probability is negative. Consider the matrix $B_{ij}=\mathbbm{1}_{T_{ij}\neq
0}$. This is an upper triangular matrix with i.i.d. $\operatorname{Ber}(p)$
entries, where $p\leq(\epsilon\log^{2}\epsilon^{-1})/n$. We will show that
with probability $1-2\exp(-c\epsilon n)$, one can remove $O(\epsilon n)$ rows
of $B$ to obtain $B^{\prime}$ such that each row and each column of
$B^{\prime}$ has at most a single entry equal to $1$. Since $|T_{ij}|\leq
5\sqrt{n/\epsilon}$, this shows that the corresponding matrix $T^{\prime}$
will satisfy $\lVert T^{\prime}\rVert\leq 5\sqrt{n/\epsilon}$. By using the
symmetry $(i,j)\mapsto(n-j,n-i)$, it follows that with probability
$1-2\exp(-c\epsilon n)$, one can remove $O(\epsilon n)$ columns of $T$ to
obtain $T^{\prime\prime}$ with $\lVert T^{\prime\prime}\rVert\leq
5\sqrt{n/\epsilon}$. Finally, Lemma 4.1 shows that the matrix $\widetilde{T}$
obtained by removing the intersection of these $O(\epsilon n)$ rows and
$O(\epsilon n)$ columns will have operator norm bounded by
$O(\sqrt{n/\epsilon})$ as desired.

Therefore, consider $B$ as above. Let $t$ denote the number of rows of $B$
with exactly one entry equal to $1$ and let $b$ denote the number of rows of
$B$ with at least two entries equal to $1$. Also, let $B^{(1)}$ denote the
$t\times n$ sub-matrix of $B$ in which each row has exactly one entry equal to
$1$. Then, by the Chernoff–Hoeffding bound [3, Theorem 1], except with
probability at most $2\exp(-c\epsilon n\log^{2}\epsilon^{-1})$, we have $t\leq
t^{*}:=\lceil 2\epsilon n\log^{2}\epsilon^{-1}\rceil$ and $b=O(\epsilon n)$.
Hence, with probability at least $1-2\exp(-c\epsilon n\log^{2}\epsilon^{-1})$,
we have enough room to remove all rows of $B$ with at least two entries equal
to $1$.

It remains to deal with $B^{(1)}$. Let $B^{(-)}$ denote the sub-matrix of
$B^{(1)}$ consisting of the first $n_{-}$ columns and $B^{(+)}$ denote the
sub-matrix of $B^{(1)}$ consisting of the remaining $n_{+}$ columns, where
$n_{-}$ and $n_{+}$ are chosen to be as close to each other as possible. We
wish to bound the probability

$\mathbb{P}[B^{(\pm)}\in\mathcal{B}\mid t]$

uniformly for all $t\leq t^{*}$, where $\mathcal{B}$ denotes the collection of
$\\{0,1\\}$-valued $t\times n_{\pm}$ matrices for which the number of non-zero
entries present in the union of all columns with at least two non-zero entries
is not $O(\epsilon n)$. We present the bound for $B^{(-)}$, noting that the
same argument also applies to $B^{(+)}$. Clearly, the probability is maximized
for $t=t^{*}$. Moreover, since the rows of $B^{(-)}$ are independent and since
each row has the distribution

$R\sim\begin{cases}\mathbf{0},\text{ w.p. }n_{-}/n,\\\ e_{i},\text{ w.p.
}n_{+}/(n_{-}\cdot n)\text{ for all }i\in[n_{-}],\end{cases}$

it follows that for all $t\leq t^{*}$ and $n\geq 10$,

$\mathbb{P}[B^{(-)}\in\mathcal{B}\mid
t]\leq\mathbb{P}[B^{(-)}\in\mathcal{B}\mid
t^{*}]\leq\mathbb{P}[\widehat{B}\in\mathcal{B}],$

where $\widehat{B}$ denotes a random $t^{*}\times n_{-}$ matrix whose entries
are i.i.d. $\operatorname{Ber}(2/n)$ random variables. We note that the above
trick of splitting into $B^{(\pm)}$ and passing to the independent model is
closely related to the proof of [1, Theorem 4.1].

To bound $\mathbb{P}[\widehat{B}\in\mathcal{B}]$, we note two things. First,
by the Chernoff-Hoeffding bound, with probability at least $1-2\exp(-c\epsilon
n)$, there are at most $s^{*}=\epsilon n/\log\epsilon^{-1}$ columns of
$\widehat{B}$ with at least two non-zero entries. Second, assuming $s^{*}\geq
1$ (otherwise, we are already done) by the Chernoff-Hoeffding bound and the
union bound, the probability that _any_ $t^{*}\times\lfloor s^{*}\rfloor$
block of $\widehat{B}$ has more than $O(\epsilon n)$ entries is at most
$2\exp(-c\epsilon n)$. Combining these two facts shows that
$\mathbb{P}[\widehat{B}\in\mathcal{B}]\leq 4\exp(-c\epsilon n)$.

To summarize, we have shown that except with probability $O(\exp(-c\epsilon
n))$, the following hold simultaneously: $b=O(\epsilon n)$,
$B^{(-)}\notin\mathcal{B}$, $B^{(+)}\notin\mathcal{B}$. On this event, we are
guaranteed that there are $O(\epsilon n)$ rows of $B$ which either have at
least two non-zero entries, or which contain a non-zero entry in a column of
$B^{(\pm)}$ with at least two non-zero entries. Then, we can simply zero out
all such rows to obtain the desired conclusion. ∎

##  5\. Proof of Theorems 1.2, 1.3 and 1.4

We are now in position to prove all our results.

###### Proof of Theorems 1.2, 1.3 and 1.4.

We may assume that $n=\Omega(\epsilon^{-1})$ since otherwise, the desired
success probability is negative and the statements are vacuously true.
Moreover, it suffices to prove a version of Theorem 1.4 for i.i.d. random
upper triangular matrices since this readily implies Theorems 1.2, 1.3 and
1.4. We decompose

$T=S+M_{1}+M_{2}+L,$

where $S$ contains the entries with magnitude at most
$\sqrt{n/\log\epsilon^{-1}}$, $M_{1}$ contains the entries with magnitude in

$I_{1}=(\sqrt{n/\log\epsilon^{-1}},\sqrt{n/(\epsilon\log^{2}\epsilon^{-1})}],$

$M_{2}$ contains the entries with magnitude in

$I_{2}=(\sqrt{n/(\epsilon\log^{2}\epsilon^{-1})},5\sqrt{n/\epsilon}],$

and $L$ contains the entries with magnitude greater than $5\sqrt{n/\epsilon}$.

Since $(M_{1})_{ij}=T_{ij}\mathbbm{1}_{|T_{ij}|\in I_{1}}$, we see that
$M_{1}$ satisfies the assumptions of Lemma 4.4. Therefore, with probability at
least $1-2\exp(-\epsilon n/4)$, we can find an $\epsilon n\times\epsilon n$
sub-matrix of $M_{1}$ to zero out so that the resulting matrix
$\lVert\widetilde{M_{1}}\rVert$ has norm at most $C_{\ref{lem:medium-
low}}\sqrt{n/\epsilon}$. Moreover, the proof of [7, Corollary 8.2] shows that
this step can be done algorithmically. Indeed, one only needs to find the rows
and columns of $M_{1}$ with more than $O(\log{\epsilon^{-1}})$ non-zero
entries and then zero out _any_ $\epsilon n\times\epsilon n$ sub-matrix
containing all the entries contained in such rows and columns. This last step
is easy since [7, Corollary 8.2] guarantees that there are at most $\epsilon
n$ such entries so that they can be trivially placed in an $\epsilon
n\times\epsilon n$ sub-matrix.

Similarly, we can apply Proposition 4.5 to $M_{2}$ in order to find a suitable
$\epsilon n\times\epsilon n$ sub-matrices to remove. In order to do this
algorithmically, let $R_{1}$ denote the set of rows with exactly one non-zero
entry, let $R_{2}$ denote the set of rows with at least two non-zero entries,
let $C_{2}(R_{1})$ denote the set of columns with at least two non-zero
entries in rows in $R_{1}$, and let $R_{1}^{\prime}$ denote the set of rows in
$R_{1}$ such that the unique non-zero entry is in a column in $C_{2}(R_{1})$.
Define $C_{1},C_{2},R_{2}(C_{1}),C_{1}^{\prime}$ similarly with the role of
rows and columns interchanged. Then, the proof of Proposition 4.5 shows that,
with probability at least $1-2\exp(-c_{\ref{prop:medium-high}}\epsilon n)$,
the intersection of the rows $R_{2}\cup R_{1}^{\prime}$ and the columns
$C_{2}\cup C_{1}^{\prime}$ is contained in an $C_{\ref{prop:medium-
high}}\epsilon n\times C_{\ref{prop:medium-high}}\epsilon n$ sub-matrix and
zeroing it out suffices to regularize the norm of $M_{2}$.

To regularize the norm of $L$, we can apply Lemma 4.3. Again, this is
algorithmic, since we only need to remove a sub-matrix containing all non-zero
entries (of which there are at most $\epsilon n$ with probability at least
$1-\exp(-\epsilon n)$, see the proof of [7, Corollary 8.6]).

Finally, we regularize the norm of $S$. Let
$\xi^{\prime}=\xi\mathbbm{1}_{|\xi|\leq\sqrt{n/\log\epsilon^{-1}}}$ where
$\xi$ denotes the common distribution of the upper triangular entries of $T$
and note that the upper triangular entries of $S$ are i.i.d. copies of
$\xi^{\prime}$. Since $\mathbb{E}[\xi^{\prime 2}]\leq\mathbb{E}[\xi^{2}]\leq
1$, we can apply Proposition 2.1 to algorithmically find (with probability at
least $1-2\exp(-c_{\ref{lem:sym-2->infty}}\epsilon n)$ a set
$J_{0}\subseteq[n]$ of $O(\epsilon n)$ columns such that

$\lVert S_{J_{0}^{c}}\rVert_{2\to\infty}=O(\sqrt{n}).$

In order to be able to apply Proposition 3.1, we need such a result not for
$S$ but for $S-\mathbb{E}S$. For this, we note that

$\displaystyle|\mathbb{E}\xi^{\prime}|$
$\displaystyle=\Big{|}\mathbb{E}\xi\mathbbm{1}_{|\xi|\leq\sqrt{n/\log\epsilon^{-1}}}\Big{|}=\Big{|}\mathbb{E}\Big{[}\xi-\xi\mathbbm{1}_{|\xi|>\sqrt{n/\log\epsilon^{-1}}}\Big{]}\Big{|}$
$\displaystyle=\Big{|}\mathbb{E}\xi\mathbbm{1}_{|\xi|>\sqrt{n/\log\epsilon^{-1}}}\Big{|}\leq(\mathbb{E}\xi^{2})^{1/2}\mathbb{P}\Big{[}|\xi|>\sqrt{n/\log\epsilon^{-1}}\Big{]}^{1/2}\leq\sqrt{\frac{\log\epsilon^{-1}}{n}}.$

Therefore, for all $J\subseteq[n]$,

$\lVert(\mathbb{E}S)_{J}\rVert_{2\to\infty}\leq\sqrt{\log{\epsilon^{-1}}},\quad\lVert(\mathbb{E}S)_{J}\rVert\leq\sqrt{n\log{\epsilon^{-1}}}.$

In particular,

$\lVert(S-\mathbb{E}S)_{J_{0}^{c}}\rVert_{2\to\infty}=O(\sqrt{n}+\sqrt{\log{\epsilon^{-1}}})=O(\sqrt{n}).$

Combining this with Proposition 3.1, we see that except with probability at
least $1-4^{-n}-2\exp(-c_{\ref{lem:sym-2->infty}}\epsilon n)$,

$\lVert(S-\mathbb{E}S)_{J_{0}^{c}}\rVert_{\infty\to 2}=O(n).$ (5.1)

Therefore, by Theorem 3.7, we see that there exists some $\mu$ with
$|\mu|\leq\sqrt{\log{\epsilon^{-1}}/n}$ and a subset of columns $J_{1}$ with
$J_{1}=O(\epsilon n)$ such that for $J_{*}=J_{1}\cup J_{0}$,

$\lVert(S-\mu\mathbf{1}\mathbf{1}^{T})_{J_{*}^{c}}\rVert=O(\sqrt{n/\epsilon}).$

This immediately implies that

$\lVert S_{J_{*}^{c}}\rVert\leq
O(\sqrt{n/\epsilon})+O(\sqrt{n\log{\epsilon^{-1}}})=O(\sqrt{n/\epsilon}).$

In order to find $\mu$ and $J_{1}$ algorithmically, it suffices to apply a
deterministic version of Theorem 3.7 due to Tropp [11, Theorem 3.1] to the
matrices

$(S-\frac{j}{\sqrt{n}}\mathbf{1}\mathbf{1}^{T})_{J_{0}^{c}},\quad j=0,\pm
1,\pm 2,\dots,\pm\lceil\sqrt{\log{\epsilon^{-1}}}\rceil.$

By 5.1, Theorem 3.7, and the bound on $|\mathbb{E}\xi^{\prime}|$, this
procedure is guaranteed to succeed whenever 5.1 holds. We note that
alternatively, one may proceed by first learning the mean
$\mathbb{E}\xi^{\prime}$ to within additive error $1/\sqrt{n}$ and then using
the algorithm of [11, Theorem 3.1] on the matrix
$(S-\widehat{\mathbb{E}S})_{J_{0}^{c}}$, where $\widehat{\mathbb{E}S}$ is our
approximation for $\mathbb{E}S$.

Next, by symmetry, one may repeat this procedure to find a collection of
$O(\epsilon n)$ rows $K_{*}$ such that

$\lVert S_{K_{*}^{c}}\rVert=O(\sqrt{n/\epsilon}).$

By Lemma 4.1, it follows that zeroing out the $O(\epsilon n)\times O(\epsilon
n)$ sub-matrix formed by the intersection of the rows in $K_{*}$ and columns
in $J_{*}$ makes the norm of the resulting matrix $O(\sqrt{n/\epsilon})$. We
now use Lemma 4.1 to combine the sub-matrices zeroed out for $S,M_{1},M_{2},L$
and rescale $\epsilon$ to complete the proof.

For the running time of the algorithm, the algorithmic Grothendieck-Pietsch
factorization in [11] can be performed in time $\tilde{O}(n^{7/2})$ and
everything else can clearly be performed in time $\tilde{O}(n^{2})$. ∎

## References

  * [1] Michael B. Cohen, _Nearly tight oblivious subspace embeddings by trace inequalities_ , Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2016, pp. 278–287.
  * [2] Uriel Feige and Eran Ofek, _Spectral techniques applied to sparse random graphs_ , Random Structures Algorithms 27 (2005), 251–275.
  * [3] Wassily Hoeffding, _Probability inequalities for sums of bounded random variables_ , J. Amer. Statist. Assoc. 58 (1963), 13–30.
  * [4] Can M. Le, Elizaveta Levina, and Roman Vershynin, _Concentration and regularization of random graphs_ , Random Structures Algorithms 51 (2017), 538–561.
  * [5] Michel Ledoux and Michel Talagrand, _Probability in Banach spaces_ , Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 23, Springer-Verlag, Berlin, 1991, Isoperimetry and processes.
  * [6] Elizaveta Rebrova, _Constructive regularization of the random matrix norm_ , J. Theoret. Probab. 33 (2020), 1768–1790.
  * [7] Elizaveta Rebrova and Roman Vershynin, _Norms of random matrices: local and global problems_ , Adv. Math. 324 (2018), 40–83.
  * [8] Mark Rudelson and Roman Vershynin, _Non-asymptotic theory of random matrices: extreme singular values_ , Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II–IV: Invited Lectures, World Scientific, 2010, pp. 1576–1602.
  * [9] J. Schur, _Bemerkungen zur Theorie der beschränkten Bilinearformen mit unendlich vielen Veränderlichen_ , J. Reine Angew. Math. 140 (1911), 1–28.
  * [10] Yoav Seginer, _The expected norm of random matrices_ , Combinatorics, Probability and Computing 9 (2000), 149–166.
  * [11] Joel A. Tropp, _Column subset selection, matrix factorization, and eigenvalue optimization_ , Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2009, pp. 978–986.
  * [12] Y. Q. Yin, Z. D. Bai, and P. R. Krishnaiah, _On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix_ , Probab. Theory Related Fields 78 (1988), 509–521.