semidefinite relaxation

Wednesday, January 27, 2016 - 3:15pm - 4:05pm
Rachel Ward (The University of Texas at Austin)
The k-means clustering objective is known to be hard to minimize in general, requiring an exhaustive search over all possible partitions of a given set of data into k clusters. At the same time, fast alternating minimization algorithms act as effective surrogates for the k-means optimization problem in practice, despite only being guaranteed in general to converge to local minimizers. As a compromise between accuracy and speed, we consider a semidefinite programming relaxation of the k-means optimization problem, followed by rounding if necessary.
Subscribe to RSS - semidefinite relaxation