UPPSALA UNIVERSITET

Matematiska institutionen Christer Kiselman

ÖVNINGAR, Blad 4

Transformer för beräkningar 2001 05 04 01trp4

4.1. Let u, v ∈ l^{2}(Z_{8}) be the vectors

u = (1/\sqrt{2}, 1/\sqrt{2}, 0, 0, 0, 0, 0, 0), v = (1/\sqrt{2}, −1/\sqrt{2}, 0, 0, 0, 0, 0, 0).

(The first-stage Haar basis.)

(a) Prove that the vectors R_{2k}u, R_{2k}v, k = 0, 1, 2, 3, form an orthonormal system in l^{2}(Z_{8}). (3)

(b) Define

P (z) = ∑_{k=0}^{3}⟨z, R_{2k}u⟩R_{2k}u, Q(z) = ∑_{k=0}^{3}⟨z, R_{2k}v⟩R_{2k}v.

Calculate P (z) and Q(z) when z = (1, 2, 4, 6, 10, 12, 10, 8). Tenta 2000 05 22:5

4.2. Suggest an O(N log N) algorithm for computing matrix-vector multiplication, assuming the matrix to be Toeplitz. (Recall that the elements of a Toeplitz matrix are constant along diagonals. A circulant matrix is Toeplitz but not necessarily conversely.) Tenta 2000 05 22:6

4.3. Define f: R^{2} → R by f(x) = 1 − ∥x∥_{2}^{2} when ∥x∥_{2} < 1, f(x) = 0 when ∥x∥_{2} ⩾ 1. Calculate the Radon transform φ = ℛf of f, i.e., calculate φ(ω, p) for ω =

(cos θ, sin θ) ∈ S1, p ∈ R. Tenta 2000 05 22:7

4.4. For any z ∈ l^{∞}(Z) let us denote by K(z) the smallest interval I ⊂ Z such that z(j) = 0 for all j ∉ I. (K(0) = Ø.) Prove that if K(z) and K(w) are of finite length, then

K(z ∗ w) = K(z) + K(w).

(An easy form of Titchmarsh’ theorem on supports.) Show by an example that this may not be true if K(z) or K(w) is infinitely long. But it is true if K(z) and K(w) are contained in the set of nonnegative integers.

4.5. Prove that ẑ is a continuous function, ẑ ∈ C(R), if z ∈ l^{1}(Z). Here ẑ(t) = ∑ z(k)e^{ikt}, t ∈ R.

4.6. Prove that if f ∈ C^{2}(R) is periodic with period 2π, then f̌ ∈ l^{1}(Z). Here f̌(n) = (2π)^{−1} ∫_{−π}^{π} f(t)e^{−int}dt, t ∈ R.

4.7. Prove that the convolution equation a ∗ z = b can be solved with z ∈ l^{1}(Z) if â, b̂ ∈ C^{2}(R) and have period 2π, and if in addition we assume that there exists an ε > 0 such that |â(t)| ⩾ ε for all t such that b̂(t) ≠ 0.

4.8. Prove that the convolution equation z∗z = δ has exactly two solutions z ∈ l^{1}(Z), but infinitely many solutions z ∈ l^{2}(Z).

4.9. When does the FRFT-algorithm perform better than the usual mixed-radix implementation of FFT? Motivate your answer.

4.10. Consider a filterbank transform of z ∈ Z_{N}, where N = 2^{p} and the coarsest level in the transform has N_{0} = 2^{q} points, independent of N. Assume that the filters have the same number of non-zero elements on all levels. Show that the transform can be computed in O(N) arithmetic operations.

4.11. Let Q be a matrix representing some fast transform. Assume that A is diagonalised by Q. Show that the eigenvalues of A are given by

λ = mQD^{−1},

where m is a row of A and the corresponding row in Q are the diagonal entries of the diagonal matrix D.

4.12. Suggest a fast algorithm for solving a system of equations with A as coefficient matrix.