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

Abstract

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