Abstract
Archetypal analysis is an unsupervised learning method for exploratory dataanalysis. One major challenge that limits the applicability of archetypalanalysis in practice is the inherent computational complexity of the existingalgorithms. In this paper, we provide a novel approximation approach topartially address this issue. Utilizing probabilistic ideas fromhigh-dimensional geometry, we introduce two preprocessing techniques to reducethe dimension and representation cardinality of the data, respectively. Weprove that provided the data is approximately embedded in a low-dimensionallinear subspace and the convex hull of the corresponding representations iswell approximated by a polytope with a few vertices, our method can effectivelyreduce the scaling of archetypal analysis. Moreover, the solution of thereduced problem is near-optimal in terms of prediction errors. Our approach canbe combined with other acceleration techniques to further mitigate theintrinsic complexity of archetypal analysis. We demonstrate the usefulness ofour results by applying our method to summarize several moderately large-scaledatasets.