# Near Optimal Reconstruction of Spherical Harmonic Expansions

arXiv: https://arxiv.org/abs/2202.12995 · HTML: https://mlsanity.com/paper/2202.12995/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 37 references that are in the map.
- First posted on arXiv 25 Feb 2022.

## Builds on (most cited first, 12 of 12)

- [Spherical Message Passing for 3D Graph Networks](https://mlsanity.com/paper/2102.05013/) (2021)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [Equivariance versus Augmentation for Spherical Images](https://mlsanity.com/paper/2202.03990/) (2022)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms](https://mlsanity.com/paper/1812.08723/) (2018)
- [Fourier-sparse interpolation without a frequency gap](https://mlsanity.com/paper/1609.01361/) (2016)
- [Random Gegenbauer Features for Scalable Kernel Methods](https://mlsanity.com/paper/2202.03474/) (2022)
- [Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time](https://mlsanity.com/paper/2202.04515/) (2022)
- [Dimension-independent Sparse Fourier Transform](https://mlsanity.com/paper/1902.10633/) (2019)

## Abstract (arXiv)

We propose an algorithm for robust recovery of the spherical harmonic expansion of functions defined on the d-dimensional unit sphere mathbbSd-1 using a near-optimal number of function evaluations. We show that for any f ∈ L2(mathbbSd-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 mathbbSd-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.