$O_{q}(n\cdot\operatorname{poly}(k,1/\epsilon))$ time for any constant $p$,
and $\max_{i\in[q]}n_{i}\leq n$.

Algorithm 15 Fast Tensor Leverage Score Sampling, for General $q$-th Order

1:procedure
FastTensorLeverageScoreGeneralOrder($\\{U_{i}\\}_{i\in[q]},\\{n_{i}\\}_{i\in[q]},k,\epsilon,R_{\text{samples}}$)
$\triangleright$ Theorem C.46

2: $s_{1}\leftarrow\operatorname{poly}(k,1/\epsilon)$.

3: Choose $\Pi_{0},\Pi_{1}\in\mathbb{R}^{n_{1}n_{2}\cdots n_{q}\times s_{1}}$
to each be a TensorSketch. $\triangleright$ Definition B.34

4: Compute $R^{-1}\in\mathbb{R}^{k\times k}$ by using $(U_{1}\odot
U_{2}\odot\cdots\odot U_{q})\Pi_{0}$. $\triangleright$
$U_{i}\in\mathbb{R}^{k\times n_{i}},\forall i\in[q]$

5: $V_{0}\leftarrow R^{-1}$, $n_{0}\leftarrow k$.

6: for $i=1\to[n_{0}]$ do

7: $\alpha_{i}\leftarrow\|(V_{0})^{i}((U_{1}\odot U_{2}\odot\cdots\odot
U_{q})\Pi_{1})\|_{2}^{2}$.

8: end for

9: for $r=1\to R_{\text{samples}}$ do

10: Sample $\widehat{j}_{0}$ from $[n_{0}]$ with probability
$\alpha_{i}/\sum_{i^{\prime}=1}^{n_{0}}\alpha_{i^{\prime}}$.

11: for $l=1\to q-1$ do

12: $s_{l+1}\leftarrow O_{q}(\operatorname{poly}(k,1/\epsilon))$.

13: Choose $\Pi_{l+1}\in\mathbb{R}^{n_{l+1}\cdots n_{q}\times s_{l+1}}$ to be
a TensorSketch.

14: for $j_{l}=1\to[n_{l}]$ do $\triangleright$ Form
$V_{l}\in\mathbb{R}^{n_{l}\times k}$

15:
$(V_{l})^{j_{l}}\leftarrow(V_{l-1})^{\widehat{j}_{l-1}}\circ(U_{l})_{j_{l}}^{\top}$.

16: end for

17: for $i=1\to n_{q}$ do

18: $\beta_{i}\leftarrow\|(V_{l})^{i}((U_{l+1}\odot\cdots\odot
U_{q})\Pi_{l+1})\|_{2}^{2}$.

19: end for

20: Sample $\widehat{j}_{l}$ from $[n_{l}]$ with probability
$\beta_{i}/\sum_{i^{\prime}=1}^{n_{l}}\beta_{i^{\prime}}$.

21: end for

22: for $i=1\to n_{q}$ do

23: $\beta_{i}\leftarrow|(V_{q-1})^{\widehat{j}_{q-1}}(U_{q})_{i}|^{2}$.

24: end for

25: Sample $\widehat{j}_{q}$ from $[n_{q}]$ with probability
$\beta_{i}/\sum_{i^{\prime}=1}^{n_{q}}\beta_{i^{\prime}}$.

26: ${\cal S}\leftarrow{\cal S}\cup(\widehat{j}_{1},\cdots,\widehat{j}_{q})$.

27: end for

28: Convert ${\cal S}$ into a diagonal matrix $D$ with at most
$R_{\text{samples}}$ nonzero entries.

29: return $D$. $\triangleright$ Diagonal matrix
$D\in\mathbb{R}^{n_{1}n_{2}\cdots n_{q}\times n_{1}n_{2}\cdots n_{q}}$

30:end procedure

######  Theorem C.46.

Given $q$ matrices $U_{1}\in\mathbb{R}^{k\times n_{1}}$,
$U_{2}\in\mathbb{R}^{k\times n_{2}}$, $\cdots$, $U_{q}\in\mathbb{R}^{k\times
n_{q}}$, let $\max_{i}n_{i}\leq n$. There exists an algorithm that takes
$O_{q}(n\cdot\operatorname{poly}(k,1/\epsilon)\cdot R_{\mathrm{samples}})$
time and samples $R_{\mathrm{samples}}$ columns of $U_{1}\odot
U_{2}\odot\cdots\odot U_{q}\in\mathbb{R}^{k\times\prod_{i=1}^{q}n_{i}}$
according to the leverage scores of $U_{1}\odot U_{2}\odot\cdots\odot U_{q}$.

###### Proof.

Let $\max_{i}n_{i}\leq n$. First, choosing $\Pi_{0}$ to be a TensorSketch, we
can compute $R^{-1}$ in $O_{q}(n\operatorname{poly}(k,1/\epsilon))$ time,
where $R$ is the $R$ in a QR-factorization. We want to sample columns from
$U_{1}\odot U_{2}\odot\cdots\odot U_{q}$ according to the square of the
$\ell_{2}$-norm of each column of $R^{-1}(U_{1}\odot U_{2}\odot\cdots U_{q})$.
The issue is the number of columns of this matrix is already
$\prod_{i=1}^{q}n_{i}$. The goal is to sample columns from $R^{-1}(U_{1}\odot
U_{2}\odot\cdots U_{q})$ without explicitly computing the square of the
$\ell_{2}$-norm of each column.

Similarly as in the proof of Lemma C.32, we have the observation that the
following two sampling procedures are equivalent in terms of sampling a column
of a matrix: (1) We sample a single entry from matrix $R^{-1}(U_{1}\odot
U_{2}\odot\cdots\odot U_{q})$ proportional to its squared value, (2) We sample
a column from matrix $R^{-1}(U_{1}\odot U_{2}\odot\cdots\odot U_{q})$
proportional to its squared $\ell_{2}$-norm. Let the
$(i,j_{1},j_{2},\cdots,j_{q})$-th entry denote the entry in the $i$-th row and
the $j$-th column, where

$\displaystyle j=\sum_{l=1}^{q-1}(j_{l}-1)\prod_{t=l+1}^{q}n_{t}+j_{q}.$

Similarly to Equation (C.7.4), we can show, for a particular column $j$,

$\displaystyle\Pr[\text{we\leavevmode\nobreak\ sample\leavevmode\nobreak\
an\leavevmode\nobreak\ entry\leavevmode\nobreak\ from\leavevmode\nobreak\
the\leavevmode\nobreak\ }j\text{-th\leavevmode\nobreak\
column\leavevmode\nobreak\ of\leavevmode\nobreak\
matrix}]=\Pr[\text{we\leavevmode\nobreak\ sample\leavevmode\nobreak\
the\leavevmode\nobreak\ }j\text{-th\leavevmode\nobreak\
column\leavevmode\nobreak\ of\leavevmode\nobreak\ a\leavevmode\nobreak\
matrix}].$

Thus, it is sufficient to show how to sample a single entry from matrix
$R^{-1}(U_{1}\odot U_{2}\odot\cdots\odot U_{q})$ proportional to its squared
value without writing down all the entries of the
$k\times\prod_{i=1}^{q}n_{i}$ matrix.

Let $V_{0}$ denote $R^{-1}$. Let $n_{0}$ denote the number of rows of $V_{0}$.

In the next few paragraphs, we describe a sampling procedure (procedure
FastTensorLeverageScoreGeneralOrder in Algorithm 15) which first samples
$\widehat{j}_{0}$ from $[n_{0}]$, then samples $\widehat{j}_{1}$ from
$[n_{1}]$, $\cdots$, and at the end samples $\widehat{j}_{q}$ from $[n_{q}]$.

In the first step, we want to sample $\widehat{j}_{0}$ from $[n_{0}]$
proportional to the squared $\ell_{2}$-norm of that row. To do this
efficiently, we choose $\Pi_{1}\in\mathbb{R}^{\prod_{i=1}^{q}n_{i}\times
s_{1}}$ to be a TensorSketch to sketch on the right of $V_{0}(U_{1}\odot
U_{2}\odot\cdots\odot U_{q})$. By Section B.10, as long as
$s_{1}=O_{q}(\operatorname{poly}(k,1/\epsilon))$, then $\Pi_{1}$ is a
$(1\pm\epsilon)$-subspace embedding matrix. Thus with probability
$1-1/\Omega(q)$, for all $i\in[n_{0}]$,

$\displaystyle\|(V_{0})^{i}((U_{1}\odot U_{2}\odot\cdots\odot
U_{q})\Pi_{1})\|_{2}^{2}=(1\pm\epsilon)\|(V_{0})^{i}((U_{1}\odot
U_{2}\odot\cdots\odot U_{q}))\|_{2}^{2},$

which means we can sample $\widehat{j}_{0}$ from $[n_{0}]$ in
$O_{q}(n\operatorname{poly}(k,1/\epsilon))$ time.

In the second step, we have already obtained $\widehat{j}_{0}$. Using that row
of $V_{0}$ with $U_{1}$, we can form a new matrix
$V_{1}\in\mathbb{R}^{n_{1}\times k}$ in the following sense,

$\displaystyle(V_{1})^{i}=(V_{0})^{\widehat{j}_{0}}\circ(U_{1})_{i}^{\top},\forall
i\in[n_{1}],$

where $(V_{1})^{i}$ denotes the $i$-th row of matrix $V_{1}$,
$(V_{0})^{\widehat{j}_{0}}$ denotes the $\widehat{j}_{0}$-th row of $V_{0}$
and $(U_{1})_{i}$ is the $i$-th column of $U_{1}$. Another important
observation is, the entry in the $(j_{1},j_{2},\cdots,j_{q})$-th coordinate of
vector $(V_{0})^{\widehat{j}_{0}}(U_{1}\odot U_{2}\odot\cdots\odot U_{q})$ is
the same as the entry in the $j_{1}$-th row and $(j_{2},\cdots,j_{q})$-th
column of matrix $V_{1}(U_{2}\odot U_{3}\odot\cdots\odot U_{q})$. Thus,
sampling $j_{1}$ is equivalent to sampling $j_{1}$ from the new matrix
$V_{1}(U_{2}\odot U_{3}\odot\cdots\odot U_{q})$ proportional to the squared
$\ell_{2}$-norm of that row. We still have the computational issue that the
length of the row vector is very long. To deal with this, we can choose
$\Pi_{2}\in\mathbb{R}^{\prod_{i=2}^{q}n_{i}\times s_{2}}$ to be a TensorSketch
to multiply on the right of $V_{1}(U_{2}\odot U_{3}\odot\cdots\odot U_{q})$.

By Section B.10, as long as $s_{2}=O_{q}(\operatorname{poly}(k,1/\epsilon))$,
then $\Pi_{2}$ is a $(1\pm\epsilon)$-subspace embedding matrix. Thus with
probability $1-1/\Omega(q)$, for all $i\in[n_{1}]$,

$\displaystyle\|(V_{1})^{i}((U_{2}\odot\cdots\odot
U_{q})\Pi_{2})\|_{2}^{2}=(1\pm\epsilon)\|(V_{1})^{i}((U_{2}\odot\cdots\odot
U_{q}))\|_{2}^{2},$

which means we can sample $\widehat{j}_{1}$ from $[n_{1}]$ in
$O_{q}(n\operatorname{poly}(k,1/\epsilon))$ time.

We repeat the above procedure until we obtain each of
$\widehat{j}_{0},\widehat{j}_{1},\cdots,\widehat{j}_{q}$. Note that the last
one, $\widehat{j}_{q}$, is easier, since the length of the vector is already
small enough, and so we do not need to use TensorSketch for it.

By Section B.10, the time for multiplying by TensorSketch is
$O_{q}(n\operatorname{poly}(k,1/\epsilon))$. Setting $\epsilon$ to be a small
constant, and taking a union bound over $O(q)$ events completes the proof. ∎

######  Lemma C.47.

Given $A\in\mathbb{R}^{n_{0}\times\prod_{i=1}^{q}n_{i}}$,
$U_{1},U_{2},\cdots,U_{q}\in\mathbb{R}^{k\times n}$, for any $\epsilon>0$,
there exists an algorithm that runs in
$O(n\cdot\operatorname{poly}(k,1/\epsilon))$ time and outputs a diagonal
matrix $D\in\mathbb{R}^{\prod_{i=1}^{q}n_{i}\times\prod_{i=1}^{q}n_{i}}$ with
$m=O(k\log k+k/\epsilon)$ nonzero entries such that,

$\displaystyle\|\widehat{U}(U_{1}\odot U_{2}\odot\cdots\odot
U_{q})-A\|_{F}^{2}\leq(1+\epsilon)\min_{U\in\mathbb{R}^{n\times
k}}\|U(U_{1}\odot U_{2}\odot\cdots\odot U_{q})-A\|_{F}^{2},$

holds with probability at least $0.999$, where $\widehat{U}$ denotes the
optimal solution of

$\displaystyle\min_{U\in\mathbb{R}^{n_{0}\times k}}\|U(U_{1}\odot
U_{2}\odot\cdots\odot U_{q})D-AD\|_{F}^{2}.$

###### Proof.

This follows by combining Theorem C.46, Corollary C.30, and Lemma C.31. ∎

####  C.10.2 General iterative existential proof

Algorithm 16 General $q$-th Order Iterative Existential Proof

1:procedure GeneralIterativeExistentialProof($A,n,k,q,\epsilon$)
$\triangleright$ Section C.10.2

2: Fix $U_{1}^{*},U_{2}^{*},\cdots,U_{q}^{*}\in\mathbb{R}^{n\times k}$.

3: for $i=1\to q$ do

4: Choose sketching matrix $S_{i}\in\mathbb{R}^{n^{q-1}\times s_{i}}$ with
$s_{i}=O_{q}(k/\epsilon)$.

5: Define $Z_{i}\in\mathbb{R}^{k\times n^{q-1}}$ to be
$\underset{j<i}{\odot}\widehat{U}_{j}^{\top}\odot\underset{j^{\prime}>i}{\odot}U^{*\top}_{j^{\prime}}$.

6: Let $A_{i}$ denote the matrix obtained by flattening tensor $A$ along the
$i$-th dimension.

7: Define $\widehat{U}_{i}$ to be $A_{i}S_{i}(Z_{i}S_{i})^{\dagger}$.

8: end for

9: return $\widehat{U}_{1},\widehat{U}_{2},\cdots,\widehat{U}_{q}$.

10:end procedure

Given a $q$-th order tensor $A\in\mathbb{R}^{n\times n\times\cdots\times n}$,
we fix $U_{1}^{*},U_{2}^{*},\cdots,U_{q}^{*}\in\mathbb{R}^{n\times k}$ to be
the best rank-$k$ solution (if it does not exist, then we replace it by a good
approximation, as discussed). We define $\operatorname{OPT}=\|U_{1}^{*}\otimes
U_{2}^{*}\otimes\cdots\otimes U_{q}^{*}-A\|_{F}^{2}$. Our iterative proof
works as follows. We first obtain the objective function,

$\displaystyle\min_{U_{1}\in\mathbb{R}^{n\times k}}\|U_{1}\cdot
Z_{1}-A_{1}\|_{F}^{2}\leq\operatorname{OPT},$

where $A_{1}$ is a matrix obtained by flattening tensor $A$ along the first
dimension, $Z_{1}=(U_{2}^{*\top}\odot U_{3}^{*\top}\odot\cdots\odot
U_{q}^{*\top})$ denotes a $k\times n^{q-1}$ matrix. Choosing
$S_{1}\in\mathbb{R}^{n^{q-1}\times s_{1}}$ to be a Gaussian sketching matrix
with $s_{1}=O(k/\epsilon)$, we obtain a smaller problem,

$\displaystyle\min_{U_{1}\in\mathbb{R}^{n\times k}}\|U_{1}\cdot
Z_{1}S_{1}-A_{1}S_{1}\|_{F}^{2}.$

We define $\widehat{U}_{1}$ to be
$A_{1}S_{1}(Z_{1}S_{1})^{\dagger}\in\mathbb{R}^{n\times k}$, which gives,

$\displaystyle\|\widehat{U}_{1}\cdot
Z_{1}-A_{1}\|_{F}^{2}\leq(1+\epsilon)\operatorname{OPT}.$

After retensorizing the above, we have,

$\displaystyle\|\widehat{U}_{1}\otimes U_{2}^{*}\otimes\cdots\otimes
U_{q}^{*}-A\|_{F}^{2}\leq(1+\epsilon)\operatorname{OPT}.$

In the second round, we fix $\widehat{U}_{1}$, $U_{3}^{*}$, $\cdots$,
$U_{q}^{*}\in\mathbb{R}^{n\times k}$, and choose
$S_{2}\in\mathbb{R}^{n^{q-1}\times s_{2}}$ to be a Gaussian sketching matrix
with $s_{2}=O(k/\epsilon)$. We define $Z_{2}\in\mathbb{R}^{k\times n^{q-1}}$
to be $(\widehat{U}_{1}^{\top}\odot U_{3}^{*\top}\odot\cdots\odot
U_{q}^{*\top})$. We define $\widehat{U}_{2}$ to be
$A_{2}S_{2}(Z_{2}S_{2})^{\dagger}\in\mathbb{R}^{n\times k}$. Then, we have

$\displaystyle\|\widehat{U}_{1}\otimes\widehat{U}_{2}\otimes
U_{3}^{*}\otimes\cdots\otimes
U_{q}^{*}-A\|_{F}^{2}\leq(1+\epsilon)^{2}\operatorname{OPT}.$

We repeat the above process, where in the $i$-th round we fix
$\widehat{U}_{1},\cdots,\widehat{U}_{i-1}$, $U_{i+1}^{*}$, $\cdots$,
$U_{q}^{*}\in\mathbb{R}^{n\times k}$, and choose
$S_{i}\in\mathbb{R}^{n^{q-1}\times s_{i}}$ to be a Gaussian sketching matrix
with $s_{i}=O(k/\epsilon)$. We define $Z_{i}\in\mathbb{R}^{k\times n^{q-1}}$
to be $(\widehat{U}_{1}^{\top}\odot\cdots\odot\widehat{U}_{i-1}^{\top}\odot
U_{i+1}^{*\top}\odot\cdots\odot U_{q}^{*\top})$. We define $\widehat{U}_{i}$
to be $A_{i}S_{i}(Z_{i}S_{i})^{\dagger}\in\mathbb{R}^{n\times k}$. Then, we
have

$\displaystyle\|\widehat{U}_{1}\otimes\cdots\otimes\widehat{U}_{i-1}\otimes\widehat{U}_{i}\otimes
U_{i+1}^{*}\otimes\cdots\otimes
U_{q}^{*}-A\|_{F}^{2}\leq(1+\epsilon)^{2}\operatorname{OPT}.$

At the end of the $q$-th round, we have

$\displaystyle\|\widehat{U}_{1}\otimes\cdots\otimes\widehat{U}_{q}-A\|_{F}^{2}\leq(1+\epsilon)^{q}\operatorname{OPT}.$

Replacing $\epsilon=\epsilon^{\prime}/(2q)$, we obtain

$\displaystyle\|\widehat{U}_{1}\otimes\cdots\otimes\widehat{U}_{q}-A\|_{F}^{2}\leq(1+\epsilon^{\prime})\operatorname{OPT}.$

where for all $i\in[q]$,
$s_{i}=O(kq/\epsilon^{\prime})=O_{q}(k/\epsilon^{\prime})$ .

####  C.10.3 General input sparsity reduction

This section shows how to extend the input sparsity reduction from third order
tensors to general $q$-th order tensors. Given a tensor
$A\in\mathbb{R}^{n\times n\times\cdots\times n}$ and $q$ matrices, for each
$i\in[q]$, matrix $V_{i}$ has size $V_{i}\in\mathbb{R}^{n\times b_{i}}$, with
$b_{i}\leq\operatorname{poly}(k,1/\epsilon)$. We choose a batch of sparse
embedding matrices $T_{i}\in\mathbb{R}^{t_{i}\times n}$. Define
$\widehat{V}_{i}=T_{i}V_{i}$, and $C=A(T_{1},T_{2},\cdots,T_{q})$. Thus we
have with probability $99/100$, for any $\alpha\geq 0$, for all
$\\{X_{i},X_{i}^{\prime}\in\mathbb{R}^{b_{i}\times k}\\}_{i\in[q]}$, if

$\displaystyle\|\widehat{V}_{1}X_{1}^{\prime}\otimes\widehat{V}_{2}X_{2}^{\prime}\otimes\cdots\otimes\widehat{V}_{q}X_{q}^{\prime}-C\|_{F}^{2}\leq\alpha\|\widehat{V}_{1}X_{1}\otimes\widehat{V}_{2}X_{2}\otimes\cdots\otimes\widehat{V}_{q}X_{q}-C\|_{F}^{2},$

then

$\displaystyle\|V_{1}X_{1}^{\prime}\otimes
V_{2}X_{2}^{\prime}\otimes\cdots\otimes
V_{q}X_{q}^{\prime}-A\|_{F}^{2}\leq(1+\epsilon)\alpha\|V_{1}X_{1}\otimes
V_{2}X_{2}\otimes\cdots\otimes V_{q}X_{q}-A\|_{F}^{2},$

where $t_{i}=O_{q}(\operatorname{poly}(b_{i},1/\epsilon))$.

Algorithm 17 General $q$-th Order Input Sparsity Reduction

1:procedure
GeneralInputSparsityReduction($A,\\{V_{i}\\}_{i\in[q]},n,k,q,\epsilon$)
$\triangleright$ Section C.10.3

2: for $i=1\to q$ do

3: Choose sketching matrix $T_{i}\in\mathbb{R}^{t_{i}\times n}$ with
$t_{i}=\operatorname{poly}(k,q,1/\epsilon)$.

4: $\widehat{V}_{i}\leftarrow T_{i}V_{i}$.

5: end for

6: $C\leftarrow A(T_{1},T_{2},\cdots,T_{q})$.

7: return $\\{\widehat{V}_{i}\\}_{i\in[q]},C$.

8:end procedure

####  C.10.4 Bicriteria algorithm

This section explains how to extend the bicriteria algorithm from third order
tensors (Section C.4) to general $q$-th order tensors. Given any $q$-th order
tensor $A\in\mathbb{R}^{n\times n\times\cdots\times n}$, we can output a
$\operatorname{rank}$-$r$ tensor (or equivalently $q$ matrices
$U_{1},U_{2},\cdots,U_{q}\in\mathbb{R}^{n\times r}$) such that,

$\displaystyle\|U_{1}\otimes U_{2}\otimes\cdots\otimes
U_{q}-A\|_{F}^{2}\leq(1+\epsilon)\operatorname{OPT},$

where $r=O_{q}((k/\epsilon)^{q-1})$ and the algorithm takes
$O_{q}(\operatorname{nnz}(A)+n\cdot\operatorname{poly}(k,1/\epsilon))$.

Algorithm 18 General $q$-th Order Bicriteria Algorithm

1:procedure GeneralBicriteriaAlgorithm($A,n,k,q,\epsilon$) $\triangleright$
Section C.10.4

2: for $i=2\to q$ do

3: Choose sketching matrix $S_{i}\in\mathbb{R}^{n^{q-1}\times s_{i}}$ with
$s_{i}=O(kq/\epsilon)$.

4: Choose sketching matrix $T_{i}\in\mathbb{R}^{t_{i}\times n}$ with
$t_{i}=\operatorname{poly}(k,q,1/\epsilon)$.

5: Form matrix $\widehat{U}_{i}$ by setting $(j_{2},j_{3},\cdots,j_{q})$-th
column to be $(A_{i}S_{i})_{j_{i}}$.

6: end for

7: Solve $\min_{U_{1}}\|U_{1}B-(A(I,T_{2},\cdots,T_{q}))_{1}\|_{F}^{2}$.

8: return $\\{\widehat{U}_{i}\\}_{i\in[q]}$.

9:end procedure

####  C.10.5 CURT decomposition

This section extends the tensor CURT algorithm from $3$rd order tensors
(Section C.7) to general $q$-th order tensors. Given a $q$-th order tensor
$A\in\mathbb{R}^{n\times n\times\cdots\times n}$ and a batch of matrices
$U_{1},U_{2},\cdots,U_{q}\in\mathbb{R}^{n\times k}$, we iteratively apply the
proof in Theorem C.40 (or Theorem C.41) $q$ times. Then for each $i\in[q]$, we
are able to select $d_{i}$ columns from the $i$-th dimension of tensor $A$
(let $C_{i}$ denote those columns) and also find a tensor
$U\in\mathbb{R}^{d_{1}\times d_{2}\times\cdots\times d_{q}}$ such that,

$\displaystyle\|U(C_{1},C_{2},\cdots,C_{q})-A\|_{F}^{2}\leq(1+\epsilon)\|U_{1}\otimes
U_{2}\otimes\cdots\otimes U_{q}-A\|_{F}^{2},$

where either $d_{i}=O_{q}(k\log k+k/\epsilon)$ (similar to Theorem C.40) or
$d_{i}=O_{q}(k/\epsilon)$ (similar to Theorem C.41).

Algorithm 19 General $q$-th Order CURT Decomposition

1:procedure GeneralCURTDecomposition($A,\\{U_{i}\\}_{i\in[q]},n,k,q,\epsilon$)
$\triangleright$ Section C.10.5

2: for $i=1\to q$ do

3: Form
$B_{i}=\underset{j<i}{\odot}\widehat{U}_{j}^{\top}\odot\underset{j>i}{\odot}U_{j}^{\top}\in\mathbb{R}^{k\times
n^{q-1}}$.

4: if fast = true then $\triangleright$ Optimal running time

5: $\epsilon_{0}\leftarrow 0.01$.

6: $d_{i}\leftarrow O_{q}(k\log k+k/\epsilon)$.

7: $D_{i}\leftarrow$ FastTensorLeverageScoreGeneralOrder
$(\\{\widehat{U}_{j}\\}_{j<i},\\{U_{j}\\}_{j>i},n,k,\epsilon_{0},d_{i})$.
$\triangleright$ Algorithm 15

8: else$\triangleright$ Optimal sample complexity

9: $\epsilon_{0}\leftarrow O_{q}(\epsilon)$.

10: $D_{i}\leftarrow$ GeneralizedMatrixRowSubsetSelection
$(A_{i}^{\top},B_{i}^{\top},n^{q-1},n,k,\epsilon_{0})$. $\triangleright$
Algorithm C.5, $d_{i}=O_{q}(k/\epsilon)$.

11: end if

12: $\widehat{U}_{i}\leftarrow A_{i}D_{i}(B_{i}D_{i})^{\dagger}$.

13: $C_{i}\leftarrow A_{i}D_{i}$.

14: end for

15:
$U\leftarrow(B_{1}D_{1})^{\dagger}\otimes(B_{2}D_{2})^{\dagger}\otimes\cdots\otimes(B_{q}D_{q})^{\dagger}$.

16: return $\\{C_{i}\\}_{i\in[q]}$, $U$.

17:end procedure

###  C.11 Matrix CUR decomposition

There is a long line of research on matrix CUR decomposition under operator,
Frobenius or recently, entry-wise $\ell_{1}$ norm [DMM08, BMD09, DR10, BDM11,
BW14, SWZ17]. We provide the first algorithm that runs in
$\operatorname{nnz}(A)$ time, which improves the previous best matrix CUR
decomposition algorithm under Frobenius norm [BW14].

####  C.11.1 Algorithm

Algorithm 20 Optimal Matrix CUR Decomposition Algorithm

1:procedure OptimalMatrixCUR($A,n,k,\epsilon$) $\triangleright$ Theorem C.48

2: $\epsilon^{\prime}\leftarrow 0.1\epsilon$.
$\epsilon^{\prime\prime}\leftarrow 0.001\epsilon^{\prime}$.

3: $\widehat{U}\leftarrow$SparseSVD($A,k,\epsilon^{\prime}$). $\triangleright$
$\widehat{U}\in\mathbb{R}^{n\times k}$

4: Choose $S_{1}\in\mathbb{R}^{n\times n}$ to be a sampling and rescaling
diagonal matrix according to the leverage scores of $\widehat{U}$ with
$s_{1}=O(\epsilon^{-2}k\log k)$ nonzero entries.

5:
$R,Y\leftarrow$GeneralizedMatrixRowSubsetSelection$(S_{1}A,S_{1}\widehat{U},s_{1},n,k,\epsilon^{\prime\prime})$.
$\triangleright$ Algorithm 7, $R\in\mathbb{R}^{r\times
n},Y\in\mathbb{R}^{k\times r}$ and $r=O(k/\epsilon)$

6: $\widehat{V}\leftarrow YR\in\mathbb{R}^{k\times n}$.

7: Choose $S_{2}^{\top}\in\mathbb{R}^{n\times n}$ to be a sampling and
rescaling diagonal matrix according to the leverage scores of
$\widehat{V}^{\top}\in\mathbb{R}^{n\times k}$ with $s_{2}=O(\epsilon^{-2}k\log
k)$ nonzero entries.

8: $C^{\top},Z^{\top}\leftarrow$ GeneralizedMatrixRowSubsetSelection
$((AS_{2})^{\top},(\widehat{V}S_{2})^{\top},s_{2},n,k,\epsilon^{\prime\prime})$.
$\triangleright$ Algorithm 7, $C\in\mathbb{R}^{n\times
c},Z\in\mathbb{R}^{c\times k}$, and $c=O(k/\epsilon)$

9: $U\leftarrow ZY$. $\triangleright$ $U\in\mathbb{R}^{c\times r}$ and
$\operatorname{rank}(U)=k$

10: return $C,U,R$.

11:end procedure

######  Theorem C.48.

Given matrix $A\in\mathbb{R}^{n\times n}$, for any $k\geq 1$ and
$\epsilon\in(0,1)$, there exists an algorithm that takes
$O(\operatorname{nnz}(A)+n\operatorname{poly}(k,1/\epsilon))$ time and outputs
three matrices $C\in\mathbb{R}^{n\times c}$ with $c$ columns from $A$,
$R\in\mathbb{R}^{r\times n}$ with $r$ rows from $A$, and
$U\in\mathbb{R}^{c\times r}$ with $\operatorname{rank}(U)=k$ such that
$r=c=O(k/\epsilon)$ and,

$\displaystyle\|CUR-A\|_{F}^{2}\leq(1+\epsilon)\min_{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}}\|A_{k}-A\|_{F}^{2},$

holds with probability at least $9/10$.

###### Proof.

We define

$\displaystyle\operatorname{OPT}=\min_{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}}\|A_{k}-A\|_{F}^{2}.$

We first compute $\widehat{U}\in\mathbb{R}^{n\times k}$ by using the result of
[CW13], so that $\widehat{U}$ satisfies:

$\displaystyle\min_{X\in\mathbb{R}^{k\times
n}}\|\widehat{U}X-A\|_{F}^{2}\leq(1+\epsilon)\operatorname{OPT}.$ (25)

This step can be done in
$O(\operatorname{nnz}(A)+n\operatorname{poly}(k,1/\epsilon))$ time.

We choose $S_{1}\in\mathbb{R}^{n\times n}$ to be a sampling and rescaling
diagonal matrix according to the leverage scores of $\widehat{U}$, where here
$s_{1}=O(\epsilon^{-2}k\log k)$ is the number of samples. This step also can
be done in $O(n\operatorname{poly}(k,1/\epsilon))$ time.

We run GeneralizedMatrixRowSubsetSelection(Algorithm 7) on matrices $S_{1}A$
and $S_{1}\widehat{U}$. Then we obtain two new matrices $R$ and $Y$, where $R$
contains $r=O(k/\epsilon)$ rows of $S_{1}A$ and $Y$ has size $k\times r$.
According to Theorem C.14 and Corollary C.15, this step takes
$n\operatorname{poly}(k,1/\epsilon)$ time.

We construct $\widehat{V}=YR$, and choose $S_{2}^{\top}$ to be another
sampling and rescaling diagonal matrix according to the leverage scores of
$\widehat{V}^{\top}$ with $s_{2}=O(\epsilon^{-2}k\log k)$ nonzero entries. As
in the case of constructing $S_{1}$, this step can be done in
$O(n\operatorname{poly}(k,1/\epsilon))$ time.

We run GeneralizedMatrixRowSubsetSelection(Algorithm 7) on matrices
$(AS_{2})^{\top}$ and $(\widehat{V}S_{2})^{\top}$. Then we can obtain two new
matrices $C^{\top}$ and $Y^{\top}$, where $C^{\top}$ contains
$c=O(k/\epsilon)$ rows of $(AS_{2})^{\top}$ and $Z^{\top}$ has size $k\times
c$. According to Theorem C.14 and Corollary C.15, this step takes
$n\operatorname{poly}(k,1/\epsilon)$ time.

Thus, overall the running time is
$O(\operatorname{nnz}(A)+n\operatorname{poly}(k,1/\epsilon))$.

##### Correctness.

Let

$\displaystyle X^{*}=\arg\min_{X\in\mathbb{R}^{n\times
k}}\|X\widehat{V}-A\|_{F}^{2}.$

According to Corollary C.15,

$\displaystyle\|CZ\widehat{V}S_{2}-AS_{2}\|_{F}^{2}\leq(1+\epsilon^{\prime\prime})\min_{X\in\mathbb{R}^{n\times
k}}\|X\widehat{V}S_{2}-AS_{2}\|_{F}^{2}\leq(1+\epsilon^{\prime\prime})\|X^{*}\widehat{V}S_{2}-AS_{2}\|_{F}^{2}.$

According to Theorem C.52, $\epsilon^{\prime\prime}=0.001\epsilon^{\prime}$,

$\displaystyle\|CZ\widehat{V}-A\|_{F}^{2}\leq(1+\epsilon^{\prime})\|X^{*}\widehat{V}-A\|_{F}^{2}.$
(26)

Let

$\displaystyle\widetilde{X}=\arg\min_{X\in\mathbb{R}^{k\times
n}}\|\widehat{U}X-A\|_{F}^{2}.$

According to Corollary C.15,

$\displaystyle\|S_{1}\widehat{U}YR-
S_{1}A\|_{F}^{2}\leq(1+\epsilon^{\prime\prime})\min_{X\in\mathbb{R}^{k\times
n}}\|S_{1}\widehat{U}X-S_{1}A\|_{F}^{2}\leq(1+\epsilon^{\prime\prime})\|S_{1}\widehat{U}\widetilde{X}-S_{1}A\|_{F}^{2}.$

According to Theorem C.52, since
$\epsilon^{\prime\prime}=0.001\epsilon^{\prime}$,

$\displaystyle\|\widehat{U}YR-A\|_{F}^{2}\leq(1+\epsilon^{\prime})\|\widehat{U}\widetilde{X}-A\|_{F}^{2}.$
(27)

Then, we can conclude

$\displaystyle\|CUR-A\|_{F}^{2}=$ $\displaystyle\leavevmode\nobreak\
\|CZYR-A\|_{F}^{2}$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\|CZ\widehat{V}-A\|_{F}^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
(1+\epsilon^{\prime})\min_{X\in\mathbb{R}^{n\times
k}}\|X\widehat{V}-A\|_{F}^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
(1+\epsilon^{\prime})\|\widehat{U}\widehat{V}-A\|_{F}^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
(1+\epsilon^{\prime})^{2}\min_{X\in\mathbb{R}^{k\times
n}}\|\widehat{U}X-A\|_{F}^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
(1+\epsilon^{\prime})^{3}\operatorname{OPT}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ (1+\epsilon)\operatorname{OPT}.$

The first equality follows since $U=ZY$. The second equality follows since
$YR=\widehat{V}$. The first inequality follows by Equation (26). The third
inequality follows by Equation (27). The fourth inequality follows by Equation
(25). The last inequality follows since $\epsilon^{\prime}=0.1\epsilon$.

Notice that $C$ has $O(k/\epsilon)$ reweighted columns of $AS_{2}$, and
$AS_{2}$ is a subset of reweighted columns of $A$, so $C$ has $O(k/\epsilon)$
reweighted columns of $A$. Similarly, we can prove that $R$ has
$O(k/\epsilon)$ reweighted rows of $A$. Thus, $CUR$ is a CUR decomposition of
$A$.

∎

####  C.11.2 Stronger property achieved by leverage scores

######  Claim C.49.

Given matrix $A\in\mathbb{R}^{n\times m}$, for any distribution
$p=(p_{1},p_{2},\cdots,p_{n})$ define random variable $X$ such that
$X=\|A_{i}\|_{2}^{2}/p_{i}$ with probability $p_{i}$, where $A_{i}$ is the
$i$-th row of matrix $A$. Then take $m$ independent samples
$X^{1},X^{2},\cdots,X^{m}$, and let $Y=\frac{1}{m}\sum_{j=1}^{m}X^{j}$. We
have

$\displaystyle\Pr[Y\leq 100\|A\|_{F}^{2}]\geq.99.$

###### Proof.

We can compute the expectation of $X^{j}$, for any $j\in[m]$,

$\displaystyle\operatorname*{{\bf{E}}}[X^{j}]=\sum_{i=1}^{n}\frac{\|A_{i}\|_{2}^{2}}{p_{i}}\cdot
p_{i}=\|A\|_{F}^{2}.$

Then
$\operatorname*{{\bf{E}}}[Y]=\frac{1}{m}\sum_{j=1}^{m}\operatorname*{{\bf{E}}}[X^{j}]=\|A\|_{F}^{2}$.
Using Markov’s inequality, we have

$\displaystyle\Pr[Y\geq\|A\|_{F}^{2}]\leq.01.$

∎

######  Theorem C.50 (The leverage score case of Theorem 39 in [CW13]).

Let $A\in\mathbb{R}^{n\times k}$, $B\in\mathbb{R}^{n\times d}$. Let
$S\in\mathbb{R}^{n\times n}$ denote a sampling and rescaling diagonal matrix
according to the leverage scores of $A$. If the event occurs that $S$
satisfies $(\epsilon/\sqrt{k})$-Frobenius norm approximate matrix product for
$A$, and also $S$ is a $(1+\epsilon)$-subspace embedding for $A$, then let
$X^{*}$ be the optimal solution of $\min_{X}\|AX-B\|_{F}^{2},$ and
$\widetilde{B}\equiv AX^{*}-B$. Then, for all $X\in\mathbb{R}^{k\times d},$

$\displaystyle(1-2\epsilon)\|AX-B\|_{F}^{2}\leq\|S(AX-B)\|_{F}^{2}+\|\widetilde{B}\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}\leq(1+2\epsilon)\|AX-B\|_{F}^{2}.$

Furthermore, if $S$ has $m=O(\epsilon^{-2}k\log(k))$ nonzero entries, the
above event happens with probability at least $0.99$.

Note that Theorem 39 in [CW13] is stated in a way that holds for general
sketching matrices. However, we are only interested in the case when $S$ is a
sampling and rescaling diagonal matrix according to the leverage scores. For
completeness, we provide the full proof of the leverage score case with
certain parameters.

###### Proof.

Suppose $S$ is a sampling and rescaling diagonal matrix according to the
leverage scores of $A$, and it has $m=O(\epsilon^{-2}k\log k)$ nonzero
entries. Then, according to Lemma C.22, $S$ is a $(1+\epsilon)$-subspace
embedding for $A$ with probability at least $0.999$, and according to Lemma
C.29, $S$ satisfies $(\epsilon/\sqrt{k})$-Frobenius norm approximate matrix
product for $A$ with probability at least $0.999$.

Let $U\in\mathbb{R}^{n\times k}$ denote an orthonormal basis of the column
span of $A$. Then the leverage scores of $U$ are the same as the leverage
scores of $A$. Furthermore, for any $X\in\mathbb{R}^{k\times d}$, there is a
matrix $Y$ such that $AX=UY$, and vice versa, so we can now assume $A$ has $k$
orthonormal columns.

Then,

$\displaystyle\leavevmode\nobreak\
\|S(AX-B)\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\|SA(X-X^{*})+S(AX^{*}-B)\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\|SA(X-X^{*})\|_{F}^{2}+\|S(AX^{*}-B)\|_{F}^{2}+2\operatorname{tr}\left((X-X^{*})^{\top}A^{\top}S^{\top}S(AX^{*}-B)\right)-\|S\widetilde{B}\|_{F}^{2}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\underbrace{\|SA(X-X^{*})\|_{F}^{2}+2\operatorname{tr}\left((X-X^{*})^{\top}A^{\top}S^{\top}S\widetilde{B}\right)}_{\alpha}.$
(28)

The second equality follows using
$\|C+D\|_{F}^{2}=\|C\|_{F}^{2}+\|D\|_{F}^{2}+2\operatorname{tr}(C^{\top}D)$.
The third equality follows from $\widetilde{B}=AX^{*}-B$. Now, let us first
upper bound the term $\alpha$ in Equation (28):

$\displaystyle\leavevmode\nobreak\
\|SA(X-X^{*})\|_{F}^{2}+2\operatorname{tr}\left((X-X^{*})^{\top}A^{\top}S^{\top}S\widetilde{B}\right)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
(1+\epsilon)\|A(X-X^{*})\|_{F}^{2}+2\|X-X^{*}\|_{F}\|A^{\top}S^{\top}S\widetilde{B}\|_{F}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
(1+\epsilon)\|A(X-X^{*})\|_{F}^{2}+2(\epsilon/\sqrt{k})\cdot\|X-X^{*}\|_{F}\|A\|_{F}\|\widetilde{B}\|_{F}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
(1+\epsilon)\|A(X-X^{*})\|_{F}^{2}+2\epsilon\|A(X-X^{*})\|_{F}\|\widetilde{B}\|_{F}.$

The first inequality follows since $S$ is a $(1+\epsilon)$ subspace embedding
of $A$, and $\operatorname{tr}(C^{\top}D)\leq\|C\|_{F}\|D\|_{F}$. The second
inequality follows since $S$ satisfies $(\epsilon/\sqrt{k})$-Frobenius norm
approximate matrix product for $A$. The last inequality follows using that
$\|A\|_{F}\leq\sqrt{k}$ since $A$ only has $k$ orthonormal columns. Now, let
us lower bound the term $\alpha$ in Equation (28):

$\displaystyle\leavevmode\nobreak\
\|SA(X-X^{*})\|_{F}^{2}+2\operatorname{tr}\left((X-X^{*})^{\top}A^{\top}S^{\top}S\widetilde{B}\right)$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
(1-\epsilon)\|A(X-X^{*})\|_{F}^{2}-2\|X-X^{*}\|_{F}\|A^{\top}S^{\top}S\widetilde{B}\|_{F}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
(1-\epsilon)\|A(X-X^{*})\|_{F}^{2}-2(\epsilon/\sqrt{k})\cdot\|X-X^{*}\|_{F}\|A\|_{F}\|\widetilde{B}\|_{F}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
(1-\epsilon)\|A(X-X^{*})\|_{F}^{2}-2\epsilon\|A(X-X^{*})\|_{F}\|\widetilde{B}\|_{F}.$

The first inequality follows since $S$ is a $(1+\epsilon)$ subspace embedding
of $A$, and $\operatorname{tr}(C^{\top}D)\geq-\|C\|_{F}\|D\|_{F}$. The second
inequality follows since $S$ satisfies $(\epsilon/\sqrt{k})$-Frobenius norm
approximate matrix product for $A$. The last inequality follows using that
$\|A\|_{F}\leq\sqrt{k}$ since $A$ only has $k$ orthonormal columns.

Therefore,

$\displaystyle(1-\epsilon)\|A(X-X^{*})\|_{F}^{2}-2\epsilon\|A(X-X^{*})\|_{F}\|\widetilde{B}\|_{F}\leq\|S(AX-B)\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2},$
(29)

and

$\displaystyle(1+\epsilon)\|A(X-X^{*})\|_{F}^{2}+2\epsilon\|A(X-X^{*})\|_{F}\|\widetilde{B}\|_{F}\geq\|S(AX-B)\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}.$
(30)

Notice that $\widetilde{B}=AX^{*}-B=AA^{\dagger}B-B=(AA^{\dagger}-I)B,$ so
according to the Pythagorean theorem, we have

$\displaystyle\|AX-B\|_{F}^{2}=\|A(X-X^{*})\|_{F}^{2}+\|\widetilde{B}\|_{F}^{2},$

which means that

$\displaystyle\|A(X-X^{*})\|_{F}^{2}=\|AX-B\|_{F}^{2}-\|\widetilde{B}\|_{F}^{2}.$
(31)

Using Equation (31), we can rewrite and lower bound the $\mathrm{LHS}$ of
Equation (29),

$\displaystyle\leavevmode\nobreak\
(1-\epsilon)\|A(X-X^{*})\|_{F}^{2}-2\epsilon\|A(X-X^{*})\|_{F}\|\widetilde{B}\|_{F}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\|A(X-X^{*})\|_{F}^{2}-\epsilon\left(\|A(X-X^{*})\|_{F}^{2}+2\|A(X-X^{*})\|_{F}\|\widetilde{B}\|_{F}\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\|AX-B\|_{F}^{2}-\|\widetilde{B}\|_{F}^{2}-\epsilon\left(\|A(X-X^{*})\|_{F}^{2}+2\|A(X-X^{*})\|_{F}\|\widetilde{B}\|_{F}\right)$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
\|AX-B\|_{F}^{2}-\|\widetilde{B}\|_{F}^{2}-\epsilon\left(\|A(X-X^{*})\|_{F}+\|\widetilde{B}\|_{F}\right)^{2}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
\|AX-B\|_{F}^{2}-\|\widetilde{B}\|_{F}^{2}-2\epsilon\left(\|A(X-X^{*})\|_{F}^{2}+\|\widetilde{B}\|_{F}^{2}\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
(1-2\epsilon)\|AX-B\|_{F}^{2}-\|\widetilde{B}\|_{F}^{2}.$ (32)

The second step follows by Equation (31). The first inequality follows using
$a^{2}+2ab<(a+b)^{2}$. The second inequality follows using $(a+b)^{2}\leq
2(a^{2}+b^{2}).$ The last equality follows using
$\|A(X-X^{*})\|_{F}^{2}+\|\widetilde{B}\|_{F}^{2}=\|AX-B\|_{F}^{2}$.
Similarly, using Equation (31), we can rewrite and upper bound the
$\mathrm{LHS}$ of Equation (30)

$\displaystyle(1+\epsilon)\|A(X-X^{*})\|_{F}^{2}+2\epsilon\|A(X-X^{*})\|_{F}\|\widetilde{B}\|_{F}\leq(1+2\epsilon)\|AX-B\|_{F}^{2}-\|\widetilde{B}\|_{F}^{2}.$
(33)

Combining Equations (29),(C.11.2),(30),(33), we conclude that

$\displaystyle(1-2\epsilon)\|AX-B\|_{F}^{2}-\|\widetilde{B}\|_{F}^{2}\leq\|S(AX-B)\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}\leq(1+2\epsilon)\|AX-B\|_{F}^{2}-\|\widetilde{B}\|_{F}^{2}.$

∎

######  Theorem C.51.

Let $A\in\mathbb{R}^{n\times k}$, $B\in\mathbb{R}^{n\times d}$, and
$\frac{1}{2}>\epsilon>0$. Let $X^{*}$ be the optimal solution to
$\min_{X}\|AX-B\|_{F}^{2},$ and $\widetilde{B}\equiv AX^{*}-B$. Let
$S\in\mathbb{R}^{n\times n}$ denote a sketching matrix which satisfies the
following:

  1. 1.

$\|S\widetilde{B}\|_{F}^{2}\leq 100\cdot\|\widetilde{B}\|_{F}^{2},$

  2. 2.

for all $X\in\mathbb{R}^{k\times d},$

$\displaystyle(1-\epsilon)\|AX-B\|_{F}^{2}\leq\|S(AX-B)\|_{F}^{2}+\|\widetilde{B}\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}\leq(1+\epsilon)\|AX-B\|_{F}^{2}.$

Then, for all $X_{1},X_{2}\in\mathbb{R}^{k\times d}$ satisfying

$\displaystyle\|SAX_{1}-SB\|_{F}^{2}\leq\left(1+\frac{\epsilon}{100}\right)\cdot\|SAX_{2}-SB\|_{F}^{2},$

we have

$\displaystyle\|AX_{1}-B\|_{F}^{2}\leq(1+5\epsilon)\cdot\|AX_{2}-B\|_{F}^{2}.$

###### Proof.

Let $A,B,S,\epsilon$ be the same as in the statement of the theorem, and
suppose $S$ satisfies those two conditions. Let
$X_{1},X_{2}\in\mathbb{R}^{k\times d}$ satisfy

$\displaystyle\|SAX_{1}-SB\|_{F}^{2}\leq\left(1+\frac{\epsilon}{100}\right)\|SAX_{2}-SB\|_{F}^{2}.$

We have

$\displaystyle\leavevmode\nobreak\ \|AX_{1}-B\|_{F}^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\frac{1}{1-\epsilon}\left(\|S(AX_{1}-B)\|_{F}^{2}+\|\widetilde{B}\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}\right)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{1}{1-\epsilon}\left(\left(1+\frac{\epsilon}{100}\right)\cdot\|S(AX_{2}-B)\|_{F}^{2}+\|\widetilde{B}\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{1-\epsilon}\left(\left(1+\frac{\epsilon}{100}\right)\cdot\left(\|S(AX_{2}-B)\|_{F}^{2}+\|\widetilde{B}\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}\right)-\frac{\epsilon}{100}\cdot\left(\|\widetilde{B}\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}\right)\right)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{1}{1-\epsilon}\cdot\left(1+\frac{\epsilon}{100}\right)\cdot\|AX_{2}-B\|_{F}^{2}-\frac{1}{1-\epsilon}\cdot\frac{\epsilon}{100}\cdot\left(\|\widetilde{B}\|_{F}^{2}-\|S\widetilde{B}\|_{F}^{2}\right)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
(1+3\epsilon)\|AX_{2}-B\|_{F}^{2}+\frac{1}{1-\epsilon}\cdot\frac{\epsilon}{100}\|S\widetilde{B}\|_{F}^{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
(1+3\epsilon)\|AX_{2}-B\|_{F}^{2}+2\epsilon\|\widetilde{B}\|_{F}^{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
(1+5\epsilon)\|AX_{2}-B\|_{F}^{2}.$

The first inequality follows since $S$ satisfies the second condition. The
second inequality follows by the relationship between $X_{1}$ and $X_{2}$. The
third inequality follows since $S$ satisfies the second condition. The fifth
inequality follows using that $\epsilon<\frac{1}{2}$ and that $S$ satisfies
the first condition. The last inequality follows using that
$\|\widetilde{B}\|_{F}^{2}=\|AX^{*}-B\|_{F}^{2}\leq\|AX_{2}-B\|_{F}^{2}.$ ∎

######  Theorem C.52.

Let $A\in\mathbb{R}^{n\times k}$, $B\in\mathbb{R}^{n\times d}$, and
$\frac{1}{2}>\epsilon>0$. Let $S\in\mathbb{R}^{n\times n}$ denote a sampling
and rescaling diagonal matrix according to the leverage scores of $A$. If $S$
has at least $m=O(k\log(k)/\epsilon^{2})$ nonzero entries, then with
probability at least $0.98$, for all $X_{1},X_{2}\in\mathbb{R}^{k\times d}$
satisfying

$\displaystyle\|SAX_{1}-SB\|_{F}^{2}\leq(1+\frac{\epsilon}{500})\cdot\|SAX_{2}-SB\|_{F}^{2},$

we have

$\displaystyle\|AX_{1}-B\|_{F}^{2}\leq(1+\epsilon)\cdot\|AX_{2}-B\|_{F}^{2}.$

###### Proof.

The proof directly follows by Claim C.49, Theorem C.50 and Theorem C.51.
Because of Claim C.49, $S$ satisfies the first condition in the statement of
Theorem C.51 with probability at least $0.99$. According to Theorem C.50, $S$
satisfies the second condition in the statement of Theorem C.51 with
probability at least $0.99$. Thus, with probability $0.98$, by Theorem C.51,
we complete the proof. ∎

##  Appendix D Entry-wise $\ell_{1}$ Norm for Arbitrary Tensors

In this section, we provide several different algorithms for tensor
$\ell_{1}$-low rank approximation. Section D.1 provides some useful facts and
definitions. Section D.2 presents several existence results. Section D.3
describes a tool that is able to reduce the size of the objective function
from $\operatorname{poly}(n)$ to $\operatorname{poly}(k)$. Section D.4
discusses the case when the problem size is small. Section D.5 provides
several bicriteria algorithms. Section D.6 summarizes a batch of algorithms.
Section D.7 provides an algorithm for $\ell_{1}$ norm CURT decomposition.

Notice that if the $\operatorname{rank}-k$ solution does not exist, then every
bicriteria algorithm in Section D.5 can be stated in a form similar to Theorem
1.1, and every algorithm which can output a $\operatorname{rank}-k$ solution
in Section D.6 can be stated in a form similar to Theorem 1.2. See Section 1
for more details.

###  D.1 Facts

We present a method that is able to reduce the entry-wise $\ell_{1}$-norm
objective function to the Frobenius norm objective function.

######  Fact D.1.

Given a $3$rd order tensor $C\in\mathbb{R}^{c_{1}\times c_{2}\times c_{3}}$,
three matrices $V_{1}\in\mathbb{R}^{c_{1}\times b_{1}}$,
$V_{2}\in\mathbb{R}^{c_{2}\times b_{2}}$, $V_{3}\in\mathbb{R}^{c_{3}\times
b_{3}}$, for any $k\in[1,\min_{i}b_{i}]$, if
$X^{\prime}_{1}\in\mathbb{R}^{b_{1}\times
k},X^{\prime}_{2}\in\mathbb{R}^{b_{2}\times
k},X^{\prime}_{3}\in\mathbb{R}^{b_{3}\times k}$ satisfies that,

$\displaystyle\|(V_{1}X^{\prime}_{1})\otimes(V_{2}X^{\prime}_{2})\otimes(V_{3}X^{\prime}_{3})-C\|_{F}\leq\alpha\min_{X_{1},X_{2},X_{3}}\|(V_{1}X_{1})\otimes(V_{2}X_{2})\otimes(V_{3}X_{3})-C\|_{F},$

then

$\displaystyle\|(V_{1}X^{\prime}_{1})\otimes(V_{2}X^{\prime}_{2})\otimes(V_{3}X^{\prime}_{3})-C\|_{1}\leq\alpha\sqrt{c_{1}c_{2}c_{3}}\min_{X_{1},X_{2},X_{3}}\|(V_{1}X_{1})\otimes(V_{2}X_{2})\otimes(V_{3}X_{3})-C\|_{1}.$

We extend Lemma C.15 in [SWZ17] to tensors:

######  Fact D.2.

Given tensor $A\in\mathbb{R}^{n\times n\times n}$, let
$\operatorname{OPT}=\underset{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}}{\min}\|A-A_{k}\|_{1}$. For any $r\geq k$, if $\operatorname{rank}$-$r$
tensor $B\in\mathbb{R}^{n\times n\times n}$ is an $f$-approximation to $A$,
i.e.,

$\displaystyle\|B-A\|_{1}\leq f\cdot\operatorname{OPT},$

and $U,V,W\in\mathbb{R}^{n\times k}$ is a $g$-approximation to $B$, i.e.,

$\displaystyle\|U\otimes V\otimes W-B\|_{1}\leq
g\cdot\underset{\operatorname{rank}-k\leavevmode\nobreak\
B_{k}}{\min}\|B_{k}-B\|_{1},$

then,

$\displaystyle\|U\otimes V\otimes W-A\|_{1}\lesssim
gf\cdot\operatorname{OPT}.$

###### Proof.

We define $\widetilde{U},\widetilde{V},\widetilde{W}\in\mathbb{R}^{n\times k}$
to be three matrices, such that

$\displaystyle\|\widetilde{U}\otimes\widetilde{V}\otimes\widetilde{W}-B\|_{1}\leq
g\underset{\operatorname{rank}-k\leavevmode\nobreak\
B_{k}}{\min}\|B_{k}-B\|_{1},$

and also define,

$\displaystyle\widehat{U},\widehat{V},\widehat{W}=\underset{U,V,W\in\mathbb{R}^{n\times
k}}{\arg\min}\|U\otimes V\otimes W-B\|_{1}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}U^{*},V^{*},W^{*}=\underset{U,V,W\in\mathbb{R}^{n\times
k}}{\arg\min}\|U\otimes V\otimes W-A\|_{1}.$

It is obvious that,

$\displaystyle\|\widehat{U}\otimes\widehat{V}\otimes\widehat{W}-B\|_{1}\leq\|U^{*}\otimes
V^{*}\otimes W^{*}-B\|_{1}.$ (34)

Then,

$\displaystyle\leavevmode\nobreak\
\|\widetilde{U}\otimes\widetilde{V}\otimes\widetilde{W}-A\|_{1}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\|\widetilde{U}\otimes\widetilde{V}\otimes\widetilde{W}-B\|_{1}+\|B-A\|_{1}$
by the triangle inequality $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
g\|\widehat{U}\otimes\widehat{V}\otimes\widehat{W}-B\|_{1}+\|B-A\|_{1}$ by
definition $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
g\|U^{*}\otimes V^{*}\otimes W^{*}-B\|_{1}+\|B-A\|_{1}$ by Equation (34)
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ g\|U^{*}\otimes
V^{*}\otimes W^{*}-A\|_{1}+g\|B-A\|_{1}+\|B-A\|_{1}$ by the triangle
inequality $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
g\operatorname{OPT}+(g+1)\|B-A\|_{1}$ $\displaystyle\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ definition\leavevmode\nobreak\ of\leavevmode\nobreak\
}\operatorname{OPT}$ $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
g\operatorname{OPT}+(g+1)f\cdot\operatorname{OPT}$
$\displaystyle\text{\leavevmode\nobreak\ since\leavevmode\nobreak\
$B$\leavevmode\nobreak\ is\leavevmode\nobreak\ an\leavevmode\nobreak\
$f$-approximation\leavevmode\nobreak\ to\leavevmode\nobreak\ }A$
$\displaystyle\lesssim$ $\displaystyle\leavevmode\nobreak\
gf\operatorname{OPT}.$

This completes the proof. ∎

Using the above fact, we are able to optimize our approximation ratio.

###  D.2 Existence results

######  Definition D.3 ($\ell_{1}$ multiple regression cost preserving sketch
- Definition D.5 in [SWZ17]).

Given matrices $U\in\mathbb{R}^{n\times r},A\in\mathbb{R}^{n\times d}$, let
$S\in\mathbb{R}^{m\times n}$. If $\forall\beta\geq
1,\widehat{V}\in\mathbb{R}^{r\times d}$ which satisfy

$\displaystyle\|SU\widehat{V}-SA\|_{1}\leq\beta\cdot\min_{V\in\mathbb{R}^{r\times
d}}\|SUV-SA\|_{1},$

it holds that

$\displaystyle\|U\widehat{V}-A\|_{1}\leq\beta\cdot
c\cdot\min_{V\in\mathbb{R}^{r\times d}}\|UV-A\|_{1},$

then $S$ provides a $c$-$\ell_{1}$-multiple-regression-cost-preserving-sketch
for $(U,A)$.

######  Theorem D.4.

Given a 3rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any $k\geq
1$, there exist three matrices $S_{1}\in\mathbb{R}^{n^{2}\times s_{1}}$,
$S_{2}\in\mathbb{R}^{n^{2}\times s_{2}}$, $S_{3}\in\mathbb{R}^{n^{2}\times
s_{3}}$ such that

$\displaystyle\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{k}(A_{1}S_{1}X_{1})_{i}\otimes(A_{2}S_{2}X_{2})_{i}\otimes(A_{3}S_{3}X_{3})_{i}-A\right\|_{1}\leq\alpha\underset{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}\in\mathbb{R}^{n\times n\times n}}{\min}\|A_{k}-A\|_{1},$

holds with probability $99/100$.

$\mathrm{(\@slowromancap i@)}$. Using a dense Cauchy transform,
$s_{1}=s_{2}=s_{3}=\widetilde{O}(k)$,
$\alpha=\widetilde{O}(k^{1.5})\log^{3}n$.

$\mathrm{(\@slowromancap ii@)}$. Using a sparse Cauchy transform,
$s_{1}=s_{2}=s_{3}=\widetilde{O}(k^{5})$,
$\alpha=\widetilde{O}(k^{13.5})\log^{3}n$.

$\mathrm{(\@slowromancap iii@)}$. Guessing Lewis weights,
$s_{1}=s_{2}=s_{3}=\widetilde{O}(k)$, $\alpha=\widetilde{O}(k^{1.5})$.

###### Proof.

We use $\operatorname{OPT}$ to denote

$\displaystyle\operatorname{OPT}:=\underset{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}\in\mathbb{R}^{n\times n\times n}}{\min}\|A_{k}-A\|_{1}.$

Given a tensor $A\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$, we define
three matrices $A_{1}\in\mathbb{R}^{n_{1}\times
n_{2}n_{3}},A_{2}\in\mathbb{R}^{n_{2}\times
n_{3}n_{1}},A_{3}\in\mathbb{R}^{n_{3}\times n_{1}n_{2}}$ such that, for any
$i\in[n_{1}],j\in[n_{2}],l\in[n_{3}]$,

$\displaystyle A_{i,j,l}=(A_{1})_{i,(j-1)\cdot n_{3}+l}=(A_{2})_{j,(l-1)\cdot
n_{1}+i}=({A}_{3})_{l,(i-1)\cdot n_{2}+j}.$

We fix $V^{*}\in\mathbb{R}^{n\times k}$ and $W^{*}\in\mathbb{R}^{n\times k}$,
and use $V_{1}^{*},V_{2}^{*},\cdots,V_{k}^{*}$ to denote the columns of
$V^{*}$ and $W_{1}^{*},W_{2}^{*},\cdots,W_{k}^{*}$ to denote the columns of
$W^{*}$.

We consider the following optimization problem,

$\displaystyle\min_{U_{1},\cdots,U_{k}\in\mathbb{R}^{n}}\left\|\sum_{i=1}^{k}U_{i}\otimes
V_{i}^{*}\otimes W_{i}^{*}-A\right\|_{1},$

which is equivalent to

$\displaystyle\min_{U_{1},\cdots,U_{k}\in\mathbb{R}^{n}}\left\|\begin{bmatrix}U_{1}&U_{2}&\cdots&U_{k}\end{bmatrix}\begin{bmatrix}V_{1}^{*}\otimes
W_{1}^{*}\\\ V_{2}^{*}\otimes W_{2}^{*}\\\ \cdots\\\ V_{k}^{*}\otimes
W_{k}^{*}\end{bmatrix}-A\right\|_{1}.$

We use matrix $Z_{1}$ to denote $V^{*\top}\odot
W^{*\top}\in\mathbb{R}^{k\times n^{2}}$ and matrix $U$ to denote
$\begin{bmatrix}U_{1}&U_{2}&\cdots&U_{k}\end{bmatrix}$. Then we can obtain the
following equivalent objective function,

$\displaystyle\min_{U\in\mathbb{R}^{n\times k}}\|UZ_{1}-A_{1}\|_{1}.$

Choose an $\ell_{1}$ multiple regression cost preserving sketch
$S_{1}\in\mathbb{R}^{n^{2}\times s_{1}}$ for $(Z_{1}^{\top},A_{1}^{\top})$. We
can obtain the optimization problem,

$\displaystyle\min_{U\in\mathbb{R}^{n\times
k}}\|UZ_{1}S_{1}-A_{1}S_{1}\|_{1}=\min_{U\in\mathbb{R}^{n\times
k}}\sum_{i=1}^{n}\|U^{i}Z_{1}S_{1}-(A_{1}S_{1})^{i}\|_{1},$

where $U^{i}$ denotes the $i$-th row of matrix $U\in\mathbb{R}^{n\times k}$
and $(A_{1}S_{1})^{i}$ denotes the $i$-th row of matrix $A_{1}S_{1}$. Instead
of solving it under the $\ell_{1}$-norm, we consider the $\ell_{2}$-norm
relaxation,

$\displaystyle\underset{U\in\mathbb{R}^{n\times
k}}{\min}\|UZ_{1}S_{1}-A_{1}S_{1}\|_{F}^{2}=\underset{U\in\mathbb{R}^{n\times
k}}{\min}\sum_{i=1}^{n}\|U^{i}Z_{1}S_{1}-(A_{1}S_{1})^{i}\|_{2}^{2}.$

Let $\widehat{U}\in\mathbb{R}^{n\times k}$ denote the optimal solution of the
above optimization problem. Then,
$\widehat{U}=A_{1}S_{1}(Z_{1}S_{1})^{\dagger}$. We plug $\widehat{U}$ into the
objective function under the $\ell_{1}$-norm. According to Claim B.13, we
have,

$\displaystyle\|\widehat{U}Z_{1}S_{1}-A_{1}S_{1}\|_{1}=\sum_{i=1}^{n}\|\widehat{U}^{i}Z_{1}S_{1}-(A_{1}S_{1})^{i}\|_{1}\leq\sqrt{s_{1}}\min_{U\in\mathbb{R}^{n\times
k}}\|UZ_{1}S_{1}-A_{1}S_{1}\|_{1}.$

Since $S_{1}\in\mathbb{R}^{n^{2}\times s_{1}}$ satisfies Definition D.3, we
have

$\displaystyle\|\widehat{U}Z_{1}-A_{1}\|_{1}\leq\alpha\underset{U\in\mathbb{R}^{n\times
k}}{\min}\|UZ_{1}-A_{1}\|_{1}=\alpha\operatorname{OPT},$

where $\alpha=\sqrt{s_{1}}\beta$ and $\beta$ (see Definition D.3) is a
parameter which depends on which kind of sketching matrix we actually choose.
It implies

$\displaystyle\|\widehat{U}\otimes V^{*}\otimes
W^{*}-A\|_{1}\leq\alpha\operatorname{OPT}.$

As a second step, we fix $\widehat{U}\in\mathbb{R}^{n\times k}$ and
$W^{*}\in\mathbb{R}^{n\times k}$, and convert tensor $A$ into matrix $A_{2}$.
Let matrix $Z_{2}$ denote $\widehat{U}^{\top}\odot W^{*\top}$. We consider the
following objective function,

$\displaystyle\min_{V\in\mathbb{R}^{n\times k}}\|VZ_{2}-A_{2}\|_{1},$

and the optimal cost of it is at most $\alpha\operatorname{OPT}$.

Choose an $\ell_{1}$ multiple regression cost preserving sketch
$S_{2}\in\mathbb{R}^{n^{2}\times s_{2}}$ for $(Z_{2}^{\top},A_{2}^{\top})$,
and sketch on the right of the objective function to obtain this new objective
function,

$\displaystyle\underset{V\in\mathbb{R}^{n\times
k}}{\min}\|VZ_{2}S_{2}-A_{2}S_{2}\|_{1}=\min_{U\in\mathbb{R}^{n\times
k}}\sum_{i=1}^{n}\|V^{i}Z_{2}S_{2}-(A_{2}S_{2})^{i}\|_{1},$

where $V^{i}$ denotes the $i$-th row of matrix $V$ and $(A_{2}S_{2})^{i}$
denotes the $i$-th row of matrix $A_{2}S_{2}$. Instead of solving this under
the $\ell_{1}$-norm, we consider the $\ell_{2}$-norm relaxation,

$\displaystyle\underset{U\in\mathbb{R}^{n\times
k}}{\min}\|VZ_{2}S_{2}-A_{2}S_{2}\|_{F}^{2}=\underset{V\in\mathbb{R}^{n\times
k}}{\min}\|V^{i}(Z_{2}S_{2})-(A_{2}S_{2})^{i}\|_{2}^{2}.$

Let $\widehat{V}\in\mathbb{R}^{n\times k}$ denote the optimal solution of the
above problem. Then $\widehat{V}=A_{2}S_{2}(Z_{2}S_{2})^{\dagger}$. By
properties of the sketching matrix $S_{2}\in\mathbb{R}^{n^{2}\times s_{2}}$,
we have,

$\displaystyle\|\widehat{V}Z_{2}-A_{2}\|_{1}\leq\alpha\underset{V\in\mathbb{R}^{n\times
k}}{\min}\|VZ_{2}-A_{2}\|_{1}\leq\alpha^{2}\operatorname{OPT},$

which implies

$\displaystyle\|\widehat{U}\otimes\widehat{V}\otimes
W^{*}-A\|_{1}\leq\alpha^{2}\operatorname{OPT}.$

As a third step, we fix the matrices $\widehat{U}\in\mathbb{R}^{n\times k}$
and $\widehat{V}\in\mathbb{R}^{n\times k}$. We can convert tensor
$A\in\mathbb{R}^{n\times n\times n}$ into matrix
$A_{3}\in\mathbb{R}^{n^{2}\times n}$. Let matrix $Z_{3}$ denote
$\widehat{U}^{\top}\odot\widehat{V}^{\top}\in\mathbb{R}^{k\times n^{2}}$. We
consider the following objective function,

$\displaystyle\underset{W\in\mathbb{R}^{n\times
k}}{\min}\|WZ_{3}-A_{3}\|_{1},$

and the optimal cost of it is at most $\alpha^{2}\operatorname{OPT}$.

Choose an $\ell_{1}$ multiple regression cost preserving sketch
$S_{3}\in\mathbb{R}^{n^{2}\times s_{3}}$ for $(Z_{3}^{\top},A_{3}^{\top})$ and
sketch on the right of the objective function to obtain the new objective
function,

$\displaystyle\underset{W\in\mathbb{R}^{n\times
k}}{\min}\|WZ_{3}S_{3}-A_{3}S_{3}\|_{1}.$

Let $\widehat{W}\in\mathbb{R}^{n\times k}$ denote the optimal solution of the
above problem. Then $\widehat{W}=A_{3}S_{3}(Z_{3}S_{3})^{\dagger}$. By
properties of sketching matrix $S_{3}\in\mathbb{R}^{n^{2}\times s_{3}}$, we
have,

$\displaystyle\|\widehat{W}Z_{3}-A_{3}\|_{1}\leq\alpha\underset{W\in\mathbb{R}^{n\times
k}}{\min}\|WZ_{3}-A_{3}\|_{1}\leq\alpha^{3}\operatorname{OPT}.$

Thus, we obtain,

$\displaystyle\min_{X_{1}\in\mathbb{R}^{s_{1}\times
k},X_{2}\in\mathbb{R}^{s_{2}\times k},X_{3}\in\mathbb{R}^{s_{3}\times
k}}\left\|\sum_{i=1}^{k}(A_{1}S_{1}X_{1})_{i}\otimes(A_{2}S_{2}X_{2})_{i}\otimes(A_{3}S_{3}X_{3})_{i}-A\right\|_{1}\leq\alpha^{3}\operatorname{OPT}.$

Proof of (i@) By Theorem C.1 in [SWZ17], we can use dense Cauchy transforms
for $S_{1},S_{2},S_{3}$, and then $s_{1}=s_{2}=s_{3}=O(k\log k)$ and
$\alpha=O(\sqrt{k\log k}\log n)$.

Proof of (ii@) By Theorem C.1 in [SWZ17], we can use sparse Cauchy transforms
for $S_{1},S_{2},S_{3}$, and then $s_{1}=s_{2}=s_{3}=O(k^{5}\log^{5}k)$ and
$\alpha=O(k^{4.5}\log^{4.5}k\log n)$.

Proof of (iii@) By Theorem C.1 in [SWZ17], we can sample by Lewis weights.
Then $S_{1},S_{2},S_{3}\in\mathbb{R}^{n^{2}\times n^{2}}$ are diagonal
matrices, and each of them has $O(k\log k)$ nonzero rows. This gives
$\alpha=O(\sqrt{k\log k})$.

∎

###  D.3 Polynomial in $k$ size reduction

######  Definition D.5 (Definition D.1 in [SWZ17]).

Given a matrix $M\in\mathbb{R}^{n\times d},$ if matrix
$S\in\mathbb{R}^{m\times n}$ satisfies

$\displaystyle\|SM\|_{1}\leq\beta\|M\|_{1},$

then $S$ has at most $\beta$ dilation on $M$.

######  Definition D.6 (Definition D.2 in [SWZ17]).

Given a matrix $U\in\mathbb{R}^{n\times k},$ if matrix
$S\in\mathbb{R}^{m\times n}$ satisfies

$\displaystyle\forall
x\in\mathbb{R}^{k},\|SUx\|_{1}\geq\frac{1}{\beta}\|Ux\|_{1},$

then $S$ has at most $\beta$ contraction on $U$.

######  Theorem D.7.

Given a tensor $A\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$ and three
matrices $V_{1}\in\mathbb{R}^{n_{1}\times
b_{1}},V_{2}\in\mathbb{R}^{n_{2}\times b_{2}},V_{3}\in\mathbb{R}^{n_{3}\times
b_{3}},$ let $X_{1}^{*}\in\mathbb{R}^{b_{1}\times
k},X_{2}^{*}\in\mathbb{R}^{b_{2}\times k},X_{3}^{*}\in\mathbb{R}^{b_{3}\times
k}$ satisfies

$\displaystyle
X_{1}^{*},X_{2}^{*},X_{3}^{*}=\underset{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}{\arg\min}\|V_{1}X_{1}\otimes V_{2}X_{2}\otimes V_{3}X_{3}-A\|_{1}.$

Let $S\in\mathbb{R}^{m\times n}$ have at most $\beta_{1}\geq 1$ dilation on
$V_{1}X_{1}^{*}\cdot((V_{2}X_{2}^{*})^{\top}\odot(V_{3}X_{3}^{*})^{\top})-A_{1}$
and $S$ have at most $\beta_{2}\geq 1$ contraction on $V_{1}$. If
$\widehat{X}_{1}\in\mathbb{R}^{b_{1}\times
k},\widehat{X}_{2}\in\mathbb{R}^{b_{2}\times
k},\widehat{X}_{3}\in\mathbb{R}^{b_{3}\times k}$ satisfies

$\displaystyle\|SV_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SA\|_{1}\leq\beta\underset{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}{\min}\|SV_{1}X_{1}\otimes V_{2}X_{2}\otimes V_{3}X_{3}-SA\|_{1},$

where $\beta\geq 1$, then

$\displaystyle\|V_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-A\|_{1}\lesssim\beta_{1}\beta_{2}\beta\min_{X_{1},X_{2},X_{3}}\|V_{1}X_{1}\otimes
V_{2}X_{2}\otimes V_{3}X_{3}-A\|_{1}.$

The proof idea is similar to [SWZ17].

###### Proof.

Let $A,V_{1},V_{2},V_{3},S,X_{1}^{*},X_{2}^{*},X_{3}^{*},\beta_{1},\beta_{2}$
be the same as stated in the theorem. Let
$\widehat{X}_{1}\in\mathbb{R}^{b_{1}\times
k},\widehat{X}_{2}\in\mathbb{R}^{b_{2}\times
k},\widehat{X}_{3}\in\mathbb{R}^{b_{3}\times k}$ satisfy

$\displaystyle\|SV_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SA\|_{1}\leq\beta\underset{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}{\min}\|SV_{1}X_{1}\otimes V_{2}X_{2}\otimes V_{3}X_{3}-SA\|_{1}.$

We have,

$\displaystyle\|SV_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SA\|_{1}$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\|SV_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SV_{1}X^{*}_{1}\otimes V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}\|_{1}-\|SV_{1}X^{*}_{1}\otimes V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}-SA\|_{1}$ $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\beta_{2}}\|V_{1}\widehat{X}_{1}\otimes
V_{2}\widehat{X}_{2}\otimes V_{3}\widehat{X}_{3}-V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}\|_{1}-\beta_{1}\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\beta_{2}}\|V_{1}\widehat{X}_{1}\otimes
V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-A\|_{1}-\frac{1}{\beta_{2}}\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{1}$
$\displaystyle-\beta_{1}\|V_{1}X^{*}_{1}\otimes V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}-A\|_{1}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\beta_{2}}\|V_{1}\widehat{X}_{1}\otimes
V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-A\|_{1}-(\frac{1}{\beta_{2}}+\beta_{1})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{1}.$ (35)

The first and the third inequality follow by the triangle inequalities. The
second inequality follows using that

$\displaystyle\|SV_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SV_{1}X^{*}_{1}\otimes V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}\|_{1}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\left\|SV_{1}(\widehat{X}_{1}-X^{*}_{1})\cdot\left((V_{2}(\widehat{X}_{2}-X^{*}_{2}))^{\top}\odot(V_{3}(\widehat{X}_{3}-X^{*}_{3}))^{\top}\right)\right\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\beta_{2}}\left\|V_{1}(\widehat{X}_{1}-X^{*}_{1})\cdot\left((V_{2}(\widehat{X}_{2}-X^{*}_{2}))^{\top}\odot(V_{3}(\widehat{X}_{3}-X^{*}_{3}))^{\top}\right)\right\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\beta_{2}}\|V_{1}\widehat{X}_{1}\otimes
V_{2}\widehat{X}_{2}\otimes V_{3}\widehat{X}_{3}-V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}\|_{1},$

and

$\displaystyle\|SV_{1}X^{*}_{1}\otimes V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}-SA\|_{1}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\|S(V_{1}X_{1}^{*}\cdot((V_{2}X_{2}^{*})^{\top}\odot(V_{3}X_{3}^{*})^{\top})-A_{1})\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\|V_{1}X_{1}^{*}\cdot((V_{2}X_{2}^{*})^{\top}\odot(V_{3}X_{3}^{*})^{\top})-A_{1}\|_{1}$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\beta_{1}\|V_{1}X^{*}_{1}\otimes V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}-A\|_{1}.$ (36)

Then, we have

$\displaystyle\|V_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-A\|_{1}$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\beta_{2}\|SV_{1}\widehat{X}_{1}\otimes
V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SA\|_{1}+(1+\beta_{1}\beta_{2})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\beta_{2}\beta\|SV_{1}X^{*}_{1}\otimes V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}-SA\|_{1}+(1+\beta_{1}\beta_{2})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\beta_{1}\beta_{2}\beta\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}-A\|_{1}+(1+\beta_{1}\beta_{2})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\beta(1+2\beta_{1}\beta_{2})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{1}.$

The first inequality follows by Equation (D.3). The second inequality follows
by

$\displaystyle\|SV_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SA\|_{1}\leq\beta\underset{X_{1},X_{2},X_{3}}{\min}\|SV_{1}X_{1}\otimes
V_{2}X_{2}\otimes V_{3}X_{3}-SA\|_{1}.$

The third inequality follows by Equation (36). The final inequality follows
using that $\beta\geq 1$. ∎

Algorithm 21 Reducing the Size of the Objective Function to
$\operatorname{poly}(k)$

1:procedure L1PolyKSizeReduction($A,V_{1},V_{2},V_{3},n,b_{1},b_{2},b_{3},k$)
$\triangleright$ Lemma D.8

2: for $i=1\to 3$ do

3: $c_{i}\leftarrow\widetilde{O}(b_{i})$.

4: Choose sampling and rescaling matrices $T_{i}\in\mathbb{R}^{c_{i}\times n}$
according to the Lewis weights of $V_{i}$.

5: $\widehat{V}_{i}\leftarrow T_{i}V_{i}\in\mathbb{R}^{c_{i}\times b_{i}}$.

6: end for

7: $C\leftarrow A(T_{1},T_{2},T_{3})\in\mathbb{R}^{c_{1}\times c_{2}\times
c_{3}}$.

8: return $\widehat{V}_{1}$, $\widehat{V}_{2}$, $\widehat{V}_{3}$ and $C$.

9:end procedure

######  Lemma D.8.

Let $\min(b_{1},b_{2},b_{3})\geq k$. Given three matrices
$V_{1}\in\mathbb{R}^{n\times b_{1}}$, $V_{2}\in\mathbb{R}^{n\times b_{2}}$,
and $V_{3}\in\mathbb{R}^{n\times b_{3}}$, there exists an algorithm that takes
$O(\operatorname{nnz}(A))+n\operatorname{poly}(b_{1},b_{2},b_{3})$ time and
outputs a tensor $C\in\mathbb{R}^{c_{1}\times c_{2}\times c_{3}}$ and three
matrices $\widehat{V}_{1}\in\mathbb{R}^{c_{1}\times b_{1}}$,
$\widehat{V}_{2}\in\mathbb{R}^{c_{2}\times b_{2}}$ and
$\widehat{V}_{3}\in\mathbb{R}^{c_{3}\times b_{3}}$ with
$c_{1}=c_{2}=c_{3}=\operatorname{poly}(b_{1},b_{2},b_{3})$, such that with
probability $0.99$, for any $\alpha\geq 1$, if
$X^{\prime}_{1},X^{\prime}_{2},X^{\prime}_{3}$ satisfy that,

$\displaystyle\left\|\sum_{i=1}^{k}(\widehat{V}_{1}X_{1}^{\prime})_{i}\otimes(\widehat{V}_{2}X_{2}^{\prime})_{i}\otimes(\widehat{V}_{3}X_{3}^{\prime})_{i}-C\right\|_{1}\leq\alpha\underset{X_{1},X_{2},X_{3}}{\min}\left\|\sum_{i=1}^{k}(\widehat{V}_{1}X_{1})_{i}\otimes(\widehat{V}_{2}X_{2})_{i}\otimes(\widehat{V}_{3}X_{3})_{i}-C\right\|_{1},$

then,

$\displaystyle\left\|\sum_{i=1}^{k}(V_{1}X_{1}^{\prime})_{i}\otimes(V_{2}X_{2}^{\prime})_{i}\otimes(V_{3}X_{3}^{\prime})_{i}-A\right\|_{1}\lesssim\alpha\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{k}({V}_{1}X_{1})_{i}\otimes({V}_{2}X_{2})_{i}\otimes({V}_{3}X_{3})_{i}-A\right\|_{1}.$

###### Proof.

For simplicity, we define $\operatorname{OPT}$ to be

$\displaystyle\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{k}({V}_{1}X_{1})_{i}\otimes({V}_{2}X_{2})_{i}\otimes({V}_{3}X_{3})_{i}-A\right\|_{1}.$

Let $T_{1}\in\mathbb{R}^{c_{1}\times n}$ sample according to the Lewis weights
of $V_{1}\in\mathbb{R}^{n\times b_{1}}$, where $c_{1}=\widetilde{O}(b_{1})$.
Let $T_{2}\in\mathbb{R}^{c_{2}\times n}$ sample according to the Lewis weights
of $V_{2}\in\mathbb{R}^{n\times b_{2}}$, where $c_{2}=\widetilde{O}(b_{2})$.
Let $T_{3}\in\mathbb{R}^{c_{3}\times n}$ sample according to the Lewis weights
of $V_{3}\in\mathbb{R}^{n\times b_{3}}$, where $c_{3}=\widetilde{O}(b_{3})$.

For any $\alpha\geq 1,$ let $X^{\prime}_{1}\in\mathbb{R}^{b_{1}\times
k},X^{\prime}_{2}\in\mathbb{R}^{b_{2}\times
k},X^{\prime}_{3}\in\mathbb{R}^{b_{3}\times k}$ satisfy

$\displaystyle\|T_{1}V_{1}X^{\prime}_{1}\otimes
T_{2}V_{2}X^{\prime}_{2}\otimes
T_{3}V_{3}X^{\prime}_{3}-A(T_{1},T_{2},T_{3})\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\alpha\min_{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}\|T_{1}V_{1}X_{1}\otimes T_{2}V_{2}X_{2}\otimes
T_{3}V_{3}X_{3}-A(T_{1},T_{2},T_{3})\|_{1}.$

First, we regard $T_{1}$ as the sketching matrix for the remainder. Then by
Lemma D.11 in [SWZ17] and Theorem D.7, we have

$\displaystyle\|V_{1}X^{\prime}_{1}\otimes T_{2}V_{2}X^{\prime}_{2}\otimes
T_{3}V_{3}X^{\prime}_{3}-A(I,T_{2},T_{3})\|_{1}$
$\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\alpha\min_{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}\|V_{1}X_{1}\otimes T_{2}V_{2}X_{2}\otimes
T_{3}V_{3}X_{3}-A(I,T_{2},T_{3})\|_{1}.$

Second, we regard $T_{2}$ as a sketching matrix for $V_{1}X_{1}\otimes
V_{2}X_{2}\otimes T_{3}V_{3}X_{3}-A(I,I,T_{3})$. Then by Lemma D.11 in [SWZ17]
and Theorem D.7, we have

$\displaystyle\|V_{1}X^{\prime}_{1}\otimes V_{2}X^{\prime}_{2}\otimes
T_{3}V_{3}X^{\prime}_{3}-A(I,I,T_{3})\|_{1}$
$\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\alpha\min_{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}\|V_{1}X_{1}\otimes V_{2}X_{2}\otimes T_{3}V_{3}X_{3}-A(I,I,T_{3})\|_{1}.$

Third, we regard $T_{3}$ as a sketching matrix for $V_{1}X_{1}\otimes
V_{2}X_{2}\otimes V_{3}X_{3}-A$. Then by Lemma D.11 in [SWZ17] and Theorem
D.7, we have

$\displaystyle\left\|\sum_{i=1}^{k}(V_{1}X_{1}^{\prime})_{i}\otimes(V_{2}X_{2}^{\prime})_{i}\otimes(V_{3}X_{3}^{\prime})_{i}-A\right\|_{1}\lesssim\alpha\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{k}({V}_{1}X_{1})_{i}\otimes({V}_{2}X_{2})_{i}\otimes({V}_{3}X_{3})_{i}-A\right\|_{1}.$

∎

######  Lemma D.9.

Given tensor $A\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$, and two
matrices $U\in\mathbb{R}^{n_{1}\times s},V\in\mathbb{R}^{n_{2}\times s}$ with
$\operatorname{rank}(U)=r$, let $T\in\mathbb{R}^{t\times n_{1}}$ be a
sampling/rescaling matrix according to the Lewis weights of $U$ with
$t=\widetilde{O}(r)$. Then with probability at least $0.99$, for all
$X^{\prime}\in\mathbb{R}^{n_{3}\times s},\alpha\geq 1$ which satisfy

$\displaystyle\|T_{1}U\otimes V\otimes
X^{\prime}-T_{1}A\|_{1}\leq\alpha\cdot\min_{X\in\mathbb{R}^{n_{3}\times
s}}\|T_{1}U\otimes V\otimes X-T_{1}A\|_{1},$

it holds that

$\displaystyle\|U\otimes V\otimes
X^{\prime}-A\|_{1}\lesssim\alpha\cdot\min_{X\in\mathbb{R}^{n_{3}\times
s}}\|U\otimes V\otimes X-A\|_{1}.$

The proof is similar to the proof of Lemma D.8.

###### Proof.

Let $X^{*}=\underset{X\in\mathbb{R}^{n_{3}\times s}}{\arg\min}\|U\otimes
V\otimes X-A\|_{1}.$ Then according to Lemma D.11 in [SWZ17], $T$ has at most
constant dilation (Definition D.5) on
$U\cdot(V^{\top}\odot(X^{*})^{\top})-A_{1}$, and has at most constant
contraction (Definition D.6) on $U$. We first look at

$\displaystyle\|TU\otimes V\otimes X^{\prime}-TA\|_{1}$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\|TU\cdot(V^{\top}\odot(X^{\prime})^{\top})-TA_{1}\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\|TU\cdot((V^{\top}\odot(X^{\prime})^{\top})-(V^{\top}\odot(X^{*})^{\top}))\|_{1}-\|TU\cdot(V^{\top}\odot(X^{*})^{\top})-TA_{1}\|_{1}$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\beta_{2}}\|U\cdot((V^{\top}\odot(X^{\prime})^{\top})-A_{1}\|_{1}-(\frac{1}{\beta_{2}}+\beta_{1})\|U\cdot(V^{\top}\odot(X^{*})^{\top})-A_{1}\|_{1},$

where $\beta_{1}\geq 1,\beta_{2}\geq 1$ are two constants. Then we have:

$\displaystyle\|U\otimes V\otimes X^{\prime}-A\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\beta_{2}\|TU\cdot(V^{\top}\odot(X^{\prime})^{\top})-TA_{1}\|_{1}+(1+\beta_{1}\beta_{2})\|U\cdot(V^{\top}\odot(X^{*})^{\top})-A_{1}\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\alpha\beta_{2}\|TU\cdot(V^{\top}\odot(X^{*})^{\top})-TA_{1}\|_{1}+(1+\beta_{1}\beta_{2})\|U\cdot(V^{\top}\odot(X^{*})^{\top})-A_{1}\|_{1}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\alpha\beta_{1}\beta_{2}\|U\cdot(V^{\top}\odot(X^{*})^{\top})-A_{1}\|_{1}+(1+\beta_{1}\beta_{2})\|U\cdot(V^{\top}\odot(X^{*})^{\top})-A_{1}\|_{1}$
$\displaystyle\lesssim\leavevmode\nobreak\ $ $\displaystyle\alpha\|U\otimes
V\otimes X^{*}-A\|_{1}.$

∎

######  Corollary D.10.

Given tensor $A\in\mathbb{R}^{n\times n\times n}$, and two matrices
$U\in\mathbb{R}^{n\times s},V\in\mathbb{R}^{n\times s}$ with
$\operatorname{rank}(U)=r_{1},\operatorname{rank}(V)=r_{2}$, let
$T_{1}\in\mathbb{R}^{t_{1}\times n}$ be a sampling/rescaling matrix according
to the Lewis weights of $U$, and let $T_{2}\in\mathbb{R}^{t_{2}\times n}$ be a
sampling/rescaling matrix according to the Lewis weights of $V$ with
$t_{1}=\widetilde{O}(r_{1}),t_{2}=\widetilde{O}(r_{2})$. Then with probability
at least $0.99$, for all $X^{\prime}\in\mathbb{R}^{n\times s},\alpha\geq 1$
which satisfy

$\displaystyle\|T_{1}U\otimes T_{2}V\otimes
X^{\prime}-A(T_{1},T_{2},I)\|_{1}\leq\alpha\cdot\min_{X\in\mathbb{R}^{n\times
s}}\|T_{1}U\otimes T_{2}V\otimes X-A(T_{1},T_{2},I)\|_{1},$

it holds that

$\displaystyle\|U\otimes V\otimes
X^{\prime}-A\|_{1}\lesssim\alpha\cdot\min_{X\in\mathbb{R}^{n\times
s}}\|U\otimes V\otimes X-A\|_{1}.$

###### Proof.

We apply Lemma D.9 twice: if

$\displaystyle\|T_{1}U\otimes T_{2}V\otimes
X^{\prime}-A(T_{1},T_{2},I)\|_{1}\leq\alpha\cdot\min_{X\in\mathbb{R}^{n\times
s}}\|T_{1}U\otimes T_{2}V\otimes X-A(T_{1},T_{2},I)\|_{1},$

then

$\displaystyle\|U\otimes T_{2}V\otimes
X^{\prime}-A(I,T_{2},I)\|_{1}\lesssim\alpha\cdot\min_{X\in\mathbb{R}^{n\times
s}}\|U\otimes T_{2}V\otimes X-A(I,T_{2},I)\|_{1}.$

Then, we have

$\displaystyle\|U\otimes V\otimes
X^{\prime}-A\|_{1}\lesssim\alpha\cdot\min_{X\in\mathbb{R}^{n\times
s}}\|U\otimes V\otimes X-A\|_{1}.$

∎

###  D.4 Solving small problems

######  Theorem D.11.

Let $\max_{i}\\{t_{i},d_{i}\\}\leq n$. Given a $t_{1}\times t_{2}\times t_{3}$
tensor $A$ and three matrices: a $t_{1}\times d_{1}$ matrix $T_{1}$, a
$t_{2}\times d_{2}$ matrix $T_{2}$, and a $t_{3}\times d_{3}$ matrix $T_{3}$,
if for $\delta>0$ there exists a solution to

$\displaystyle\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{k}(T_{1}X_{1})_{i}\otimes(T_{2}X_{2})_{i}\otimes(T_{3}X_{3})_{i}-A\right\|_{1}:=\operatorname{OPT},$

such that each entry of $X_{i}$ can be expressed using $O(n^{\delta})$ bits,
then there exists an algorithm that takes $n^{O(\delta)}\cdot
2^{O(d_{1}k+d_{2}k+d_{3}k)}$ time and outputs three matrices:
$\widehat{X}_{1}$, $\widehat{X}_{2}$, and $\widehat{X}_{3}$ such that
$\|(T_{1}\widehat{X}_{1})\otimes(T_{2}\widehat{X}_{2})\otimes(T_{3}\widehat{X}_{3})-A\|_{1}=\operatorname{OPT}$.

###### Proof.

For each $i\in[3]$, we can create $t_{i}\times d_{i}$ variables to represent
matrix $X_{i}$. Let $x$ denote the list of these variables. Let $B$ denote
tensor
$\sum_{i=1}^{k}(T_{1}X_{1})_{i}\otimes(T_{2}X_{2})_{i}\otimes(T_{3}X_{3})_{i}$.
Then we can write the following objective function,

$\displaystyle\min_{x}\sum_{i=1}^{t_{1}}\sum_{j=1}^{t_{2}}\sum_{l=1}^{t_{3}}|B_{i,j,l}(x)-A_{i,j,l}|.$

To remove the $|\cdot|$, we create $t_{1}t_{2}t_{3}$ extra variables
$\sigma_{i,j,l}$. Then we obtain the objective function:

$\displaystyle\min_{x,\sigma}$ $\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{t_{1}}\sum_{j=1}^{t_{2}}\sum_{l=1}^{t_{3}}\sigma_{i,j,l}(B_{i,j,l}(x)-A_{i,j,l})$
s.t. $\displaystyle\leavevmode\nobreak\ \sigma_{i,j,l}^{2}=1,$
$\displaystyle\leavevmode\nobreak\ \sigma_{i,j,l}(B_{i,j,l}(x)-A_{i,j,l})\geq
0,$ $\displaystyle\leavevmode\nobreak\ \|x\|_{2}^{2}+\|\sigma\|_{2}^{2}\leq
2^{O(n^{\delta})}$

where the last constraint is unharmful, because there exists a solution that
can be written using $O(n^{\delta})$ bits. Note that the number of inequality
constraints in the above system is $O(t_{1}t_{2}t_{3})$, the degree is $O(1)$,
and the number of variables is $v=(t_{1}t_{2}t_{3}+d_{1}k+d_{2}k+d_{3}k)$.
Thus by Theorem B.11, we know that the minimum nonzero cost is at least

$\displaystyle(2^{O(n^{\delta})})^{-2^{\widetilde{O}(v)}}.$

It is immediate that the upper bound on cost is at most $2^{O(n^{\delta})}$,
and thus the number of binary search steps is at most
$\log(2^{O(n^{\delta})})2^{\widetilde{O}(v)}$. In each step of the binary
search, we need to choose a cost $C$ between the lower bound and the upper
bound, and write down the polynomial system,

$\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{t_{1}}\sum_{j=1}^{t_{2}}\sum_{l=1}^{t_{3}}\sigma_{i,j,l}(B_{i,j,l}(x)-A_{i,j,l})\leq
C,$ $\displaystyle\leavevmode\nobreak\ \sigma_{i,j,l}^{2}=1,$
$\displaystyle\leavevmode\nobreak\ \sigma_{i,j,l}(B_{i,j,l}(x)-A_{i,j,l})\geq
0,$ $\displaystyle\leavevmode\nobreak\ \|x\|_{2}^{2}+\|\sigma\|_{2}^{2}\leq
2^{O(n^{\delta})}.$

Using Theorem B.10, we can determine if there exists a solution to the above
polynomial system. Since the number of variables is $v$, and the degree is
$O(1)$, the number of inequality constraints is $t_{1}t_{2}t_{2}$. Thus, the
running time is

$\displaystyle\operatorname{poly}(\text{bitsize})\cdot(\\#\operatorname{constraints}\cdot\operatorname{degree})^{\\#\operatorname{variables}}=n^{O(\delta)}2^{\widetilde{O}(v)}$

∎

###  D.5 Bicriteria algorithms

We present several bicriteria algorithms with different tradeoffs. We first
present an algorithm that runs in nearly linear time and outputs a solution
with rank $\widetilde{O}(k^{3})$ in Theorem D.12. Then we show an algorithm
that runs in $\operatorname{nnz}(A)$ time but outputs a solution with rank
$\operatorname{poly}(k)$ in Theorem D.13. Then we explain an idea which is
able to decrease the cubic rank to quadratic rank, and thus we can obtain
Theorem D.14 and Theorem D.15.

####  D.5.1 Input sparsity time

Algorithm 22 $\ell_{1}$-Low Rank Approximation, Bicriteria Algorithm,
$\operatorname{rank}$-$\widetilde{O}(k^{3})$, Nearly Input Sparsity Time

1:procedure L1BicriteriaAlgorithm($A,n,k$) $\triangleright$ Theorem D.12

2: $s_{1}\leftarrow s_{2}\leftarrow s_{3}\leftarrow\widetilde{O}(k)$.

3: For each $i\in[3]$, choose $S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$ to be a
dense Cauchy transform. $\triangleright$ Part (i@) of Theorem D.2

4: Compute $A_{1}\cdot S_{1}$, $A_{2}\cdot S_{2}$, $A_{3}\cdot S_{3}$.

5:
$Y_{1},Y_{2},Y_{3},C\leftarrow$L1PolyKSizeReduction($A,A_{1}S_{1},A_{2}S_{2},A_{3}S_{3},n,s_{1},s_{2},s_{3},k$)
$\triangleright$ Algorithm 21

6: Form objective function  $\displaystyle\min_{X\in\mathbb{R}^{s_{1}\times
s_{2}\times
s_{3}}}\left\|\sum_{i=1}^{s_{1}}\sum_{j=1}^{s_{2}}\sum_{l=1}^{s_{3}}X_{i,j,l}(Y_{1})_{i}\otimes(Y_{2})_{j}\otimes(Y_{3})_{l}-C\right\|_{1}.$

7: Run $\ell_{1}$-regression solver to find $X$.

8: return $A_{1}S_{1}$, $A_{2}S_{2}$, $A_{3}S_{3}$ and $X$.

9:end procedure

######  Theorem D.12.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, $\epsilon\in(0,1)$, let $r=\widetilde{O}(k^{3})$. There exists an
algorithm which takes
$\operatorname{nnz}(A)\cdot\widetilde{O}(k)+O(n)\operatorname{poly}(k)+\operatorname{poly}(k)$
time and outputs three matrices $U,V,W\in\mathbb{R}^{n\times r}$ such that

$\displaystyle\left\|\sum_{i=1}^{r}U_{i}\otimes V_{i}\otimes
W_{i}-A\right\|_{1}\leq\widetilde{O}(k^{3/2})\log^{3}n\min_{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}}\|A_{k}-A\|_{1}$

holds with probability $9/10$.

###### Proof.

We first choose three dense Cauchy transforms $S_{i}\in\mathbb{R}^{n^{2}\times
s_{i}}$. According to Section B.7, for each $i\in[3]$, $A_{i}S_{i}$ can be
computed in $\operatorname{nnz}(A)\cdot\widetilde{O}(k)$ time. Then we apply
Lemma D.8 (Algorithm 21). We obtain three matrices $Y_{1},Y_{2},Y_{3}$ and a
tensor $C$. Note that for each $i\in[3]$, $Y_{i}$ can be computed in
$n\operatorname{poly}(k)$ time. Because $C=A(T_{1},T_{2},T_{3})$ and
$T_{1},T_{2},T_{3}\in\mathbb{R}^{n\times\widetilde{O}(k)}$ are three sampling
and rescaling matrices, $C$ can be computed in
$\operatorname{nnz}(A)+\widetilde{O}(k^{3})$ time. At the end, we just need to
run an $\ell_{1}$-regression solver to find the solution to the problem,

$\displaystyle\min_{X\in\mathbb{R}^{s_{1}\times s_{2}\times
s_{3}}}\left\|\sum_{i=1}^{s_{1}}\sum_{j=1}^{s_{2}}\sum_{l=1}^{s_{3}}X_{i,j,l}(Y_{1})_{i}\otimes(Y_{2})_{j}\otimes(Y_{3})_{j}\right\|_{1},$

where $(Y_{1})_{i}$ denotes the $i$-th column of matrix $Y_{1}$. Since the
size of the above problem is only $\operatorname{poly}(k)$, this can be solved
in $\operatorname{poly}(k)$ time. ∎

Algorithm 23 $\ell_{1}$-Low Rank Approximation, Bicriteria Algorithm,
$\operatorname{rank}$-$\operatorname{poly}(k)$, Input Sparsity Time

1:procedure L1BicriteriaAlgorithm($A,n,k$) $\triangleright$ Theorem D.13

2: $s_{1}\leftarrow s_{2}\leftarrow s_{3}\leftarrow\widetilde{O}(k^{5})$.

3: For each $i\in[3]$, choose $S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$ to be a
sparse Cauchy transform. $\triangleright$ Part (ii@) of Theorem D.4

4: Compute $A_{1}\cdot S_{1}$, $A_{2}\cdot S_{2}$, $A_{3}\cdot S_{3}$.

5:
$Y_{1},Y_{2},Y_{3},C\leftarrow$L1PolyKSizeReduction($A,A_{1}S_{1},A_{2}S_{2},A_{3},S_{3},n,s_{1},s_{2},s_{3},k$)
$\triangleright$ Algorithm 21

6: Form objective function  $\displaystyle\min_{X\in\mathbb{R}^{s_{1}\times
s_{2}\times
s_{3}}}\left\|\sum_{i=1}^{s_{1}}\sum_{j=1}^{s_{2}}\sum_{l=1}^{s_{3}}X_{i,j,l}(Y_{1})_{i}\otimes(Y_{2})_{j}\otimes(Y_{3})_{l}-C\right\|_{1}.$

7: Run $\ell_{1}$-regression solver to find $X$.

8: return $A_{1}S_{1}$, $A_{2}S_{2}$, $A_{3}S_{3}$ and $X$.

9:end procedure

######  Theorem D.13.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, $\epsilon\in(0,1)$, let $r=\widetilde{O}(k^{15})$. There exists an
algorithm that takes
$\operatorname{nnz}(A)+O(n)\operatorname{poly}(k)+\operatorname{poly}(k)$ time
and outputs three matrices $U,V,W\in\mathbb{R}^{n\times r}$ such that

$\displaystyle\left\|\sum_{i=1}^{r}U_{i}\otimes V_{i}\otimes
W_{i}-A\right\|_{1}\leq\operatorname{poly}(k,\log
n)\min_{\operatorname{rank}-k\leavevmode\nobreak\ A_{k}}\|A_{k}-A\|_{1}$

holds with probability $9/10$.

###### Proof.

We first choose three dense Cauchy transforms $S_{i}\in\mathbb{R}^{n^{2}\times
s_{i}}$. According to Section B.7, for each $i\in[3]$, $A_{i}S_{i}$ can be
computed in $O(\operatorname{nnz}(A))$ time. Then we apply Lemma D.8
(Algorithm 21), and can obtain three matrices $Y_{1},Y_{2},Y_{3}$ and a tensor
$C$. Note that for each $i\in[3]$, $Y_{i}$ can be computed in
$O(n)\operatorname{poly}(k)$ time. Because $C=A(T_{1},T_{2},T_{3})$ and
$T_{1},T_{2},T_{3}\in\mathbb{R}^{n\times\widetilde{O}(k)}$ are three sampling
and rescaling matrices, $C$ can be computed in
$\operatorname{nnz}(A)+\widetilde{O}(k^{3})$ time. At the end, we just need to
run an $\ell_{1}$-regression solver to find the solution to the problem,

$\displaystyle\min_{X\in\mathbb{R}^{s_{1}\times s_{2}\times
s_{3}}}\left\|\sum_{i=1}^{s_{1}}\sum_{j=1}^{s_{2}}\sum_{l=1}^{s_{3}}X_{i,j,l}(Y_{1})_{i}\otimes(Y_{2})_{j}\otimes(Y_{3})_{l}-C\right\|_{1},$

where $(Y_{1})_{i}$ denotes the $i$-th column of matrix $Y_{1}$. Since the
size of the above problem is only $\operatorname{poly}(k)$, it can be solved
in $\operatorname{poly}(k)$ time. ∎

####  D.5.2 Improving cubic rank to quadratic rank

Algorithm 24 $\ell_{1}$-Low Rank Approximation, Bicriteria Algorithm,
$\operatorname{rank}$-$\widetilde{O}(k^{2})$, Nearly Input Sparsity Time

1:procedure L1BicriteriaAlgorithm($A,n,k$) $\triangleright$ Theorem D.14

2: $s_{1}\leftarrow s_{2}\leftarrow s_{3}\leftarrow\widetilde{O}(k)$.

3: For each $i\in[3]$, choose $S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$ to be a
dense Cauchy transform. $\triangleright$ Part (i@) of Theorem D.2

4: Compute $A_{1}\cdot S_{1}$, $A_{2}\cdot S_{2}$.

5: For each $i\in[2]$, choose $T_{i}$ to be a sampling and rescaling diagonal
matrix according to the Lewis weights of $A_{i}S_{i}$, with
$t_{i}=\widetilde{O}(k)$ nonzero entries.

6: $C\leftarrow A(T_{1},T_{2},I)$.

7:
$B^{i+(j-1)s_{1}}\leftarrow\operatorname{vec}((T_{1}A_{1}S_{1})_{i}\otimes(T_{2}A_{2}S_{2})_{j}),\forall
i\in[s_{1}],j\in[s_{2}]$.

8: Form objective function $\min_{W}\|WB-C_{3}\|_{1}$

9: Run $\ell_{1}$-regression solver to find $\widehat{W}$.

10: Construct $\widehat{U}$ by using $A_{1}S_{1}$ according to Equation (38).

11: Construct $\widehat{V}$ by using $A_{2}S_{2}$ according to Equation (39).

12: return $\widehat{U},\widehat{V},\widehat{W}$.

13:end procedure

######  Theorem D.14.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, $\epsilon\in(0,1)$, let $r=\widetilde{O}(k^{2})$. There exists an
algorithm which takes
$\operatorname{nnz}(A)\cdot\widetilde{O}(k)+O(n)\operatorname{poly}(k)+\operatorname{poly}(k)$
time and outputs three matrices $U,V,W\in\mathbb{R}^{n\times r}$ such that

$\displaystyle\left\|\sum_{i=1}^{r}U_{i}\otimes V_{i}\otimes
W_{i}-A\right\|_{1}\leq\widetilde{O}(k^{3/2})\log^{3}n\min_{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}}\|A_{k}-A\|_{1}$

holds with probability $9/10$.

###### Proof.

Let $\operatorname{OPT}=\underset{A_{k}\in\mathbb{R}^{n\times n\times
n}}{\min}\|A_{k}-A\|_{1}.$ We first choose three dense Cauchy transforms
$S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$, $\forall i\in[3]$. According to
Section B.7, for each $i\in[3]$, $A_{i}S_{i}$ can be computed in
$\operatorname{nnz}(A)\cdot\widetilde{O}(k)$ time. Then we choose $T_{i}$ to
be a sampling and rescaling diagonal matrix according to the Lewis weights of
$A_{i}S_{i}$, $\forall i\in[2]$.

According to Theorem D.4, we have

$\displaystyle\min_{X_{1}\in\mathbb{R}^{s_{1}\times
k},X_{2}\in\mathbb{R}^{s_{2}\times k},X_{3}\in\mathbb{R}^{s_{3}\times
k}}\left\|\sum_{l=1}^{k}(A_{1}S_{1}X_{1})_{l}\otimes(A_{2}S_{2}X_{2})_{l}\otimes(A_{3}S_{3}X_{3})_{l}-A\right\|_{1}\leq\widetilde{O}(k^{1.5})\log^{3}n\operatorname{OPT}$

Now we fix an $l$ and we have:

$\displaystyle(A_{1}S_{1}X_{1})_{l}\otimes(A_{2}S_{2}X_{2})_{l}\otimes(A_{3}S_{3}X_{3})_{l}$
$\displaystyle=$
$\displaystyle\left(\sum_{i=1}^{s_{1}}(A_{1}S_{1})_{i}(X_{1})_{i,l}\right)\otimes\left(\sum_{j=1}^{s_{2}}(A_{2}S_{2})_{j}(X_{2})_{j,l}\right)\otimes(A_{3}S_{3}X_{3})_{l}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{s_{1}}\sum_{j=1}^{s_{2}}(A_{1}S_{1})_{i}\otimes(A_{2}S_{2})_{j}\otimes(A_{3}S_{3}X_{3})_{l}(X_{1})_{i,l}(X_{2})_{j,l}$

Thus, we have

$\displaystyle\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{s_{1}}\sum_{j=1}^{s_{2}}(A_{1}S_{1})_{i}\otimes(A_{2}S_{2})_{j}\otimes\left(\sum_{l=1}^{k}(A_{3}S_{3}X_{3})_{l}(X_{1})_{i,l}(X_{2})_{j,l}\right)-A\right\|_{1}\leq\widetilde{O}(k^{1.5})\log^{3}n\operatorname{OPT}.$
(37)

We create matrix $\widehat{U}\in\mathbb{R}^{n\times s_{1}s_{2}}$ by copying
matrix $A_{1}S_{1}$ $s_{2}$ times, i.e.,

$\displaystyle\widehat{U}=\begin{bmatrix}A_{1}S_{1}&A_{1}S_{1}&\cdots&A_{1}S_{1}\end{bmatrix}.$
(38)

We create matrix $\widehat{V}\in\mathbb{R}^{n\times s_{1}s_{2}}$ by copying
the $i$-th column of $A_{2}S_{2}$ a total of $s_{1}$ times into the columns
$(i-1)s_{1},\cdots,is_{1}$ of $\widehat{V}$, for each $i\in[s_{2}]$, i.e.,

$\displaystyle\widehat{V}=\begin{bmatrix}(A_{2}S_{2})_{1}&\cdots&(A_{2}S_{2})_{1}&(A_{2}S_{2})_{2}&\cdots&(A_{2}S_{2})_{2}&\cdots(A_{2}S_{2})_{s_{2}}&\cdots&(A_{2}S_{2})_{s_{2}}.\end{bmatrix}$
(39)

According to Equation (37), we have:

$\displaystyle\underset{W\in\mathbb{R}^{n\times
s_{1}s_{2}}}{\min}\|\widehat{U}\otimes\widehat{V}\otimes
W-A\|_{1}\leq\widetilde{O}(k^{1.5})\log^{3}n\cdot\operatorname{OPT}.$

Let

$\displaystyle\widehat{W}=\underset{W\in\mathbb{R}^{n\times
s_{1}s_{2}}}{\arg\min}\|T_{1}\widehat{U}\otimes T_{2}\widehat{V}\otimes
W-A(T_{1},T_{2},I)\|_{1}.$

Due to Corollary D.10, we have

$\displaystyle\|\widehat{U}\otimes\widehat{V}\otimes\widehat{W}-A\|_{1}\leq\widetilde{O}(k^{1.5})\log^{3}n\cdot\operatorname{OPT}.$

Putting it all together, we have that $\widehat{U},\widehat{V},\widehat{W}$
gives a rank-$\widetilde{O}(k^{2})$ bicriteria algorithm to the original
problem. ∎

Algorithm 25 $\ell_{1}$-Low Rank Approximation, Bicriteria Algorithm,
$\operatorname{rank}$-$\operatorname{poly}(k)$, Input Sparsity Time

1:procedure L1BicriteriaAlgorithm($A,n,k$) $\triangleright$ Theorem D.15

2: $s_{1}\leftarrow s_{2}\leftarrow s_{3}\leftarrow\widetilde{O}(k^{5})$.

3: For each $i\in[3]$, choose $S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$ to be a
sparse Cauchy transform. $\triangleright$ Part (ii@) of Theorem D.2

4: Compute $A_{1}\cdot S_{1}$, $A_{2}\cdot S_{2}$.

5: For each $i\in[2]$, choose $T_{i}$ to be a sampling and rescaling diagonal
matrix according to the Lewis weights of $A_{i}S_{i}$, with
$t_{i}=\widetilde{O}(k)$ nonzero entries.

6: $C\leftarrow A(T_{1},T_{2},I)$.

7:
$B^{i+(j-1)s_{1}}\leftarrow\operatorname{vec}((T_{1}A_{1}S_{1})_{i}\otimes(T_{2}A_{2}S_{2})_{j}),\forall
i\in[s_{1}],j\in[s_{2}]$.

8: Form objective function $\min_{W}\|WB-C_{3}\|_{1}$.

9: Run $\ell_{1}$-regression solver to find $\widehat{W}$.

10: Construct $\widehat{U}$ by using $A_{1}S_{1}$ according to Equation (38).

11: Construct $\widehat{V}$ by using $A_{2}S_{2}$ according to Equation (39).

12: return $\widehat{U},\widehat{V},\widehat{W}$.

13:end procedure

######  Theorem D.15.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, $\epsilon\in(0,1)$, let $r=\widetilde{O}(k^{10})$. There exists an
algorithm which takes
$\operatorname{nnz}(A)+O(n)\operatorname{poly}(k)+\operatorname{poly}(k)$ time
and outputs three matrices $U,V,W\in\mathbb{R}^{n\times r}$ such that

$\displaystyle\left\|\sum_{i=1}^{r}U_{i}\otimes V_{i}\otimes
W_{i}-A\right\|_{1}\leq\operatorname{poly}(k,\log
n)\min_{\operatorname{rank}-k\leavevmode\nobreak\ A_{k}}\|A_{k}-A\|_{1}$

holds with probability $9/10$.

###### Proof.

The proof is similar to the proof of Theorem D.14. The only difference is that
instead of choosing dense Cauchy matrices $S_{1},S_{2}$, we choose sparse
Cauchy matrices. ∎

Notice that if we firstly apply a sparse Cauchy transform, we can reduce the
rank of the matrix to $\operatorname{poly}(k)$. Then we apply a dense Cauchy
transform and can further reduce the dimension while only incurring another
$\operatorname{poly}(k)$ factor in the approximation ratio. By combining a
sparse Cauchy transform and a dense Cauchy transform, we can improve the
running time from $\operatorname{nnz}(A)\cdot\widetilde{O}(k)$ to
$\operatorname{nnz}(A)$.

######  Corollary D.16.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, $\epsilon\in(0,1)$, let $r=\widetilde{O}(k^{2})$. There exists an
algorithm which takes
$\operatorname{nnz}(A)+O(n)\operatorname{poly}(k)+\operatorname{poly}(k)$ time
and outputs three matrices $U,V,W\in\mathbb{R}^{n\times r}$ such that

$\displaystyle\left\|\sum_{i=1}^{r}U_{i}\otimes V_{i}\otimes
W_{i}-A\right\|_{1}\leq\operatorname{poly}(k,\log
n)\min_{\operatorname{rank}-k\leavevmode\nobreak\ A_{k}}\|A_{k}-A\|_{1}$

holds with probability $9/10$.

Algorithm 26 $\ell_{1}$-Low Rank Approximation, Bicriteria Algorithm,
$\operatorname{rank}$-$\widetilde{O}(k^{2})$, Input Sparsity Time

1:procedure L1BicriteriaAlgorithm($A,n,k$) $\triangleright$ Corollary D.16

2: $s_{1}\leftarrow s_{2}\leftarrow s_{3}\leftarrow\widetilde{O}(k)$.

3: For each $i\in[3]$, choose $S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$ to be
the composition of a sparse Cauchy transform and a dense Cauchy transform.
$\triangleright$ Part (i@,ii@) of Theorem D.2

4: Compute $A_{1}\cdot S_{1}$, $A_{2}\cdot S_{2}$.

5: For each $i\in[2]$, choose $T_{i}$ to be a sampling and rescaling diagonal
matrix according to the Lewis weights of $A_{i}S_{i}$, with
$t_{i}=\widetilde{O}(k)$ nonzero entries.

6: $C\leftarrow A(T_{1},T_{2},I)$.

7:
$B^{i+(j-1)s_{1}}\leftarrow\operatorname{vec}((T_{1}A_{1}S_{1})_{i}\otimes(T_{2}A_{2}S_{2})_{j}),\forall
i\in[s_{1}],j\in[s_{2}]$.

8: Form objective function $\min_{W}\|WB-C_{3}\|_{1}$.

9: Run $\ell_{1}$-regression solver to find $\widehat{W}$.

10: Construct $\widehat{U}$ by using $A_{1}S_{1}$ according to Equation (38).

11: Construct $\widehat{V}$ by using $A_{2}S_{2}$ according to Equation (39).

12: return $\widehat{U},\widehat{V},\widehat{W}$.

13:end procedure

###  D.6 Algorithms

In this section, we show two different algorithms by using different kind of
sketches. One is shown in Theorem D.17 which gives a fast running time.
Another one is shown in Theorem D.19 which gives the best approximation ratio.

####  D.6.1 Input sparsity time algorithm

Algorithm 27 $\ell_{1}$-Low Rank Approximation, Input sparsity Time Algorithm

1:procedure L1TensorLowRankApproxInputSparsity($A,n,k$) $\triangleright$
Theorem D.17

2: $s_{1}\leftarrow s_{2}\leftarrow s_{3}\leftarrow\widetilde{O}(k^{5})$.

3: Choose $S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$ to be a dense Cauchy
transform, $\forall i\in[3]$. $\triangleright$ Part (i@) of Theorem D.4

4: Compute $A_{1}\cdot S_{1}$, $A_{2}\cdot S_{2}$, and $A_{3}\cdot S_{3}$.

5:
$Y_{1},Y_{2},Y_{3},C\leftarrow$L1PolyKSizeReduction($A,A_{1}S_{1},A_{2}S_{2},A_{3}S_{3},n,s_{1},s_{2},s_{3},k$).
$\triangleright$ Algorithm 21

6: Create variables $s_{1}\times k+s_{2}\times k+s_{3}\times k$ variables for
each entry of $X_{1}$, $X_{2}$, $X_{3}$.

7: Form objective function
$\|(Y_{1}X_{1})\otimes(Y_{2}X_{2})\otimes(Y_{3}X_{3})-C\|_{F}^{2}$.

8: Run polynomial system verifier.

9: return $A_{1}S_{1}X_{1},A_{2}S_{2}X_{2},A_{3}S_{3}X_{3}$.

10:end procedure

######  Theorem D.17.

Given a $3$rd tensor $A\in\mathbb{R}^{n\times n\times n}$, for any $k\geq 1$,
there exists an algorithm that takes
$\operatorname{nnz}(A)\cdot\widetilde{O}(k)+O(n)\operatorname{poly}(k)+2^{\widetilde{O}(k^{2})}$
time and outputs three matrices $U,V,W\in\mathbb{R}^{n\times k}$ such that,

$\displaystyle\left\|U\otimes V\otimes
W-A\right\|_{1}\leq\operatorname{poly}(k,\log
n)\min_{\operatorname{rank}-k\leavevmode\nobreak\
A^{\prime}}\|A^{\prime}-A\|_{1}.$

holds with probability at least $9/10$.

###### Proof.

First, we apply part (ii@) of Theorem D.4. Then $A_{i}S_{i}$ can be computed
in $O(\operatorname{nnz}(A))$ time. Second, we use Lemma D.8 to reduce the
size of the objective function from $O(n^{3})$ to $\operatorname{poly}(k)$ in
$n\operatorname{poly}(k)$ time by only losing a constant factor in
approximation ratio. Third, we use Claim B.15 to relax the objective function
from entry-wise $\ell_{1}$-norm to Frobenius norm, and this step causes us to
lose some other $\operatorname{poly}(k)$ factors in approximation ratio. As a
last step, we use Theorem C.45 to solve the Frobenius norm objective function.
∎

Notice again that if we first apply a sparse Cauchy transform, we can reduce
the rank of the matrix to $\operatorname{poly}(k)$. Then as before we can
apply a dense Cauchy transform to further reduce the dimension while only
incurring another $\operatorname{poly}(k)$ factor in the approximation ratio.
By combining a sparse Cauchy transform and a dense Cauchy transform, we can
improve the running time from $\operatorname{nnz}(A)\cdot\widetilde{O}(k)$ to
$\operatorname{nnz}(A)$, while losing some additional $\operatorname{poly}(k)$
factors in approximation ratio.

######  Corollary D.18.

Given a $3$rd tensor $A\in\mathbb{R}^{n\times n\times n}$, for any $k\geq 1$,
there exists an algorithm that takes
$\operatorname{nnz}(A)+O(n)\operatorname{poly}(k)+2^{\widetilde{O}(k^{2})}$
time and outputs three matrices $U,V,W\in\mathbb{R}^{n\times k}$ such that,

$\displaystyle\left\|U\otimes V\otimes
W-A\right\|_{1}\leq\operatorname{poly}(k,\log
n)\min_{\operatorname{rank}-k\leavevmode\nobreak\
A^{\prime}}\|A^{\prime}-A\|_{1}.$

holds with probability at least $9/10$.

####  D.6.2 $\widetilde{O}(k^{3/2})$-approximation algorithm

Algorithm 28 $\ell_{1}$-Low Rank Approximation Algorithm,
$\widetilde{O}(k^{3/2})$-approximation

1:procedure L1TensorLowRankApproxK($A,n,k$) $\triangleright$ Theorem D.19

2: $s_{1}\leftarrow s_{2}\leftarrow s_{3}\leftarrow\widetilde{O}(k)$.

3: Guess diagonal matrices $S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$ with
$s_{i}$ nonzero entries, $\forall i\in[3]$. $\triangleright$ Part (iii@) of
Theorem D.4

4: Compute $A_{1}\cdot S_{1}$, $A_{2}\cdot S_{2}$, and $A_{3}\cdot S_{3}$.

5:
$Y_{1},Y_{2},Y_{3},C\leftarrow$L1PolyKSizeReduction($A,A_{1}S_{1},A_{2}S_{2},A_{3}S_{3},n,s_{1},s_{2},s_{3},k$).
$\triangleright$ Algorithm 21

6: Create $s_{1}\times k+s_{2}\times k+s_{3}\times k$ variables for each entry
of $X_{1}$, $X_{2}$, $X_{3}$.

7: Form objective function
$\|(Y_{1}X_{1})\otimes(Y_{2}X_{2})\otimes(Y_{3}X_{3})-C\|_{1}$.

8: Run polynomial system verifier.

9: return $U,V,W$.

10:end procedure

######  Theorem D.19.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, there exists an algorithm that takes
$n^{\widetilde{O}(k)}2^{\widetilde{O}(k^{3})}$ time and output three matrices
$U,V,W\in\mathbb{R}^{n\times k}$ such that,

$\displaystyle\|U\otimes V\otimes
W-A\|_{1}\leq\widetilde{O}(k^{3/2})\min_{\operatorname{rank}-k\leavevmode\nobreak\
A^{\prime}}\|A^{\prime}-A\|_{1}.$

holds with probability at least $9/10$.

###### Proof.

First, we apply part (iii@) of Theorem D.4. Then, guessing $S_{i}$ requires
$n^{\widetilde{O}(k)}$ time. Second, we use Lemma D.8 to reduce the size of
the objective from $O(n^{3})$ to $\operatorname{poly}(k)$ in polynomial time
while only losing a constant factor in approximation ratio. Third, we use
Theorem D.11 to solve the entry-wise $\ell_{1}$-norm objective function
directly. ∎

###  D.7 CURT decomposition

Algorithm 29 $\ell_{1}$-CURT Decomposition Algorithm

1:procedure L1CURT($A,U_{B},V_{B},W_{B},n,k$) $\triangleright$ Theorem D.20

2: Form $B_{1}=V_{B}^{\top}\odot W_{B}^{\top}\in\mathbb{R}^{k\times n^{2}}$.

3: Let $D_{1}^{\top}\in\mathbb{R}^{n^{2}\times n^{2}}$ be the sampling and
rescaling diagonal matrix corresponding to the Lewis weights of
$B_{1}^{\top}$, and let $D_{1}$ have $d_{1}=O(k\log k)$ nonzero entries.

4: Form $\widehat{U}=A_{1}D_{1}(B_{1}D_{1})^{\dagger}\in\mathbb{R}^{n\times
k}$.

5: Form $B_{2}=\widehat{U}^{\top}\odot W_{B}^{\top}\in\mathbb{R}^{k\times
n^{2}}$.

6: Let $D_{2}^{\top}\in\mathbb{R}^{n^{2}\times n^{2}}$ be the sampling and
rescaling diagonal matrix corresponding to the Lewis weights of
$B_{2}^{\top}$, and let $D_{2}$ have $d_{2}=O(k\log k)$ nonzero entries.

7: Form $\widehat{V}=A_{2}D_{2}(B_{2}D_{2})^{\dagger}\in\mathbb{R}^{n\times
k}$.

8: Form $B_{3}=\widehat{U}^{\top}\odot\widehat{V}^{\top}\in\mathbb{R}^{k\times
n^{2}}$.

9: Let $D_{3}^{\top}\in\mathbb{R}^{n^{2}\times n^{2}}$ be the sampling and
rescaling diagonal matrix corresponding to the Lewis weights of
$B_{3}^{\top}$, and let $D_{3}$ have $d_{3}=O(k\log k)$ nonzero entries.

10: $C\leftarrow A_{1}D_{1}$, $R\leftarrow A_{2}D_{2}$, $T\leftarrow
A_{3}D_{3}$.

11:
$U\leftarrow\sum_{i=1}^{k}((B_{1}D_{1})^{\dagger})_{i}\otimes((B_{2}D_{2})^{\dagger})_{i}\otimes((B_{3}D_{3})^{\dagger})_{i}$.

12: return $C$, $R$, $T$ and $U$.

13:end procedure

######  Theorem D.20.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, let $k\geq
1$, let $U_{B},V_{B},W_{B}\in\mathbb{R}^{n\times k}$ denote a rank-$k$,
$\alpha$-approximation to $A$. Then there exists an algorithm which takes
$O(\operatorname{nnz}(A))+O(n^{2})\operatorname{poly}(k)$ time and outputs
three matrices: $C\in\mathbb{R}^{n\times c}$ with columns from $A$,
$R\in\mathbb{R}^{n\times r}$ with rows from $A$, $T\in\mathbb{R}^{n\times t}$
with tubes from $A$, and a tensor $U\in\mathbb{R}^{c\times r\times t}$ with
$\operatorname{rank}(U)=k$ such that $c=r=t=O(k\log k)$, and

$\displaystyle\left\|\sum_{i=1}^{c}\sum_{j=1}^{r}\sum_{l=1}^{t}U_{i,j,l}\cdot
C_{i}\otimes R_{j}\otimes
T_{l}-A\right\|_{1}\leq\widetilde{O}(k^{1.5})\alpha\min_{\operatorname{rank}-k\leavevmode\nobreak\
A^{\prime}}\|A^{\prime}-A\|_{1}$

holds with probability $9/10$.

###### Proof.

We define

$\displaystyle\operatorname{OPT}:=\min_{\operatorname{rank}-k\leavevmode\nobreak\
A^{\prime}}\|A^{\prime}-A\|_{1}.$

We already have three matrices $U_{B}\in\mathbb{R}^{n\times k}$,
$V_{B}\in\mathbb{R}^{n\times k}$ and $W_{B}\in\mathbb{R}^{n\times k}$ and
these three matrices provide a $\operatorname{rank}$-$k$, $\alpha$
approximation to $A$, i.e.,

$\displaystyle\left\|\sum_{i=1}^{k}(U_{B})_{i}\otimes(V_{B})_{i}\otimes(W_{B})_{i}-A\right\|_{1}\leq\alpha\operatorname{OPT}$
(40)

Let $B_{1}=V_{B}^{\top}\odot W_{B}^{\top}\in\mathbb{R}^{k\times n^{2}}$ denote
the matrix where the $i$-th row is the vectorization of
$(V_{B})_{i}\otimes(W_{B})_{i}$. By Section B.3, we can compute
$D_{1}\in\mathbb{R}^{n^{2}\times n^{2}}$ which is a sampling and rescaling
matrix corresponding to the Lewis weights of $B_{1}^{\top}$ in
$O(n^{2}\operatorname{poly}(k))$ time, and there are $d_{1}=O(k\log k)$
nonzero entries on the diagonal of $D_{1}$. Let $A_{i}\in\mathbb{R}^{n\times
n^{2}}$ denote the matrix obtained by flattening $A$ along the $i$-th
direction, for each $i\in[3]$.

Define $U^{*}\in\mathbb{R}^{n\times k}$ to be the optimal solution to
$\underset{U\in\mathbb{R}^{n\times k}}{\min}\|UB_{1}-A_{1}\|_{1}$,
$\widehat{U}=A_{1}D_{1}(B_{1}D_{1})^{\dagger}\in\mathbb{R}^{n\times k}$,
$V_{0}\in\mathbb{R}^{n\times k}$ to be the optimal solution to
$\underset{V\in\mathbb{R}^{n\times k}}{\min}\|V\cdot(\widehat{U}^{\top}\odot
W_{B}^{\top})-A_{2}\|_{1}$, and $U^{\prime}$ to be the optimal solution to
$\underset{U\in\mathbb{R}^{n\times k}}{\min}\|UB_{1}D_{1}-A_{1}D_{1}\|_{1}$.

By Claim B.13, we have

$\displaystyle\|\widehat{U}B_{1}D_{1}-A_{1}D_{1}\|_{1}\leq\sqrt{d_{1}}\|U^{\prime}B_{1}D_{1}-A_{1}D_{1}\|_{1}$

Due to Lemma D.11 and Lemma D.8 (in [SWZ17]) with constant probability, we
have

$\displaystyle\|\widehat{U}B_{1}-A_{1}\|_{1}\leq\sqrt{d_{1}}\alpha_{D_{1}}\|U^{*}B_{1}-A_{1}\|_{1},$
(41)

where $\alpha_{D_{1}}=O(1)$.

Recall that $(\widehat{U}^{\top}\odot W_{B}^{\top})\in\mathbb{R}^{k\times
n^{2}}$ denotes the matrix where the $i$-th row is the vectorization of
$\widehat{U}_{i}\otimes(W_{B})_{i}$, $\forall i\in[k]$. Now, we can show,

$\displaystyle\|V_{0}\cdot(\widehat{U}^{\top}\odot
W_{B}^{\top})-A_{2}\|_{1}\leq$ $\displaystyle\leavevmode\nobreak\
\|\widehat{U}B_{1}-A_{1}\|_{1}$ $\displaystyle\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ }V_{0}=\underset{V\in\mathbb{R}^{n\times
k}}{\arg\min}\|V\cdot(\widehat{U}^{\top}\odot W_{B}^{\top})-A_{2}\|_{1}$
$\displaystyle\lesssim$ $\displaystyle\leavevmode\nobreak\
\sqrt{d_{1}}\|U^{*}B_{1}-A_{1}\|_{1}$ by Equation (41) $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ \sqrt{d_{1}}\|U_{B}B_{1}-A_{1}\|_{1}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}U^{*}=\underset{U\in\mathbb{R}^{n\times k}}{\arg\min}\|UB_{1}-A_{1}\|_{1}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
O(\sqrt{d_{1}})\alpha\operatorname{OPT}$ by Equation (40) (42)

We define $B_{2}=\widehat{U}^{\top}\odot W_{B}^{\top}$. We can compute
$D_{2}\in\mathbb{R}^{n^{2}\times n^{2}}$ which is a sampling and rescaling
matrix corresponding to the Lewis weights of $B_{2}^{\top}$ in
$O(n^{2}\operatorname{poly}(k))$ time, and there are $d_{2}=O(k\log k)$
nonzero entries on the diagonal of $D_{2}$.

Define $V^{*}\in\mathbb{R}^{n\times k}$ to be the optimal solution of
$\min_{V\in\mathbb{R}^{n\times k}}\|VB_{2}-A_{2}\|_{1}$,
$\widehat{V}=A_{2}D_{2}(B_{2}D_{2})^{\dagger}\in\mathbb{R}^{n\times k}$,
$W_{0}\in\mathbb{R}^{n\times k}$ to be the optimal solution of
$\underset{W\in\mathbb{R}^{n\times
k}}{\min}\|W\cdot(\widehat{U}^{\top}\odot\widehat{V}^{\top})-A_{3}\|_{1}$, and
$V^{\prime}$ to be the optimal solution of $\underset{V\in\mathbb{R}^{n\times
k}}{\min}\|VB_{2}D_{2}-A_{2}D_{2}\|_{1}$.

By Claim B.13, we have

$\displaystyle\|\widehat{V}B_{2}D_{2}-A_{2}D_{2}\|_{1}\leq\sqrt{d_{2}}\|V^{\prime}B_{2}D_{2}-A_{2}D_{2}\|_{1}.$

Due to Lemma D.11 and Lemma D.8(in [SWZ17]) with constant probability, we have

$\displaystyle\|\widehat{V}B_{2}-A_{2}\|_{1}\leq\sqrt{d_{2}}\alpha_{D_{2}}\|V^{*}B_{2}-A_{2}\|_{1},$
(43)

where $\alpha_{D_{2}}=O(1)$.

Recall that $(\widehat{U}^{\top}\odot\widehat{V}^{\top})\in\mathbb{R}^{k\times
n^{2}}$ denotes the matrix for which the $i$-th row is the vectorization of
$\widehat{U}_{i}\otimes\widehat{V}_{i}$, $\forall i\in[k]$. Now, we can show,

$\displaystyle\|W_{0}\cdot(\widehat{U}^{\top}\odot\widehat{V}^{\top})-A_{3}\|_{1}\leq$
$\displaystyle\leavevmode\nobreak\ \|\widehat{V}B_{2}-A_{2}\|_{1}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}W_{0}=\underset{W\in\mathbb{R}^{n\times
k}}{\arg\min}\|W\cdot(\widehat{U}^{\top}\odot\widehat{V}^{\top})-A_{3}\|_{1}$
$\displaystyle\lesssim$ $\displaystyle\leavevmode\nobreak\
\sqrt{d_{2}}\|V^{*}B_{2}-A_{2}\|_{1}$ by Equation (43) $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ \sqrt{d_{2}}\|V_{0}B_{2}-A_{2}\|_{1}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}V^{*}=\underset{V\in\mathbb{R}^{n\times k}}{\arg\min}\|VB_{2}-A_{2}\|_{1}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
O(\sqrt{d_{1}d_{2}})\alpha\operatorname{OPT}$ by Equation (D.7) (44)

We define $B_{3}=\widehat{U}^{\top}\odot\widehat{V}^{\top}$. We can compute
$D_{3}\in\mathbb{R}^{n^{2}\times n^{2}}$ which is a sampling and rescaling
matrix corresponding to the Lewis weights of $B_{3}^{\top}$ in
$O(n^{2}\operatorname{poly}(k))$ time, and there are $d_{3}=O(k\log k)$
nonzero entries on the diagonal of $D_{3}$.

Define $W^{*}\in\mathbb{R}^{n\times k}$ to be the optimal solution to
$\min_{W\in\mathbb{R}^{n\times k}}\|WB_{3}-A_{3}\|_{1}$,
$\widehat{W}=A_{3}D_{3}(B_{3}D_{3})^{\dagger}\in\mathbb{R}^{n\times k}$, and
$W^{\prime}$ to be the optimal solution to $\underset{W\in\mathbb{R}^{n\times
k}}{\min}\|WB_{3}D_{3}-A_{3}D_{3}\|_{1}$.

By Claim B.13, we have

$\displaystyle\|\widehat{W}B_{3}D_{3}-A_{3}D_{3}\|_{1}\leq\sqrt{d_{3}}\|W^{\prime}B_{3}D_{3}-A_{3}D_{3}\|_{1}.$

Due to Lemma D.11 and Lemma D.8(in [SWZ17]) with constant probability, we have

$\displaystyle\|\widehat{W}B_{3}-A_{3}\|_{1}\leq\sqrt{d_{3}}\alpha_{D_{3}}\|W^{*}B_{3}-A_{3}\|_{1},$
(45)

where $\alpha_{D_{3}}=O(1)$. Now we can show,

$\displaystyle\|\widehat{W}B_{3}-A_{3}\|_{1}\lesssim$
$\displaystyle\leavevmode\nobreak\ \sqrt{d_{3}}\|W^{*}B_{3}-A_{3}\|_{1},$ by
Equation (45) $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sqrt{d_{3}}\|W_{0}B_{3}-A_{3}\|_{1},$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}W^{*}=\underset{W\in\mathbb{R}^{n\times k}}{\arg\min}\|WB_{3}-A_{3}\|_{1}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
O(\sqrt{d_{1}d_{2}d_{3}})\alpha\operatorname{OPT}$ by Equation (D.7)

Thus, it implies,

$\displaystyle\left\|\sum_{i=1}^{k}\widehat{U}_{i}\otimes\widehat{V}_{i}\otimes\widehat{W}_{i}-A\right\|_{1}\leq\operatorname{poly}(k,\log
n)\operatorname{OPT}.$

where $\widehat{U}=A_{1}D_{1}(B_{1}D_{1})^{\dagger}$,
$\widehat{V}=A_{2}D_{2}(B_{2}D_{2})^{\dagger}$,
$\widehat{W}=A_{3}D_{3}(B_{3}D_{3})^{\dagger}$.

∎

Algorithm 30 $\ell_{1}$-CURT decomposition algorithm

1:procedure L1CURT+($A,n,k$) $\triangleright$ Theorem D.21

2: $U_{B},V_{B},W_{B}\leftarrow$L1LowRankApproximation($A,n,k$).
$\triangleright$ Corollary D.18

3: $C,R,T,U\leftarrow$ L1CURT($A,U_{B},V_{B},W_{B},n,k$). $\triangleright$
Algorithm 29

4: return $C$, $R$, $T$ and $U$.

5:end procedure

######  Theorem D.21.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, there exists an algorithm which takes
$O(\operatorname{nnz}(A))+O(n^{2})\operatorname{poly}(k)+2^{\widetilde{O}(k^{2})}$
time and outputs three matrices $C\in\mathbb{R}^{n\times c}$ with columns from
$A$, $R\in\mathbb{R}^{n\times r}$ with rows from $A$, $T\in\mathbb{R}^{n\times
t}$ with tubes from $A$, and a tensor $U\in\mathbb{R}^{c\times r\times t}$
with $\operatorname{rank}(U)=k$ such that $c=r=t=O(k\log k)$, and

$\displaystyle\left\|\sum_{i=1}^{c}\sum_{j=1}^{r}\sum_{l=1}^{t}U_{i,j,l}\cdot
C_{i}\otimes R_{j}\otimes T_{l}-A\right\|_{1}\leq\operatorname{poly}(k,\log
n)\underset{\operatorname{rank}-k\leavevmode\nobreak\
A^{\prime}}{\min}\|A^{\prime}-A\|_{1},$

holds with probability $9/10$.

###### Proof.

This follows by combining Corollary D.18 and Theorem D.20. ∎

##  Appendix E Entry-wise $\ell_{p}$ Norm for Arbitrary Tensors, $1<p<2$

There is a long line of research dealing with $\ell_{p}$ norm-related problems
[DDH+09, MM13, CDMI+13, CP15, BCKY16, YCRM16, BBC+17].

In this section, we provide several different algorithms for tensor
$\ell_{p}$-low rank approximation. Section E.1 formally states the $\ell_{p}$
version of Theorem C.1 in [SWZ17]. Section E.2 presents several existence
results. Section E.3 describes a tool that is able to reduce the size of the
objective function from $\operatorname{poly}(n)$ to $\operatorname{poly}(k)$.
Section E.4 discusses the case when the problem size is small. Section E.5
provides several bicriteria algorithms. Section E.6 summarizes a batch of
algorithms. Section E.7 provides an algorithm for $\ell_{p}$ norm CURT
decomposition.

Notice that if the $\operatorname{rank}$-$k$ solution does not exist, then
every bicriteria algorithm in Section E.5 can be stated in the form as Theorem
1.1, and every algorithm which can output a $\operatorname{rank}$-$k$ solution
in Section E.6 can be stated in the form as Theorem 1.2. See Section 1 for
more details.

###  E.1 Existence results for matrix case

######  Theorem E.1 ([SWZ17]).

Let $1\leq p<2$. Given $V\in\mathbb{R}^{k\times n},A\in\mathbb{R}^{d\times
n}$. Let $S\in\mathbb{R}^{n\times s}$ be a proper random sketching matrix. Let

$\displaystyle\widehat{U}=\arg\min_{U\in\mathbb{R}^{d\times k}}\|UVS-
AS\|_{F}^{2},$

i.e.,

$\displaystyle\widehat{U}=AS(VS)^{\dagger}.$

Then with probability at least $0.999,$

$\displaystyle\|\widehat{U}V-A\|_{p}^{p}\leq\alpha\cdot\min_{U\in\mathbb{R}^{d\times
k}}\|UV-A\|_{p}^{p}.$

$\mathrm{(\@slowromancap i@)}$. $S$ denotes a dense $p$-stable transform,
$s=\widetilde{O}(k)$, $\alpha=\widetilde{O}(k^{1-p/2})\log d$.

$\mathrm{(\@slowromancap ii@)}$. $S$ denotes a sparse $p$-stable transform,
$s=\widetilde{O}(k^{5})$, $\alpha=\widetilde{O}(k^{5-5p/2+2/p})\log d$.

$\mathrm{(\@slowromancap iii@)}$. $S^{\top}$ denotes a sampling/rescaling
matrix according to the $\ell_{p}$ Lewis weights of $V^{\top}$,
$s=\widetilde{O}(k)$, $\alpha=\widetilde{O}(k^{1-p/2})$.

We give the proof for completeness.

###### Proof.

Let $S\in\mathbb{R}^{n\times s}$ be a sketching matrix which satisfies the
property $(*)$: $\forall c\geq 1,\widetilde{U}\in\mathbb{R}^{d\times k}$ which
satisfy

$\displaystyle\|\widetilde{U}VS-AS\|_{p}^{p}\leq
c\cdot\min_{U\in\mathbb{R}^{d\times k}}\|UVS-AS\|_{p}^{p},$

we have

$\displaystyle\|\widetilde{U}V-A\|_{p}^{p}\leq
c\beta_{S}\cdot\min_{U\in\mathbb{R}^{d\times k}}\|UV-A\|_{p}^{p},$

where $\beta_{S}\geq 1$ only depends on the sketching matrix $S$. Let

$\displaystyle\forall
i\in[d],(\widehat{U}^{i})^{\top}=\arg\min_{x\in\mathbb{R}^{k}}\|x^{\top}VS-A^{i}S\|_{2}^{2},$

i.e.,

$\displaystyle\widehat{U}=AS(VS)^{\dagger}.$

Let

$\displaystyle\widetilde{U}=\arg\min_{U\in\mathbb{R}^{d\times k}}\|UVS-
AS\|_{p}^{p}.$

Then, we have:

$\displaystyle\leavevmode\nobreak\ \|\widehat{U}VS-AS\|_{p}^{p}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{d}\|\widehat{U}^{i}VS-A^{i}S\|_{p}^{p}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{d}(s^{1/p-1/2}\|\widehat{U}^{i}VS-A^{i}S\|_{2})^{p}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{d}(s^{1/p-1/2}\|\widetilde{U}^{i}VS-A^{i}S\|_{2})^{p}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{d}(s^{1/p-1/2}\|\widetilde{U}^{i}VS-A^{i}S\|_{p})^{p}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
s^{1-p/2}\|\widetilde{U}VS-AS\|_{p}^{p}.$

The first inequality follows using $\forall x\in\mathbb{R}^{s},\|x\|_{p}\leq
s^{1/p-1/2}\|x\|_{2}$ since $p<2$. The third inequality follows using $\forall
x\in\mathbb{R}^{s},\|x\|_{2}\leq\|x\|_{p}$ since $p<2$. Thus, according to the
property $(*)$ of $S$,

$\displaystyle\|\widehat{U}V-A\|_{p}^{p}\leq
s^{1-p/2}\beta_{S}\min_{U\in\mathbb{R}^{d\times k}}\|UV-A\|_{p}^{p}.$

Due to Lemma E.8 and Lemma E.11 of [SWZ17], we have:

for (i@), $s=\widetilde{O}(k),\beta_{S}=O(\log
d),\alpha=s^{1-p/2}\beta_{S}=\widetilde{O}(k^{1-p/2})\log d$,

for (ii@), $s=\widetilde{O}(k^{5}),\beta_{S}=\widetilde{O}(k^{2/p}\log
d),\alpha=s^{1-p/2}\beta_{S}=\widetilde{O}(k^{5-5p/2+2/p})\log d$,

for (iii@),
$s=\widetilde{O}(k),\beta_{S}=O(1),\alpha=s^{1-p/2}\beta_{S}=\widetilde{O}(k^{1-p/2})$.
∎

###  E.2 Existence results

######  Theorem E.2.

Given a 3rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any $k\geq
1$, there exist three matrices $S_{1}\in\mathbb{R}^{n^{2}\times s_{1}}$,
$S_{2}\in\mathbb{R}^{n^{2}\times s_{2}}$, $S_{3}\in\mathbb{R}^{n^{2}\times
s_{3}}$ such that

$\displaystyle\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{k}(A_{1}S_{1}X_{1})_{i}\otimes(A_{2}S_{2}X_{2})_{i}\otimes(A_{3}S_{3}X_{3})_{i}-A\right\|_{p}^{p}\leq\alpha\underset{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}\in\mathbb{R}^{n\times n\times n}}{\min}\|A_{k}-A\|_{p}^{p},$

holds with probability $99/100$.

$\mathrm{(\@slowromancap i@)}$. Using a dense $p$-stable transform,
$s_{1}=s_{2}=s_{3}=\widetilde{O}(k)$,
$\alpha=\widetilde{O}(k^{3-1.5p})\log^{3}n$.

$\mathrm{(\@slowromancap ii@)}$. Using a sparse $p$-stable transform,
$s_{1}=s_{2}=s_{3}=\widetilde{O}(k^{5})$,
$\alpha=\widetilde{O}(k^{15-7.5p+6/p})\log^{3}n$.

$\mathrm{(\@slowromancap iii@)}$. Guessing Lewis weights,
$s_{1}=s_{2}=s_{3}=\widetilde{O}(k)$, $\alpha=\widetilde{O}(k^{3-1.5p})$.

###### Proof.

We use $\operatorname{OPT}$ to denote

$\displaystyle\operatorname{OPT}:=\underset{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}\in\mathbb{R}^{n\times n\times n}}{\min}\|A_{k}-A\|_{p}^{p}.$

Given a tensor $A\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$, we define
three matrices $A_{1}\in\mathbb{R}^{n_{1}\times
n_{2}n_{3}},A_{2}\in\mathbb{R}^{n_{2}\times
n_{3}n_{1}},A_{3}\in\mathbb{R}^{n_{3}\times n_{1}n_{2}}$ such that, for any
$i\in[n_{1}],j\in[n_{2}],l\in[n_{3}]$

$\displaystyle A_{i,j,l}=(A_{1})_{i,(j-1)\cdot n_{3}+l}=(A_{2})_{j,(l-1)\cdot
n_{1}+i}=({A}_{3})_{l,(i-1)\cdot n_{2}+j}.$

We fix $V^{*}\in\mathbb{R}^{n\times k}$ and $W^{*}\in\mathbb{R}^{n\times k}$,
and use $V_{1}^{*},V_{2}^{*},\cdots,V_{k}^{*}$ to denote the columns of
$V^{*}$ and $W_{1}^{*},W_{2}^{*},\cdots,W_{k}^{*}$ to denote the columns of
$W^{*}$.

We consider the following optimization problem,

$\displaystyle\min_{U_{1},\cdots,U_{k}\in\mathbb{R}^{n}}\left\|\sum_{i=1}^{k}U_{i}\otimes
V_{i}^{*}\otimes W_{i}^{*}-A\right\|_{p}^{p},$

which is equivalent to

$\displaystyle\min_{U_{1},\cdots,U_{k}\in\mathbb{R}^{n}}\left\|\begin{bmatrix}U_{1}&U_{2}&\cdots&U_{k}\end{bmatrix}\begin{bmatrix}V_{1}^{*}\otimes
W_{1}^{*}\\\ V_{2}^{*}\otimes W_{2}^{*}\\\ \cdots\\\ V_{k}^{*}\otimes
W_{k}^{*}\end{bmatrix}-A\right\|_{p}^{p}.$

We use matrix $Z_{1}$ to denote $V^{*\top}\odot
W^{*\top}\in\mathbb{R}^{k\times n^{2}}$ and matrix $U$ to denote
$\begin{bmatrix}U_{1}&U_{2}&\cdots&U_{k}\end{bmatrix}$. Then we can obtain the
following equivalent objective function,

$\displaystyle\min_{U\in\mathbb{R}^{n\times k}}\|UZ_{1}-A_{1}\|_{p}^{p}.$

Choose a sketching matrix (a dense $p$-stable, a sparse $p$-stable or an
$\ell_{p}$ Lewis weight sampling/rescaling matrix to $Z_{1}$)
$S_{1}\in\mathbb{R}^{n^{2}\times s_{1}}$. We can obtain the optimization
problem,

$\displaystyle\min_{U\in\mathbb{R}^{n\times
k}}\|UZ_{1}S_{1}-A_{1}S_{1}\|_{p}^{p}=\min_{U\in\mathbb{R}^{n\times
k}}\sum_{i=1}^{n}\|U^{i}Z_{1}S_{1}-(A_{1}S_{1})^{i}\|_{p}^{p},$

where $U^{i}$ denotes the $i$-th row of matrix $U\in\mathbb{R}^{n\times k}$
and $(A_{1}S_{1})^{i}$ denotes the $i$-th row of matrix $A_{1}S_{1}$. Instead
of solving it under the $\ell_{p}$-norm, we consider the $\ell_{2}$-norm
relaxation,

$\displaystyle\underset{U\in\mathbb{R}^{n\times
k}}{\min}\|UZ_{1}S_{1}-A_{1}S_{1}\|_{F}^{2}=\underset{U\in\mathbb{R}^{n\times
k}}{\min}\sum_{i=1}^{n}\|U^{i}Z_{1}S_{1}-(A_{1}S_{1})^{i}\|_{2}^{2}.$

Let $\widehat{U}\in\mathbb{R}^{n\times k}$ denote the optimal solution of the
above optimization problem. Then,
$\widehat{U}=A_{1}S_{1}(Z_{1}S_{1})^{\dagger}$. We plug $\widehat{U}$ into the
objective function under the $\ell_{p}$-norm. By choosing $s_{1}$ and by the
properties of sketching matrices (a dense $p$-stable, a sparse $p$-stable or
an $\ell_{p}$ Lewis weight sampling/rescaling matrix to $Z_{1}$)
$S_{1}\in\mathbb{R}^{n^{2}\times s_{1}}$, we have

$\displaystyle\|\widehat{U}Z_{1}-A_{1}\|_{p}^{p}\leq\alpha\underset{U\in\mathbb{R}^{n\times
k}}{\min}\|UZ_{1}-A_{1}\|_{p}^{p}=\alpha\operatorname{OPT}.$

This implies

$\displaystyle\|\widehat{U}\otimes V^{*}\otimes
W^{*}-A\|_{p}^{p}\leq\alpha\operatorname{OPT}.$

As a second step, we fix $\widehat{U}\in\mathbb{R}^{n\times k}$ and
$W^{*}\in\mathbb{R}^{n\times k}$, and convert tensor $A$ into matrix $A_{2}$.
Let matrix $Z_{2}$ denote $\widehat{U}^{\top}\odot W^{*\top}$. We consider the
following objective function,

$\displaystyle\min_{V\in\mathbb{R}^{n\times k}}\|VZ_{2}-A_{2}\|_{p}^{p},$

and the optimal cost of it is at most $\alpha\operatorname{OPT}$.

We choose a sketching matrix (a dense $p$-stable, a sparse $p$-stable or an
$\ell_{p}$ Lewis weight sampling/rescaling matrix to $Z_{2}$)
$S_{2}\in\mathbb{R}^{n^{2}\times s_{2}}$ and sketch on the right of the
objective function to obtain the new objective function,

$\displaystyle\underset{V\in\mathbb{R}^{n\times
k}}{\min}\|VZ_{2}S_{2}-A_{2}S_{2}\|_{p}^{p}=\min_{V\in\mathbb{R}^{n\times
k}}\sum_{i=1}^{n}\|V^{i}Z_{2}S_{2}-(A_{2}S_{2})^{i}\|_{p}^{p},$

where $V^{i}$ denotes the $i$-th row of matrix $V$ and $(A_{2}S_{2})^{i}$
denotes the $i$-th row of matrix $A_{2}S_{2}$. Instead of solving this under
the $\ell_{p}$-norm, we consider the $\ell_{2}$-norm relaxation,

$\displaystyle\underset{V\in\mathbb{R}^{n\times
k}}{\min}\|VZ_{2}S_{2}-A_{2}S_{2}\|_{F}^{2}=\underset{V\in\mathbb{R}^{n\times
k}}{\min}\sum_{i=1}^{n}\|V^{i}(Z_{2}S_{2})-(A_{2}S_{2})^{i}\|_{2}^{2}.$

Let $\widehat{V}\in\mathbb{R}^{n\times k}$ denote the optimal solution of the
above problem. Then $\widehat{V}=A_{2}S_{2}(Z_{2}S_{2})^{\dagger}$. By
properties of sketching matrix $S_{2}\in\mathbb{R}^{n^{2}\times s_{2}}$, we
have,

$\displaystyle\|\widehat{V}Z_{2}-A_{2}\|_{p}^{p}\leq\alpha\underset{V\in\mathbb{R}^{n\times
k}}{\min}\|VZ_{2}-A_{2}\|_{p}^{p}\leq\alpha^{2}\operatorname{OPT},$

which implies

$\displaystyle\|\widehat{U}\otimes\widehat{V}\otimes
W^{*}-A\|_{p}^{p}\leq\alpha^{2}\operatorname{OPT},$

As a third step, we fix the matrices $\widehat{U}\in\mathbb{R}^{n\times k}$
and $\widehat{V}\in\mathbb{R}^{n\times k}$. We can convert tensor
$A\in\mathbb{R}^{n\times n\times n}$ into matrix
$A_{3}\in\mathbb{R}^{n^{2}\times n}$. Let matrix $Z_{3}$ denote
$\widehat{U}^{\top}\odot\widehat{V}^{\top}\in\mathbb{R}^{k\times n^{2}}$. We
consider the following objective function,

$\displaystyle\underset{W\in\mathbb{R}^{n\times
k}}{\min}\|WZ_{3}-A_{3}\|_{p}^{p},$

and the optimal cost of it is at most $\alpha^{2}\operatorname{OPT}$.

We choose sketching matrix (a dense $p$-stable, a sparse $p$-stable or an
$\ell_{p}$ Lewis weight sampling/rescaling matrix to $Z_{3}$)
$S_{3}\in\mathbb{R}^{n^{2}\times s_{3}}$ and sketch on the right of the
objective function to obtain the new objective function,

$\displaystyle\underset{W\in\mathbb{R}^{n\times
k}}{\min}\|WZ_{3}S_{3}-A_{3}S_{3}\|_{p}^{p}.$

Instead of solving this under the $\ell_{p}$-norm, we consider the
$\ell_{2}$-norm relaxation,

$\displaystyle\underset{W\in\mathbb{R}^{n\times
k}}{\min}\|WZ_{3}S_{3}-A_{3}S_{3}\|_{F}^{2}=\underset{W\in\mathbb{R}^{n\times
k}}{\min}\sum_{i=1}^{n}\|W^{i}(Z_{3}S_{3})-(A_{3}S_{3})^{i}\|_{2}^{2}.$

Let $\widehat{W}\in\mathbb{R}^{n\times k}$ denote the optimal solution of the
above problem. Then $\widehat{W}=A_{3}S_{3}(Z_{3}S_{3})^{\dagger}$. By
properties of sketching matrix $S_{3}\in\mathbb{R}^{n^{2}\times s_{3}}$, we
have,

$\displaystyle\|\widehat{W}Z_{3}-A_{3}\|_{p}^{p}\leq\alpha\underset{W\in\mathbb{R}^{n\times
k}}{\min}\|WZ_{3}-A_{3}\|_{p}^{p}\leq\alpha^{3}\operatorname{OPT}.$

Thus, we obtain,

$\displaystyle\min_{X_{1}\in\mathbb{R}^{s_{1}\times
k},X_{2}\in\mathbb{R}^{s_{2}\times k},X_{3}\in\mathbb{R}^{s_{3}\times
k}}\left\|\sum_{i=1}^{k}(A_{1}S_{1}X_{1})_{i}\otimes(A_{2}S_{2}X_{2})_{i}\otimes(A_{3}S_{3}X_{3})_{i}-A\right\|_{p}^{p}\leq\alpha^{3}\operatorname{OPT}.$

According to Theorem E.1, we let $s=s_{1}=s_{2}=s_{3}$ and take the
corresponding $\alpha$. We can directly get the results for (i@), (ii@) and
(iii@). ∎

###  E.3 Polynomial in $k$ size reduction

######  Definition E.3 (Definition E.1 in [SWZ17]).

Given a matrix $M\in\mathbb{R}^{n\times d},$ if matrix
$S\in\mathbb{R}^{m\times n}$ satisfies

$\displaystyle\|SM\|_{p}^{p}\leq\beta\|M\|_{p}^{p},$

then $S$ has at most $\beta$ dilation on $M$ in the $\ell_{p}$ case.

######  Definition E.4 (Definition E.2 in [SWZ17]).

Given a matrix $U\in\mathbb{R}^{n\times k},$ if matrix
$S\in\mathbb{R}^{m\times n}$ satisfies

$\displaystyle\forall
x\in\mathbb{R}^{k},\|SUx\|_{p}^{p}\geq\frac{1}{\beta}\|Ux\|_{p}^{p},$

then $S$ has at most $\beta$ contraction on $U$ in the $\ell_{p}$ case.

######  Theorem E.5.

Given a tensor $A\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$ and three
matrices $V_{1}\in\mathbb{R}^{n_{1}\times
b_{1}},V_{2}\in\mathbb{R}^{n_{2}\times b_{2}},V_{3}\in\mathbb{R}^{n_{3}\times
b_{3}},$ let $X_{1}^{*}\in\mathbb{R}^{b_{1}\times
k},X_{2}^{*}\in\mathbb{R}^{b_{2}\times k},X_{3}^{*}\in\mathbb{R}^{b_{3}\times
k}$ satisfy

$\displaystyle
X_{1}^{*},X_{2}^{*},X_{3}^{*}=\underset{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}{\arg\min}\|V_{1}X_{1}\otimes V_{2}X_{2}\otimes V_{3}X_{3}-A\|_{p}^{p}.$

Let $S\in\mathbb{R}^{m\times n}$ have at most $\beta_{1}\geq 1$ dilation on
$V_{1}X_{1}^{*}\cdot((V_{2}X_{2}^{*})^{\top}\odot(V_{3}X_{3}^{*})^{\top})-A_{1}$
and $S$ have at most $\beta_{2}\geq 1$ contraction on $V_{1}$ in the
$\ell_{p}$ case. If $\widehat{X}_{1}\in\mathbb{R}^{b_{1}\times
k},\widehat{X}_{2}\in\mathbb{R}^{b_{2}\times
k},\widehat{X}_{3}\in\mathbb{R}^{b_{3}\times k}$ satisfy

$\displaystyle\|SV_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SA\|_{p}^{p}\leq\beta\underset{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}{\min}\|SV_{1}X_{1}\otimes V_{2}X_{2}\otimes V_{3}X_{3}-SA\|_{p}^{p},$

where $\beta\geq 1$, then

$\displaystyle\|V_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-A\|_{p}^{p}\lesssim\beta_{1}\beta_{2}\beta\min_{X_{1},X_{2},X_{3}}\|V_{1}X_{1}\otimes
V_{2}X_{2}\otimes V_{3}X_{3}-A\|_{p}^{p}.$

The proof is essentially the same as the proof of Theorem D.7:

###### Proof.

Let $A,V_{1},V_{2},V_{3},S,X_{1}^{*},X_{2}^{*},X_{3}^{*},\beta_{1},\beta_{2}$
be as stated in the theorem. Let $\widehat{X}_{1}\in\mathbb{R}^{b_{1}\times
k},\widehat{X}_{2}\in\mathbb{R}^{b_{2}\times
k},\widehat{X}_{3}\in\mathbb{R}^{b_{3}\times k}$ satisfy

$\displaystyle\|SV_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SA\|_{p}^{p}\leq\beta\underset{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}{\min}\|SV_{1}X_{1}\otimes V_{2}X_{2}\otimes V_{3}X_{3}-SA\|_{p}^{p}.$

Similar to the proof of Theorem D.7, we have,

$\displaystyle\|SV_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SA\|_{p}^{p}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle 2^{2-2p}\frac{1}{\beta_{2}}\|V_{1}\widehat{X}_{1}\otimes
V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-A\|_{p}^{p}-(2^{1-p}\frac{1}{\beta_{2}}+\beta_{1})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{p}^{p}$

The only difference from the proof of Theorem D.7 is that instead of using
triangle inequality, we actually use $\|x+y\|_{p}^{p}\leq
2^{p-1}\|x\|_{p}^{p}+\|y\|_{p}^{p}.$ Then, we have

$\displaystyle\|V_{1}\widehat{X}_{1}\otimes V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-A\|_{p}^{p}$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle 2^{2p-2}\beta_{2}\|SV_{1}\widehat{X}_{1}\otimes
V_{2}\widehat{X}_{2}\otimes
V_{3}\widehat{X}_{3}-SA\|_{p}^{p}+(2^{p-1}+2^{2p-2}\beta_{1}\beta_{2})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{p}^{p}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2^{2p-2}\beta_{2}\beta\|SV_{1}X^{*}_{1}\otimes V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}-SA\|_{p}^{p}+(2^{p-1}+2^{2p-2}\beta_{1}\beta_{2})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{p}^{p}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2^{2p-2}\beta_{1}\beta_{2}\beta\|V_{1}X^{*}_{1}\otimes V_{2}X^{*}_{2}\otimes
V_{3}X^{*}_{3}-A\|_{p}^{p}+(2^{p-1}+2^{2p-2}\beta_{1}\beta_{2})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{p}^{p}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2^{p-1}\beta(1+2\beta_{1}\beta_{2})\|V_{1}X^{*}_{1}\otimes
V_{2}X^{*}_{2}\otimes V_{3}X^{*}_{3}-A\|_{p}^{p}.$

∎

######  Lemma E.6.

Let $\min(b_{1},b_{2},b_{3})\geq k$. Given three matrices
$V_{1}\in\mathbb{R}^{n\times b_{1}}$, $V_{2}\in\mathbb{R}^{n\times b_{2}}$,
and $V_{3}\in\mathbb{R}^{n\times b_{3}}$, there exists an algorithm which
takes $O(\operatorname{nnz}(A))+n\operatorname{poly}(b_{1},b_{2},b_{3})$ time
and outputs a tensor $C\in\mathbb{R}^{c_{1}\times c_{2}\times c_{3}}$ and
three matrices $\widehat{V}_{1}\in\mathbb{R}^{c_{1}\times b_{1}}$,
$\widehat{V}_{2}\in\mathbb{R}^{c_{2}\times b_{2}}$ and
$\widehat{V}_{3}\in\mathbb{R}^{c_{3}\times b_{3}}$ with
$c_{1}=c_{2}=c_{3}=\operatorname{poly}(b_{1},b_{2},b_{3})$, such that with
probability $0.99$, for any $\alpha\geq 1$, if
$X^{\prime}_{1},X^{\prime}_{2},X^{\prime}_{3}$ satisfy that,

$\displaystyle\left\|\sum_{i=1}^{k}(\widehat{V}_{1}X_{1}^{\prime})_{i}\otimes(\widehat{V}_{2}X_{2}^{\prime})_{i}\otimes(\widehat{V}_{3}X_{3}^{\prime})_{i}-C\right\|_{p}^{p}\leq\alpha\underset{X_{1},X_{2},X_{3}}{\min}\left\|\sum_{i=1}^{k}(\widehat{V}_{1}X_{1})_{i}\otimes(\widehat{V}_{2}X_{2})_{i}\otimes(\widehat{V}_{3}X_{3})_{i}-C\right\|_{p}^{p},$

then,

$\displaystyle\left\|\sum_{i=1}^{k}(V_{1}X_{1}^{\prime})_{i}\otimes(V_{2}X_{2}^{\prime})_{i}\otimes(V_{3}X_{3}^{\prime})_{i}-A\right\|_{p}^{p}\lesssim\alpha\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{k}({V}_{1}X_{1})_{i}\otimes({V}_{2}X_{2})_{i}\otimes({V}_{3}X_{3})_{i}-A\right\|_{p}^{p}.$

###### Proof.

For simplicity, we define $\operatorname{OPT}$ to be

$\displaystyle\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{k}({V}_{1}X_{1})_{i}\otimes({V}_{2}X_{2})_{i}\otimes({V}_{3}X_{3})_{i}-A\right\|_{p}^{p}.$

Let $T_{1}\in\mathbb{R}^{c_{1}\times n}$ correspond to sampling according to
the $\ell_{p}$ Lewis weights of $V_{1}\in\mathbb{R}^{n\times b_{1}}$, where
$c_{1}=\widetilde{b_{1}}$. Let $T_{2}\in\mathbb{R}^{c_{2}\times n}$ be
sampling according to the $\ell_{p}$ Lewis weights of
$V_{2}\in\mathbb{R}^{n\times b_{2}}$, where $c_{2}=\widetilde{b_{2}}$. Let
$T_{3}\in\mathbb{R}^{c_{3}\times n}$ be sampling according to the $\ell_{p}$
Lewis weights of $V_{3}\in\mathbb{R}^{n\times b_{3}}$, where
$c_{3}=\widetilde{b_{3}}$.

For any $\alpha\geq 1,$ let $X^{\prime}_{1}\in\mathbb{R}^{b_{1}\times
k},X^{\prime}_{2}\in\mathbb{R}^{b_{2}\times
k},X^{\prime}_{3}\in\mathbb{R}^{b_{3}\times k}$ satisfy

$\displaystyle\|T_{1}V_{1}X^{\prime}_{1}\otimes
T_{2}V_{2}X^{\prime}_{2}\otimes
T_{3}V_{3}X^{\prime}_{3}-A(T_{1},T_{2},T_{3})\|_{p}^{p}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\alpha\min_{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}\|T_{1}V_{1}X_{1}\otimes T_{2}V_{2}X_{2}\otimes
T_{3}V_{3}X_{3}-A(T_{1},T_{2},T_{3})\|_{p}^{p}.$

First, we regard $T_{1}$ as the sketching matrix for the remainder. Then by
Lemma D.11 in [SWZ17] and Theorem D.7, we have

$\displaystyle\|V_{1}X^{\prime}_{1}\otimes T_{2}V_{2}X^{\prime}_{2}\otimes
T_{3}V_{3}X^{\prime}_{3}-A(I,T_{2},T_{3})\|_{p}^{p}$
$\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\alpha\min_{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}\|V_{1}X_{1}\otimes T_{2}V_{2}X_{2}\otimes
T_{3}V_{3}X_{3}-A(I,T_{2},T_{3})\|_{p}^{p}.$

Second, we regard $T_{2}$ as the sketching matrix for $V_{1}X_{1}\otimes
V_{2}X_{2}\otimes T_{3}V_{3}X_{3}-A(I,I,T_{3})$. Then by Lemma D.11 in [SWZ17]
and Theorem D.7, we have

$\displaystyle\|V_{1}X^{\prime}_{1}\otimes V_{2}X^{\prime}_{2}\otimes
T_{3}V_{3}X^{\prime}_{3}-A(I,I,T_{3})\|_{p}^{p}$
$\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\alpha\min_{X_{1}\in\mathbb{R}^{b_{1}\times
k},X_{2}\in\mathbb{R}^{b_{2}\times k},X_{3}\in\mathbb{R}^{b_{3}\times
k}}\|V_{1}X_{1}\otimes V_{2}X_{2}\otimes
T_{3}V_{3}X_{3}-A(I,I,T_{3})\|_{p}^{p}.$

Third, we regard $T_{3}$ as the sketching matrix for $V_{1}X_{1}\otimes
V_{2}X_{2}\otimes V_{3}X_{3}-A$. Then by Lemma D.11 in [SWZ17] and Theorem
D.7, we have

$\displaystyle\left\|\sum_{i=1}^{k}(V_{1}X_{1}^{\prime})_{i}\otimes(V_{2}X_{2}^{\prime})_{i}\otimes(V_{3}X_{3}^{\prime})_{i}-A\right\|_{p}^{p}\lesssim\alpha\min_{X_{1},X_{2},X_{3}}\left\|\sum_{i=1}^{k}({V}_{1}X_{1})_{i}\otimes({V}_{2}X_{2})_{i}\otimes({V}_{3}X_{3})_{i}-A\right\|_{p}^{p}.$

∎

###  E.4 Solving small problems

Combining Section B.5 in [SWZ17] and the proof of Theorem D.4, for any $p=a/b$
with $a,b$ are integers, we can obtain the $\ell_{p}$ version of Theorem D.4.

###  E.5 Bicriteria algorithm

We present several bicriteria algorithms with different tradeoffs. We first
present an algorithm that runs in nearly linear time and outputs a solution
with rank $\widetilde{O}(k^{3})$ in Theorem E.7. Then we show an algorithm
that runs in $\operatorname{nnz}(A)$ time but outputs a solution with rank
$\operatorname{poly}(k)$ in Theorem E.8. Then we explain an idea which is able
to decrease the cubic rank to quadratic, and thus we can obtain Theorem E.9.

######  Theorem E.7.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, let $r=\widetilde{O}(k^{3})$. There exists an algorithm which takes
$\operatorname{nnz}(A)\cdot\widetilde{O}(k)+n\operatorname{poly}(k)+\operatorname{poly}(k)$
time and outputs three matrices $U,V,W\in\mathbb{R}^{n\times r}$ such that

$\displaystyle\left\|\sum_{i=1}^{r}U_{i}\otimes V_{i}\otimes
W_{i}-A\right\|_{p}^{p}\leq\widetilde{O}(k^{3-p/2})\log^{3}n\min_{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}}\|A_{k}-A\|_{p}^{p}$

holds with probability $9/10$.

###### Proof.

We first choose three dense Cauchy transforms $S_{i}\in\mathbb{R}^{n^{2}\times
s_{i}}$. According to Section B.7, for each $i\in[3]$, $A_{i}S_{i}$ can be
computed in $\operatorname{nnz}(A)\cdot\widetilde{O}(k)$ time. Then we apply
Lemma E.6. We obtain three matrices
$Y_{1}=T_{1}A_{1}S_{1},Y_{2}=T_{2}A_{2}S_{2},Y_{3}=T_{3}A_{3}S_{3}$ and a
tensor $C=A(T_{1},T_{2},T_{3})$. Note that for each $i\in[3]$, $Y_{i}$ can be
computed in $n\operatorname{poly}(k)$ time. Because $C=A(T_{1},T_{2},T_{3})$
and $T_{1},T_{2},T_{3}\in\mathbb{R}^{n\times\widetilde{O}(k)}$ are three
sampling and rescaling matrices, $C$ can be computed in
$\operatorname{nnz}(A)+\widetilde{O}(k^{3})$ time. At the end, we just need to
run an $\ell_{p}$-regression solver to find the solution for the problem:

$\displaystyle\min_{X\in\mathbb{R}^{s_{1}\times s_{2}\times
s_{3}}}\left\|\sum_{i=1}^{s_{1}}\sum_{j=1}^{s_{2}}\sum_{l=1}^{s_{3}}X_{i,j,l}(Y_{1})_{i}\otimes(Y_{2})_{j}\otimes(Y_{3})_{j}\right\|_{p}^{p},$

where $(Y_{1})_{i}$ denotes the $i$-th column of matrix $Y_{1}$. Since the
size of the above problem is only $\operatorname{poly}(k)$, this can be solved
in $\operatorname{poly}(k)$ time. ∎

######  Theorem E.8.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, let $r=\widetilde{O}(k^{15})$. There exists an algorithm that takes
$\operatorname{nnz}(A)+n\operatorname{poly}(k)+\operatorname{poly}(k)$ time
and outputs three matrices $U,V,W\in\mathbb{R}^{n\times r}$ such that

$\displaystyle\left\|\sum_{i=1}^{r}U_{i}\otimes V_{i}\otimes
W_{i}-A\right\|_{p}^{p}\leq\operatorname{poly}(k,\log
n)\min_{\operatorname{rank}-k\leavevmode\nobreak\ A_{k}}\|A_{k}-A\|_{p}^{p}$

holds with probability $9/10$.

###### Proof.

We first choose three sparse $p$-stable transforms
$S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$. According to Section B.7, for each
$i\in[3]$, $A_{i}S_{i}$ can be computed in $O(\operatorname{nnz}(A))$ time.
Then we apply Lemma E.6, and can obtain three matrices
$Y_{1}=T_{1}A_{1}S_{1},Y_{2}=T_{2}A_{2}S_{2},Y_{3}=T_{3}A_{3}S_{3}$ and a
tensor $C=A(T_{1},T_{2},T_{3})$. Note that for each $i\in[3]$, $Y_{i}$ can be
computed in $n\operatorname{poly}(k)$ time. Because $C=A(T_{1},T_{2},T_{3})$
and $T_{1},T_{2},T_{3}\in\mathbb{R}^{n\times\widetilde{O}(k)}$ are three
sampling and rescaling matrices, $C$ can be computed in
$\operatorname{nnz}(A)+\widetilde{O}(k^{3})$ time. At the end, we just need to
run an $\ell_{p}$-regression solver to find the solution to the problem,

$\displaystyle\min_{X\in\mathbb{R}^{s_{1}\times s_{2}\times
s_{3}}}\left\|\sum_{i=1}^{s_{1}}\sum_{j=1}^{s_{2}}\sum_{l=1}^{s_{3}}X_{i,j,l}(Y_{1})_{i}\otimes(Y_{2})_{j}\otimes(Y_{3})_{l}-C\right\|_{p}^{p},$

where $(Y_{1})_{i}$ denotes the $i$-th column of matrix $Y_{1}$. Since the
size of the above problem is only $\operatorname{poly}(k)$, it can be solved
in $\operatorname{poly}(k)$ time. ∎

######  Theorem E.9.

Given a $3$rd order tensor $A\in\mathbb{R}^{n\times n\times n}$, for any
$k\geq 1$, $\epsilon\in(0,1)$, let $r=\widetilde{O}(k^{2})$. There exists an
algorithm which takes
$\operatorname{nnz}(A)\cdot\widetilde{O}(k)+n\operatorname{poly}(k)+\operatorname{poly}(k)$
time and outputs three matrices $U,V,W\in\mathbb{R}^{n\times r}$ such that

$\displaystyle\left\|\sum_{i=1}^{r}U_{i}\otimes V_{i}\otimes
W_{i}-A\right\|_{p}^{p}\leq\widetilde{O}(k^{3-1.5p})\log^{3}n\min_{\operatorname{rank}-k\leavevmode\nobreak\
A_{k}}\|A_{k}-A\|_{p}^{p}$

holds with probability $9/10$.

###### Proof.

The proof is similar to Theorem D.14. ∎

Algorithm 31 $\ell_{p}$-Low Rank Approximation, Bicriteria Algorithm,
$\operatorname{rank}$-$\widetilde{O}(k^{2})$, Input Sparsity Time

1:procedure LpBicriteriaAlgorithm($A,n,k$) $\triangleright$ Corollary E.10

2: $s_{1}\leftarrow s_{2}\leftarrow s_{3}\leftarrow\widetilde{O}(k)$.

3: For each $i\in[3]$, choose $S_{i}\in\mathbb{R}^{n^{2}\times s_{i}}$ to be
the composition of a sparse $p$-stable transform and a dense $p$-stable
transform. $\triangleright$ Part (i@,ii@) of Theorem E.2

4: Compute $A_{1}\cdot S_{1}$, $A_{2}\cdot S_{2}$.

5: For each $i\in[2]$, choose $T_{i}$ to be a sampling and rescaling diagonal
matrix according to the Lewis weights of $A_{i}S_{i}$, with
$t_{i}=\widetilde{O}(k)$ nonzero entries.

6: $C\leftarrow A(T_{1},T_{2},I)$.

7:
$B^{i+(j-1)s_{1}}\leftarrow\operatorname{vec}((T_{1}A_{1}S_{1})_{i}\otimes(T_{2}A_{2}S_{2})_{j}),\forall
i\in[s_{1}],j\in[s_{2}]$.

8: Form objective function $\min_{W}\|WB-C_{3}\|_{1}$.

9: Run $\ell_{p}$-regression solver to find $\widehat{W}$.

10: Construct $\widehat{U}$ by copying $(A_{1}S_{1})_{i}$ to the $(i,j)$-th
column of $\widehat{U}$.

11: Construct $\widehat{V}$ by copying $(A_{2}S_{2})_{j}$ to the $(i,j)$-th
column of $\widehat{V}$ .

12: return $\widehat{U},\widehat{V},\widehat{W}$.

13:end procedure

As for $\ell_{1}$, notice that if we first apply a sparse Cauchy transform, we