Learning algebraic decompositions using Prony structures

DOI10.1016/J.AAM.2020.102044MaRDI QIDQ2182612zbMATH OpenOpenAlexFDO

Authors Stefan Kunis, Tim Römer, Ulrich von der Ohe

Publication date 26 May 2020

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algebraic nature of Prony's methodHankel matricesmultivariate exponential sumProny structureProny's methodreconstruction methodToeplitz matrices

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Toeplitz, Cauchy, and related matrices (15B05) Moment problems and interpolation problems in the complex plane (30E05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We propose an algebraic framework generalizing several variants of Prony's method and explaining their relations. This includes Hankel and Toeplitz variants of Prony's method for the decomposition of multivariate exponential sums, polynomials (with respect to the monomial and Chebyshev bases), Gau{ss}ian sums, spherical harmonic sums, taking also into account whether they have their support on an algebraic set.

Review text

The recovery of a structured function from sampled data is a fundamental problem in signal processing. The classical Prony method recovers all parameters of a univariate exponential sum from sampled data. Up to now, several variants and multivariate generalizations of the classical Prony method are known. In this paper, the authors analyze the purely algebraic nature of Prony's reconstruction method. Therefore they introduce a general algebraic framework called Prony structures for reconstruction methods. This new approach allows a simultaneous treatment of decomposition problems for multivariate exponential sums, for multivariate polynomials, multivariate Gaussian sums, spherical harmonic sums, and eigenfunction sums.

Recommendations

• Prony's method in several variables
• Prony methods for recovery of structured functions
• Structured low rank decomposition of multivariate Hankel matrices
• Polynomial-exponential decomposition from moments
• A multivariate generalization of Prony's method

Cites work

• A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators
• A multivariate generalization of Prony's method
• A randomized multivariate matrix pencil method for superresolution microscopy
• Algorithms for computing cubatures based on moment theory
• Arithmetic circuits: a survey of recent results and open questions
• Differential geometry and Lie groups. A second course
• Early termination in sparse interpolation algorithms
• Faster sparse multivariate polynomial interpolation of straight-line programs
• Geometry and singularities of the Prony mapping
• How well can the concept of Padé approximant be generalized to the multivariate case?
• scientific article; zbMATH DE number 3489473 (Why is no real title available?)
• scientific article; zbMATH DE number 1216133 (Why is no real title available?)
• scientific article; zbMATH DE number 1262424 (Why is no real title available?)
• scientific article; zbMATH DE number 195102 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• scientific article; zbMATH DE number 2206382 (Why is no real title available?)
• Ideals, Varieties, and Algorithms
• Interpolation of polynomials given by straight-line programs
• Multivariate exponential analysis from the minimal number of samples
• Nonlinear approximation by sums of exponentials and translates
• Numerical Fourier analysis
• On exact and approximate interpolation of sparse rational functions
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Parameter estimation for exponential sums by approximate prony method
• Parameter estimation for multivariate exponential sums
• Parameter estimation for nonincreasing exponential sums by Prony-like methods
• Polynomial-exponential decomposition from moments
• Progress on polynomial identity testing
• Progress on polynomial identity testing. II
• Prony's method in several variables
• Prony's method in several variables: symbolic solutions by universal interpolation
• Prony's method on the sphere
• Prony's method under an almost sharp multivariate Ingham inequality
• Prony’s Method,Z-Transforms, and Padé Approximation
• Sparse interpolation of multivariate rational functions
• Sparse polynomial interpolation in Chebyshev bases
• Sparse Polynomial Interpolation in Nonstandard Bases
• Sparse polynomial interpolation with arbitrary orthogonal polynomial bases
• Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?
• Symmetric tensor decomposition
• The collected mathematical papers of James Joseph Sylvester. Volume I: (1837--1853). Edited by H. F. Baker
• The generalized operator based Prony method
• The interpolation problem for \(k\)-sparse polynomials and character sums
• The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators

Cited in

(9)

• Structured low rank decomposition of multivariate Hankel matrices
• Prony's method on the sphere
• Prony systems via decimation and homotopy continuation
• Recovery of atomic measures on the unit sphere
• An ``algebraic reconstruction of piecewise-smooth functions from integral measurements
• Prony's method in several variables
• Reconstruction of stationary and non-stationary signals by the generalized Prony method
• Multiscale matrix pencils for separable reconstruction problems
• Stabilized recovery and model reduction for multivariate exponential polynomials

Describes a project that uses

Uses Software

• FOXBOX

This page was built for publication: Learning algebraic decompositions using Prony structures

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