CS 754 -  Assignment 2 Solved

 Advanced Image Processing

1. Refer to a copy of the paper ‘The restricted isometry property and its implications for compressed sensing’ in the homework folder. Your task is to open the paper and answer the question posed in each and every green-colored highlight. The task is the complete proof of Theorem 3 done in class. [24 points = 1.5 points for each of the 16 questions]

2. Your task here is to implement the ISTA algorithm for the following three cases:

(a)   Consider the image from the homework folder. Add iid Gaussian noise of mean 0 and variance 4 (on a [0,255] scale) to it, using the ‘randn’ function in MATLAB. Thus y = x + η where η .V(0, 4). You should obtain x from y using the fact that patches from x have a sparse or near-sparse representation in the 2D-DCT basis.

(b)   Divide the image shared in the homework folder into patches of size 8 x 8. Let xi be the vectorized version of the ith patch. Consider the measurement yi = 4xi where 4 is a 32 x 64 matrix with entries drawn iid from .V(0, 1). Note that xi has a near-sparse representation in the 2D-DCT basis U which is computed in MATLAB as ‘kron(dctmtx(8)’,dctmtx(8)’)’. In other words, xi = UOi where Oi is a near-sparse vector. Your job is to reconstruct each xi given yi and 4 using ISTA. Then you should reconstruct the image by averaging the overlapping patches. You should choose the a parameter in the ISTA algorithm judiciously. Choose A = 1 (for a [0,255] image). Display the reconstructed image in your report. State the RMSE given as IX(:) - ˆX(:)I2/IX(:)I2 where Xˆ is the reconstructed image and X is the true image. [16 points]

(c)   Repeat the reconstruction task using the Haar wavelet basis via the MATLAB command ‘dwt2’ with the option ‘db1’. Display the reconstructed image in your report. State the RMSE. Use MATLAB function handles carefully. [8 points]

(d)   Consider a 100-dimensional sparse signal x containing 10 non-zero elements. Let this signal be convolved with a kernel h = [1,2,3,4,3,2, 1]/16 followed by addition of Gaussian noise of standard deviation equal to 5% of the magnitude of x to yield signal y, i.e. y = h * x + η. Your job is to reconstruct x from y given h. Be careful of how you create the matrix A in the ISTA algorithm. [8 points]

3. One of the questions that came up in a live session was the notion of an oracle. Consider compressive measurements y = 4x + η of a purely sparse signal x, where IηI2 < €. When we studied Theorem 3 in class, I had made a statement that the solution provided by the basis pursuit problem for a purely sparse

 signal comes very close (i.e. has an error that is only a constant factor worse than) an oracular solution. An oracular solution is defined as the solution that we could obtain if we knew in advance the indices (set S) the non-zero elements of the signal x. This homework problem is to understand my statement better. For this, do as follows. In the following, we will assume that the inverse of ΦT SΦS exists, where ΦS is a submatrix of Φ with columns belonging to indices in S.

(a)  Express the oracular solution x˜ using a pseudo-inverse of the sub-matrix ΦS. [5 points]

(b)  Now, show that l˜x −xl2 = IΦ SηI2 ≤ ~Φ S~2IηI2. Here Φ S 4 (ΦT SΦS)−1ΦT S is standard notation for the pseudo-inverse of ΦS. The largest singular value of matrix X is denoted as X 12. [3 points]

1                            1

(c)  Argue that the largest singular value of Φ S lies between √1 + δ2k and √1 − δ2k where k = |S| and δ2k

is the RIC of Φ of order 2k. [4 points]

€

(d)  This yields  __________________ . Argue that the solution given by Theorem 3 is only a

√1 + δ2k ≤ Ix − ˜x~2 ≤      €

√1 − δ2k

constant factor worse than this solution. [3 points]

4.   If s < t where s and t are positive integers, prove that δs ≤ δt where δs, δt stand for the restricted isometry constant (of any sensing matrix) of order s and t respectively. [8 points]

5.   Here is our obligatory Google search question :-). Your task is to find out any one paper from within the last 5 years, apart from our Tapestry pooling paper from https://arxiv.org/abs/2005.07895, which applied compressed sensing for group testing (not necessarily for COVID-19 pooling, but other applications or even theoretical papers are fine). You may look for references in the Tapestry pooling paper as well. Unpublished papers from arxiv are allowed as well. Answer the following questions: (1) Mention the title of the paper and a link to it. (2) Mention the key objective function being minimized in the paper with the meaning of all symbols clearly explained. (3) Enlist any three differences between the proposed approach and the Tapestry pooling approach. [8+7=15 points]

6.   Consider the problem P1: minxIxI1 s. t. y − ΦxI2 ≤ €. Also consider the LASSO problem which seeks to minimize the cost function J(x) = Iy − ΦxI2 2 + AIxI1. If x is a minimizer of J(.) for some value of A > 0, then show that there exists some value of € for which x is also the minimizer of the problem P1. [6 points] (Hint: Consider €' = Iy − ΦxI2. Now use the fact that x is a minimizer of J(.) to show that it is also a minimizer of P1 subject to an appropriate constraint involving €'.)