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és & Fernandez-Granda in the univariate case (and later extended to the multi-variate setting) can be applied. In particular, exact recovery is guaranteed provided that a geometric spacing condition on the "support " holds and the number of evaluations are sufficiently many (but not many). It also turns out that the (compressed sensing) LP-formulation of ell_1-norm minimization is also guaranteed to provide exact recovery provided that the evaluations are made in a certain manner and even though the Restricted Isometry Property for exact recovery is not satisfied. (A naive compressed sensing 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 also compare the three techniques on some numerical experiments.