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
