Centerless Learning via Pairwise Distance Objectives

20 concepts10 papers2 proposals

Many foundational algorithms in machine learning rely on a central reference point. Principal Component Analysis (PCA) maximizes variance relative to the empirical mean; $K$-means clustering iteratively updates cluster centroids; Linear Discriminant Analysis (LDA) separates classes based on global and class-specific means.

However, computing an explicit mean introduces severe vulnerabilities:

  1. Outlier Sensitivity: A single extreme outlier can heavily distort an arithmetic mean, dragging the entire coordinate system or cluster boundary along with it.
  2. Initialization Dependency: Centroid-based clustering algorithms are notoriously sensitive to initial random centroid placement, often getting trapped in poor local optima.
  3. Geometric Instability: In non-Euclidean geometries or complex data spaces (such as hyperbolic spaces or spaces of probability distributions), a central "mean" may be mathematically unstable, non-unique, or computationally prohibitive to compute.

To bypass these limitations, a growing body of research reformulates classical unsupervised learning objectives to eliminate central reference points entirely, replacing them with objectives based strictly on pairwise distances or differences.

The Pairwise Intuition

How do we measure the spread or compactness of data without computing a mean? The core insight relies on a simple algebraic identity. In a Euclidean space, the sum of squared deviations of $n$ points from their sample mean $\mu$ is exactly proportional to the sum of all squared pairwise distances between those points:

$$\sum_{i=1}^n \|x_i - \mu\|^2 = \frac{1}{2n} \sum_{i=1}^n \sum_{j=1}^n \|x_i - x_j\|^2$$

By optimizing the right-hand side of this equation, we can reason about the global structure of data without ever calculating $\mu$. This shift from absolute coordinates relative to a center to relative coordinates between pairs forms the foundation of centerless learning.

Crucially, once the objective is framed in terms of pairwise differences, we are no longer bound to the squared $\ell_2$-norm. We can substitute robust norms ($\ell_1$ or $\ell_{2,p}$) or non-Euclidean metrics directly into the pairwise interactions—modifications that would make calculating an explicit analytical mean mathematically intractable.

Robust Dimensionality Reduction Without the Mean

Traditional PCA maximizes variance, making it highly vulnerable to outliers. To address this, Luo et al. and the authors of Avoiding Optimal Mean Robust PCA/2DPCA with Non-greedy reformulated PCA to maximize the sum of projected pairwise differences using a robust $\ell_1$-norm. Because the objective function omits the mean entirely, outliers cannot bias the projection space through a skewed central reference point. Expanding on this, Liao et al. generalized the pairwise variation maximization framework to the $\ell_{2,p}$-norm ($0 < p < 2$), providing even greater flexibility and robustness against heavy-tailed noise.

Traditional PCA:
[Data Points] ------> Distance to Mean (Skewed by Outliers) -------> Projection

Centerless PCA:
[Data Point A] <==== Pairwise Difference (Robust Norm) ====> [Data Point B] ===> Projection

This principle also extends to discriminant analysis. Standard LDA can be derailed if a single outlier class pulls the global mean away from the rest of the data. To mitigate this, Yan et al. replaced the global mean in the between-class scatter matrix with the sum of distances between all pairs of class centers, ensuring that a single distant category does not dominate the projection space.

Centerless Clustering and Initialization Independence

In clustering, the reliance on centroids creates a chicken-and-egg problem: to find good clusters, we need good centroids, but to find good centroids, we need good clusters.

By reformulating clustering to minimize intra-cluster pairwise distances rather than distances to an explicit centroid, researchers have developed "centerless" clustering frameworks that eliminate initialization anxiety. Wang et al. proposed a centerless $K$-means framework that swaps centroid calculations for minimizing intra-cluster sample distances, allowing the algorithm to handle non-linearly separable data via manifold learning. Similarly, Lu et al. framed centerless multi-view clustering as a matrix trace minimization problem over an adjacency matrix, completely bypassing random centroid initialization.

To scale this to deep learning and unsupervised dimensionality reduction, Yan et al. introduced Deep Online Probability Aggregation Clustering (DPAC), which defines cluster membership based on collective spatial relationships and pairwise distances in a mini-batch fashion. In parallel, Wang et al. integrated centerless clustering directly into an unsupervised discriminant dimensionality reduction framework, demonstrating that optimizing pairwise sample distances prevents individual noisy points from distorting the global subspace structure.

Thriving in Non-Euclidean Spaces

The true elegance of the centerless approach emerges when data does not live in a flat Euclidean space, where computing a mean is often mathematically fraught.

Probability Distributions and Wasserstein Space

When clustering probability distributions, the standard "average" distribution is the Wasserstein barycenter. However, as Zhuang et al. note, Wasserstein barycenters are mathematically unstable and highly sensitive to noise or small perturbations. By optimizing the sum of squared pairwise Wasserstein distances within each cluster instead, their method bypasses barycenters entirely, yielding stable and consistent clustering on distributional data.

Hyperbolic Space and Hierarchical Data

A parallel challenge exists in hyperbolic spaces, which are widely used to model hierarchical data. Traditional PCA requires choosing a central "base point" or origin to project data, breaking location invariance. To solve this, Chami et al. introduced HoroPCA, which optimizes an intrinsic variance objective based entirely on the average of all squared pairwise distances between projected points. This formulation achieves complete base-point independence, ensuring that the learned principal components remain invariant to coordinate shifts on the hyperbolic manifold.

Key Foundational Work

Robust Formulation for PCA: Avoiding Mean Calculation With L2, p-norm Maximization (2018) — contributed 2 concept elements to this direction.
Avoiding Optimal Mean Robust PCA/2DPCA with Non-greedy ℓ1-Norm Maximization (2016) — contributed 2 concept elements to this direction.
Avoiding Optimal Mean Robust PCA/2DPCA with Non-greedy ℓ1-Norm Maximization (2016) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 11 papers
  2. Version 1 · 2026-10-04 · 16 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_mean_invariant_dimensionality_reduction_e36c7571,
  title = {mean-invariant dimensionality reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mean-invariant-dimensionality-reduction/rdr_e36c7571496246f59136dd5697b97371},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_mean_invariant_dimensionality_reduction_e36c7571_v2,
  title = {mean-invariant dimensionality reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mean-invariant-dimensionality-reduction/rdr_e36c7571496246f59136dd5697b97371/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake