article · arXiv (Cornell University) · 2017

Relative Error Tensor Low Rank Approximation

Zhao Song, David P. Woodruff, Peilin Zhong

Cited by 0Open access

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+ε)$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/ε)^{q-1})$ tensor $B$ for which $\|A-B\|_F^2 \leq (1+ε)$OPT in $nnz(A) + n \cdot \textrm{poly}(k/ε)$ 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 $δ>0$ which outputs a rank $k$ tensor $B$ for which $\|A-B\|_F^2 \leq (1+ε)$OPT and runs in $ ( nnz(A) + n \cdot \textrm{poly}(k/ε) + \exp(k^2/ε) ) \cdot n^δ$ 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^{Ω(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.

Cite this paper

APA 7

Song, Z., Woodruff, D. P., & Zhong, P. (2017). Relative Error Tensor Low Rank Approximation. arXiv (Cornell University), 25, 103. https://doi.org/10.48550/arxiv.1704.08246

MLA 9

Song, Zhao, et al. “Relative Error Tensor Low Rank Approximation.” arXiv (Cornell University), vol. 25, 2017, p. 103, https://doi.org/10.48550/arxiv.1704.08246.

Chicago

Song, Zhao, David P. Woodruff, and Peilin Zhong. 2017. “Relative Error Tensor Low Rank Approximation.” arXiv (Cornell University) 25: 103. https://doi.org/10.48550/arxiv.1704.08246.

Harvard

Song, Z., Woodruff, D.P. and Zhong, P. (2017) ‘Relative Error Tensor Low Rank Approximation’, arXiv (Cornell University), 25, p. 103. Available at: https://doi.org/10.48550/arxiv.1704.08246.

BibTeX

@article{song2017relative,
  title = {{Relative Error Tensor Low Rank Approximation}},
  author = {Song, Zhao and Woodruff, David P. and Zhong, Peilin},
  journal = {arXiv (Cornell University)},
  volume = {25},
  pages = {103},
  year = {2017},
  doi = {10.48550/arxiv.1704.08246}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.