Description
- Problem 1: Orthogonal Complement of a Subspace. Suppose that V is a subspace of Rn. Let
V⊥ = {x ∈ Rn : xTy = 0, ∀y ∈ V}
be the set of vectors orthogonal to every element in V.
- Verify that V⊥ is a subspace of Rn.
- Suppose that V = span(v1, v2, . . . , vk) for some v1, v2, . . . , vk ∈ Rn. Express V and V⊥
as subspaces induced by the matrix A Rn×k and its transpose
AT.
- Show that (V⊥)⊥ = V.
- Show that dim(V) + dim(V⊥) = n.
- Show that V ⊆ W for another subspace W implies W⊥ ⊆ V⊥.
- Show that every x ∈ Rn can be expressed uniquely as x = v + v⊥, where v ∈ V and v⊥ ∈ V⊥. (Hint: Let v be the projection of x on V.)
- Problem 2: Projection Matrices. A symmetric matrix P = PT ∈ Rn×n is said to be a projection matrix if P = P2.
*For more information on Academic Integrity Policies at UCSD, please visit http://academicintegrity.ucsd.
edu/excel-integrity/define-cheating/index.html
- Show that if P is a projection matrix, then so is I − P.
- Suppose that the columns of U ∈ Rn×k are orthonormal. Show that UUT is a projection matrix.
- Suppose that A ∈ Rn×k is full-rank with k ≤ n. Show that A(ATA)−1AT is a projection matrix.
- Recall from lectures that the point y ∈ S ⊆ Rn closest to x ∈ Rn is said to be the orthogonal projection (or projection in short) of x onto S. Show that if P is a projection matrix, then y = Px is the projection of x onto R(P).
- Let u be a unit vector (A unit vector is a vector normalized by its norm). Find the projection matrix P such that y = Px is the projection of x onto span(u).
Programming Assignment:
Finding Sparse Solutions via Orthogonal Matching Pursuit (OMP)
In this mini project, we will implement and study the performance of the Orthogonal Matching Pursuit (OMP) algorithm for recovering sparse signals and images.
Required Reading: Read the paper “Greed is good: algorithmic results for sparse approximation” by Joel Tropp to learn about OMP (available on Canvas under Files>Homework), and relevant lectures and discussion sessions. For this assignment, you will mainly need to understand the algorithm (and not the proofs concerning the theoretical performance guarantees of OMP), although you are certainly encouraged to go over them and discuss with Prof. Pal if you are interested.
Consider the measurement model
y = Ax + n
where y ∈ RM is the (compressed, M < N) measurement, A ∈ RM×N is the measurement matrix, and n ∈ RN is the additive noise. Here, x ∈ RN is the unknown signal (to be estimated) with s ≪ N non-zero elements. The indices of the non-zero entries of x (also known as the support of x) is denoted by S = {i|xi ̸= 0}, with |S| = s.
- Performance Metrics: Let xˆ be the estimate of x obtained from OMP. To measure the performance of OMP, we consider the Normalized Error defined as
The average Normalized Error is obtained by averaging the Normalized Error over 2000 Monte Carlo runs.
- Experimental setup:
- Generate A as a random matrix with independent and identically distributed entries drawn from the standard normal distribution. Normalize the columns of A.
- Generate the sparse vector x with random support of cardinality s (i.e. s indices are generated uniformly at random from integers 1 to N), and non-zero entries drawn as uniform random variables in the range [−10, −1] ∪ [1, 10].
- The entries of noise n are drawn independently from the normal distribution with standard deviation σ and zero mean.
- For each cardinality s ∈ [1, smax], the average Normalized Error should be computed by repeating step (a) to step (c) 2000 times and averaging the results over these 2000 Monte Carlo runs.
- Noiseless case: (n = 0)
Implement OMP (you may stop the OMP iterations once ∥y − Ax(k)∥2 is close to 0 and evaluate its performance. Calculate the probability of Exact Support Recovery (i.e. the fraction of runs when Sˆ = S) by averaging over 2000 random realizations of A, as a function of M and smax (for different fixed values of N). For each N, the probability of exact support recovery is a two dimensional plot (function of M and smax) and you can display it as an image. The resulting plot is called the “noiseless phase transition” plot, and it shows how many measurements (M) are needed for OMP to successfully recover the sparse signal, as a function of smax. Do you observe a sharp transition region where the probability quickly transitions from a large value (close to 1) to a very small value (close to 0)? Generate different phase transition plots for the following values of N: 20, 50 and 100. Regenerate phase transition plots for average Normalized Error (instead of probability of successful recovery). Comment on both kinds of plots.
- Noisy case: (n ̸= 0)
- Assume that sparsity s is known. Implement OMP (terminate the algorithm after first s columns of A are selected). Generate “noisy phase transition” plots (for fixed N and σ) where success is defined as the event that the Normalized Error is less than 10−3. Repeat the experiment for two values of σ (one small and one large) and choose N as 20, 50 and 100. Comment on the results.
- Assume the sparsity s is NOT known, but ∥n∥2 is known. Implement OMP where you may stop the OMP iterations once ∥y − Ax(k)∥ ≤ ∥n∥2). Generate phase transition plots using the same criterion for success as the previous part. Comment on the results.
- Decode a Compressed Message: In this part of the assignment, you will uncover a hidden message from their compressed sketches (generated using random measurement matrices) using the OMP algorithm that seeks the sparsest solution. An unknown and sparse image X, containing a message, has been compressed using three different random matrices (of different sizes) A1, A2, A3 to produce three corrupted images as follows
Yi = AiX
The corrupted images and the measurement matrices are provided to you under Files>Homework.
- Can you guess the message by simply displaying the compressed images?
- Using OMP, recover X from Y1, Y2, Y3. Figure out the appropriate stopping criteria. Reshape the recovered X into a 2D image of size 90 × 160 and decode the message. Show your results for each case. Compare these results with the Least Squares Solution.
- Which corrupted image gave you the best result for OMP? Can you explain why?
- (For Fun) Can you make an (educated) guess about the meaning of this message?
