As a part of introducing nonparametric statistics, I wanted to write about applications of computation geometry from the nonparametric 2/3 dimensional density estimation perspective. Also, the following article came along when I just began to collect statistical applications in astronomy (my [ArXiv] series). This [arXiv] paper, in fact, initiated me to investigate Voronoi Tessellations in astronomy in general.

[arxiv/astro-ph:0707.2877]
Voronoi Tessellations and the Cosmic Web: Spatial Patterns and Clustering across the Universe
by Rien van de Weygaert

Since then, quite time has passed. In the mean time, I found more publications in astronomy specifically using tessellation as a main tool of nonparametric density estimation and for data analysis. Nonetheless, in general, topics in spatial statistics tend to be unrecognized or almost ignored in analyzing astronomical spatial data (I mean data points with coordinate information). Many seem only utilizing statistics partially or not at all. Some might want to know how often Voronoi tessellation is applied in astronomy. Here, I listed results from my ADS search by limiting tessellation in title key words. :

• [arxiv/astro-ph:0110259]
  Detecting Clusters of Galaxies in the Sloan Digital Sky Survey I : Monte Carlo Comparison of Cluster Detection Algorithms
  by Kim, R.S.J. et al. (2002) AJ, 123, pp.20-36.
• [arxiv/astro-ph:0906.1905]
  The VOISE Algorithm: a Versatile Toll for Automatic Segmentation of Astronomical Images
  by Guio, P. and Achilleos, N. (2009)
• Using Voronoi Techniques to determine the shapes of photon sources
  by Wilkinson and Meurs Irish Astronomical Journal, 1998, 25(1), 37
• High-order 3D Voronoi tessellation for identifying isolated galaxies, pairs and triplets
  by Elyiv, A.; Melnyk, O.; Vavilova, I. 2009..MNRAS..394..1409E
• 3-D Voronoi’s Tessellation as a Tool for Identifying Galaxy Groups
  by Melnyk, Olga V.; Elyiv, Andrii A.; Vavilova, Iryna B. 2007..IAUS..235..223M
• Adaptive binning of X-ray data with weighted Voronoi tessellations
  by Diehl, Steven; Statler, Thomas S. 2006..MNRAS..368..497D
• Adaptive spatial binning of integral-field spectroscopic data using Voronoi tessellations
  by Cappellari, M. and Copin, Y. 2003..MNRAS..342..345C
• Adaptive Spatial Binning of 2D Spectra and Images Using Voronoi Tessellations
  by Cappellari, M.; Copin, Y. 2002..ASPC..282..515CA
• Finding galaxy clusters using Voronoi tessellations
  by Ramella, M.; Boschin, W.; Fadda, D.; Nonino, M. 2001..A&A…368..776R
• The Forest Method as a New Parallel Tree Method with the Sectional Voronoi Tessellation
  by Yahagi, Hideki; Mori, Masao; Yoshii, Yuzuru 1999..ApJS..124..1
• Cluster Identification via Voronoi Tesselation ..1999..ASPC..176..108
• The accuracy of parameters determined with the core-sampling method: Application to Voronoi tessellations 1997..A&AS..123..495
• Dynamical Voronoi tessellation. V. Thickness and incompleteness.
  by Zaninetti, L 1995..A&AS..109..71
• Fragmenting the Universe. 3: The constructions and statistics of 3-D Voronoi tessellations
  by van de Weygaert, Rien 1994..A&A..283..361
• Dynamical Voronoi tessellation. IV. The distribution of the asteroids
  by Zaninetti, L 1993..A&A..276..255
• Quasi-periodic structures in the large-scale galaxy distribution and three-dimensional Voronoi tessellation
  1991..MNRAS..250..519
• Dynamical Voronoi tessellation. III – The distribution of galaxies
  by Zaninetti, L 1991..A&A..246..291
• Dynamical Voronoi tessellation. II – The three-dimensional case
  by Zaninetti, L 1990..A&A..233..293
• Dynamical Voronoi tessellation. I – The two-dimensional case
  by Zaninetti, L 1989..A&A..224..345

Then, the topic has been forgotten for a while until this recent [arXiv] paper, which reminded me my old intention for introducing tessellation for density estimation and for understanding large scale structures or clusters (astronomers’ jargon, not the term in machine or statistical learning).

[arxiv:stat.ME:0910.1473] Moment Analysis of the Delaunay Tessellation Field Estimator
by M.N.M van Lieshout

Looking into plots of the papers by van de Weygaert or van Lieshout, without mathematical jargon and abstraction, one can immediately understand what Voronoi and Delaunay Tessellation is (Delaunay Tessellation is also called as Delaunay Triangulation (wiki). Perhaps, you want to check out wiki:Delaunay Tessellation Field Estimator as well). Voronoi tessellations have been adopted in many scientific/engineering fields to describe the spatial distribution. Astronomy is not an exception. Voronoi Tessellation has been used for field interpolation.

van de Weygaert described Voronoi tessellations as follows:

1. the asymptotic frame for the ultimate matter distribution,
2. the skeleton of the cosmic matter distribution,
3. a versatile and flexible mathematical model for weblike spatial pattern, and
4. a natural asymptotic result of an evolution in which low-density expanding void regions dictate the spatial organization of the Megaparsec universe, while matter assembles in high-density filamentary and wall-like interstices between the voids.

van Lieshout derived explicit expressions for the mean and variance of Delaunay Tessellatoin Field Estimator (DTFE) and showed that for stationary Poisson processes, the DTFE is asymptotically unbiased with a variance that is proportional to the square intensity.

We’ve observed voids and filaments of cosmic matters with patterns of which theory hasn’t been discovered. In general, those patterns are manifested via observed galaxies, both directly and indirectly. Individual observed objects, I believe, can be matched to points that construct Voronoi polygons. They represent each polygon and investigating its distributional properly helps to understand the formation rules and theories of those patterns. For that matter, probably, various topics in stochastic geometry, not just Voronoi tessellation, can be adopted.

There are plethora information available on Voronoi Tessellation such as the website of International Symposium on Voronoi Diagrams in Science and Engineering. Two recent meeting websites are ISVD09 and ISVD08. Also, the following review paper is interesting.

Centroidal Voronoi Tessellations: Applications and Algorithms (1999) Du, Faber, and Gunzburger in SIAM Review, vol. 41(4), pp. 637-676

By the way, you may have noticed my preference for Voronoi Tessellation over Delaunay owing to the characteristics of this centroidal Voronoi that each observation is the center of each Voronoi cell as opposed to the property of Delaunay triangulation that multiple simplices are associated one observation/point. However, from the perspective of understanding the distribution of observations as a whole, both approaches offer summaries and insights in a nonparametric fashion, which I put the most value on.

When I learned “Kalman filter” for the first time, I was not sure how to distinguish it from “Yule-Walker equation” (time series), “Pade approximant, (unfortunately, the wiki page does not have its matrix form). Wiener Filter” (signal processing), etc. Here are those publications, specifically mentioned the name Kalman filter in their abstracts found from ADS.

• Application of Data Assimilation Method for Predicting Solar Cycles (2008) in ApJ
• Time series analysis in astronomy: Limits and potentialities (2005) in A&A
  From the abstract: Only techniques of data aalysis developed in a specific physical context can be expected to provide useful results. The filed of stochastic dynamics appears to be an interesting framework for such an approach.
• Determination of the Mass of Jupiter Using the Motion of Its Ninth Satellite and a Kaiman-Bucy Filter (1972) in A&A

The motivation of introducing Kalman filter although it is a very well known term is the recent Fisher Lecture given by Noel Cressie at the JSM 2009. He is the leading expert in spatial statistics. He is the author of a very famous book in Spatial Statistics. During his presentation, he described challenges from satellite data and how Kalman filter accelerated computing a gigantic covariance matrix in kriging. Satellite data of meteorology and geosciences may not exactly match with astronomical satellite data but from statistical modeling perspective, the challenges are similar. Namely, massive data, streaming data, multi dimensional, temporal, missing observations in certain areas, different exposure time, estimation and prediction, interpolation and extrapoloation, large image size, and so on. It’s not just focusing denoising/cleaning images. Statisticians want to find the driving force of certain features by modeling and to perform statistical inference. (They do not mind parametrization of interesting metric/measure/quantity for modeling or they approach the problem in a nonparametric fashion). I understood the use of Kalman filter for a fast solution to inverse problems for inference.

There are three distinctive subjects in spatial statistics: geostatistics, lattice data analysis, and spatial point pattern analysis. Because of the resemblance between the spatial distribution of observations in coordinates and the notion of spatially random points, spatial statistics in astronomy has leaned more toward the spatial point pattern analysis than the other subjects. In other fields from immunology to forestry to geology whose data are associated spatial coordinates of underlying geometric structures or whose data were sampled from lattices, observations depend on these spatial structures and scientists enjoy various applications from geostatistics and lattice data analysis. Particularly, kriging is the fundamental notion in geostatistics whose application is found many fields.

Hitherto, I expected that the term kriging can be found rather frequently in analyzing cosmic micro-wave background (CMB) data or large extended sources, wide enough to assign some statistical models for understanding the expected geometric structure and its uncertainty (or interpolating observations via BLUP, best linear unbiased prediction). Against my anticipation, only one referred paper from ADS emerged:

Topography of the Galactic disk – Z-structure and large-scale star formation
by Alfaro, E. J., Cabrera-Cano, J., and Delgado (1991)
in ApJ, 378, pp. 106-118

I attribute this shortage of applying kriging in astronomy to missing data and differential exposure time across the sky. Both require underlying modeling to fill the gap or to convolve with observed data to compensate this unequal sky coverage. Traditionally the kriging analysis is only applied to localized geological areas where missing and unequal coverage is no concern. As many survey and probing missions describe the wide sky coverage, we always see some gaps and selection biases in telescope pointing directions. So, once this characteristics of missing is understood and incorporated into models of spatial statistics, I believe statistical methods for spatial data could reveal more information of our Galaxy and universe.

A good news for astronomers is that nowadays more statisticians and geo-scientists working on spatial data, particularly from satellites. These data are not much different compared to traditional astronomical data except the direction to which a satellite aims (inward or outward). Therefore, data of these scientists has typical properties of astronomical data: missing, unequal sky coverage or exposure and sparse but gigantic images. Due to the increment of computational power and the developments in hierarchical modeling, techniques in geostatistics are being developed to handle these massive, but sparse images for statistical inference. Not only denoising images but they also aim to produce a measure of uncertainty associated with complex spatial data.

For those who are interested in what spatial statistics does, there are a few books I’d like to recommend.

• Cressie, N (1993) Statistics for spatial data
  (the bible of statistical statistics)
• Stein, M.L. (2002) Interpolation of Spatial Data: Some Theory for Kriging
  (it’s about Kriging and written by one of scholarly pinnacles in spatial statistics)
• Banerjee, Carlin, and Gelfand (2004) Hierarchical Modeling and Analysis for Spatial Data
  (Bayesian hierarchical modeling is explained. Very pragmatic but could give an impression that it’s somewhat limited for applications in astronomy)
• Illian et al (2008) Statistical Analysis and Modelling of Spatial Point Patterns
  (Well, I still think spatial point pattern analysis is more dominant in astronomy than geostatistics. So… I feel obliged to throw a book for that. If so, I must mention Peter Diggle’s books too.)
• Diggle (2004) Statistical Analysis of Spatial Point Patterns
  Diggle and Ribeiro (2007) Model-based Geostatistics
  

• The statistician’s and astronomer’s understanding of clustering is different:
  • classification vs. clustering or supervised learning vs. unsupervised learning: the former terms from the pairs indicate the fact that the scientist already knows types of objects in his hands. A photometry data set with an additional column saying star, galaxy, quasar, and unknown is a target for classification or supervised learning. Simply put, classification is finding a rule with photometric colors that could classify these different type objects. If there’s no additional column but the scatter plots or plots after dimension reduction manifesting grouping patterns, it is clustering or unsupervised learning whose goal is finding hyperplanes to separates these clusters optimally; in other words, answering these questions, are there real clusters? If so, how many? is the objective of clustering/unsupervised learning. Overall, rudimentarily, the presence of an extra column of types differentiates between classification and clustering.
  • physical clustering vs. statistical clustering:
    Cosmologists and alike are interested in clusters/clumps of matters/particles/objects. For astrophysicists, clusters are associated with spatial evolution of the universe. Inquiries related to clustering from astronomers are more likely related to finding these spatial clumps statistically, which is a subject of stochastic geometry or spatial statistics. On the other hand, statisticians and data analysts like to investigate clusters in a reparameterized multi-dimensional space. Distances computed do not follow the fundamental laws of physics (gravitation, EM, weak, and strong) but reflect relationships in the multi-dimensional space; for example, in a CM diagram, stars of a kind are grouped. The consensus between two communities about clustering is that the number of clusters is unknown, where the plethora of classification methods cannot be applied and that the study objectives are seeking methodologies for quantifying clusters .
• astronomer’s clustering problems are either statistical classification (closed to semi-supervised learning) or spatial statistics.
  The way of manifesting noisy clusters in the universe or quantifying the current status of matter distribution leads to the very fundamentals of the birth of the universe, where spatial statistics can be a great partner. In the era of photometric redshifts, various classification techniques enhances the accuracy of prediction.
• astronomer’s testing the reality of clusters seems limited: Cosmology problems have been tackled as inverse problem. Based on theoretical cosmology models, simulations are performed and the results are transformed into some surrogate parameters. These surrogates are generally represented by some smooth curves or straight lines in a plot where observations made their debut as points with bidirectional error bars (so called measurement errors). The judgment about the cosmological model under the test happens by a simple regression (correlation) or eyes on these observed data points. If observations and a curve from a cosmological model presented in a 2D plot match well, the given cosmological model is confirmed in the conclusion section. Personally, this procedure of testing cosmological models to account for clusters of the universe can be developed in a more statistically rigorous fashion instead of matching straight lines.
• Challenges to statisticians in astronomy, measurement errors: In (statistical) learning, I believe, there has been no standard procedure to account for astronomers’ measurement errors into modeling. I think measurements errors are, in general, ignored because systematics errors are not recognized in statistics. On the other hand, in astronomy, measurement errors accompanying data, are a very crucial piece of information, particularly for verifying the significance of the observations. Often this measurement errors became denominator in the χ² function which is treated as a χ² distribution to get best fits and confidence intervals.

Personal lessons from two short discussions at the AAS were more collaboration between statisticians and astronomers to include measurement errors in classification or semi-supervised learning particularly for nowadays when we are enjoying plethora of data sets and moving forward with a better aid from statisticians for testing/verifying the existence of clusters beyond fitting a straight line.

[astro-ph:0804.3044] J.M. Loh
Estimating Third-Order Moments for an Absorber Catalog

Instead of getting to the detailed contents, which is left to the readers, I’d rather cite a few key points without math symbols.The script K is denoted as the 3rd order K-function from which the three-point and reduced three-point correlation functions are derived. The benefits of using the script K function over these correlation functions are given regarding bin size and edge correction. Yet, the author did not encourage to use the script K function only but to use all tools. Also, the feasibility of computing third or higher order measures of clustering is mentioned due to larger datasets and advances in computing. In appendix, the unbiasedness of the estimator regarding the script K is proved.

The reason for bringing in this K-function comes from my early experience in learning statistics. My memory of learning the 2 point correlation function from an undergraduate cosmology class is very vague but the basic idea of modeling this function gave me an epiphany during a spatial statistics class several years ago when the Ripley’s K-function was introduced. I vividly remember that I set up my own project to use this K-function to get the characteristics of the spatial distribution of GRBs. The particular reason for selecting GRBs instead of galaxies was 1. I was able to find the data set from the internet on my own (BATSE catalog: astronomers may think accessing data archives is easy but generally statistics students were not exposed to the fact that astronomical data sets are available via internet and in terms of data sets, they depend heavily on data providers, or clients), and 2. I recalled a paper by Professors Efron and Petrosian (1995, ApJ, 449:215-223 Testing Isotropy versus Clustering of Gamma-ray Bursts, who utilized the nearest neighborhood approach. After a few weeks, I made another discovery that people found GRB redshifts and began to understand the cosmological origin of GRBs more deeply. In other words, 2D spatial statistics was not the way to find the origins of GRBs. Due to a few shortcomings, one of them was the latitude dependent observation of BATSE (as a second year graduate student, I didn’t confront the idea of censoring and truncation, yet), I discontinued my personal project with a discouragement that I cannot make any contribution (data themselves, like discovering the distances, speak more louder than statistical inferences without distances).

I was delighted to see the work by Prof. Loh about the Ripley’s K function. Those curious about the K function may check the book written by Martinez and Saar, Statistics of the Galaxy Distribution (Amazon Link). Many statistical publications are also available under spatial statistics and point process that includes the Ripley’s K function.