RKHS and Kernel Regression

Fit a curve through noisy samples using only how alike the points are. A kernel gives you n weights and a model with infinitely many features, from one solve.

Pick a kernel, then slide the smoothing and the width. Click the plot to add your own noisy point. Watch the same twelve samples turn into a line, a quartic, a smooth wave or a zigzag. Then we build it piece by piece: the Bayesian view of ridge and lasso, duality, the kernel trick, the function space behind it, and the sinc kernel that rebuilds a sampled signal.

You need least squares (fit a line by shrinking squared errors) and a little calculus. We build the rest from zero.

Based on the slides of Stanford EE269: Signal Processing for Machine Learning, taught by Mert Pilanci (this lecture’s slides, all decks). Every idea is re-taught here in our own words and devices.

Fit the signal

0.010
0.12

Illustrative: twelve samples of a made-up signal, 0.8 sin(3πx), plus seeded noise of 0.12. The fit solves c = (K + λI)−1y with the kernel you pick (Line is 1 + xy, Polynomial is (1 + xy)4, Gaussian is e−(x−y)2/2w2, Sobolev is min(x, y)). The error is measured against the true signal on 120 points.

Chapter 0

Why a Straight Line Is Not Enough

See why signals need curved models, and why the obvious way to build one runs out of memory

A temperature sensor logs one reading every ten minutes. By evening you have sixty noisy numbers. Your boss asks what the temperature was at 2:07 pm, between two readings.

You draw a straight line through the data. It misses the morning rise and the afternoon peak. The signal bends, and a line cannot bend. You need a model that bends, and you need it to stay stable when the readings are noisy.

This lecture is about that model. It is Mert Pilanci’s thirteenth lecture in the Stanford EE269 deck, given in February 2019. The course numbering on this site calls it lecture 21. The slides begin with the title card, so we start from the sensor.

Make the line bend by changing what it is made of

Here is the oldest trick. Keep the model linear, but feed it better inputs. A feature is a number computed from the input, such as x, x2 or sin(x). A feature map φ turns one input into a list of features.

The model then adds up the features with weights. If the features are 1, x, x2 and x3, the model is a cubic curve. It is still linear in the weights, so least squares still works. Only the inputs changed.

f(x)
The model’s answer for the input x, for example the temperature at 2:07 pm.
wT
The weights, one per feature, written as a row. The superscript T turns a column of weights into a row so it can multiply the features.
φ(x)
The feature map: the list of features computed from x. Its length is the number of weights you must learn.

Try it. The device fits the same sixteen noisy points with features 1, x, up to xd. Raise the degree and watch the line bend.

Bend the line with features

The blue dots are noisy samples of a curved signal. The orange curve is least squares on the features 1, x, up to x to the degree you choose. The bars on the right count the features if the input had 100 numbers instead of one.

1

Illustrative: sixteen points from the made-up signal 0.9 sin(3.2x) with seeded noise of 0.1, fitted by least squares with a tiny ridge of 10−8 so high degrees still solve. The count of features of degree up to d in p inputs is the binomial coefficient C(p + d, d); here p = 100.

The memory problem

One input is easy. A real signal has many inputs. A one-second audio clip at 8,000 samples per second is a point with 8,000 numbers. An image has thousands.

Polynomial features of degree d in p inputs number C(p + d, d). With 100 inputs and degree 4, that is about 4.6 million features. You must store a weight for each one, and the least-squares step inverts a table that is 4.6 million wide.

Now ask for the best features of all: a list that never ends. The bell-shaped Gaussian curve has such a list, because its Taylor series (a sum of powers of x) has infinitely many terms. No computer can store infinitely many weights.

The way out. You never need the features themselves. You only need how alike two inputs are, as one number. That number is a kernel. With it you store as many weights as you have samples, no matter how many features exist.

What this lecture answers

The slides build the answer in four steps. First, they show what ridge and lasso really assume about the world, using Bayes’ rule. Second, they use duality to rewrite ridge so that only similarities between samples appear. Third, they describe the huge space of curves that a kernel hides, a reproducing kernel Hilbert space (RKHS), and prove that the best curve always uses just n weights. Fourth, they study three kernels built for signals: the Gaussian, the Sobolev and the sinc.

The last of these closes a circle. The sinc kernel turns kernel regression into the sampling theorem you met in Lecture 2 and Lecture 6. It sits beside Lecture 19 on kernels, Lecture 20 on regression and ridge and Lecture 18 on duality, and we recall what we need from each.

The road

  1. Gaussian regression and ridge: a prior on the weights turns into a penalty.
  2. Laplace prior and lasso: a different prior makes weights exactly zero.
  3. Duality: rewrite ridge with one weight per sample.
  4. The kernel trick: replace dot products by a kernel and fit curves.
  5. Mercer and the RKHS: the curves a kernel can make, and a norm for them.
  6. The representer theorem: why n weights are always enough.
  7. The Gaussian kernel: Hermite waves and a smoothness penalty.
  8. Sobolev against polynomial: two kernels, one set of samples.
  9. The sinc kernel: bandlimited signals and Shannon interpolation.
  10. The Field Guide: numbers, checklist, code and links.

Counting the features

Count them in a small case first. Two inputs and degree 2 give six features: 1, x1, x2, x12, x22 and x1x2. That is C(4, 2) = 6. Degree 4 on the same two inputs gives C(6, 4) = 15.

Now take a real signal. Cut an audio clip into frames of 256 samples, so each frame is one input with 256 numbers. Degree 2 gives C(258, 2) = 33,153 features. Degree 3 gives C(259, 3) = 2,862,209. Degree 4 gives C(260, 4) = 186,043,585. The count grows by a factor between 65 and 86 at each step.

The failure, and the fix

The symptom of too many features is the opposite of the straight line. Raise the degree in the device above and the curve starts to pass through every dot, wiggling between them. The measurement is two errors. The error on the training dots keeps falling, while the error against the true signal turns around and rises. The fix is a penalty on how large the weights can grow, which the next two chapters derive, and a way to compute without the features, which Chapter 4 gives.

A model uses polynomial features of high degree on inputs with 100 numbers. What goes wrong if you build the features explicitly?

Chapter 1

Gaussian Regression and Why Ridge Works

Turn a belief about the weights into a penalty, and see ridge regression appear on its own

Four readings arrive from two sensors that sit side by side. Sensor A reads 1, 2, 3, 4 and sensor B reads 1.1, 1.9, 3.1, 3.9, so the two columns are nearly equal. The labels are 1.9, 4.2, 5.7, 8.3 (illustrative numbers). You fit a line with least squares, and it returns weights of +4.23 and −2.22.

The two weights cancel each other. The fit is fine on the data, but the weights are absurd. Change one reading slightly and they jump. You want a method that prefers small, sensible weights. Bayes’ rule gives you one, and it also tells you exactly how strongly to prefer them.

Every weight is a hypothesis

Treat a weight vector w as a guess about how the world works. Some guesses explain the data well and some do not. The first step is to say how the data would be made if a guess were true.

The slides use a Gaussian regression model. An input x is a list of d numbers and the label y is one real number. Given w, the label is the straight-line prediction plus bell-shaped noise:

p(y | x, w, b)
How likely the label y is, if the input is x and the guess is (w, b). The bar reads “given”.
N(mean, variance)
The Gaussian, or bell curve, with the stated centre and squared spread.
wTx + b
The straight-line prediction. The label is most likely to land here, and less likely the further it lands away.
σ2
The noise variance. A small value says the sensor is precise. A large one says the readings scatter widely.

The slide calls this “infinitely many classes parametrized by w”. Each value of w is its own small world that makes data a slightly different way.

From likelihood to a sum

We have n samples x1 to xn with labels y1 to yn. If the noise on each reading is independent, the chance of all the labels is the product of the chances of each one. That product is the likelihood of w.

You also hold a belief before you see any data. It is a probability P(w) over weight vectors, called the prior. Bayes’ rule multiplies the likelihood by the prior. The weight vector that makes this product largest is the maximum a posteriori estimate, or MAP.

  1. Multiply the chances: ∏ P(yi | xi, w, b) · P(w).
  2. Take the logarithm. It never moves the best w, and it turns the product into a sum.
  3. Maximise ∑ log P(yi | …) + log P(w).

Why take the logarithm? A product of a thousand small numbers underflows to zero in a computer. A sum of their logarithms does not. The best w is the same either way, because the log is an increasing function.

Choose a Gaussian prior, and ridge falls out

Now pick the prior. A natural belief is that weights are small and symmetric around zero. A Gaussian expresses that: P(w) = N(0, t2I). The number t says how far a weight is likely to stray from zero.

Take the log of each Gaussian. The noise term gives −(y − wTx − b)2 / 2σ2. The prior gives −‖w‖2 / 2t2. Maximising a negative is minimising its opposite, so the MAP estimate becomes

wMAP
The weights you keep: the most plausible guess after combining the data with your prior.
∑ (y − wTx − b)2
The squared errors on the training data. This is ordinary least squares.
σ2/t2
The price of a big weight. It is the noise variance divided by the prior variance, and it plays the role of λ in ridge regression.
‖w‖22
The sum of the squared weights. The subscript 2 marks the usual straight-line length, so this is the “ℓ2 penalty”.

This is ridge regression, or ℓ2 regularisation. The lecture’s point is that the penalty is not a trick. It is a belief about the weights written as a cost. The strength is not a free knob either: λ = σ2/t2.

Slide the prior against the data

One weight w, in the model y = w x. Top: the likelihood (blue), the prior (purple) and their product (orange). Bottom: the data and the two lines. Shrink the prior width t and watch the orange peak slide toward zero.

2.00
4

Illustrative: twelve seeded points from y = 1.5x plus noise, with the noise level σ = 0.5 known and b = 0. All three curves are scaled to the same height so they can share a plot. The orange peak is the closed form w = ∑xy / (∑x2 + σ2/t2).

A worked number

Take one weight and three samples, with inputs 1, 2, 3 and labels 1.2, 1.9, 3.4. Then ∑x2 = 14 and ∑xy = 1.2 + 3.8 + 10.2 = 15.2. Plain least squares gives w = 15.2 / 14 = 1.086.

Let the noise be σ = 0.5 and the prior t = 0.5. Then λ = 0.25 / 0.25 = 1, and wMAP = 15.2 / (14 + 1) = 1.013. Tighten the belief to t = 0.1. Then λ = 25 and wMAP = 15.2 / 39 = 0.390.

t = ∞: 1.086  →  t = 0.5: 1.013  →  t = 0.1: 0.390 (λ = 0, 1, 25)

A tight prior says “I am almost sure the weight is near zero”. The data has to shout to move it. A wide prior says “I know little”. The data decides, and you recover least squares.

The failure, and the fix

The symptom is the two-sensor fit from the start: least squares returns +4.23 and −2.22, and raising the first label by 0.3 moves the weights by −0.81 and +0.83. The measurement is the size of the weights, and their sensitivity to noise. The cause is that the two columns are nearly the same, so many pairs of weights fit equally well and the data cannot choose among them.

The fix is the prior. Ridge with λ = 1 returns 1.06 and 0.93 on the same data, and the same 0.3 change moves them by only −0.01 and +0.02. It splits the credit nearly evenly, which is what you believe when the sensors measure the same thing. Lecture 20 shows ridge in its matrix form.

You use a Gaussian prior with spread t on the weights and Gaussian noise with spread σ. What ridge penalty strength λ does MAP estimation give?

Chapter 2

A Different Belief: Laplace Prior and Lasso

Swap the bell curve for a pointed one, and see weights drop to exactly zero

An array has eight sensors. You suspect that only two of them carry the signal. The other six add noise. You want a model that says so, with six weights equal to zero, not six weights that are merely small.

Ridge cannot do that. It shrinks every weight a little and sets none of them to zero. The prior behind ridge is a Gaussian, and a Gaussian does not believe in exact zeros. To get zeros, change the belief.

The pointed prior

The Laplace distribution, also called the double exponential, has the density P(w) ∝ e−|w|/t. The vertical bars mean absolute value. Compare it with the Gaussian density e−w²/t². Both are symmetric humps around zero, but they differ in shape in two ways.

First, the Laplace has a sharp peak at zero, like a tent. The Gaussian is smooth and round at the top. Second, the Laplace has heavier tails. It gives more chance to a few large weights. The slide shows exactly this plot, with the Laplace density as the prior that lasso uses and the Gaussian as the prior that ridge uses.

Compare the two priors

Both curves have the same spread, so only the shape differs. Choose Density to see the tent and the bell. Choose Penalty to see what each prior charges for a weight: a V against a U.

0.40

Exact formulas: Laplace e−|w|/b / 2b has variance 2b2; the Gaussian drawn beside it has the same variance 2b2. The penalty view plots |w|/b and w2/4b2, the two negative logarithms without constants. The percentages are computed live.

From the pointed prior to the lasso

Run the same recipe as in Chapter 1. Take the log of the likelihood, add the log of the prior, and minimise the negative. For the Laplace prior, the negative log is ∑|wj|/t, the sum of absolute weights. Multiply through by 2σ2 to match the squared errors:

wMAP
The most plausible weights once you believe most weights sit exactly at zero.
∑ (y − wTx − b)2
The same squared errors as before.
2σ2/t
The strength of the penalty, again set by the noise and the prior together. It is the lecture’s λ.
‖w‖1
The sum of the absolute values of the weights. This is the “ℓ1 penalty”.

This is lasso, or ℓ1 regularisation. Slides 6 and 7 then write the two methods as plain optimisation problems, side by side: minimise ‖Xw − y‖22 + λ‖w‖22 for ridge, and the same with λ‖w‖1 for lasso. Here X stacks the samples as rows and y stacks the labels.

Why the corner makes zeros

Start with one weight, to see the mechanism. Suppose least squares alone would pick the value z. We minimise (w − z)2 plus a penalty.

  1. Ridge penalty λw². Setting the slope to zero gives 2(w − z) + 2λw = 0, so w = z / (1 + λ). The weight shrinks by a fixed factor and never reaches zero.
  2. Lasso penalty λ|w|. For w > 0 the slope is 2(w − z) + λ = 0, so w = z − λ/2. This only works if z > λ/2. Otherwise the best answer is w = 0.

So lasso soft-thresholds: it subtracts λ/2 from every weight and clips anything smaller to zero. The penalty has a corner at zero, and a small pull from the data cannot push the weight off that corner. Take z = 1.0 and λ = 0.6. Ridge gives 0.625 and lasso gives 0.7. Take z = 0.25. Ridge gives 0.156, and lasso gives exactly 0, because 0.25 is below 0.3.

z = 0.25, λ = 0.6: ridge 0.156  ·  lasso 0 (threshold λ/2 = 0.3)

The closed forms extend to many weights when the columns of X are at right angles and have length 1. Then every weight is its own one-weight problem. Take eight sensors whose least-squares weights are 2.0, 0.9, 0.25, −1.4, 0.1, −0.2, 0.05 and 0.5, and set λ = 0.6. Lasso subtracts 0.3 from the size of each and clips at zero. It returns 1.7, 0.6, 0, −1.1, 0, 0, 0 and 0.2: four sensors are switched off. Ridge divides every weight by 1.6. It returns 1.25, 0.56, 0.16, −0.88, 0.06, −0.13, 0.03 and 0.31, and keeps all eight.

With two or more weights the same corner idea works in a picture. The squared-error term is a family of ellipses around the least-squares answer. The penalty is a ball around zero: a circle for ridge, a diamond for lasso. The answer is where the smallest ellipse that you can afford first touches the ball.

Find where the ellipse meets the ball

Two weights, w1 across and w2 up. The blue dot is plain least squares. Raise λ and the orange answer slides in. Switch between ridge and lasso and watch which one lands on an axis.

1.50

Illustrative: the error is (w − w0)TA(w − w0) with w0 = (1.1, 0.45) and A = [[1, 0.6], [0.6, 1]]. Ridge solves (A + λI)w = Aw0 exactly; lasso uses coordinate descent with the soft-threshold from above, so a zero is exact.

The failure, and the fix

Lasso has a known weak spot. Suppose two sensors are near copies of each other and both are useful. The symptom: lasso keeps one and zeroes the other, and a new batch of data flips the choice. Measure it by refitting on resampled data and counting how often each sensor is kept. The fix is ridge, which splits the weight between the twins, or a blend of the two penalties. Both appear in practice.

One weight would be z = 0.25 under plain least squares. With a lasso penalty strength λ = 0.6 (threshold 0.3), what does the lasso return, and why?

Chapter 3

Duality: Ridge With One Weight per Sample

Rewrite ridge regression so the unknowns are samples, not features, and see that each one is a leftover error

You have recorded 200 clips of machine vibration. Each clip is turned into a spectrogram with 10,000 frequency bins. So n = 200 samples and d = 10,000 features. Ridge regression asks you to solve for 10,000 weights, which means inverting a table that is 10,000 by 10,000.

That is a hundred million numbers to store, and far more to compute with. Yet you only have 200 clips. It feels wasteful to hunt for 10,000 unknowns when the data has 200 rows. Duality gives a way to hunt for 200 unknowns instead, and the answer is the same.

The setup: ridge in matrix form

Stack the samples as the rows of a matrix X, with n rows and d columns. Stack the labels in a column y of length n. The slides rename the penalty so that it absorbs the sample count, and write ridge as

minw
Search over all weight vectors w and keep the one with the smallest total.
½‖Xw − y‖2
Half the sum of squared prediction errors. The vector Xw holds the model’s answers for all n samples at once.
(λ/2)‖w‖2
The ridge penalty. The half is only for tidy algebra later.

Step 1: name the predictions

Give the vector of predictions its own name, z = Xw. Now the problem has two sets of unknowns, z and w, joined by a rule they must obey. This is the equivalent constrained problem on the slide:

min over (z, w) with Xw = z: ½‖z − y‖2 + (λ/2)‖w‖2

Step 2: price the rule

A Lagrange multiplier is a price you charge for breaking a rule. Charge a price αi for each unit by which prediction zi differs from xiTw. The total cost is the Lagrangian:

L(z, w, α) = ½‖z − y‖2 + (λ/2)‖w‖2 + αT(z − Xw)

For fixed prices α, minimise over z and w by setting each slope to zero. This is the dual step, and it is the heart of the chapter.

  1. Slope in w: λw − XTα = 0, so w = XTα / λ.
  2. Slope in z: (z − y) + α = 0, so z = y − α.
  3. Substitute both back. The cost becomes ½‖α‖2 + (1/2λ)‖XTα‖2 + αT(y − α − XXTα/λ).
  4. Collect terms. This simplifies to −αT(XXT/2λ + I/2)α + αTy.

That last line is the dual problem on slide 9. You maximise it over α, because the right prices push the lower bound on the cost as high as it can go. It is a smooth bowl in α, so set its slope to zero: (XXT/λ + I)α = y. The closed form is

α*
The best prices, one per sample. This is a vector of length n, not d.
XXT
An n by n table. Entry (i, j) is the dot product of sample i with sample j. Remember this table: it becomes the kernel matrix.
w* = XTα*/λ
The weights are a weighted sum of the training samples, with the prices as the weights. This is the slide’s KKT condition. The KKT conditions are the slope-zero equations above.

Because the problem is convex and the rule is linear, the dual has the same best value as the original. This is strong duality, the subject of Lecture 18.

What a price means

Look at step 2 again. It said z = y − α, and z = Xw is the model’s prediction. So α = y − Xw*: each price is the model’s leftover error on that sample. The weight vector is a sum of the samples, each scaled by how badly the model still misses it. Samples the model already fits get a price near zero and barely matter.

A worked number

Take n = 2 samples with one feature each: X = [[1], [2]], y = [1, 3] and λ = 1. The primal route needs one number: w = (XTX + λ)−1XTy = 7/6 = 1.167.

The dual route inverts a 2 by 2 table. XXT = [[1, 2], [2, 4]], so XXT + I = [[2, 2], [2, 5]], with determinant 6. Then α = (1/6)[5·1 − 2·3, −2·1 + 2·3] = [−0.167, 0.667]. Recover w = 1·(−0.167) + 2·0.667 = 1.167. The two routes agree. The residuals are 1 − 1.167 = −0.167 and 3 − 2.333 = 0.667, which are exactly α.

Pick the cheaper side

The squares are the two tables you could invert: d by d (features) or n by n (samples). The bars are the rough cost of each solve, on a log scale. Drag n and d. Then press the button to check that both routes find the same weights.

200
10,000

Illustrative costs: the feature side costs about n·d2 + d3 multiply-adds (form XTX, then solve); the sample side costs about n2·d + n3. The check button draws a seeded random 8 by 5 problem, solves both exactly in your browser, and prints the largest difference.

The failure, and the fix

The symptom is a job that never finishes, or runs out of memory, before it solves anything. The measurement is the size of the table. With a million samples, the sample table has a trillion entries; with ten thousand features, the feature table has a hundred million. The fix is to solve on whichever side is smaller. Both give identical weights, so the choice is only about cost.

In dual ridge regression, what does the price αi of sample i equal at the solution?

Chapter 4

The Kernel Trick: Fit Curves From Similarities

Replace every dot product with a kernel, and fit a bending curve with one weight per sample

Look again at the table XXT from the last chapter. Entry (i, j) is the dot product of sample i with sample j. A dot product multiplies two lists of numbers entry by entry and adds the results. It is large when the two samples point the same way, so you can read it as a score of how alike they are.

Now ask what the dual solution really uses. Look at the formulas on slide 10. The weights are w* = XTα*/λ. The prediction for a new sample x is

w*Tx
The model’s answer for the new input x.
(1/λ) ∑
Add up one term for each of the n training samples, then divide by λ.
⟨xi, x⟩
How alike training sample i is to the new input, as a dot product.
αi*
The price of sample i from Chapter 3: how much it still matters.

The data only ever appears inside dot products. Neither the training step nor the prediction needs the numbers of any sample on their own, only how alike pairs of samples are.

Swap the similarity

Here is the trick. First lift each sample with a feature map Φ, as in Chapter 0. Then the dual solution needs the dot products of the lifted samples, ⟨Φ(xi), Φ(xj)⟩. Call this number a kernel, κ(x, y). The kernel matrix (also called the Gram matrix) K collects it for every pair of training samples.

The dual formulas then read, word for word as on the slide: α* = (K/λ + I)−1y, and the prediction is (1/λ)∑ κ(xi, x)αi*. Fold the 1/λ into the prices by writing c = α*/λ. Then the whole method is two lines:

  1. Train. Build K, an n × n table with Kij = κ(xi, xj). Solve (K + λI)c = y for the vector c, of length n.
  2. Predict. For a new x, compute f(x) = ∑i ci κ(xi, x). That is n kernel values, one weighted sum.

Nowhere do you compute Φ. The kernel is a shortcut for the dot product of two lifted points, and it can cost far less than lifting them.

Check the shortcut with real numbers

Take two inputs with two numbers each and the kernel κ(x, y) = (1 + xTy)2. Multiply it out and you find six features: Φ(x) = (1, √2x1, √2x2, x12, x22, √2x1x2). Take x = (1, 2) and y = (3, 1). Then xTy = 5 and the kernel gives (1 + 5)2 = 36. Now compute the six products: 1, 6, 4, 9, 4 and 12. They sum to 36.

(1 + xTy)2 = 36  =  1 + 6 + 4 + 9 + 4 + 12 (the six feature products)

Check the kernel against its features

Move the two points. Each bar is one of the six feature products. Their sum always equals the kernel value, which costs one dot product and one square.

1.0
2.0
3.0
1.0

Exact: the six features of (1 + xTy)2 in two inputs are 1, √2x1, √2x2, x12, x22, √2x1x2. For degree d in p inputs there are C(p + d, d) features; the slide’s degree 4 with p = 100 gives about 4.6 million, yet the kernel still costs about p multiplications.

Kernel regression at work

Slides 11 and 12 show the method with two kernels. The polynomial kernel κ(x, y) = (1 + xTy)4 fits a curve made of powers up to the fourth. The Gaussian kernel κ(x, y) = e−‖x−y‖²/2σ² is 1 when two points coincide and falls toward 0 as they move apart. The width σ sets how far “alike” reaches.

Work a tiny case with the Gaussian kernel at σ = 1 and λ = 0.1. Two samples sit at x = 0 and x = 1 with labels 1 and 0. Their similarity is e−1/2 = 0.607, so K = [[1, 0.607], [0.607, 1]]. Solve (K + 0.1I)c = y to get c = (1.306, −0.720).

Predict. At x = 0: 1.306 · 1 − 0.720 · 0.607 = 0.869. At x = 1: 1.306 · 0.607 − 0.720 = 0.072. At x = 0.5 both bumps reach 0.5 away with height e−1/8 = 0.882, so f = (1.306 − 0.720) · 0.882 = 0.517. The curve starts near 1, ends near 0 and passes smoothly between. Each ci scales a bump centred on sample i.

See the fit as a sum of bumps

Pink curves are the bumps ciκ(xi, ·), one per sample, centred on the samples. The orange curve is their sum. Switch kernels, then move the smoothing and the width.

0.032
0.15

Illustrative: eight seeded samples of 0.8 sin(3πx) plus noise of 0.1 on [0, 1]. The weights come from c = (K + λI)−1y, solved in your browser. The polynomial bumps are large and cancel one another, so the plot clips them to the frame.

The failure, and the fix

The symptom: with a very narrow Gaussian the fit passes through every point and sags to zero between them. The measurement is the width against the spacing of the samples, here about 0.125 apart. If σ is far smaller than the spacing, each bump is an isolated spike. The fix is a wider σ or a larger λ, or both. Later chapters explain what each one controls inside the function space.

You train kernel ridge regression on n = 500 samples. How many numbers does the trained model store, and what does a prediction cost?

Chapter 5

Mercer and the Space Behind the Kernel

Open the kernel into waves, and build a ruler that charges more for rough curves

Every kernel fit in Chapter 4 was a sum of bumps. But what is the full set of curves a kernel could produce, if you used every possible sample? That set is a space of functions. Its shape decides which curves are cheap and which are costly, and so what the fit prefers.

Think of a guitar string. A plucked string vibrates as a mix of a few pure modes: a fundamental, then higher overtones. Each mode has its own loudness in the mix. The kernel has modes too, and this chapter finds them.

Eigenvectors and eigenfunctions, from zero

A square table K acts on a list of numbers by multiplying. Most lists get turned and stretched in a messy way. An eigenvector is a special list that the table only stretches, without turning. The stretch factor is its eigenvalue. A symmetric table has a full set of eigenvectors that are at right angles to each other.

A kernel is a table with a continuum of rows and columns, one for each point. Its eigenvectors become curves, called eigenfunctions. A kernel is positive definite when all its eigenvalues are positive, which is what you need for the dual problem to be a bowl with a single bottom.

Mercer’s theorem

The slides state Mercer’s theorem: any positive definite kernel splits into its modes,

κ(x, y)
The kernel: how alike the two points x and y are.
∑i=1∞
Add up infinitely many modes. For the Gaussian kernel the tail of the list is tiny, so a handful of modes already does most of the work.
λi
The eigenvalue of mode i: how loud this mode is in the kernel. These are positive and shrink as i grows.
φi(x)φi(y)
Mode i read at the two points. The modes are orthonormal: each has size 1, and no two overlap.

This is the same idea as an eigen-decomposition of a matrix, only with curves in place of lists. The kernel does not even need to be a Gaussian. On a circle, any kernel that depends only on the gap between two points has sines and cosines as modes, which is the Fourier basis of Lecture 6. Its eigenvalues are then the kernel’s strength at each frequency.

The space of curves, and its price tag

Use the modes as building blocks. Every curve in the space is a mix, f(x) = ∑ fiφi(x), with fi the amount of mode i. The slide defines the reproducing kernel Hilbert space (RKHS) as the mixes whose total price is finite:

Hκ = { f = ∑ fiφi : ∑ fi2 / λi < ∞ }

A Hilbert space is a space of vectors, here curves, where you can take lengths and angles with an inner product. Slide 15 gives the inner product of two curves f and g built from the same modes: ⟨f, g⟩ = ∑ figi / λi. The squared length of one curve is its norm, ‖f‖2 = ∑ fi2 / λi.

Read that division carefully. A mode with a small eigenvalue has a large 1/λi. The same amount of a rough, fast-wiggling mode costs far more than the same amount of a smooth one. The norm is a ruler that charges more for roughness.

A worked toy: let κ = 2φ1(x)φ1(y) + 0.5φ2(x)φ2(y). The curve f = φ1 has norm2 1/2 = 0.5. The curve g = φ2 has the same size but norm2 1/0.5 = 2. The rough one costs four times as much.

The reproducing property

Now the name. Fix a point x and view κ(x, ·) as a curve in its own right. By Mercer it equals ∑ λiφi(x) φi(·), so its mode amounts are λiφi(x). Take its inner product with any curve f:

  1. Write the inner product: ⟨f, κ(x, ·)⟩ = ∑ fi · (λiφi(x)) / λi.
  2. Cancel λi. It appears above and below.
  3. What remains is ∑ fiφi(x), which is exactly f(x).

So taking an inner product with κ(x, ·) reproduces the value of f at x. Put f = κ(y, ·) and you get the slide’s identity, ⟨κ(x, ·), κ(y, ·)⟩ = κ(x, y). Looking up a value becomes an inner product, a tool we use in the next chapter.

Mix modes and pay the norm

The five sliders set how much of each mode a curve uses. Top: the curve (orange) and its parts (pink). Bottom: the price of each part, fi2/λi. Equal amounts of rougher modes cost more. Move the point x to check the reproducing property.

0.80
0.40
0.00
0.00
0.00
0.30

Computed live: the Gaussian kernel of width 0.25 on [0, 1] is sampled on 48 points, and a Jacobi eigen-solver finds its modes (eigenvalues scaled so each mode has unit size on the interval). The reproducing check uses the first five modes only, where it holds exactly.

The failure, and the fix

A common slip is to measure a curve’s size by how tall it is. The symptom: two curves with the same peak height give very different fits when used as the penalty. The measurement is the norm, which includes the division by λi. The fix is to use ‖f‖H, not the height, when you ask how complex a curve is. Height says how large. The norm says how rough.

Two curves each use one unit of a single mode. Mode A has eigenvalue 0.2 and mode B has eigenvalue 0.01. What does the RKHS norm say?

Chapter 6

The Representer Theorem: Why n Weights Are Enough

Prove that the best curve in an infinite space is always a sum of n bumps, one per sample

Chapter 4 handed you a recipe: fit a sum of n bumps. But the RKHS from Chapter 5 holds curves of every shape. A better curve might hide outside the span of the bumps. Why should the best fit be a sum of bumps at all?

This is the question the representer theorem answers. Picture a lamp above a flat floor. Any object has a shadow on the floor and a height above it. The floor is the set of sums of bumps. Every curve in the space splits into its shadow on that floor and its height above it.

What we want to minimise

Over all curves f in the RKHS, the slides minimise the training error plus a penalty on the norm from Chapter 5:

min over f in H
Search over every curve in the space, which has infinitely many dimensions.
∑ (f(xi) − yi)2
The data term. It looks at the curve only at the n training points.
λ‖f‖2
The roughness price from Chapter 5, scaled by λ. It looks at the whole curve.

The theorem says the winner has the form f*(x) = ∑i=1n αiκ(x, xi): a sum of n bumps, one centred on each sample. An infinite search shrinks to n numbers.

The proof, in four short steps

  1. Split. Write any curve as f = f∥ + f⊥. The first part is a sum of bumps (the shadow). The second part is at right angles to every bump κ(xi, ·) (the height). At right angles means the inner product with each bump is zero.
  2. The data cannot see the height. By the reproducing property, f(xi) = ⟨f, κ(xi, ·)⟩ = ⟨f∥, κ(xi, ·)⟩ + 0. So f and its shadow give the same value at every training point, and the same data term.
  3. The penalty can. Parts at right angles obey Pythagoras: ‖f‖2 = ‖f∥‖2 + ‖f⊥‖2. So the height only adds cost.
  4. Throw the height away. The shadow has the same data term and a smaller or equal penalty. The best curve therefore has no height, and it is a sum of bumps. ■

The proof uses the reproducing property from the last chapter in a deep way. That property is what turns “the value at xi” into an inner product that the height cannot affect.

Try to cheat with a hidden part

The orange curve is the best fit through four blue points. Add the part that vanishes at all four points (teal curve) and slide its size s. The curve moves between the points but not on them. Watch the total cost below.

1.60
0.25

Illustrative: Gaussian kernel of width 0.2, λ = 0.3, four points. The hidden part is h(x) = κ(z, x) − ∑βiκ(xi, x) with β = K−1κz, which is exactly zero at each xi and has squared norm κ(z, z) − κzTK−1κz. The cost is J(s) = J* + λs2‖h‖2.

Plug in the bumps

Now we only need to search over the n numbers α. Write f = ∑j αjκ(·, xj) and use the reproducing property to find each piece:

  1. Values at the data: f(xi) = ∑j αjκ(xi, xj) = (Kα)i. The data term becomes ‖Kα − y‖2.
  2. The norm: ‖f‖2 = ∑i,j αiαj⟨κ(xi, ·), κ(xj, ·)⟩ = ∑i,j αiαjκ(xi, xj) = αTKα.
  3. The problem: minimise ‖Kα − y‖2 + λαTKα, a smooth bowl in n unknowns.
  4. Set the slope to zero: 2K(Kα − y) + 2λKα = 0, that is K[(K + λI)α − y] = 0. So α* = (K + λI)−1y.

The prediction is f(x) = ∑ αi*κ(x, xi). This is exactly the rule that Chapter 4 found by duality, as slide 18 notes. Two routes, one answer: duality got there with algebra, and the representer theorem got there by geometry.

A worked number

Reuse the two samples from Chapter 4: K = [[1, 0.607], [0.607, 1]], λ = 0.1, y = (1, 0). We found α* = (1.306, −0.720). Then Kα* = (0.869, 0.072), so the data term is (−0.131)2 + 0.0722 = 0.0224. The norm is αTKα = 1.306 · 0.869 + (−0.720) · 0.072 = 1.083, so the penalty is 0.108. The total is about 0.131. Any other curve, including any with a hidden part, costs more.

The failure, and the fix

The symptom people hit is a surprise: the fitted curve wanders between samples, for example by making a bump where no sample sits. The measurement is the weights α. They may be large and of opposite signs, and their norm αTKα is large. The theorem guarantees only the form of the answer, not that the answer is good. If the weights are large, raise λ or widen the kernel.

In the proof, why can the part f⊥ be dropped without hurting the fit to the training data?

Chapter 7

The Gaussian Kernel: Hermite Waves and a Smoothness Penalty

Meet the modes of the most popular kernel, and see the penalty favour smooth waves

You tune a vibration sensor model and pick the Gaussian kernel, as most people do. You try three widths. One fit is a flat blur that misses the signal. One is a spiky mess that chases every noisy reading. One looks right. The width σ changed nothing about the data. It changed which curves the kernel can afford.

The lecture opens the Gaussian kernel with Mercer’s theorem to show exactly what σ does. It is the best-studied case, and the one place where the modes have a closed form.

The modes of the Gaussian kernel

The Gaussian kernel is κ(x, y) = e−‖x−y‖²/2σ². Slide 19 gives its modes. Each is a bell curve multiplied by a Hermite polynomial Hi: φi(x) ∝ e−(c−a)x² Hi(x√2c). The numbers a, b and c are set by σ, and the eigenvalues are λi = bi. This closed form is the standard result for inputs that follow a Gaussian distribution.

The slide plots the first three modes. Mode 0 is a single bell. Mode 1 is one swing up and one down, crossing zero once. Mode 2 crosses zero twice. The index counts the wiggles. Each higher mode is a faster oscillation, like the overtones of the guitar string.

The eigenvalues are bi with b less than 1. They shrink by the same factor at each step, so the loudness drops geometrically. Suppose b = 0.4, for illustration. Then λ = 1, 0.4, 0.16, 0.064, 0.026 for modes 0 to 4.

Meet the modes

Pick a mode to see its shape. The bars show the first eight eigenvalues on a log scale. Widen the kernel and the eigenvalues fall faster, so fewer wiggles are affordable.

0.20

Computed live on [0, 1] with a uniform input distribution, so the numbers are close to, but not the same as, the slide’s Hermite form for Gaussian inputs. The shapes and the geometric fall-off are the same story. Modes are labelled from 1 here, so mode 1 is the slide’s mode 0.

The fit, written in modes

Slide 20 rewrites the kernel fit with Mercer’s sum. Start from the sum of bumps, f(x) = ∑i αiκ(xi, x), and expand each bump into modes:

  1. Expand the kernel: f(x) = ∑i αi ∑j λjφj(xi)φj(x).
  2. Swap the sums: f(x) = ∑j [λj ∑i αiφj(xi)] φj(x).
  3. Read off the amount of mode j: fj = λj ∑i αiφj(xi).

So the fit is a mix of the Hermite-like waves, with n weights deciding all the amounts. (The slide folds a factor √λj into its basis; the maths is the same.) The data fixes how the amounts must look near the samples, and the penalty chooses how to spend the rest.

The penalty favours smooth waves

For any curve h = ∑ hiφi, the slide writes the norm as ‖h‖H2 = ∑ hi2/λi. It adds that this “enforces smoothness by penalising rough eigenfunctions (small λi)”. Now the geometric fall-off pays off. With b = 0.4, one unit of mode 3 costs 1/0.064 = 15.6, against 1 for mode 0. Spending the same amount on a rough wave costs sixteen times as much.

The ridge penalty λ‖f‖2 then pushes the fit toward the first few modes. A narrow kernel lets the eigenvalues stay large for many modes, so many wiggles are cheap and the fit can chase noise. A wide kernel makes them collapse quickly, and only a few smooth waves are affordable.

The width is a low-pass filter

There is a signal-processing way to read σ. The Fourier transform of a Gaussian bump is another Gaussian bump, with width 1/σ. In frequency the kernel’s strength falls as e−σ²ω²/2 at angular frequency ω. A wide kernel in time is a narrow one in frequency, which makes the kernel a low-pass filter whose cutoff drops as the width grows.

Put numbers on it at ω = 20 radians per unit. With σ = 0.1 the kernel keeps e−2 = 13.5% of its strength at that frequency, so fast wiggles stay affordable. With σ = 0.5 it keeps e−50, about 2 × 10−22. The norm divides by that strength, so a wiggle at 20 radians costs an astronomical amount. That is the smoothness penalty in the language of Lecture 6.

Underfit, fit and overfit

Nine noisy samples, three kernel widths. The dashed green line is the truth. The bars show which modes carry the fit’s norm. Switch the width and watch the error against the truth, not just against the dots.

0.0032

Illustrative: nine seeded samples of 0.8 sin(3πx) with noise 0.12. The error against the truth is measured on 120 points. The mode shares use the live eigen-modes of the chosen kernel on [0, 1] and the norm cTKc of the fit.

The failure, and the fix

The symptom is the narrow fit: it touches every dot, and between them it jumps. The measurement is a gap between two errors. The error on the dots is tiny, and the error against the truth is large. The fix is to widen the kernel or raise λ. Choose them by testing on points the fit never saw, so that you trust the second error and not the first.

Which statement about the Gaussian kernel’s modes and the RKHS norm is correct?

Chapter 8

Sobolev Against Polynomial: Two Kernels, One Set of Samples

Learn a kernel whose norm is the energy of the slope, and see why it fits sampled signals gently

A sensor ramps up and then saturates. You have eleven readings along the ramp, equally spaced. You want a curve that passes through every reading and behaves between them. Which kernel should you use?

The answer depends on what the kernel’s norm measures. Chapter 5 said the norm is the price of roughness. For the Gaussian, the price is hidden inside the Hermite modes. Now we meet a kernel whose price you can write in one line, and read in plain words.

The Sobolev space

A Sobolev space collects curves by how much their slope varies. The slide takes curves on [0, 1] that start at zero, f(0) = 0, and that are absolutely continuous. That phrase means the slope f′(t) exists almost everywhere, and the curve is the running total of its slope. The space allows corners. It is

Hκ
The space of allowed curves. It is an RKHS with the kernel κ(x, y) = min(x, y).
f(0) = 0
Every curve starts at zero. This pins the curve down, so the slope alone fixes its shape.
∫ |f′|2
The squared slope, added up along the curve. Call it the slope energy. This is the squared norm of the curve.

So the norm of a curve is its slope energy. A curve that drifts gently has low energy. A curve that swings up and down has high energy, even if it is not tall.

Why min(x, y) is the kernel

Check the reproducing property from Chapter 5. The bump κ(x, ·) = min(x, ·) rises with slope 1 until it reaches x, and then stays flat. Its slope is 1 for t < x and 0 after. The inner product in this space multiplies slopes: ⟨f, g⟩ = ∫ f′g′.

  1. Take the inner product: ⟨f, min(x, ·)⟩ = ∫01 f′(t) · (1 for t < x, 0 after) dt.
  2. The indicator keeps only [0, x]: the integral is ∫0x f′(t) dt.
  3. Running total of slope: that equals f(x) − f(0) = f(x).

It reproduces the value, so min(x, y) is the kernel. The condition f(0) = 0 is what removes the leftover term.

What the Sobolev fit looks like

Ask for the curve with least slope energy that passes through given points. A straight segment between two points has the least energy of any path, because any detour must climb more and so spends more slope. So the interpolant is a broken line, straight between samples, starting at (0, 0). After the last sample it stays flat, since slope there only costs energy.

A worked check. Take two samples, (0.5, 1) and (1, 0). The broken line goes up with slope 2 for 0.5 and down with slope −2 for 0.5. Its energy is 4 × 0.5 + 4 × 0.5 = 4. A smooth parabola through the same points, 4x(1 − x), has slope 4 − 8x, and ∫(4 − 8x)2 dx = 16 − 32 + 21.33 = 5.33. The broken line is cheaper, as promised.

broken line: energy 4  <  parabola 4x(1 − x): energy 5.33 (same two samples)

Here is the proof that the broken line wins. Between two samples the curve rises by Δy over a gap Δx. By the Cauchy-Schwarz inequality, (∫ f′)2 is at most Δx times ∫ f′2. The left side is Δy2, so the energy on that stretch is at least Δy2/Δx, and a constant slope reaches it. For the segment from (0, 0) to (0.5, 1) that floor is 12/0.5 = 2, which matches the energy we counted above.

The caption of slide 23 calls this kernel first order, because it penalises the first derivative. Penalise the second derivative instead and the cheapest interpolant becomes a cubic spline, a smoother curve with no corners. The same recipe gives a family of kernels, one for each notion of smoothness.

The polynomial kernel has no such story. Its norm, written in the powers 1, x, x2 and so on, charges each power by its own coefficient, with no regard for how the curve behaves between samples. Slide 23 puts the two side by side on eleven equally spaced samples, and the polynomial interpolant wanders away from the samples while the Sobolev one stays close.

Interpolate the same samples

The dashed green line is a sensor ramp. The dots are samples of it. Switch the kernel, then change how many samples you take. Watch the slope energy and the largest miss between samples.

11

Illustrative: the ramp is 1/(1 + e−12(x−0.5)) sampled at x = i/n, with a tiny ridge of 10−9 so the exact interpolation can be solved. The slide uses its own eleven samples. The slope energy is ∫|f′|2 computed on 400 points. The Sobolev curve is forced through 0 at x = 0, as the space requires.

The failure, and the fix

The symptom of a poor kernel is a curve that strays between samples, with wiggles that the signal does not have. The measurement is the largest miss between the samples, and the slope energy. A polynomial of degree 10 through the samples can sit 0.3 or more away from a ramp that only rises by 1. The fix is to choose a kernel whose norm matches the smoothness you believe the signal has. For a ramp, the slope energy is the right ruler.

For the Sobolev kernel min(x, y), what is the squared norm of a curve, and what is the cheapest curve through a few samples?

Chapter 9

The Sinc Kernel: Bandlimited Signals and Shannon Interpolation

See that the sampling theorem you know is kernel regression with a kernel made of sinc waves

A microphone takes 8,000 readings per second. Later a speaker must turn those readings back into a smooth sound, drawing a continuous curve through numbers that came one at a time. How should it fill the gaps?

You have met the answer before, in the sampling theorem from Lecture 2 on discrete signals. The last three slides of this lecture show that the answer is also kernel regression. The kernel is the sinc function.

Bandlimited signals

A bandlimited signal has no frequencies above some limit. Slide 25 names the set of such functions. Slide 24 calls the space of bandlimited functions the Paley-Wiener space. The slide’s kernel for it is

κ(x, y)
How alike two time points are. It depends only on their gap, so it is the same everywhere along the signal.
sinc(α(x − y))
The sinc bump: 1 when the points coincide, then a decaying ripple that crosses zero again and again.
sin(u) / u, with u = α(x − y)
The explicit formula. The number α is the band limit, in radians per unit time. A bigger α gives a narrower bump.

This kernel is the shift-invariant case from Chapter 5, so its modes are sines and cosines. Every frequency up to α has the same eigenvalue, and every frequency above α is excluded. The norm of a bandlimited curve is, up to a constant, its signal energy. So the sinc kernel says: any slow wave is equally cheap and any wave faster than α is forbidden. It is an ideal low-pass filter turned into a prior.

The Shannon-Whittaker formula

Now sample at times nT and call the samples x[n] = x(nT). Slide 26 recalls the Shannon-Whittaker interpolation formula:

x(t) = ∑n x[n] · sinc((t − nT) / T)   (here sinc(u) = sin(πu) / (πu))

Each sample sends out a sinc bump centred on its own time, scaled by its own value. The sum of the bumps rebuilds the curve exactly, if the signal has no frequency above 1/(2T) hertz. That limit is the Nyquist frequency. Sampling at fs = 1/T samples per second means the Nyquist frequency is fs/2.

See why it equals kernel regression. Choose the band limit α = π/T, which is the Nyquist limit in radians. The kernel between two sample times is sinc(π(i − j)), since the gap is (i − j)T. A sine at a whole multiple of π is zero, so this is 0 when i ≠ j and 1 when i = j. The Gram matrix is the identity.

  1. Gram matrix: K = I, because the sinc bumps are zero at every other sample.
  2. Weights: c = (K + λI)−1y = y/(1 + λ). With λ = 0 the weights are the samples themselves.
  3. Fit: f(t) = ∑n cn sinc((t − nT)/T). That is the Shannon formula.

So Shannon interpolation is kernel regression with the sinc kernel, placed on a uniform grid at the Nyquist limit and with no smoothing. The kernel view also does more. It handles samples at uneven times, and it handles noise through λ.

Rebuild a signal from its samples

The dashed green line is a two-tone signal. The dots are samples at the rate you set. The orange curve is the sum of sinc bumps, one per sample. Raise the top tone, or lower the sampling rate, until the curve stops matching.

4.0 Hz
20.0 Hz

Illustrative: x(t) = sin(2πFt) + 0.5 sin(2π(0.45F)t + 0.6). Samples run from t = −3 to 5 s so the middle of the plot has no edge effects; only 0 to 2 s is drawn, and the error is measured from 0.5 to 1.5 s. The alias frequency is |F − k·fs| for the nearest whole k.

Sampling rates in practice

The Nyquist limit is half the rate. Telephone speech is sampled at 8,000 Hz, so it keeps frequencies up to 4,000 Hz, which covers the band of speech that a phone line carries. A compact disc samples at 44,100 Hz and keeps up to 22,050 Hz, a little above the range of human hearing. In both cases an analogue filter removes anything higher before the sampler sees it.

One practical note. The sinc bump decays slowly, like 1/t, so a sample far away still moves the curve a little. A finite stretch of samples therefore rebuilds the middle of the signal well and the two ends less well. The device samples beyond the plotted window for this reason.

The kernel view with uneven, noisy samples

Real sensors miss samples and add noise. Use the sinc kernel and the ridge solution from Chapter 4. Pick a band limit α at least as large as the signal’s top frequency, and the bumps can build the signal from samples at any times. Pick α too small, and the space cannot contain the signal. Pick it far too large, and the space is roomy enough to chase the noise.

Choose the band limit

Sixteen uneven noisy samples of a signal whose top frequency is 7 radians per second. Move α below, near and above 7 and compare the fit with the truth.

8.00
0.032

Illustrative: g(t) = sin(4t) + 0.6 sin(7t + 0.5) on [0, 6], sixteen seeded uneven sample times, noise 0.1. The fit is c = (K + λI)−1y with Kij = sin(α(ti − tj)) / (α(ti − tj)). The error is measured from t = 0.3 to 5.7.

The failure, and the fix

The symptom is aliasing: the rebuilt wave has a tone that was never in the original, and it is slower than the real one. The measurement is the alias frequency |F − k·fs|. A 9 Hz tone sampled at 12 Hz comes back as 3 Hz, because the samples of the two tones are identical. No interpolation can tell them apart afterwards. The fix has to come before sampling: raise the rate above twice the top frequency, or filter the signal first so the top tone is gone.

A 9 Hz tone is sampled at 12 Hz, and the samples are rebuilt with sinc bumps. What comes out, and why?

Chapter 10

The Field Guide

Review the lecture on one page: the numbers, the checklist, the code, and where to go next

You can now rebuild this lecture from memory. It is Mert Pilanci’s thirteenth deck in EE269, given on February 27, 2019, and it lists no assignments or readings on its slides. The one thread that runs through it is this: a penalty is a belief, a kernel is a similarity, and the right function space turns an infinite search into n weights.

The one-paragraph summary

Ridge and lasso are maximum a posteriori estimates under a Gaussian and a Laplace prior. Duality rewrites ridge so the unknowns are one price per sample, and each price is that sample’s leftover error. Because the data then appears only in dot products, you can swap them for a kernel and fit curves with infinitely many features. Mercer’s theorem opens the kernel into modes, and the RKHS norm charges more for rough modes. The representer theorem then proves that the best curve is a sum of n bumps. The Gaussian, Sobolev and sinc kernels are three priors about smoothness, and the sinc kernel turns kernel regression into Shannon interpolation.

The numbers and the terms

IdeaThe formula or numberChapter
Ridge from a Gaussian priorλ = σ2/t2; worked: 1.086 → 1.013 → 0.3901
Lasso from a Laplace priorλ = 2σ2/t; soft threshold λ/2; 0.25 → 02
Dual ridgeα* = (XXT/λ + I)−1y, w* = XTα*/λ, α* = y − Xw*3
Kernel ridgec = (K + λI)−1y, f(x) = ∑ ciκ(xi, x); n weights4
Polynomial kernel(1 + xTy)4; C(p + d, d) features, about 4.6 million at p = 1004
Gaussian kernele−‖x−y‖²/2σ²; infinitely many features; eigenvalues λi = bi7
Mercer’s theoremκ(x, y) = ∑ λiφi(x)φi(y)5
RKHS norm‖f‖2 = ∑ fi2/λi; mode with λ = 0.01 costs 100 per unit25
Reproducing property⟨f, κ(x, ·)⟩ = f(x); ⟨κ(x, ·), κ(y, ·)⟩ = κ(x, y)5
Representer theoremf* = ∑ αiκ(·, xi), α = (K + λI)−1y; cost J = ‖Kα − y‖² + λαTKα6
Sobolev kernelκ = min(x, y); ‖f‖² = ∫|f′|²; interpolant is a broken line8
Sinc kernelκ = sin(αd)/(αd); α = π/T gives K = I and Shannon interpolation; Nyquist fs/29

The checklist

  1. Say the belief. Name the prior behind your penalty: Gaussian for ridge, Laplace for lasso.
  2. Pick the smaller side. Solve on features if d < n, on samples if n < d.
  3. Choose the kernel by its norm. Ask what the kernel charges for: wiggles (Gaussian), slope energy (Sobolev), frequency above a limit (sinc).
  4. Set the width and λ on held-out points. Trust the error away from the samples.
  5. Check the cost. Training solves an n by n system. Each prediction needs n kernel values.
  6. For a sampled signal, filter before sampling and keep tones below half the rate.

The core as code

pythonimport numpy as np

def kernel_ridge(X, y, kappa, lam):
    """X: (n, p) samples, y: (n,) labels, kappa(A, B) returns a (len(A), len(B)) table."""
    K = kappa(X, X)                                    # (n, n)  the Gram table
    c = np.linalg.solve(K + lam * np.eye(len(X)), y)   # (n,)    one weight per sample
    return lambda Xnew: kappa(Xnew, X) @ c            # (m, n) @ (n,) -> (m,)

gauss = lambda s: lambda A, B: np.exp(-((A[:, None, :] - B[None, :, :])**2).sum(-1) / (2 * s * s))
sinc  = lambda a: lambda A, B: np.sinc(a * (A[:, None, 0] - B[None, :, 0]) / np.pi)   # sin(a d) / (a d)

# the dual and the primal agree (Chapter 3): each price is a leftover error
w     = np.linalg.solve(X.T @ X + lam * np.eye(X.shape[1]), X.T @ y)   # (d,)
alpha = np.linalg.solve(X @ X.T / lam + np.eye(len(X)), y)             # (n,)
assert np.allclose(w, X.T @ alpha / lam) and np.allclose(alpha, y - X @ w)

# Shannon interpolation (Chapter 9): sinc bumps on a uniform grid
x_hat = lambda t, x, T: (x * np.sinc((t[:, None] - np.arange(len(x)) * T) / T)).sum(1)

Where it sits in the field

Aronszajn formalised reproducing kernel Hilbert spaces in 1950. Kimeldorf and Wahba proved a representer theorem for smoothing splines in 1971, and the general form is the one in this lecture. Kernel ridge regression is the same estimator that a Gaussian process gives as its mean. Shannon published the sampling theorem in 1949. Later lectures turn to models that learn their own features.

Keep going

The sibling lessons cover the neighbouring ground. Lecture 19 introduces kernels. Lecture 17 and Lecture 18 build the support vector machine and the duality used here. Lecture 20 covers ridge in matrix form. Lecture 6 teaches the Fourier basis behind the sinc kernel. Lecture 22 comes next, on adaptive filters.

The takeaway. A kernel is a promise about which curves are cheap. The representer theorem says the best curve under that promise needs only n bumps, so you can fit in an infinite space with a table the size of your data.
You have 50 samples with 20,000 features each, and you want to fit a smooth curve with a Gaussian kernel. What do you store and solve?

Now press Present or Teach and explain the lecture out loud from memory. Cover six points: why a penalty is a prior, why the dual needs one price per sample, how a kernel replaces a lift, what the RKHS norm charges for, why n bumps are enough, and why Shannon’s formula is kernel regression. Then go back to the fitting instrument and try the four kernels on your own points.

EE269 Lecture 21: RKHS and Kernel Regression. Slides by Mert Pilanci, Stanford University, February 27, 2019.
The course site · Lecture slides · All decks · Previous: Regression · Next: Adaptive filters · Back to Gleams