Generalized Vandermonde Determinants Over the Chebyshev Basis

TitleGeneralized Vandermonde Determinants Over the Chebyshev Basis
Publication TypeTechnical Report
Year of Publication1993
AuthorsWerther, T.
Other Numbers812

The recent developments in the area of interpolation and learnability of sparse polynomials over the reals are based on the nonsingularity of the generalized Vandermonde matrix. In this paper we study real polynomials that admit sparse representations in the Chebyshev basis. The main result of the paper states the analogy of Michell's theorem for the Chebyshev case, i.e. the determinant of the generalized Vandermonde matrix build over the Chebyshev basis can be represented in this basis as the product of the standard Vandermonde determinant and a polynomial with nonnegative integer coefficients. An immediate consequence of this result is the nonsingularity of Vandermonde matrices over the Chebyshev basis provided that the indeterminates take distinct values greater 1.As an application, we investigate the relationship between the number of real roots of a polynomial and its sparsity with respect to the Chebyshev basis. We prove that the number of real zeros of a polynomial, either to the left or to the right of the interval of orthogonality, does not exceed its sparsity with respect to the Chebyshev basis. The bound on the number of real roots is used to prove finiteness of the Vapnik- Chervonenkis dimension (and thereby uniform learnability) of the class of polynomials of bounded sparsity over the Chebyshev basis.

Bibliographic Notes

ICSI Technical Report TR-93-024

Abbreviated Authors

T. Werther

ICSI Publication Type

Technical Report