Most machine learning algorithms operate under a hidden geometric tax: the assumption that similarity behaves like a distance in Euclidean space. In this world, kernels must be positive definite (PD), satisfying Mercer’s condition to ensure that optimization problems remain convex and well-behaved.
However, as Frank-Michael Schleif and Peter Tiňo argue in Learning in indefinite proximity spaces - recent trends, real-world data rarely follows these strict rules. Measures like Dynamic Time Warping (DTW) for time series, edit distances for protein sequences, and KL-divergence for probability distributions are "indefinite"—they produce similarity matrices with negative eigenvalues. Standard practice involves "fixing" these matrices by discarding negative components, but this destroys the very structural information that makes the data unique.
The Geometry of Indefiniteness
To understand why this matters, imagine trying to map a set of points onto a flat sheet of paper. If the distances between points are metric, they fit perfectly. But if the distances are non-metric—perhaps point A is close to B, and B is close to C, but A is very far from C—the sheet of paper must "warp" or "stretch" in ways Euclidean geometry cannot represent.
Instead of forcing this data into a standard Hilbert space, researchers have proposed embedding it into Krein spaces. A Krein space is essentially a space that supports an indefinite inner product. As Stefanos Zafeiriou explains in Subspace Learning in Krein Spaces, this framework allows us to decompose the feature space into two distinct components: a positive subspace and a negative subspace. By treating the space as a direct sum of two Hilbert spaces, we can preserve the "negative" information rather than treating it as noise.
Reproducing Kernel Krein Spaces (RKKS)
The most robust extension of the kernel trick to this domain is the Reproducing Kernel Krein Space (RKKS). While standard methods use Reproducing Kernel Hilbert Spaces (RKHS), Fanghui Liu et al. demonstrate in Indefinite Kernel Logistic Regression that RKKS provides the necessary mathematical foundation to handle kernels that do not satisfy Mercer's condition.
The intuition is that an indefinite kernel can be viewed as the difference between two positive definite kernels. By working in an RKKS, algorithms like Indefinite Kernel PCA (IKPCA) or Krein-SVM can natively process non-metric similarities. For example, Joseph Redshaw et al. used this approach in Krein support vector machine classification of antimicrobial peptides to classify biological sequences. By using sequence alignment scores directly—which are naturally indefinite—their model outperformed traditional neural networks that required manual feature extraction.
Preserving Structure via Pseudo-Euclidean Embeddings
When we encounter negative eigenvalues during dimensionality reduction, we are seeing evidence that the data lives in a pseudo-Euclidean or Minkowski space. Mark Blumstein shows in Multi-Dimensional Scaling on Groups that these negative spectral components are not errors; they are fundamental "frequencies" of the data's underlying structure.
This perspective is powerful for tasks like approximate nearest neighbor search. Yadong Mu et al. developed a non-metric Locality-Sensitive Hashing (LSH) scheme in Non-Metric Locality-Sensitive Hashing by embedding data into an indefinite RKKS. This allows the hashing algorithm to capture human-like perceptual similarities that standard metric-based hashing would miss. Similarly, Harit Vishwakarma et al. utilized pseudo-Euclidean embeddings in Lifting Weak Supervision To Structured Prediction to represent complex structures like rankings isometrically, ensuring that geometric relationships are maintained exactly during analysis.
Overcoming the Optimization Challenge
The primary hurdle for indefinite learning is that the loss functions often become non-convex. To solve this, Fanghui Liu et al. proposed the Concave-Inexact-Convex Procedure (CCICP) in Indefinite Kernel Logistic Regression With Concave-Inexact-Convex Procedure. This optimization framework breaks the problem into manageable pieces, allowing models to converge efficiently even in the presence of negative inner products.
Furthermore, recent theoretical work has begun to close the gap between indefinite and standard kernels. In Analysis of regularized least-squares in reproducing kernel Kreĭn spaces, Fanghui Liu et al. proved that under certain conditions, learning algorithms in RKKS can achieve learning rates comparable to those in standard Hilbert spaces. This suggests that the flexibility of indefinite kernels does not necessarily come at the cost of theoretical reliability.
By embracing the "weirdness" of non-metric data through Krein spaces and pseudo-Euclidean embeddings, researchers are moving toward a more expressive form of machine learning—one that respects the inherent geometry of the problem rather than forcing it into a Euclidean box.
Key Foundational Work
Non-Metric Locality-Sensitive Hashing (2010) — contributed 1 concept elements to this direction.
Subspace Learning in Krein Spaces: Complete Kernel Fisher Discriminant Analysis with Indefinite Kernels (2012) — contributed 1 concept elements to this direction.