Matthew Gray

9.520 Problem Set 1 May 19, 1998

Problem 3

Finding the minimum of H[f] is a “simple” case of taking the derivative and setting it to 0. The difficulty arises by the fact that we are differentiating with respect to a function, f. First, let’s rewrite H[f] as

H[f] = V [f] + λϕ(f)  (1)

so, we want to solve for f in

\frac{δH}{δf(y)} = \frac{δV [f]}{δf(y)} + λ\frac{δϕ[f]}{δf(y)} = 0  (2)

Fist solving for \frac{δV [f]}{δf(y)}:

\frac{δV [f]}{δf(y)} = ∫ dx2 [∫ dtθ(x − t)f(t) − F_{l}(x)] ∫ dtθ(x − t)\frac{δf(t)}{δf(y)}  (3)

which simplifies to:

\frac{δV [f]}{δf(y)} = ∫ dx2 [∫ dtθ(x − t)f(t) − F_{l}(x)] θ(x − y) = 2(θ ∗ f ∗ θ)(y) − (F_{l} ∗ θ)(y)  (4)

Taking the Fourier transform,

F [\frac{δV [f]}{δf(y)}] = 2θ̃(ω)f̃(ω) − F̃_{l}θ̃  (5)

Given that θ̃ = \frac{1}{ω} and F̃_{l} = \frac{1}{l} ∑_{i=1}^{l} θ̃e^{iωt_{i}}, we get the final expression:

F [\frac{δV [f]}{δf(y)}] = \frac{2}{ω^{2}} f̃(ω) − \frac{1}{ω^{2}l} ∑_{i=1}^{l} e^{iωt_{i}}  (6)

Now, we use the general case of ϕ[f], we obtain:

\frac{δϕ[f]}{δf(y)} = \frac{δ}{δf(y)} ∫ dω \frac{|f̃(ω)|^{2}}{G̃(ω)}  (7)

Since |f̃(ω)|^{2} = f̃(ω)f̃^{∗}(ω), we can rewrite as:

= \frac{δ}{δf(y)} ∫ dω \frac{1}{G̃(ω)} ∫ dxe^{iωx}f(x) ∫ dte^{−iωt}f(t)  (8)

Bringing all the terms that are constant with respect to f(y) out front:

= ∫ dωdxdt\frac{e^{iω(x−t)}}{G̃(ω)} \frac{δ}{δf(y)}f(x)f(t)  (9)

which simplifies to

= 2 ∫ dωdt\frac{e^{iω(y−t)}f(t)}{G̃(ω)}  (10)

which makes

F [\frac{δϕ[f]}{δf(y)}] = \frac{2f̃(ω)}{G̃(ω)}  (11)

Combining equations 2, 6 and 11:

\frac{f̃(ω)}{ω^{2}} − \frac{1}{ω^{2}} \frac{1}{l} ∑_{i=1}^{l} e^{iωt_{i}} + λ\frac{f̃(ω)}{G̃(ω)} = 0  (12)

Therefore,

f̃(ω) = \frac{1}{1 + λ\frac{ω^{2}}{G̃(ω)}} \frac{1}{l} ∑_{i=1}^{l} e^{iωt_{i}}  (13)

If we define the part before the \frac{1}{l} to be the Fourier transform of Φ(x),

f(x) = \frac{1}{l} ∑_{i=1}^{l} Φ[x − t_{i}]  (14)

which is Parzen windows, with a kernel function dependent on the regularization function ϕ.