Wissen, was gut ist. Studieren in Chemnitz.
Daniel Potts, Manfred Tasche: Sparse polynomial interpolation in Chebyshev bases

Daniel Potts, Manfred Tasche: Sparse polynomial interpolation in Chebyshev bases

Author(s):
Daniel Potts
Manfred Tasche
Title:
Daniel Potts, Manfred Tasche: Sparse polynomial interpolation in Chebyshev bases
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 09, 2012
Mathematics Subject Classification:
65D05 [Interpolation]
41A45 [Approximation by arbitrary linear expressions]
65F15 [Eigenvalues, eigenvectors]
65F20 [Overdetermined systems, pseudoinverses]
Abstract:
We study the problem of reconstructing a sparse polynomial in a basis of Chebyshev polynomials (Chebyshev basis in short) from given samples on a Chebyshev grid of $[-1,\,1]$. A polynomial is called $M$-sparse in a Chebyshev basis, if it can be represented by a linear combination of $M$ Chebyshev polynomials. We show that an $M$-sparse polynomial of maximum degree $2N-1$ can be theoretically recovered from $2M$ samples on a Chebyshev grid. As efficient recovery methods, Prony--like methods are used. The reconstruction results are mainly presented for bases of Chebyshev polynomials of first and second kind, respectively. But similar issues can be obtained for bases of Chebyshev polynomials of third and fourth kind, respectively.
Keywords:
Sparse interpolation, Chebyshev basis, Chebyshev polynomial, sparse polynomial, Prony--like method, ESPRIT, matrix pencil factorization, companion matrix, Prony polynomial, eigenvalue problem, rectangular Toeplitz-plus-Hankel matrix
Language:
English
Publication time:
08/2012