The math behind KTS

This is the only heavily mathematical chapter. We'll go slowly and explain every symbol. The payoff is one simple formula that scores how "tight" a segment is, using only the kernel matrix from the previous chapter.

Reading the notation

A few symbols appear a lot:

  • $\sum_{t=i}^{j}$ means "add up, for every $t$ from $i$ to $j$." For example $\sum_{t=1}^{3} t = 1 + 2 + 3 = 6$. The big $\Sigma$ is just shorthand for "sum".
  • $\phi_t$ (the Greek letter phi) is frame $t$'s fingerprint after the kernel's similarity transformation. You never compute it directly: it's a thinking tool.
  • $\mu$ (mu) is the average (mean) of a group of fingerprints.
  • $\lVert a \rVert^2$ is the squared length of vector $a$, a measure of "how big" it is. $\lVert a - b \rVert^2$ is then the squared distance between $a$ and $b$: small when they're close, large when far apart.
  • $\langle a, b \rangle$ is the dot product of $a$ and $b$ (the similarity measure from before). Crucially, $\langle \phi_s, \phi_t \rangle = K_{st}$, the dot product of two fingerprints is exactly the kernel-matrix entry.

Step 1: what "spread out" means

Take one segment covering frames $i, i+1, \dots, j$. Call its length $L = j - i + 1$ (the number of frames in it). Its average fingerprint is

$$ \mu = \frac{1}{L} \sum_{t=i}^{j} \phi_t. $$

(Add up the fingerprints in the segment, divide by how many there are, an ordinary average.)

The scatter of the segment is the total squared distance from each frame to that average:

$$ v(i, j) = \sum_{t=i}^{j} \lVert \phi_t - \mu \rVert^2. $$

In words: how far is each frame from the segment's "typical" frame, added up. A consistent segment → every frame near the average → small $v$. A jumbled segment → frames far from the average → large $v$. This single number is what KTS uses to grade a segment.

Step 2: rewrite it using only the kernel matrix

The problem: $\mu$ and $\phi_t$ live in an abstract space we can't compute in directly. The fix: expand the formula until only dot products $\langle \phi_s, \phi_t \rangle = K_{st}$ remain.

Expanding the squared distance (using $\lVert a-b\rVert^2 = \langle a,a\rangle - 2\langle a,b\rangle + \langle b,b\rangle$):

$$ v(i,j) = \sum_{t=i}^{j} \Big( \langle \phi_t, \phi_t \rangle - 2\langle \phi_t, \mu \rangle + \langle \mu, \mu \rangle \Big). $$

Now substitute $\mu = \frac{1}{L}\sum_s \phi_s$ and replace every $\langle \phi_s, \phi_t \rangle$ with $K_{st}$. The three pieces become:

  • $\displaystyle \sum_{t=i}^{j} \langle \phi_t, \phi_t \rangle = \sum_{t=i}^{j} K_{tt}$, the diagonal entries summed.
  • $\displaystyle \sum_{t=i}^{j} 2\langle \phi_t, \mu \rangle = \frac{2}{L}\sum_{t=i}^{j}\sum_{s=i}^{j} K_{st}$, twice the sum of the whole block, divided by $L$.
  • $\displaystyle \sum_{t=i}^{j} \langle \mu, \mu \rangle = \frac{1}{L}\sum_{s,t} K_{st}$, the block sum divided by $L$.

The last two combine, leaving the key formula:

$$ \boxed{\,v(i,j) = \sum_{t=i}^{j} K_{tt} \;-\; \frac{1}{L} \sum_{s=i}^{j}\sum_{t=i}^{j} K_{st}\,} $$

In plain words:

scatter = (sum of the diagonal entries for the segment) − (sum of the whole square block of $K$ for the segment, divided by its length).

No averages, no abstract fingerprints, just sums of numbers we already have in the grid $K$. That's the whole trick.

A worked example you can check by hand

Take two frames that are each a single number: $x_1 = 0$ and $x_2 = 0.2$, with the linear kernel (so this is just ordinary distance). The segment containing both has length $L = 2$ and average $\mu = (0 + 0.2)/2 = 0.1$.

Directly from the definition:

$$ v = (0 - 0.1)^2 + (0.2 - 0.1)^2 = 0.01 + 0.01 = 0.02. $$

In Chapter 4 we compute this segment's scatter with code and get the matching value 0.02. Two completely different routes (by hand and by computer), agree.

The total objective

A full segmentation with change points $t_1 < \dots < t_m$ (giving $m+1$ segments) is scored by adding up every segment's scatter:

$$ J = \sum_{r=0}^{m} v\big(t_r,\ t_{r+1}-1\big). $$

KTS chooses the cut positions that make $J$ as small as possible. Two cases:

  • You know how many segments you want → minimize $J$ directly with dynamic programming (Chapter 5).
  • You don't → add a penalty for extra cuts and let the computer pick (Chapter 6).

Why we'll precompute sums

Each $v(i,j)$ needs a sum over a block of $K$. Done naively for every possible segment, that's far too slow. The next chapter shows a trick (cumulative sums) that makes each scatter an instant lookup. First, let's write the code to build $K$. 👉