Relative Error Tensor Low Rank Approximation

2017/04/26 by Zhao Song, David P. Woodruff, Song, Zhao +3 · 2 citations
Computer Science · Engineering · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Matrix Theory and Algorithms #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.1704.08246

openalex publication_date 2017/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider relative error low rank approximation of tensors with respect to the Frobenius norm: given an order-q tensor A ∈ ℝ^∏_i=1^q n_i, output a rank-k tensor B for which ‖A-B‖_F² ≤ (1+ε)OPT, where OPT = inf_\textrmrank-k~A' ‖A-A'‖_F². 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² ≤ (1+ε)OPT in nnz(A) + n ⋅ \textrmpoly(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² ≤ (1+ε)OPT and runs in ( nnz(A) + n ⋅ \textrmpoly(k/ε) + exp(k²/ε) ) ⋅ 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.

Cited by

• Davis-Kahan Theorem under a moderate gap condition
• Towards Sampling Data Structures for Tensor Products in Turnstile Streams

Related

• Tensor rank and the ill-posedness of the best low-rank approximation problem
• Nearly Low Rank Tensors and Their Approximations
• Robust low-rank multilinear tensor approximation for a joint estimation of the multilinear rank and the loading matrices
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions
• Low-Rank Approximation and Completion of Positive Tensors