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.
Description
[2004.09589] Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities
%0 Journal Article
%1 chu2020weighted
%A Chu, Timothy
%A Miller, Gary L.
%A Walkington, Noel J.
%A Wang, Alex L.
%D 2020
%K clustering density inequality probability
%T Weighted Cheeger and Buser Inequalities, with Applications to Clustering
and Cutting Probability Densities
%U http://arxiv.org/abs/2004.09589
%X 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.
@article{chu2020weighted,
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.},
added-at = {2020-05-03T10:59:08.000+0200},
author = {Chu, Timothy and Miller, Gary L. and Walkington, Noel J. and Wang, Alex L.},
biburl = {https://www.bibsonomy.org/bibtex/2701f34fa26599332b4a759057c5c8f44/kirk86},
description = {[2004.09589] Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities},
interhash = {2d8cf882a1dfa65d99181bca61470219},
intrahash = {701f34fa26599332b4a759057c5c8f44},
keywords = {clustering density inequality probability},
note = {cite arxiv:2004.09589},
timestamp = {2020-05-03T10:59:08.000+0200},
title = {Weighted Cheeger and Buser Inequalities, with Applications to Clustering
and Cutting Probability Densities},
url = {http://arxiv.org/abs/2004.09589},
year = 2020
}