close

Вход

Забыли?

вход по аккаунту

?

Maximally persistent cycles

код для вставкиСкачать
computational topology
Maximally persistent
cycles
in random geometric complexes
Joint work with
Omer Bobrowski and Primoz Skraba
Motivation
The probabilistic method provides existence proofs.
The probabilistic method provides existence proofs.
1. Ramsey theory
2. Expander graphs
3. Metric geometry
4. Geometric group theory
The probabilistic method provides existence proofs.
1. Ramsey theory
2. Expander graphs
3. Metric geometry
4. Geometric group theory
The probabilistic method provides existence proofs.
1. Ramsey theory
2. Expander graphs
3. Metric geometry
4. Geometric group theory
The probabilistic method provides existence proofs.
1. Ramsey theory
2. Expander graphs
3. Metric geometry
4. Geometric group theory
Randomness models natural phenomena.
Randomness models natural phenomena.
1. Physics—black holes, quantum gravity, material science.
2. Mathematics—what does a typical object look like?
3. Statistics—often the null hypothesis is that the data is random.
Randomness models natural phenomena.
1. Physics—black holes, quantum gravity, material science.
2. Mathematics—what does a typical object look like?
3. Statistics—often the null hypothesis is that the data is random.
Randomness models natural phenomena.
1. Physics—black holes, quantum gravity, material science.
2. Mathematics—what does a typical object look like?
3. Statistics—often the null hypothesis is that the data is random.
Random geometric graphs
Definition.
The random geometric graph G(n, r) has as its
vertices n points chosen i.i.d. in Rd , according to
some probability distribution.
Two vertices are adjacent if they are within distance r.
Usually r = r(n) and n ! 1.
Proposition.
Consider n points chosen i.i.d. uniformly in the unit square [0, 1]2 .
If r ⌧ n
3/4
then with high probability G(n; r) contains no triangles.
If r
3/4
then with high probability G(n; r) contains many triangles.
n
Sketch of proof.
E [# triangles]
✓ ◆
n
=
P [{x, y, z} form a triangle]
3
✓ ◆
n
=
P [x ⇠ y and y ⇠ z and z ⇠ x]
3
✓ ◆
n
=
P [x ⇠ y] P [y ⇠ z] P [z ⇠ x | x ⇠ y and y ⇠ z]
3
⇣ n3 r 4
Proposition. (Gilbert, Penrose, etc.)
Let G1 be the number of vertices in the largest connected
component of G(n; r).
There exists a constant c⇤ with the following property.
If r 
pc
n
and c < c⇤ , then w.h.p. G1 = O(log n)
If r
pc
n
and c > c⇤ , then w.h.p. G1 = ⌦(n)
Random geometric complexes
Random geometric graphs can be extended
to random geometric complexes, via either
ˇ
the Vietoris–Rips or Cech
constructions.
Proposition.
Consider n points chosen i.i.d. uniformly in the unit square [0, 1]2 .
If r ⌧ n
If r
If n
3/4
then w.h.p. H1 (C(n, r)) = 0.
log n/n then w.h.p. H1 (C(n, r)) = 0.
3/4
⌧ r ⌧ log n/n then w.h.p. H1 (C(n, r)) 6= 0.
Proposition.
Consider n points chosen i.i.d. uniformly in the unit square [0, 1]2 .
If r ⌧ n
If r
If n
3/4
then w.h.p. H1 (C(n, r)) = 0.
log n/n then w.h.p. H1 (C(n, r)) = 0.
3/4
⌧ r ⌧ log n/n then w.h.p. H1 (C(n, r)) 6= 0.
References.
M. Kahle. Random geometric complexes. Discrete Comput. Geom., 45 (2011),
no. 3, 553–573.
O. Bobrowski and M. Kahle. Topology of random geometric complexes: a
survey. (to appear in AMS Proceedings of Symposia in Applied Mathematics,
arXiv:1409.4734.)
Persistent homology of a random geometric complex.
−3
1.5
x 10
1
0.5
0
0
0.5
1
1.5
−3
x 10
Definition.
For a cycle
in persistent homology, let
b( ) denote the birth radius of ,
Definition.
For a cycle
in persistent homology, let
b( ) denote the birth radius of ,
d( ) denote the death radius of ,
Definition.
For a cycle
in persistent homology, let
b( ) denote the birth radius of ,
d( ) denote the death radius of ,
and p( ) = d( )/b( ) denote the persistence of .
Advantages of the multiplicative definition.
1. In the random setting, many cycles
d( )
satisfy
b( ) ⇡ d( ).
2. This makes the persistence a scale-free, dimensionless parameter.
ˇ
3. The relationship between Cech
and Rips is a multiplicative one.
That is, for every finite point set P, we have that
C(P, r) ,! R(P, r) ,! C(P, 2r).
Advantages of the multiplicative definition.
1. In the random setting, many cycles
d( )
satisfy
b( ) ⇡ d( ).
2. This makes the persistence a scale-free, dimensionless parameter.
ˇ
3. The relationship between Cech
and Rips is a multiplicative one.
That is, for every finite point set P, we have that
C(P, r) ,! R(P, r) ,! C(P, 2r).
Advantages of the multiplicative definition.
1. In the random setting, many cycles
d( )
satisfy
b( ) ⇡ d( ).
2. This makes the persistence a scale-free, dimensionless parameter.
ˇ
3. The relationship between Cech
and Rips is a multiplicative one.
That is, for every finite point set P, we have that
C(P, r) ,! R(P, r) ,! C(P, 2r).
Main result
Theorem. (Two-dimensional case.)
Consider n points chosen i.i.d. uniformly in the unit square [0, 1]2 .
Then w.h.p. the maximal persistence in degree one homology
is of order
log n
max p( ) ⇣
.
log log n
That is, there exist constants C1 and C2 such that
✓
◆
✓
◆
log n
log n .
C1
 max p( )  C2
log log n
log log n
Maximum H1 in 2D
2.6
death
birth
2.4
3
max
max
death
birth
4
2.2
2
1.8
2
1.6
3
3.5
4
log n
log log n
4.5
5
Sketch of upper bound. (Attempt 1.)
p
Set r = c/ n for some sufficiently small c > 0.
⇤
Sketch of upper bound. (Attempt 1.)
p
Set r = c/ n for some sufficiently small c > 0.
⇤
Call cycles with b( ) < r⇤ early-born cycles,
and cycles with b( ) r⇤ late-born cycles.
Sketch of upper bound. (Attempt 1.)
p
Set r = c/ n for some sufficiently small c > 0.
⇤
⇤
Call cycles with b( ) < r early-born, and
cycles with b( ) r⇤ late-born.
With high probability, all late-born cycles have
p
p( ) = O log
⇣pn , since⌘all cycles have died
before r = O
log n/n .
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
1. Probability to vertices.
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
1. Probability to vertices.
2. Vertices to length.
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
1. Probability to vertices.
2. Vertices to length.
3. Length to filling radius.
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
1. Probability to vertices.
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
1. Probability to vertices.
2. Vertices to length.
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
1. Probability to vertices.
2. Vertices to length.
3. Length to filling radius.
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
1. Probability to vertices.
2. Vertices to length.
3. Length to filling radius.
4. Filling radius to persistence.
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
1. Probability to vertices.
2. Vertices to length.
3. Length to filling radius.
4. Filling radius to persistence.
This allows us to show that early-born cycles
p( )  O(log n).
have
Sketch of upper bound. (Attempt 1.)
So our main concern is early-born cycles.
1. Probability to vertices.
2. Vertices to length.
3. Length to filling radius.
4. Filling radius to persistence.
This allows us to show that early-born cycles
p( )  O(log n).
So then all cycles p( ) have p( )  O(log n).
have
Sketch of upper bound. (Attempt 1.)
p
Set r = c/ n for some sufficiently small c > 0.
⇤
Sketch of upper bound. (Attempt 2.)
⇤
Set r = (log n)
↵
p
/ n for some small ↵ > 0.
Sketch of upper bound. (Attempt 2.)
⇤
Set r = (log n)
↵
p
/ n for some small ↵ > 0.
⇤
Call cycles with b( ) < r early-born, and
cycles with b( ) r⇤ late-born.
...
We conclude that
p( ) = O
✓
log n
log log n
for all cycles , with high probability.
◆
,
Theorem. (General case.)
Consider n points chosen i.i.d. uniformly in the unit cube [0, 1]d .
Then the maximally persistent cycle in degree i homology
is of order
max p( ) ⇣
✓
log n
log log n
◆1/i
.
(The implied constants depend on i, d, and on whether
ˇ
we are considering the random Cech
or Rips filtration.)
(a)
1.8
1.4
1.6
1.3
max death
birth
max
death
birth
Maximum H2 in 3D
1.4
1.1
1.2
1
1.2
1
1.7
1.8
1.9
q
(c)
2
2.1
log n
log log n
2.2
2.3
(b)
Maximum H2 in 4D
D
max death
birth
1.4
1.3
1.2
1.1
1
2.2
2.3
1.7
1.8
q
log n
log log n
(d)
1.9
2
Sketch of upper bound.
1. Probability to vertices.
2. Vertices to volume.
3. Volume to filling radius (isoperimetry).
4. Filling radius to persistence.
Main tool: isoperimetric inequality.
Theorem. (Federer–Fleming, 1960.)
If is a k-cycle in Rd of k-dimensional volume V ,
then the filling radius R satisfies
R = O V 1/k .
Main tool: isoperimetric inequality.
Theorem. (Federer–Fleming, 1960.)
If is a k-cycle in Rd of k-dimensional volume V ,
then the filling radius R satisfies
R = O V 1/k .
References.
H. Federer and W.H. Fleming. Normal and integral currents. Annals of Math.
Vol. 72, No. 3 (1960), pp. 458-520.
L. Guth. Notes on Gromov’s systolic estimate. Geom. Dedicata. Vol. 123
(2006), pp. 113-129.
Future directions
1. Law of large numbers. Is it true that
max p( )
lim
exists?
1/i
n!1 (log n/ log log n)
1. Law of large numbers. Is it true that
max p( )
lim
exists?
1/i
n!1 (log n/ log log n)
2. Other distributions. What about a standard
multivariate normal distribution?
1. Law of large numbers. Is it true that
max p( )
lim
exists?
1/i
n!1 (log n/ log log n)
2. Other distributions. What about a standard
multivariate normal distribution?
3. Homology in the critical regime. Find a formula
for E[ i ] when r = cn
1/i
.
Thanks for your time and attention!
Acknowledgements
DARPA Young Faculty Award
Alfred P. Sloan Research Fellowship
NSF-CAREER Award
Автор
iknyazeva
Документ
Категория
Математика
Просмотров
23
Размер файла
6 740 Кб
Теги
computational topology
1/--страниц
Пожаловаться на содержимое документа