  In this paper, we build up a framework for sparse interpolation. We first
investigate the theoretical limit of the number of unisolvent points for sparse
interpolation under a general setting and try to answer some basic questions of
this topic. We also explore the relation between classical interpolation and
sparse interpolation. We second consider the design of the interpolation points
for the $s$-sparse functions in high dimensional Chebyshev bases, for which the
possible applications include uncertainty quantification, numerically solving
stochastic or parametric PDEs and compressed sensing. Unlike the traditional
random sampling method, we present in this paper a deterministic method to
produce the interpolation points, and show its performance with $\ell_1$
minimization by analyzing the mutual incoherence of the interpolation matrix.
Numerical experiments show that the deterministic points have a similar
performance with that of the random points.
