Tensor Deflation for CANDECOMP/PARAFAC— Part I: Alternating Subspace Update Algorithm.

CANDECOMP/PARAFAC (CP) approximates multiway data by sum of rank-1 tensors. Unlike matrix decomposition, the procedure which estimates the best rank-R tensor approximation through R sequential best rank-1 approximations does not work for tensors, because the deflation does not always reduce the tensor rank. In this paper, we propose a novel deflation method for the problem. When one factor matrix of a rank-R CP decomposition is of full column rank, the decomposition can be performed through (R-1) rank-1 reductions. At each deflation stage, the residue tensor is constrained to have a reduced multilinear rank. For decomposition of order-3 tensors of size R\times R\times R and rank-R, estimation of one rank-1 tensor has a computational cost of \cal O(R^3) per iteration which is lower than the cost \cal O(R^4) of the ALS algorithm for the overall CP decomposition. The method can be extended to tracking one or a few rank-one tensors of slow changes, or inspect variations of common patterns in individual datasets. [ABSTRACT FROM PUBLISHER]