CaltechAUTHORS
  A Caltech Library Service

Geometric structure of graph Laplacian embeddings

García Trillos, Nicolás and Hoffmann, Franca and Hosseini, Bamdad (2019) Geometric structure of graph Laplacian embeddings. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20200331-074327697

[img] PDF - Submitted Version
See Usage Policy.

668Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200331-074327697

Abstract

We analyze the spectral clustering procedure for identifying coarse structure in a data set x₁,…,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 M embedded in R^d, and pick a connectivity length-scale ε>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 ε=ε(n) is allowed to decay to zero at a slow enough rate as the number of data points grows. This rate depends on the intrinsic dimension of the manifold on which the data is supported.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1901.10651arXivDiscussion Paper
ORCID:
AuthorORCID
Hoffmann, Franca0000-0002-1182-5521
Additional Information:The authors would like to thank Ulrike von Luxburg for pointing them to the paper [21] which was the starting point of this work. Franca Hoffmann was partially supported by Caltech’s von Karman postdoctoral instructorship. Bamdad Hosseini is supported in part by a postdoctoral fellowship granted by Natural Sciences and Engineering Research Council of Canada.
Funders:
Funding AgencyGrant Number
CaltechUNSPECIFIED
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Record Number:CaltechAUTHORS:20200331-074327697
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200331-074327697
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:102184
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:31 Mar 2020 16:09
Last Modified:31 Mar 2020 16:09

Repository Staff Only: item control page