  Spectral clustering is a broad class of clustering procedures in which an
intractable combinatorial optimization formulation of clustering is "relaxed"
into a tractable eigenvector problem, and in which the relaxed solution is
subsequently "rounded" into an approximate discrete solution to the original
problem. In this paper we present a novel margin-based perspective on multiway
spectral clustering. We show that the margin-based perspective illuminates both
the relaxation and rounding aspects of spectral clustering, providing a unified
analysis of existing algorithms and guiding the design of new algorithms. We
also present connections between spectral clustering and several other topics
in statistics, specifically minimum-variance clustering, Procrustes analysis
and Gaussian intrinsic autoregression.
