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 {f_{i} | i ≥ 0} are orthogonal if
<f_{i} , f_{j} > = 0,
∀ i, j s.t. i≠j
and are orthonormal if also
||f_{i} || = 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).
Please turn JavaScript on.
Series of Functions
If a function f(x) has an expansion
f(x) = a_{0} f_{0} (x)
+ a_{1} f_{1} (x)
+ ...
over [lo, hi] in terms of orthogonal basis functions,
{f_{0} (x), f_{1} (x), ...},
then
<f, f_{i} > =
∫ _{[lo..hi]} f(x) f_{i} (x) dx
= ∫ _{[lo..hi]}
a_{0} f_{0} (x) f_{i} (x)
+ a_{1} f_{1} (x) f_{i} (x)
+ ... dx
=^{ } a_{0} .<f_{0} ,f_{i} >
+ a_{1} .<f_{1} ,f_{i} >
+ ...
= a_{0} . 0 + ...
+ a_{i-1} . 0
+ a_{i} . ||f_{i} ||^{2}
+ a_{i+i} . 0 + ...
= a_{i} . ||f_{i} ||^{2}
so
a_{i}
= <f, f_{i} > / ||f_{i} ||^{2}
If the basis functions are orthonormal
then a_{i} = <f, f_{i} >.
Interpolation
Suppose we are given "training" data points
{(x_{1} , y_{1} ),
(x_{2} , y_{2} ), ...,
(x_{N} , y_{N} )},
where the x_{i} ∈ [lo, hi], and
want to find a function, f(x), that is a "good" fit to the data,
that is each f(x_{i} ) is close to its corresponding y_{i} .
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} (y_{i} - f(x_{i} ))^{2} .
A random example computed by JavaScript (if it is on) ...
Oh dear ... JavaScript is still off.
(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]:
p_{0} (x) = 1,
p_{1} (x) = x,
p_{2} (x) = (3x^{2} - 1) / 2,
p_{3} (x) = (5x^{3} - 3x) / 2,
p_{4} (x) = (35x^{4} - 30x^{2} + 3) / 8,
. . .
and in general (Bonnet):
p_{i+1} (x) =
{(2i + 1) x p_{i} (x) - i p_{i-1} (x)} / (i+1)
(e.g.,
p_{2+1} (x)
= { 5 (3x^{3} - x) / 2 - 2 x } / 3
= { 15x^{3} - 9 x } / 6
= { 5x^{3} - 3 x } / 2),
or
p_{n} (x) =
∑_{k=0..n}
(-1)^{k}
(
n
)^{2}
((1 + x) / 2)^{n-k}
((1 - x) / 2)^{k}
k
Note that
p_{n} (1) = 1,
p_{n} (-1) = (-1)^{n} ,
<p_{n} , p_{n} > = 2 / (2n + 1).
By JavaScript (if it is on):
. . . But no, JavaScript is off.-()
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 :
. . . Oh, dear JavaScript is still off.
For continuous f on [0, 2π],
or equivalently infinitely repeated on
..., [-2π,0), [0, 2π), [2π,4π), ...,
f's Fourier series is
f(x) ~
a_{0}
+ a_{1} cos x
+ a_{2} cos 2x
+ ...
+ b_{1} sin x
+ b_{2} sin 2x
+ ...,
where
a_{0} =
(1/(2π))
∫ _{[0..2π]} f(θ) dθ,
a_{n} =
(1/π) ∫ _{[0..2π]}
f(θ) cos(nθ) dθ, n≥1,
b_{n} =
(1/π) ∫ _{[0..2π]}
f(θ) sin(nθ) dθ, n≥1.
(Often^{ } a_{0} ' is defined
to be twice as large as a_{0} , and the series written
f(x) ~ ^{a0'} /_{2}
+ a_{1} f_{1} (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]:
JavaScript is off.-()
f = saw_tooth on [0, 1]:
It would be better on.
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:
Pity that JavaScript is off.