Multi-subspace power method for decomposing partially symmetric tensors
This work addresses the problem of tensor decomposition for a broad class of symmetries, offering a practical improvement over existing methods for practitioners in signal processing, data analysis, and machine learning.
The authors present an algorithm for low-rank decomposition of partially symmetric tensors that overcomes the failure of the higher-order power method by transforming the tensor to have orthonormal slices. The algorithm achieves higher accuracy and faster runtime than existing methods in numerical experiments.
We present an algorithm for low rank decomposition of tensors of any symmetry type, from fully asymmetric to fully symmetric. It recovers the decomposition one summand at a time via the higher-order power method. This approach is known to fail in general: there need not be a relationship between the summands of a decomposition and the (partially symmetric) singular vector tuples (pSVTs) of the tensor. Our approach overcomes this problem by transforming the input to a tensor with orthonormal slices, via orthogonalization of a flattening. The summands of the decomposition of the original tensor can be recovered from the pSVTs of this new transformed tensor. We introduce a shifted power method for computing pSVTs and prove its global convergence. Numerical experiments demonstrate that our algorithm achieves higher accuracy and faster runtime than existing methods.