%0 Generic %1 chu2020weighted %A Chu, Timothy %A Miller, Gary L. %A Walkington, Noel J. %A Wang, Alex L. %D 2020 %K clustering fiedler spectral %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.

@misc{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-04-25T00:10:17.000+0200}, author = {Chu, Timothy and Miller, Gary L. and Walkington, Noel J. and Wang, Alex L.}, biburl = {https://www.bibsonomy.org/bibtex/2abe94155e9de86d037f15a52d409d43d/j.c.m.janssen}, description = {Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities}, interhash = {2d8cf882a1dfa65d99181bca61470219}, intrahash = {abe94155e9de86d037f15a52d409d43d}, keywords = {clustering fiedler spectral}, note = {cite arxiv:2004.09589}, timestamp = {2020-04-25T00:10:17.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 }