Loading [MathJax]/jax/output/CommonHTML/jax.js

Near Optimal Reconstruction of Spherical Harmonic Expansions

Part of Advances in Neural Information Processing Systems 36 (NeurIPS 2023) Main Conference Track

Bibtex Paper Supplemental

Authors

Amir Zandieh, Insu Han, Haim Avron

Abstract

We propose an algorithm for robust recovery of the spherical harmonic expansion of functions defined on the d-dimensional unit sphere Sd1 using a near-optimal number of function evaluations. We show that for any fL2(Sd1), 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 kernel regression-based algorithm to recover degree-q expansion of f by only evaluating the function on uniformly sampled points on Sd1. Our algorithm is built upon the connections between spherical harmonics and Gegenbauer polynomials. 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. Furthermore, we illustrate the empirical performance of our algorithm on numerical examples.