  We present the Fast Chebyshev Transform (FCT), a fast, randomized algorithm
to compute a Chebyshev approximation of functions in high-dimensions from the
knowledge of the location of its nonzero Chebyshev coefficients. Rather than
sampling a full-resolution Chebyshev grid in each dimension, we randomly sample
several grids with varied resolutions and solve a least-squares problem in
coefficient space in order to compute a polynomial approximating the function
of interest across all grids simultaneously. We theoretically and empirically
show that the FCT exhibits quasi-linear scaling and high numerical accuracy on
challenging and complex high-dimensional problems. We demonstrate the
effectiveness of our approach compared to alternative Chebyshev approximation
schemes. In particular, we highlight our algorithm's effectiveness in high
dimensions, demonstrating significant speedups over commonly-used alternative
techniques.
