Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph

Gen Li, Yuantao Gu
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:6337-6345, 2021.

Abstract

Spectral method is a commonly used scheme to cluster data points lying close to Union of Subspaces, a task known as Subspace Clustering. The typical usage is to construct a Random Geometry Graph first and then apply spectral method to the graph to obtain clustering result. The latter step has been coined the name Spectral Clustering. As far as we know, in spite of the significance of both steps in spectral-method-based Subspace Clustering, all existing theoretical results focus on the first step of constructing the graph, but ignore the final step to correct false connections through spectral clustering. This paper establishes a theory to show the power of this method for the first time, in which we demonstrate the mechanism of spectral clustering by analyzing a simplified algorithm under the widely used semi-random model. Based on this theory, we prove the efficiency of Subspace Clustering in fairly broad conditions. The insights and analysis techniques developed in this paper might also have implications for other random graph problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-li21f, title = {Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph}, author = {Li, Gen and Gu, Yuantao}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {6337--6345}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/li21f/li21f.pdf}, url = {https://proceedings.mlr.press/v139/li21f.html}, abstract = {Spectral method is a commonly used scheme to cluster data points lying close to Union of Subspaces, a task known as Subspace Clustering. The typical usage is to construct a Random Geometry Graph first and then apply spectral method to the graph to obtain clustering result. The latter step has been coined the name Spectral Clustering. As far as we know, in spite of the significance of both steps in spectral-method-based Subspace Clustering, all existing theoretical results focus on the first step of constructing the graph, but ignore the final step to correct false connections through spectral clustering. This paper establishes a theory to show the power of this method for the first time, in which we demonstrate the mechanism of spectral clustering by analyzing a simplified algorithm under the widely used semi-random model. Based on this theory, we prove the efficiency of Subspace Clustering in fairly broad conditions. The insights and analysis techniques developed in this paper might also have implications for other random graph problems.} }
Endnote
%0 Conference Paper %T Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph %A Gen Li %A Yuantao Gu %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-li21f %I PMLR %P 6337--6345 %U https://proceedings.mlr.press/v139/li21f.html %V 139 %X Spectral method is a commonly used scheme to cluster data points lying close to Union of Subspaces, a task known as Subspace Clustering. The typical usage is to construct a Random Geometry Graph first and then apply spectral method to the graph to obtain clustering result. The latter step has been coined the name Spectral Clustering. As far as we know, in spite of the significance of both steps in spectral-method-based Subspace Clustering, all existing theoretical results focus on the first step of constructing the graph, but ignore the final step to correct false connections through spectral clustering. This paper establishes a theory to show the power of this method for the first time, in which we demonstrate the mechanism of spectral clustering by analyzing a simplified algorithm under the widely used semi-random model. Based on this theory, we prove the efficiency of Subspace Clustering in fairly broad conditions. The insights and analysis techniques developed in this paper might also have implications for other random graph problems.
APA
Li, G. & Gu, Y.. (2021). Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:6337-6345 Available from https://proceedings.mlr.press/v139/li21f.html.

Related Material