Abstract
We examine the connection between the second eigenvalue of a weighted
Laplacian and the isoperimetric constant of a Lipschitz function whose domain
is Euclidean space. We prove both Cheeger and Buser-type inequalities for
appropriate definitions of the "weighted Laplacian" and "isoperimetric
constant."
We show that given a positive-valued Lipschitz function $\rho$ whose domain
is Euclidean space, we can define a weighted Laplacian based on $\rho$ and a
weighted isoperimetric constant such that bounds similar to the bounds for the
normalized graph Laplacian of Alon-Milman are true. Further we show that no
such bounds hold for most prior definitions of weighted Laplacian and weighted
isoperimetric constant. We then apply this result to generate novel algorithms
for cutting probability densities and clustering data.
Users
Please
log in to take part in the discussion (add own reviews or comments).