Lab 5
Sparsity Aware Learning
Advanced Machine Learning DATA 442/642
Exercise 1
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.
