Guaranteed Tensor Decomposition: A Moment Approach
[edit]
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:14911500, 2015.
Abstract
We develop a theoretical and computational framework to perform guaranteed tensor decomposition, which also has the potential to accomplish other tensor tasks such as tensor completion and denoising. We formulate tensor decomposition as a problem of measure estimation from moments. By constructing a dual polynomial, we demonstrate that measure optimization returns the correct CP decomposition under an incoherence condition on the rankone factors. To address the computational challenge, we present a hierarchy of semidefinite programs based on sumsofsquares relaxations of the measure optimization problem. By showing that the constructed dual polynomial is a sumofsquares modulo the sphere, we prove that the smallest SDP in the relaxation hierarchy is exact and the decomposition can be extracted from the solution under the same incoherence condition. One implication is that the tensor nuclear norm can be computed exactly using the smallest SDP as long as the rankone factors of the tensor are incoherent. Numerical experiments are conducted to test the performance of the moment approach.
Related Material



