next up previous contents
Next: Solver - inverse transforms Up: NFSFT - nonequispaced fast Previous: Legendre polynomials and associated   Contents

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

$\displaystyle 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.,

$\displaystyle \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

$\displaystyle 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

$\displaystyle \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''

$\displaystyle \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

$\displaystyle 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{displaymath}\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}\end{displaymath}    

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

$\displaystyle \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

$\displaystyle \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].


\begin{algorithm}
% latex2html id marker 1063
[tb]
\caption[NFSFT]{Nonequispace...
...y: $\mathcal{O}\left(N^2 \log^2 N +
M\right)$.
\end{algorithmic}\end{algorithm}


\begin{algorithm}
% latex2html id marker 1107
[tb]
\caption[Adjoint NFSFT]{Adjo...
...y: $\mathcal{O}\left(N^2 \log^2 N +
M\right)$.
\end{algorithmic}\end{algorithm}


next up previous contents
Next: Solver - inverse transforms Up: NFSFT - nonequispaced fast Previous: Legendre polynomials and associated   Contents
Jens Keiner 2006-11-20