When we compute pairwise similarities between real-world objects—whether comparing human facial features, protein sequences, or text documents—we often find that our data defies standard Euclidean geometry. In a perfectly flat, Euclidean world, similarities are well-behaved and satisfy the triangle inequality. Mathematically, this means the matrix representing these similarities is positive semidefinite (PSD), containing only non-negative eigenvalues.
However, real-world data is rarely so cooperative. Human perception and complex domain-specific metrics frequently violate metric axioms. When you perform an eigendecomposition on these non-metric similarity matrices, you encounter a mathematical surprise: negative eigenvalues.
For decades, the standard engineering response to negative eigenvalues was to treat them as noise or artifacts. Practitioners routinely "fixed" indefinite matrices by clipping, flipping, or shifting the negative components to force the matrix back into a valid PSD state. But a growing body of research reveals that this mathematical housekeeping comes at a steep cost. Negative eigenvalues are not noise; they encode critical structural, semantic, and discriminative information.
The Destructive Nature of the PSD Fix
To understand why forcing an indefinite matrix to be PSD is problematic, we have to look at what happens to the underlying data space during these transformations. Standard kernel methods, like classical Support Vector Machines (SVMs), rely on the Mercer condition, which requires a PSD kernel to guarantee a convex optimization problem.
When faced with an indefinite kernel, a common heuristic is to project it onto the PSD cone by zeroing out the negative eigenvalues (clipping) or taking their absolute values (flipping). As shown by Ying et al. and Luss et al., this arbitrary truncation discards significant discriminative features relevant to the learning task. Similarly, in network structure recovery, Fan et al. observe that zeroing out negative eigenvalues to handle noisy, indefinite input matrices strips away valuable information, leading to less accurate precision matrix estimations.
Beyond simple information loss, spectral manipulation introduces a fundamental algorithmic flaw: train-test mismatch.
[Raw Indefinite Data] ───> Preprocessing: Clip/Flip ───> [Forced PSD Matrix] ───> Train Model
│
(Inconsistency!)
▼
[New Test Sample] ─────────────────────────────────────────────────────────────> Inference
When you alter the eigenvalues of a training matrix, you are implicitly changing the feature space. However, when a new test sample arrives, its similarities are computed using the original, raw non-metric function. As highlighted by Gu et al., Alabdulmohsin et al., and Liu et al., this creates an architectural disconnect. The model is trained on a distorted, forced-PSD space but evaluated on the raw, indefinite space, severely degrading generalization performance.
What the Negative Spectrum Actually Encodes
If negative eigenvalues aren't noise, what are they? They are mathematical signatures of non-Euclidean structure.
In a foundational paper, Julian Laub demonstrated in Feature Discovery in Non-Metric Pairwise Data that the negative components of a spectrum capture genuine, hidden features that Euclidean methods systematically ignore. For example, when analyzing handwriting similarities, the positive eigenvalues might capture the basic topology of a digit, while the negative eigenvalues encode fine-grained structural variations like stroke weight. In text analysis, they can capture abstract semantic relationships like word specificity.
This perspective is echoed across diverse domains:
- Data Topology: Zhang et al. and Münch et al. argue that non-metricity is an intrinsic property of complex data, such as time-series alignments or human perceptual distances. Forcing these matrices into metric formats distorts the true semantic relationships.
- Group Symmetries: When analyzing discrete spaces with group symmetries, Mark Blumstein showed that Multidimensional Scaling (MDS) behaves like a generalized Fourier transform, where negative eigenvalues correspond to fundamental "frequencies" of the underlying group structure.
- Discriminative Power: In face recognition and subspace learning, Stefanos Zafeiriou proved that the dimensions associated with large negative eigenvalues contain highly discriminative structural information, meaning the negative subspace is just as valuable for classification as the positive one.
Embracing Indefiniteness Natively
Rather than fighting indefiniteness, modern machine learning frameworks seek to work with it natively. This shift requires moving away from traditional Hilbert spaces (which are strictly positive-definite) and adopting mathematical frameworks that accommodate both positive and negative dimensions.
1. Kreĭn Spaces and Bilinear Forms
A Kreĭn space is an inner product space endowed with an indefinite metric. Instead of computing standard Euclidean distances, it splits the geometry into a positive subspace and a negative subspace.
The Non-Metric Locality-Sensitive Hashing framework leverages this by embedding non-metric data directly into an indefinite reproducing kernel Kreĭn space. This allows fast approximate nearest-neighbor searches to preserve human-like perceptual similarities without losing structural information.
Similarly, in geometric embeddings, Deng et al. introduced Neuc-MDS, an extension of Multidimensional Scaling that uses symmetric bilinear forms. By intentionally selecting both positive and negative eigenvalues, it dramatically reduces embedding error and resolves the "dimensionality paradox"—a phenomenon where adding dimensions in classical MDS can counterintuitively make non-Euclidean reconstructions worse.
2. Absolute Eigenvalue Selection
When performing dimensionality reduction on indefinite data, standard practices dictate selecting the eigenvectors corresponding to the largest positive eigenvalues. However, in Kreĭn spaces, the magnitude of the eigenvalue dictates its informational importance, regardless of its sign.
Stefanos Zafeiriou formalized this by showing that subspace learning is most effective when eigenvectors are selected based on their largest absolute eigenvalues. This ensures that dominant negative dimensions—which contain crucial structural contrasts—are preserved rather than discarded.
3. Non-Convex Optimization and Primal Formulations
If we refuse to alter the indefinite kernel, the resulting optimization problem becomes non-convex. To solve this without sacrificing mathematical rigor, researchers use advanced optimization techniques that bypass the need for the Mercer condition.
- Difference of Convex (DC) Programming: Xu et al. and Xue et al. reformulate the non-convex learning objectives of indefinite SVMs and feature selection models as the difference of two convex functions. This allows them to optimize the models in their native primal forms, achieving superior classification accuracy and faster convergence without altering the underlying data structure.
- 1-Norm Regularization: Alabdulmohsin et al. and Alabdulmohsin et al. demonstrated that the 1-norm SVM is exceptionally well-suited for indefinite similarities. It provides a naturally convex, highly sparse solution that completely avoids spectral transformations, treating the raw similarity scores consistently during both training and inference.
By treating the negative spectrum as an asset rather than a liability, these methods allow machine learning models to capture the full geometric complexity of non-metric data.
Key Foundational Work
Feature Discovery in Non-Metric Pairwise Data (2004) — contributed 1 concept elements to this direction.
Classification on Pairwise Proximity Data (1998) — contributed 1 concept elements to this direction.