Orthogonal
- For functions f and g defined on the range [lo..hi], define their inner product to be
- <f, g> = ∫lo..hi f(x) g(x) dx,
- and the norm
- ||f||2 = <f, f>1/2 (also written as just ||f||);
- hence
- <c f, g> = <f, c g> = c <f, g>
- and
- ||c f||2 = c ||f||2, where c is a constant.
- Functions {fi | i ≥ 0} are orthogonal if
- <fi, fj> = 0, ∀ i, j s.t. i≠j
- and are orthonormal if also
- ||fi|| = 1, ∀ i.
- Note that
- ∫-1..+1 f(x) dx = 1/a ∫-a..+a f(y/a) dy
- and that
- ∫-a..+a f(x) dx = ∫-a+b..a+b f(y-b) dy
- so one can scale and shift a set of orthogonal functions to another range, [lo, hi], and normalise them (individually).
Series of Functions
- If a function f(x) has an expansion
- f(x) = a0f0(x) + a1f1(x) + ...
- over [lo, hi] in terms of orthogonal basis functions, {f0(x), f1(x), ...}, then
- <f, fi> = ∫[lo..hi] f(x) fi(x) dx
- = ∫[lo..hi] a0 f0(x) fi(x) + a1 f1(x) fi(x) + ... dx
- = a0.<f0,fi> + a1.<f1,fi> + ...
- = a0 . 0 + ... + ai-1 . 0 + ai . ||fi||2 + ai+i . 0 + ...
- = ai . ||fi||2
- so
- ai = <f, fi> / ||fi||2
- If the basis functions are orthonormal then ai = <f, fi>.
Interpolation
- Suppose we are given "training" data points {(x1, y1), (x2, y2), ..., (xN, yN)}, where the xi ∈ [lo, hi], and want to find a function, f(x), that is a "good" fit to the data, that is each f(xi) is close to its corresponding yi. A common approach is to try to find some function, f(), expressed as a series in terms of a set of "simple" functions (orthonormal basis functions have advantages), which amounts to solving the resulting linear regression problem to minimise the sum of the squared errors, ∑i (yi - f(xi))2.
- A random example computed by JavaScript (if it is on) ...
- true f=sawtooth, range=[-1,1]
- sampled {x[i]} : -0.9, -0.83, -0.81, -0.72, -0.62, -0.6, -0.45, -0.43, -0.26, -0.16, -0.16, 0.16, 0.29, 0.4, 0.48, 0.7, 0.74, 0.75, 0.95, 0.97,
- sampled {y[i]} : -0.21, -0.34, -0.37, -0.55, -0.76, -0.8, -0.91, -0.86, -0.51, -0.33, -0.32, 0.32, 0.58, 0.8, 0.97, 0.59, 0.53, 0.5, 0.1, 0.06,
- fit polynomial, order 3 :
- {est_f(x[i])}: -0.15, -0.38, -0.43, -0.64, -0.77, -0.78, -0.77, -0.76, -0.54, -0.37, -0.37, 0.32, 0.57, 0.72, 0.79, 0.72, 0.67, 0.64, 0.04, -0.05,
- RMS=0.089, <true_f,est_f>=0.64
- fit polynomial, order 5 :
- {est_f(x[i])}: -0.17, -0.36, -0.4, -0.6, -0.76, -0.78, -0.82, -0.81, -0.58, -0.39, -0.38, 0.42, 0.67, 0.79, 0.82, 0.61, 0.55, 0.52, 0.1, 0.05,
- RMS=0.06, <true_f,est_f>=0.65
- (A polynomial can only approximate a sawtooth.)
- A high order approximation gives a smaller RMS error than a low order one in general. This of course opens the well known over-fitting trap; [Wallace] showed how to stop before falling into it (in the real world there is no looking at <true_f, est_f> because invariably true_f is unknown in a real inference problem).
Polynomials
- The Legendre polynomials are orthogonal polynomials on [-1, 1]:
- p0(x) = 1,
- p1(x) = x,
- p2(x) = (3x2 - 1) / 2,
- p3(x) = (5x3 - 3x) / 2,
- p4(x) = (35x4 - 30x2 + 3) / 8,
- . . .
- and in general (Bonnet):
- pi+1(x) = {(2i + 1) x pi(x) - i pi-1(x)} / (i+1)
- (e.g., p2+1(x) = { 5 (3x3 - x) / 2 - 2 x } / 3 = { 15x3 - 9 x } / 6 = { 5x3 - 3 x } / 2),
- or
-
pn(x) = ∑k=0..n (-1)k ( n )2 ((1 + x) / 2)n-k ((1 - x) / 2)k k - Note that
- pn(1) = 1, pn(-1) = (-1)n, <pn, pn> = 2 / (2n + 1).
- By JavaScript (if it is on):
- p0(x) = + 1
- p1(x) = + x
- p2(x) = + 1.5x2 - 0.5
- p3(x) = + 2.5x3 - 1.5x
- p4(x) = + 4.375x4 - 3.75x2 + 0.375
- p5(x) = + 7.875x5 - 8.75x3 + 1.875x
- . . . etc.
-
. . . etc.<p0,p0>=2 <p0,p1>=0 <p0,p2>=0 <p0,p3>=0 <p0,p4>=0 <p0,p5>=0 <p1,p0>=0 <p1,p1>=0.667 <p1,p2>=0 <p1,p3>=0 <p1,p4>=0 <p1,p5>=0 <p2,p0>=0 <p2,p1>=0 <p2,p2>=0.4 <p2,p3>=0 <p2,p4>=0 <p2,p5>=0 <p3,p0>=0 <p3,p1>=0 <p3,p2>=0 <p3,p3>=0.286 <p3,p4>=0 <p3,p5>=0 <p4,p0>=0 <p4,p1>=0 <p4,p2>=0 <p4,p3>=0 <p4,p4>=0.222 <p4,p5>=0 <p5,p0>=0 <p5,p1>=0 <p5,p2>=0 <p5,p3>=0 <p5,p4>=0 <p5,p5>=0.182 Fourier Series
- <sin(m . ), cos(n . )> = 0, and
- <sin(m . ), sin(n . )> = 0∫2 π sin(mθ) sin(nθ) dθ = π, if m=n, = 0 otherwise, similarly for cos.
- Hence, || sin(m θ) ||2 = || cos(m θ) ||2 = √π, on [0, 2π].
- {1/√(2π), sin(x)/√π, cos(x)/√π, sin(2x)/√π, cos(2x)/√π, sin(3x)/√π, cos(3x)/√π, ... } are orthonormal on [0, 2π] (and on [-π, π]), so . . .
- {1, √2 sin(2π x), √2 cos(2π x), √2 sin(4π x), √2 cos(4π x), √2 sin(6π x), √2 cos(6π x), ... } are orthonormal on [0, 1].
- e.g., ∫[0..1] √2 sin(2π m x) √2 sin(2π n x) dx :
- 0:0=0, 0:1=0, 0:2=0, 0:3=0, 0:4=0, ...
- 1:0=0, 1:1=1, 1:2=0, 1:3=0, 1:4=0, ...
- 2:0=0, 2:1=0, 2:2=1, 2:3=0, 2:4=0, ...
- 3:0=0, 3:1=0, 3:2=0, 3:3=1, 3:4=0, ...
- 4:0=0, 4:1=0, 4:2=0, 4:3=0, 4:4=1, ... etc.
- For continuous f on [0, 2π], or equivalently infinitely repeated on ..., [-2π,0), [0, 2π), [2π,4π), ..., f's Fourier series is
- f(x) ~ a0 + a1 cos x + a2 cos 2x + ... + b1 sin x + b2 sin 2x + ..., where
- a0 = (1/(2π)) ∫[0..2π] f(θ) dθ,
- an = (1/π) ∫[0..2π] f(θ) cos(nθ) dθ, n≥1,
- bn = (1/π) ∫[0..2π] f(θ) sin(nθ) dθ, n≥1.
- (Often a0' is defined to be twice as large as a0, and the series written f(x) ~ a0'/2 + a1f1(x) + ... .)
- Or, we can employ orthonormal versions of the basis functions on [0, 2π], or on [0, 1], and use the "general form" given earlier.
- E.g., square_wave(1,1,-1)(x)
= (4/π){sin 2πx + (1/3) sin 6πx + (1/5) sin 10πx + ...},
NB. on [0,1]. - f = square_wave(1,1,-1) on [0, 1]:
- f ~ + 0.9*√2*sin2*π*1 + 0.3*√2*sin2*π*3 + 0.18*√2*sin2*π*5.
- RMSE = 0.259
- f = saw_tooth on [0, 1]:
- f ~ + 0.573*f1 - 0.064*f5 + 0.023*f9.
- RMSE = 0.016
- √(odd2+even2): 0, 0.573, 0, 0.064, 0, 0.023,.
- where f1(x) = √2 sin 2πx; f2(x) = √2 cos 2πx; ... etc.
- f = shift(saw_tooth, 0.1), i.e., a 10% phase change:
- f ~ + 0.464*f1 + 0.337*f2 + 0.02*f5 - 0.061*f6 - 0.023*f9.
- RMSE = 0.016
- √(odd2+even2): 0, 0.573, 0, 0.064, 0, 0.023,.