 |
    |
Spectral Clustering with a Convex Regularizer on Millions of Images
Maxwell D. Collins1, Ji Liu2, Jia Xu1, Lopamudra Mukherjee3, and Vikas Singh1
1University of Wisconsin, Madison, USA
mcollins@cs.wisc.edu
jiaxu@cs.wisc.edu
vsingh@biostat.wisc.edu
2University of Rochester, USA
jliu@cs.rochester.edu
3University of Wisconsin, Whitewater, USA
mukherjl@uww.edu
Abstract. This paper focuses on efficient algorithms for single and multi-view spectral clustering with a convex regularization term for very large scale image datasets. In computer vision applications, multiple views denote distinct image-derived feature representations that inform the clustering. Separately, the regularization encodes high level advice such as tags or user interaction in identifying similar objects across examples. Depending on the specific task, schemes to exploit such information may lead to a smooth or non-smooth regularization function. We present stochastic gradient descent methods for optimizing spectral clustering objectives with such convex regularizers for datasets with up to a hundred million examples. We prove that under mild conditions the local convergence rate is 
where T is the number of iterations; further, our analysis shows that the convergence improves linearly by increasing the number of threads. We give extensive experimental results on a range of vision datasets demonstrating the algorithm’s empirical behavior.
LNCS 8691, p. 282 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014