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

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

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

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

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

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

Cited In (6)

• Recovery from Power Sums
• Short Communication: Weak Sparse Superresolution is Well-Conditioned
• Approximation and interpolation of singular measures by trigonometric polynomials
• Prony's method on the sphere
• Learning algebraic decompositions using Prony structures
• Recovery of Atomic Measures on the Unit Sphere

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)