# Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 18 Jun 2022.

## Builds on (most cited first, 25 of 25)

- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm](https://mlsanity.com/paper/1804.03728/) (2018)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization](https://mlsanity.com/paper/1708.04181/) (2017)
- [Robust Low-rank Tensor Recovery: Models and Algorithms](https://mlsanity.com/paper/1311.6182/) (2013)
- [Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection](https://mlsanity.com/paper/2110.05649/) (2021)
- [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014)
- [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020)
- [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)
- [Accelerated Alternating Projections for Robust Principal Component Analysis](https://mlsanity.com/paper/1711.05519/) (2017)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimization](https://mlsanity.com/paper/2103.08895/) (2021)
- [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020)
- [Streaming PCA and Subspace Tracking: The Missing Data Case](https://mlsanity.com/paper/1806.04609/) (2018)
- [Robust Spectral Compressed Sensing via Structured Matrix Completion](https://mlsanity.com/paper/1304.8126/) (2013)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Tensor Regression Using Low-rank and Sparse Tucker Decompositions](https://mlsanity.com/paper/1911.03725/) (2019)
- [Static and Dynamic Robust PCA and Matrix Completion: A Review](https://mlsanity.com/paper/1803.00651/) (2018)
- [Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations](https://mlsanity.com/paper/1510.04747/) (2015)
- [Tensor Robust Principal Component Analysis: Better recovery with atomic norm regularization](https://mlsanity.com/paper/1901.10991/) (2019)

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

- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption](https://mlsanity.com/paper/2305.04080/) (2023)
- [Deep Unfolded Tensor Robust PCA with Self-supervised Learning](https://mlsanity.com/paper/2212.11346/) (2022)
- [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)
- [Learning Spatial-Temporal Regularized Tensor Sparse RPCA for Background Subtraction](https://mlsanity.com/paper/2309.15576/) (2023)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Low-Rank Adaptation Redux for Large Models](https://mlsanity.com/paper/2604.21905/) (2026)
- [Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCA](https://mlsanity.com/paper/2501.04565/) (2025)
- [Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2512.07490/) (2025)
- [Outlier-aware Tensor Robust Principal Component Analysis with Self-guided Data Augmentation](https://mlsanity.com/paper/2504.18323/) (2025)

## Abstract (arXiv)

An increasing number of data science and machine learning problems rely on computation with tensors, which better capture the multi-way relationships and interactions of data than matrices. When tapping into this critical advantage, a key challenge is to develop computationally efficient and provably correct algorithms for extracting useful information from tensor data that are simultaneously robust to corruptions and ill-conditioning. This paper tackles tensor robust principal component analysis (RPCA), which aims to recover a low-rank tensor from its observations contaminated by sparse corruptions, under the Tucker decomposition. To minimize the computation and memory footprints, we propose to directly recover the low-dimensional tensor factors -- starting from a tailored spectral initialization -- via scaled gradient descent (ScaledGD), coupled with an iteration-varying thresholding operation to adaptively remove the impact of corruptions. Theoretically, we establish that the proposed algorithm converges linearly to the true low-rank tensor at a constant rate that is independent with its condition number, as long as the level of corruptions is not too large. Empirically, we demonstrate that the proposed algorithm achieves better and more scalable performance than state-of-the-art matrix and tensor RPCA algorithms through synthetic experiments and real-world applications.