mlsanityData to 7 Oct 2026

Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence

arXiv 2104.12031 ↗First posted 24 Apr 2021stat.ML cs.LG cs.NAcited by 13

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider the estimation of a low Tucker rank tensor from a number of noisy linear measurements. The general problem covers many specific examples arising from applications, including tensor regression, tensor completion, and tensor PCA/SVD. We consider an efficient Riemannian Gauss-Newton (RGN) method for low Tucker rank tensor estimation. Different from the generic (super)linear convergence guarantee of RGN in the literature, we prove the first local quadratic convergence guarantee of RGN for low-rank tensor estimation in the noisy setting under some regularity conditions and provide the corresponding estimation error upper bounds. A deterministic estimation error lower bound, which matches the upper bound, is provided that demonstrates the statistical optimality of RGN. The merit of RGN is illustrated through two machine learning applications: tensor regression and tensor SVD. Finally, we provide the simulation results to corroborate our theoretical findings.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 49 of its 118 references that are in the map. First posted on arXiv 24 Apr 2021.

Builds on

49 of 118 references.

References · 49

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  2. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  3. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 81
  4. 2014A statistical model for tensor PCAcited by 72
  5. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  6. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  7. 2017Tensor SVD: Statistical and Computational Limitscited by 52
  8. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 50
  9. 2020An Optimal Statistical and Computational Framework for Generalized Tensor Estimationcited by 39
  10. 2013Square Deal: Lower Bounds and Improved Relaxations for Tensor Recoverycited by 37
  11. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  12. 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
37 more
  1. 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
  2. 2014On Tensor Completion via Nuclear Norm Minimizationcited by 32
  3. 2014Provable Tensor Factorization with Missing Datacited by 31
  4. 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
  5. 2020Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limitscited by 29
  6. 2014Multilinear tensor regression for longitudinal relational datacited by 28
  7. 2016Statistical limits of spiked tensor modelscited by 27
  8. 2016Spectral algorithms for tensor completioncited by 27
  9. 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
  10. 2013Tucker Tensor Regression and Neuroimaging Analysiscited by 26
  11. 2015Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matricescited by 24
  12. 2021Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimizationcited by 24
  13. 2016Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regressioncited by 23
  14. 2017Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entriescited by 23
  15. 2020Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limitcited by 23
  16. 2014Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updatescited by 21
  17. 2015Bayesian Tensor Regressioncited by 21
  18. 2016A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimationcited by 21
  19. 2015Parsimonious Tensor Response Regressioncited by 20
  20. 2016Low-rank tensor completion: a Riemannian manifold preconditioning approachcited by 19
  21. 2013ROP: Matrix recovery via rank-one projectionscited by 18
  22. 2017Multilayer tensor factorization with applications to recommender systemscited by 16
  23. 2020Tensor Completion Made Practicalcited by 15
  24. 2019ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketchingcited by 14
  25. 2016Learning from Multiway Data: Simple and Efficient Tensor Regressioncited by 11
  26. 2016STORE: Sparse Tensor Response Regression and Neuroimaging Analysiscited by 11
  27. 2018Sparse and Low-rank Tensor Estimation via Cubic Sketchingscited by 11
  28. 2020Optimal High-order Tensor SVD via Tensor-Train Orthogonal Iterationcited by 11
  29. 2020Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergencecited by 11
  30. 2019Tensor Regression Using Low-rank and Sparse Tucker Decompositionscited by 10
  31. 2020Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entriescited by 10
  32. 2020Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detectioncited by 9
  33. 2017A Riemannian trust-region method for low-rank tensor completioncited by 8
  34. 2020Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initializationcited by 8
  35. 2021New Riemannian preconditioned algorithms for tensor completion via polyadic decompositioncited by 4
  36. 2018Tensor Methods for Additive Index Models under Discordance and Heterogeneitycited by 3
  37. 2020Second-order optimization for tensors with fixed tensor-train rankcited by 2

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 2; 2023: 1; 2024: 4; 2025: 4.

13 papers.

Sort:

  1. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  2. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  3. 2022Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descentcited by 11
  4. 2021Tensor Principal Component Analysis in High Dimensional CP Modelscited by 7
  5. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  6. 2025Generalized Parallel Scaling with Interdependent Generationscited by 6
  7. 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
  8. 2025A Scalable Factorization Approach for High-Order Structured Tensor Recoverycited by 4
  9. 2024Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimizationcited by 3
  10. 2024Time Series Generative Learning with Application to Brain Imaging Analysiscited by 0
  11. 2024Matrix Completion via Residual Spectral Matchingcited by 0
  12. 2025Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurementscited by 0
1 more
  1. 2025Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifoldcited by 0