# A Scalable Factorization Approach for High-Order Structured Tensor Recovery

arXiv: https://arxiv.org/abs/2506.16032 · HTML: https://mlsanity.com/paper/2506.16032/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 91 references that are in the map.
- First posted on arXiv 19 Jun 2025.

## Builds on (most cited first, 30 of 40)

- [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [A Tensorized Transformer for Language Modeling](https://mlsanity.com/paper/1906.09777/) (2019)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Tensor-Train Recurrent Neural Networks for Video Classification](https://mlsanity.com/paper/1707.01786/) (2017)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [Long-term Forecasting using Higher Order Tensor RNNs](https://mlsanity.com/paper/1711.00073/) (2017)
- [Expressive power of recurrent neural networks](https://mlsanity.com/paper/1711.00811/) (2017)
- [Latent Space Models for Dynamic Networks](https://mlsanity.com/paper/2005.08808/) (2020)
- [Multilinear tensor regression for longitudinal relational data](https://mlsanity.com/paper/1412.0048/) (2014)
- [Compressing Recurrent Neural Network with Tensor Train](https://mlsanity.com/paper/1705.08052/) (2017)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [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)
- [Tensor Methods and Recommender Systems](https://mlsanity.com/paper/1603.06038/) (2016)
- [Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regression](https://mlsanity.com/paper/1611.10349/) (2016)
- [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016)
- [Parsimonious Tensor Response Regression](https://mlsanity.com/paper/1501.07815/) (2015)
- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching](https://mlsanity.com/paper/1911.03804/) (2019)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [High-dimension Tensor Completion via Gradient-based Optimization Under Tensor-train Format](https://mlsanity.com/paper/1804.01983/) (2018)
- [Sparse and Low-rank Tensor Estimation via Cubic Sketchings](https://mlsanity.com/paper/1801.09326/) (2018)
- [Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent](https://mlsanity.com/paper/2206.09109/) (2022)

## Built on by (most cited first, 4 of 4)

- [Generalized Parallel Scaling with Interdependent Generations](https://mlsanity.com/paper/2510.01143/) (2025)
- [Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2512.07490/) (2025)
- [StoTAM: Stochastic Alternating Minimization for Tucker-Structured Tensor Sensing](https://mlsanity.com/paper/2601.13522/) (2026)
- [Structured Adaptive Tensor Prediction for Streaming Data](https://mlsanity.com/paper/2606.10085/) (2026)

## Abstract (arXiv)

Tensor decompositions, which represent an N-order tensor using approximately N factors of much smaller dimensions, can significantly reduce the number of parameters. This is particularly beneficial for high-order tensors, as the number of entries in a tensor grows exponentially with the order. Consequently, they are widely used in signal recovery and data analysis across domains such as signal processing, machine learning, and quantum physics. A computationally and memory-efficient approach to these problems is to optimize directly over the factors using local search algorithms such as gradient descent, a strategy known as the factorization approach in matrix and tensor optimization. However, the resulting optimization problems are highly nonconvex due to the multiplicative interactions between factors, posing significant challenges for convergence analysis and recovery guarantees. In this paper, we present a unified framework for the factorization approach to solving various tensor decomposition problems. Specifically, by leveraging the canonical form of tensor decompositions--where most factors are constrained to be orthonormal to mitigate scaling ambiguity--we apply Riemannian gradient descent (RGD) to optimize these orthonormal factors on the Stiefel manifold. Under a mild condition on the loss function, we establish a Riemannian regularity condition for the factorized objective and prove that RGD converges to the ground-truth tensor at a linear rate when properly initialized. Notably, both the initialization requirement and the convergence rate scale polynomially rather than exponentially with N, improving upon existing results for Tucker and tensor-train format tensors.