Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Near Optimal Reconstruction of Spherical Harmonic Expansions


Zandieh,  Amir
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available

Zandieh, A., Han, I., & Avron, H. (2022). Near Optimal Reconstruction of Spherical Harmonic Expansions. Retrieved from https://arxiv.org/abs/2202.12995.

Cite as: https://hdl.handle.net/21.11116/0000-000C-9105-A
We propose an algorithm for robust recovery of the spherical harmonic
expansion of functions defined on the d-dimensional unit sphere
$\mathbb{S}^{d-1}$ using a near-optimal number of function evaluations. We show
that for any $f \in L^2(\mathbb{S}^{d-1})$, the number of evaluations of $f$
needed to recover its degree-$q$ spherical harmonic expansion equals the
dimension of the space of spherical harmonics of degree at most $q$ up to a
logarithmic factor. Moreover, we develop a simple yet efficient algorithm to
recover degree-$q$ expansion of $f$ by only evaluating the function on
uniformly sampled points on $\mathbb{S}^{d-1}$. Our algorithm is based on the
connections between spherical harmonics and Gegenbauer polynomials and leverage
score sampling methods. Unlike the prior results on fast spherical harmonic
transform, our proposed algorithm works efficiently using a nearly optimal
number of samples in any dimension d. We further illustrate the empirical
performance of our algorithm on numerical examples.