Search

ispartof: Siam Journal On Matrix Analysis And Applications vol:43 issue:2 pages:912-938 status: published

The canonical polyadic decomposition (CPD) is a compact decomposition which expresses a tensor as a sum of its rank-1 components. A common step in the computation of a CPD is computing a generalized eigenvalue decomposition (GEVD) of the tensor. A GEVD provides an algebraic approximation of the CPD which can then be used as an initialization in optimization routines. While in the noiseless setting GEVD exactly recovers the CPD, it has recently been shown that pencil-based computations such as GEVD are not stable. In this article we present an algebraic method for approximation of a CPD which greatly improves on the accuracy of GEVD. Our method is still fundamentally pencil-based; however, rather than using a single pencil and computing all of its generalized eigenvectors, we use many different pencils and in each pencil compute generalized eigenspaces corresponding to sufficiently well-separated generalized eigenvalues. The resulting "generalized eigenspace decomposition" is significantly more robust to noise than the classical GEVD. Accuracy of the generalized eigenspace decomposition is examined both empirically and theoretically. In particular, we provide a deterministic perturbation theoretic bound which is predictive of error in the computed factorization., 27 pages. 8 Figures. To appear in SIAM J. Matrix Anal. Appl

We propose a multilinear algebra framework to solve systems of polynomial equations with simple roots. We translate connections between univariate polynomial root-finding, eigenvalue decompositions...

Copyright © by SIAM. Coupled tensor decompositions are becoming increasingly important in signal processing and data analysis. However, the uniqueness properties of coupled tensor decompositions have not yet been studied. In this paper, we first provide new uniqueness conditions for one factor matrix of the coupled canonical polyadic decomposition (CPD) of third-order tensors. Then, we present necessary and sufficient overall uniqueness conditions for the coupled CPD of third-order tensors. The results demonstrate that improved uniqueness conditions can indeed be obtained by taking into account the coupling between several tensor decompositions. We extend the results to higher-order tensors and explain that the higher-order structure can further improve the uniqueness results. We discuss the special case of coupled matrix-tensor factorizations. We also present a new variant of the coupled CPD model called the coupled block term decomposition (BTD). On one hand, the coupled BTD can be seen as a variant of coupled CPD for the case where the common factor contains collinear columns. On the other hand, it can also be seen as an extension of the decomposition into multilinear rank-(Lr, Lr, 1) terms to coupled factorizations. ispartof: SIAM Journal on Matrix Analysis and Applications vol:36 issue:2 pages:496-522 status: published

International audience; 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 column-wise 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 column-wise 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.

We present a new necessary and sufficient condition for essential uniqueness of the decomposition of a third-order tensor in rank-$(L_r,L_r,1)$ terms. We derive a new deterministic technique for blind signal separation that relies on this decomposition. The method assumes that the signals can be modeled as linear combinations of exponentials or, more generally, as exponential polynomials. The results are illustrated by means of numerical experiments.

Higher-order tensors are used in many application fields, such as statistics, signal processing, and scientific computing. Efficient and reliable algorithms for manipulating these multi-way arrays are thus required. In this paper, we focus on the best rank-$(R_1,R_2,R_3)$ approximation of third-order tensors. We propose a new iterative algorithm based on the trust-region scheme. The tensor approximation problem is expressed as a minimization of a cost function on a product of three Grassmann manifolds. We apply the Riemannian trust-region scheme, using the truncated conjugate-gradient method for solving the trust-region subproblem. Making use of second order information of the cost function, superlinear convergence is achieved. If the stopping criterion of the subproblem is chosen adequately, the local convergence rate is quadratic. We compare this new method with the well-known higher-order orthogonal iteration method and discuss the advantages over Newton-type methods. Read More: http://epubs.siam.org/doi/abs/10.1137/090764827

Computing the Candecomp/Parafac (CP) solution of $R$ components (i.e., the best rank-$R$ approximation) for a generic $I\times J\times 2$ array may result in diverging components, also known as “degeneracy.” In such a case, several components are highly correlated in all three modes, and their component weights become arbitrarily large. Evidence exists that this is caused by the nonexistence of an optimal CP solution. Instead of using CP, we propose to compute the best approximation by means of a generalized Schur decomposition (GSD), which always exists. The obtained GSD solution is the limit point of the sequence of CP updates (whether it features diverging components or not) and can be separated into a nondiverging CP part and a sparse Tucker3 part or into a nondiverging CP part and a smaller GSD part. We show how to obtain both representations and illustrate our results with numerical experiments.

In this paper we study a generalization of Kruskal's permutation lemma to partitioned matrices. We define the k'-rank of partitioned matrices as a generalization of the k-rank of matrices. We derive a lower-bound on the k'-rank of Khatri-Rao products of partitioned matrices. We prove that Khatri-Rao products of partitioned matrices are generically full column rank.

In this paper we introduce a new class of tensor decompositions. Intuitively, we decompose a given tensor block into blocks of smaller size, where the size is characterized by a set of mode-$n$ ranks. We study different types of such decompositions. For each type we derive conditions under which essential uniqueness is guaranteed. The parallel factor decomposition and Tucker's decomposition can be considered as special cases in the new framework. The paper sheds new light on fundamental aspects of tensor algebra.

In this paper we derive alternating least squares algorithms for the computation of the block term decompositions introduced in Part II. We show that degeneracy can also occur for block term decompositions.

The canonical decomposition of higher-order tensors is a key tool in multilinear algebra. First we review the state of the art. Then we show that, under certain conditions, the problem can be rephrased as the simultaneous diagonalization, by equivalence or congruence, of a set of matrices. Necessary and sufficient conditions for the uniqueness of these simultaneous matrix decompositions are derived. In a next step, the problem can be translated into a simultaneous generalized Schur decomposition, with orthogonal unknowns [A.-J. van der Veen and A. Paulraj, IEEE Trans. Signal Process., 44 (1996), pp. 1136--1155]. A first-order perturbation analysis of the simultaneous generalized Schur decomposition is carried out. We discuss some computational techniques (including a new Jacobi algorithm) and illustrate their behavior by means of a number of numerical experiments.

In this paper, we show that the restricted singular value decomposition of a matrix triplet $A\in \R^{n \times m}, B\in \R^{n \times l}, C\in \R^{p \times m}$ can be computed by means of the cosine-sine decomposition. In the first step, the matrices A, B, C are reduced to a lower-dimensional matrix triplet ${\cal A}, {\cal B}, {\cal C}$, in which ${\cal B}$ and ${\cal C}$ are nonsingular, using orthogonal transformations such as the QR-factorization with column pivoting and the URV decomposition. In the second step, the components of the restricted singular value decomposition of A, B, C are derived from the singular value decomposition of ${\cal B}^{-1}{\cal A}{\cal C}^{-1}$. Instead of explicitly forming the latter product, a link with the cosine-sine decomposition, which can be computed by Van Loan's method, is exploited. Some numerical examples are given to show the performance of the presented method.

In this paper we discuss a multilinear generalization of the best rank-R approximation problem for matrices, namely, the approximation of a given higher-order tensor, in an optimal least-squares sense, by a tensor that has prespecified column rank value, row rank value, etc. For matrices, the solution is conceptually obtained by truncation of the singular value decomposition (SVD); however, this approach does not have a straightforward multilinear counterpart. We discuss higher-order generalizations of the power method and the orthogonal iteration method.

We discuss a multilinear generalization of the singular value decomposition. There is a strong analogy between several properties of the matrix and the higher-order tensor decomposition; uniqueness, link with the matrix eigenvalue decomposition, first-order perturbation effects, etc., are analyzed. We investigate how tensor symmetries a ect the decomposition and propose a multilinear generalization of the symmetric eigenvalue decomposition for pair-wise symmetric tensors. ispartof: SIAM Journal on Matrix Analysis and Applications vol:21 issue:4 pages:1253-1278 status: published