Sparse polynomial interpolation in Chebyshev bases

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 polynomia...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2014-01, Vol.441, p.61-87
Main Authors: Potts, Daniel, Tasche, Manfred
Format: Article
Language:English
Subjects:
41A45
65D05
65F15
65F20
Chebyshev basis
Chebyshev polynomial
Companion matrix
Eigenvalue problem
ESPRIT
Matrix pencil factorization
Prony polynomial
Prony-like method
Rectangular Toeplitz-plus-Hankel matrix
Sparse interpolation
Sparse polynomial
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. For a polynomial with known and unknown Chebyshev sparsity, respectively, we present efficient reconstruction methods, where 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.
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2013.02.006