Title: Relative Error Tensor Low Rank Approximation,
Abstract: We consider relative error low rank approximation of $tensors$ with respect
to the Frobenius norm: given an order-$q$ tensor $A \in
\mathbb{R}^{\prod_{i=1}^q n_i}$, output a rank-$k$ tensor $B$ for which
$\|A-B\|_F^2 \leq (1+\epsilon)$OPT, where OPT $= \inf_{\textrm{rank-}k~A'}
\|A-A'\|_F^2$. Despite the success on obtaining relative error low rank
approximations for matrices, no such results were known for tensors. One
structural issue is that there may be no rank-$k$ tensor $A_k$ achieving the
above infinum. Another, computational issue, is that an efficient relative
error low rank approximation algorithm for tensors would allow one to compute
the rank of a tensor, which is NP-hard. We bypass these issues via (1)
bicriteria and (2) parameterized complexity solutions:
(1) We give an algorithm which outputs a rank $k' = O((k/\epsilon)^{q-1})$
tensor $B$ for which $\|A-B\|_F^2 \leq (1+\epsilon)$OPT in $nnz(A) + n \cdot
\textrm{poly}(k/\epsilon)$ time in the real RAM model. Here $nnz(A)$ is the
number of non-zero entries in $A$.
(2) We give an algorithm for any $\delta >0$ which outputs a rank $k$ tensor
$B$ for which $\|A-B\|_F^2 \leq (1+\epsilon)$OPT and runs in $ ( nnz(A) + n
\cdot \textrm{poly}(k/\epsilon) + \exp(k^2/\epsilon) ) \cdot n^\delta$ time in
the unit cost RAM model.
For outputting a rank-$k$ tensor, or even a bicriteria solution with
rank-$Ck$ for a certain constant $C > 1$, we show a $2^{\Omega(k^{1-o(1)})}$
time lower bound under the Exponential Time Hypothesis.
Our results give the first relative error low rank approximations for tensors
for a large number of robust error measures for which nothing was known, as
well as column row and tube subset selection. We also obtain new results for
matrices, such as $nnz(A)$-time CUR decompositions, improving previous
$nnz(A)\log n$-time algorithms, which may be of independent interest.