---
abstract: 'A fast algorithm for Antoine and Vandergheynst’s (1998) directional Continuous Spherical Wavelet Transform () is presented. Computational requirements are reduced by a factor of $\complexity(\sqrt{\num_{\rm pix}})$, when $\num_{\rm pix}$ is the number of pixels on the sphere. The spherical  wavelet Gaussianity analysis of the  1-year data performed by Vielva  (2003) is reproduced and confirmed using the fast . The proposed extension to directional analysis is inherently afforded by the fast  algorithm.'
address: 'Cavendish Laboratory, Madingley Road, Cambridge CB3 0HE, U.K.'
author:
- 'J.D. MCEWEN, M.P. HOBSON, A.N. LASENBY and D.J. MORTLOCK'
title: |
    A FAST DIRECTIONAL CONTINUOUS SPHERICAL\
    WAVELET TRANSFORM
---

Introduction
============

A range of primordial processes imprint signatures on the temperature fluctuations of the  (). For instance, various cosmic defect and non-standard inflationary models predict non-Gaussian anisotropies. By studying the Gaussianity of the  anisotropies evidence may be provided for competing scenarios of the early Universe. In addition, a number of astrophysical processes introduce secondary sources of non-Gaussianity. Measurement systematics or contamination may also be highlighted by Gaussianity analysis.

Wavelets are a powerful tool for probing the Gaussianity of anisotropies. Previous wavelet analysis of the , however, has been restricted to simple spherical Haar and isotropic Mexican Hat wavelets. A directional analysis on the full sky has previously been prohibited by the computational infeasibility of any implementation. We rectify this problem by providing a fast algorithm for Antoine and Vandergheynst’s[@antoine:1998] Continuous Spherical Wavelet Transform (), based on the fast spherical convolution proposed by Wandelt and Górski[@wandelt:2001].

The remainder of this paper is organised as follows. The  is presented in and the fast implementation in . In the fast  is applied to reproduce the non-Gaussianity  analysis performed by Vielva [@vielva:2003]. Concluding remarks are made in .

A directional Continuous Spherical Wavelet Transform {#sec:cswt}
====================================================

Antoine and Vandergheynst[@antoine:1998] extend Euclidean wavelet analysis to spherical geometry by constructing a wavelet basis on the sphere. The natural extension of Euclidean motions on the sphere are rotations, defined by where we parameterise $\rho$ by the Euler angles $(\eulers)$. Dilations on the sphere, denoted $(\dil_\scale f)(\sa) = f_\scale(\sa)$, are constructed by first lifting the sphere  to the plane by a norm preserving stereographic projection from the South pole, performing the usual Euclidean dilation in the plane, before re-projecting back onto . Mother spherical wavelets are constructed simply by projecting Euclidean planar wavelets onto the sphere by a norm preserving inverse stereographic projection. A wavelet basis on  may be constructed from rotations and dilations of an admissible mother spherical wavelet. The corresponding wavelet family $\{ \wav_{\scale,\rho} \equiv \rot_\rho \dil_\scale \wav,
\, \rho \in SO(3), \, \scale \in \real_{\ast}^{+} \}$ provides an over-complete set of functions in $L^2(\sphere)$. The  is given by the projection onto each wavelet basis function $$\skywav(\scale, \eulers) =
\int_{\sphere}
(\rot_{\eulers} \wav_\scale)^\conj(\sa) \:
\sky(\sa) \:
d\mu(\sa)
\spcend ,
\label{eqn:cswt}$$ where the  denotes complex conjugation and $d\mu(\sa)=\sin(\saa)
\, d\saa \, d\sab$ is the usual rotation invariant measure on the sphere.

Fast algorithm {#sec:fast}
==============

A direct implementation of the  is simply not computationally feasible for a data set of any practical size; a fast algorithm is essential. At a particular scale the  is essentially a spherical convolution, hence it is possible to apply Wandelt and Górski’s[@wandelt:2001] fast spherical convolution algorithm to rapidly evaluate the transform.

Fast implementation {#sec:harmonic}
-------------------

There does not exist any finite point set on the sphere that is invariant under rotations, hence it is more natural, and in fact more accurate for numerical purposes, to recast the  in spherical harmonic space. The Wigner rotation matrices (defined by Brink and Satchler[@brink:1993], for example) introduced to characterise the rotation of a spherical harmonic may be decomposed as $
\dmatbig_{mm\p}^{l}(\eulers)
= e^{-\img m\eulera} \:
\dmatsmall_{mm\p}^l(\eulerb) \:
e^{-\img m\p\eulerc}
$. This decomposition is exploited by factoring the rotation into two separate rotations, both of which contain a constant $\pm \pi/2$ polar rotation: $
\rot_{\eulers}
= \rot_{\eulera-\pi/2, \; -\pi/2, \; \eulerb} \:\:
\rot_{0, \; \pi/2, \; \eulerc+\pi/2}
$. By uniformly sampling and applying some algebra the  may be recast as $$\skywav [\ind_\eulera, \ind_\eulerb, \ind_\eulerc] =
e^{-\img 2\pi [ 
\frac{\ind_\eulera \lmax}{\num_\eulera} +
\frac{\ind_\eulerb \lmax}{\num_\eulerb} +
\frac{\ind_\eulerc \mmax}{\num_\eulerc}]}
\sum_{j=0}^{\num_\eulera-1} \:
\sum_{j\p=0}^{\num_\eulerb-1} \:
\sum_{j\pp=0}^{\num_\eulerc-1}
\cswtfftterm_{j, j\p, j\pp} \:
e^{ \img 2\pi [
\frac{j\ind_\eulera}{\num_\eulera} +
\frac{j\p \ind_\eulerb}{\num_\eulerb} +
\frac{j\pp \ind_\eulerc}{\num_\eulerc}]}
\spcend ,
\label{eqn:cswt_fast}$$ where the summation is simply the unnormalised  inverse discrete Fourier transform of $$\cswtfftterm_{m+\lmax, m\p+\lmax, m\pp+\mmax} =
e^{i(m\pp-m)\pi/2} 
\sum_{l=\max(\mid m \mid, \mid m\p \mid, \mid m\pp \mid)}^{\lmax}
\dmatsmall_{m\p m}^l(\pi/2) \:
\dmatsmall_{m\p m\pp}^l(\pi/2) \:
\shcoeff{\wav}_{lm\pp}{}^\conj \:
\shcoeff{\sky}_{lm}
\spcend ,
\label{eqn:cswt_fast_term}$$ where $\shcoeff{\cdot}_{lm}$ denote spherical harmonic coefficients, $\lmax$ and $\mmax$ define the general and azimuthal band limits of the wavelet respectively and the shifted indices show the conversion between the harmonic and Fourier conventions. The  may be performed very rapidly in spherical harmonic space by using fast Fourier techniques to rapidly and simultaneously evaluate , once is precomputed.[^1]

Comparison with other algorithms
--------------------------------

Direct and semi-fast (where only one rotation is performed in Fourier space) implementations of the  are also possible. A comparison of the theoretical complexity and typical execution times of each algorithm is presented in . The fast  algorithm provides a saving of $\complexity(\sqrt{\num_{\rm pix}})$ for $\num_{\rm pix}$ pixels on the sphere.

 non-Gaussianity analysis {#sec:cmb}
=========================

We reproduce the Gaussianity analysis of Vielva [@vielva:2003], preprocessing the  data in the same manner. The resolution of the co-added map defined by Komatsu [@komatsu:2003] is down-sampled by a factor or 4, before the *[Kp0]{}* exclusion mask is applied to remove emissions due to the Galactic plane and known point sources.

Spherical wavelet analysis
--------------------------

The  is a linear operation, hence the wavelet coefficients of a Gaussian map will also obey a Gaussian distribution. To test for deviations from Gaussianity, skewness and kurtosis statistics are calculated for each wavelet coefficient map at each scale. Monte Carlo simulations are performed to construct confidence bounds on the test statistics.

The application of the *Kp0* mask distorts coefficients corresponding to wavelets that overlap with the mask exclusion region. These wavelet coefficients must be removed from any subsequent analysis. Our construction of an extended coefficient exclusion mask differs to that of Vielva  and inherently accounts for the dominant distortion (either point-source or Galactic plane) at each scale. The only non-zero coefficients in a  of the original mask are those that are distorted (due to the zero-mean property of spherical wavelets). These may be easily detected and the coefficient exclusion mask extended accordingly.

Results
-------

We reproduce the results of Vielva [@vielva:2003] for the spherical  wavelet analysis of the co-added  data. The  wavelet scales $\{ \scale_i \}_{i=1}^{11} = \{ 14, 
25, 50, 75, 100, 150, 200, \linebreak 250, 300, 400, 500\}_{i=1}^{11}$ acrmin are considered, corresponding to an effective size of the sky of $\effsize_i=4\tan^{-1}(  a_i/\sqrt{2} ) \approx 2\sqrt{2} \, \scale_i $ (defined as the angular separation between opposite zero-crossings). shows the skewness and kurtosis of the coefficients at each scale. The wavelet analysis inherently allows one to localise signal components on the sky, as illustrated in . We make similar observations to Vielva [@vielva:2003], although the different coefficient exclusion masks [produce]{} slight discrepancies. These discrepancies do not alter the general findings of the analysis.

Conclusions and future work {#sec:conc}
===========================

A fast algorithm is presented and evaluated for performing a directional  on the sphere. The fast implementation reduces the complexity of the  by $\complexity(\sqrt{\num_{\rm pix}})$, where $\num_{\rm pix}$ is the number of pixels on the sphere. Furthermore, the numerical accuracy of the  is improved by elegantly representing rotations in harmonic space.

The Gaussianity analysis of the  1-year data performed by Vielva [@vielva:2003] has been reproduced and confirmed using the fast . We consider the extension to a full directional analysis in an upcoming publication by McEwen [@mcewen:2004]; preliminary findings indicate deviations from Gaussianity outside of the 99% confidence level.

References {#references .unnumbered}
==========

[99]{}

, [*J. Math. Phys.*, 39, 8, 3987–4008]{}. [(1998)]{}.

, [*Angular Momentum* (3rd Ed.)]{}, [Clarendon Press, Oxford]{}, [(1993)]{}.

, [*ApJ*, 148, 119]{}, [(2003)]{}.

, [*Preprint* (/0406604)]{}, submitted to MNRAS, [(2004)]{}.

, [*Preprint* (/0310273)]{}, submitted to ApJ, [(2003)]{}.

, [*Phys. Rev.*, 63, 123002, 1–6]{}, [(2001)]{}.

[^1]: Memory and computational requirements may be reduced by a further factor of two for real signals by exploiting the conjugate symmetry relationship $\cswtfftterm_{-m,-m\p,-m\pp}=\cswtfftterm_{m,m\p,m\pp}^\conj$.
