< 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.
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