Learning with Indefinite Kernels in Krein Spaces

This direction is merged into another direction: positive semi-definite constraint. Its last version stays readable and citable here.

Version 1 of 112 papers26 conceptsfrozen 2026-10-04

In classical kernel methods, we assume that similarity is "well-behaved." Mathematically, this means using a Positive Definite (PD) kernel, which ensures that our data can be mapped into a Reproducing Kernel Hilbert Space (RKHS). In this space, every point has a positive "norm," and optimization problems are generally convex and solvable.

However, real-world similarity often breaks these rules. Human perception, hyperbolic distances, KL divergence, and even the Neural Tangent Kernel (NTK) on a unit sphere can be indefinite. These kernels produce matrices with negative eigenvalues, causing standard algorithms to fail. To handle these "invalid" kernels, researchers have turned to Reproducing Kernel Kreĭn Spaces (RKKS)—a theoretical framework that embraces negative geometry to unlock more expressive similarity measures.

The Geometry of Negative Space

A Hilbert space is like a standard Euclidean space: the distance from a point to itself is always positive. A Kreĭn space, however, is more flexible. It can be thought of as the difference between two Hilbert spaces.

As Yadong MU and Shuicheng YAN demonstrate in Non-Metric Locality-Sensitive Hashing, many perceptual similarities are non-metric. By embedding data into an indefinite Kreĭn space, we can capture complex relationships—like the Chamfer distance used in vision—that standard hashing methods lose.

The intuition is that an indefinite kernel $k$ can be decomposed into two positive definite components: $$k(x, y) = k_+(x, y) - k_-(x, y)$$ Here, $k_+$ represents the "standard" similarity, while $k_-$ captures the "indefinite" or "negative" spectral information. This decomposition allows us to treat an indefinite problem as two parallel positive definite problems that are recombined at the end.

The Decomposition Hurdle

While it is easy to decompose a finite matrix into positive and negative parts using its eigenvalues, decomposing a kernel function (which must work for any possible set of points) is much harder. For years, it was unclear if every indefinite kernel could be formally split into $k_+ - k_-$.

Fanghui Liu, Xiaolin Huang, and Johan Suykens solved this in Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures. They leveraged the theory of signed measures.

In standard kernel theory (Bochner’s Theorem), a stationary kernel is the Fourier transform of a positive probability measure. For indefinite kernels, the Fourier transform is a signed measure—it can assign negative weights to certain frequencies. By applying the Jordan decomposition theorem, the authors split this signed measure into two distinct non-negative measures. This provides a necessary and sufficient condition: an indefinite kernel is decomposable if and only if the total mass of its associated signed measure is finite.

Scaling to Large Datasets

Once we have a decomposition, how do we actually compute with it? Standard kernel methods scale poorly ($O(n^3)$). To solve this, the field uses Random Fourier Features (RFF), which approximate the kernel by sampling from its spectral distribution.

In Fast Learning in Reproducing Kernel Krein Spaces via Generalized Measures, Fanghui Liu and colleagues introduced the first unbiased random features algorithm for indefinite kernels. Instead of sampling from one probability distribution, they sample from the positive and negative parts of the Jordan decomposition separately. This allows them to build a feature map that accounts for the negative eigenvalues, leading to much lower approximation errors than simply "ignoring" the indefiniteness.

This approach even extends to asymmetric kernels (like those found in directed graphs or Transformer attention). In Random Fourier Features for Asymmetric Kernels, Mingzhen He and Fanghui Liu show that by splitting complex measures into four positive components, they can create scalable, theoretically grounded approximations for non-symmetric similarities.

Why It Works: Stability and Convergence

One might worry that working with negative inner products would make learning unstable. However, Analysis of regularized least-squares in reproducing kernel Kreĭn spaces proves that under certain conditions—such as adding a spherical constraint to manage non-convexity—learning rates in Kreĭn spaces can actually match the optimal rates of standard Hilbert spaces.

Furthermore, Nathaël Da Costa and Cyrus Mostajeran argue in Geometric Learning with Positively Decomposable Kernels that many "invalid" kernels used on manifolds (like the geodesic Gaussian) are actually well-founded when viewed through the lens of Kreĭn spaces.

By moving from Hilbert to Kreĭn, we stop trying to force square pegs into round holes. Instead of approximating an indefinite similarity with a "close" positive definite one, we model the full spectrum of the data, including its negative components, leading to more precise and theoretically sound machine learning models.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_learning_with_indefinite_kernels_in_krei_7f2c485a,
  title = {Learning with Indefinite Kernels in Krein Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-with-indefinite-kernels-in-krein-spaces/rdr_7f2c485aa9084aaabf2497e02ddd73c3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_learning_with_indefinite_kernels_in_krei_7f2c485a_v1,
  title = {Learning with Indefinite Kernels in Krein Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-with-indefinite-kernels-in-krein-spaces/rdr_7f2c485aa9084aaabf2497e02ddd73c3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}