Search

The canonical polyadic decomposition (CPD) of a low rank tensor plays a major role in data analysis and signal processing by allowing for unique recovery of underlying factors. However, it is well known that the low rank CPD approximation problem is ill-posed. That is, a tensor may fail to have a best rank $R$ CPD approximation when $R>1$. This article gives deterministic bounds for the existence of best low rank tensor approximations over $\mathbb{K}=\mathbb{R}$ or $\mathbb{K}=\mathbb{C}$. More precisely, given a tensor $\mathcal{T} \in \mathbb{K}^{I \times I \times I}$ of rank $R \leq I$, we compute the radius of a Frobenius norm ball centered at $\mathcal{T}$ in which best $\mathbb{K}$-rank $R$ approximations are guaranteed to exist. In addition we show that every $\mathbb{K}$-rank $R$ tensor inside of this ball has a unique canonical polyadic decomposition. This neighborhood may be interpreted as a neighborhood of "mathematical truth" in with CPD approximation and computation is well-posed. In pursuit of these bounds, we describe low rank tensor decomposition as a ``joint generalized eigenvalue" problem. Using this framework, we show that, under mild assumptions, a low rank tensor which has rank strictly greater than border rank is defective in the sense of algebraic and geometric multiplicities for joint generalized eigenvalues. Bounds for existence of best low rank approximations are then obtained by establishing perturbation theoretic results for the joint generalized eigenvalue problem. In this way we establish a connection between existence of best low rank approximations and the tensor spectral norm. In addition we solve a "tensor Procrustes problem" which examines orthogonal compressions for pairs of tensors. The main results of the article are illustrated by a variety of numerical experiments., 46 pages. 8 Figures. Includes supplementary proofs. To appear in SIAM J. Matrix Anal. Appl

Decompositions of higher-order tensors into sums of simple terms are ubiquitous. We show that in order to verify that two tensors are generated by the same (possibly scaled) terms it is not necessary to compute the individual decompositions. In general the explicit computation of such a decomposition may have high complexity and can be ill-conditioned. We now show that under some assumptions the verification can be reduced to a comparison of both the column and row spaces of the corresponding matrix representations of the tensors. We consider rank-1 terms as well as low multilinear rank terms (also known as block terms) and show that the number of the terms and their multilinear rank can be inferred as well. The comparison relies only on numerical linear algebra and can be done in a numerically reliable way. We also illustrate how our results can be applied to solve a multi-label classification problem that appears in the context of blind source separation., 24 pages

Tensor decompositions play an important role in a variety of applications, such as signal processing and machine learning. In practice, the tensor can be incomplete or very large, making it difficu...

© 2015 Society for Industrial and Applied Mathematics. The uniqueness properties of the canonical polyadic decomposition (CPD) of higherorder tensors make it an attractive tool for signal separation. However, CPD uniqueness is not yet fully understood. In this paper, we first present a new uniqueness condition for a polyadic decomposition (PD) where one of the factor matrices is assumed to be known. We also show that this result can be used to obtain a new overall uniqueness condition for the CPD. In signal processing the CPD factor matrices are often constrained. Building on the preceding results, we provide a new uniqueness condition for a CPD with a columnwise orthonormal factor matrix, representing uncorrelated signals. We also obtain a new uniqueness condition for a CPD with a partial Hermitian symmetry, useful for tensors in which covariance matrices are stacked, which are common in statistical signal processing. We explain that such constraints can lead to more relaxed uniqueness conditions. Finally, we provide an inexpensive algorithm for computing a PD with a known factor matrix that is also useful for the computation of the full CPD. ispartof: SIAM Journal on Matrix Analysis and Applications vol:36 issue:4 pages:1381-1403 status: published

We find conditions that guarantee that a decomposition of a generic third-order tensor in a minimal number of rank-$1$ tensors (canonical polyadic decomposition (CPD)) is unique up to permutation of rank-$1$ tensors. Then we consider the case when the tensor and all its rank-$1$ terms have symmetric frontal slices (INDSCAL). Our results complement the existing bounds for generic uniqueness of the CPD and relax the existing bounds for INDSCAL. The derivation makes use of algebraic geometry. We stress the power of the underlying concepts for proving generic properties in mathematical engineering., Comment: 23 pages

© 2015 Society for Industrial and Applied Mathematics. The coupled canonical polyadic decomposition (CPD) is an emerging tool for the joint analysis of multiple data sets in signal processing and statistics. Despite their importance, linear algebra based algorithms for coupled CPDs have not yet been developed. In this paper, we first explain how to obtain a coupled CPD from one of the individual CPDs. Next, we present an algorithm that directly takes the coupling between several CPDs into account. We extend the methods to single and coupled decompositions in multilinear rank-(Lr,n, Lr,n, 1) terms. Finally, numerical experiments demonstrate that linear algebra based algorithms can provide good results at a reasonable computational cost. ispartof: SIAM Journal on Matrix Analysis and Applications vol:36 issue:3 pages:1015-1045 status: published

Canonical Polyadic Decomposition (CPD) of a third-order tensor is decomposition in a minimal number of rank-$1$ tensors. We call an algorithm algebraic if it is guaranteed to find the decomposition when it is exact and if it only relies on standard linear algebra (essentially sets of linear equations and matrix factorizations). The known algebraic algorithms for the computation of the CPD are limited to cases where at least one of the factor matrices has full column rank. In the paper we present an algebraic algorithm for the computation of the CPD in cases where none of the factor matrices has full column rank. In particular, we show that if the famous Kruskal condition holds, then the CPD can be found algebraically., 32 pages = 25 pages of paper itself + 7 pages of supplementary materials

Canonical Polyadic (also known as Candecomp/Parafac) Decomposition (CPD) of a higher-order tensor is decomposition in a minimal number of rank-1 tensors. In Part I, we gave an overview of existing results concerning uniqueness and presented new, relaxed, conditions that guarantee uniqueness of one factor matrix. In Part II we use these results for establishing overall CPD uniqueness in cases where none of the factor matrices has full column rank. We obtain uniqueness conditions involving Khatri-Rao products of compound matrices and Kruskal-type conditions., 28 pages