|
Ravi Kannan Microsoft Research |
|
The elegant Lloyd's algorithm (k-means algorithm) for clustering is a workhorse in many applications. But it can fail to yield the \desired" clustering. Assuming (i) clusters are far apart (means separated by several standard deviations) and (ii) stochastic models of data, more complex algorithms producing the desired clustering have been developed over the last decade. Here we prove that the k-means algorithm does yield the desired clustering assuming a purely deterministic version of (i) and (b) starting centers \close enough" to the desired centers. Another workhorse - Singular Value Decomposition gives us such a good start. This result subsumes known stochastic results. Ravi Kannan, Joint work with Amit Kumar, IIT, Delhi
Bio: Ravindran Kannan is currently a Principal Researcher at Microsoft Research India, where he leads the Algorithms Research Group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science. Before joining Microsoft, he was the William K. Lanman Jr. Professor of Computer Science and Professor of Applied Mathematics at Yale University. He has also taught at MIT and CMU. The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2011 Knuth Prize to Ravi Kannan for developing influential algorithmic techniques aimed at solving long-standing computational problems.
Ravi Kannan did his B.Tech at IIT, Bombay and PhD. at Cornell University. His research interests include Algorithms, Theoretical Computer Science and Discrete Mathematics as well as Optimization. His work has mainly focused on efficient algorithms for problems of a mathematical (often geometric) flavor that arise in Computer Science. He has worked on algorithms for integer programming and the geometry of numbers, random walks in n-space, randomized algorithms for linear algebra and learning algorithms for convex sets. |
|
4:15pm B17 Upson Hall Thursday, September 1, 2011 Refreshments at 3:45pm in the Upson 4th Floor Atrium |
|
Computer Science Colloquium Fall 2011 |
|
www.cs.cornell.edu/events/colloquium |
|
The k-means algorithm works |