[Solved] CS 754 Assignment 2

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:

• 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.
• Divide the image shared in the homework folder into patches of size 8 x Let xi be the vectorized version of the i^th 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]
• 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]
• 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 II2 < . 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 SS exists, where S is a submatrix of with columns belonging to indices in S.

• Express the oracular solution x using a pseudo-inverse of the sub-matrix S. [5 points]
• Now, show that lx xl2 = I SI2 ~ _S~2II2. Here _S 4 (^T SS)1T _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

• 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]

• 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 [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: min_xIxI1 t. y xI2 . Also consider the LASSO problem which seeks to minimize the cost function J(x) = Iy xI2 ₂ + 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 .)