Doubly Stochastic Subspace Clustering
  Many state-of-the-art subspace clustering methods follow a two-step process
by first constructing an affinity matrix between data points and then applying
spectral clustering to this affinity. Most of the research into these methods
focuses on the first step of generating the affinity, which often exploits the
self-expressive property of linear subspaces, with little consideration
typically given to the spectral clustering step that produces the final
clustering. Moreover, existing methods often obtain the final affinity that is
used in the spectral clustering step by applying ad-hoc or arbitrarily chosen
postprocessing steps to the affinity generated by a self-expressive clustering
formulation, which can have a significant impact on the overall clustering
performance. In this work, we unify these two steps by learning both a
self-expressive representation of the data and an affinity matrix that is
well-normalized for spectral clustering. In our proposed models, we constrain
the affinity matrix to be doubly stochastic, which results in a principled
method for affinity matrix normalization while also exploiting known benefits
of doubly stochastic normalization in spectral clustering. We develop a general
framework and derive two models: one that jointly learns the self-expressive
representation along with the doubly stochastic affinity, and one that
sequentially solves for one then the other. Furthermore, we leverage sparsity
in the problem to develop a fast active-set method for the sequential solver
that enables efficient computation on large datasets. Experiments show that our
method achieves state-of-the-art subspace clustering performance on many common
datasets in computer vision.
