< Back to previous page

Project

Study of Canonical Polyadic Decomposition of Higher-Order Tensors

In many applications signals or data  vary with respect to severalparameters (such as spatial coordinates, velocity,
time, frequency,temperature, etc.) and are therefore naturally represented by higher-order  arrays of numerical values, which
are called higher-order tensors.

Matrices are tensors of order two.
By definition,  a matrix is rank-1 if its  columns (or equivalently,  rows) are proportional.
A decomposition of matrix into a minimal number (known as the rank of the matrix) of rank-1 matrices
is not unique.
Indeed, there are many ways to write a matrix as a product of two  matrices and every such
factorization  can be associated with a decomposition of  a matrix into a sum of rank-1 matrices.

Onthe other hand, the factorization of  a  matrix into two or more  structured matrices
can be unique. The uniqueness of structured matrix factorizations (and hence, the uniqueness of decompositionsof a matrix into a sum of structured
rank-1 matrices) has  found many applications in engineering.
A famous example is  the singular value decomposition (SVD) --- a factorization
into  threematrices: a matrix with orthonormal columns, a diagonal
matrix with positive values on the main diagonal, and a matrix with orthonormal rows.
It is well known that the SVD is unique if and only if the diagonalentries of the second matrix are distinct.

In several cases theconstraints on factor matrices
that guarantee uniqueness of matrix decompositions are hard to justify from an application point of view.

By  definition, a tensor is rank-1 if its  columns (resp. rows, fibers, etc.) are proportional.
A decomposition of a tensor in a minimal number of rank-1 tensors is called the Canonical Polyadic Decomposition (CPD),
and the number of terms in the CPD is called the rank of tensor.

The CPD was introduced by F. Hitchcock in 1927 but it was not in use until
1970 when it was rediscovered as the CanonicalDecomposition (Candecomp) in Psychometrics and the  Parallel Factor Model (Parafac) in Chemometrics.
The  interest in CPD from theside of data analysts and engineers was due to the  remarkable property that  CPD is unique  under very mild conditions.
Moreover, under simple constraints on the tensor dimensions the CPD is unique with probability one (``generic uniqueness'').

Over the years CPD has found many applications in Signal Processing, Data Analysis, Machine Learning, Chemometrics,
Psychometrics, etc.

For instance, in Chemometrics, one wishes to estimate the spectra and the concentrations of the chemicals present in a given solution.
This can be done by decomposing a third-order tensor, which mathematically splits the mixture into a sum
of rank-1 tensors that correspond to spectra of the chemicals and their concentrations.

In Chapter 1 we introduce CPD andrecall some well-known applications in Chemometrics and Signal Processing.

In Chapter 2  we  consider the case where at least one factor matrix is unique.
The situation where one factor matrix isunique but the overall CPD is not, is typical for tensors with collinear loading vectors in some mode.
We employ linear algebra tools to obtain new results on compound matrices.
Then we obtain new conditions guaranteeing minimality of the number of terms and  uniqueness of one factor matrix.

In Chapter 3 we study the overall uniqueness of the CPD.
We also obtain new results on generic  uniqueness of the  structured CPD, i.e.,
the case where factor matrices analytically depend on some parameters.
This  includes the cases of partially symmetric tensors, tensors with Hankel, Toeplitz or Vandermonde factor matrices and cases where some entries of factor
matrices are not allowed to change.

In Chapter 4 we present  two algorithmsfor the computation
of CPD. Both algorithms  work under mild conditions on factor matrices
(for instance, under the  famous Kruskal condition) and reduce the problem to a generalized eigenvalue decomposition.

In the thesis we restrict ourselves to  third-order tensors. New results for  tensors of order higher than three
can be easily derived from the third-order case by reshaping the higher-order tensor into a third-order tensor, with partial loss of structure.
Date:20 Apr 2009 →  19 Sep 2013
Keywords:Signal separation
Disciplines:Other engineering and technology
Project type:PhD project