Consistency of archetypal analysis

DOI10.1137/20M1331792zbMATH Open1477.62161arXiv2010.08148OpenAlexW3119963133MaRDI QIDQ5019779FDOQ5019779

Authors:

Publication date: 11 January 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: Archetypal analysis is an unsupervised learning method that uses a convex polytope to summarize multivariate data. For fixed $k$, the method finds a convex polytope with $k$ vertices, called archetype points, such that the polytope is contained in the convex hull of the data and the mean squared distance between the data and the polytope is minimal. In this paper, we prove a consistency result that shows if the data is independently sampled from a probability measure with bounded support, then the archetype points converge to a solution of the continuum version of the problem, of which we identify and establish several properties. We also obtain the convergence rate of the optimal objective values under appropriate assumptions on the distribution. If the data is independently sampled from a distribution with unbounded support, we also prove a consistency result for a modified method that penalizes the dispersion of the archetype points. Our analysis is supported by detailed computational experiments of the archetype points for data sampled from the uniform distribution in a disk, the normal distribution, an annular distribution, and a Gaussian mixture model.

Full work available at URL: https://arxiv.org/abs/2010.08148

Recommendations

• Archetypal Analysis
• Probabilistic archetypal analysis
• Weighted and robust archetypal analysis
• Nonnegative matrix factorization via archetypal analysis
• Functional archetype and archetypoid analysis

zbMATH Keywords

consistencyunsupervised learningarchetypal analysismultivariate data summarizationprincipal convex hull

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Estimation in multivariate analysis (62H12) Pattern recognition, speech recognition (68T10)

Cites Work

• Strong consistency of k-means clustering
• Consistency of Single Linkage for High-Density Clusters
• High-Dimensional Probability
• Consistency of spectral clustering
• Archetypal Analysis
• Archetypal analysis of spatio-temporal dynamics
• Probabilistic archetypal analysis
• From graph to manifold Laplacian: the convergence rate
• Learning Theory
• A central limit theorem for k-means clustering
• Rates of convergence for random approximations of convex sets
• Extreme Points of Certain Sets of Probability Measures, with Applications
• Regularized \(k\)-means clustering of high-dimensional data and its asymptotic consistency
• Graph Laplacians and their convergence on random neighborhood graphs
• Learning Theory
• A variational approach to the consistency of spectral clustering
• Consistency of Cheeger and ratio graph cuts
• Consistency of Dirichlet Partitions
• Uniform behaviors of random polytopes under the Hausdorff metric

Cited In (3)

• Nearest neighbor sampling of point sets using rays
• Wasserstein archetypal analysis
• On the use of archetypes as benchmarks

This page was built for publication: Consistency of archetypal analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5019779)