Abstract

Recent Geometric Multiscale Algorithms for n-point Correlations

Alexander Gray
Carnegie Mellon University

I will describe recent algorithms we have developed for computing n-point correlation functions, which have been successfully used in several cosmological projects on datasets of unprecedented size. I'll first review the hierarchical/multiscale geometric data structures upon which the methods are based, describe the exact algorithm for the case of general n, and show its algorithmic runtime analysis for the isotropic homogeneous Poisson case. I'll conclude by showing an approach yielding estimates with confidence bounds rather than exact answers, based on a new geometrically-stratified Monte Carlo idea, which leads to even greater efficiencies. Depending on time I'll go
into some other extensions I've made including multiple matchers and projected correlations.

This work is in collaboration with computer scientist Andrew Moore, astrophysicists Bob Nichol, Andy Connolly, Alex Szalay, and Istvan Szapudi, and statisticians Larry Wasserman and Chris Genovese.