  This work studies the classical spectral clustering algorithm which embeds
the vertices of some graph $G=(V_G, E_G)$ into $\mathbb{R}^k$ using $k$
eigenvectors of some matrix of $G$, and applies $k$-means to partition $V_G$
into $k$ clusters. Our first result is a tighter analysis on the performance of
spectral clustering, and explains why it works under some much weaker condition
than the ones studied in the literature. For the second result, we show that,
by applying fewer than $k$ eigenvectors to construct the embedding, spectral
clustering is able to produce better output for many practical instances; this
result is the first of its kind in spectral clustering. Besides its conceptual
and theoretical significance, the practical impact of our work is demonstrated
by the empirical analysis on both synthetic and real-world datasets, in which
spectral clustering produces comparable or better results with fewer than $k$
eigenvectors.
