A Caltech Library Service

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

Anandkumar, Animashree and Jain, Prateek and Shi, Yang and Niranjan, U. N. (2015) Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Additional Information:Animashree Anandkumar is supported in part by Microsoft Faculty Fellowship, NSF Career Award CCF-1254106, ONR Award N00014-14-1-0665, ARO YIP Award W911NF-13-1-0084, and AFOSR YIP FA9550-15-1-0221. Yang Shi is supported by NSF Career Award CCF-1254106 and ONR Award N00014-15-1-2737, Niranjan is supported by NSF BigData Award IIS-1251267 and ONR Award N00014-15-1-2737.
Funding AgencyGrant Number
Microsoft Faculty FellowshipUNSPECIFIED
Office of Naval Research (ONR)N00014-14-1-0665
Army Research Office (ARO)W911NF-13-1-0084
Air Force Office of Scientific Research (AFOSR)FA9550-15-1-0221
Office of Naval Research (ONR)N00014-15-1-2737
Record Number:CaltechAUTHORS:20190401-123303824
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94322
Deposited By: George Porter
Deposited On:01 Apr 2019 22:58
Last Modified:03 Oct 2019 21:02

Repository Staff Only: item control page