# Average Case Column Subset Selection for
Entrywise $\ell_{1}$-Norm Loss††thanks: A preliminary version of this paper
appears in Proceedings of Thirty-third Conference on Neural Information
Processing Systems (NeurIPS 2019).

Zhao Song<EMAIL_ADDRESS>University of Washington. David P. Woodruff
<EMAIL_ADDRESS>Carnegie Mellon University. Peilin Zhong
<EMAIL_ADDRESS>Columbia University.

We study the column subset selection problem with respect to the entrywise
$\ell_{1}$-norm loss. It is known that in the worst case, to obtain a good
rank-$k$ approximation to a matrix, one needs an arbitrarily large
$n^{\Omega(1)}$ number of columns to obtain a $(1+\epsilon)$-approximation to
the best entrywise $\ell_{1}$-norm low rank approximation of an $n\times n$
matrix. Nevertheless, we show that under certain minimal and realistic
distributional settings, it is possible to obtain a
$(1+\epsilon)$-approximation with a nearly linear running time and
poly$(k/\epsilon)+O(k\log n)$ columns. Namely, we show that if the input
matrix $A$ has the form $A=B+E$, where $B$ is an arbitrary rank-$k$ matrix,
and $E$ is a matrix with i.i.d. entries drawn from any distribution $\mu$ for
which the $(1+\gamma)$-th moment exists, for an arbitrarily small constant
$\gamma>0$, then it is possible to obtain a $(1+\epsilon)$-approximate column
subset selection to the entrywise $\ell_{1}$-norm in nearly linear time.
Conversely we show that if the first moment does not exist, then it is not
possible to obtain a $(1+\epsilon)$-approximate subset selection algorithm
even if one chooses any $n^{o(1)}$ columns. This is the first algorithm of any
kind for achieving a $(1+\epsilon)$-approximation for entrywise
$\ell_{1}$-norm loss low rank approximation.

##  1 Introduction

Numerical linear algebra algorithms are fundamental building blocks in many
machine learning and data mining tasks. A well-studied problem is low rank
matrix approximation. The most common version of the problem is also known as
Principal Component Analysis (PCA), in which the goal is to find a low rank
matrix to approximate a given matrix such that the Frobenius norm of the error
is minimized. The optimal solution of this objective can be obtained via the
singular value decomposition (SVD). Hence, the problem can be solved in
polynomial time. If approximate solutions are allowed, then the running time
can be made almost linear in the number of non-zero entries of the given
matrix [Sar06, CW13, MM13, NN13, BDN15, Coh16].

An important variant of the PCA problem is the entrywise $\ell_{1}$-norm low
rank matrix approximation problem. In this problem, instead of minimizing the
Frobenius norm of the error, we seek to minimize the $\ell_{1}$-norm of the
error. In particular, given an $n\times n$ input matrix $A$, and a rank
parameter $k$, we want to find a matrix $B$ with rank at most $k$ such that
$\|A-B\|_{1}$ is minimized, where for a matrix $C$, $\|C\|_{1}$ is defined to
be $\sum_{i,j}|C_{i,j}|$. There are several reasons for using the
$\ell_{1}$-norm as the error measure. For example, solutions with respect to
the $\ell_{1}$-norm loss are usually more robust than solutions with Frobenius
norm loss [Hub64, CLMW11]. Further, the $\ell_{1}$-norm loss is often used as
a relaxation of the $\ell_{0}$-loss, which has wide applications including
sparse recovery, matrix completion, and robust PCA; see e.g., [XCS10, CLMW11].
Although a number of algorithms have been proposed for the $\ell_{1}$-norm
loss [KK03, KK05, KLC+15, Kwa08, ZLS+12, BJ12, BD13, BDB13, MXZZ13, MKP13,
MKP14, MKCP16, PK16], the problem is known to be NP-hard [GV15]. The first
$\ell_{1}$-low rank approximation with provable guarantees was proposed by
[SWZ17]. To cope with NP-hardness, the authors gave a solution with a
$\operatorname{poly}(k\log n)$-approximation ratio, i.e., their algorithm
outputs a rank-$k$ matrix $B^{\prime}\in\mathbb{R}^{n\times n}$ for which

$\displaystyle\|A-B^{\prime}\|_{1}\leq\alpha\cdot\min_{\operatorname{rank}-k\
B}\|A-B\|_{1}$ (1)

for $\alpha=\operatorname{poly}(k\log n)$. The approximation ratio $\alpha$
was further improved to $O(k\log k)$ by allowing $B^{\prime}$ to have a
slightly larger $k^{\prime}=O(k\log n)$ rank [CGK+17]. Such $B^{\prime}$ with
larger rank is referred to as a bicriteria solution. However, in high
precision applications, such approximation factors are too large. A natural
question is if one can compute a $(1+\epsilon)$-approximate solution
efficiently for $\ell_{1}$-norm low rank approximation. In fact, a
$(1+\epsilon)$-approximation algorithm was given in [BBB+19], but the running
time of their algorithm is a prohibitive
$n^{\operatorname{poly}(k/\epsilon)}$. Unfortunately, [BBB+19] shows in the
worst case that a $2^{k^{\Omega(1)}}$ running time is necessary for any
constant approximation given a standard conjecture in complexity theory.

Notation. To describe our results, let us first introduce some notation. We
will use $[n]$ to denote the set $\\{1,2,\cdots,n\\}$. We use $A_{i}$ to
denote the $i^{\text{th}}$ column of $A$. We use $A^{j}$ to denote the
$j^{\text{th}}$ row of $A$. Let $Q\subseteq[n]$. We use $A_{Q}$ to denote the
matrix which is comprised of the columns of $A$ with column indices in $Q$.
Similarly, we use $A^{Q}$ to denote the matrix which is comprised of the rows
of $A$ with row indices in $Q$. We use $[n]\choose t$ to denote the set of all
the size-$t$ subsets of $[n]$. Let $\|A\|_{F}$ denote the Frobenius norm of a
matrix $A$, i.e., $\|A\|_{F}$ is the square root of the sum of squares of all
the entries in $A$. For $1\leq p<2$, we use $\|A\|_{p}$ to denote the entry-
wise $\ell_{p}$-norm of a matrix $A$, i.e., $\|A\|_{p}$ is the $p$-th root of
the sum of $p$-th powers of the absolute values of the entries of $A$.
$\|A\|_{1}$ is an important special case of $\|A\|_{p}$, which corresponds to
the sum of absolute values of the entries in $A$. A random variable $X$ has
the Cauchy distribution if its probability density function is
$f(z)=\frac{1}{\pi(1+z^{2})}$.

###  1.1 Our Results

We propose an efficient bicriteria $(1+\epsilon)$-approximate column subset
selection algorithm for the $\ell_{1}$-norm. We bypass the running time lower
bound mentioned above by making a mild assumption on the input data, and also
show that our assumption is necessary in a certain sense.

Our main algorithmic result is described as follows.

######  Theorem 1.1 (Informal version of Theorem 2.13).

Suppose we are given a matrix $A=A^{*}+\Delta\in\mathbb{R}^{n\times n}$, where
$\operatorname{rank}(A^{*})=k$ for $k=n^{o(1)}$, and $\Delta$ is a random
matrix for which the $\Delta_{i,j}$ are i.i.d. symmetric random variables with
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]^{p})$
for some constant $p>1$. Let $\epsilon\in(0,1/2)$ satisfy
$1/\epsilon=n^{o(1)}.$ There is an
$\widetilde{O}(n^{2}+n\operatorname{poly}(k/\epsilon))$111We use the notation
$\widetilde{O}(f):=O(f\cdot\log^{O(1)}f)$. time algorithm (Algorithm 1) which
can output a subset $S\subseteq[n]$ with
$|S|\leq\operatorname{poly}(k/\epsilon)+O(k\log n)$ for which

$\displaystyle\min_{X\in\mathbb{R}^{|S|\times
n}}\|A_{S}X-A\|_{1}\leq(1+\epsilon)\|\Delta\|_{1},$

holds with probability at least $99/100$.

Note the running time in Theorem 1.1 is nearly linear in the number of non-
zero entries of $A$, since for an $n\times n$ matrix with i.i.d. noise drawn
from any continuous distribution, the number of non-zero entries of $A$ will
be $n^{2}$ with probability $1$. We also show the moment assumption of Theorem
1.1 is necessary in the following precise sense.

######  Theorem 1.2 (Hardness, informal version of Theorem B.20).

Let $n>0$ be sufficiently large. Let
$A=\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta\in\mathbb{R}^{n\times n}$
be a random matrix where $\eta=n^{c_{0}}$ for some sufficiently large constant
$c_{0},$ $\mathbf{1}\in\mathbb{R}^{n}$ is the all-ones vector, and $\forall
i,j\in[n],\Delta_{i,j}\sim C(0,1)$ are i.i.d. standard Cauchy random
variables. Let $r=n^{o(1)}.$ Then with probability at least $1-O(1/\log\log
n),$ $\forall S\subseteq[n]$ with $|S|=r,$

$\displaystyle\min_{X\in\mathbb{R}^{r\times n}}\|A_{S}X-A\|_{1}\geq
1.002\|\Delta\|_{1}.$

###  1.2 Our Techniques

For an overview of our hardness result, we refer readers to the supplementary
material, namely, Appendix B. In the following, we will outline the main
techniques used in our algorithm.

####  $(1+\epsilon)$-Approximate $\ell_{1}$-Low Rank Approximation.

We make the following distributional assumption on the input matrix
$A\in\mathbb{R}^{n\times n}$: namely, $A=A^{*}+\Delta$ where $A^{*}$ is an
arbitrary rank-$k$ matrix and the entries of $\Delta$ are i.i.d. from any
symmetric distribution with $\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1$ and
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1)$ for any real number $p$
strictly greater than $1$, e.g., $p=1.000001$ would suffice. Note that such an
assumption is mild compared to typical noise models which require the noise be
Gaussian or have bounded variance; in our case the random variables may even
be heavy-tailed with infinite variance. In this setting we show it is possible
to obtain a subset of $\operatorname{poly}(k(\epsilon^{-1}+\log n))$ columns
spanning a $(1+\epsilon)$-approximation. This provably overcomes the column
subset selection lower bound of [SWZ17] which shows for entrywise
$\ell_{1}$-low rank approximation that there are matrices for which any subset
of $\operatorname{poly}(k)$ columns spans at best a
$k^{\Omega(1)}$-approximation.

Consider the following algorithm: sample $\operatorname{poly}(k/\epsilon)$
columns of $A$, and try to cover as many of the remaining columns as possible.
Here, by covering a column $i$, we mean that if $A_{I}$ is the subset of
columns sampled, then $\min_{y}\|A_{I}y-A_{i}\|_{1}\leq(1+O(\epsilon))n$. The
reason for this notion of covering is that we are able to show in Lemma 2.1
that in this noise model, $\|\Delta\|_{1}\geq(1-\epsilon)n^{2}$ w.h.p., and so
if we could cover every column $i$, our overall cost would be
$(1+O(\epsilon))n^{2}$, which would give a $(1+O(\epsilon))$-approximation to
the overall cost.

We will not be able to cover all columns, unfortunately, with our initial
sample of $\operatorname{poly}(k/\epsilon)$ columns of $A$. Instead, though,
we will show that we will be able to cover all but a set $T$ of $\epsilon
n/(k\log k)$ of the columns. Fortunately, we show in Lemma 2.4 another
property of the noise matrix $\Delta$ is that all subsets $S$ of columns of
size at most $n/r$, for $r\geq(1/\gamma)^{1+1/(p-1)}$ satisfy $\sum_{j\in
S}\|\Delta_{j}\|_{1}=O(\gamma n^{2})$. Thus, for the above set $T$ that we do
not cover, we can apply this lemma to it with $\gamma=\epsilon/(k\log k)$, and
then we know that $\sum_{j\in T}\|\Delta_{j}\|_{1}=O(\epsilon n^{2}/(k\log
k))$, which then enables us to run a previous $\widetilde{O}(k)$-approximate
$\ell_{1}$ low rank approximation algorithm [CGK+17] on the set $T$, which
will only incur total cost $O(\epsilon n^{2})$, and since by Lemma 2.1 above
the overall cost is at least $(1-\epsilon)n^{2}$, we can still obtain a
$(1+O(\epsilon))$-approximation overall.

The main missing piece of the algorithm to describe is why we are able to
cover all but a small fraction of the columns. One thing to note is that our
noise distribution may not have a finite variance, and consequently, there can
be very large entries $\Delta_{i,j}$ in some columns. In Lemma 2.3, we show
the number of columns in $\Delta$ for which there exists an entry larger than
$n^{1/2+1/(2p)}$ in magnitude is $O(n^{(2-p)/2})$, which since $p>1$ is a
constant bounded away from $1$, is sublinear. Let us call this set with
entries larger than $n^{1/2+1/(2p)}$ in magnitude the set $H$ of “heavy"
columns; we will not make any guarantees about $H$, rather, we will stuff it
into the small set $T$ of columns above on which we will run our earlier
$O(k\log k)$-approximation.

For the remaining, non-heavy columns, which constitute almost all of our
columns, we show in Lemma 2.5 that $\|\Delta_{i}\|_{1}\leq(1+\epsilon)n$
w.h.p. The reason this is important is that recall to cover some column $i$ by
a sample set $I$ of columns, we need
$\min_{y}\|A_{I}y-A_{i}\|_{1}\leq(1+O(\epsilon))n$. It turns out, as we now
explain, that we will get
$\min_{y}\|A_{I}y-A_{i}\|_{1}\leq\|\Delta_{i}\|_{1}+e_{i}$, where $e_{i}$ is a
quantity which we can control and make $O(\epsilon n)$ by increasing our
sample size $I$. Consequently, since $\|\Delta_{i}\|_{1}\leq(1+\epsilon)n$,
overall we will have $\min_{y}\|A_{I}y-A_{i}\|_{1}\leq(1+O(\epsilon))n$, which
means that $i$ will be covered. We now explain what $e_{i}$ is, and why
$\min_{y}\|A_{I}y-A_{i}\|_{1}\leq\|\Delta_{i}\|_{1}+e_{i}$.

Towards this end, we first explain a key insight in this model. Since the
$p$-th moment exists for some real number $p>1$ (e.g., $p=1.000001$ suffices),
averaging helps reduce the noise of fitting a column $A_{i}$ by subsets of
other columns. Namely, we show in Lemma 2.2 that for any $t$ non-heavy column
$\Delta_{i_{1}},\ldots,\Delta_{i_{t}}$ of $\Delta$, and any coefficients
$\alpha_{1},\alpha_{2},\ldots,\alpha_{t}\in[-1,1]$,
$\|\sum_{j=1}^{t}\alpha_{j}\Delta_{i_{j}}\|_{1}=O(t^{1/p}n)$, that is, since
the individual coordinates of the $\Delta_{i_{j}}$ are zero-mean random
variables, their sum concentrates as we add up more columns. We do not need
bounded variance for this property.

How can we use this averaging property for subset selection? The idea is,
instead of sampling a single subset $I$ of $O(k)$ columns and trying to cover
each remaining column with this subset as shown in [CGK+17], we will sample
multiple independent subsets $I_{1},I_{2},\ldots,I_{t}$. Each set has size
$\operatorname{poly}(k/\epsilon)$ and we will sample at most
$\operatorname{poly}(k/\epsilon)$ subsets. By a similar argument of [CGK+17],
for any given column index $i\in[n]$, for most of these subset $I_{j}$, we
have that $A^{*}_{i}/\|\Delta_{i}\|_{1}$ can be expressed as a linear
combination of columns $A^{*}_{\ell}/\|\Delta_{\ell}\|_{1},\ell\in I_{j},$ via
coefficients of absolute value at most $1$. Note that this is only true for
most $i$ and most $j$; we develop terminology for this in Definitions 2.6,
2.7, 2.8, and 2.9, referring to what we call a good core. We quantify what we
mean by most $i$ and most $j$ having this property in Lemma 2.11 and Lemma
2.12.

The key though, that drives the analysis, is Lemma 2.10, which shows that
$\min_{y}\|A_{i}y-A_{i}\|_{1}\leq\|\Delta_{i}\|_{1}+e_{i}$, where
$e_{i}=O(q^{1/p}/t^{1-1/p}n)$, where $q$ is the size of each $I_{j}$, and $t$
is the number of different $I_{j}$. We need $q$ to be at least $k$, just as
before, so that we can be guaranteed that when we adjoin a column index $i$ to
$I_{j}$, there is some positive probability that
$A^{*}_{i}/\|\Delta_{i}\|_{1}$ can be expressed as a linear combination of
columns $A^{*}_{\ell}/\|\Delta_{\ell}\|_{1},\ell\in I_{j}$, with coefficients
of absolute value at most $1$. What is different in our noise model though is
the division by $t^{1-1/p}$. Since $p>1$, if we set $t$ to be a large enough
$\operatorname{poly}(k/\epsilon)$, then $e_{i}=O(\epsilon n)$, and then we
will have covered $A_{i}$, as desired. This captures the main property that
averaging the linear combinations for expression
$A^{*}_{i}/\|\Delta_{i}\|_{1}$ using different subsets $I_{j}$ gives us better
and better approximations to $A^{*}_{i}/\|\Delta_{i}\|_{1}$. Of course we need
to ensure several properties such as not sampling a heavy column (the
averaging in Lemma 2.2 does not apply when this happens), we need to ensure
most of the $I_{j}$ have small-coefficient linear combinations expressing
$A^{*}_{i}/\|\Delta_{i}\|_{1}$, etc. This is handled in our main theorem,
Theorem 2.13.

##  2 $\ell_{1}$-Norm Column Subset Selection

We first present two subroutines.

Linear regression with $\ell_{1}$ loss. The first subroutine needed is an
approximate $\ell_{1}$ linear regression solver. In particular, given a matrix
$M\in\mathbb{R}^{n\times d}$, $n$ vectors
$b_{1},b_{2},\cdots,b_{n}\in\mathbb{R}^{n}$, and an error parameter
$\epsilon\in(0,1)$, we want to compute
$x_{1},x_{2},\cdots,x_{n}\in\mathbb{R}^{d}$ for which $\forall i\in[n]$, we
have

$\displaystyle\|Mx_{i}-b_{i}\|_{1}\leq(1+\epsilon)\cdot\min_{x\in\mathbb{R}^{d}}\|Mx-
b_{i}\|_{1}.$

Furthermore, we also need an estimate $v_{i}$ of the regression cost
$\|Mx_{i}-b_{i}\|_{1}$ for each $i\in[n]$ such that $\|Mx_{i}-b_{i}\|_{1}\leq
v_{i}\leq(1+\epsilon)\|Mx_{i}-b_{i}\|_{1}$. Such an $\ell_{1}$-regression
problem can be solved efficiently (see [Woo14] for a survey). The total
running time to solve these $n$ regression problems simultaneously is at most
$\widetilde{O}(n^{2})+n\cdot\operatorname{poly}(d\log n)$, and the success
probability is at least $0.999$.

$\ell_{1}$ Column subset selection for general matrices. The second subroutine
needed is an $\ell_{1}$-low rank approximation solver for general input
matrices, though we allow a large approximation ratio. We use the algorithm
proposed by [CGK+17] for this purpose. In particular, given an $n\times d$
$(d\leq n)$ matrix $M$ and a rank parameter $k$, the algorithm can output a
small set $S\subset[n]$ with size at most $O(k\log n)$, such that

$\displaystyle\min_{X\in\mathbb{R}^{|S|\times d}}\|M_{S}X-M\|_{1}\leq O(k\log
k)\cdot\min_{\operatorname{rank}-k\ B}\|M-B\|_{1}.$

Furthermore, the running time is at most
$\widetilde{O}(n^{2})+n\cdot\operatorname{poly}(k\log n)$, and the success
probability is at least $0.999$. Now we can present our algorithm, Algorithm
1.

1:procedure L1NoisyLowRankApprox($A\in\mathbb{R}^{n\times n},k,\epsilon$)
$\triangleright$ Theorem 2.13

2: Sample a set $I$ from ${[n]\choose s}$ uniformly at random, where
$s=\operatorname{poly}(k/\epsilon).$

3: Solve the approximate $\ell_{1}$-regression problem
$\min_{x\in\mathbb{R}^{|I|}}\|A_{I}x-A_{i}\|_{1}$ for each $i\in[n]$, and let
$v_{i}$ be the estimated regression cost.

4: Compute the set $T=\\{i\in[n]\mid v_{i}\text{ is one of the top }l\text{
largest values among }v_{1},v_{2},\cdots,v_{n}\\}$, where
$l=n/\operatorname{poly}(k/\epsilon)$.

5: Solve $\ell_{1}$-column subset selection for $A_{T}.$ Let the solution be
$A_{Q}$.

6: Solve the approximate $\ell_{1}$-regression problem
$\min_{X\in\mathbb{R}^{(|I|+|Q|)\times n}}\|A_{(I\cup Q)}X-A\|_{1}$, and let
$\widehat{X}$ be the solution. Return $A_{(I\cup Q)}$ and $\widehat{X}$.
$\triangleright$ $A_{(I\cup Q)}\widehat{X}$ is a good low rank approximation
to $A$

7:end procedure

Algorithm 1 $\ell_{1}$-Low Rank Approximation with Input Assumption

Running time. Uniformly sampling a set $I$ can be done in
$\operatorname{poly}(k/\epsilon)$ time. According to our $\ell_{1}$-regression
subroutine, solving $\min_{x}\|A_{I}x-A_{i}\|_{1}$ for all $i\in[n]$ can be
finished in
$\widetilde{O}(n^{2})+n\cdot\operatorname{poly}(k\log(n)/\epsilon)$ time. We
only need sorting to compute the set $T$ which takes $O(n\log n)$ time. By our
second subroutine, the $\ell_{1}$-column subset selection for $A_{T}$ will
take $\widetilde{O}(n^{2})+n\cdot\operatorname{poly}(k\log n)$. The last step
only needs an $\ell_{1}$-regression solver, which takes
$\widetilde{O}(n^{2})+n\cdot\operatorname{poly}(k\log(n)/\epsilon)$ time.
Thus, the overall running time is
$\widetilde{O}(n^{2})+n\cdot\operatorname{poly}(k\log(n)/\epsilon)$.

The remaining parts in this section will focus on analyzing the correctness of
the algorithm.

###  2.1  Properties of the Noise Matrix

Recall that the input matrix $A\in\mathbb{R}^{n\times n}$ can be decomposed as
$A^{*}+\Delta$, where $A^{*}$ is the ground truth, and $\Delta$ is a random
noise matrix. In particular, $A^{*}$ is an arbitrary rank-$k$ matrix, and
$\Delta$ is a random matrix where each entry is an i.i.d. sample drawn from an
unknown symmetric distribution. The only assumption on $\Delta$ is that each
entry $\Delta_{i,j}$ satisfies
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}])$
for some constant $p>1$, i.e., the $p$-th moment of the noise distribution is
bounded. Without loss of generality, we will suppose
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1$,
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1)$, and $p\in(1,2)$
throughout the paper. In this section, we will present some key properties of
the noise matrix.

The following lemma provides a lower bound on $\|\Delta\|_{1}$. Once we have
the such lower bound, we can focus on finding a solution for which the
approximation cost is at most that lower bound.

######  Lemma 2.1 (Lower bound on the noise matrix).

Let $\Delta\in\mathbb{R}^{n\times n}$ be a random matrix where $\Delta_{i,j}$
are i.i.d. samples drawn from a symmetric distribution. Suppose
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1$ and
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1)$ for some constant
$p\in(1,2)$. Then, $\forall\epsilon\in(0,1)$ which satisfies
$1/\epsilon=n^{o(1)},$ we have

$\displaystyle\Pr\left[\|\Delta\|_{1}\geq(1-\epsilon)n^{2}\right]\geq
1-e^{-\Theta(n)}.$

The next lemma shows the main reason why we are able to get a small fitting
cost when running regression. Consider a toy example. Suppose we have a target
number $a\in\mathbb{R}$, and another $t$ numbers
$a+g_{1},a+g_{2},\cdots,a+g_{t}\in\mathbb{R}$, where $g_{i}$ are i.i.d.
samples drawn from the standard Gaussian distribution $N(0,1)$. If we use
$a+g_{i}$ to fit $a$, then the expected cost is
$\operatorname*{{\bf{E}}}[|a+g_{i}-a|]=\operatorname*{{\bf{E}}}[|g_{i}|]=\sqrt{2/\pi}$.
However, if we use the average of $a+g_{1},a+g_{2},\cdots,a+g_{t}$ to fit $a$,
then the expected cost is $\operatorname*{{\bf{E}}}[|\sum_{i=1}^{t}g_{i}|/t]$.
Since the $g_{i}$ are independent, $\sum_{i=1}^{t}g_{i}$ is a random Gaussian
variable with variance $t$, which means that the above expected cost is
$\sqrt{2/\pi}/\sqrt{t}$. Thus the fitting cost is reduced by a factor
$\sqrt{t}$. By generalizing the above argument, we obtain the following lemma.

######  Lemma 2.2 (Averaging reduces the noise).

Let $\Delta_{1},\Delta_{2},\cdots,\Delta_{t}\in\mathbb{R}^{n}$ be $t$ random
vectors. The $\Delta_{i,j}$ are i.i.d. symmetric random variables with
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1$ and
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1)$ for some constant
$p\in(1,2)$. Let $\alpha_{1},\alpha_{2},\cdots,\alpha_{t}\in[-1,1]$ be $t$
real numbers. Conditioned on $\forall i\in[n],j\in[t],|\Delta_{i,j}|\leq
n^{1/2+1/(2p)},$ with probability at least $1-2^{-n^{\Theta(1)}},$

$\displaystyle\left\|\sum_{i=1}^{t}\alpha_{i}\Delta_{i}\right\|_{1}\leq
O(t^{1/p}n).$

The above lemma needs a condition that each entry in the noise column should
not be too large. Fortunately, we can show that most of the (noise) columns do
not have any large entry.

######  Lemma 2.3 (Only a small number of columns have large entries).

Let $\Delta\in\mathbb{R}^{n\times n}$ be a random matrix where the
$\Delta_{i,j}$ are i.i.d. symmetric random variables with
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1$ and
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1)$ for some constant
$p\in(1,2)$. Let

$\displaystyle H=\\{j\in[n]\leavevmode\nobreak\ \big{|}\leavevmode\nobreak\
\exists i\in[n],|\Delta_{i,j}|>n^{1/2+1/(2p)}\\}.$

Then with probability at least $0.999$ $|H|\leq O(n^{1-(p-1)/2}).$

The following lemma shows that any small subset of the columns of the noise
matrix $\Delta$ cannot contribute too much to the overall error. By combining
with the previous lemma, the entrywise $\ell_{1}$ cost of all columns
containing large entries can be bounded.

######  Lemma 2.4.

Let $\Delta\in\mathbb{R}^{n\times n}$ be a random matrix where $\Delta_{i,j}$
are i.i.d. symmetric random variables with
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1$ and
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1)$ for some constant
$p\in(1,2)$. Let $\epsilon\in(0,1)$ satisfy $1/\epsilon=n^{o(1)}.$ Let
$r\geq(1/\epsilon)^{1+1/(p-1)}.$ Then, with probability at least $.999,$
$\forall S\subset[n]$ with $|S|\leq n/r,$ $\sum_{j\in
S}\|\Delta_{j}\|_{1}=O(\epsilon n^{2}).$

We say a (noise) column is good if it does not have a large entry. We can show
that, with high probability, the entry-wise $\ell_{1}$ cost of a good (noise)
column is small.

######  Lemma 2.5 (Cost of good noise columns).

Let $\Delta\in\mathbb{R}^{n}$ be a random vector where $\Delta_{i}$ are i.i.d.
symmetric random variables with $\operatorname*{{\bf{E}}}[|\Delta_{i}|]=1$ and
$\operatorname*{{\bf{E}}}[|\Delta_{i}|^{p}]=O(1)$ for some constant
$p\in(1,2)$. Let $\epsilon\in(0,1)$ satisfy $1/\epsilon=n^{o(1)}.$ If $\forall
i\in[n],|\Delta_{i}|\leq n^{1/2+1/(2p)},$ then with probability at least
$1-2^{-n^{\Theta(1)}},$ $\|\Delta\|_{1}\leq(1+\epsilon)n.$

###  2.2 Definition of Tuples and Cores

In this section, we provide some basic definitions, e.g., of a tuple, a good
tuple, the core of a tuple, and a coefficients tuple. These definitions will
be heavily used later when we analyze the correctness of our algorithm.

Before we present the definitions, we introduce a notion $R_{A^{*}}(S)$. Given
a matrix $A^{*}\in\mathbb{R}^{n_{1}\times n_{2}}$, for a set
$S\subseteq[n_{2}]$, we define

$\displaystyle R_{A^{*}}(S):=\arg\max_{P:P\subseteq
S}\left\\{\left|\det\left((A^{*})_{P}^{Q}\right)\right|\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\
|P|=|Q|=\operatorname{rank}(A^{*}_{S}),Q\subseteq[n_{1}]\right\\},$

where for a squared matrix $C$, $\det(C)$ denotes the determinant of $C$. The
above maximum is over both $P$ and $Q$ while $R_{A^{*}}(S)$ only takes the
value of the corresponding $P$.

By Cramer’s rule, if we use the columns of $A^{*}$ with index in the set
$R_{A^{*}}(S)$ to fit any column of $A^{*}$ with index in the set $S$, the
absolute value of any fitting coefficient will be at most $1$. The use of
Cramer’s rule is as follows. Consider a rank $k$ matrix
$M\in\mathbb{R}^{n\times(k+1)}$. Let $P\subseteq[k+1],Q\subseteq[n],|P|=|Q|=k$
be such that $|\det(M_{P}^{Q})|$ is maximized. Since $M$ has rank $k$, we know
$\det(M_{P}^{Q})\not=0$ and thus the columns of $M_{P}$ are independent. Let
$i\in[k+1]\setminus P$. Then the linear equation $M_{P}x=M_{i}$ is feasible
and there is a unique solution $x$. Furthermore, by Cramer’s rule
$x_{j}={\det(M^{Q}_{[k+1]\setminus\\{j\\}})}/{\det(M_{P}^{Q})}$. Since
$|\det(M_{P}^{Q})|\geq|\det(M^{Q}_{[k+1]\setminus\\{j\\}})|$, we have
$\|x\|_{\infty}\leq 1$.

Small fitting coefficients are good since they will not increase the noise by
too much. For example, suppose $A^{*}_{i}=A^{*}_{S}x$ and $\|x\|_{\infty}\leq
1$, i.e., the $i$-th column can be fit by the columns with indices in the set
$S$ and the fitting coefficients $x\in\mathbb{R}^{|S|}$ are small. If we use
the noisy columns of $A^{*}_{S}+\Delta_{S}$ to fit the noisy column
$A^{*}_{i}+\Delta_{i}$, then the fitting cost is at most
$\|(A^{*}_{S}+\Delta_{S})x-(A^{*}_{i}+\Delta_{i})\|_{1}\leq\|\Delta_{i}\|_{1}+\|\Delta_{S}x\|_{1}$.
Since $\|x\|_{\infty}\leq 1$, it is possible to give a good upper bound for
$\|\Delta_{S}x\|_{1}$.

######  Definition 2.6 (Tuple).

A $(q,t,n)-$tuple is defined to be $(S_{1},S_{2},\cdots,S_{t},i),$ where
$\forall j\in[t],S_{j}\subset[n]$ with $|S_{j}|=q.$ Let
$S=\bigcup_{j=1}^{t}S_{j}$. Then $|S|=qt,$ i.e., $S_{1},S_{2},\cdots,S_{t}$
are disjoint. Furthermore, $i\in[n]$ and $i\not\in S.$ For simplicity, we use
$(S_{[t]},i)$ to denote $(S_{1},S_{2},\cdots,S_{t},i)$.

We next provide the definition of a good tuple.

######  Definition 2.7 (Good tuple).

Given a $\operatorname{rank}$-$k$ matrix $A^{*}\in\mathbb{R}^{n\times n},$ an
$(A^{*},q,t,\alpha)$-good tuple is a $(q,t,n)$-tuple $(S_{[t]},i)$ which
satisfies

$\displaystyle|\\{j\in[t]\mid i\not\in
R_{A^{*}}(S_{j}\cup\\{i\\})\\}|\geq\alpha\cdot t.$

We need the definition of the core of a tuple.

######  Definition 2.8 (Core of a tuple).

The core of $(S_{[t]},i)$ is defined to be the set

$\displaystyle\\{j\in[t]\mid i\not\in R_{A^{*}}(S_{j}\cup\\{i\\})\\}.$

We define a coefficients tuple as follows.

######  Definition 2.9 (Coefficients tuple).

Given a $\operatorname{rank}$-$k$ matrix $A^{*}\in\mathbb{R}^{n\times n},$ let
$(S_{[t]},i)$ be an $(A^{*},q,t,\alpha)$-good tuple. Let $C$ be the core of
$(S_{[t]},i)$. A coefficients tuple corresponding to $(S_{[t]},i)$ is defined
to be $(x_{1},x_{2},\cdots,x_{t})$ where $\forall
j\in[t],x_{j}\in\mathbb{R}^{q}.$ The vector $x_{j}\in\mathbb{R}^{q}$
satisfies: $x_{j}=0$ if $j\in[t]\backslash C$, while
$A_{S_{j}}^{*}x_{j}=A_{i}^{*}$ and $\|x_{j}\|_{\infty}\leq 1$, if $j\in C$. To
guarantee the coefficients tuple is unique, we restrict each vector
$x_{j}\in\mathbb{R}^{q}$ to be one that has the minimum lexicographic order.

###  2.3 Properties of a Good Tuple and a Coefficients Tuple

Consider a good tuple $(S_{1},S_{2},\cdots,S_{t},i)$. By the definition of a
good tuple, the size of the core $C$ of the tuple is large. For each $j\in C$,
the coefficients $x_{j}$ of using $A^{*}_{S_{j}}$ to fit $A^{*}_{i}$ should
have absolute value at most $1$. Now consider the noisy setting. As discussed
in the previous section, using $A_{S_{j}}$ to fit $A_{i}$ has cost at most
$\|\Delta_{i}\|_{1}+\|\Delta_{S_{j}}x_{j}\|_{1}$. Although
$\|\Delta_{S_{j}}x_{j}\|_{1}$ has a good upper bound, it is not small enough.
To further reduce the $\ell_{1}$ fitting cost, we can now apply the averaging
argument (Lemma 2.2) over all the fitting choices corresponding to $C$.
Formally, we have the following lemma.

######  Lemma 2.10 (Good tuples imply low fitting cost).

Suppose we are given a matrix $A\in\mathbb{R}^{n\times n}$ which satisfies
$A=A^{*}+\Delta$, where $A^{*}\in\mathbb{R}^{n\times n}$ has rank $k$. Here
$\Delta\in\mathbb{R}^{n\times n}$ is a random matrix where $\Delta_{i,j}$ are
i.i.d. symmetric random variables with
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1$ and
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1)$ for some constant
$p\in(1,2)$. Let $H\subset[n]$ be defined as follows:

$\displaystyle H=\left\\{j\in[n]\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\ \exists
i\in[n],|\Delta_{i,j}|>n^{1/2+1/(2p)}\right\\}.$

Let $q,t\leq n^{o(1)}.$ Then, with probability at least
$1-2^{-n^{\Theta(1)}},$ for all $(A^{*},q,t,1/2)$-good tuples
$(S_{1},S_{2},\cdots,S_{t},i)$ which satisfy
$H\cap\left(\bigcup_{j=1}^{t}S_{j}\right)=\emptyset,$ we have

$\displaystyle\min_{y\in\mathbb{R}^{qt}}\left\|A_{\\{\bigcup_{j=1}^{t}S_{j}\\}}y-A_{i}\right\|_{1}\leq\left\|\frac{1}{|C|}\sum_{j=1}^{t}A_{S_{j}}x_{j}-A_{i}\right\|_{1}\leq\|\Delta_{i}\|_{1}+O(q^{1/p}/t^{1-1/p}n),$

where $C$ is the core of $(S_{1},S_{2},\cdots,S_{t},i)$, and
$(x_{1},x_{2},\cdots,x_{t})$ is the coefficients tuple corresponding to
$(S_{1},S_{2},\cdots,S_{t},i).$

We next show that if we choose columns randomly, it is easy to find a good
tuple.

######  Lemma 2.11.

Given a rank-$k$ matrix $A^{*}\in\mathbb{R}^{n\times n}$, let $q>10k,t>0.$ Let
$I=\\{i_{1},i_{2},\cdots,i_{qt+1}\\}$ be a subset drawn uniformly at random
from $[n]\choose qt+1$. Let $\pi:I\rightarrow I$ be a random permutation of
$qt+1$ elements. $\forall j\in[t],$ let

$\displaystyle
S_{j}=\left\\{i_{\pi((j-1)q+1)},i_{\pi((j-1)q+2)},\cdots,i_{\pi((j-1)q+q)}\right\\}.$

We use $i$ to denote $i_{\pi(qt+1)}$. With probability $\geq 1-2k/q$,
$(S_{1},S_{2},\cdots,S_{t},i)$ is an $(A^{*},q,t,1/2)-$good tuple.

Lemma 2.11 implies that if we randomly choose $S_{1},S_{2},\cdots,S_{t}$, then
with high probability, there are many choices of $i\in[n]$, such that
$(S_{1},S_{2},\cdots,S_{t},i)$ is a good tuple. Precisely, we can show the
following.

######  Lemma 2.12.

Given a rank-$k$ matrix $A^{*}\in\mathbb{R}^{n\times n}$, let $q>10k,t>0.$ Let
$I=\\{i_{1},i_{2},\cdots,i_{qt}\\}$ be a random subset uniformly drawn from
$[n]\choose qt$. Let $\pi$ be a random permutation of $qt$ elements. $\forall
j\in[t],$ we define $S_{j}$ as follows:

$\displaystyle
S_{j}=\left\\{i_{\pi((j-1)q+1)},i_{\pi((j-1)q+2)},\cdots,i_{\pi((j-1)q+q)}\right\\}.$

Then with probability at least $2k/q$,

$\displaystyle\left|\left\\{i\in[n]\setminus I\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\
(S_{1},S_{2},\cdots,S_{t},i)\mathrm{\leavevmode\nobreak\
is\leavevmode\nobreak\ an\leavevmode\nobreak\
}(A^{*},q,t,1/2)\mathrm{-good\leavevmode\nobreak\ tuple\leavevmode\nobreak\
}\right\\}\right|\geq(1-4k/q)(n-qt).$

###  2.4 Main Result

Now we are able to put all ingredients together to prove our main theorem,
Theorem 2.13.

######  Theorem 2.13 (Formal version of Theorem 1.1).

Suppose we are given a matrix $A=A^{*}+\Delta\in\mathbb{R}^{n\times n}$, where
$\operatorname{rank}(A^{*})=k$ for $k=n^{o(1)}$, and $\Delta$ is a random
matrix for which the $\Delta_{i,j}$ are i.i.d. symmetric random variables with
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1$ and
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1)$ for some constant
$p\in(1,2)$. Let $\epsilon\in(0,1/2)$ satisfy $1/\epsilon=n^{o(1)}.$ There is
an $\widetilde{O}(n^{2}+n\operatorname{poly}(k/\epsilon))$ time algorithm
(Algorithm 1) which can output a subset $S\in[n]$ with
$|S|\leq\operatorname{poly}(k/\epsilon)+O(k\log n)$ for which

$\displaystyle\min_{X\in\mathbb{R}^{|S|\times
n}}\|A_{S}X-A\|_{1}\leq(1+\epsilon)\|\Delta\|_{1},$

holds with probability at least $99/100$.

###### Proof.

We discussed the running time at the beginning of Section 2. Next, we turn to
correctness. Let $q=\Omega\left(\frac{k(k\log
k)^{1+\frac{1}{p-1}}}{\epsilon^{1+\frac{1}{p-1}}}\right),$
$t=\frac{q^{\frac{1}{p-1}}}{\epsilon^{1+\frac{1}{p-1}}}.$ Let $r=\Theta(q/k).$
Let

$\displaystyle
I_{1}=\left\\{i_{1}^{(1)},i_{2}^{(1)},\cdots,i_{qt}^{(1)}\right\\},I_{2}=\left\\{i_{1}^{(2)},i_{2}^{(2)},\cdots,i_{qt}^{(2)}\right\\},\cdots,I_{r}=\left\\{i_{1}^{(r)},i_{2}^{(r)},\cdots,i_{qt}^{(r)}\right\\},$

be $r$ independent subsets drawn uniformly at random from $[n]\choose qt$. Let
$I=\bigcup_{s\in[r]}I_{s}$, which is the same as that in Algorithm 1. Let
$\pi_{1},\pi_{2},\cdots,\pi_{r}$ be $r$ independent random permutations of
$qt$ elements. Due to Lemma 2.12 and a Chernoff bound, with probability at
least $.999,$ $\exists s\in[r]$,

$\displaystyle\left|\left\\{i\in[n]\setminus I_{s}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\
(S_{1},S_{2},\cdots,S_{t},i)\text{\leavevmode\nobreak\ is an
$(A^{*},q,t,1/2)-$good tuple\leavevmode\nobreak\
}\right\\}\right|\geq(1-4k/q)(n-qt)$

where

$\displaystyle
S_{j}=\left\\{i^{(s)}_{\pi_{s}((j-1)q+1)},i^{(s)}_{\pi_{s}((j-1)q+2)},\cdots,i^{(s)}_{\pi_{s}((j-1)q+q)}\right\\},\forall
j\in[t].$

Let set $H\subset[n]$ be defined as follows:

$\displaystyle H=\\{j\in[n]\mid\exists
i\in[n],|\Delta_{i,j}|>n^{1/2+1/(2p)}\\}.$

Then due to Lemma 2.3, with probability at least $0.999,$ $|H|\leq
O(n^{1-(p-1)/2}).$ Thus, for $j\in[r],$ the probability that $H\cap
I_{j}\not=\emptyset$ is at most $O(qt\cdot
n^{1-(p-1)/2}/(n-qt))=1/n^{\Omega(1)}.$ By taking a union bound over all
$j\in[r],$ with probability at least $1-1/n^{\Omega(1)},$ $\forall
j\in[r],I_{j}\cap H=\emptyset.$ Thus, we can condition on $I_{s}\cap
H=\emptyset.$ Due to Lemma 2.10 and $q^{1/p}/t^{1-1/p}=\epsilon,$

$\displaystyle\left|\left\\{i\in[n]\setminus I_{s}\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\
\min_{y\in\mathbb{R}^{qt}}\|A_{I_{s}}y-A_{i}\|_{1}\leq\|\Delta_{i}\|_{1}+O(\epsilon
n)\right\\}\right|\geq(1-4k/q)(n-qt).$

Due to Lemma 2.5 and a union bound over all $i\in[n]\setminus H$, with
probability at least $.999,$ $\forall i\not\in
H,\|\Delta_{i}\|\leq(1+\epsilon)n$. Thus,

$\displaystyle\left|\left\\{i\in[n]\setminus I_{s}\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\
\min_{y\in\mathbb{R}^{qt}}\|A_{I_{s}}y-A_{i}\|_{1}\leq(1+O(\epsilon))n\right\\}\right|\geq(1-4k/q)(n-qt)-|H|.$

Let

$\displaystyle T^{\prime}=[n]\setminus\left\\{i\in[n]\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\
\min_{y\in\mathbb{R}^{qt}}\|A_{I_{s}}y-A_{i}\|_{1}\leq(1+O(\epsilon))n\right\\}.$

Then $|T^{\prime}|\leq O(kn/q+n^{1-(p-1)/2})=O(kn/q)=O((\epsilon/(k\log
k))^{1+1/(p-1)}n).$ By our selection of $T$ in algorithm 1, $T^{\prime}$
should be a subset of $T$. Due to Lemma 2.4, with probability at least $.999,$
$\|\Delta_{T}\|_{1}\leq O(\epsilon n^{2}/(k\log k))$. By our second subroutine
mentioned at the beginning of Section 2 it can find a set $Q\subset[n]$ with
$|Q|=O(k\log n)$ such that
$min_{X\in\mathbb{R}^{|Q|\times|T|}}\|A_{Q}X-A_{T}\|_{1}\leq O(k\log
k)\|\Delta_{T}\|_{1}\leq O(\epsilon n^{2}).$ Thus, we have
$\min_{X\in\mathbb{R}^{(|Q|+q\cdot t\cdot r)\times n}}\|A_{(Q\cup
I)}X-A\|_{1}\leq\min_{X_{1}\in\mathbb{R}^{(q\cdot t\cdot r)\times
n}}\|A_{I}X_{1}-A_{[n]\setminus T}\|_{1}+\min_{X_{2}\in\mathbb{R}^{|Q|\times
n}}\|A_{Q}X_{2}-A_{T}\|_{1}\leq(1+O(\epsilon))n^{2}.$ Due to Lemma 2.1, with
probability at least $.999,$ $\|\Delta\|_{1}\geq(1-\epsilon)n^{2},$ and thus
$\min_{X\in\mathbb{R}^{(|Q|+q\cdot t\cdot r)\times n}}\|A_{(Q\cup
I)}X-A\|_{1}\leq(1+O(\epsilon))\|\Delta\|_{1}.$

∎

##  3 Experiments

The take-home message from our theoretical analysis is that although the noise
distribution may be heavy-tailed, if the $p$-th $(p>1)$ moment of the
distribution exists, averaging the noise may reduce the noise. In the spirit
of averaging, we found that taking a median works a bit better in practice.
Inspired by our theoretical analysis, we propose a simple heuristic algorithm
(Algorithm 2) which can output a rank-$k$ solution. We tested Algorithm 2 on
both synthetic and real datasets.

1:procedure L1NoisyLowRankApproxHeu($A\in\mathbb{R}^{n\times d},k\geq 1$)

2: Sample a set $I=\\{i_{1},i_{2},\cdots,i_{sk}\\}$ from ${[n]\choose sk}$
uniformly at random.

3: Compute $B\in\mathbb{R}^{n\times k}$ s.t., for $t\in[n],q\in[k],$
$B_{t,q}=\mathrm{median}(A_{t,i_{s(q-1)+1}},\cdots,A_{t,i_{sq}})$.

4: Solve $\min_{X\in\mathbb{R}^{k\times d}}\|BX-A\|_{1}$ and let the solution
be $X^{*}$. Output $BX^{*}$.

5:end procedure

Algorithm 2 Median Heuristic

Datasets. For each rank-$k$ experiment, we chose a high rank matrix
$\widehat{A}\in\mathbb{R}^{n\times d}$, applied top-$k$ SVD to $\widehat{A}$
and obtained a rank-$k$ matrix $A^{*}$ as our ground truth matrix. For our
synthetic data experiments, the matrix $\widehat{A}\in\mathbb{R}^{500\times
500}$ was generated at random, where each entry was drawn uniformly from
$\\{0,1,\cdots,9\\}$. For real datasets, we chose
isolet222https://archive.ics.uci.edu/ml/datasets/isolet $(617\times 1559)$ or
mfeat333https://archive.ics.uci.edu/ml/datasets/Multiple+Features $(651\times
2000)$ as $\widehat{A}$ [AN07]. We tested two different noise distributions.
One distribution is the standard Lévy $1.1$-stable distribution [Man60].
Another distribution is constructed from the standard Cauchy distribution,
i.e., to draw a sample from the constructed distribution, we draw a sample
from the Cauchy distribution, keep the sign unchanged, and take the
$\frac{1}{1.1}$-th power of the absolute value. Notice that both distributions
have bounded $1.1$-th moment, but do not have a $p$-th moment for any $p>1.1$.
To construct the noise matrix $\Delta\in\mathbb{R}^{n\times d}$, we drew a
matrix $\widehat{\Delta}$ where each entry is an i.i.d. sample from one of the
two noise distributions, and then scaled the noise:
$\Delta=\widehat{\Delta}\cdot\frac{\|A^{*}\|_{1}}{20\cdot n\cdot d}$. We set
$A=A^{*}+\Delta$ as the input.

Methodologies. We compare Algorithm 2 with SVD, $\operatorname{poly}(k,\log
n)$-approximate entrywise $\ell_{1}$ low rank approximation [SWZ17], and
uniform $k$-column subset sampling [CGK+17]444We chose to compare with [SWZ17,
CGK+17] due to their theoretical guarantees. Though the uniform $k$-column
subset sampling described in the experiments of [CGK+17] is a heuristic
algorithm, it is inspired by their theoretical algorithm.. For Algorithm 2, we
set $s=\min(50,\lfloor n/k\rfloor)$. For all of algorithms we repeated the
experiment the same number of times and compared the best solution obtained by
each algorithm. We report the approximation ratio $\|B-A\|_{1}/\|\Delta\|_{1}$
for each algorithm, where $B\in\mathbb{R}^{n\times d}$ is the output rank-$k$
matrix. The results are shown in Figure 1. As shown in the figure, Algorithm 2
outperformed all of the other algorithms.

synthetic | isolet | mfeat
---|---|---
Figure 1: Empirical results. The noise distributions of the experiments in the
first row are from a $1.1$-stable distribution. The noise distributions
corresponding to the second row are the $1.1$-th root of a Cauchy
distribution. The blue, red, orange and yellow bar denote SVD, the entrywise
$\ell_{1}$-norm low rank algorithm in [SWZ17], the uniform $k$-column subset
sampling algorithm in [CGK+17], and Algorithm 2 respectively.

#### Acknowledgments.

David P. Woodruff was supported in part by Office of Naval Research (ONR)
grant N00014- 18-1-2562. Part of this work was done while he was visiting the
Simons Institute for the Theory of Computing. Peilin Zhong is supported in
part by NSF grants (CCF-1703925, CCF-1421161, CCF-1714818, CCF-1617955 and
CCF-1740833), Simons Foundation (#491119 to Alexandr Andoni), Google Research
Award and a Google Ph.D. fellowship. Part of this work was done while Zhao
Song and Peilin Zhong were interns at IBM Research - Almaden and while Zhao
Song was visiting the Simons Institute for the Theory of Computing.

## References

  * [AN07] Arthur Asuncion and David Newman.  Uci machine learning repository, 2007.
  * [BBB+19] Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, and David P. Woodruff.  A PTAS for $\ell_{p}$-low rank approximation.  In SODA, 2019.
  * [BD13] J. Paul Brooks and José H. Dulá.  The $\ell_{1}$-norm best-fit hyperplane problem.  Appl. Math. Lett., 26(1):51–55, 2013.
  * [BDB13] J. Paul Brooks, José H. Dulá, and Edward L Boone.  A pure $\ell_{1}$-norm principal component analysis.  Computational statistics & data analysis, 61:83–98, 2013.
  * [BDN15] Jean Bourgain, Sjoerd Dirksen, and Jelani Nelson.  Toward a unified theory of sparse dimensionality reduction in euclidean space.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 499–508, 2015.
  * [BJ12] J. Paul Brooks and Sapan Jot.  Pcal1: An implementation in r of three methods for $\ell_{1}$-norm principal component analysis.  Optimization Online preprint, 2012.
  * [CGK+17] Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David P Woodruff.  Algorithms for $\ell_{p}$ low rank approximation.  In ICML. arXiv preprint arXiv:1705.06730, 2017.
  * [CLMW11] Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright.  Robust principal component analysis?  Journal of the ACM (JACM), 58(3):11, 2011.
  * [Coh16] Michael B. Cohen.  Nearly tight oblivious subspace embeddings by trace inequalities.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, USA, January 10-12, 2016, pages 278–287, 2016.
  * [CW13] Kenneth L. Clarkson and David P. Woodruff.  Low rank approximation and regression in input sparsity time.  In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 81–90. https://arxiv.org/pdf/1207.6365, 2013.
  * [DDH+09] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W Mahoney.  Sampling algorithms and coresets for $\ell_{p}$ regression.  SIAM Journal on Computing, 38(5):2060–2078, 2009.
  * [GV15] Nicolas Gillis and Stephen A Vavasis.  On the complexity of robust pca and $\ell_{1}$-norm low-rank matrix approximation.  arXiv preprint arXiv:1509.09236, 2015.
  * [Hub64] Peter J. Huber.  Robust estimation of a location parameter.  The Annals of Mathematical Statistics, 35(1):73–101, 1964.
  * [KK03] Qifa Ke and Takeo Kanade.  Robust subspace computation using $\ell_{1}$ norm.  Technical Report CMU-CS-03-172, Carnegie Mellon University, Pittsburgh, PA., 2003.
  * [KK05] Qifa Ke and Takeo Kanade.  Robust $\ell_{1}$ norm factorization in the presence of outliers and missing data by alternative convex programming.  In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, pages 739–746. IEEE, 2005.
  * [KLC+15] Eunwoo Kim, Minsik Lee, Chong-Ho Choi, Nojun Kwak, and Songhwai Oh.  Efficient-norm-based low-rank matrix approximations for large-scale problems using alternating rectified gradient method.  IEEE transactions on neural networks and learning systems, 26(2):237–251, 2015.
  * [Kwa08] Nojun Kwak.  Principal component analysis based on $\ell_{1}$-norm maximization.  IEEE transactions on pattern analysis and machine intelligence, 30(9):1672–1680, 2008.
  * [Lat97] Rafal Latala.  Estimation of moments of sums of independent real random variables.  The Annals of Probability, pages 1502–1513, 1997.
  * [Man60] Benoit Mandelbrot.  The pareto-levy law and the distribution of income.  International Economic Review, 1(2):79–106, 1960.
  * [Mau03] Andreas Maurer.  A bound on the deviation probability for sums of non-negative random variables.  J. Inequalities in Pure and Applied Mathematics, 4(1):15, 2003.
  * [MKCP16] P. P. Markopoulos, S. Kundu, S. Chamadia, and D. A. Pados.  Efficient $\ell_{1}$-Norm Principal-Component Analysis via Bit Flipping.  ArXiv e-prints, 2016.
  * [MKP13] Panos P. Markopoulos, George N. Karystinos, and Dimitrios A. Pados.  Some options for $\ell_{1}$-subspace signal processing.  In ISWCS 2013, The Tenth International Symposium on Wireless Communication Systems, Ilmenau, TU Ilmenau, Germany, August 27-30, 2013, pages 1–5, 2013.
  * [MKP14] Panos P. Markopoulos, George N. Karystinos, and Dimitrios A. Pados.  Optimal algorithms for $\ell_{1}$-subspace signal processing.  IEEE Trans. Signal Processing, 62(19):5046–5058, 2014.
  * [MM13] Xiangrui Meng and Michael W Mahoney.  Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 91–100. ACM, https://arxiv.org/pdf/1210.3135, 2013\.
  * [MXZZ13] Deyu Meng, Zongben Xu, Lei Zhang, and Ji Zhao.  A cyclic weighted median method for $\ell_{1}$ low-rank matrix factorization with missing entries.  In AAAI, volume 4, page 6, 2013.
  * [NN13] Jelani Nelson and Huy L Nguyên.  Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 117–126. IEEE, https://arxiv.org/pdf/1211.1002, 2013\.
  * [PK16] Young Woong Park and Diego Klabjan.  Iteratively reweighted least squares algorithms for $\ell_{1}$-norm principal component analysis.  arXiv preprint arXiv:1609.02997, 2016.
  * [Sar06] Tamás Sarlós.  Improved approximation algorithms for large matrices via random projections.  In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 143–152, 2006.
  * [SWZ17] Zhao Song, David P Woodruff, and Peilin Zhong.  Low rank approximation with entrywise $\ell_{1}$-norm error.  In Proceedings of the 49th Annual Symposium on the Theory of Computing (STOC). ACM, https://arxiv.org/pdf/1611.00898, 2017.
  * [Woo14] David P. Woodruff.  Sketching as a tool for numerical linear algebra.  Foundations and Trends in Theoretical Computer Science, 10(1-2):1–157, 2014.
  * [XCS10] Huan Xu, Constantine Caramanis, and Sujay Sanghavi.  Robust pca via outlier pursuit.  In Advances in Neural Information Processing Systems, pages 2496–2504, 2010.
  * [ZLS+12] Yinqiang Zheng, Guangcan Liu, Shigeki Sugimoto, Shuicheng Yan, and Masatoshi Okutomi.  Practical low-rank matrix approximation under robust $\ell_{1}$-norm.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, June 16-21, 2012, pages 1410–1417, 2012.

##  Appendix A Missing Proofs in Section 2

###  A.1 Proof of Lemma 2.1

###### Proof.

Let $Z\in\mathbb{R}^{n\times n}$ be a random matrix. For each $i,j\in[n],$
define random variable $Z_{i,j}$ as

$\displaystyle
Z_{i,j}=\left\\{\begin{array}[]{ll}|\Delta_{i,j}|,&\text{\leavevmode\nobreak\
if\leavevmode\nobreak\ }|\Delta_{i,j}|\leq n;\\\
n,&\mathrm{otherwise.}\end{array}\right.$

For $i,j\in[n],$ by Markov’s inequality, we have

$\displaystyle\Pr[|\Delta_{i,j}|\geq n]=\Pr[|\Delta_{i,j}|^{p}\geq
n^{p}]\leq\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]/n^{p}=O(1/n^{p}).$ (2)

Notice that

$\displaystyle\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=\int_{0}^{n}x^{p}f(x)\mathrm{d}x+\int_{n}^{\infty}x^{p}f(x)\mathrm{d}x=O(1)$

where $f(x)$ is the probability density function of $|\Delta_{i,j}|.$ Thus we
have

$\displaystyle\int_{n}^{\infty}xf(x)\mathrm{d}x\leq\int_{n}^{\infty}x^{p}/n^{p-1}\cdot
f(x)\mathrm{d}x=O(1/n^{p-1}).$

Because $\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1,$ we have

$\displaystyle\int_{0}^{\infty}xf(x)\mathrm{d}x=\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]-\int_{n}^{\infty}xf(x)\mathrm{d}x\geq
1-O(1/n^{p-1}).$ (3)

By Equation (3), we have

$\displaystyle\operatorname*{{\bf{E}}}[Z_{i,j}]=\int_{0}^{n}xf(x)dx+n\cdot\Pr[|\Delta_{i,j}|\geq
n]\geq\int_{0}^{n}xf(x)dx\geq 1-O(1/n^{p-1}).$

By Equation (2) and $E[|\Delta_{i,j}|^{p}]\leq O(1)$, we have

$\displaystyle\operatorname*{{\bf{E}}}[Z_{i,j}^{2}]=\int_{0}^{n}x^{2}f(x)\mathrm{d}x+n^{2}\Pr[|\Delta_{i,j}|\geq
n]\leq O(n^{2-p})+O(n^{2-p})=O(n^{2-p}).$

By the inequality of [Mau03],

$\displaystyle\Pr[\operatorname*{{\bf{E}}}[\|Z\|_{1}]-\|Z\|_{1}\geq\epsilon\operatorname*{{\bf{E}}}[\|Z\|_{1}]/2]$
$\displaystyle\leq\exp\left(\frac{-\epsilon^{2}\operatorname*{{\bf{E}}}[\|Z\|_{1}]^{2}/4}{2\sum_{i,j}\operatorname*{{\bf{E}}}[Z_{i,j}^{2}]}\right)$
$\displaystyle\leq\exp\left(\frac{-\epsilon^{2}(n^{2}-O(n^{3-p}))^{2}/4}{2n^{2}\cdot
O(n^{2-p})}\right)$ $\displaystyle\leq e^{-\Theta(n)}$

Thus with probability at least $1-e^{-\Theta(n)},$
$\|Z\|_{1}\geq(1-\epsilon/2)\operatorname*{{\bf{E}}}[\|Z\|_{1}]\geq(1-\epsilon)n^{2}$
where the last inequality follows by $\operatorname*{{\bf{E}}}[\|Z\|_{1}\geq
n^{2}-O(n^{3-p})]$ and $1/\epsilon=n^{o(1)}.$ Since
$\|\Delta\|_{1}\geq\|Z\|_{1},$ we complete the proof. ∎

###  A.2 Proof of Lemma 2.2

###### Proof.

Let $Z\in\mathbb{R}^{n\times t}$ be a random matrix where $Z_{i,j}$ are i.i.d.
random variables with probability density function:

$\displaystyle g(x)=\left\\{\begin{array}[]{ll}f(x)/\Pr[|\Delta_{1,1}|\leq
n^{1/2+1/(2p)}],&\text{\leavevmode\nobreak\ if\leavevmode\nobreak\ }|x|\leq
n^{1/2+1/(2p)};\\\ 0,&\mathrm{\leavevmode\nobreak\
otherwise.}\end{array}\right.$

where $f(x)$ is the probability density function of $\Delta_{1,1}$. (Note that
in the above equation, $\Pr[|\Delta_{1,1}|\leq n^{1/2+1/(2p)}]>0$.) Now, we
have $\forall a\geq 0$,

$\displaystyle\Pr\left[\left\|\sum_{j=1}^{t}\alpha_{j}\Delta_{j}\right\|_{1}\leq
a\leavevmode\nobreak\ \bigg{|}\leavevmode\nobreak\ \forall
i\in[n],j\in[t],|\Delta_{i,j}|\leq
n^{1/2+1/(2p)}\right]=\Pr\left[\left\|\sum_{j=1}^{t}\alpha_{j}Z_{j}\right\|_{1}\leq
a\right].$

Now we look at the $i$-th row of $\sum_{j=1}^{t}\alpha_{j}Z_{j}.$ We have

$\displaystyle\operatorname*{{\bf{E}}}\left[\left|\sum_{j=1}^{t}\alpha_{j}Z_{i,j}\right|\right]=$
$\displaystyle\leavevmode\nobreak\
\left(\operatorname*{{\bf{E}}}\left[\left|\sum_{j=1}^{t}\alpha_{j}Z_{i,j}\right|\right]^{p}\right)^{1/p}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\bf{E}}}\left[\left|\sum_{j=1}^{t}\alpha_{j}Z_{i,j}\right|^{p}\right]^{1/p}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\bf{E}}}\left[\left(\left(\sum_{j=1}^{t}\alpha_{j}^{2}Z_{i,j}^{2}\right)^{1/2}\right)^{p}\right]^{1/p}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\bf{E}}}\left[\sum_{j=1}^{t}|\alpha_{j}Z_{i,j}|^{p}\right]^{1/p}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\left(\sum_{j=1}^{t}\operatorname*{{\bf{E}}}[|\alpha_{j}Z_{i,j}|^{p}]\right)^{1/p}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\left(\sum_{j=1}^{t}\operatorname*{{\bf{E}}}[|Z_{i,j}|^{p}]\right)^{1/p}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ O(t^{1/p}),$ (4)

where the first inequality follows by Jensen’s inequality, the second
inequality follows by Remark 3 of [Lat97], the third inequality follows by
$\|x\|_{2}\leq\|x\|_{p}$ for $p<2$, the fourth inequality follows by
$|\alpha_{j}|\leq 1$, the fifth inequality follows by
$\operatorname*{{\bf{E}}}[|Z_{i,j}|^{p}]=\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}\mid|\Delta_{1,1}|\leq
n^{1/2+1/(2p)}]\leq\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1).$ For the
second moment, we have

$\displaystyle\operatorname*{{\bf{E}}}\left[\left|\sum_{j=1}^{t}\alpha_{j}Z_{i,j}\right|^{2}\right]$
$\displaystyle=\sum_{j=1}^{t}\operatorname*{{\bf{E}}}\left[\alpha_{j}^{2}Z_{i,j}^{2}\right]+\sum_{j\not=k}\operatorname*{{\bf{E}}}[\alpha_{j}\alpha_{k}Z_{i,j}Z_{i,k}]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sum_{j=1}^{t}\alpha_{j}^{2}\operatorname*{{\bf{E}}}\left[Z_{i,j}^{2}\right]+\sum_{j\not=k}\alpha_{j}\alpha_{k}\operatorname*{{\bf{E}}}[Z_{i,j}]\operatorname*{{\bf{E}}}[Z_{i,k}]$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sum_{j=1}^{t}\operatorname*{{\bf{E}}}\left[Z_{i,j}^{2}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ t\cdot
2\int_{0}^{n^{1/2+1/(2p)}}x^{2}f(x)/\Pr\left[|\Delta_{i,j}|\leq
n^{1/2+1/(2p)}\right]\mathrm{d}x$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ 2t/\Pr\left[|\Delta_{i,j}|\leq
n^{1/2+1/(2p)}\right]\cdot(n^{1/2+1/(2p)})^{2-p}\int_{0}^{n^{1/2+1/(2p)}}x^{p}f(x)\mathrm{d}x$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ O(tn^{2-p}),$ (5)

where the second inequality follows by independence of $Z_{i,j}$ and
$Z_{i,k}.$ The first inequality follows by $|\alpha_{j}|\leq 1$ and
$\operatorname*{{\bf{E}}}[Z_{i,j}]=\operatorname*{{\bf{E}}}[Z_{i,k}]=0.$ The
third equality follows by the probability density function of $Z_{i,j}.$ The
second inequality follows by $x^{2-p}\leq(n^{1/2+1/(2p)})^{2-p}$ when $0\leq
x\leq n^{1/2+1/(2p)}.$ The last inequality follows by
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1),p>1$ and
$\Pr[|\Delta_{i,j}|\leq n^{1/2+1/(2p)}]\geq
1-\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]/(n^{1/2+1/(2p)})^{p}=1-O(1/n^{p/2+1/2})\geq
1/2.$

For $i\in[n],$ define $X_{i}=|\sum_{j=1}^{t}\alpha_{j}Z_{i,j}|.$ Then, by
Bernstein’s inequality

$\displaystyle\Pr\left[\left\|\sum_{j=1}^{t}\alpha_{j}Z_{j}\right\|_{1}-\operatorname*{{\bf{E}}}\left[\left\|\sum_{j=1}^{t}\alpha_{j}Z_{j}\right\|_{1}\right]\geq
0.5t^{1/p}n\right]$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\Pr\left[\sum_{i=1}^{n}X_{i}-\operatorname*{{\bf{E}}}\left[\sum_{i=1}^{n}X_{i}\right]\geq
0.5t^{1/p}n\right]$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\exp\left(-\frac{0.5\cdot
0.5^{2}t^{2/p}n^{2}}{\sum_{i=1}^{n}\operatorname*{{\bf{E}}}[X_{i}^{2}]+\frac{1}{3}n^{1/2+1/(2p)}\cdot
0.5t^{1/p}n}\right)$ $\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
e^{-n^{\Theta(1)}}.$

The last inequality follows by Equation (A.2). According to Equation (A.2),
with probability at least $1-e^{-n^{\Theta(1)}},$

$\displaystyle\left\|\sum_{j=1}^{t}\alpha_{j}Z_{j}\right\|_{1}\leq\operatorname*{{\bf{E}}}\left[\left\|\sum_{j=1}^{t}\alpha_{j}Z_{j}\right\|_{1}\right]+0.5t^{1/p}n\leq
O(t^{1/p}n).$

∎

###  A.3 Proof of Lemma 2.3

###### Proof.

For $i,j\in[n],$ we have

$\displaystyle\Pr\left[|\Delta_{i,j}|>n^{1/2+1/(2p)}\right]=\Pr\left[|\Delta_{i,j}|^{p}>n^{p/2+1/2}\right]\leq\operatorname*{{\bf{E}}}\left[|\Delta_{i,j}|^{p}\right]/n^{p/2+1/2}\leq
O(1/n^{p/2+1/2}).$

For column $j$, by taking a union bound,

$\displaystyle\Pr[j\in H]=\Pr\left[\exists
i\in[n],|\Delta_{i,j}|>n^{1/2+1/(2p)}\right]\leq O(1/n^{p/2-1/2}).$

Thus, $\operatorname*{{\bf{E}}}[|H|]\leq O(n^{1-(p-1)/2}).$ By applying
Markov’s inequality, we complete the proof. ∎

###  A.4 Proof of Lemma 2.4

###### Proof.

For $l\in\mathbb{N}_{\geq 0},$ define
$G_{l}=\\{j\mid\|\Delta_{j}\|_{1}\in(n\cdot 2^{l},n\cdot 2^{l+1}]\\}.$ We have

$\displaystyle\operatorname*{{\bf{E}}}[|G_{l}|]\leq$
$\displaystyle\leavevmode\nobreak\
\sum_{j=1}^{n}\Pr\left[\|\Delta_{j}\|_{1}\geq n\cdot 2^{l}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
n\Pr\left[\|\Delta_{1}\|_{1}\geq n\cdot 2^{l}\right]$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ n\Pr\left[n^{1-1/p}\|\Delta_{1}\|_{p}\geq
n\cdot 2^{l}\right]$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
n\Pr\left[n^{p-1}\|\Delta_{1}\|_{p}^{p}\geq n^{p}\cdot 2^{lp}\right]$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
n\operatorname*{{\bf{E}}}\left[n^{p-1}\|\Delta_{1}\|_{p}^{p}\right]/(n^{p}\cdot
2^{lp})$ $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ O(n/2^{lp}).$

The first inequality follows by the definition of $G_{l}$. The second
inequality follows since $\forall x\in\mathbb{R}^{n},\|x\|_{1}\leq
n^{1-1/p}\|x\|_{p}.$ The third inequality follows by Markov’s inequality. The
last inequality follows since $\forall
i,j\in[n],\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1).$

Let $l^{*}\in\mathbb{N}_{\geq 0}$ satisfy $2^{l^{*}}<\epsilon r$ and
$2^{l^{*}+1}\geq\epsilon r.$ We have

$\displaystyle\operatorname*{{\bf{E}}}\left[\sum_{j:\|\Delta_{j}\|_{1}\geq
n2^{l^{*}}}\|\Delta_{j}\|_{1}\right]$
$\displaystyle\leq\operatorname*{{\bf{E}}}\left[\sum_{l=l^{*}}^{\infty}|G_{l}|\cdot
n2^{l+1}\right]=\sum_{l=l^{*}}^{\infty}\operatorname*{{\bf{E}}}[|G_{l}|]\cdot
n2^{l+1}$ $\displaystyle\leq\sum_{l=l^{*}}^{\infty}O(n/2^{lp})\cdot
n2^{l+1}=\sum_{l=l^{*}}^{\infty}O(n^{2}/2^{l(p-1)})$
$\displaystyle=O(n^{2}/2^{l^{*}(p-1)})=O(n^{2}/(\epsilon r)^{p-1})$
$\displaystyle=O(\epsilon n^{2}).$

By Markov’s inequality, with probability at least $.999,$
$\sum_{j:\|\Delta_{j}\|_{1}\geq n2^{l^{*}}}\|\Delta_{j}\|_{1}\leq O(\epsilon
n^{2}).$ Conditioned on $\sum_{j:\|\Delta_{j}\|_{1}\geq
n2^{l^{*}}}\|\Delta_{j}\|_{1}\leq O(\epsilon n^{2}),$ for any $S\subset[n]$
with $|S|\leq n/r,$ we have

$\displaystyle\sum_{j\in S}\|\Delta_{j}\|_{1}\leq|S|\cdot
n2^{l^{*}}+\sum_{j:\|\Delta_{j}\|_{1}\geq
n2^{l^{*}}}\|\Delta_{j}\|_{1}\leq\epsilon n^{2}+O(\epsilon n^{2})=O(\epsilon
n^{2}).$

The second inequality follows because $|S|\leq n/r,2^{l^{*}}\leq\epsilon r$
and $\sum_{j:\|\Delta_{j}\|_{1}\geq n2^{l^{*}}}\|\Delta_{j}\|_{1}\leq
O(\epsilon n^{2}).$ ∎

###  A.5 Proof of Lemma 2.5

###### Proof.

Let $M=n^{1/2+1/(2p)}.$ Let $Z\in\mathbb{R}^{n}$ be a random vector where
$Z_{i}$ are i.i.d. random variables with probability density function

$\displaystyle g(x)=\left\\{\begin{array}[]{ll}f(x)/\Pr[|\Delta_{1}|\leq
M]&\text{\leavevmode\nobreak\ if\leavevmode\nobreak\ }0\leq x\leq M;\\\
0&\text{\leavevmode\nobreak\ otherwise.}\end{array}\right.$

where $f(x)$ is the probability density function of $|\Delta_{1}|.$ Then
$\forall a>0$

$\displaystyle\Pr\left[\|\Delta\|_{1}\leq a\mid\forall
i\in[n],|\Delta_{i}|\leq M\right]=\Pr\left[\|Z\|_{1}\leq a\right].$

For $i\in[n],$ because $\operatorname*{{\bf{E}}}[|\Delta_{i}|]=1,$ it holds
that $\operatorname*{{\bf{E}}}[Z_{i}]\leq 1.$ We have
$\operatorname*{{\bf{E}}}[\sum_{i=1}^{n}Z_{i}]\leq n.$ For the second moment,
we have

$\displaystyle\operatorname*{{\bf{E}}}[Z_{i}^{2}]$
$\displaystyle=\int_{0}^{M}x^{2}f(x)/\Pr[|\Delta_{1}|\leq M]\mathrm{d}x$
$\displaystyle\leq M^{2-p}/\Pr[|\Delta_{1}|\leq
M]\int_{0}^{M}x^{p}f(x)\mathrm{d}x$ $\displaystyle\leq O(M^{2-p})$
$\displaystyle\leq O(n^{2-p})$

where the second inequality follows by
$\operatorname*{{\bf{E}}}[|\Delta_{1}|^{p}]=O(1),$ and $\Pr[|\Delta_{1}|\leq
M]\geq 1-\operatorname*{{\bf{E}}}[|\Delta_{1}|^{p}]/M^{p}\geq 1/2.$

Then by Bernstein’s inequality, we have

$\displaystyle\Pr\left[\sum_{i=1}^{n}Z_{i}-E\left[\sum_{i=1}^{n}Z_{i}\right]\geq\epsilon
n\right]$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\exp\left(\frac{-0.5\epsilon^{2}n^{2}}{\sum_{i=1}^{n}\operatorname*{{\bf{E}}}[Z_{i}^{2}]+\frac{1}{3}M\cdot\epsilon
n}\right)$ $\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
e^{-n^{\Theta(1)}}.$

Thus,

$\displaystyle\Pr\left[\|\Delta\|_{1}\leq(1+\epsilon)n\mid\forall
i\in[n],|\Delta_{i}|\leq
M\right]=\Pr\left[\|Z\|_{1}\leq(1+\epsilon)n\right]\geq 1-e^{-n^{\Theta(1)}}.$

∎

###  A.6 Proof of Lemma 2.10

###### Proof.

Recall that $(S_{1},S_{2},\cdots,S_{t},i)$ is equivalent to $(S_{[t]},i)$. Let
$(S_{[t]},i)$ be an $(A^{*},q,t,1/2)$-good tuple which satisfies
$H\cap\left(\bigcup_{j=1}^{t}S_{j}\right)=\emptyset.$ Let $C$ be the core of
$(S_{[t]},i).$ Let $(x_{1},x_{2},\cdots,x_{t})$ be the coefficients tuple
corresponding to $(S_{[t]},i).$ Then we have that

$\displaystyle\left\|\frac{1}{|C|}\sum_{j=1}^{t}A_{S_{j}}x_{j}-A_{i}\right\|_{1}$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\left\|\frac{1}{|C|}\sum_{j=1}^{t}\left(A^{*}_{S_{j}}+\Delta_{S_{j}}\right)x_{j}-(A^{*}_{i}+\Delta_{i})\right\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\left\|\frac{1}{|C|}\sum_{j=1}^{t}A^{*}_{S_{j}}x_{j}-A^{*}_{i}\right\|_{1}+\|\Delta_{i}\|_{1}+\frac{1}{|C|}\left\|\sum_{j=1}^{t}\Delta_{S_{j}}x_{j}\right\|_{1}$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\|\Delta_{i}\|_{1}+\frac{1}{|C|}\left\|\sum_{j=1}^{t}\Delta_{S_{j}}x_{j}\right\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\|\Delta_{i}\|_{1}+\frac{2}{t}\left\|\sum_{j=1}^{t}\Delta_{S_{j}}x_{j}\right\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\|\Delta_{i}\|_{1}+O\left(\frac{1}{t}\cdot(qt)^{1/p}n\right)$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\|\Delta_{i}\|_{1}+O\left(q^{1/p}/t^{1-1/p}n\right)$

holds with probability at least $1-2^{-n^{\Theta(1)}}.$ The first equality
follows using $A=A^{*}+\Delta.$ The first inequality follows using the
triangle inequality. The second equality follows using the definition of the
core and the coefficients tuple (see Definition 2.7 and Definition 2.9). The
second inequality follows using Definition 2.7. The third inequality follows
by Lemma 2.2 and the condition that
$H\cap\left(\bigcup_{j=1}^{t}S_{j}\right)=\emptyset.$

Since the size of
$\left|\\{i\\}\cup\left(\bigcup_{j=1}^{t}S_{j}\right)\right|=qt+1,$ the total
number of $(A^{*},q,t,1/2)-$good tuples is upper bounded by $n^{qt+1}\leq
2^{n^{o(1)}}.$ By taking a union bound, we complete the proof. ∎

###  A.7 Proof of Lemma 2.11

###### Proof.

For $j\in[t],$ by symmetry of the choices of $S_{j}$ and $i$, we have
$\Pr[i\in R_{A^{*}}(S_{j}\cup\\{i\\})]\leq k/(q+1).$ Thus, by Markov’s
inequality,

$\displaystyle\Pr[|\\{j\in[t]\mid i\in R_{A^{*}}(S_{j}\cup\\{i\\})\\}|>0.5t]$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\operatorname*{{\bf{E}}}[|\\{j\in[t]\mid i\in
R_{A^{*}}(S_{j}\cup\\{i\\})\\}|]/(0.5t)$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle 2k/q.$

Thus,

$\displaystyle\Pr[|\\{j\in[t]\mid i\not\in R_{A^{*}}(S_{j}\cup\\{i\\})\\}|\geq
0.5t]\geq 1-2k/q.$

∎

###  A.8 Proof of Lemma 2.12

###### Proof.

For $S_{1},S_{2},\cdots,S_{t}\in{[n]\choose q}$ with
$\sum_{j=1}^{t}|S_{j}|=qt,$ define

$\displaystyle
P_{(S_{1},S_{2},\cdots,S_{t})}=\Pr_{i\in[n]\setminus\left(\bigcup_{j=1}^{t}S_{j}\right)}[(S_{1},S_{2},\cdots,S_{t},i)\text{\leavevmode\nobreak\
is an $(A^{*},q,t,1/2)-$good tuple\leavevmode\nobreak\ }].$

Let set $T$ be defined as follows:

$\displaystyle\left\\{(S_{1},S_{2},\cdots,S_{t})\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\ S_{1},S_{2},\cdots,S_{t}\in{[n]\choose
q}\text{\leavevmode\nobreak\ with\leavevmode\nobreak\
}\sum_{j=1}^{t}|S_{j}|=qt\right\\}.$

Let $G$ be the set of all the $(A^{*},q,t,1/2)-$good tuples. Then, we have

$\displaystyle\Pr_{(S_{1},S_{2},\cdots,S_{t})\sim
T}\left[\left|\left\\{i\in[n]\setminus\left(\cup_{j=1}^{t}S_{j}\right)\mid(S_{1},S_{2},\cdots,S_{t},i)\in
G\right\\}\right|\geq(1-4k/q)(n-qt)\right]$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{1}{|T|}\left|\left\\{(S_{1},S_{2},\cdots,S_{t})\mid(S_{1},S_{2},\cdots,S_{t})\in
T\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}P_{(S_{1},S_{2},\cdots,S_{t})}\geq 1-4k/q\right\\}\right|$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{1}{|T|}\underset{P_{(S_{1},S_{2},\cdots,S_{t})}\geq
1-4k/q}{\sum_{(S_{1},S_{2},\cdots,S_{t})\in T}}1$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1}{|T|}\underset{P_{(S_{1},S_{2},\cdots,S_{t})}\geq
1-4k/q}{\sum_{(S_{1},S_{2},\cdots,S_{t})\in T}}P_{(S_{1},S_{2},\cdots,S_{t})}$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle
1-2k/q-\frac{1}{|T|}\underset{P_{(S_{1},S_{2},\cdots,S_{t})}<1-4k/q}{\sum_{(S_{1},S_{2},\cdots,S_{t})\in
T}}P_{(S_{1},S_{2},\cdots,S_{t})}$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle 1-2k/q-(1-4k/q)$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle 2k/q.$

The second inequality follows from Lemma 2.11

$\displaystyle\frac{1}{|T|}\underset{P_{(S_{1},S_{2},\cdots,S_{t})}<1-4k/q}{\sum_{(S_{1},S_{2},\cdots,S_{t})\in
T}}P_{(S_{1},S_{2},\cdots,S_{t})}+\frac{1}{|T|}\underset{P_{(S_{1},S_{2},\cdots,S_{t})}\geq
1-4k/q}{\sum_{(S_{1},S_{2},\cdots,S_{t})\in
T}}P_{(S_{1},S_{2},\cdots,S_{t})}\geq 1-2k/q.$

∎

##  Appendix B Hardness Result

#### An overview of the hardness result.

Recall that we overcame the column subset selection lower bound of [SWZ17],
which shows for entrywise $\ell_{1}$-low rank approximation that there are
matrices for which any subset of $\operatorname{poly}(k)$ columns spans at
best a $k^{\Omega(1)}$-approximation. Indeed, we came up with a column subset
of size $\operatorname{poly}(k(\epsilon^{-1}+\log n))$ spanning a
$(1+\epsilon)$-approximation. To do this, we assumed $A=A^{*}+\Delta$, where
$A^{*}$ is an arbitrary rank-$k$ matrix, and the entries are i.i.d. from a
distribution with $\operatorname*{{\bf{E}}}[|\Delta_{i,j}|]=1$ and
$\operatorname*{{\bf{E}}}[|\Delta_{i,j}|^{p}]=O(1)$ for any real number $p$
strictly greater than $1$.

Here we show an assumption on the moments is necessary, by showing if instead
$\Delta$ were drawn from a matrix of i.i.d. Cauchy random variables, for which
the $p$-th moment is undefined or infinite for all $p\geq 1$, then for any
subset of $n^{o(1)}$ columns, it spans at best a $1.002$ approximation. The
input matrix $A=n^{C}1\cdot 1^{\top}+\Delta$, where $C>0$ is a constant and we
show that $n^{\Omega(1)}$ columns need to be chosen to obtain a
$1.001$-approximation, even for $k=1$. Note that this result is stronger than
that in [SWZ17] in that it rules out column subset selection even if one were
to choose $n^{o(1)}$ columns; the result in [SWZ17] requires at most
$\operatorname{poly}(k)$ columns, which for $k=1$, would just rule out $O(1)$
columns. Our main goal here is to show that a moment assumption on our
distribution is necessary, and our result also applies to a symmetric noise
distribution which is i.i.d. on all entries, whereas the result of [SWZ17]
requires a specific deterministic pattern (namely, the identity matrix) on
certain entries.

Our main theorem is given in Theorem B.20. The outline of the proof is as
follows. We first condition on the event that
$\|\Delta\|_{1}\leq\frac{4.0002}{\pi}n^{2}\ln n$, which is shown in Lemma B.2
and follows form standard analysis of sums of absolute values of Cauchy random
variables. Thus, it is sufficient to show if we choose any subset $S$ of
$r=n^{o(1)}$ columns, denoted by the submatrix $A_{S}$, then
$\min_{X\in\mathbb{R}^{r\times n}}\|A_{S}X-A\|_{1}\geq\frac{4.01}{\pi}\cdot
n^{2}\ln n$, as indeed then $\min_{X\in\mathbb{R}^{r\times
n}}\|A_{S}X-A\|_{1}\geq 1.002\|\Delta\|_{1}$ and we rule out a
$(1+\epsilon)$-approximation for $\epsilon$ a sufficiently small constant. To
this end, we instead show for a fixed $S$, that $\min_{X\in\mathbb{R}^{r\times
n}}\|A_{S}X-A\|_{1}\geq\frac{4.01}{\pi}\cdot n^{2}\ln n$ with probability
$1-2^{-n^{\Theta(1)}}$, and then apply a union bound over all $S$. To prove
this for a single subset $S$, we argue that for every “coefficient matrix”
$X$, that $\|A_{S}X-A\|_{1}\geq\frac{4.01}{\pi}\cdot n^{2}\ln n$.

We show in Lemma B.6, that with probability $1-(1/n)^{\Theta(n)}$ over
$\Delta$, simultaneously for all $X$, if $X$ has a column $X_{j}$ with
$\|X_{j}\|_{1}\geq n^{c}$ for a constant $c>0$, then
$\|A_{S}X_{j}-A_{j}\|_{1}\geq.9n^{3}$, which is already too large to provide
an $O(1)$-approximation. Note that we need such a high probability bound to
later union bound over all $S$. Lemma B.6 is in turn shown via a net argument
on all $X_{j}$ (it suffices to prove this for a single $j\in[n]$, since there
are only $n$ different $j$, so we can union bound over all $j$). The net
bounds are given in Definition B.4 and Definition B.5, and the high
probability bound for a given coefficient vector $X_{j}$ is shown in Lemma
B.3, where we use properties of the Cauchy distribution. Thus, we can assume
$\|X_{j}\|_{1}<n^{c}$ for all $j\in[n]$. We also show in Fact B.1, conditioned
on the fact that $\|\Delta\|_{1}\leq\frac{4.002}{\pi}n^{2}\ln n$, it holds
that for any vector $X_{j}$, if $\|X_{j}\|_{1}<n^{c}$ and $|1-{\bf
1}^{\top}X_{j}|>1-10^{-20}$, then
$\|A_{S}X-A\|_{1}\geq\|A_{S}X_{j}-A_{j}\|_{1}>n^{3}$. The intuition here is
$A=n^{c_{0}}{\bf 1}\cdot{\bf 1^{\top}}+\Delta$ for a large constant $c_{0}$,
and $X_{j}$ does not have enough norm ($\|X_{j}\|_{1}\leq n^{c}$) or
correlation with the vector ${\bf 1}$ ($|1-{\bf 1}^{\top}X_{j}|>1-10^{-20}$)
to make $\|A_{S}X_{j}-A_{j}\|_{1}$ small.

Given the above, we can assume both that $\|X_{j}\|_{1}\leq n^{c}$ and
$|1-{\bf 1}^{\top}X_{j}|\leq 1-10^{-20}$ for all columns $j$ of our
coefficient matrix $X$. We can also assume that $\|A_{S}X-A\|_{1}\leq
4n^{2}\ln n$, as otherwise such an $X$ already satisfies
$\|A_{S}X-A\|_{1}\geq\frac{4.01}{\pi}\cdot n^{2}\ln n$ and we are done. To
analyze $\|A_{S}X-A\|_{1}=\sum_{i,j}|(A_{S}X-A_{[n]\setminus S})_{i,j}|$ in
Theorem B.20, we then split the sum over “large coordinates” $(i,j)$ for which
$|\Delta_{i,j}|>n^{1.0002}$, and “small coordinates” $(i,j)$ for which
$|\Delta_{i,j}|<n^{.9999}$, and since we seek to lower bound
$\|A_{S}X-A_{[n]\setminus S}\|_{1}$, we drop the remaining coordinates
$(i,j)$. To handle large coordinates, we observe that since the column span of
$A_{S}$ is only $r=n^{o(1)}$-dimensional, as one ranges over all vectors $y$
in its span of $1$-norm, say, $O(n^{2}\ln n)$, there is only a small subset
$T$, of size at most $n^{.99999}$ of coordinates $i\in[n]$ for which we could
ever have $|y_{i}|\geq n^{1.0001}$. We show this in Lemma B.9. This uses the
property of vectors in low-dimensional subspaces, and has been exploited in
earlier works in the context of designing so-called subspace embeddings [CW13,
MM13]. We call $T$ the “bad region” for $A_{S}$. While the column span of
$A_{S}$ depends on $\Delta_{S}$, it is independent of $\Delta_{[n]\setminus
S}$, and thus it is extremely unlikely that the large coordinate of
$\Delta_{S}$ “match up” with the bad region of $A_{S}$. This is captured in
Lemma B.13, where we show that if $\|A_{S}X-A_{[n]\setminus S}\|_{1}\leq
4n^{2}\ln n$ (as we said we could assume above), then $\sum_{\textrm{large
coordinates }i,j}|(A_{S}X-A_{[n]\setminus S})_{i,j}|$ is at least
$\frac{1.996}{\pi}n^{2}\ln n$. Intuitively, the heavy coordinates make up
about $\frac{2}{\pi}n^{2}\ln n$ of the total mass of $\|\Delta\|_{1}$, by tail
bounds of the Cauchy distribution, and for any set $S$ of size $n^{o(1)}$,
$A_{S}$ fits at most a small portion of this, still leaving us left with
$\frac{1.996}{\pi}n^{2}\ln n$ in cost. Our goal is to show that
$\|A_{S}X-A_{[n]\setminus S}\|_{1}\geq\frac{4.01}{\pi}\cdot n^{2}\ln n$, so we
still have a way to go.

We next analyze $\sum_{\textrm{small coordinates }i,j}|(A_{S}X-A_{[n]\setminus
S})_{i,j}|$. Via Bernstein’s inequality, in Lemma B.14 we argue that for any
fixed vector $y$ and random vector $\Delta_{j}$ of i.i.d. Cauchy entries,
roughly half of the contribution of coordinates to $\|\Delta_{j}\|_{1}$ will
come from coordinates $j$ for which sign$(y_{j})=$sign$(\Delta_{j})$ and
$|\Delta_{j}|\leq n^{.9999}$, giving us a contribution of roughly
$\frac{.9998}{\pi}n\ln n$ to the cost. The situation we will actually be in,
when analyzing a column of $A_{S}X-A_{[n]\setminus S}$, is that of taking the
sum of two independent Cauchy vectors, shifted by a multiple of ${\bf
1}^{\top}$. We analyze this setting in Lemma B.16, after first conditioning on
certain level sets having typical behavior in Lemma B.15. This roughly doubles
the contribution, gives us roughly a contribution of
$\frac{1.996}{\pi}n^{2}\ln n$ from coordinates $j$ for which $(i,j)$ is a
small coordinate and we look at coordinates $i$ on which the sum of two
independent Cauchy vectors have the same sign. Combined with the contribution
from the heavy coordinates, this gives us a cost of roughly
$\frac{3.992}{\pi}n^{2}\ln n$, which still falls short of the
$\frac{4.01}{\pi}\cdot n^{2}\ln n$ total cost we are aiming for. Finally, if
we sum up two independent Cauchy vectors and look at the contribution to the
sum from coordinates which disagree in sign, due to the anti-concentration of
the Cauchy distribution we can still “gain a little bit of cost” since the
values, although differing in sign, are still likely not to be very close in
magnitude. We formalize this in Lemma B.17. We combine all of the costs from
small coordinates in Lemma B.18, where we show we obtain a contribution of at
least $\frac{2.025}{\pi}n\ln n$. This is enough, when combined with our
earlier $\frac{1.996}{\pi}n^{2}\ln n$ contribution from the heavy coordinates,
to obtain an overall $\frac{4.01}{\pi}\cdot n^{2}\ln n$ lower bound on the
cost, and conclude the proof of our main theorem in Theorem B.20.

In the remaining sections, we will present detailed proofs.

###  B.1 A Useful Fact

######  Fact B.1.

Let $c_{0}>0$ be a sufficiently large constant. Let $u=n^{c_{0}}\cdot{\bf
1}\in\mathbb{R}^{n}$ and $\Delta\in\mathbb{R}^{n\times(d+1)}.$ If
$\sum_{i=1}^{d+1}\|\Delta_{i}\|_{1}\leq n^{3}$ and if
$\alpha\in\mathbb{R}^{d}$ satisfies $|1-{\bf 1}^{\top}\alpha|>1/n^{c_{1}}$ and
$\|\alpha\|_{1}\leq n^{c}$, where $0<c<c_{0}-10$ is a constant and $c_{1}>3$
is another constant depending on $c_{0},c$, then

$\displaystyle\|u-u{\bf
1}^{\top}\alpha+\Delta_{d+1}-\Delta_{[d]}\alpha\|_{1}>n^{3}.$

###### Proof.

$\displaystyle\|u-u{\bf 1}^{\top}\alpha+\Delta_{d+1}-\Delta_{[d]}\alpha\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle|1-{\bf
1}^{\top}\alpha|\cdot\|u\|_{1}-\|\Delta_{d+1}\|_{1}-\|\Delta_{[d]}\alpha\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle|1-{\bf
1}^{\top}\alpha|\cdot n\cdot n^{c_{0}}-n^{3}-n^{4}\|\alpha\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle|1-{\bf
1}^{\top}\alpha|\cdot n\cdot n^{c_{0}}-n^{5+c}$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle
n^{c_{0}+1-c_{1}}-n^{5+c}$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle n^{3}.$

The first inequality follows by the triangle inequality. The second inequality
follows since $u=n^{c_{0}}\cdot{\bf 1}\in\mathbb{R}^{n}$ and
$\sum_{i=1}^{d+1}\|\Delta_{i}\|_{1}\leq n^{3}.$ The third inequality follows
since $\|\alpha\|_{1}\leq n^{c}.$ The fourth inequality follows since $|1-{\bf
1}^{\top}\alpha|>1/n^{c_{1}}.$ The last inequality follows since
$c_{0}-c_{1}>c+5.$ ∎

###  B.2 One-Sided Error Concentration Bound for a Random Cauchy Matrix

######  Lemma B.2 (Lower bound on the cost).

If $n$ is sufficiently large, then

$\displaystyle\Pr_{\Delta\sim\\{C(0,1)\\}^{n\times
n}}\left[\|\Delta\|_{1}\leq\frac{4.0002}{\pi}n^{2}\ln n\right]\geq
1-O(1/\log\log n).$

###### Proof.

Let $\Delta\in\mathbb{R}^{n\times n}$ be a random matrix such that each entry
is an i.i.d. $C(0,1)$ random Cauchy variable. Let $B=n^{2}\ln\ln n.$ Let
$Z\in\mathbb{R}^{n\times n}$ and $\forall i,j\in[n],$

$\displaystyle
Z_{i,j}=\left\\{\begin{array}[]{ll}|\Delta_{i,j}|&|\Delta_{i,j}|<B\\\
B&\text{Otherwise}\end{array}\right..$

For fixed $i,j\in[n],$ we have

$\displaystyle\operatorname*{{\bf{E}}}[Z_{i,j}]$
$\displaystyle=\frac{2}{\pi}\int_{0}^{B}\frac{x}{1+x^{2}}\mathrm{d}x+\Pr[|\Delta_{i,j}|\geq
B]\cdot B$ $\displaystyle=\frac{1}{\pi}\ln(B^{2}+1)+\Pr[|\Delta_{i,j}|\geq
B]\cdot B$ $\displaystyle\leq\frac{1}{\pi}\ln(B^{2}+1)+1$

where the first inequality follows by the cumulative distribution function of
a half Cauchy random variable. We also have
$\operatorname*{{\bf{E}}}[Z_{i,j}]\geq\frac{1}{\pi}\ln(B^{2}+1).$ For the
second moment, we have

$\displaystyle\operatorname*{{\bf{E}}}[Z_{i,j}^{2}]$
$\displaystyle=\frac{2}{\pi}\int_{0}^{B}\frac{x^{2}}{1+x^{2}}\mathrm{d}x+\Pr[|\Delta_{i,j}|\geq
B]\cdot B^{2}$
$\displaystyle=\frac{2}{\pi}(B-\tan^{-1}B)+\Pr[|\Delta_{i,j}|\geq B]\cdot
B^{2}$ $\displaystyle\leq\frac{2}{\pi}B+B$ $\displaystyle\leq 2B$

where the first inequality follows by the cumulative distribution function of
a half Cauchy random variable. By applying Bernstein’s inequality, we have

$\displaystyle\Pr\left[\|Z\|_{1}-\operatorname*{{\bf{E}}}[\|Z\|_{1}]>0.0001\operatorname*{{\bf{E}}}[\|Z\|_{1}]\right]$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\exp\left(-\frac{0.5\cdot
0.0001^{2}\operatorname*{{\bf{E}}}[\|Z\|_{1}]^{2}}{n^{2}\cdot
2B+\frac{1}{3}B\cdot 0.0001\operatorname*{{\bf{E}}}[\|Z\|_{1}]}\right)$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle\exp(-\Omega(\ln
n/\ln\ln n))$ $\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle O(1/\ln
n).$ (6)

The first inequality follows by the definition of $Z$ and the second moment of
$Z_{i,j}.$ The second inequality follows from
$\operatorname*{{\bf{E}}}[\|Z\|_{1}]=\Theta(n^{2}\ln n)$ and
$B=\Theta(n^{2}\ln\ln n).$ Notice that

$\displaystyle\Pr\left[\|\Delta\|_{1}>\frac{4.0002}{\pi}n^{2}\ln n\right]$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\Pr\left[\|\Delta\|_{1}>\frac{4.0002}{\pi}n^{2}\ln n\mid\forall
i,j,|\Delta_{i,j}|<B\right]\Pr\left[\forall i,j,|\Delta_{i,j}|<B\right]$
$\displaystyle+\Pr\left[\|\Delta\|_{1}>\frac{4.0002}{\pi}n^{2}\ln n\mid\exists
i,j,|\Delta_{i,j}|\geq B\right]\Pr\left[\exists i,j,|\Delta_{i,j}|\geq
B\right]$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\Pr\left[\|\Delta\|_{1}>\frac{4.0002}{\pi}n^{2}\ln n\mid\forall
i,j,|\Delta_{i,j}|<B\right]+\Pr\left[\exists i,j,|\Delta_{i,j}|\geq B\right]$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\Pr\left[\|Z\|_{1}>\frac{4.0002}{\pi}n^{2}\ln
n\right]+\Pr\left[\exists i,j,|\Delta_{i,j}|\geq B\right]$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\Pr\left[\|Z\|_{1}>\frac{4.0002}{\pi}n^{2}\ln
n\right]+n^{2}\cdot 1/B$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\Pr\left[\|Z\|_{1}>1.0001\operatorname*{{\bf{E}}}[\|Z\|_{1}]\right]+n^{2}\cdot
1/B$ $\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
O(1/\log(n))+O(1/\log\log n)$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle O(1/\log\log n)$

The second inequality follows by the definition of $Z$. The third inequality
follows by the union bound and the cumulative distribution function of a half
Cauchy random variable. The fourth inequality follows from
$\operatorname*{{\bf{E}}}[\|Z\|_{1}]\leq n^{2}(1/\pi\cdot\ln(B^{2}+1)+1)\leq
4.0000001/\pi\cdot n^{2}\ln n$ when $n$ is sufficiently large. ∎

###  B.3 “For Each” Guarantee

In the following Lemma, we show that, for each fixed coefficient vector
$\alpha$, if the entry of $\alpha$ is too large, the fitting cost cannot be
small.

######  Lemma B.3 (For each fixed $\alpha$, the entry cannot be too large).

Let $c>0$ be a sufficiently large constant, $n\geq d\geq 1,$
$u\in\mathbb{R}^{n}$ be any fixed vector and $\Delta\in\mathbb{R}^{n\times d}$
be a random matrix where $\forall i\in[n],j\in[d],\Delta_{i,j}\sim C(0,1)$
independently. For any fixed $\alpha\in\mathbb{R}^{d}$ with
$\|\alpha\|_{1}=n^{c}$,

$\displaystyle\Pr_{\Delta\sim\\{C(0,1)\\}^{n\times d}}[\|(u\cdot{\bf
1}^{\top}+\Delta)\alpha\|_{1}>n^{3}]>1-(1/n)^{\Theta(n)}.$

###### Proof.

Let $c$ be a sufficiently large constant. Let $\alpha\in\mathbb{R}^{d}$ with
$\|\alpha\|_{1}=n^{c}$. Let $u\in\mathbb{R}^{n}$ be any fixed vector. Let
$\Delta\in\mathbb{R}^{n\times d}$ be a random matrix where $\forall
i\in[n],j\in[d],\Delta_{i,j}\sim C(0,1).$ Then $\Delta\alpha\in\mathbb{R}^{n}$
is a random vector with each entry drawn independently from
$C(0,\|\alpha\|_{1})$. Due to the probability density function of standard
Cauchy random variables,

$\displaystyle\Pr[\|\Delta\alpha\|_{1}<n^{3}]\geq\Pr[\|\Delta\alpha+u\cdot{\bf
1}^{\top}\alpha\|_{1}<n^{3}].$

It suffices to upper bound $\Pr[\|\Delta\alpha\|_{1}<n^{3}].$ If $c>10,$ then
due to the cumulative distribution function of Cauchy random variables, for a
fixed $i\in[n],$ $\Pr[|(\Delta\alpha)_{i}|<n^{3}]<1/n.$ Thus,
$\Pr[\|\Delta\alpha\|_{1}<n^{3}]<(\frac{1}{n})^{n}.$ Thus,

$\displaystyle\Pr_{\Delta\sim\\{C(0,1)\\}^{n\times d}}[\|(u\cdot{\bf
1}^{\top}+\Delta)\alpha\|_{1}>n^{3}]>1-(1/n)^{n}.$

∎

###  B.4 From “For Each” to “For All” via an $\epsilon$-Net

######  Definition B.4 ($\epsilon$-net for the $\ell_{1}$-norm ball).

Let $A\in\mathbb{R}^{n\times d}$ have rank $d$, and let
$L=\\{y\in\mathbb{R}^{n}\mid y=Ax,x\in\mathbb{R}^{d}\\}$ be the column space
of $A.$ An $\epsilon$-net of the $\ell_{1}$-unit sphere
$\mathcal{S}^{d-1}=\\{y\mid\|y\|_{1}=1,y\in L\\}\subset L$ is a set
$N\subset\mathcal{S}^{d-1}$ of points for which $\forall
y\in\mathcal{S}^{d-1},\exists y^{\prime}\in N$ for which
$\|y-y^{\prime}\|\leq\epsilon.$

[DDH+09] proved an upper bound on the size of an $\epsilon$-net.

######  Lemma B.5 (See, e.g., the ball $B$ on page 2068 of [DDH+09]).

Let $A\in\mathbb{R}^{n\times d}$ have rank $d$, and let
$L=\\{y\in\mathbb{R}^{n}\mid y=Ax,x\in\mathbb{R}^{d}\\}$ be the column space
of $A.$ For $\epsilon\in(0,1),$ an $\epsilon$-net (Definition B.4) $N$ of the
$\ell_{1}$-unit sphere $\mathcal{S}^{d-1}=\\{y\mid\|y\|_{1}=1,y\in L\\}\subset
L$ exists. Furthermore, the size of $N$ is at most $(3/\epsilon)^{d}.$

######  Lemma B.6 (For all possible $\alpha$, the entry cannot be too large).

Let $n\geq 1,d=n^{o(1)}.$ Let $u=n^{c_{0}}\cdot{\bf 1}\in\mathbb{R}^{n}$
denote a fixed vector where $c_{0}$ is a constant. Let
$\Delta\in\mathbb{R}^{n\times d}$ be a random matrix where $\forall
i\in[n],j\in[d],\Delta_{i,j}\sim C(0,1)$ independently. Let $c>0$ be a
sufficiently large constant. Conditioned on $\|\Delta\|_{1}\leq n^{3},$ with
probability at least $1-(1/n)^{\Theta(n)},$ for all $\alpha\in\mathbb{R}^{d}$
with $\|\alpha\|_{1}\geq n^{c},$ we have $\|(u\cdot{\bf
1}^{\top}+\Delta)\alpha\|_{1}>0.9n^{3}.$

###### Proof.

Due to Lemma B.5, there is a set
$N\subset\\{\alpha\in\mathbb{R}^{d}\mid\|\alpha\|_{1}=n^{c}\\}\subset\mathbb{R}^{d}$
with $|N|\leq 2^{\Theta(d\log n)}$ such that $\forall\alpha\in\mathbb{R}^{d}$
with $\|\alpha\|_{1}=n^{c},$ $\exists\alpha^{\prime}\in N$ such that
$\|\alpha-\alpha^{\prime}\|_{1}\leq 1/n^{c^{\prime}}$ where
$c^{\prime}>c_{0}+100$ is a constant. By applying Lemma B.3 and union bounding
over all the points in $N,$ with probability at least $1-(1/n)^{n}\cdot|N|\geq
1-(1/n)^{n}\cdot 2^{n^{o(1)}}=1-(1/n)^{\Theta(n)},$ $\forall\alpha^{\prime}\in
N,$ $\|(u\cdot{\bf 1}^{\top}+\Delta)\alpha^{\prime}\|_{1}>n^{3}.$
$\forall\alpha\in\mathbb{R}^{d}$ with $\|\alpha\|_{1}=n^{c},$ we can find
$\alpha^{\prime}\in N$ such that $\|\alpha-\alpha^{\prime}\|_{1}\leq
1/n^{c^{\prime}}.$ Let $\gamma=\alpha-\alpha^{\prime}.$ Then,

$\displaystyle\|(u\cdot{\bf 1}^{\top}+\Delta)\alpha\|_{1}$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle\|(u\cdot{\bf
1}^{\top}+\Delta)(\alpha^{\prime}+\gamma)\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle\|(u\cdot{\bf
1}^{\top}+\Delta)\alpha^{\prime}\|_{1}-\|(u\cdot{\bf
1}^{\top}+\Delta)\gamma\|_{1}$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle n^{3}-\sqrt{n}\|(u\cdot{\bf 1}^{\top}+\Delta)\gamma\|_{2}$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle
n^{3}-\sqrt{n}(\|u\cdot{\bf 1}^{\top}\|_{2}+\|\Delta\|_{2})\|\gamma\|_{2}$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle
n^{3}-n^{c_{0}+50}/n^{c^{\prime}}$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle 0.9n^{3}.$

The first equality follows from $\alpha=\alpha^{\prime}+\gamma.$ The first
inequality follows by the triangle inequality. The second inequality follows
by the relaxation from the $\ell_{1}$ norm to the $\ell_{2}$ norm. The third
inequality follows from the operator norm and the triangle inequality. The
fourth inequality follows using $\|\Delta\|_{2}\leq\|\Delta\|_{1}\leq
n^{3},\|u\|_{2}\leq
n^{c_{0}+10},\|\gamma\|_{2}\leq\|\gamma\|_{1}\leq(1/n)^{c^{\prime}}.$ The last
inequality follows since $c^{\prime}>c_{0}+100.$

For $\alpha\in\mathbb{R}^{n}$ with $\|\alpha\|_{1}>n^{c},$ let
$\alpha^{\prime}=\alpha/\|\alpha\|_{1}\cdot n^{c}.$ Then

$\displaystyle\|(u\cdot{\bf 1}^{\top}+\Delta)\alpha\|_{1}\geq\|(u\cdot{\bf
1}^{\top}+\Delta)\alpha^{\prime}\|_{1}\geq 0.9n^{3}.$

∎

###  B.5 Bounding the Cost from the Large-Entry Part via “Bad” Regions

In this section, we will use the concept of _well-conditioned basis_ in our
analysis.

######  Definition B.7 (Well-conditioned basis [DDH+09]).

Let $A\in\mathbb{R}^{n\times m}$ have rank $d$. Let $p\in[1,\infty),$ and let
$\|\cdot\|_{q}$ be the dual norm of $\|\cdot\|_{p},$ i.e., $1/p+1/q=1.$ If
$U\in\mathbb{R}^{n\times d}$ satisfies

  1. 1.

$\|U\|_{p}\leq\alpha,$

  2. 2.

$\forall z\in\mathbb{R}^{d},\|z\|_{q}\leq\beta\|Uz\|_{p},$

then $U$ is an $(\alpha,\beta,p)$ well-conditioned basis for the column space
of $A$.

The following theorem gives an existence result of a well-conditioned basis.

######  Theorem B.8 ($\ell_{1}$ well-conditioned basis [DDH+09]).

Let $A\in\mathbb{R}^{n\times m}$ have rank $d$. There exists
$U\in\mathbb{R}^{n\times d}$ such that $U$ is a $(d,1,1)$ well-conditioned
basis for the column space of $A$.

In the following lemma, we consider vectors from low-dimensional subspaces.
For a coordinate, if there is a vector from the subspace for which this entry
is large, but the norm of the vector is small, then this kind of coordinate is
pretty “rare”. More formally,

######  Lemma B.9.

Given a matrix $U\in\mathbb{R}^{n\times r}$ for a sufficiently large $n\geq
1$, let $r=n^{o(1)}$. Let $S=\\{y|y=Ux,x\in\mathbb{R}^{r}\\}$. Let the set $T$
denote $\\{i\in[n]\leavevmode\nobreak\ |\leavevmode\nobreak\ \exists y\in
S,|y_{i}|\geq n^{1.0001}\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}\|y\|_{1}<8n^{2}\ln n\\}$. Then we have

$\displaystyle|T|\leq n^{0.99999}.$

###### Proof.

Due to Theorem B.8, let $U\in\mathbb{R}^{n\times r}$ be the $(r,1,1)$ well-
conditioned basis of the column space of $U$. If $i\in T,$ then $\exists
x\in\mathbb{R}^{r}$ such that $|(Ux)_{i}|\geq n^{1.0001}$ and
$\|Ux\|_{1}<8n^{2}\ln n.$ Thus, we have

$\displaystyle
n^{1.0001}\leq|(Ux)_{i}|\leq\|U^{i}\|_{1}\|x\|_{\infty}\leq\|U^{i}\|_{1}\|Ux\|_{1}\leq\|U^{i}\|_{1}\cdot
8n^{2}\ln n.$

The first inequality follows using $n^{1.0001}\leq|(Ux)_{i}|.$ The second
inequality follows by Hölder’s inequality. The third inequality follows by the
second property of the well-conditioned basis. The fourth inequality follows
using $\|Ux\|_{1}<8n^{2}\ln n.$ Thus, we have

$\displaystyle\|U^{i}\|_{1}\geq n^{1.0001}/n^{2+o(1)}\geq 1/n^{0.9999-o(1)}.$

Notice that $\sum_{j=1}^{n}\|U^{j}\|_{1}=\|U\|_{1}\leq r.$ Thus,

$\displaystyle|T|\leq r/(1/n^{0.9999-o(1)})=n^{0.9999+o(1)}\leq n^{0.99999}.$

∎

######  Definition B.10 (Bad region).

Given a matrix $U\in\mathbb{R}^{n\times r}$, we say ${\cal
B}(U)=\\{i\in[n]\leavevmode\nobreak\ |\leavevmode\nobreak\ \exists
y\in\mathrm{colspan}(U)\subset\mathbb{R}^{n}\mathrm{\leavevmode\nobreak\
s.t.\leavevmode\nobreak\ }y_{i}\geq n^{1.0001}\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }\|y\|_{1}\leq 8n^{2}\ln n\\}$ is a bad region for
$U$.

Next we state a lower and an upper bound on the probability that a Cauchy
random variable is in a certain range,

######  Claim B.11.

Let $X\sim C(0,1)$ be a standard Cauchy random variable. Then for any
$x>1549,$

$\displaystyle\frac{2}{\pi}\cdot\frac{\ln(1.001)}{x}\geq\Pr[|X|\in(x,1.001x]]\geq\frac{1.999}{\pi}\cdot\frac{\ln(1.001)}{x}.$

###### Proof.

When $x>1549,$
$\frac{2}{\pi}\cdot\frac{\ln(1.001)}{x}\geq\frac{2}{\pi}\cdot(\tan^{-1}(1.001x)-\tan^{-1}(x))\geq\frac{1.999}{\pi}\cdot\frac{\ln(1.001)}{x}.$
∎

We build a level set for the “large” noise values, and we show the bad region
cannot cover much of the large noise. The reason is that the bad region is
small, and for each row, there is always some large noise.

######  Lemma B.12.

Given a matrix $U\in\mathbb{R}^{n\times r}$ with $n$ sufficiently large, let
$r=n^{o(1)}$, and consider a random matrix
$\Delta\in\mathbb{R}^{n\times(n-r)}$ with $\Delta_{i,j}\sim C(0,1)$
independently. Let $L_{t}=\\{(i,j)\leavevmode\nobreak\ |\leavevmode\nobreak\
(i,j)\in[n]\times[n-r],|\Delta_{i,j}|\in(1.001^{t},1.001^{t+1}]\\}$. With
probability at least $1-1/2^{n^{\Theta(1)}}$, for all $t\in(\frac{1.0002\ln
n}{\ln 1.001},\frac{1.9999\ln n}{\ln 1.001})\cap\mathbb{N}$,

$\displaystyle|L_{t}\setminus({\cal B}(U)\times[n-r])|\geq n(n-r)\cdot
1.998\cdot\ln(1.001)/(\pi\cdot 1.001^{t}).$

###### Proof.

Let $N=n\cdot(n-r).$ Then according to Claim B.11, $\forall
t\in(\frac{1.0002\ln n}{\ln 1.001},\frac{1.9999\ln n}{\ln
1.001})\cap\mathbb{N},$ $\operatorname*{{\bf{E}}}(|L_{t}|)\geq N\cdot
1.999\cdot\ln(1.001)/(\pi\cdot 1.001^{t})\geq n^{\Theta(1)}.$ For a fixed $t,$
by a Chernoff bound, with probability at least $1-1/2^{n^{\Theta(1)}}$,
$|L_{t}|\geq N\cdot 1.9989\cdot\ln(1.001)/(\pi\cdot 1.001^{t}).$ Due to Lemma
B.9, $|{\cal B}(U)\times[n-r]|\leq n^{0.99999}(n-r)=N/n^{0.00001}.$ Due to the
Chernoff bound, with probability at least $1-1/2^{n^{\Theta(1)}},$
$|L_{t}\cap({\cal B}(U)\times[n-r])|<N/n^{0.00001}\cdot
2.0001\cdot\ln(1.001)/(\pi\cdot 1.001^{t}).$ Thus, with probability at least
$1-1/2^{n^{\Theta(1)}},$ $|L_{t}\setminus({\cal B}(U)\times[n-r])|\geq N\cdot
1.998\cdot\ln(1.001)/(\pi\cdot 1.001^{t}).$ By taking a union bound over all
$t\in(\frac{1.0002\ln n}{\ln 1.001},\frac{1.9999\ln n}{\ln
1.001})\cap\mathbb{N}$, we complete the proof. ∎

######  Lemma B.13 (The cost of the large noise part).

Let $n\geq 1$ be sufficiently large, and let $r=n^{o(1)}.$ Given a matrix
$U\in\mathbb{R}^{n\times r}$, and a random matrix
$\Delta\in\mathbb{R}^{n\times(n-r)}$ with $\Delta_{i,j}\sim C(0,1)$
independently, let ${\cal I}=\\{(i,j)\in[n]\times[n-r]\leavevmode\nobreak\
|\leavevmode\nobreak\ |\Delta_{i,j}|\geq n^{1.0002}\\}$. If
$\|\Delta\|_{1}\leq 4n^{2}\ln n$, then with probability at least
$1-1/2^{n^{\Theta(1)}}$, for all $X\in\mathbb{R}^{r\times n}$, either

$\displaystyle\sum_{(i,j)\in{\cal
I}}|(UX-\Delta)_{i,j}|>\frac{1.996}{\pi}n^{2}\ln n,$

or

$\displaystyle\|UX-\Delta\|_{1}>4n^{2}\ln n$

###### Proof.

$\displaystyle\sum_{(i,j)\in{\cal I}}|(UX-\Delta)_{i,j}|$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle\sum_{(i,j)\in{\cal
I}\setminus\mathcal{B}(U)}|(UX-\Delta)_{i,j}|$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle\sum_{(i,j)\in{\cal
I}\setminus\mathcal{B}(U)}|(\Delta)_{i,j}|-\sum_{(i,j)\in{\cal
I}\setminus\mathcal{B}(U)}|(UX)_{i,j}|$ (7)

Let $N=n(n-r).$ By a Chernoff bound and the cumulative distribution function
of a Cauchy random variable, with probability at least
$1-1/2^{n^{\Theta(1)}},$ $|{\cal I}|\leq 1.1\cdot N/n^{1.0002}.$ If
$\exists(i,j)\in{\cal I}\setminus\mathcal{B}(U)$ which has
$|(UX)_{i,j}|>n^{1.0001}$, then according to the definition of
$\mathcal{B}(U),$ $\|UX\|_{1}\geq\|(UX)_{j}\|_{1}\geq 8n^{2}\ln n.$ Due to the
triangle inequality, $\|UX-\Delta\|_{1}\geq\|UX\|_{1}-\|\Delta\|_{1}\geq
4n^{2}\ln n.$ If $\forall(i,j)\in{\cal I}\setminus\mathcal{B}(U)$ we have
$|(UX)_{i,j}|\leq n^{1.0001},$ then

$\displaystyle\sum_{(i,j)\in{\cal
I}\setminus\mathcal{B}(U)}|(UX)_{i,j}|\leq|\mathcal{I}|\cdot n^{1.0001}\leq
1.1\cdot N/n^{0.0001}.$ (8)

Due to Lemma B.12, with probability at least $1-1/2^{n^{\Theta(1)}},$

$\displaystyle\sum_{(i,j)\in{\cal I}\setminus\mathcal{B}(U)}|(\Delta)_{i,j}|$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\sum_{t\in(\frac{1.0002\ln n}{\ln 1.001},\frac{1.9999\ln n}{\ln
1.001})\cap\mathbb{N}}1.001^{t}\cdot N\cdot 1.998\cdot\ln(1.001)/(\pi\cdot
1.001^{t})$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1.997}{\pi}\cdot N\ln n.$ (9)

We plug (8) and (9) into (7), from which we have

$\displaystyle\sum_{(i,j)\in{\cal
I}}|(UX-\Delta)_{i,j}|\geq\frac{1.996}{\pi}n^{2}\ln n.$

∎

###  B.6 Cost from the Sign-Agreement Part of the Small-Entry Part

We use $-y$ to fit $\Delta$ (we think of $A_{S}\alpha=A_{S}^{*}\alpha-y$, and
want to minimize $\|-y-\Delta\|_{1}$). If the sign of $y_{j}$ is the same as
the sign of $\Delta_{j}$, then both coordinate values will collectively
contribute.

######  Lemma B.14 (The contribution from $\Delta_{i}$ when $\Delta_{i}$ and
$y_{i}$ have the same sign).

Suppose we are given a vector $y\in\mathbb{R}^{n}$ and a random vector
$\Delta\in\mathbb{R}^{n}$ with $\Delta_{j}\sim C(0,1)$ independently. Then
with probability at least $1-1/2^{n^{\Theta(1)}},$

$\displaystyle\sum_{j\leavevmode\nobreak\ :\leavevmode\nobreak\
\operatorname{sign}(y_{j})=\operatorname{sign}(\Delta_{j})\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }|\Delta_{j}|\leq
n^{0.9999}}|\Delta_{j}|>\frac{0.9998}{\pi}n\ln n.$

###### Proof.

For $j\in[n]$, define the random variable

$\displaystyle Z_{j}=\left\\{\begin{array}[]{ll}\Delta_{j}&0<\Delta_{j}\leq
n^{0.9999}\\\ 0&\text{otherwise}\end{array}\right..$

Then, we have

$\displaystyle\Pr\left[\sum_{j\leavevmode\nobreak\ :\leavevmode\nobreak\
\operatorname{sign}(y_{j})=\operatorname{sign}(\Delta_{i,j})\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }|\Delta_{j}|\leq
n^{0.9999}}|\Delta_{j}|>\frac{0.9998}{\pi}n\ln
n\right]=\Pr\left[\sum_{j=1}^{n}Z_{j}>\frac{0.9998}{\pi}n\ln n\right].$

Let $B=n^{0.9999}.$ For $j\in[n],$

$\displaystyle\operatorname*{{\bf{E}}}[Z_{j}]=\frac{1}{\pi}\int_{0}^{B}\frac{x}{1+x^{2}}\mathrm{d}x=\frac{1}{2\pi}\ln(B^{2}+1).$

Also,

$\displaystyle\operatorname*{{\bf{E}}}[Z_{j}^{2}]=\frac{1}{\pi}\int_{0}^{B}\frac{x^{2}}{1+x^{2}}\mathrm{d}x=\frac{B-\tan^{-1}(B)}{\pi}\leq
B.$

By Bernstein’s inequality,

$\displaystyle\Pr\left[\operatorname*{{\bf{E}}}\left[\sum_{j=1}^{n}Z_{j}\right]-\sum_{j=1}^{n}Z_{j}>10^{-5}\operatorname*{{\bf{E}}}\left[\sum_{j=1}^{n}Z_{j}\right]\right]$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\exp\left(-\frac{0.5\cdot\left(10^{-5}\operatorname*{{\bf{E}}}\left[\sum_{j=1}^{n}Z_{j}\right]\right)^{2}}{\sum_{j=1}^{n}\operatorname*{{\bf{E}}}[Z_{j}^{2}]+\frac{1}{3}B\cdot
10^{-5}\operatorname*{{\bf{E}}}\left[\sum_{j=1}^{n}Z_{j}\right]}\right)$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle\exp\left(-\frac{5\cdot
10^{-11}n^{2}\ln^{2}(B^{2}+1)/(4\pi^{2})}{nB+\frac{1}{3}B\cdot
10^{-5}n\ln(B^{2}+1)/(2\pi)}\right)$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle e^{-n^{\Theta(1)}}.$

The last inequality follows since $B=n^{0.9999}.$ Thus, we have

$\displaystyle\Pr\left[\sum_{j=1}^{n}Z_{j}<0.9998/\pi\cdot n\ln
n\right]\leq\Pr\left[\sum_{j=1}^{n}Z_{j}<0.99999n\ln(B^{2}+1)/(2\pi)\right]\leq
e^{-n^{\Theta(1)}}.$

∎

######  Lemma B.15 (Bound on level sets of a Cauchy vector).

Suppose we are given a random vector $y\in\mathbb{R}^{n}$ with $y_{i}\sim
C(0,1)$ chosen independently. Let

$\displaystyle L_{t}^{-}=\\{i\in[n]\leavevmode\nobreak\ |\leavevmode\nobreak\
-y_{i}\in(1.001^{t},1.001^{t+1}]\\}\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }L_{t}^{+}=\\{i\in[n]\leavevmode\nobreak\
|\leavevmode\nobreak\ y_{i}\in(1.001^{t},1.001^{t+1}]\\}.$

With probability at least $1-1/2^{n^{\Theta(1)}}$, for all $t\in(\frac{\ln
1549}{\ln 1.001},\frac{0.9999\ln n}{\ln 1.001})\cap\mathbb{N}$,

$\displaystyle\min(|L_{t}^{-}|,|L_{t}^{+}|)\geq
0.999n\cdot\frac{1}{\pi}\frac{\ln 1.001}{1.001^{t}}.$

###### Proof.

For $i\in[n],t\geq\frac{\ln 1549}{\ln 1.001},$ according to Claim B.11,
$\Pr[y_{i}\in(1.001^{t},1.001^{t+1}]]\geq
0.9995/\pi\cdot\ln(1.0001)/1.001^{t}.$ Thus,
$\operatorname*{{\bf{E}}}[|L_{t}^{+}|]=\operatorname*{{\bf{E}}}[|L_{t}^{-}|]=n\cdot
0.9995/\pi\cdot\ln(1.0001)/1.001^{t}.$ Since $t\leq\frac{0.9999\ln n}{\ln
1.001},$ $1.001^{t}\leq n^{0.9999},$ we have
$\operatorname*{{\bf{E}}}[|L_{t}^{+}|]=\operatorname*{{\bf{E}}}[|L_{t}^{-}|]\geq
n^{\Theta(1)}.$ By applying a Chernoff bound,

$\displaystyle\Pr[|L_{t}^{+}|>0.999n/\pi\cdot\ln(1.0001)/1.001^{t}]\geq
1-1/2^{n^{\Theta(1)}}.$

Similarly, we have

$\displaystyle\Pr[|L_{t}^{-}|>0.999n/\pi\cdot\ln(1.0001)/1.001^{t}]\geq
1-1/2^{n^{\Theta(1)}}.$

By taking a union bound over all the $L_{t}^{+}$ and $L_{t}^{-},$ we complete
the proof. ∎

######  Lemma B.16 (The contribution from $y_{i}$ when $\Delta_{i}$ and
$y_{i}$ have the same sign).

Let $u=\eta\cdot\mathbf{1}\in\mathbb{R}^{n}$ where $\eta\in\mathbb{R}$ is an
arbitrary real number. Let $y\in\mathbb{R}^{n}$ be a random vector with
$y_{i}\sim C(0,\beta)$ independently for some $\beta>0.$ Let
$\Delta\in\mathbb{R}^{n}$ be a random vector with $\Delta_{i}\sim C(0,1)$
independently. With probability at least $1-1/2^{n^{\Theta(1)}},$

$\displaystyle\sum_{i\leavevmode\nobreak\ :\leavevmode\nobreak\
\operatorname{sign}((u+y)_{i})=\operatorname{sign}(\Delta_{i})\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }|\Delta_{i}|\leq
n^{0.9999}}|(u+y)_{i}|\geq\beta\cdot\frac{0.997}{\pi}n\ln n.$

###### Proof.

For all $t\in(\frac{\ln 1549}{\ln 1.001},\frac{0.9999\ln n}{\ln
1.001})\cap\mathbb{N},$ define

$\displaystyle L_{t}^{-}=\\{i\in[n]\leavevmode\nobreak\ |\leavevmode\nobreak\
-y_{i}\in(\beta\cdot 1.001^{t},\beta\cdot
1.001^{t+1}]\\}\mathrm{\leavevmode\nobreak\ and\leavevmode\nobreak\
}L_{t}^{+}=\\{i\in[n]\leavevmode\nobreak\ |\leavevmode\nobreak\
y_{i}\in(\beta\cdot 1.001^{t},\beta\cdot 1.001^{t+1}]\\}.$

Define

$\displaystyle
G=\\{i\in[n]\mid\operatorname{sign}((u+y)_{i})=\operatorname{sign}(\Delta_{i})\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }|\Delta_{i}|\leq n^{0.9999}\\}.$

Then $\forall i\in[n],\Pr[i\in G]\geq 0.5-1/n^{0.9999}\geq 0.4999999999.$ Due
to Lemma B.15,

$\displaystyle\min(|L_{t}^{-}|,|L_{t}^{+}|)\geq
0.999n\cdot\frac{1}{\pi}\frac{\ln 1.001}{1.001^{t}}\geq n^{\Theta(1)}.$

By a Chernoff bound and a union bound, with probability at least
$1-1/2^{n^{\Theta(1)}},$ $\forall t\in(\frac{\ln 1549}{\ln
1.001},\frac{0.9999\ln n}{\ln 1.001})\cap\mathbb{N},$

$\displaystyle\min(|L_{t}^{-}\cap G|,|L_{t}^{+}\cap G|)$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle
0.499n\cdot\frac{1}{\pi}\frac{\ln 1.001}{1.001^{t}}.$ (10)

Then we have

$\displaystyle\sum_{i\in G}|(u+y)_{i}|$ $\displaystyle\geq\leavevmode\nobreak\
$ $\displaystyle\sum_{t\in(\frac{\ln 1549}{\ln 1.001},\frac{0.9999\ln n}{\ln
1.001})\cap\mathbb{N}}\left(\sum_{i\in L_{t}^{+},i\in
G}|y_{i}+\eta|+\sum_{i\in L_{t}^{-},i\in G}|-y_{i}-\eta|\right)$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle\sum_{t\in(\frac{\ln
1549}{\ln 1.001},\frac{0.9999\ln n}{\ln
1.001})\cap\mathbb{N}}0.499n\cdot\frac{1}{\pi}\frac{\ln 1.001}{1.001^{t}}\cdot
2\cdot 1.001^{t}\cdot\beta$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\beta\cdot\frac{0.997}{\pi}n\ln n$

The second inequality follows by Equation (10) and the triangle inequality,
i.e., $\forall a,b,c\in\mathbb{R},|a+c|+|b-c|\geq|a+b|.$ ∎

###  B.7 Cost from the Sign-Disagreement Part of the Small-Entry Part

######  Lemma B.17.

Given a vector $y\in\mathbb{R}^{n}$ and a random vector
$\Delta\in\mathbb{R}^{n}$ with $\Delta_{i}\sim C(0,1)$ independently, with
probability at least $1-1/2^{n^{\Theta(1)}}$,

$\displaystyle\sum_{i\leavevmode\nobreak\ :\leavevmode\nobreak\
\operatorname{sign}(y_{i})\neq\operatorname{sign}(\Delta_{i})\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\
}|\Delta_{i}|<n^{0.9999}}|y_{i}+\Delta_{i}|>\frac{0.03}{\pi}n\ln n.$

###### Proof.

For $t\in[0,\frac{0.9999\ln n}{\ln 4})\cap\mathbb{N}$ define

$\displaystyle
L_{t}=\\{i\in[n]\mid\operatorname{sign}(y_{i})\neq\operatorname{sign}(\Delta_{i}),|\Delta_{i}|\in(4^{t},4^{t+1}],|\Delta_{i}|\not\in[|y_{i}|-4^{t},|y_{i}|+4^{t}]\\}.$

$\forall x\geq 1,y>0,$ we have

$\displaystyle\Pr_{X\sim C(0,1)}[|X|\in(x,4x],|X|\not\in[y-x,y+x]]$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle\Pr_{X\sim
C(0,1)}[|X|\in(3x,4x]]$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{2}{\pi}\cdot(\tan^{-1}(4x)-\tan^{-1}(3x))$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{0.1}{\pi}\cdot\frac{\ln(4)}{x}$

Thus, $\forall i\in[n],t\in[0,\frac{0.9999\ln n}{\ln 4})\cap\mathbb{N},$

$\displaystyle\Pr[i\in L_{t}]\geq\frac{0.05}{\pi}\cdot\frac{\ln(4)}{4^{t}}.$

Thus, $\forall t\in[0,\frac{0.9999\ln n}{\ln
4})\cap\mathbb{N},\operatorname*{{\bf{E}}}[|L_{t}|]\geq
0.05n/\pi\cdot\ln(4)/4^{t}\geq n^{\Theta(1)}.$ By a Chernoff bound and a union
bound, with probability at least $1-1/2^{n^{\Theta(1)}}$ $\forall
t\in[0,\frac{0.9999\ln n}{\ln 4})\cap\mathbb{N},$ $|L_{t}|\geq
0.04n/\pi\cdot\ln(4)/4^{t}.$ Thus, we have, with probability at least
$1-1/2^{n^{\Theta(1)}},$

$\displaystyle\sum_{i\leavevmode\nobreak\ :\leavevmode\nobreak\
\operatorname{sign}(y_{i})\neq\operatorname{sign}(\Delta_{i})\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }|\Delta_{i}|<n^{0.9999}}|y_{i}+\Delta_{i}|$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\sum_{t\in[0,\frac{0.9999\ln n}{\ln
4})\cap\mathbb{N}}|L_{t}|\cdot 4^{t}$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{0.03}{\pi}n\ln n.$

∎

###  B.8 Overall Cost of the Small-Entry Part

######  Lemma B.18 (For each).

Let $u=\eta\cdot\mathbf{1}\in\mathbb{R}^{n}$ where $\eta\in\mathbb{R}$ is an
arbitrary real number. Let $\alpha\in\mathbb{R}^{d}$ where $\|\alpha\|_{1}\geq
1-10^{-20}.$ Let $\Delta\in\mathbb{R}^{n\times(d+1)}$ and
$\forall(i,j)\in[n]\times[d+1],\Delta_{i,j}\sim C(0,1)$ are i.i.d. standard
Cauchy random variables. Then with probability at least
$1-1/2^{n^{\Theta(1)}},$

$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u+\Delta_{d+1}-(u\mathbf{1}^{\top}+\Delta_{[d]})\alpha)_{j}|\geq\frac{2.025}{\pi}n\ln
n.$

###### Proof.

Let
$G_{1}=\\{j\in[n]\mid|\Delta_{j,d+1}|<n^{0.9999},\operatorname{sign}((u(1-\mathbf{1}^{\top}\alpha)-\Delta_{[d]}\alpha)_{j})=\operatorname{sign}(\Delta_{d+1})_{j})\\},G_{2}=\\{j\in[n]\mid|\Delta_{j,d+1}|<n^{0.9999},\operatorname{sign}((u(1-\mathbf{1}^{\top}\alpha)-\Delta_{[d]}\alpha)_{j})\not=\operatorname{sign}(\Delta_{d+1})_{j})\\}.$
Notice that $\Delta_{[d]}\alpha$ is a random vector with each entry
independently drawn from $C(0,\|\alpha\|_{1}).$ Then with probability at least
$1-1/2^{n^{\Theta(1)}},$

$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u+\Delta_{d+1}-(u\mathbf{1}^{\top}+\Delta_{[d]})\alpha)_{j}|$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u(1-\mathbf{1}^{\top}\alpha)-\Delta_{[d]}\alpha+\Delta_{d+1})_{j}|$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle\sum_{j\in
G_{1}}|(u(1-\mathbf{1}^{\top}\alpha)-\Delta_{[d]}\alpha+\Delta_{d+1})_{j}|+\sum_{j\in
G_{2}}|(u(1-\mathbf{1}^{\top}\alpha)-\Delta_{[d]}\alpha+\Delta_{d+1})_{j}|$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle\sum_{j\in
G_{1}}|(u(1-\mathbf{1}^{\top}\alpha)-\Delta_{[d]}\alpha)_{j}|+\sum_{j\in
G_{1}}|(\Delta_{d+1})_{j}|+\sum_{j\in
G_{2}}|(u(1-\mathbf{1}^{\top}\alpha)-\Delta_{[d]}\alpha+\Delta_{d+1})_{j}|$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\|\alpha\|_{1}\cdot\frac{0.997}{\pi}\cdot n\ln
n+\frac{0.9998}{\pi}n\ln n+\frac{0.03}{\pi}n\ln n$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle\frac{2.025}{\pi}n\ln
n$

The first inequality follows by Lemma B.16, Lemma B.14 and Lemma B.17. The
second inequality follows by $\|\alpha\|_{1}\geq 1-10^{-20}.$ ∎

######  Lemma B.19 (For all).

Let $c>0,c_{0}>0$ be two arbitrary constants. Let
$u=\eta\cdot\mathbf{1}\in\mathbb{R}^{n}$ where $\eta\in\mathbb{R}$ satisfies
$|\eta|\leq n^{c_{0}}$. Consider a random matrix
$\Delta\in\mathbb{R}^{n\times(d+1)}$ with $d=n^{o(1)}$ and
$\forall(i,j)\in[n]\times[d+1],\Delta_{i,j}\sim C(0,1)$ are i.i.d. standard
Cauchy random variables. Conditioned on $\|\Delta\|_{1}\leq n^{3},$ with
probability at least $1-1/2^{n^{\Theta(1)}},$ $\forall\alpha\in\mathbb{R}^{d}$
with $1-10^{-20}\leq\|\alpha\|_{1}\leq n^{c},$

$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u+\Delta_{d+1}-(u\mathbf{1}^{\top}+\Delta_{[d]})\alpha)_{j}|\geq\frac{2.024}{\pi}n\ln
n.$

###### Proof.

Let $\mathcal{N}$ be a set of points:

$\displaystyle\mathcal{N}=\left\\{\alpha\in\mathbb{R}^{d}\mid
1-10^{-20}\leq\|\alpha\|_{1}\leq n^{c}\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }\exists
q\in\mathbb{Z}^{d},\mathrm{\leavevmode\nobreak\ such\leavevmode\nobreak\
that\leavevmode\nobreak\ }\alpha=q/n^{c+c_{0}+1000}\right\\}.$

Since $d=n^{o(1)},$ we have
$|\mathcal{N}|\leq(n^{2c+c_{0}+2000})^{d}=2^{n^{o(1)}}.$ By Lemma B.18 and a
union bound, with probability at least
$1-1/2^{n^{\Theta(1)}}\cdot|\mathcal{N}|\geq 1-1/2^{n^{\Theta(1)}},$
$\forall\alpha\in\mathcal{N},$ we have

$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u+\Delta_{d+1}-(u\mathbf{1}^{\top}+\Delta_{[d]})\alpha)_{j}|\geq\frac{2.025}{\pi}n\ln
n.$

Due to the construction of $\mathcal{N},$ we have
$\forall\alpha\in\mathbb{R}^{d}$ with $1-10^{-20}\leq\|\alpha\|_{1}\leq
n^{c},$ $\exists\alpha^{\prime}\in\mathcal{N}$ such that
$\|\alpha-\alpha^{\prime}\|_{\infty}\leq 1/n^{c+c_{0}+1000}.$ Let
$\gamma=\alpha-\alpha^{\prime}.$ Then

$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u+\Delta_{d+1}-(u\mathbf{1}^{\top}+\Delta_{[d]})\alpha)_{j}|$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u+\Delta_{d+1}-(u\mathbf{1}^{\top}+\Delta_{[d]})(\alpha^{\prime}+\gamma))_{j}|$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u+\Delta_{d+1}-(u\mathbf{1}^{\top}+\Delta_{[d]})\alpha^{\prime})_{j}|-\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|((u\mathbf{1}^{\top}+\Delta_{[d]})\gamma)_{j}|$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u+\Delta_{d+1}-(u\mathbf{1}^{\top}+\Delta_{[d]})\alpha^{\prime})_{j}|-\|(u\mathbf{1}^{\top}+\Delta_{[d]})\gamma\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle\frac{2.025}{\pi}n\ln
n-1/n^{500}$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{2.024}{\pi}n\ln n$

The first equality follows from $\alpha=\alpha^{\prime}+\gamma.$ The first
inequality follows by the triangle inequality. The third inequality follows
from $\|\gamma\|_{1}\leq 1/n^{c+c_{0}+800},\|u\mathbf{1}^{\top}\|_{1}\leq
n^{c_{0}+10},\|\Delta\|_{1}\leq n^{3},$ and
$\forall\alpha^{\prime}\in\mathcal{N},$

$\displaystyle\sum_{j\in[n],|\Delta_{j,d+1}|<n^{0.9999}}|(u+\Delta_{d+1}-(u\mathbf{1}^{\top}+\Delta_{[d]})\alpha^{\prime})_{j}|\geq\frac{2.025}{\pi}n\ln
n.$

∎

###  B.9 Main result

######  Theorem B.20 (Formal version of Theorem 1.2).

Let $n>0$ be sufficiently large. Let
$A=\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta\in\mathbb{R}^{n\times n}$
be a random matrix where $\eta=n^{c_{0}}$ for some sufficiently large constant
$c_{0},$ and $\forall i,j\in[n],\Delta_{i,j}\sim C(0,1)$ are i.i.d. standard
Cauchy random variables. Let $r=n^{o(1)}.$ Then with probability at least
$1-O(1/\log\log n),$ $\forall S\subset[n]$ with $|S|=r,$

$\displaystyle\min_{X\in\mathbb{R}^{r\times n}}\|A_{S}X-A\|_{1}\geq
1.002\|\Delta\|_{1}$

###### Proof.

We first argue that for a fixed set $S,$ conditioned on $\|\Delta\|_{1}\leq
100n^{2}\ln n,$ with probability at least $1-1/2^{n^{\Theta(1)}},$

$\displaystyle\min_{X\in\mathbb{R}^{r\times n}}\|A_{S}X-A\|_{1}\geq
1.002\|\Delta\|_{1}.$

Then we can take a union bound over the at most $n^{r}=2^{n^{o(1)}}$ possible
choices of $S.$ It suffices to show for a fixed set $S,$
$\min_{X\in\mathbb{R}^{r\times n}}\|A_{S}X-A\|_{1}$ is not small.

Without loss of generality, let $S=[r],$ and we want to argue the cost

$\displaystyle\min_{X\in\mathbb{R}^{r\times
n}}\|A_{S}X-A\|_{1}\geq\min_{X\in\mathbb{R}^{r\times n}}\|A_{S}X_{[n]\setminus
S}-A_{[n]\setminus S}\|_{1}\geq 1.002\|\Delta\|_{1}.$

Due to Lemma B.2, with probability at least $1-O(1/\log\log n),$
$\|\Delta\|_{1}\leq 4.0002/\pi\cdot n^{2}\ln n.$ Now, we can condition on
$\|\Delta\|_{1}\leq 4.0002/\pi\cdot n^{2}\ln n.$

Consider $j\in[n]\setminus S.$ Due to Lemma B.6, with probability at least
$1-(1/n)^{\Theta(n)},$ for all $X_{j}\in\mathbb{R}^{r}$ with
$\|X_{j}\|_{1}\geq n^{c}$ for some constant $c>0,$ we have

$\displaystyle\|A_{S}X_{j}-A_{j}\|_{1}$
$\displaystyle=\|(\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+[\Delta_{S}\
\Delta_{j}])[X_{j}^{\top}\ -1]^{\top}\|_{1}\geq 0.9n^{3}.$

By taking a union bound over all $j\in[n]\setminus S,$ with probability at
least $1-(1/n)^{\Theta(n)},$ for all $X\in\mathbb{R}^{r\times n}$ with
$\exists j\in[n]\setminus S,\|X_{j}\|_{1}\geq n^{c},$ we have

$\displaystyle\|A_{S}X-A\|_{1}\geq 0.9n^{3}.$

Thus, we only need to consider the case $\forall j\in[n]\setminus
S,\|X_{j}\|_{1}\leq n^{c}.$ Notice that we condition on $\|\Delta\|_{1}\leq
4.0002/\pi\cdot n^{2}\ln n.$ By Fact B.1, we have that if $\|X_{j}\|_{1}\leq
n^{c}$ and $|1-\mathbf{1}^{\top}X_{j}|>1-10^{-20},$ then
$\|A_{S}X-A\|_{1}\geq\|A_{S}X_{j}-A_{j}\|_{1}>n^{3}.$

Thus, we only need to consider the case $\forall j\in[n]\setminus
S,\|X_{j}\|_{1}\leq n^{c},|1-\mathbf{1}^{\top}X_{j}|\leq 1-10^{-20}.$ $\forall
X\in\mathbb{R}^{r\times n}$ with $\forall j\in[n]\setminus S,\|X_{j}\|_{1}\leq
n^{c},|1-\mathbf{1}^{\top}X_{j}|\leq 1-10^{-20},$ if $\|A_{S}X_{[n]\setminus
S}-A_{[n]\setminus S}\|_{1}\leq 4n^{2}\ln n,$ then

$\displaystyle\|A_{S}X_{[n]\setminus S}-A_{[n]\setminus S}\|_{1}$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\|(\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta_{S})X_{[n]\setminus
S}-(\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta_{[n]\setminus S})\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\sum_{i\in[n],j\in[n]\setminus S,|\Delta_{i,j}|\geq
n^{1.0002}}|(((\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta_{S})X_{[n]\setminus
S}-\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top})-\Delta_{[n]\setminus S})_{i,j}|$
$\displaystyle+\sum_{i\in[n],j\in[n]\setminus
S,|\Delta_{i,j}|<n^{0.9999}}|((\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta_{S})X_{[n]\setminus
S}-(\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta_{[n]\setminus
S}))_{i,j}|$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1.996}{\pi}\cdot n^{2}\ln n+\sum_{i\in[n],j\in[n]\setminus
S,|\Delta_{i,j}|<n^{0.9999}}|((\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta_{S})X_{[n]\setminus
S}-(\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta_{[n]\setminus
S}))_{i,j}|$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{1.996}{\pi}\cdot n^{2}\ln n+\sum_{j\in[n]\setminus
S}\sum_{i\in[n],|\Delta_{i,j}|<n^{0.9999}}|((\eta\cdot\mathbf{1}\cdot\mathbf{1}^{\top}+\Delta_{S})X_{j}-\eta\cdot\mathbf{1}-\Delta_{j})_{i}|$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle\frac{1.996}{\pi}\cdot
n^{2}\ln n+\sum_{j\in[n]\setminus S}\frac{2.024}{\pi}n\ln n$
$\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle\frac{1.996}{\pi}\cdot
n^{2}\ln n+\frac{2.023}{\pi}n^{2}\ln n$ $\displaystyle\geq\leavevmode\nobreak\
$ $\displaystyle\frac{4.01}{\pi}\cdot n^{2}\ln n$

holds with probability at least $1-1/2^{n^{\Theta}(1)}.$ The first equality
follows by the definition of $A$. The first inequality follows by the
partition by $|\Delta_{i,j}|.$ Notice that $[\mathbf{1}\ \Delta_{S}]$ has rank
at most $r+1=n^{o(1)}.$ Then, due to Lemma B.13, and the condition
$\|A_{S}X_{[n]\setminus S}-A_{[n]\setminus S}\|_{1}\leq 4n^{2}\ln n,$ the
second inequality holds with probability at least $1-1/2^{n^{\Theta(1)}}.$ The
second equality follows by grouping the cost by each column. The third
inequality holds with probability at least $1-1/2^{n^{\Theta(1)}}$ by Lemma
B.19, and a union bound over all the columns in $[n]\setminus S.$ The fourth
inequality follows by $n-r=n-n^{o(1)}\geq(1-10^{-100})n.$

Thus, conditioned on $\|\Delta\|_{1}\leq 4.0002/\pi\cdot n^{2}\ln n,$ with
probability at least $1-1/2^{n^{\Theta(1)}},$ we have
$\min_{X\in\mathbb{R}^{r\times n}}\|A_{S}X-A\|_{1}\geq\frac{4.02}{\pi}\cdot
n^{2}\ln n.$ By taking a union bound over all the ${n\choose r}=2^{n^{o(1)}}$
choices of $S,$ we have that conditioned on
$\|\Delta\|_{1}\leq\frac{4.0002}{\pi}n^{2}\ln n,$ with probability at least
$1-1/2^{n^{\Theta(1)}},$ $\forall S\subset[n]$ with $|S|=r=n^{o(1)},$
$\min_{X\in\mathbb{R}^{r\times n}}\|A_{S}X-A\|_{1}\geq\frac{4.02}{\pi}\cdot
n^{2}\ln n.$ Since $4.01/4.0002>1.002,$

$\displaystyle\min_{X\in\mathbb{R}^{r\times n}}\|A_{S}X-A\|_{1}\geq
1.002\|\Delta\|_{1}.$

Since $\|\Delta\|_{1}\leq\frac{4.0002}{\pi}n^{2}\ln n$ happens with
probability at least $1-O(1/\log\log n),$ this completes the proof. ∎