1. k-term best approximation in L²

Consider the space of squared integrable functions E = L²(C), to which we associate the natural Hermitian product. Let f E and F be a subspace of E of finite dimension n.

1. Consider and fix a finite family of orthonormal functions ₁,,_n F such that F = Vec(₁,,_n). Let k {1,,n}.
   • Let 1 i₁ < i₂ < < i_k 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?
   • Which, of the -approximation of f in F is best in the MSE sense? Is it unique? What is the associated MSE?
2. Consider and fix two different finite families of orthonormal functions ₁,,_n F and _e1,,_en F.
   • Compare the n-approximations of f, in the MSE sense, using the family on one hand and the _e family on the other.
   • 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(2t) (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).

1. The 4 4 Haar matrix is given by

H (2)

and its columns are used to form a set of 4 orthonormal functions, {_i^H(t)}⁴_i=1, defined for t [0,1).

• Show the set of orthonormal Haar functions {_i^H(t)}⁴_i=1. The functions should be presented using graphs with explicit notation of relevant values on the two axes.
• For the case of, what is the best 1-term approximation of (t) on the set of the Haar functions {_i^H(t)}⁴_i=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)?
• For the case of, what is the best 1-term approximation of (t) on the set of the Haar functions {_i^H(t)}⁴_i=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)?

1. he 4 4 Walsh-Hadamard matrix is given by

W (3)

and its columns are used to form a set of 4 orthonormal functions, {^W_i (t)}⁴_i=1, defined for t [0,1).

• For the case of , what is the best 1-term approximation of (t) on the set of the Walsh-Hadamard functions {^W_i (t)}⁴_i=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)?
• For the case of , what is the best 1-term approximation of (t) on the set of the Walsh-Hadamard functions {^W_i (t)}⁴_i=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) R² mapping to a two-components column vector, i.e.,

(4)

where ⁽¹⁾ : [0,1) R and ⁽²⁾ : [0,1) R. The inner product of the functions f : [0,1) R² and g : [0,1) R² is defined by

(5)

1. 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.

1. Consider a function : [0,1) R² 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_ii(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.

1. Define and calculate the properties of the signal (x,y) as required for the bitallocation optimization (suitable for signals defined over two-dimensional domains).
2. Consider the number of sampling intervals along the horizontal direction by N_x, the number of sampling intervals along the vertical direction by N_y, 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

1. 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 b⁰. What is the difference between N_x and ? Comment.

5. On Hadamard matrices

Let n N a positive integer and N = 2ⁿ. Consider the Hadamard matrix of dimension H₂n = H_N.

1. Prove that H_N a symmetric, real, and unitary matrix. Prove also that it can be written as H_N = _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.
2. For a sequence, s, of digit numbers taking the value 1, we denote S(s) the number of changes of sign in s.
   • Denote s₁,s₂ two sequences of numbers of same length. What is S(s₁s₂), where s₁s₂ the concatenation of both sequences? Hint: you might want to consider several cases.
   • Denote r_i the i-th row of H_N. Prove the ensemble equality:

{S(r₁),,S(r_N)} = {0,,N 1}

, i.e. that the number of changes of sign in the rows of H_N 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.

1. Mathematically develop formulas for derivatives and integrals to calculate the value-range, the horizontal-derivative energy and the vertical-derivative energy.
2. 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).
3. 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.
4. Use the numerical approximations and numerically solve the bit-allocation optimiza-

tion to determine N_x, N_y and b.

(Hint: using fmincon function)

50000. Consider two bit-allocation procedures with the bit-budgets B_low = 5000 and B_high = 50000. Write the obtained values of N_x, N_y and b.
50001. Implement a searching procedure that finds the best bit-allocation parameters bypractically evaluating the bit-allocation MSE for many combinations of parameters.
50002. Apply the practical searching procedure for two bit-budgets B_low = 5000 and B_high = 50000. For each of the two bit-budgets, what are the optimal values of N_x, N_y 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.
50003. 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

1. Implement Hadamard matrices H₂n. This should be a function taking as input the level n. This function should return a 2ⁿ 2ⁿ
2. Take the two orthonormal families H₂n and into a new set of functions by

(13)

Plot the functions for n = 2,,6.

1. Implement Walsh-Hadamard matrices . This should be a function taking as input Hadamard matrices H₂n. This function should return a 2ⁿ 2ⁿ
2. 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,,2ⁿ? Present the results on the graph. What are the corresponding MSE errors?