We present a new framework for large-scale data clustering. The main
idea is to modify functional dimensionality reduction techniques
to directly optimize over discrete labels using stochastic gradient
descent. Compared to methods like spectral clustering our approach
solves a single optimization problem, rather than an ad-hoc two-stage
optimization approach, does not require a matrix inversion, can easily
encode prior knowledge in the set of implementable functions, and
does not have an ?out-of-sample? problem. Experimental results on
both artificial and real-world datasets show the usefulness of our
approach.