Kernel sums¶
A kernel sum computes, for every point x_i, Σ_j k(x_i, y_j) b_j. It is the
basic operation behind kernel density estimation, Gaussian processes, kernel
methods and many particle simulations.
Gaussian kernel¶
import torch
import kernox as kp
device = "cuda"
x, y = kp.Vi("x", 3), kp.Vj("y", 3)
b = kp.Vj("b", 1)
sigma = kp.Param("sigma")
k = kp.exp(-x.sqdist(y) / (2 * sigma**2))
gauss = kp.compile((k * b).sum_over("j"), dtype="float32")
X = torch.randn(5_000, 3, device=device)
Y = torch.randn(10_000, 3, device=device)
B = torch.randn(10_000, 1, device=device)
out = gauss(x=X, y=Y, b=B, sigma=0.3) # (5000, 1)
The 5,000 × 10,000 kernel matrix is never stored, so the same code works for millions of points: memory stays proportional to M + N.
Several signals at once¶
Give b more columns to apply the same kernel to several signals in a single
pass. The output has one column per signal:
b5 = kp.Vj("b", 5)
gauss5 = kp.compile((k * b5).sum_over("j"), dtype="float32")
out5 = gauss5(x=X, y=Y, b=torch.randn(10_000, 5, device=device), sigma=0.3) # (5000, 5)
Other kernels¶
Any formula works. A few common ones:
r2 = x.sqdist(y)
laplace = kp.exp(-kp.sqrt(r2) / sigma)
cauchy = 1 / (1 + r2 / sigma**2)
matern32 = (1 + kp.sqrt(3 * r2) / sigma) * kp.exp(-kp.sqrt(3 * r2) / sigma)
Anisotropic distances use weightedsqdist. With a weight s of dimension D,
the distance is Σ_k s_k (x_k - y_k)²:
s = kp.Param("s", 3)
aniso = kp.exp(-x.weightedsqdist(y, s))
run = kp.compile((aniso * b).sum_over("j"), dtype="float32")
out = run(x=X, y=Y, b=B, s=[1.0, 0.5, 2.0])
Accuracy of large sums¶
In float32, a sum over millions of terms loses a few digits. Two remedies, both cheap compared to switching everything to float64:
kahan = kp.compile((k * b).sum_over("j"), dtype="float32", sum_scheme="kahan")
acc64 = kp.compile((k * b).sum_over("j"), dtype="float32", acc_dtype="float64")
The first uses compensated summation; the second accumulates in float64 and returns a float64 result. See Numerics.
Gradients¶
The result is differentiable with respect to X, Y, B and a tensor
sigma: see Gradients.