mlsanityData to 7 Oct 2026

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

arXiv 2206.09109 ↗First posted 18 Jun 2022stat.ML cs.LG eess.SPcited by 11

Not on the map. Why?

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.

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

Builds on

25 of 49 references.

References · 25

  1. 2019Optuna: A Next-generation Hyperparameter Optimization Frameworkcited by 2,455
  2. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  3. 2018Tensor Robust Principal Component Analysis with A New Tensor Nuclear Normcited by 110
  4. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  5. 2014Non-convex Robust PCAcited by 41
  6. 2016Fast Algorithms for Robust PCA via Gradient Descentcited by 39
  7. 2020An Optimal Statistical and Computational Framework for Generalized Tensor Estimationcited by 39
  8. 2017Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimizationcited by 35
  9. 2021Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detectioncited by 34
  10. 2013Robust Low-rank Tensor Recovery: Models and Algorithmscited by 33
  11. 2014On Tensor Completion via Nuclear Norm Minimizationcited by 32
  12. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
13 more
  1. 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
  2. 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 27
  3. 2017Accelerated Alternating Projections for Robust Principal Component Analysiscited by 25
  4. 2018Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimationcited by 25
  5. 2021Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimizationcited by 24
  6. 2020Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Datacited by 23
  7. 2018Streaming PCA and Subspace Tracking: The Missing Data Casecited by 18
  8. 2013Robust Spectral Compressed Sensing via Structured Matrix Completioncited by 13
  9. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  10. 2019Tensor Regression Using Low-rank and Sparse Tucker Decompositionscited by 10
  11. 2018Static and Dynamic Robust PCA and Matrix Completion: A Reviewcited by 6
  12. 2015Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbationscited by 5
  13. 2019Tensor Robust Principal Component Analysis: Better recovery with atomic norm regularizationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 0; 2025: 5; 2026: 1.

11 papers.

  1. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  2. 2023Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruptioncited by 11
  3. 2022Deep Unfolded Tensor Robust PCA with Self-supervised Learningcited by 7
  4. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  5. 2025Generalized Parallel Scaling with Interdependent Generationscited by 6
  6. 2023Learning Spatial-Temporal Regularized Tensor Sparse RPCA for Background Subtractioncited by 4
  7. 2025A Scalable Factorization Approach for High-Order Structured Tensor Recoverycited by 4
  8. 2025Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCAcited by 2
  9. 2026Low-Rank Adaptation Redux for Large Modelscited by 2
  10. 2025Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descentcited by 1
  11. 2025Outlier-aware Tensor Robust Principal Component Analysis with Self-guided Data Augmentationcited by 0