# Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence arXiv: https://arxiv.org/abs/2104.12031 ยท HTML: https://mlsanity.com/paper/2104.12031/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 49 of its 118 references that are in the map. - First posted on arXiv 24 Apr 2021. ## Builds on (most cited first, 30 of 49) - [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018) - [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015) - [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014) - [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014) - [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018) - [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017) - [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017) - [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020) - [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020) - [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013) - [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015) - [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019) - [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015) - [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014) - [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014) - [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019) - [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020) - [Multilinear tensor regression for longitudinal relational data](https://mlsanity.com/paper/1412.0048/) (2014) - [Statistical limits of spiked tensor models](https://mlsanity.com/paper/1612.07728/) (2016) - [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016) - [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017) - [Tucker Tensor Regression and Neuroimaging Analysis](https://mlsanity.com/paper/1304.5637/) (2013) - [Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matrices](https://mlsanity.com/paper/1507.02772/) (2015) - [Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimization](https://mlsanity.com/paper/2103.08895/) (2021) - [Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regression](https://mlsanity.com/paper/1611.10349/) (2016) - [Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries](https://mlsanity.com/paper/1711.04934/) (2017) - [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020) - [Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates](https://mlsanity.com/paper/1402.5180/) (2014) - [Bayesian Tensor Regression](https://mlsanity.com/paper/1509.06490/) (2015) - [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016) ## Built on by (most cited first, 13 of 13) - [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021) - [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022) - [Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent](https://mlsanity.com/paper/2206.09109/) (2022) - [Tensor Principal Component Analysis in High Dimensional CP Models](https://mlsanity.com/paper/2108.04428/) (2021) - [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023) - [Generalized Parallel Scaling with Interdependent Generations](https://mlsanity.com/paper/2510.01143/) (2025) - [Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decomposition](https://mlsanity.com/paper/2406.06002/) (2024) - [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025) - [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024) - [Time Series Generative Learning with Application to Brain Imaging Analysis](https://mlsanity.com/paper/2407.14003/) (2024) - [Matrix Completion via Residual Spectral Matching](https://mlsanity.com/paper/2412.10005/) (2024) - [Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements](https://mlsanity.com/paper/2502.05134/) (2025) - [Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifold](https://mlsanity.com/paper/2510.00569/) (2025) ## 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.