Orthogonal Matching Pursuit (OMP) in Compressive Sensing

1. Introduction

Compressive Sensing (CS) aims to recover a sparse signal from a small number of measurements. In many systems, the measurement process can be expressed as:

y = Q h_b + n

where:

• y: Measurement vector (observed data)
• Q: Known sensing matrix or dictionary
• h_b: Sparse vector (unknown signal to estimate)
• n: Noise

Orthogonal Matching Pursuit (OMP) is a greedy algorithm that reconstructs h_b by iteratively selecting the columns of Q that best match the measurements y.

---

2. OMP Algorithm Overview

The OMP process proceeds as follows:

1. Initialization: Set residual r⁽⁰⁾ = y and selected index set S = ∅.
2. Correlation: Compute correlations of all columns with the current residual:
   c_i = q_i^T r^(k)
3. Select: Choose the column with the maximum absolute correlation:
   i(k+1) = argmax |c_i|
4. Update Support: Add the selected index to the set S.
5. Least Squares Estimate: Solve for the coefficients of the selected columns:
   h_b^(k+1) = (Q_(S)^T Q_(S))^-1 Q_(S)^T y
6. Residual Update:
   r^(k+1) = y - Q_(S) h_b^(k+1)
7. Stopping Criterion: Stop when the residual norm is small or when the desired sparsity level is reached.

---

3. Example from Slides

Consider the example matrix:

Q = ⎡1 0 1 0 0 1⎤
⎡0 1 1 1 0 0⎤
⎡1 0 1 0 1 0⎤
⎡0 1 0 1 1 1⎤

and measurement vector:

y = [0 2 3 5]^T

Iteration 1

• Compute correlations c = Q^Ty.
• The column with the largest correlation is q₅, so i(1) = 5.
• Estimate coefficient using least squares with Q₍₁₎ = [q₅].

Iteration 2

• Compute new residual r⁽¹⁾ and new correlations.
• Next selected column: i(2) = 2.
• Submatrix:
  Q₍₂₎ = [q₅ q₂] = ⎡0 0⎤
  ⎡0 1⎤
  ⎡1 0⎤
  ⎡1 1⎤
• Compute new coefficients:
  h_b⁽²⁾ = (Q₍₂₎^T Q₍₂₎)^-1 Q₍₂₎^T y = [3 2]^T

Final Sparse Vector

ĥ_b = [0 2 0 0 3 0]^T

The reconstructed signal has only two nonzero elements → the signal is sparse.

---

4. Interpretation of Q

In this example, the matrix Q is not the actual channel matrix. Rather, it represents how the sparse channel vector is mapped to the received signal. In mmWave MIMO systems:

y = (X^T ⊗ W^H) (A_t^* ⊗ A_r) h_b + n

Here:

• A_t – Transmit array response (dictionary of transmit directions)
• A_r – Receive array response
• X – Transmit pilot matrix
• W – Receive combiner matrix

Thus, we define:

Q = (X^T ⊗ W^H) (A_t^* ⊗ A_r)

Therefore, Q depends on the beamforming and pilot structure, not on the channel itself. The channel is represented by h_b, which is sparse in the beamspace domain.

---

5. Summary

Quantity	Meaning
H	Physical MIMO channel matrix
hb	Sparse beamspace channel vector
Q	Sensing (measurement) matrix derived from array and pilot structure
y = Qhb	Measurement equation used in OMP
OMP	Greedy algorithm selecting the most correlated columns of Q iteratively

In summary, OMP reconstructs the sparse vector h_b from the measurements y by selecting the most relevant columns of Q in each iteration. In mmWave systems, this allows efficient estimation of the sparse channel using a small number of pilots.

Further Reading

1.