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
- = ∫[lo..hi] a0 f0(x) fi(x) + a1 f1(x) fi(x) + ... dx
- 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) ...
- 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 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,
- . . .
- p1(x) = x,
- 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):
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π].
- <sin(m . ), cos(n . )> = 0, and
- {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 :
- {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].
- 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) + ... .)
- a0 = (1/(2π)) ∫[0..2π] f(θ) dθ,
- 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 = saw_tooth on [0, 1]:
- 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:
-