Search

In this work, we study the tensor ring decomposition and its associated numerical algorithms. We establish a sharp transition of algorithmic difficulty of the optimization problem as the bond dimension increases: On one hand, we show the existence of spurious local minima for the optimization landscape even when the tensor ring format is much overparameterized, i.e., with bond dimension much larger than that of the true target tensor. On the other hand, when the bond dimension is further increased, we establish one-loop convergence for the alternating least squares algorithm for the tensor ring decomposition. The theoretical results are complemented by numerical experiments for both local minima and the one-loop convergence for the alternating least squares algorithm. [ABSTRACT FROM AUTHOR]

A few iterations of alternating least squares with a random starting point provably suffice to produce nearly optimal spectral- and Frobenius-norm accuracies of low-rank approximations to a matrix; iterating to convergence of the matrix entries is unnecessary. Such good accuracy is in fact well known for the low-rank approximations calculated via subspace iterations and other well-known methods that happen to produce mathematically the same low-rank approximations as alternating least squares, at least when starting all the methods with the same appropriately random initializations. Thus, software implementing alternating least squares can be retrofitted via appropriate setting of parameters to calculate nearly optimally accurate low-rank approximations highly efficiently, with no need for convergence of the matrix entries. (Even so, convergence could still be helpful for some applications, say to ensure that the approximations are strongly rank-revealing.) [ABSTRACT FROM AUTHOR]

We propose a new method for low-rank approximation of Moore-Penrose pseudo-inverses of large-scale matrices using tensor networks. The computed pseudoinverses can be useful for solving or preconditioning of large-scale overdetermined or underdetermined systems of linear equations. The computation is performed efficiently and stably based on the modified alternating least squares scheme using low-rank tensor train (TT) decompositions and tensor network contractions. The formulated large-scale optimization problem is reduced to sequential smaller-scale problems for which any standard and stable algorithms can be applied. A regularization technique is incorporated in order to alleviate ill-posedness and obtain robust low-rank approximations. Numerical simulation results illustrate that the regularized pseudoinverses of a wide class of nonsquare or nonsymmetric matrices admit good approximate low-rank TT representations. Moreover, we demonstrated that the computational cost of the proposed method is only logarithmic in the matrix size given that the TT ranks of a data matrix and its approximate pseudoinverse are bounded. It is illustrated that a strongly nonsymmetric convection-diffusion problem can be efficiently solved by using the preconditioners computed by the proposed method. [ABSTRACT FROM AUTHOR]

With the notable exceptions of two cases--that tensors of order 2, namely, matrices, always have best approximations of arbitrary low ranks and that tensors of any order always have the best rank-1 approximation, it is known that high-order tensors may fail to have best low rank approximations. When the condition of orthogonality is imposed, even under the modest assumption of semiorthogonality where only one set of components in the decomposed rank-1 tensors is required to be mutually perpendicular, the situation is changed completely--orthogonal low rank approximations always exist. The purpose of this paper is to discuss the best low rank approximation subject to semiorthogonality. The conventional high-order power method is modified to address the desirable orthogonality via the polar decomposition. Algebraic geometry technique is employed to show that for almost all tensors the orthogonal alternating least squares method converges globally. [ABSTRACT FROM AUTHOR]

Tensor decomposition has important applications in various disciplines, but it remains an extremely challenging task even to this date. A slightly more manageable endeavor has been to find a low rank approximation in place of the decomposition. Even for this less stringent undertaking, it is an established fact that tensors beyond matrices can fail to have best low rank approximations, with the notable exception that the best rank-one approximation always exists for tensors of any order. Toward the latter, the most popular approach is the notion of alternating least squares whose specific numerical scheme appears in the form as a variant of the power method. Though the limiting behavior of the objective values is well understood, a proof of global convergence for the iterates themselves has been elusive. This paper partially addresses the missing piece by showing that for almost all tensors, the iterates generated by the alternating least squares method for the rank-one approximation converge globally. The underlying technique employed is an eclectic mix of knowledge from algebraic geometry and dynamical system. [ABSTRACT FROM AUTHOR]

The damped Gauss--Newton (dGN) algorithm for CANDECOMP/PARAFAC (CP) decomposition can handle the challenges of collinearity of factors and different magnitudes of factors; nevertheless, for factorization of an order-N tensor of size I1 x ... x IN with rank R, the algorithm is computationally demanding due to construction of a large approximate Hessian of size (RT x RT) and its inversion where T = Σn In. In this paper, we propose a fast implementation of the dGN algorithm which is based on novel expressions of the inverse approximate Hessian in block form. The new implementation has lower computational complexity, besides computation of the gradient (this part is common to both methods), requiring the inversion of a matrix of size NR² x NR², which is much smaller than the whole approximate Hessian, if T >> NR. In addition, the implementation has lower memory requirements, because neither the Hessian nor its inverse never needs to be stored in its entirety. A variant of the algorithm working with complex-valued data is proposed as well. Complexity and performance of the proposed algorithm is compared with those of dGN and ALS with line search on examples of difficult benchmark tensors. [ABSTRACT FROM AUTHOR]

Canonical polyadic decomposition (CPD) of a higher-order tensor is an important tool in mathematical engineering. In many applications at least one of the matrix factors is constrained to be columnwise orthonormal. We first derive a relaxed condition that guarantees uniqueness of the CPD under this constraint. Second, we give a simple proof of the existence of the optimal low-rank approximation of a tensor in the case that a factor matrix is columnwise orthonormal. Third, we derive numerical algorithms for the computation of the constrained CPD. In particular, orthogonality-constrained versions of the CPD methods based on simultaneous matrix diagonalization and alternating least squares are presented. Numerical experiments are reported. [ABSTRACT FROM AUTHOR]