Description
1. Let θ
? be the result of the following minimization problem (BP): minkθk1 such that ky −ΦΨθk2 ≤ ε, where
y is an m-element measurement vector, Φ is a m×n measurement matrix (m < n), Ψ is a n×n orthonormal
basis in which n-element signal x has a sparse representation of the form x = Ψθ. Notice that y = Φx + η
and ε is an upper bound on the magnitude of the noise vector η.
Theorem 3 we studied in class states the following: If Φ obeys the restricted isometry property with isometry
constant δ2s <
√
2 − 1, then we have kθ − θ
?k2 ≤ C1s
−1/2kθ − θsk1 + C2ε where C1 and C2 are functions of
only δ2s and where ∀i ∈ S, θsi = θi
; ∀i /∈ S, θsi = 0. Here S is a set containing the indices of the s largest
magnitude elements of θ.
A curious student asks the following questions: ‘(1) It appears that the upper bound on kθ −θ
?k2 is reduced
as s increases, which goes against the very premise of compressed sensing. How do we address this apparent
discrepancy? (2) It also appears that the error bound is independent of m. How do you address this? (3)
Now consider that I gave you another theorem (called Theorem 3A), which is the same as Theorem 3 except
that it requires that δ2s < 0.1. Out of Theorem 3 and Theorem 3A, which is the more useful theorem? Why?
(4) It appears that if I set ε = 0 in BP, I can always reduce the upper bound on the error even if the noise
vector η has non-zero magnitude. Am I missing something? If so, what am I missing?’
Your job is to answer all four of the student’s questions. [5+5+5+5=20 points]
2. We will prove why the value of the coherence between m×n measurement matrix Φ (with all rows normalized
to unit magnitude) and n × n orthonormal representation matrix Ψ must lie within the range [1,
√
n] (both
1 and √
n inclusive). Recall that the coherence is given by the formula
µ(Φ, Ψ) = √
nmaxi∈{0,1,…,m−1},j∈{0,1,…,n−1}
|Φi
tΨj |. Proving the upper bound should be very easy for you.
To prove the lower bound, proceed as follows. Consider a unit vector g ∈ R
n
. We know that it can be expressed as g =
Pn
k=1 αkΨk as Ψ is an orthonormal basis. Now prove that µ(g, Ψ) = √
nmaxi∈{0,1,…,n−1}
|αi
|
Pn
j=1 α
2
j
.
Exploiting the fact that g is a unit vector, prove that the minimal value of coherence is attained when
g =
p
1/nPn
k=1 Ψk and that hence the minimal value of coherence is 1. [10 points]
3. Compressive sensing reconstructions involve estimating a sparse signal x ∈ R
n
, n 2 from a vector y ∈
R
m(m n) of compressed measurements of the form y = Φx where Φ ∈ R
m×n
is the measurement matrix
(assume there is no noise). Now answer the following questions, from first principles. Do not merely quote
theorems or algorithms.
1
(a) If it is known that x has only 1 non-zero element and that the other elements are zero, can you uniquely
estimate x if m = 1? If yes, how? If not, why not? Now further suppose, you knew beforehand the
index (but not the value) of the non-zero element of x? Does this help you any further? If yes, how?
If not, why not?
(b) If it is known that x has only 1 non-zero element and that the other elements are zero, can you uniquely
estimate x if m = 2? If yes, how? If not, why not?
(c) If it is known that x has only 2 non-zero elements and that the other elements are zero, can you uniquely
estimate x if m = 3? If yes, describe an algorithm that is guaranteed to estimate it accurately. If not,
explain why not, and explain whether there are any special instances of Φ for which unique estimation
is possible?
(d) Repeat part (c) with m = 4. [1+2+3+4=10 points]
4. Consider compressive measurements of the form y = Ax + v for sensing matrix A, signal vector x, noise
vector v and measurement vector y. Consider the problem P1 done in class: Minimize kxk1 w.r.t. x such
that ky − Axk2 ≤ e. Also consider the problem Q1: Minimize kAx − yk2 w.r.t. x subject to the constraint
kxk1 ≤ t. Prove that if x is a unique minimizer of P1 for some value e ≥ 0, then there exists some value
t ≥ 0 for which x is also a unique minimizer of Q1. Note that kxk1 and kxk2 stand for the L1 and L2 norms
of the vector x respectively. [15 points] (Hint: Consider t = kxk1 and now consider another vector z with
L1 norm less than or equal to t).
5. Here is our mandatory Google search question. Note that this is the only question for which you can perform
a google search to get the answer. Your task is to search for a research paper which applies compressed sensing
in any one application not covered in class. Some examples include air quality monitoring, optical microscopy,
or any other. Answer the following questions briefly:
(a) Mention the title of the paper, where and when it was published, which venue (name of journal or
conference or workshop) and include a link to the paper.
(b) Very briefly describe the hardware architecture used in the paper. You may refer to figures from the
paper itself.
(c) What reconstruction techhnique or cost function does the paper adopt for the sake of compressive
reconstruction in this application? [3+4+4=10 points]
6. In class, we studied a video compressive sensing architecture from the paper ‘Video from a single exposure coded snapshot’ published in ICCV 2011 (See http://www.cs.columbia.edu/CAVE/projects/single_
shot_video/). Such a video camera acquires a ‘coded snapshot’ Eu in a single exposure time interval u.
This coded snapshot is the superposition of the form Eu =
PT
t=1 Ct
· Ft where Ft
is the image of the scene
at instant t within the interval u and Ct
is a randomly generated binary code at that time instant, which
modulates Ft
. Note that Eu, Ft and Ct are all 2D arrays. Also, the binary code generation as well as the
final summation all occur within the hardware of the camera. Your task here is as follows:
(a) Read the ‘cars’ video in the homework folder in MATLAB using the ‘mmread’ function which has been
provided in the homework folder and convert it to grayscale. Extract the first T = 3 frames of the
video.
(b) Generate a H × W × T random code pattern whose elements lie in {0, 1}. Compute a coded snapshot
using the formula mentioned and add zero mean Gaussian random noise of standard deviation 2 to it.
Display the coded snapshot in your report.
(c) Given the coded snapshot and assuming full knowledge of Ct for all t from 1 to T, your task is to
estimate the original video sequence Ft
. For this you should rewrite the aforementioned equation in the
form Ax = b where x is an unknown vector (vectorized form of the video sequence). Mention clearly
what A and b are, in your report.
(d) You should perform the reconstruction using Orthogonal Matching Pursuit (OMP). For computational
efficiency, we will do this reconstruction patchwise. Write an equation of the form Ax = b where x
represents the i
th patch from the video and having size (say) 8×8×T and mention in your report what
2 CS 754
A and b stand for. For perform the reconstruction, assume that each 8 × 8 slice in the patch is sparse
or compressible in the 2D-DCT basis. Carefully work out the error term in the OMP algorithm, and
explain this in your report!
(e) Repeat the reconstruction for all overlapping patches and average across the overlapping pixels to
yield the final reconstruction. Display the reconstruction and mention the relative mean squared error
between reconstructed and original data, in your report as well as in the code.
(f) Repeat this exercise for T = 5, T = 7 and mention the mention the relative mean squared error between
reconstructed and original data again.
(g) Note: To save time, extract a portion of about 120 × 240 around the lowermost car in the
cars video and work entirely with it. In fact, you can show all your results just on this
part. Some sample results are included in the homework folder.
(h) Repeat the experiment with any consecutive 5 frames of the ‘flame’ video from the homework folder.
[35 points = 18 points for successful OMP implementation + 7 points for carefully presenting error term
bound + 10 points for displaying of all results]
3 CS 754
