Fetching the paper…

Reading the bibliography…

2019

Geometric structure of graph Laplacian embeddings

Trillos, Nicolas Garcia, Hoffmann, Franca, Hosseini, Bamdad

Original
PDF
Post on X

Understand

We analyze the spectral clustering procedure for identifying coarse structure in a data set $x_1, \dots, x_n$, and in particular study the geometry of graph Laplacian embeddings which form the basis for spectral clustering algorithms.

More precisely, we assume that the data is sampled from a mixture model supported on a manifold $\mathcal{M}$ embedded in $\mathbb{R}^d$, and pick a connectivity length-scale $\varepsilon>0$ to construct a kernelized graph Laplacian.
We introduce a notion of a well-separated mixture model which only depends on the model itself, and prove that when the model is well separated, with high probability the embedded data set concentrates on cones that are centered around orthogonal vectors.
Our results are meaningful in the regime where $\varepsilon = \varepsilon(n)$ is allowed to decay to zero at a slow enough rate as the number of data points grows.

Geometric structure of graph Laplacian embeddings · Around

Built on

K. Rohe, S. Chatterjee, and B. Yu
1915
Earlier work this paper cites.
J. Cheeger
1969
Earlier work this paper cites.
N. J. Higham
1989
Earlier work this paper cites.
F. R. K. Chung
1997
Earlier work this paper cites.
J. Shi and J. Malik
2000
Earlier work this paper cites.
C. Villani
2003
Earlier work this paper cites.
M. Hein, J.-Y. Audibert, and U. von Luxburg
2005
Earlier work this paper cites.
R. R. Coifman and S. Lafon
2006
Earlier work this paper cites.
V. I. Bogachev
2007
Earlier work this paper cites.

Similar

U. von Luxburg
2007
Cited alongside, same era.
M. Belkin and P. Niyogi
2008
Cited alongside, same era.
U. von Luxburg, M. Belkin, and O. Bousquet
2008
Cited alongside, same era.
H. Attouch, G. Buttazzo, and G. Michaille
2014
Cited alongside, same era.
D. Burago, S. Ivanov, and Y. Kurylev
2014
Cited alongside, same era.
N. García Trillos and D. Slepčev
2015
Cited alongside, same era.
G. Schiebinger, M. J. Wainwright, and B. Yu
2015
Cited alongside, same era.

Then

M. M. Dunlop, D. Slepčev, A. M. Stuart, and M. Thorpe
Original
2018
Later among the works it cites.
N. Garcia Trillos, M. Gerlach, M. Hein, and D. Slepcev
Original
2018
Later among the works it cites.
N. García Trillos and D. Sanz-Alonso
2018
Later among the works it cites.
N. García Trillos and D. Slepčev
2018
Later among the works it cites.
S. Ling and T. Strohmer
Original
2018
Later among the works it cites.
D. Slepčev and M. Thorpe
2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

N. García Trillos and R. Murray

2017

Cited alongside, same era.

A. Little, M. Maggioni, and J. M. Murphy

2017

Cited alongside, same era.

F. Hoffmann, B. Hosseini, A. Oberai, and A. M. Stuart

2019

Closest in time.

To appear in SIMODS, 2019

N. G. Trillos · 2019

Closest in time.