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

Harry Dong, Tian Tong, Cong Ma, Yuejie Chi

Introduction

In the era of big data, multi-way arrays known as tensors have become essential for capturing complex, multi-dimensional relationships in data such as video sequences (height, width, time, and color). However, analyzing these structures is often hindered by two primary challenges: sparse corruptions and ill-conditioning. Real-world data is frequently "dirty," containing sensor failures or adversarial outliers that manifest as sparse but large errors. Furthermore, the underlying signals often possess components of vastly different scales, leading to ill-conditioned data that causes standard gradient descent algorithms to converge at an agonizingly slow pace.

While Matrix Robust Principal Component Analysis (RPCA) is well-established, extending these techniques to tensors is computationally difficult. Existing tensor methods often rely on expensive convex optimization or suffer from slow convergence when data is ill-conditioned. This research introduces a new algorithm for Tensor RPCA that utilizes Scaled Gradient Descent (ScaledGD) to achieve fast, linear convergence regardless of the data's condition number.

Methodology

The proposed approach utilizes a non-convex framework based on the Tucker decomposition, which represents a high-dimensional tensor through a small core tensor and several factor matrices. The algorithm alternates between two primary phases:

  1. Corruption Pruning: The method employs an iteration-varying soft-thresholding operation. In the early stages, the algorithm ignores large residuals to avoid being misled by outliers. As the low-rank estimate improves, the threshold drops geometrically, allowing for the precise identification and removal of sparse corruptions.
  2. Factor Refinement via ScaledGD: To address ill-conditioning, the authors implement "Scaled" updates. By preconditioning the gradients with the inverse of the factor matrices' Gram matrices, the algorithm balances the steps across different components. This ensures that the convergence rate remains constant, even when the tensor is highly ill-conditioned.

The process is anchored by a tailored spectral initialization, which provides a high-quality starting point by performing a Higher-Order Singular Value Decomposition (HOSVD) on a cleaned version of the initial observations.

Key Theoretical Insights

Condition Number Independence

A major contribution of this work is the proof that ScaledGD’s convergence rate is independent of the tensor’s condition number. In practice, this means the algorithm does not slow down when some parts of the signal are significantly weaker than others, a common failure point for standard first-order methods.

Refined Entrywise Analysis

The paper provides the first refined entrywise error analysis for tensor RPCA. It demonstrates that if the ground truth tensor is "incoherent" (meaning information is spread across the structure rather than concentrated), the errors remain distributed evenly across entries. This prevents error "bunching" that could otherwise degrade the recovery of specific data points.

Selective Mode Updates

For specific applications like video processing, the authors observed that updating every part of the Tucker decomposition in every iteration is unnecessary. By focusing updates on the "temporal" mode (the frames), they achieved a 4.6x to 5x speed-up per iteration without sacrificing the quality of the recovered signal.

Experimental Evaluation

The authors evaluated ScaledGD across synthetic and real-world datasets:

  • Synthetic Data: Testing confirmed linear convergence and robustness across various ranks, corruption levels, and condition numbers.
  • MNIST Database: The algorithm successfully performed image denoising and outlier detection on sequences of handwritten digits.
  • VIRAT Dataset: In real-world video surveillance tasks, ScaledGD effectively separated static backgrounds from moving foreground objects (background subtraction), significantly outperforming state-of-the-art methods like Riemannian Gradient Descent (RiemannianGD) and Tensor Nuclear Norm (TNN) in terms of scalability and speed.

Conclusion and Future Work

ScaledGD offers a robust, memory-efficient, and mathematically grounded solution for Tensor RPCA. It achieves linear convergence and maintains performance even in the presence of heavy corruption and ill-conditioning.

Future research directions include extending the framework to Tensor Completion (handling missing data points) and adapting the algorithm for Streaming Data, which would allow for real-time tensor tracking in live video feeds. Additionally, the authors aim to develop more automated methods for hyperparameter tuning to make the algorithm more accessible for general use.

Summary updated

Abstract

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.
BibTeX
@misc{dong2022fast,
  author = {Harry Dong and Tian Tong and Cong Ma and Yuejie Chi},
  title = {{Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent}},
  year = {2022},
  eprint = {2206.09109},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.09109},
}
Figure