@online{zandieh2202.12995,
TITLE = {Near Optimal Reconstruction of Spherical Harmonic Expansions},
AUTHOR = {Zandieh, Amir and Han, Insu and Avron, Haim},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2202.12995},
EPRINT = {2202.12995},
EPRINTTYPE = {arXiv},
YEAR = {2022},
ABSTRACT = {We propose an algorithm for robust recovery of the spherical harmonic<br>expansion of functions defined on the d-dimensional unit sphere<br>$\mathbb{S}^{d-1}$ using a near-optimal number of function evaluations. We show<br>that for any $f \in L^2(\mathbb{S}^{d-1})$, the number of evaluations of $f$<br>needed to recover its degree-$q$ spherical harmonic expansion equals the<br>dimension of the space of spherical harmonics of degree at most $q$ up to a<br>logarithmic factor. Moreover, we develop a simple yet efficient algorithm to<br>recover degree-$q$ expansion of $f$ by only evaluating the function on<br>uniformly sampled points on $\mathbb{S}^{d-1}$. Our algorithm is based on the<br>connections between spherical harmonics and Gegenbauer polynomials and leverage<br>score sampling methods. Unlike the prior results on fast spherical harmonic<br>transform, our proposed algorithm works efficiently using a nearly optimal<br>number of samples in any dimension d. We further illustrate the empirical<br>performance of our algorithm on numerical examples.<br>},
}