We derive a generalization for the reconstruction of M -sparse sums in Chebyshev bases of the third and fourth kind. This work is used for a polynomial with Chebyshev sparsity and samples on a Chebyshev grid of [−1, 1]. | Turk J Math (2016) 40: 250 – 271 ¨ ITAK ˙ c TUB ⃝ Turkish Journal of Mathematics doi: Research Article Sparse sums with bases of Chebyshev polynomials of the third and fourth kind Maryam SHAMS SOLARY∗ Department of Mathematics, Payame Noor University, Tehran, Iran Received: • Accepted/Published Online: • Final Version: Abstract: We derive a generalization for the reconstruction of M -sparse sums in Chebyshev bases of the third and fourth kind. This work is used for a polynomial with Chebyshev sparsity and samples on a Chebyshev grid of [−1, 1] . Further, fundamental reconstruction algorithms can be a way for getting M-sparse expansions of Chebyshev polynomials of the third and fourth kind. The numerical results for these algorithms are designed to compare the time effects of doing them. Key words: Sparse interpolation, Chebyshev polynomial, Prony method, eigenvalue problem, Toeplitz-plus-Hankel matrix, SVD, QR decomposition 1. Introduction A linear combination of Chebyshev polynomials with M nonzero coefficients, where M is much smaller than the degree, is called a M-sparse polynomial in the corresponding Chebyshev basis. One of the applications is the recovery and the repair of the sparse signals from a small set of measurements [11, 12]. There are also some efficient reconstruction algorithms for this work. One of them is a random recovery method such as Legendre expansion with M nonzero coefficients; see [8, 11]. Moreover, there are some deterministic methods for the reconstruction F (x) = M ∑ ck eiwk x k=1 with complex parameters ck and wk , k = 1, . . . , M , and −π < Imw1 < . . . < ImwM < π . We hope to reconstruct ck and wk from a given small amount of (possibly noisy) measurement values F (x) . In [9], Potts and Tasche introduced some processes for reconstruction of sparse expansions in bases of Chebyshev polynomials of the first and second kind. We are motivated