mlsanityData to 7 Oct 2026

Tensor SVD: Statistical and Computational Limits

arXiv 1703.02724 ↗First posted 8 Mar 2017math.ST cs.LG stat.MEcited by 52

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose a general framework for tensor singular value decomposition (tensor SVD), which focuses on the methodology and theory for extracting the hidden low-rank structure from high-dimensional tensor data. Comprehensive results are developed on both the statistical and computational limits for tensor SVD. This problem exhibits three different phases according to the signal-to-noise ratio (SNR). In particular, with strong SNR, we show that the classical higher-order orthogonal iteration achieves the minimax optimal rate of convergence in estimation; with weak SNR, the information-theoretical lower bound implies that it is impossible to have consistent estimation in general; with moderate SNR, we show that the non-convex maximum likelihood estimation provides optimal solution, but with NP-hard computational cost; moreover, under the hardness hypothesis of hypergraphic planted clique detection, there are no polynomial-time algorithms performing consistently in general.

Key facts. Cited by 52 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Mar 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 7; 2023: 6; 2024: 14; 2025: 5; 2026: 6.

52 papers.

Sort:

By area:

  1. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  2. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  3. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  4. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  5. 2021Latent Space Model for Higher-order Networks and Generalized Tensor Decompositioncited by 13
  6. 2024Tensor-view Topological Graph Neural Networkcited by 12
  7. 2021On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errorscited by 10
  8. 2021Long Random Matrices and Tensor Unfoldingcited by 10
  9. 2024Optimal Differentially Private PCA and Estimation for Spiked Covariance Matricescited by 10
  10. 2022Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Boundcited by 8
  11. 2021Learning Good State and Action Representations via Tensor Decompositioncited by 7
  12. 2021Tensor Principal Component Analysis in High Dimensional CP Modelscited by 7
38 more
  1. 2023Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCAcited by 7
  2. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  3. 2022Optimal Estimation and Computational Limit of Low-rank Gaussian Mixturescited by 6
  4. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  5. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  6. 2024Valid Conformal Prediction for Dynamic GNNscited by 6
  7. 2024Optimal Estimation of Shared Singular Subspaces across Multiple Noisy Matricescited by 6
  8. 2021Modelling matrix time series via a tensor CP-decompositioncited by 5
  9. 2022Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Modelcited by 5
  10. 2021Beyond the Signs: Nonparametric Tensor Completion via Sign Seriescited by 4
  11. 2022Multiway Spherical Clustering via Degree-Corrected Tensor Block Modelscited by 4
  12. 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
  13. 2022Consensus Knowledge Graph Learning via Multi-view Sparse Low Rank Block Modelcited by 3
  14. 2024A Random Matrix Approach to Low-Multilinear-Rank Tensor Approximationcited by 3
  15. 2024Conditional Uncertainty Quantification for Tensorized Topological Neural Networkscited by 3
  16. 2024Tensor-Fused Multi-View Graph Contrastive Learningcited by 3
  17. 2021Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutationscited by 2
  18. 2023Multi-dimensional domain generalization with low-rank structurescited by 2
  19. 2024Sharp Analysis of Power Iteration for Tensor PCAcited by 2
  20. 2024Robust Low-rank Tensor Train Recoverycited by 2
  21. 2021Jointly Modeling and Clustering Tensors in High Dimensionscited by 1
  22. 2022Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCAcited by 1
  23. 2023Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Modelcited by 1
  24. 2024Signed Diverse Multiplex Networks: Clustering and Inferencecited by 1
  25. 2024Tensor Methods in High Dimensional Data Analysis: Opportunities and Challengescited by 1
  26. 2021Logspace Reducibility From Secret Leakage Planted Cliquecited by 0
  27. 2021Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapescited by 0
  28. 2023Statistical and computational rates in high rank tensor estimationcited by 0
  29. 2024On Minimum Trace Factor Analysis -- An Old Song Sung to a New Tunecited by 0
  30. 2025A Robust and Non-Iterative Tensor Decomposition Method with Automatic Thresholdingcited by 0
  31. 2025Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)cited by 0
  32. 2025Perfect Clustering in Very Sparse Diverse Multiplex Networkscited by 0
  33. 2025A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decompositioncited by 0
  34. 2025Optimal Bias-variance Tradeoff in Matrix and Tensor Estimationcited by 0
  35. 2026Tucker Diffusion Model for High-dimensional Tensor Generationcited by 0
  36. 2026Dual-Channel Tensor Neural Networks: Finite-Sample Theory and Conformal Structure Selectioncited by 0
  37. 2026Structured Adaptive Tensor Prediction for Streaming Datacited by 0
  38. 2026Exponential-Family Tensor Completion via Nonconvex Dual Total-Variation Regularizationcited by 0

50 most cited of 52 All 52 (JSON)