Low rank decomposition, completion problems and applications : low rank decomposition of Hankel matrices and tensors

Jouhayna Harmouch 1
1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , National and Kapodistrian University of Athens
Abstract : We study the decomposition of a multivariate Hankel matrix as a sum of Hankel matrices of small rank in correlation with the decomposition of its symbol σ as a sum of polynomialexponential series. We present a new algorithm to compute the low rank decomposition of the Hankel operator and the decomposition of its symbol exploiting the properties of the associated Artinian Gorenstein quotient algebra . A basis of is computed from the Singular Value Decomposition of a sub-matrix of the Hankel matrix . The frequencies and the weights are deduced from the generalized eigenvectors of pencils of shifted sub-matrices of Explicit formula for the weights in terms of the eigenvectors avoid us to solve a Vandermonde system. This new method is a multivariate generalization of the so-called Pencil method for solving Pronytype decomposition problems. We analyse its numerical behaviour in the presence of noisy input moments, and describe a rescaling technique which improves the numerical quality of the reconstruction for frequencies of high amplitudes. We also present a new Newton iteration, which converges locally to the closest multivariate Hankel matrix of low rank and show its impact for correcting errors on input moments. We study the decomposition of a multi-symmetric tensor T as a sum of powers of product of linear forms in correlation with the decomposition of its dual as a weighted sum of evaluations. We use the properties of the associated Artinian Gorenstein Algebra to compute the decomposition of its dual which is defined via a formal power series τ. We use the low rank decomposition of the Hankel operator associated to the symbol τ into a sum of indecomposable operators of low rank. A basis of is chosen such that the multiplication by some variables is possible. We compute the sub-coordinates of the evaluation points and their weights using the eigen-structure of multiplication matrices. The new algorithm that we propose works for small rank. We give a theoretical generalized approach of the method in n dimensional space. We show a numerical example of the decomposition of a multi-linear tensor of rank 3 in 3 dimensional space. We show a numerical example of the decomposition of a multi-symmetric tensor of rank 3 in 3 dimensional space. We study the completion problem of the low rank Hankel matrix as a minimization problem. We use the relaxation of it as a minimization problem of the nuclear norm of Hankel matrix. We adapt the SVT algorithm to the case of Hankel matrix and we compute the linear operator which describes the constraints of the problem and its adjoint. We try to show the utility of the decomposition algorithm in some applications such that the LDA model and the ODF model.
Document type :
Theses
Complete list of metadatas

Cited literature [50 references]  Display  Hide  Download

https://tel.archives-ouvertes.fr/hal-02073968
Contributor : Abes Star <>
Submitted on : Tuesday, April 16, 2019 - 10:47:10 AM
Last modification on : Friday, May 10, 2019 - 12:23:13 PM

File

2018AZUR4236.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : hal-02073968, version 2

Collections

Citation

Jouhayna Harmouch. Low rank decomposition, completion problems and applications : low rank decomposition of Hankel matrices and tensors. Algebraic Geometry [math.AG]. Université Côte d'Azur; Université libanaise, 2018. English. ⟨NNT : 2018AZUR4236⟩. ⟨hal-02073968v2⟩

Share

Metrics

Record views

133

Files downloads

73