Description
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. [32 points = 2 points for
each of the 16 questions]
2. Consider compressive measurements y = Φx + η of a purely sparse signal x, where kηk2 ≤ . 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 kx˜ − xk2 = kΦ
†
S
ηk2 ≤ kΦ
†
S
k2kηk2. Here Φ
†
S , (Φ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 kXk2. [3 points]
(c) Argue that the largest singular value of Φ
†
S
lies between 1
√
1 + δ2k
and 1
√
1 − δ2k
where k = |S| and δ2k
is the RIC of Φ of order 2k. [4 points]
(d) This yields
√
1 + δ2k
≤ kx − x˜k2 ≤
√
1 − δ2k
. Argue that the solution given by Theorem 3 is only a
constant factor worse than this solution. [3 points]
3. 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]
4. Here is our obligatory Google search question :-). Your task is to search the web for papers that used some
technique of sensing matrix design (eg: coherence minimization, RIC minimization, or any other) to improve
the performance of a practical compressive imaging system. (Hint: Look at the archives of journals such as
IEEE Transactions on Computational Imaging, IEEE Transactions on Image Processing, Applied Optics or
the webpages of authors such as David Brady or Gonzalo Arce). To answer this question, do the following:
(a) Mention the title, venue, author list publication year of the paper. Put a link to it.
1
(b) Briefly describe the imaging system in the paper; you may refer to figures from the paper itself or refer
to lecture slides.
(c) Write the mathematical expression for the matrix quality measure being optimized in the paper, along
with various contraints on the matrix (eg: non-negative elements, block diagonal, etc.).
(d) Mention the optimization technique.
(e) Briefly describe the improvements due to this design as compared to a random design. You may refer
to tables or graphs from the paper itself.
[3 +3 + 3 + 3 + 3 =15 points]
5. Consider the problem P1: minxkxk1 s. t. ky − Φxk2 ≤ . Also consider the LASSO problem which seeks to
minimize the cost function J(x) = ky − Φxk
2
2 + λkxk1. If x is a minimizer of J(.) for some value of λ > 0,
then show that there exists some value of for which x is also the minimizer of the problem P1. [15 points]
(Hint: Consider
0 = ky − Φxk2. 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
0
.)
6. Suppose there are n subjects being tested by Dorfman pooling and only k n out of these are infected. In
the first round, assume that the n subjects are divided into groups of size g each. For simplicity, assume
n/g is an integer. Derive a formula for the average number of tests required to be performed in Dorfman
pooling. What is the worst case? What is the optimal group size in the worst case? [15 points]
2