DATA642-Lab 4 Solved

Lab 4

Sparsity Aware Learning

Advanced Machine Learning DATA 442/642

Exercise 1
Consider an unknown 2-sparse vector θ0, which when measured with the sensing matrix

X  

that is, of y = Xθ0, gives y = [1.253.75]>. Perform the following tasks in Python.

(a)    Based on the pseudoinverse of X, compute θˆ2, which is the `2 norm minimized solution. Next, check that this solution θˆ2 leads to zero estimation error (up to machine precision). Is θˆ2 a 2-space vector such as the true unknown vector θ0?

(b)    Solve the `0 minimization task based on an exhaustive search for all possible 1- and 2sparse solutions and get the best one, θˆ0. Does θˆ0 lead to zero estimation error (up to machine precision)?

(c)    Compute and compare the `2 norms of θˆ2 and θˆ0. Which is the smaller one? Was this result expected?

Exercise 2: Image Denoising
A typical example in sparsity aware learning is the denoising problem. The problem in signal denoising is that instead of the actual signal samples, y˜, a noisy version of the corresponding observations, y, is available; that is, y = y˜ + η, where η is the vector of noise samples. Under the sparse modeling framework, the unknown signal y˜ is modeled as a sparse representation in terms of a specific known dictionary Ψ, that is, y˜ = Ψθ. Moreover, the dictionary is allowed to be redundant (overcomplete). Then the denoising procedure is realized in two steps. First, an estimate of the sparse representation vector, θ, is obtained via any LASSO formulation, and second, the estimate of the true signal is computed as yˆ = Ψθˆ.

For Exercise 2, you have to reproduce the the denoising results of the case study in Section 9.10. First, extract from the image all the possible sliding patches of size 12 × 12. Confirm that (256 − 12 + 1)2 = 60,025 patches in total are obtained. Next, a dictionary in which all the patches are sparsely represented needs to be designed. Specifically, the dictionary atoms are going to be those corresponding to the two-dimensional redundant DCT transform, and are obtained as follows

(a)     Consider vectors di = [di,1,di,2,...,di,12]>, i = 0,...,13, being the sampled sinusoids of the form

 .

Then make (12×14) matrix D¯, having as columns the vectors di normalized to unit norm; D resembles a redundant DCT matrix.

(b)    Construct the (122 × 142) dictionary Ψ according to Ψ = D ⊗ D, where ⊗ denoted Kronecker product. Built in this way, the resulting atoms correspond to atoms related to the overcomplete 2D-DCT transform.

As a next step, denoise each image patch separately. In particular, assuming that yi is the ith patch reshaped in column vector, estimate a sparse vector θi ∈R196 and obtain the corresponding denoised vector as yˆi = Ψθˆi. Finally, average the values of the overlapping patches in order to form the full denoised image.