Doubly Stochastic Normalization for Spectral Clustering
Abstract
In this paper we focus on the issue of normalization of the affinity matrix in spectral clustering. We show that the difference between N-cuts and Ratio-cuts is in the error measure being used (relative-entropy versus L1 norm) in finding the closest doubly-stochastic matrix to the input affinity matrix. We then develop a scheme for finding the optimal, under Frobenius norm, doubly-stochastic approximation using Von-Neumann's successive projections lemma. The new normalization scheme is simple and efficient and provides superior clustering performance over many of the standardized tests.
Cite
Text
Zass and Shashua. "Doubly Stochastic Normalization for Spectral Clustering." Neural Information Processing Systems, 2006.Markdown
[Zass and Shashua. "Doubly Stochastic Normalization for Spectral Clustering." Neural Information Processing Systems, 2006.](https://mlanthology.org/neurips/2006/zass2006neurips-doubly/)BibTeX
@inproceedings{zass2006neurips-doubly,
title = {{Doubly Stochastic Normalization for Spectral Clustering}},
author = {Zass, Ron and Shashua, Amnon},
booktitle = {Neural Information Processing Systems},
year = {2006},
pages = {1569-1576},
url = {https://mlanthology.org/neurips/2006/zass2006neurips-doubly/}
}