mlsanityData to 7 Oct 2026

Relative Error Tensor Low Rank Approximation

arXiv 1704.08246 ↗First posted 26 Apr 2017cs.DS cs.CC cs.LGcited by 45

Not on the map. Why?

Abstract (arXiv)

We consider relative error low rank approximation of tensors with respect to the Frobenius norm: given an order-q tensor A ∈ ℝ^prodi=1q ni, output a rank-k tensor B for which |A-B|F2 ≤ (1+ε)OPT, where OPT = inf_textrmrank-k~A' |A-A'|F2. 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 Ak 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|F2 ≤ (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|F2 ≤ (1+ε)OPT and runs in ( nnz(A) + n · textrmpoly(k/ε) + exp(k2/ε) ) · 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^Omega(k1-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.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). First posted on arXiv 26 Apr 2017.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 7; 2022: 6; 2023: 23; 2024: 6; 2025: 3.

45 papers.

Sort:

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  2. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  3. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  4. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  5. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  6. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  7. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  8. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  9. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  10. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  11. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  12. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
33 more
  1. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  2. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  3. 2022Dynamic Tensor Product Regressioncited by 17
  4. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  5. 2021Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositionscited by 13
  6. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  7. 2021Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositionscited by 11
  8. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  9. 2023Optimal Embedding Dimension for Sparse Subspace Embeddingscited by 11
  10. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  11. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  12. 2023Approximately Optimal Core Shapes for Tensor Decompositionscited by 8
  13. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  14. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  15. 2023Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameterscited by 7
  16. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  17. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  18. 2022Subquadratic Kronecker Regression with Applications to Tensor Decompositioncited by 6
  19. 2024How to Inverting the Leverage Score Distribution?cited by 5
  20. 2021Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Timecited by 4
  21. 2022Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositionscited by 4
  22. 2023Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basiscited by 4
  23. 2025Tensor Sketch: Fast and Scalable Polynomial Kernel Approximationcited by 4
  24. 2021Symmetric Sparse Boolean Matrix Factorization and Applicationscited by 3
  25. 2021Fast Graph Neural Tangent Kernel via Kronecker Sketchingcited by 2
  26. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  27. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  28. 2024Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walkcited by 1
  29. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  30. 2022Sample Efficient Learning of Factored Embeddings of Tensor Fieldscited by 0
  31. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  32. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  33. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0