K-Polytopes: a Superproblem of K-Means

Abstract

It has already been proven that under certain circumstances dictionary learning for sparse representations is equivalent to conventional k-means clustering. Through additional modifications on sparse representations, it is possible to generalize the notion of centroids to higher orders. In a related algorithm which is called k-flats, q-dimensional flats have been considered as alternative central prototypes. In the proposed formulation of this paper, central prototypes are instead simplexes or even more general polytopes. Using higher-dimensional, nonconvex prototypes may alleviate the curse of dimensionality while also enabling to model nonlinearly distributed datasets successfully. The proposed framework in this study can further be applied in supervised settings flexibly through one-class learning and also in other nonlinear frameworks through kernels.