25
$\begingroup$

If you generate points in $\mathbb R^n$ via a process that respects a Gaussian normal distribution, then compute the persistent homology / barcodes, to my eye something fairly regular seems to be happening, with the barcodes tending towards something like a "wing" shape, fat in lower dimensions, thinning out towards dimension $n$.

Has anyone proven any theorems that describe the asymptotic "shape" of the barcodes?

Ideally I'd like a test so that I can look at some barcodes and say "that's typical of a Gaussian normal distribution".

The closest thing I've been able to find is experiments and results on the expected Euler characteristic of the persistent homology, in the following two references (arXiv links): Persistent homology for random fields and complexes, Euler integration of Gaussian random fields and persistent homology.

Edit:

I did a very rough computation to try and get some kind of guess as to what the distribution of barcodes should look like. So I made a very coarse estimate based on a distribution of points that is roughly `locally cubical' and approximately respecting a normal distribution.

The density is given by:

$$\mu = N e^{-r^2}$$

where $r$ is the distance from the origin. Then if $\epsilon$ is the parameter for persistent homology, it appears that $H_0$ is rank approximately

$$N \int_{\sqrt{\ln(N\epsilon^{1/n})}}^\infty r^{n-1}e^{-r^2} dr$$

and $H_k$ for $k \in \{1,2,\cdots,n-1\}$ has rank approximately

$$ {n \choose k+1}\frac{(\sqrt{\ln(N\epsilon^{1/n}/\sqrt{k}))}^{n-2}}{4\sqrt{k}\epsilon^{1/n}} $$

These are fairly coarse estimates, and in no way rigorous. But if something like this is actually true it seems to be saying that for $N$ large and $n \geq 3$, the $H_0$ betti number tends to some asymptote (dependent on $\epsilon$), and $H_1, \cdots, H_{n-1}$ are non-trivial but small. So most of the points in the distribution are in a giant homology `black hole' at the centre and persitent homology sees the thin crust around the outside.

I'd be curious if people have done other similar guestimates (or better) and if they had similar-looking results.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ I suspect Adler's work is the state of the art on marrying random fields or their ilk with persistent homology...You should bear in mind that a high-dimensional Gaussian contains almost all its mass in a thin spherical shell far from the origin. The concomitant sparsity of the samples away from the shell will manifest in the Vietoris-Rips complex. Does your wing look like what you'd get with points on a big sphere? $\endgroup$
    – Steve Huntsman
    Commented Dec 4, 2012 at 22:39
  • 2
    $\begingroup$ Presumably the cycles in the homology will predominantly sit in thin spherical layers, fairly far out on the bell-curve, so to speak. The $H_0$ classes will be on the most distant spherical shell, the $H_1$ classes next closest, then the $H_n$ classes will be in the central most spherical shell before all the homology vanishes in the core of the distribution. The main issue is the relative thickness of the shells I would imagine. $\endgroup$
    – Ryan Budney
    Commented Dec 4, 2012 at 23:06
  • 1
    $\begingroup$ I'm surprised no one has asked this yet, but: how many sample points? If you have only one sample point, the barcode is not goint to be terribly hard to describe. Perhaps by asymptotic behavior you mean "let the sample size go to infinity" at which point generically nothing survives for too long. In short, I don't see a sample size invariant answer to your question that is also interesting. What do you have in mind? $\endgroup$
    – Vidit Nanda
    Commented Dec 7, 2012 at 0:26
  • 1
    $\begingroup$ Vel, I'm not asking for a precise prediction of homology classes, but just a general prediction of the shape of the barcodes. Interpret that broadly -- it can be a request for the expected proportion of various Betti numbers, for example. Also, it doesn't have to be an asymptotic prediction -- the prediction could depend on the sample size and it's fine to say "with a sampling of N points one would expect barcodes in this range, X times out of Y", etc. $\endgroup$
    – Ryan Budney
    Commented Dec 7, 2012 at 1:27
  • 3
    $\begingroup$ If you think of a Gaussian distribution of points in $\mathbb R^n$ as something of a probabilistic version of an $n$-dimensional $0$-handle, you could think of this question as something like "persistent homology is the first instance of a probabilistic homology theory, so what are its coefficients?" $\endgroup$
    – Ryan Budney
    Commented Dec 7, 2012 at 1:29

3 Answers 3

Reset to default
10
$\begingroup$

Adler, Bobrowski and Weinberber's "Crackle: The Persistent Homology of Noise" is an answer to my question. I have not read it closely yet but it appears to confirm the guess in the question, and provide answers for other distributions as well.

Although this paper does not target my question directly it gives a more quantitative answer to a nearby question, that of the length of the largest barcode for certain types of random point clouds. Maximally persistent cycles in random geometric complexes.

Improve this answer
$\endgroup$
8
$\begingroup$

The closest I can find spontaneously would be Matthew Kahle's work on random topology; http://arxiv.org/abs/0910.1649 looks like it would be directly related to your question, and http://arxiv.org/abs/1009.4130 seems related too.

Improve this answer
$\endgroup$
5
$\begingroup$

For what it's worth, Laura Balzano and I ran some experiments on this precise question for Gaussian clouds in R^2, trying to understand what kind of barcodes are rare under this "null hypothesis" of data without topological structure. We focused on the question "how long a bar in R^1 constitutes a surprisingly long bar?" and ran some tests on this. No theorems, though. I agree with your implicit assertion that this is an important question for the theory!

http://www.math.wisc.edu/~ellenber/topoData_icassp-3.pdf

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .