  This paper proposes a variant of the normalized cut algorithm for spectral
clustering. Although the normalized cut algorithm applies the K-means algorithm
to the eigenvectors of a normalized graph Laplacian for finding clusters, our
algorithm instead uses a minimum volume enclosing ellipsoid for them. We show
that the algorithm shares similarity with the ellipsoidal rounding algorithm
for separable nonnegative matrix factorization. Our theoretical insight implies
that the algorithm can serve as a bridge between spectral clustering and
separable NMF. The K-means algorithm has the issues in that the choice of
initial points affects the construction of clusters and certain choices result
in poor clustering performance. The normalized cut algorithm inherits these
issues since K-means is incorporated in it, whereas the algorithm proposed here
does not. An empirical study is presented to examine the performance of the
algorithm.
