The Weizmann Institute of Science
Faculty of Mathematics and Computer Science
Vision and Robotics Seminar
Amnon Shashua
School of Engineering and Computer Science
Hebrew University of Jerusalem
will speak on
Probabilistic and Hard Clustering in Graphs and Hypergraphs
and Symmetric Factorization
Abstract:
I will show that the problem of finding a probabilistic partition of points
into groups (clustering) from n-tuple ``affinity" measurements among subsets of
n points can be represented as a collection of conditional independent
statements leading to a symmetric factorization problem. When n=2 (pairwise
affinity measures) we obtain a non-negative symmetric matrix factorization
problem and for n$>$2 it becomes a non-negative super-symmetric tensor
factorization problem. The resulting algebraic principle generalizes the
problem of finding a maximal clique, spectral clustering and K-means. Finding
the global solution requires a solution to a concave optimization problem
(which is NP-complete) and we will derive a number of efficient iterative
update schemes which converge to local optimum solutions. The algorithms are
applied to general clustering problems and to model selection such as 3D
multi-body segmentation and illumination-cone segmentation.
The talk is based on a recent paper with Ron Zass (ICCV05) and a submitted
paper with Tamir Hazan and Ron Zass.
The lecture will take place in the
Lecture Hall, Room 1, Ziskind Building
on Thursday, December 8, 2005
noon - 13:00