UPPSALA UNIVERSITET

Matematiska institutionen Christer Kiselman

FORMELSAMLING

Transformer för beräkningar

2001 05 06 formelsamling2001

1. Notation

We shall denote the set {0, 1, 2, ...} by N, and the set {1, 2, 3, ...} by N^{∗}.^{1} Other common notation is Z for the ring of integers, Q for the field of rationals, R for the field of real numbers, and C for the field of complex numbers.

2. Bases and dimensions

2.1. An algebraic basis (also known as a Hamel basis) of a vector space E is an indexed family (e_{i})_{i∈I} such that every element x ∈ E can be written in a unique way as x = ∑_{i∈I} x_{i}e_{i} with only finitely many coordinates x_{i} different from zero. If there exists a finite basis, then all bases have the same number of elements, and this number is called the dimension of the space.

2.2. If f: V → W is a linear mapping of one vector space V into another, called W, then dim ker f + dim im f = dim V, with a natural interpretation even if some of the dimensions are infinite (two or three).

3. Normed spaces and inner product spaces

3.1. A norm on a vector space E is a function E ∋ x ↦ ∥x∥ ∈ R such that (i) ∥x∥ ⩾ 0 with equality only if x = 0; (ii) ∥tx∥ = |t|∥x∥ for all x ∈ E and all scalars t; (iii) ∥x + y∥ ⩽ ∥x∥ + ∥y∥ for all x, y ∈ E. Examples: ∥x∥_{p} = ( ∑ |x(j)|^{p})^{1/p}, 1 ⩽ p < +∞ and ∥x∥_{∞} = sup_{j} |x(j)| for vectors such that these expressions are finite. We denote by l^{p}(Z_{N}) the space C^{N} equipped with the norm ∥ · ∥_{p}, and by l^{p}(Z) the space of all sequences (z(n))_{n} such that ∥z∥_{p} is finite. The space c_{0}(Z) of all sequences z = (z(n))_{n∈Z} tending to zero as n → ±∞ is a closed subspace of l^{∞}(Z). We have

l^{1}(Z) ⊂ l^{2}(Z) ⊂ c_{0}(Z) ⊂ l^{∞}(Z).

3.2. An inner product on a vector space E is a sesquilinear form E × E ∋ (x, y) ↦ ⟨x, y⟩ such that ⟨x, x⟩ ⩾ 0 with equality only for x = 0. (Another common notation is (x | y).) Then \sqrt{⟨x, x⟩} is a norm. Example: ⟨x, y⟩ = ∑ x(j)\overline{y(j)} for x, y ∈ l^{2}(Z_{N}). If (e_{i})_{i∈I} with I finite is an orthonormal basis, then z = ∑_{i∈I}⟨z, e_{i}⟩e_{i}. In l^{2}(Z_{N}) the family (δ_{k})_{k=0}^{N−1} of all Dirac functions forms an ON-basis (δ_{k}(j) = 1 if j = k and zero otherwise)

1Michael W. Frazier, in his book An Introduction to Wavelets Through Linear Algebra. Springer, 1999, on which this Formelsamling is based, writes N for {1, 2, 3, ...}. Here I use N and N^{∗} according to the more usual convention. Otherwise I follow Frazier closely.

4. Bases in a normed space

4.1. A Schauder basis in a normed space E is an indexed family (e_{i})_{i∈I} such that every element can be written in a unique way as a convergent sum z = ∑_{i∈I} z_{i}e_{i} for some scalars z_{i}. The convergence means here that for every positive ε there exists a finite set J_{ε} ⊂ I such that ∥z − ∑_{i∈J} z_{i}e_{i}∥ < ε for all finite subsets J ⊃ J_{ε}. If (e_{i})_{i∈I} is an orthonormal Schauder basis in an inner-product space, then z = ∑_{i∈I}⟨z, e_{i}⟩e_{i} with convergence in norm, i.e., the coordinates are just z_{i} = ⟨z, e_{i}⟩. The family of all Dirac functions (δ_{k})_{k∈Z} form a Schauder basis (not an algebraic basis) in the spaces l^{p}(Z), 1 ⩽ p < ∞, as well as in c_{0}(Z). For p = 2 they form an ON-basis. (In an infinite-dimensional space, an algebraic basis must have many more elements than a Schauder basis.) An orthogonal indexed family (e_{i})_{i∈I} is said to be complete if it is a basis, which is equivalent to saying that the closure of the vector space spanned by all finite linear combinations of the e_{i} is equal to the whole space.

5. Convolution on a finite group

5.1. On any finite group G we may define

(f ∗ g)(z) = ∑ f(x)g(y),

where the sum is extended over all elements x, y ∈ G such that xy = z. If the group is commutative it is customary to write the group operation as addition, thus

(f ∗ g)(z) = ∑_{y∈G} f(z − y)g(y), z ∈ G.

Convolution is commutative and associative if the group is finite and commutative.

5.2. We consider the finite cyclic group Z_{N} = Z mod N = Z/NZ. A function on that space can be represented by its values (z(0), z(1), ..., z(N − 1)), but equally well by its values (z(1), z(2), ..., z(N)) or any other period. Convolution of two functions or vectors is defined as

(z ∗ w)(n) = ∑_{j} z(j)w(n − j), n ∈ Z_{N},

where it is understood that summation is extended over a period, the vectors being periodic functions. The translation operator R_{k} is defined by (R_{k}z)(n) = z(n − k). We have z ∗ δ_{k} = R_{k}z, where δ_{k} is the Dirac delta placed at position k.

5.3. Any linear translation-invariant operator T: l^{2}(Z_{N}) → l^{2}(Z_{N}) is given by convolution by some vector b:

T (z) = b ∗ z, z ∈ l^{2}(Z_{N}).

6. The discrete Fourier transform

6.1. For z ∈ l^{2}(Z_{N}) we define its Fourier^{2} transform

ẑ(n) = ∑_{j} z(j)ω^{jn} = ∑_{j} z(j)e^{−2πijn/N}, n ∈ Z_{N}.

2Jean-Baptiste-Joseph Fourier, 1768–1830.

Here ω = e^{−2πi/N} is a root of unity: ω^{N} = 1. It is easy to express the Fourier transform of a convolution product in terms of that of the factors:

{ \atop z ∗ w}(n) = ẑ(n)ŵ(n), n ∈ Z_{N}.

6.2. For any z ∈ l^{2}(Z_{N}), we define z̃ ∈ l^{2}(Z_{N}) by z̃(n) = \overline{z(−n)}. We note that ˆ z̃ = \overline{ẑ}, that ˆ \overline{z} = ˜ ẑ, and that (z ∗ w̃)(k) = ⟨z, R_{k}w⟩.

6.3. Any linear operator T: l^{2}(Z_{N}) → l^{2}(Z_{N}) which commutes with translation is diagonalized by the Fourier transformation in that we have

{ \atop T (z)} = b̂ · ẑ, z ∈ l^{2}(Z_{N}),

for some b ∈ l^{2}(Z_{N}).

7. Wavelets on a finite cyclic group

7.1. Downsampling and upsampling. We define D: l^{2}(Z_{N}) → l^{2}(Z_{M}), where N = 2M, by D(z)(n) = z(2n), n ∈ Z_{M}. We define U: l^{2}(Z_{M}) → l^{2}(Z_{N}) by U(z)(n) = z(n/2) when n is even, U(z) = 0 when n is odd. These are the downsampling and upsampling operators; D ∘ U is the identity in l^{2}(Z_{M}). We note that U is a homomorphism between two convolution algebras: it is linear and U(z ∗ w) = U(z) ∗ U(w), while in general D(z ∗ w) ≠ D(z) ∗ D(w); however there is equality here when w = U(x) for some x.

7.2. A first stage wavelet basis is an orthonormal sequence of vectors R_{2k}u, R_{2k}v, k = 0, 1..., M − 1, where u, v ∈ l^{2}(Z_{N}), N = 2M.

7.3. If N is even, N = 2M, and u, v ∈ l^{2}(Z_{N}), we define the system matrix A(n) of u and v by

A(n) = \frac{1}{\sqrt{2}} ( \begin{matrix}û(n) & v̂(n) \\ û(n + M) & v̂(n + M) \end{matrix} ) .

Then the N vectors R_{k}v, R_{k}u, k = 0, ..., M − 1, form an orthonormal system if and only if A(n) is unitary for every n.

7.4. An arbitrary signal z can be reconstructed from U(D(z ∗ ṽ)) and U(D(z ∗ ũ)) as

t̃∗ U(D(z ∗ ṽ)) + s̃ ∗ U(D(z ∗ ũ)) = z

if and only if

A(n) ( \begin{matrix}ŝ(n) \\ t̂(n) \end{matrix} ) = ( \begin{matrix}√ & \overline{2} \\ 0 \end{matrix} ) for all n.

7.5. The first stage Shannon^{3} basis. Here the basis vectors are defined by

û(n) = \{ \begin{matrix}\sqrt{2}, & n = 0, 1, ..., \frac{1}{4}N − 1 or n = \frac{3}{4}N, \frac{3}{4}N + 1, ..., N − 1, \\ 0 & otherwise; \end{matrix}
v̂(n) = \{ \begin{matrix}\sqrt{2}, & n = \frac{1}{4}N, \frac{1}{4}N + 1, ..., \frac{3}{4}N − 1, \\ 0 & otherwise, \end{matrix}

3Claude Elwood Shannon, b. 1916 04 30 – 2001 02 24. assuming that N is divisible by 4.

7.6. The first stage Haar^{4} basis. Here the basis vectors are

u(n) = \{ \begin{matrix}\frac{1}{\sqrt{2}}, & n = 0, 1, \\ 0 & otherwise; \end{matrix}

v(n) = \{ \begin{matrix}\frac{1}{\sqrt{2}}, & n = 0, \\ −\frac{1}{\sqrt{2}}, & n = 1, \\ 0 & otherwise. \end{matrix}

7.7. A p^{th} stage wavelet filter sequence is a sequence of vectors u_{1}, v_{1}, u_{2}, v_{2}, ..., u_{p}, v_{p}, such that, for each j = 1, 2, ..., p, we have u_{j}, v_{j} ∈ l^{2}(Z_{N/2^{j−1}}) and the system matrix

A_{j}(n) = \frac{1}{\sqrt{2}} ( \begin{matrix}û_{j}(n) & v̂_{j}(n) \\ û_{j}(n + \frac{1}{2}N) & v̂_{j}(n + \frac{1}{2}N) \end{matrix} )

is unitary for all n = 0, 1, ..., N/2^{j} − 1. For any input z we define x_{1} = D(z ∗ ṽ_{1}), y_{1} = D(z ∗ ũ_{1}), x_{j} = D(y_{j−1} ∗ ṽ_{j}) ∈ l^{2}(Z_{N/2^{j}}), y_{j} = D(y_{j−1} ∗ ũ_{j}) ∈ l^{2}(Z_{N/2^{j}}). The output of the analysis phase is the sequence of vectors x_{1}, x_{2}, ..., x_{p}, y_{p}.

7.8. Suppose N is divisible by 2^{p} and let u_{1}, v_{1}, u_{2}, v_{2}, ..., u_{p}, v_{p} be a p^{th}-stage wavelet filter sequence. Define f_{1}, f_{2}, ..., f_{p}, g_{1}, g_{2}, ..., g_{p} by

f_{j} = g_{j−1} ∗ U^{j−1}(v_{j}), g_{j} = g_{j−1} ∗ U^{j−1}(u_{j}).

Then f_{1}, f_{2}, ..., f_{p}, g_{p} generate a p^{th}-stage wavelet basis for l^{2}(Z_{N}), i.e.,

R_{2kf_{1}}, k = 0, ..., \frac{1}{2}N − 1; R_{4k}f_{2}, k = 0, ..., \frac{1}{4}N − 1; …; R_{2^{p}k}f_{j}, k = 0, ..., N/2^{p} − 1,

R_{2^{p}k}g_{p}, k = 0, ..., N/2^{p} − 1,

form an orthonormal basis for l^{2}(Z_{N}). With the notation

ψ_{−j,k} = R_{2^{j}k}f_{j}, φ_{−j,k} = R_{2^{j}k}g_{j}, j = 1, 2, ..., p, k = 0, 1, ..., N/2^{j} − 1,

the p^{th}-stage wavelet basis generated by f_{1}, f_{2}, ..., f_{p}, g_{p} is

ψ_{−1,k}, k = 0, ..., \frac{1}{2}N − 1; ψ_{−2,k}, k = 0, ..., \frac{1}{4}N − 1; ...; ψ_{−p,k}, k = 0, ..., N/2^{p} − 1;

φ_{−p,k}, k = 0, ..., N/2^{p} − 1.

We see that the space V_{−j} spanned by φ_{−j,0}, ..., φ_{−j,N/2^{j}−1} and the space W_{−j} spanned by ψ_{−j,0}, ..., ψ_{−j,N/2^{j}−1} satisfy V_{−j} = V_{−j−1} + W_{−j−1}, while V_{0} = l^{2}(Z_{N}).

8. Convolution on the integers

8.1. The convolution product of two vectors z, w is defined by

(z ∗ w)(n) = ∑_{j∈Z} z(j)w(n − j), n ∈ Z,

4Alfred Haar, 1885 10 11 – 1933 03 16. whenever the sum has a sense. The following cases are noteworthy. If one of the factors has only finitely many values different from zero, then the convolution product always exists. If both factors are zero for large negative values of the index, i.e., if z(j) = w(j) = 0 when j ≪ 0, then the convolution product exists. If one of the factors is in l^{1}(Z) and the other is in l^{p}(Z), then then the convolution product exists and belongs to l^{p}(Z). In particular, l^{1}(Z) is a convolution algebra. If both factors belong to l^{2}(Z), then the convolution exists and belongs to c_{0}(Z). Connected with these statements are the inequalities

∥z ∗ w∥_{p} ⩽ ∥z∥_{1} · ∥w∥_{p} for 1 ⩽ p ⩽ +∞; ∥z ∗ w∥_{∞} ⩽ ∥z∥_{2} · ∥w∥_{2}.

Convolution is commutative and associative under reasonable hypotheses. Note, however, examples like this:

1 = 1 ∗ δ = 1 ∗ ((δ_{0} − δ_{1}) ∗ h) ≠ (1 ∗ (δ_{0} − δ_{1})) ∗ h = 0 ∗ h = 0,

where h(n) = 0 for n < 0, h(n) = 1 for n ⩾ 0. Here all convolutions listed in the formula do exist, but the convolution 1 ∗ h does not.

8.2. Support. The support of a sequence (z(n))_{n∈Z} is the set of all indices n such that z(n) ≠ 0. We denote this set by supp z. It is clear that supp(z∗w) ⊂ supp z+supp w, but the inclusion may be strict. If we denote by K(z) the smallest interval which contains supp z, then we have an equality K(z ∗ w) = K(z) + K(w) valid for all vectors z, w with finite support. Actually K(z) = cvx supp z; see Chapter 11.

9. The Fourier transformation on the integers

9.1. For z ∈ l^{p}(Z) we define its Fourier transform as the periodic function

ẑ(t) = ∑ z(n)e^{int}, t ∈ R.

The sum has to be interpreted as a limit in L^{2}(I), I = [−π, π[, of finite sums. However, if z ∈ l^{1}(Z), then the sum is absolutely convergent and the transform ẑ is a continuous function.

9.2. The inverse Fourier transform f̌ of a function f on I is the sequence

f̌(n) = \frac{1}{2π} ∫_{−π}^{π} f(t)e^{−int}dt.

If f ∈ L^{2}(I), then f̌ ∈ l^{2}(Z); if f ∈ L^{1}(I), then f̌ ∈ c_{0}(Z).

9.3. The Fourier transform of a convolution product is given by the usual formula { \atop z ∗ w} = ẑŵ, at least if z ∈ l^{1}(Z) and w ∈ l^{2}(Z). (Distribution theory enables us to weaken these assumptions.)

10. Wavelets on the group of integers

10.1. Downsampling and upsampling on Z. The downsampling operator D: l^{2}(Z) → l^{2}(Z) and the upsampling operator U: l^{2}(Z) → l^{2}(Z) are defined on l^{2}(Z) by the same formulas as in the finite-dimensional case.

10.2. A first-stage wavelet system for l^{2}(Z) is a complete orthonormal family R_{2k}v, R_{2k}u, k ∈ Z, where u, v ∈ l^{1}(Z).

10.3. The system matrix of two vectors u, v ∈ l^{2}(Z) is

A(t) = \frac{1}{\sqrt{2}} ( \begin{matrix}û(t) & v̂(t) \\ û(t + π) & v̂(t + π) \end{matrix} ) .

If u, v ∈ l^{1}(Z), then R_{2k}v, R_{2k}u, k ∈ Z, is a first-stage wavelet system if and only if A(t) is unitary for all t ∈ R.

10.4. Assume that u, v ∈ l^{1}(Z) and that their system matrix A(t) is unitary for all t. Let an element g_{j−1} ∈ l^{2}(Z) be given such that (R_{2k})_{k∈Z} is orthonormal. Define

f_{j} = g_{j−1} ∗ U^{j−1}(v), g_{j} = g_{j−1} ∗ U^{j−1}(u).

Then the system (R_{2^{j}k}f_{j})_{k∈Z}, (R_{2^{j}k}g_{j})_{k∈Z} is orthonormal.

10.5. Now define

V_{−j} = {∑_{k∈Z} z(k)R_{2^{j}k}g_{j}; z ∈ l^{2}(Z)} ,
W_{−j} = {∑_{k∈Z} z(k)R_{2^{j}k}f_{j}; z ∈ l^{2}(Z)} .

Then V_{−j} + W_{−j} = V_{−j+1}, and the sum is orthogonal.

10.6. A p^{th}-stage wavelet system for l^{2}(Z) is an indexed family

(R_{2^{j}k}f_{j}, R_{2^{j}k}g_{p})_{k∈Z,j=1,...,p}

which is orthonormal and complete.

10.7. Let u_{j}, v_{j} ∈ l^{1}(Z), j = 1, ..., p, and assume that the system matrix A_{j}(t) of u_{j} and v_{j} is unitary for all j = 1, ..., p and all t ∈ R. Define f_{j} = v_{1}, g_{j} = u_{1} and inductively f_{j} = g_{j−1} ∗ U^{j−1}(v_{j}), g_{j} = g_{j−1} ∗ U^{j−1}(u_{j}). Then the system

(R_{2^{j}k}f_{j}, R_{2^{j}k}g_{p})_{k∈Z,j=1,...,p}

is a p^{th}-stage wavelet system for l^{2}(Z).

10.8. A homogeneous wavelet system for l^{2}(Z) is an indexed family (R_{2^{j}k}f_{j})_{k∈Z,j∈N^{∗}} which is orthonormal and complete.

10.9. Suppose that u_{j}, v_{j} ∈ l^{1}(Z), j ∈ N, and that the system matrix A_{j}(t) is unitary for all t ∈ R. Define f_{j} and g_{j} as in 10.7 and V_{−j} as in 10.5. Then if the intersection of all the V_{−j} consists of the origin only, the system (R_{2^{j}k}f_{j})_{k∈Z,j∈N^{∗}} is a homogeneous wavelet system.

10.10. The Haar wavelets on Z. Define u, v ∈ l^{1}(Z) by

u(n) = \{ \begin{matrix}\frac{1}{\sqrt{2}}, & n = 0, 1, \\ 0 & otherwise; \end{matrix}

v(n) = \{ \begin{matrix}\frac{1}{\sqrt{2}}, & n = 0, \\ −\frac{1}{\sqrt{2}}, & n = 1, \\ 0 & otherwise. \end{matrix}

Then the pair u, v generates a first-stage wavelet system for l^{2}(Z), and the intersection of all the spaces V_{−j}, defined as in 10.7, consists of the zero vector only. Hence (R_{2^{j}k}f_{j})_{k∈Z,j∈N^{∗}} is a homogeneous wavelet system, called the Haar system for l^{2}(Z).

10.11. Daubechies^{5} D6 wavelets on Z are defined by taking u(n) = 0 for n ≠ 0, 1, 2, 3, 4, 5, and then

(u(0), u(1), u(2), u(3), u(4), u(5))

= \frac{\sqrt{2}}{32}(b + c, 2a + 3b + 3c, 6a + 4b + 2c, 6a + 4b − 2c, 2a + 3b − 3c, b − c),

where

a = 1 − \sqrt{10}, b = 1 + \sqrt{10}, c = \sqrt{5 + 2\sqrt{10}},

and then v defined by v(−4) = −u(5), v(−3) = u(4), v(−2) = −u(3), v(−1) = u(2), v(−1) = u(2), v(0) = −u(1), v(1) = u(0), all other values being zero.

11. Convolution on the real axis

11.1. Support. The support of a function f defined on the real axis is the closure of the set of all points where the function is nonzero; it is denoted by supp f. It is easy to prove that supp(f ∗ g) ⊂ supp f + supp g. It is a deep theorem, called the Titchmarsh^{6} support theorem, that cvx supp(f ∗ g) = cvx supp f + cvx supp g if both supp f and supp g are bounded. Here cvx A denotes the convex hull of a set A; the theorem is valid also in R^{n}. On the real axis, cvx supp f is the smallest closed interval outside of which the function vanishes.

12. The Fourier transformation on the real axis

12.1. For a reasonable function f: R → C on the real axis we define its Fourier transform f̂ as

f̂(ξ) = ∫_{R} f(x)e^{−iξx}dx, ξ ∈ R.

The inverse Fourier transform of a function g is

ǧ(x) = \frac{1}{2π} ∫_{R} g(ξ)e^{iξx}dξ, x ∈ R.

12.2. Under some hypotheses we have (f̂)ˇ = f. In particular this is true if both f and its transform f̂ are integrable on the real axis.

12.3. If f, g are in L^{2}(R), the space of all square-integrable functions, then ⟨f̂, ĝ⟩ = 2π⟨f, g⟩ (Parseval’s relation); in particular ∥f̂∥_{2} = \sqrt{2π}∥f∥_{2} (Plancherel’s formula).

5Ingrid Daubechies, b. 1954. 6Edward Charles Titchmarsh, 1899 06 01 – 1963 01 18.

13. Wavelets on the real axis

13.1. A wavelet system for L^{2}(R) is a complete orthonormal system of the form {ψ_{j,k}}_{j,k∈Z}, for some ψ ∈ L^{2}(R), where ψ_{j,k}(x) = 2^{j/2}ψ(2^{j}x − k), x ∈ R.

13.2. A multiresolution analysis with scaling function φ is an indexed family (V_{j})_{j∈Z} of subspaces of L^{2}(R) such that (i) V_{j} ⊂ V_{j+1}, j ∈ Z; (ii) There exists a function φ ∈ V_{0} (the scaling function) such that the family (φ_{0,k})_{k∈Z} is orthonormal and V_{0} = {∑_{k∈Z} φ_{0,k}; z ∈ l^{2}(Z)}; (iii) f ∈ V_{0} if and only if x ↦ f(2^{j}x) is in V_{j}; (iv) ⋂_{j} V_{j} = {0}; (v) The closure of ⋃_{j} V_{j} is equal to all of L^{2}(R).

13.3. The Haar multiresolution analysis consists of the spaces V_{j} of functions which are constant on the interval [2^{−j}k, 2^{−j}(k + 1)[ for every k ∈ Z. Its scaling function is the characteristic function of the interval [0, 1[.

13.4. The scaling sequence of a multiresolution analysis (V_{j}) is the sequence u ∈ l^{2}(Z) such that φ = ∑_{k∈Z} u(k)φ_{1,k}. It follows that u(k) = ⟨φ, φ_{1,k}⟩. The indexed family (R_{2k}u)_{k∈Z} is orthonormal in l^{2}(Z).

13.5. Suppose (V_{j})_{j∈Z} is a multiresolution analysis with scaling function φ and such that its scaling sequence u belongs to l^{1}(Z). Define v ∈ l^{1}(Z) by v(k) = (−1)^{k−1}\overline{u(1 − k)}, k ∈ Z, and ψ = ∑_{k∈Z} v(k)φ_{1,k}. Then (ψ_{0,k})_{k∈Z} is an orthonormal family in L^{2}(R). If we define W_{0} = {∑ z(k)ψ_{0,k}; z ∈ l^{2}(Z)}, then V_{1} = V_{0} +W_{0}, and the two spaces V_{0} and W_{0} are orthogonal. Finally, (ψ_{j,k})_{j,k∈Z} is a wavelet system in L^{2}(R). (Mallat’s theorem.)

14. Orthogonal polynomials

14.1. General. We consider an inner product

⟨f, g⟩ = ∫_{a}^{b} f(x)\overline{g(x)}ρ(x)dx,

defined on functions on an interval [a, b], where ρ ⩾ 0 is called a weight function. A well-known example of an orthogonal sequence on [0, π] with weight function ρ(x) = 1 is f_{n} defined by f_{n}(x) = cos nx.

14.2. Legendre^{7} polynomials. Here a = −1, b = 1, ρ(x) = 1. The polynomials are defined by

P_{n}(x) = \frac{1}{2^{n}n!} (\frac{d}{dx})^{n} (x^{2} − 1)^{n}.

The first few Legendre polynomials are P_{0}(x) = 1, P_{1}(x) = x, P_{2}(x) = \frac{1}{2}(3x^{2} − 1), P_{3}(x) = \frac{1}{2}(5x^{3} − 3x). A generating function is

w(x, t) = \frac{1}{\sqrt{1 − 2xt + t^{2}}} = ∑_{0}^{∞} P_{n}(x)t^{n}.

The polynomial u = P_{n} solves the equation

((1 − x^{2})u′)′ + n(n + 1)u = 0.

7Adrien Marie Legendre, 1752–1833.

The inner product of P_{n} with itself is

∥P_{n}∥_{ρ}^{2} = ⟨P_{n}, P_{n}⟩ = ∫_{−1}^{1} P_{n}^{2}dx = \frac{2}{2n + 1}.

A continuous function on [−1, 1] can be expanded in a series f(x) = ∑ c_{n}P_{n}(x), where the coeffcients are given by c_{n} = (n + \frac{1}{2})⟨f, P_{n}⟩. The Legendre polynomials can be used to define a solution to the Laplace equation in a ball in case the boundary values are independent of the longitude: the function

u(r, θ) = ∑ r^{n}a^{−n}f_{n}P_{n}(cos θ),

where the coefficients f_{n} are defined by the expansion f(θ) = ∑ f_{n}P_{n}(cos θ), solves the equation Δu = 0 in the Euclidean ball ∥x∥_{2} < a with boundary values u = f on the sphere ∥x∥_{2} = a. Here we use spherical coordinates defined by the equations x = (x_{1}, x_{2}, x_{3}) = (r sin θ cos φ, r sin θ sin φ, r cos θ), so that π/2 − θ is the latitude, φ the longitude.

14.3. Hermite^{8} polynomials. Here a = −∞, b = +∞, ρ(x) = e^{−x^{2}}, thus

∫_{−∞}^{+∞} H_{m}(x)H_{n}(x)e^{−x^{2}}dx = 0, m ≠ n.

The polynomials are defined by

H_{n}(x) = (−1)^{n}e^{x^{2}} \frac{d^{n}}{dx^{n}} e^{−x^{2}}, n ∈ N.

The first few Hermite polynomials are H_{0}(x) = 1, H_{1}(x) = 2x, H_{3}(x) = 4x^{2} − 2, H_{3}(x) = 8x^{3} − 12x. A generating function is

w(x, t) = e^{2xt−t^{2}} = ∑_{0}^{∞} \frac{1}{n!}H_{n}(x)t^{n}, t ∈ C.

The Hermite polynomials solve the differential equation u′′ − 2xu′ + 2nu = 0. The function v = e^{−x^{2}/2}H_{n} solves the equation v′′ + (2n + 1 − x^{2})v = 0. The Hermite polynomials can be used to solve the Laplace and Helmholtz equations in a cylinder bounded by a parabolic cylinder surface.

14.4. Laguerre^{9} polynomials. Here a = 0, b = +∞, ρ(x) = x^{α}e^{−x}, thus

∫_{0}^{+∞} L_{m}^{α}(x)L_{n}^{α}(x)x^{α}e^{−x}dx = 0, m ≠ n.

The polynomials are defined by

L_{n}^{α}(x) = e^{x} \frac{x^{−α}}{n!} \frac{d^{n}}{dx^{n}} (e^{−x}x^{n+α}), n ∈ N, α > −1.

8Charles Hermite, 1822–1901. 9Edmond Nicolas Laguerre, 1834–1886.

The first few Laguerre polynomials are L_{0}^{α}(x) = 1, L_{1}^{α}(x) = 1 + α − x, L_{3}^{α}(x) = \frac{1}{2}((1 + α)(2 + α) − 2(2 + α)x + x^{2}). The general formula is

L_{n}^{α}(x) = ∑_{k=0}^{n}(n + α)(n + α − 1) ⋯ (k + 1 + α)\frac{(−x)^{k}}{k!(n − k)!}.

A generating function is

w(x, t) = (1 − t)^{−α−1}e^{−xt/(1−t)} = ∑_{0}^{∞} L_{n}^{α}(x)t^{n}, |t| < 1.

The Laguerre polynomials solve the differential equation xu′′ + (α + 1 − x)u′ + nu = 0. The Laguerre polynomials can be used to solve the problem of propagation of electromagnetic waves along a transmission line.

14.5. Chebyshev^{10} polynomials. Here a = −1, b = 1, ρ(x) = 1/\sqrt{1 − x^{2}}, thus

∫_{−1}^{1} \frac{T_{m}(x)T_{n}(x)}{\sqrt{1 − x^{2}}}dx = 0, m ≠ n.

The polynomials are defined by

T_{n}(x) = cos(n arccos x), x ∈ [−1, 1], n ∈ N.

(Note that the T_{n} are polynomials and therefore can be extended to all x ∈ R.) A generating function is

w(x, t) = \frac{1 − t^{2}}{1 − 2xt + t^{2}} = T_{0} + 2 ∑_{1}^{∞} T_{n}(x)t^{n}, |t| < r,

where r = min(r_{1}, r_{2}), r_{j} being the two roots of the equation 1 − 2xt + t^{2} = 0, t = r_{1}, r_{2}. Chebyshev proved that every continuous function on an interval [a, b] has a unique best approximant in the supremum norm among the polynomials of degree < m. If a = −1, b = 1, then the best approximant to f(x) = x^{m} among the polynomials of degree < m is 2^{−m+1}T_{m}; more precisely

x^{m} − p_{m−1}(x) = 2^{−m+1} cos(m arccos x) = 2^{−m+1}T_{m}(x).

(See my lecture notes Approximation by polynomials, Uppsala University, Department of Mathematics, Lecture Notes 1999:LN1.)

14.6. Jacobi^{11} polynomials. Here a = −1, b = 1, ρ(x) = (1 − x)^{α}(1 + x)^{β}, α, β > −1, thus

∫_{−1}^{1} P_{m}^{(α,β)}(x)P_{n}^{(α,β)}(x)(1 − x)^{α}(1 + x)^{β}dx = 0, m ≠ n.

10Pafnutiĭ L′vovič Čebyšëv, 1821–1894. 11Carl Gustav Jacob Jacobi, 1804–1851.

The polynomials are defined by

P_{n}^{(α,β)}(x) = \frac{(−1)^{n}}{2^{n}n!} (1 − x)^{−α}(1 + x)^{−β} \frac{d^{n}}{dx^{n}} ((1 − x)^{n+α}(1 + x)^{n+β}) , n ∈ N.

The function u = P_{n}^{(α,β)} solves the differential equation

(1 − x^{2})u′′ + (β − α − (α + β + 2)x)u′ + n(n + α + β + 1)u = 0.

A generating function is

w(x, t) = 2^{α+β}R^{−1}(1 − t + R)^{−α}(1 + t + R)^{−β} = ∑_{0}^{∞} P^{(α,β)}(x)t^{n}, |t| < r,

where R = (1 − 2xt + t^{2})^{−1/2}, and r = min(r_{1}, r_{2}), r_{j} being the two roots of the equation 1 − 2xt + t^{2} = 0, t = r_{1}, r_{2}.

15. The Radon transformation

15.1. History. Johann Radon (1887–1956) published a remarkable paper in 1917:

Über die Bestimmung von Funktionen durch ihre Integralwerte längs gewisser Mannigfaltigkeiten. Ber. Verh. Sächs. Akad. Wiss. Leipzig Math.-Nat. Kl. 69 (1917), 262–277.

Forty-six years later Alan M. Cormack (b. 1924) published the paper

Representation of a function by its line integrals, with some radiological applications I, II. J. Appl. Phys. 34 (1963), 2722–2727; 35 (1964), 2908–2912.

Cormack and Godfrey N. Hounsfield (b. 1919) produced the first picture of a brain using this method in 1972.

15.2. Definitions. The Radon transform of a function f defined in R^{2} is

ℛf(L) = ∫_{L} f,

where L is any straight line in the plane. We assume that the function f tends to zero at infinity in such a way that the integral converges.

More generally, the Radon transform of f is:

ℛf(ω, p) = ∫_{ω·x=p} f(x) dm(x), (ω, p) ∈ S^{n−1} × R,

where f is defined on R^{n} and (ω, p) ∈ S^{n−1} × R defines a hyperplane

{x ∈ R^{n}; ω · x = p}.

Here, again, we must assume that the function tends to zero at infinity sufficiently rapidly.

The dual Radon transform ℛ^{♯} of a function φ defined on the set of all hyperplanes is

ℛ^{♯}φ(x) = ∫_{ξ∋x} φ(ξ)dμ(ξ), x ∈ R^{n}.

The integral is defined to yield the mean value of φ over all hyperplanes passing through x. If we let ξ be defined by (ω, p) ∈ S^{n−1} × R, then this definition takes the form

ℛ^{♯}g(x) = ∫_{S^{n−1}} g(ω, ω · x)dω, x ∈ R^{n},

where g is defined on S^{n−1} × R and the integral is normalized to yield the mean value over the (n − 1)-dimensional sphere.

15.3. Rules of calculus. We note that

ℛ(∂_{j}f) = ω_{j} \frac{∂}{∂p}ℛf;

and that the Laplacian

Δ = \frac{∂^{2}}{∂x_{1}^{2}} + \frac{∂^{2}}{∂x_{2}^{2}} + \frac{∂^{2}}{∂x_{3}^{2}}

intertwines with the operator □ = ∂^{2}/∂p^{2} as follows:

ℛ ∘ Δ = □ ∘ ℛ, Δ ∘ ℛ^{♯} = ℛ^{♯} ∘ □.

15.4. Relation to the Fourier transformation. Let ℱ_{n} denote the Fourier transformation in R^{n}:

ℱ_{n}f(ξ) = ∫_{R^{n}} f(x)e^{−iξ·x}dx, ξ ∈ R^{n}.

Then the Fourier slice theorem says that ℱ_{n} = ℱ_{1}∘ℛ, where ℱ_{1} is the one-dimensional Fourier transformation in the variable p.

15.5. Relation to convolution. We have ℛ(f ∗ g) = ℛf ∗_{p} ℛg, where ∗_{p} denotes convolution in the p variable only.

15.6. Inversion via the Fourier transformation. From the Fourier slice theorem ℱ_{n} = ℱ_{1} ∘ ℛ we deduce that Id = ℱ_{n}^{−1} ∘ ℱ_{n} = ℱ_{n}^{−1} ∘ ℱ_{1} ∘ ℛ, so that f can be recovered from its Radon transform φ as f = ℱ_{n}^{−1}(ℱ_{1}(φ)). This formula is actually used in numerical computations.

When n = 2, we can recover f from ℛf by the formula:

f(x) = −\frac{1}{π} ∫_{0}^{∞} \frac{dg_{x}(q)}{q}, x ∈ R^{2},

a Stieltjes integral, where g_{x}(q) is the mean value of ℛf(L) over all lines L with distance q to x.

For n = 3:

f(x) = −\frac{1}{8π^{2}} Δ ∫_{S^{2}} ℛf(ω, ω · x)dω, x ∈ R^{3}.

The inversion formula for any dimension is:

f = c_{n}Δ^{(n−1)/2}ℛ^{♯}ℛf, f ∈ 𝒮(R^{n}).

Note: When n is odd, we have an integer power of the Laplacian: the operator is local. When n is even, the operator is not local; it has to be interpreted via the Fourier transformation. Recall that −Δ corresponds to multiplication by ∥ξ∥_{2}^{2} = ⟨ξ, ξ⟩. Therefore any power (−Δ)^{α} can be interpreted as multiplication by ∥ξ∥_{2}^{α/2} on the Fourier transform side.

15.7. The Helgason^{12} support theorem. If f ∈ C(R^{n}) decreases so fast that sup_{x∈R^{n}} ∥x∥_{2}^{m}|f(x)| is finite for all m ⩾ 0 and ℛf has support in {(ω, p); |p| ⩽ r}, then f has support in the ball {x; ∥x∥_{2} ⩽ r}. More generally, if ℛf(ω, p) = 0 for all (ω, p) such that {x; ω · x = p} does not meet a convex compact set K, then supp f ⊂ K.

To reconstruct f outside K we need to know ℛf only for hyperplanes that do not meet K. Application: Let K contain the heart (which is pounding all the time)... Note: The function f must decrease rapidly, faster than any power of ∥x∥_{2}.

12Sigurdur Helgason, b. 1927.