Fast Directional Correlation on the Sphere with Steerable Filters

Yves Wiaux, Laurent Jacques, P. Vielva, Pierre VandergheynstThe Astrophysical Journal 2006 · DOI

TL;DR

This paper introduces a significantly faster algorithm for analyzing directional features in spherical data, like the Cosmic Microwave Background (CMB). By leveraging steerable filters and spherical harmonics, they reduce computation times from years to seconds, making detailed analysis of large-scale sky maps computationally feasible.

What Problem Does This Paper Address?

Analyzing the Cosmic Microwave Background (CMB) is crucial for understanding the universe's origins and evolution. The CMB, imprinted on the sky, contains subtle temperature and polarization anisotropies that can reveal information about fundamental physics, such as non-Gaussianity or statistical anisotropy. To detect these subtle features, especially local ones, researchers need to perform "directional correlation" – essentially, analyzing how a signal behaves when viewed from different directions. However, a naive approach to this on the sphere is computationally prohibitive, requiring years of processing for current and future high-resolution sky maps (like those from WMAP and Planck). This paper aims to bridge this gap by developing a computationally efficient method for directional correlation.

Methods

The core of the paper lies in a clever combination of mathematical tools:

  • Steerable Filters: These are filters whose orientation can be precisely controlled without recomputing them from scratch. This allows for efficient directional analysis.
  • Spherical Harmonics: These are the 3D equivalent of Fourier series, used to decompose functions on a sphere into a set of basis functions. The paper utilizes scalar spherical harmonics for signal representation.
  • Wigner D-functions: These are used to represent rotations in 3D space and are crucial for handling the directional aspect of the correlation.
  • Separation of Variables: By breaking down the spherical harmonics transform into independent operations along the polar and azimuthal angles, the computational complexity is reduced from O(L⁵) to O(L³).
  • Sampling Theorems (Driscoll & Healy): For specific "equi-angular" pixelizations of the sphere, these theorems allow for exact computation of spherical harmonics transforms, further optimizing the process.

The algorithm essentially transforms the signal and filters into their spherical harmonic representations, performs a computationally cheaper correlation in this domain, and then transforms back. The steerability of the filters allows this correlation to be expressed solely in terms of direct and inverse scalar spherical harmonics transforms.

Datasets

The paper uses simulated CMB temperature maps for evaluation. These simulations are generated using the angular power spectrum that best fits the three-year WMAP data, up to a band limit of L=1024. The authors also discuss the relevance to real CMB data from missions like WMAP and Planck, which use HEALPix pixelizations.

Key Insights and Ideas

  • Steerability is Key: The ability to "steer" filters without recomputing them is fundamental to achieving computational efficiency for directional analysis on the sphere.
  • Spherical Harmonics Domain Efficiency: Performing the correlation in the spherical harmonics domain, rather than directly on the pixelized map, drastically reduces computational cost.
  • Equi-angular Grids Offer Exactness: For specific equi-angular pixelizations, the use of sampling theorems allows for theoretically exact spherical harmonics transforms, a significant advantage over approximate methods.
  • CMB Analysis Revolutionized: The speedup achieved makes detailed scale-space analysis of CMB temperature and polarization data, including the search for non-Gaussianity and anisotropy, computationally accessible for the first time at high resolutions.

Key Results

  • Massive Speedup: The algorithm reduces the computation time for directional correlation of maps with millions of pixels (L~10³) from years to tens of seconds on a single standard computer.
  • O(L³) Complexity: The overall asymptotic complexity for the directional correlation with steerable filters is reduced to O(L³), a significant improvement over the naive O(L⁵) approach.
  • O(L² log³ L) Potential: On equi-angular pixelizations, with pre-calculated Legendre polynomials, the complexity can be further reduced to O(L² log³ L).
  • Numerical Stability: Both the equi-angular (SpharmonicKit) and HEALPix implementations demonstrate good numerical stability, with the equi-angular method offering theoretical exactness.
  • CMB Applications: The method is directly applicable to WMAP and Planck data, enabling detailed analysis of temperature and polarization maps.

Limitations and Future Work

  • Pixelization Choice: While both equi-angular and HEALPix implementations are discussed, the equi-angular grid offers theoretical exactness, which is a notable advantage. The choice between them might depend on specific application needs and existing data formats.
  • Pre-calculation Trade-off: For very high resolutions (L > 1024), pre-calculating associated Legendre polynomials for the equi-angular implementation can lead to prohibitive memory requirements. The authors opt for on-the-fly calculation, which increases computation time but keeps memory usage manageable.
  • Future Work: The paper suggests that this algorithm opens doors for various applications beyond CMB analysis, including the study of asymmetric beam effects and other fields requiring directional analysis on the sphere. The authors also highlight the potential for detecting local features in CMB data with unprecedented precision in both position and direction.

Summary updated

Abstract

A fast algorithm is developed for the directional correlation of scalar band-limited signals and band-limited steerable filters on the sphere. The asymptotic complexity associated to it through simple quadrature is of order O(L^5), where 2L stands for the square-root of the number of sampling points on the sphere, also setting a band limit L for the signals and filters considered. The filter steerability allows to compute the directional correlation uniquely in terms of direct and inverse scalar spherical harmonics transforms, which drive the overall asymptotic complexity. The separation of variables technique for the scalar spherical harmonics transform produces an O(L^3) algorithm independently of the pixelization. On equi-angular pixelizations, a sampling theorem introduced by Driscoll and Healy implies the exactness of the algorithm. The equi-angular and HEALPix implementations are compared in terms of memory requirements, computation times, and numerical stability. The computation times for the scalar transform, and hence for the directional correlation, of maps of several megapixels on the sphere (L~10^3) are reduced from years to tens of seconds in both implementations on a single standard computer. These generic results for the scale-space signal processing on the sphere are specifically developed in the perspective of the wavelet analysis of the cosmic microwave background (CMB) temperature (T) and polarization (E and B) maps of the WMAP and Planck experiments. As an illustration, we consider the computation of the wavelet coefficients of a simulated temperature map of several megapixels with the second Gaussian derivative wavelet.
BibTeX
@article{wiaux2006fast,
  author = {Yves Wiaux and Laurent Jacques and P. Vielva and Pierre Vandergheynst},
  title = {{Fast Directional Correlation on the Sphere with Steerable Filters}},
  journal = {The Astrophysical Journal},
  year = {2006},
  doi = {10.1086/507692},
}
Figure