Orthogonal Matching Pursuit (OMP) in MATLAB

 

MATLAB Code

clc; clear; close all;

% Given measurement matrix Q (4x6)
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];

% Given measurement vector y (4x1)
y = [0; 2; 3; 5];

% Sparsity level (number of nonzero entries to find)
L = 2; % you can adjust this based on expected sparsity

% --- OMP Algorithm ---
r = y; % Initial residual
support = []; % Index set
x_hat = zeros(size(Q, 2), 1); % Sparse solution initialization

for l = 1:L
% Step 1: Find column most correlated with residual
proj = abs(Q' * r);
[~, idx] = max(proj);
support = unique([support, idx]);

% Step 2: Solve LS for chosen support
Qs = Q(:, support);
x_s = pinv(Qs) * y;

% Step 3: Update residual
r = y - Qs * x_s;

% Optional stopping condition
if norm(r) < 1e-6
break;
end
end

% Step 4: Construct full sparse vector
x_hat(support) = x_s;

% Display results
disp('Selected atom indices (support):');
disp(support);
disp('Recovered sparse signal x_hat:');
disp(x_hat);
disp('Residual norm:');
disp(norm(r));

 

Output 

Selected atom indices (support):
     2     5

Recovered sparse signal x_hat (estimated transmitted signal):
         0
    2.0000
         0
         0
    3.0000
         0

Residual norm:
   1.1102e-15 

 

Further Reading

1.