236200 Homework 2 - k-term solved

1. k-term best approximation in L2
Consider the space of squared integrable functions E = L2(C), to which we associate the natural Hermitian product. Let f ∈ E and F be a subspace of E of finite dimension n.

a.     Consider and fix a finite family of orthonormal functions β1,...,βn ∈ F such that F = Vec(β1,...,βn). Let k ∈ {1,...,n}.

(a)    Let 1 ≤ i1 < i2 < ... < ik ≤ n be a set of k increasing integers between 1 and n. What is the k-term approximation of f in F using Vec(βi1,...,βin)? What is the associated MSE?

(b)    Which, of the -approximation of f in F is best in the MSE sense? Is it unique? What is the associated MSE?

b.    Consider and fix two different finite families of orthonormal functions β1,...,βn ∈ F and βe1,...,βen ∈ F.

(a)    Compare the n-approximations of f, in the MSE sense, using the β family on one hand and the βe family on the other.

(b)    What can you say about the k-term approximation on each family, where k ∈ {1,...,n − 1}?

2.         Haar matrix and Walsh-Hadamard matrix
Given t ∈ [0,1), consider the signal as

                                                                           φ(t) = a + bsin(2πt)                                                                       (1)

where a and b are constants. The procedures considered in this question for the approximation of φ(t) should be optimal with respect to minimization of the approximation MSE, calculated over the continuous domain [0,1).

a.     The 4 × 4 Haar matrix is given by

                                                                       H                                                       (2)

and its columns are used to form a set of 4 orthonormal functions, {ψiH(t)}4i=1, defined for t ∈ [0,1).

(i)        Show the set of orthonormal Haar functions {ψiH(t)}4i=1. The functions should be presented using graphs with explicit notation of relevant values on the two axes.

(ii)      For the case of , what is the best 1-term approximation of φ(t) on the set of the Haar functions {ψiH(t)}4i=1? What is the best 2-term approximation of φ(t)? What is the best 3-term approximation of φ(t)? What is the 4-term approximation of φ(t)?

(iii)    For the case of , what is the best 1-term approximation of φ(t) on the set of the Haar functions {ψiH(t)}4i=1? What is the best 2-term approximation of φ(t)? What is the best 3-term approximation of φ(t)? What is the 4-term approximation of φ(t)?

b.    he 4 × 4 Walsh-Hadamard matrix is given by

                                                                          W                                                          (3)

and its columns are used to form a set of 4 orthonormal functions, {χWi (t)}4i=1, defined for t ∈ [0,1).

(i)        For the case of , what is the best 1-term approximation of φ(t) on the set of the Walsh-Hadamard functions {χWi (t)}4i=1? What is the best 2-term approximation of φ(t)? What is the best 3-term approximation of φ(t)? What is the 4-term approximation of φ(t)?

(ii)      For the case of , what is the best 1-term approximation of φ(t) on the set of the Walsh-Hadamard functions {χWi (t)}4i=1? What is the best 2-term approximation of φ(t)? What is the best 3-term approximation of φ(t)? What is the 4-term approximation of φ(t)?

3.       Orthonormal functions
Consider a function φ : [0,1) → R2 mapping to a two-components column vector, i.e.,

                                                                                                                                                           (4)

where φ(1) : [0,1) → R and φ(2) : [0,1) → R. The inner product of the functions f : [0,1) → R2 and g : [0,1) → R2 is defined by

                                                                                     (5)

a.     Consider two distinct sets of N functions

                                                          and                                         (6)

               Prove that if both and           are a set of orthonormal functions, then

                                                                                                                       (7)

is also orthonormal.

b.    Consider a function φ : [0,1) → R2 and another function a set of N orthonormal functions . The approximation of the given signal φ(t) by the orthonormal functions is given by

N

                                                                                     φe(t) = Xφiψi(t)                                                                     (8)

i=1

where φi ∈ R for i = 1,...,N. The approximation MSE is defined by

                                                                   MSE = hφ(t) − φe(t),φ(t) − φe(t)i                                                   (9)

Develop the expressions for the optimal coefficients and the minimal approximation MSE in detail.

4.          Bit Allocation of a Two-Dimensional Signal
Consider a function φ : R × R → R by

                                                                                                                              (10)

where   0. We shall consider sampling (resp. quantizations) with high number of samples (resp. levels), and we choose to work with uniform quantization.

a.     Define and calculate the properties of the signal φ(x,y) as required for the bitallocation optimization (suitable for signals defined over two-dimensional domains).

b.    Consider the number of sampling intervals along the horizontal direction by Nx, the number of sampling intervals along the vertical direction by Ny, the number of bits for the quantization of each sample by b and the bit-allocation should be done under a constraint of overall bit-budget B.

Formulate the basic bit-allocation optimization problem

c.     Consider another function ψ : R × R → R by

                                                                                                                               (11)

where

The optimal bit-allocation under a budget of B bits for the signal ψ(x,y) is obtained by and b0. What is the difference between Nx and ? Comment.

5.       On Hadamard matrices
Let n ∈ N∗ a positive integer and N = 2n. Consider the Hadamard matrix of dimension H2n = HN.

a.     Prove that HN a symmetric, real, and unitary matrix. Prove also that it can be written as HN = λNA where λN ∈ R a constant (give its explicit value) and A a matrix with only ±1 entries, up to a normalisation constant to be given.

b.    For a sequence, s, of digit numbers taking the value ±1, we denote S(s) the number of changes of sign in s.

(i)      Denote s1,s2 two sequences of numbers of same length. What is S(s1s2), where s1s2 the concatenation of both sequences? Hint: you might want to consider several cases.

(ii)    Denote ri the i-th row of HN. Prove the ensemble equality:

{S(r1),...,S(rN)} = {0,...,N − 1}

, i.e. that the number of changes of sign in the rows of HN are the first N integers starting at 0.

II       Matlab
Instruction:

•    Figures should be titled in a appropriate font size.

•    Submit the code and a report describing the results and your understanding of the exercise.

1. Numerical and Practical Bit Allocation for TwoDimensional Signals
Consider a function

                               φ(x,y) = Acos(2πωxx)cos(2πωyy)       for      (x,y) ∈ (0,1] × (0,1]                          (12)

where A = 5000, ωx = 5 and ωy = 3.

a.     Mathematically develop formulas for derivatives and integrals to calculate the value-range, the horizontal-derivative energy and the vertical-derivative energy.

b.    Approximate the continuous-domain signal φ(x,y) by a very high resolution digitalization. Present the signal as an image using the imshow function (use an appropriate gray-level scaling that suits the value of A).

c.     Numerically calculate the value-range, the horizontal-derivative energy and the vertical-derivative energy. Compare these numerical results to the analytically calculated values from the question a.

d.    Use the numerical approximations and numerically solve the bit-allocation optimiza-

tion to determine Nx, Ny and b.

(Hint: using fmincon function)

e.     Consider two bit-allocation procedures with the bit-budgets Blow = 5000 and Bhigh = 50000. Write the obtained values of Nx, Ny and b.

f.      Implement a searching procedure that finds the best bit-allocation parameters bypractically evaluating the bit-allocation MSE for many combinations of parameters.

g.     Apply the practical searching procedure for two bit-budgets Blow = 5000 and Bhigh = 50000. For each of the two bit-budgets, what are the optimal values of Nx, Ny and b? Are these similar to the corresponding values from the question e? Explain it in detail. Present the reconstructed images obtained in the experiments.

h.    Consider the same function but with different parameters: A = 5000, ωx = 5 and ωy = 7. Repeat the analysis from question a to question g and compare the results. Explain the differences.

2.     Hadamard matrices and Hadamard-Walsh matrices
a.     Implement Hadamard matrices H2n. This should be a function taking as input the level n. This function should return a 2n × 2n matrix.

b.    Take the two orthonormal families H2n and into a new set of functions by

                                                                                                                    (13)

Plot the functions for n = 2,...,6.

c.     Implement Walsh-Hadamard matrices . This should be a function taking as input Hadamard matrices H2n. This function should return a 2n × 2n matrix.

d.    Take the two orthonormal families and         into a new set of functions by

                                                                                                                 (14)

Plot the functions for n = 2,...,6.

e. Given t ∈ [−5,5], consider a function
 
φ(t) = 3t3 + t2 − 4t + 2
(15)
Consider n = 4, what are the best k-term approximation of φ(t) for k = 1,...,2n? Present the results on the graph. What are the corresponding MSE errors?