In classical kernel-based machine learning, the "kernel trick" relies on a strict mathematical guarantee: the similarity function must be symmetric and positive semi-definite (PSD). This requirement, known as Mercer's condition, ensures that the kernel matrix behaves like a matrix of inner products in a high-dimensional Hilbert space. Geometrically, it guarantees that the optimization landscape of algorithms like Support Vector Machines (SVMs) is a perfectly convex bowl with a single, easily reachable global minimum.
However, real-world data rarely conforms to these strict geometric rules. When we build similarity measures for complex structures—such as alignment scores for protein sequences, structural paths in heterogeneous networks, edit distances for text, or subjective human judgments—the resulting matrices are frequently indefinite, meaning they contain negative eigenvalues.
Standard PSD Kernel: [Convex Bowl] --> Unique Global Minimum
Indefinite Kernel: [Saddle/Rugged] --> Non-Convex / Unbounded Optimization
As Fanghui Liu et al. note in Indefinite Kernel Logistic Regression With Concave-Inexact-Convex Procedure, this indefiniteness breaks traditional kernel methods. If you plug an indefinite matrix directly into a standard SVM, the optimization landscape warps, creating local minima or becoming entirely unbounded.
Historically, practitioners "fixed" this by clipping or thresholding negative eigenvalues to force the matrix into a PSD shape. However, as Ibrahim Alabdulmohsin et al. argue in Support vector machines with indefinite kernels, this heuristic discards vital structural information and creates a mathematical mismatch between training and testing data. Instead of fixing the data to fit the math, a prominent research direction focuses on changing the math to natively embrace indefinite similarities.
Re-Engineering the Optimization Landscape
If we refuse to alter the raw, indefinite similarity matrix, we must alter how we optimize over it. Researchers have developed two primary algorithmic strategies to maintain stable learning without forcing PSD constraints.
1. Linear Programming via the 1-Norm
Standard SVMs use a 2-norm (quadratic) regularization term, which directly interacts with the kernel matrix's eigenvalues. If the matrix has negative eigenvalues, the quadratic form loses convexity.
To bypass this, Ibrahim Alabdulmohsin et al. demonstrate in Large margin classification with indefinite similarities that switching to a 1-norm SVM formulation completely immunizes the optimization process against indefiniteness. Because the 1-norm objective relies on linear programming rather than quadratic programming, the optimization problem remains strictly convex regardless of the kernel's eigenvalues. This allows the model to find a globally optimal separating hyperplane while natively preserving the raw, non-Mercer similarity metrics.
2. Difference of Convex (DC) Programming
When quadratic formulations are preferred, the non-convexity must be managed explicitly. Any indefinite kernel matrix $K$ can be mathematically decomposed into the difference of two PSD matrices: $K = K_+ - K_-$.
In Solving Indefinite Kernel Support Vector Machine with Difference of Convex Functions Programming, Haiming Xu et al. leverage this decomposition to solve the SVM primal problem using Difference of Convex (DC) programming. By separating the objective function into a well-behaved convex part (governed by $K_+$) and a concave part (governed by $K_-$), they can iteratively linearize the concave component. This approach is expanded by Hui Xue et al. in Multiple Indefinite Kernel Learning for Feature Selection, demonstrating that optimizing in the primal space avoids the severe duality gaps that occur when trying to solve indefinite problems in the dual space.
Moving Beyond Hilbert Spaces
Another way to understand why indefinite kernels work is to replace the underlying geometric framework entirely. Traditional kernels map data into a Hilbert space (an inner product space with strictly positive distances). Indefinite kernels require spaces that allow for negative variance or directional scaling.
Krein Spaces
Stefanos Zafeiriou provides a rigorous geometric alternative by shifting learning from Hilbert spaces to Krein spaces in Subspace Learning in Krein Spaces: Complete Kernel Fisher Discriminant Analysis with Indefinite Kernels. A Krein space is an inner product space equipped with an indefinite metric, meaning the inner product of a vector with itself can be negative. By formalizing operations like Principal Component Analysis (PCA) and Fisher Discriminant Analysis within Krein spaces, the author shows that non-PSD similarity measures can be treated with the same geometric rigor as standard Euclidean projections.
Signed Measures for Scalability
Decomposing indefinite kernels into positive and negative spaces is theoretically clean, but computationally expensive for large datasets. To scale these methods, Fanghui Liu et al. introduced a framework based on signed measures in Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures. By treating the negative components of the kernel as negative weights in a continuous measure space, the authors developed the first unbiased random features algorithm for indefinite kernels. This allows large-scale models to approximate indefinite similarities on the fly, bypassing the $O(N^3)$ cost of full matrix decompositions.
Bypassing the Kernel Trick Entirely
The most radical conceptual shift in this field abandons the idea that a similarity function must represent a high-dimensional geometric projection at all. Instead, it treats similarity scores simply as raw, informative features.
Traditional Kernel Trick: Data Point --> High-Dim Hilbert Space --> Dot Product
Similarity-as-Features: Data Point --> Vector of Similarities to Landmarks --> Linear Classifier
The Similarity Function Framework
Maria Florina Balcan et al. established a foundational theory for this perspective in On a theory of learning with similarity functions. They proved that a similarity function does not need to be symmetric or PSD to guarantee learnability. Instead, they define a "good" similarity function purely by its behavior: it must, on average, rate pairs of the same class as more similar than pairs of different classes.
If this condition is met, you can select a set of random "landmark" points from your dataset and represent every other data point as a vector of similarity scores to these landmarks. As Avrim Blum demonstrates in A Theory of Similarity Functions for Learning and Clustering, this maps the data into a low-dimensional space where standard linear classifiers can achieve high accuracy with rigorous generalization guarantees. Purushottam Kar and Prateek Jain extended this framework to regression and ranking in Supervised Learning with Similarity Functions, proving empirically that landmark-based models using raw non-PSD metrics (like Sigmoid or Manhattan measures) frequently outperform rigid PSD kernels by retaining raw, un-smoothed information.
Automatic Relevance Determination
This concept of using arbitrary similarity functions as basis features aligns closely with the Relevance Vector Machine (RVM) introduced by Michael E. Tipping in The Relevance Vector Machine. Because the RVM is a Bayesian framework that relies on Automatic Relevance Determination (ARD) to prune unnecessary parameters, it does not require kernels to satisfy Mercer's condition. The model treats the basis functions as arbitrary similarity fields, aggressively pruning irrelevant landmarks to create highly sparse, probabilistic predictors without ever enforcing a positive semi-definite constraint.
Key Foundational Work
The Relevance Vector Machine (1999) — contributed 3 concept elements to this direction.