Spectral Clustering with a Convex Regularizer on Millions of Images
Maxwell D. Collins, Ji Liu, Jia Xu, Lopamudra Mukherjee, Vikas Singh. Spectral Clustering with a Convex Regularizer on Millions of Images. Proceedings of European Conference on Computer Vision (ECCV), September 2014.
Code
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 which 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.