Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations

Abstract

Robust tensor CP decomposition involves decomposing a tensor into low rank and sparse components. We propose a novel non-convex iterative algorithm with guaranteed recovery. It alternates between low-rank CP decomposition through gradient ascent (a variant of the tensor power method), and hard thresholding of the residual. We prove convergence to the globally optimal solution under natural incoherence conditions on the low rank component, and bounded level of sparse perturbations. We compare our method with natural baselines which apply robust matrix PCA either to the {\em flattened} tensor, or to the matrix slices of the tensor. Our method can provably handle a far greater level of perturbation when the sparse tensor is block-structured. This naturally occurs in many applications such as the activity detection task in videos. Our experiments validate these findings. Thus, we establish that tensor methods can tolerate a higher level of gross corruptions compared to matrix methods.

References in corpus (1)

• Non-convex Robust PCA

Cited by in corpus (10)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• When Are Nonconvex Problems Not Scary?
• Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Convolutional Phase Retrieval via Gradient Descent
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Provable Online CP/PARAFAC Decomposition of a Structured Tensor via Dictionary Learning
• Guaranteed Simultaneous Asymmetric Tensor Decomposition via Orthogonalized Alternating Least Squares
• Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition