Fetching the paper…

Reading the bibliography…

2016

Robust and efficient multi-way spectral clustering

Damle, Anil, Minden, Victor, Ying, Lexing

Original
PDF
Post on X

Understand

We present a new algorithm for spectral clustering based on a column-pivoted QR factorization that may be directly used for cluster assignment or to provide an initial guess for k-means.

Our algorithm is simple to implement, direct, and requires no initial guess.
Furthermore, it scales linearly in the number of nodes of the graph and a randomized variant provides significant computational gains.
Provided the subspace spanned by the eigenvectors used for clustering contains a basis that resembles the set of indicator vectors on the clusters, we prove that both our deterministic and randomized algorithms recover a basis close to the indicators in Frobenius norm.

Robust and efficient multi-way spectral clustering · Around

Built on

Rohe, K., Chatterjee, S. &
1915
Earlier work this paper cites.
Fan, K. &
1955
Earlier work this paper cites.
Businger, P. &
1965
Earlier work this paper cites.
Davis, C. &
1970
Earlier work this paper cites.
Donath, W. E. &
1973
Earlier work this paper cites.
Fiedler, M
1973
Earlier work this paper cites.
Holland, P. W., Laskey, K. B. &
1983
Earlier work this paper cites.
Higham, N. J
1986
Earlier work this paper cites.
Chandrasekaran, S. &
1994
Earlier work this paper cites.
Golub, G. H. &
1996
Earlier work this paper cites.
Gu, M. &
1996
Earlier work this paper cites.
Quintana-Ortí, G., Sun, X. &
1998
Earlier work this paper cites.
Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A. &
1999
Earlier work this paper cites.

Similar

Ng, A. Y., Jordan, M. I. &
2001
Cited alongside, same era.
Zha, H., He, X., Ding, C., Gu, M. &
2001
Cited alongside, same era.
Frieze, A., Kannan, R. &
2004
Cited alongside, same era.
Lloyd, S
2006
Cited alongside, same era.
Arthur, D. &
2007
Cited alongside, same era.
von Luxburg, U
2007
Cited alongside, same era.
Mahoney, M. W. &
2009
Cited alongside, same era.
Motwani, R. &
2010
Cited alongside, same era.

Then

Massoulié, L
2014
Later among the works it cites.
Abbe, E. &
2015
Later among the works it cites.
Agarwal, N., Bandeira, A. S., Koiliaris, K. &
Original
2015
Later among the works it cites.
Damle, A., Lin, L. &
2015
Later among the works it cites.
Gao, C., Ma, Z., Zhang, A. Y. &
Original
2015
Later among the works it cites.
Hajek, B., Wu, Y. &
Original
2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Benzi, M., Boito, P. &

2013

Cited alongside, same era.

Celebi, M. E., Kingravi, H. A. &

2013

Cited alongside, same era.

Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L. &

2013

Cited alongside, same era.

Gharan, S. O. &

2014

Cited alongside, same era.

Schiebinger, G., Wainwright, M. J., Yu, B. et al

2015

Later among the works it cites.

Tropp, J. A

2015

Later among the works it cites.

Abbe, E., Bandeira, A. S. &

2016

Closest in time.

Bandeira, A. S. &

2016

Closest in time.

Damle, A., Lin, L. &

2016

Closest in time.

Montanari, A. &

2016

Closest in time.