Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?

DOI10.1007/S10444-019-09672-2zbMATH Open1417.90112OpenAlexW2901849449MaRDI QIDQ2000529FDOQ2000529

Authors: Cédric Josz, Jean B. Lasserre, Bernard Mourrain 

Publication date: 28 June 2019

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

Abstract: We show that the sparse polynomial interpolation problem reduces to a discrete super-resolution problem on the $n$-dimensional torus. Therefore the semidefinite programming approach initiated by Cand`es \& Fernandez-Granda cite{candes_towards_2014} in the univariate case can be applied. We extend their result to the multivariate case, i.e., we show that exact recovery is guaranteed provided that a geometric spacing condition on the supports holds and the number of evaluations are sufficiently many (but not many). It also turns out that the sparse recovery LP-formulation of $el{l}_1$-norm minimization is also guaranteed to provide exact recovery {it provided that} theevaluations are made in a certain manner and even though the Restricted Isometry Property for exact recovery is not satisfied. (A naive sparse recovery LP-approach does not offer such a guarantee.) Finally we also describe the algebraic Prony method for sparse interpolation, which also recovers the exact decomposition but from less point evaluations and with no geometric spacing condition. We provide two sets of numerical experiments, one in which the super-resolution technique and Prony's method seem to cope equally well with noise, and another in which the super-resolution technique seems to cope with noise better than Prony's method, at the cost of an extra computational burden (i.e. a semidefinite optimization).

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

Recommendations

• scientific article; zbMATH DE number 1104515
• Symbolic-numeric sparse interpolation of multivariate polynomials
• MultiDimensional Sparse Super-Resolution
• Polynomial homotopy method for the sparse interpolation problem. I: Equally spaced sampling
• Reconstructing sparse exponential polynomials from samples: difference operators, Stirling numbers and Hermite interpolation

zbMATH Keywords

linear programmingsemidefinite programmingsuper-resolutionProny's method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Linear programming (90C05) Semidefinite programming (90C22) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Probabilistic and RIPless Theory of Compressed Sensing
• A generalized flat extension theorem for moment matrices
• A multivariate generalization of Prony's method
• A performance analysis of subspace-based methods in the presence of model errors. I. The MUSIC algorithm
• Decoding by Linear Programming
• Decomposition of Low Rank Multi-symmetric Tensor
• Exact Solutions to Super Resolution on Semi-Algebraic Domains in Higher Dimensions
• Exact support recovery for sparse spikes deconvolution
• Exponential data fitting and its applications
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Fast estimates of Hankel matrix condition numbers and numeric sparse interpolation
• Interpolating polynomials from their values
• Lasserre hierarchy for large scale polynomial optimization in real and complex variables
• Linear Programming
• MultiDimensional Sparse Super-Resolution
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Nearly optimal sparse Fourier transform
• Nonlinear approximation by sums of nonincreasing exponentials
• On approximation of functions by exponential sums
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Optimization, a Moment Problem, and Nonlinear Programming
• Polynomial-exponential decomposition from moments
• Prony's method in several variables
• Separable nonlinear least squares: the variable projection method and its applications
• Shift-register synthesis and BCH decoding
• Sparse Interpolation and Rational Approximation
• Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values
• Spike detection from inaccurate samplings
• Stable signal recovery from incomplete and inaccurate measurements
• Super-resolution from noisy data
• Symbolic-numeric sparse interpolation of multivariate polynomials
• The restricted isometry property and its implications for compressed sensing
• Towards a Mathematical Theory of Super‐resolution
• Truncated \(K\)-moment problems in several variables

Cited In (8)

• Recovery from Power Sums
• A scale and shift paradigm for sparse interpolation in one and more dimensions
• Short Communication: Weak Sparse Superresolution is Well-Conditioned
• Recovery of atomic measures on the unit sphere
• Numerical sparsity determination and early termination
• Approximation and interpolation of singular measures by trigonometric polynomials
• Prony's method on the sphere
• Learning algebraic decompositions using Prony structures

This page was built for publication: Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?

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