Under-Determined Tensor Diagonalization for Decomposition of Difficult Tensors

Analysis of multidimensional arrays, usually called tensors, often becomes difficult in cases when the tensor rank (a minimum number of rank-one components) exceeds all the tensor dimensions. Traditional methods of canonical polyadic decomposition of such tensors, namely the alternating least squares, can be used, but a presence of a large number of false local minima can make the problem hard. Usually, multiple random initializations are advised in such cases, but the question is how many such random initializations are sufficient to get a good chance of finding the right solution. It appears that the number of the initializations can be very large. We propose a novel approach to the problem. The given tensor is augmented by some unknown parameters to the shape that admits ordinary tensor diagonalization, i.e., transforming the augmented tensor into an exact or nearly diagonal form through multiplying the tensor by non-orthogonal invertible matrices. Three possible constraints are proposed to make the optimization problem well defined. The method can be modified for an under-determined block-term decomposition.