A generalized Prony method for sparse approximation

We derive a new generalization of Prony's method to reconstruct M-sparse expansions of (generalized) eigenfunctions of linear operators from only O(M) suitable values in a deterministic way. The proposed method covers the well-known reconstruction methods for M-sparse sums of exponentials as well as for the interpolation of M-sparse polynomials by using special linear operators. Further, we can derive new reconstruction formulas for M-sparse expansions of orthogonal polynomials using the Sturm-Liouville operator. The method is also applied to the recovery of M-sparse vectors in finite-dimensional vector spaces.