Spherical harmonics

The spherical harmonics $Y_k^n : \S ^2 \rightarrow \ensuremath{\mathbb{C}}$ , $k \ge \vert n\vert$ , $n\in\ensuremath{\mathbb{Z}}$ , are given by

$$Y_k^n(\vartheta,\varphi) := P_k^{n}(\cos\vartheta) \, \mathrm{e}^{\mathrm{i} n \varphi}.$$

They form an orthogonal basis for the space of square integrable functions on the sphere, i.e.,

$$\left\langle Y_k^n,Y_l^m \right\rangle = \int_{0}^{2\pi} \int_{0}... ...} \vartheta \; \mathrm{d} \varphi = \frac{4\pi}{2k+1} \delta_{k,l}\delta_{n,m}.$$

The orthonormal spherical harmonics are denoted by $\bar{Y}_k^n = \sqrt{\frac{2k+1}{4\pi}} Y_k^n$ .

Hence, any square integrable function $f:\S ^2\rightarrow\ensuremath{\mathbb{C}}$ has the expansion

$$f = \sum_{k=0}^{\infty} \sum_{n=-k}^{k} \hat{f}(k,n) \bar{Y}_k^n,$$

with the spherical Fourier coefficients $\hat{f}(k,n) = \left\langle f, \bar{Y}_k^n \right\rangle$ . The function $f$ is called bandlimited, if $\hat{f}(k,n)=0$ for $k>N$ and some $N\in\ensuremath{\mathbb{N}}$ . In analogy to the NFFT on the Torus $\mathbb{T}$ , we define the sampling set

$$\mathcal{X}: = \left\{\left(\vartheta_{j},\varphi_{j}\right) \in \mathbb{S}^2:\,j=0,\hdots,M-1\right\}$$

of nodes on the sphere $\S ^2$ and the set of possible ''frequencies''

$$\mathcal{I}_{N} := \left\{(k,n):\,k=0,1,\ldots,N;\; n=-k,\ldots,k\right\}.$$

The nonequispaced discrete spherical Fourier transform (NDSFT) is defined as the evaluation of the finite spherical Fourier sum

$$f_j= f\left(\vartheta_{j},\varphi_{j}\right) = \sum_{(k,n) \in \,... ...k=0}^N \sum_{n=-k}^k \hat{f}_k^n \, Y_k^n\left(\vartheta_{j},\varphi_{j}\right)$$ (3.1)

for $j=0,\hdots,M-1$ . In matrix vector notation, this reads $\mathbf{f} = \mathbf{Y} \; \mathbf{\hat f}$ with

$$\begin{split}\mathbf{f} & := \left(f_j\right)_{j=0}^{M-1} \in... ...{(k,n) \in \mathcal{I}_N} \in \mathbb{C}^{(N+1)^2}. \end{split}$$

The corresponding adjoint nonequispaced discrete fast spherical Fourier transform (adjoint NDSFT) is defined as the evaluation of

$$\hat h_{k}^n = \sum_{j = 0}^{M-1} f\left(\vartheta_{j},\varphi_{j}\right) \overline{Y_k^n\left(\vartheta_{j},\varphi_{j}\right)}$$

for all $(k,n) \in \mathcal{I}_{N}$ . Again, in matrix vector notation, this reads $\mathbf{\hat h} = \mathbf{Y}^{{\vdash \hspace*{-1.72mm} \dashv}} \, \mathbf{f}$ .

The coefficients $\hat h_{k}^n$ are, in general, not identical to the Fourier coefficients $\hat{f}(k,n)$ of the function $f$ . However, provided that for the sampling set $\mathcal{X}$ a quadrature rule with weights $w_{j}$ , $j=0,\hdots,M-1$ , and sufficient degree of exactness is available, one might recover the Fourier coefficients $\hat{f}(k,n)$ by evaluating

$$\hat{f}_{k}^n = \int_{0}^{2\pi} \int_{0}^{\pi} f(\vartheta,\varph... ...a_{j},\varphi_{j}\right) \overline{Y_k^n\left(\vartheta_{j},\varphi_{j}\right)}$$

for all $(k,n) \in \mathcal{I}_{N}$ .

Direct algorithms for computing the NDSFT and adjoint NDSFT transformations need ${\cal O}(M N^2)$ arithmetic operations. A combination of the fast polynomial transform and the NFFT leads to approximate algorithms with ${\cal O}(N^2 \log^2 N + M)$ arithmetic operations. These are denoted NFSFT and adjoint NFSFT, respectively. The NFSFT algorithm using the FPT and the NFFT was introduced in [34] while the adjoint NFSFT variant was developed in [32].