Timezone: »

 
Spotlight
Understanding Doubly Stochastic Clustering
Tianjiao Ding · Derek Lim · Rene Vidal · Benjamin Haeffele

Thu Jul 21 01:55 PM -- 02:00 PM (PDT) @ Room 301 - 303
in Applications/MISC »

The problem of projecting a matrix onto the space of \emph{doubly stochastic} matrices finds several applications in machine learning. For example, in spectral clustering, it has been shown that forming the normalized Laplacian matrix from a data affinity matrix has close connections to projecting it onto the set of doubly stochastic matrices. However, the analysis of why this projection improves clustering has been limited. In this paper we present theoretical conditions on the given affinity matrix under which its doubly stochastic projection is an ideal affinity matrix (i.e., it has no false connections between clusters, and is well-connected within each cluster). In particular, we show that a necessary and sufficient condition for a projected affinity matrix to be ideal reduces to a set of conditions on the input affinity that decompose along each cluster. Further, in the \emph{subspace clustering} problem, where each cluster is defined by a linear subspace, we provide geometric conditions on the underlying subspaces which guarantee correct clustering via a continuous version of the problem. This allows us to explain theoretically the remarkable performance of a recently proposed doubly stochastic subspace clustering method.

Keywords: MISC: Unsupervised and Semi-supervised Learning

Author Information

Tianjiao Ding (Johns Hopkins University)
Tianjiao Ding

I am a second-year Ph.D. student at [Johns Hopkins University](https://www.jhu.edu/), advised by [René Vidal](http://cis.jhu.edu/~rvidal/). I also work closely with [Benjamin D. Haeffele](https://www.cis.jhu.edu/~haeffele/) and [Yi Ma](http://people.eecs.berkeley.edu/~yima/). Prior to joining Hopkins, I spent two years as a research assistant at [ShanghaiTech University](https://sist.shanghaitech.edu.cn/sist_en/), advised by [Manolis C. Tsakiris](https://sites.google.com/site/manolisctsakiris/) and collaborating with [Laurent Kneip](https://laurentkneip.com/). I received my undergraduate degree in computer science with honor from [ShanghaiTech](https://sist.shanghaitech.edu.cn/sist_en/), working with [Manolis](https://sites.google.com/site/manolisctsakiris/) and [Yi](http://people.eecs.berkeley.edu/~yima/). My research interests lie in the theoretical foundations of machine learning and data science as well as emerging applications. As such, I develop both rigorous mathematics and practical implementations in my work. In particular, I study subspace learning, 3D vision, and robotics.

Derek Lim (MIT)
Rene Vidal (Johns Hopkins University, USA)
Benjamin Haeffele (Johns Hopkins University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors