mlsanityData to 7 Oct 2026

Faster Robust Tensor Power Method for Arbitrary Order

arXiv 2306.00406 ↗First posted 1 Jun 2023cs.LG cs.NA math.NAcited by 8

Not on the map. Why?

Abstract (arXiv)

Tensor decomposition is a fundamental method used in various areas to deal with high-dimensional data. Tensor power method (TPM) is one of the widely-used techniques in the decomposition of tensors. This paper presents a novel tensor power method for decomposing arbitrary order tensors, which overcomes limitations of existing approaches that are often restricted to lower-order (less than 3) tensors or require strong assumptions about the underlying data structure. We apply sketching method, and we are able to achieve the running time of widetildeO(np-1), on the power p and dimension n tensor. We provide a detailed analysis for any p-th order tensor, which is never given in previous works.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 33 of its 75 references that are in the map. First posted on arXiv 1 Jun 2023.

Builds on

33 of 75 references.

References · 33

  1. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  2. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  3. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  4. 2017Relative Error Tensor Low Rank Approximationcited by 45
  5. 2017Introduction to Tensor Decompositions and their Applications in Machine Learningcited by 45
  6. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  7. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  8. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  9. 2022A Faster Small Treewidth SDP Solvercited by 36
  10. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  11. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  12. 2020A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Pathcited by 29
21 more
  1. 2022Speeding Up Sparsification using Inner Product Search Data Structurescited by 22
  2. 2022A Sublinear Adversarial Training Algorithmcited by 22
  3. 2022Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenancecited by 22
  4. 2015Fast and Guaranteed Tensor Decomposition via Sketchingcited by 19
  5. 2014Efficient Nonnegative Tucker Decompositions: Algorithms and Uniquenesscited by 17
  6. 2022Dynamic Tensor Product Regressioncited by 17
  7. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  8. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  9. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  10. 2014DFacTo: Distributed Factorization of Tensorscited by 8
  11. 2016Online and Differentially-Private Tensor Decompositioncited by 8
  12. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  13. 2022Uniform Approximations for Randomized Hadamard Transforms with Applicationscited by 7
  14. 2022Fast Distance Oracles for Any Symmetric Normcited by 6
  15. 2022Adore: Differentially Oblivious Relational Database Operatorscited by 6
  16. 2021Tensor decomposition for learning Gaussian mixtures from momentscited by 5
  17. 2013Online Tensor Methods for Learning Latent Variable Modelscited by 4
  18. 2022Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositionscited by 4
  19. 2022Robust Low-rank Tensor Decomposition with the operatornameL2 Criterioncited by 4
  20. 2022Dynamic Kernel Graph Sparsifierscited by 4
  21. 2015A New Sampling Technique for Tensorscited by 2

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 2; 2025: 3.

8 papers.

  1. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  2. 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
  3. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  4. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  5. 2023A Unified Scheme of ResNet and Softmaxcited by 12
  6. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  7. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  8. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2