Structured low rank decomposition of multivariate Hankel matrices

DOI10.1016/J.LAA.2017.04.015MaRDI QIDQ2002778zbMATH OpenOpenAlexFDO

Authors J. Harmouch, Houssam Khalil, Bernard Mourrain

Publication date 12 July 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05805

zbMATH Keywords

eigenvectorexponential seriesHankel matrixlow rank decompositionpolynomialsingular value decomposition

Mathematics Subject Classification ID

Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Toeplitz, Cauchy, and related matrices (15B05) Toeplitz operators, Hankel operators, Wiener-Hopf operators (47B35) Symbolic computation and algebraic computation (68W30)

Abstract: We study the decomposition of a multivariate Hankel matrix H_$sigma$ as a sum of Hankel matrices of small rank in correlation with the decomposition of its symbol $sigma$ as a sum of polynomial-exponential 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_$sigma$. A basis of A_$sigma$ is computed from the Singular Value Decomposition of a sub-matrix of the Hankel matrix H_$sigma$. The frequencies and the weights are deduced from the generalized eigenvectors of pencils of shifted sub-matrices of H $sigma$. 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 Prony-type 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.

Recommendations

• Polynomial-exponential decomposition from moments
• A simple method for computing the Vandermonde decomposition of a Hankel tensor
• scientific article; zbMATH DE number 1820172
• A fast method to diagonalize a Hankel matrix
• Learning algebraic decompositions using Prony structures

Cites work

• A multivariate generalization of Prony's method
• A performance analysis of subspace-based methods in the presence of model errors. I. The MUSIC algorithm
• A polynomial approach to linear algebra
• Exponential data fitting and its applications
• General tensor decomposition, moment matrices and applications
• How bad are Hankel matrices?
• How bad are Vandermonde matrices?
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Introduction to the solution of polynomial systems
• Isolated points, duality and residues
• Low rank approximation. Algorithms, implementation, applications
• Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise
• Multivariate polynomials, duality, and structured matrices
• Nonlinear approximation by sums of nonincreasing exponentials
• Nonlinear approximation of functions in two dimensions by sums of exponential functions
• On approximation of functions by exponential sums
• On the numerical condition of a generalized Hankel eigenvalue problem
• Parameter estimation for multivariate exponential sums
• Polynomial-exponential decomposition from moments
• Separable nonlinear least squares: the variable projection method and its applications
• Symmetric tensor decomposition
• The condition number of real Vandermonde, Krylov and positive definite Hankel matrices

Cited in

(13)

• Polynomial-exponential decomposition from moments
• Low rank approximation of a Hankel matrix by structured total least norm
• Riemannian Newton optimization methods for the symmetric tensor approximation problem
• Tensor decomposition for learning Gaussian mixtures from moments
• Learning algebraic decompositions using Prony structures
• A randomized multivariate matrix pencil method for superresolution microscopy
• Lasserre hierarchy for large scale polynomial optimization in real and complex variables
• ESPRIT for Multidimensional General Grids
• scientific article; zbMATH DE number 1820172 (Why is no real title available?)
• Hankel Tensor Decompositions and Ranks
• Stabilized recovery and model reduction for multivariate exponential polynomials
• Multidimensional unstructured sparse recovery via eigenmatrix
• Polynomial optimization in geometric modeling

This page was built for publication: Structured low rank decomposition of multivariate Hankel matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2002778)