Efficient and Generalizable Archetypal Analysis for Discrete Data

A. Emilie J. Wedenborg; Jesper Løve Hinrich; Morten Mørup

stat.MLOct 8, 2026

Efficient and Generalizable Archetypal Analysis for Discrete Data

Authors: A. Emilie J. Wedenborg, Jesper Løve Hinrich, Morten Mørup

Organizations: Department of Applied Mathematics and Computer Science, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark

Abstract

Archetypal Analysis (AA) represents observations as convex combinations of extremal data-driven profiles, yielding interpretable low-dimensional descriptions of complex datasets. Classical AA relies on a least-squares objective, which is poorly suited to discrete observations such as binary, count, and categorical data. We introduce an efficient likelihood-based framework for AA supporting Bernoulli, Poisson, and multinomial observation models. Our optimization scheme employs local quadratic approximations of the negative log-likelihood, enabling constrained updates through sequential minimal optimization (SMO) and an active-set method. Scalability is improved by bounding the active set while preserving simplex feasibility. We further introduce a cross-validated predictive likelihood criterion for selecting the number of archetypes, providing a principled alternative to reconstruction-error heuristics and stability-based diagnostics. Synthetic experiments demonstrate computational efficiency and accurate recovery of model complexity. Applications to single-cell RNA sequencing, microbiome composition, and somatic mutation data show that the learned archetypes capture interpretable domain-specific structures while achieving competitive likelihood fits and stable solutions. Overall, the proposed framework enables efficient likelihood-based archetypal analysis of discrete data, complemented by predictive likelihood-based model selection.

Figures & tables

Likelihood	Gradient factor $g_{i,j}$	Hessian factor $w_{i,j}$
Gaussian	$-2(x_{i,j}-r_{i,j})$	$2$
Bernoulli	$-\left(\dfrac{x_{i,j}}{r_{i,j}}-\dfrac{1-x_{i,j}}{1-r_{i,j}}\right)$	$\dfrac{x_{i,j}}{r_{i,j}^{2}}+\dfrac{1-x_{i,j}}{(1-r_{i,j})^{2}}$
Poisson	$-\left(\dfrac{x_{i,j}}{r_{i,j}}-1\right)$	$\dfrac{x_{i,j}}{r_{i,j}^{2}}$
Multinomial	$-\dfrac{x_{i,j,p}}{r_{i,j,p}}$	$\dfrac{x_{i,j,p}}{r_{i,j,p}^{2}}$

TABLE I : Likelihood-specific gradient and Hessian factors.

Update	Partial derivative	Hessian term
$\mathbf{S}$	$\displaystyle\frac{\partial L}{\partial s_{k,j}}=\sum_{i}g_{i,j}\alpha_{i,k}$	$\displaystyle h^{(j)}_{k^{\prime},k^{\prime\prime}}=\sum_{i}w_{i,j}\alpha_{i,k^{\prime}}\alpha_{i,k^{\prime\prime}}$
$\mathbf{C}$	$\displaystyle\frac{\partial L}{\partial c_{j,k}}=\sum_{i,\ell}g_{i,\ell}\beta_{i,j,\ell,k}$	$\displaystyle h^{(k)}_{j^{\prime},j^{\prime\prime}}=\sum_{i,\ell}w_{i,\ell}\beta_{i,j^{\prime},\ell,k}\beta_{i,j^{\prime\prime},\ell,k}$

TABLE II : Generic S- and C-update components using the likelihood-specific factors from Table I .

Model	$\log p(\mathbf{x}\mid\mathbf{r}_{j})$
Bernoulli	$\displaystyle\sum_{f=1}^{M}\left[x_{m}\log r_{mj}+(1-x_{m})\log(1-r_{mj})\right]$
Poisson	$\displaystyle\sum_{m=1}^{M}\left[x_{m}\log r_{mj}-r_{jm}\right]$
Gaussian	$\displaystyle-\frac{1}{2}\left(\frac{\\|\mathbf{x}-\mathbf{r}_{j}\\|_{2}^{2}}{\sigma^{2}}+d\log(2\pi)+d\log\sigma^{2}\right)$
Multinomial	$\displaystyle\sum_{m=1}^{M}x_{m}\log r_{mj}$

TABLE III : Log-likelihood contributions used in the predictive likelihood criterion.

Fig. 1 : Cross-distribution robustness of synthetic data , for

K\in\{5,10,15\}

, with

K^{\star}=5

. Each point shows the average performance of PAA, PCHA, and DAAA across repeated initializations for a fixed synthetic data setting. Runtime (seconds) and final loss (NLL) are reported relative to DAAA within each distribution, so values above one indicate slower runtime or higher loss than DAAA. NMI measures stability across random initializations, with larger values indicating more consistent recovered archetypal representations.

Fig. 2 : Convergence of Archetypal Analysis under varying active set sizes . Training loss as a function of wall-clock time for active-set fractions

N_{\text{max}}\in\{1\%,5\%,10\%,25\%,50\%,75\%,100\%\}

. Where

100\%

corresponds to using all

N

samples. Shaded bands show mean

\pm

std across five random seeds. The x-axis is on log scale.

Fig. 3 : Model selection for Gaussian archetypal analysis on synthetic data (

K=5

true archetypes). Left : Cross-validated predictive log-likelihood (Pred. LL), Gaussian training log-likelihood (Gaussian LL), and variance explained (VE) as functions of

K

at a single noise level. The predictive LL peaks at the true

K^{*}=5

(dashed line), while Gaussian LL and VE increase monotonically, failing to identify the correct model complexity (inset). Right : Predictive LL normalized by its maximum across noise levels

\sigma\in\{0.05,0.1,0.2,0.3,0.4,0.5\}

; shaded bands show variance across seeds. The predictive LL is maximised at

K^{\star}=5

across all noise levels, and the penalty for overspecifying

K

grows with

\sigma

, reflecting greater sensitivity to overfitting under high noise.

Fig. 4 : Real-data benchmarks across three datasets and distributions . Each column corresponds to one dataset (MSK Heme, Bernoulli; PBMC 3k, Poisson; HMP microbiome, Multinomial) and each row to one metric: training loss (NLL), cross-validated predictive log-likelihood (star marks the DAAA selected

K

), stability NMI across random initialisations, and wall-clock fit time. DAAA uses max_active = 25% of samples. PCHA and PAA use the full dataset. Shaded bands denote

\pm 1

standard deviation across five random seeds.

Fig. 5 : Interpretability of learned archetypes on the MSK-IMPACT Heme somatic mutation cohort . Each row corresponds to one of

K=10

archetypes. Bar colors show the fraction of hard-assigned patients from each cancer type group. Archetypes are sorted by dominant lineage, indicated by the colored strip and vertical label on the left. The four most enriched mutations per archetype, the largest positive deviations from the dataset, wide mean mutation rate, are listed to the right. Without using cancer type labels during fitting, the method recovers clinically coherent structure: the two AML archetypes are defined by chromatin-regulator mutations (ASXL1, RUNX1) and the canonical NPM1/FLT3 driver pair; the MDS archetypes are characterised by DNA-methylation genes (DNMT3A, TET2, IDH1/2); and five distinct B-NHL archetypes separate known molecular subtypes, including an ABC-DLBCL profile (MYD88, CD79B) and a follicular lymphoma profile (BCL2, EZH2, CREBBP). Archetype

A_{10}

is a diffuse, mixed-lineage profile with no single dominant mutation signal, reflecting the shared background mutation burden across all subtypes.

Fig. 6 : Within cell type gene groups across $K=40$ archetypes (PBMC3k scRNA-seq) Dot plot of gene expression across 40 archetypes fitted by DAAA to the PBMC3k dataset (2,700 peripheral blood mononuclear cells, 2,000 highly variable genes. Archetypes (A1–A40, columns) are grouped by dominant cell type (coloured bar) and sorted by decreasing cell-type purity within each group. Genes (rows) are selected as the top drivers of within-cell-type expression variance across sub-archetypes. Dot size (square-root scaled, normalised per gene) encodes within-cell-type enrichment, the archetype mean expression minus the mean across all archetypes of the same cell type, isolating sub-state variation from the shared cell-type background. Dot colour encodes absolute expression as log(1 + mean raw count), compressing the dynamic range of integer counts. CD4 T cells (A1–A12) resolve into 12 sub-archetypes spanning a translational-activity gradient (MALAT1, RPL13), an MHC-I axis (B2M), and a mitochondrial-high state (MT-CO1); CD14 + monocytes (A13–A23) separate into LYZ-high classical and FTL/FTH1-enriched sub-states

Fig. 7 : Multinomial Archetype microbiome profiles across four anatomical body-site groups (235 subjects, 18 body sites, 589 genera). ( Left ) Each bar shows the mean relative abundance of the dominant genera, averaged across all body sites within the group (Gut: 1 site; Oral: 9 sites; Skin: 5 sites; Vaginal: 3 sites). Archetype profiles are computed as the anchor-weighted mean composition

\sum_{i}C_{ik}X_{ijp}

, then averaged over sites within each group. A1 and A2 are nearly indistinguishable at gut and oral sites. Skin shows a moderate enrichment of Propionibacterium in A1 and Staphylococcus in A2. Vaginal sites show the main difference: A2 is 90% Lactobacillus on average, compared to 11% in A1. ( Right ) Histogram of A2 membership weights by sex (dashed lines: group means). Male subjects cluster near zero (mean 0.24) and female subjects near one (mean 0.86), demonstrating that the model unsupervised recovers sex as the dominant axis of variation through the vaginal Lactobacillus signal.

Explore similar work

A Survey on Archetypal Analysis
Apr 16, 2025Aleix Alcacer, Irene Epifanio, Sebastian Mair +1Representation Learning
Jaume I University and ValgrAI · Linköping University · Technical University of Denmark
Riemannian Archetypal Analysis: Interpretable non-linear data analysis on deformed star distributions
May 22, 2026Willem Diepeveen, Deanna NeedellManifold Learning Dimensionality Reduction
Department of Mathematics University of California, Los Angeles Los Angeles, CA 90095, USA
ARO: Aligned Representation learning for multi-Omics data
Oct 5, 2026Amogh Singh, Yash Shah, Chiara D'Ercoli +4Missing-Modality Learning Learning with Missing Data
Department of Computer Science, University of Cambridge, Cambridge, UK · DIAG, University of Rome “Sapienza”, Rome, Italy · Max Planck Institute for Intelligent Systems

Apr 16, 2025, stat.MEJ/K move · Enter open · S save

A Survey on Archetypal Analysis

Aleix Alcacer, Irene Epifanio, Sebastian Mair, Morten Mørup

Jaume I University and ValgrAI · Linköping University · Technical University of Denmark

Representation Learning

Open paper AskPDF arXiv

Archetypal analysis (AA) was originally proposed in 1994 by Adele Cutler and Leo Breiman as a computational procedure for extracting distinct aspects, so-called archetypes, from observations, with each observational record approximated as a mixture (i.e., convex combination) of these archetypes. AA thereby provides straightforward, interpretable, and explainable representations for feature extraction and dimensionality reduction, facilitating the understanding of the structure of high-dimensional data and enabling wide applications across the sciences. However, AA also faces challenges, particularly as the associated optimization problem is nonconvex. This is the first survey that provides researchers and data mining practitioners with an overview of the methodologies and opportunities that AA offers, surveying the many applications of AA across disparate fields of science, as well as best practices for modeling data with AA and its limitations. The survey concludes by explaining crucial future research directions concerning AA.

Abstract

Explore similar work

A Survey on Archetypal Analysis

Riemannian Archetypal Analysis: Interpretable non-linear data analysis on deformed star distributions

ARO: Aligned Representation learning for multi-Omics data