OMP for sparse signal recovery

Ortogonal Matching Pursuit for recovering sparse signals

application areas:

• sparse signal recovery
• template matching /measuring similarity with respect to a dictionary (dictionary could be built from samples of one class)
• outlier detection/ one-class classification (by setting a threshold)

Example python codes consists of solving coeffients using OMP and measure the reconstruction error using cosine similarity

from sklearn.linear_model import OrthogonalMatchingPursuit
import numpy as np

# find coef such as y = X * coef, coef is n_nonzero_coefs sparse
def cal_coeff_omp(X, y , n_nonzero_coefs, normalization = True):
    omp = OrthogonalMatchingPursuit(n_nonzero_coefs=n_nonzero_coefs, normalize=normalization)
    omp.fit(X, y)
    coef = omp.coef_
    return coef

# calculate the cosine similarity between y and y_hat
def cosine_similarity(y_hat, y):

    cos_sim = (np.matmul(y_hat.T, y)) / \
                ((np.matmul(y_hat.T, y_hat)) ** (0.5) * \
                 (np.matmul(y.T, y)) ** 0.5)
    return cos_sim

We simulate the dictionary $X$. We give the algorithm the exact sparsity of coefficient that generates $y$. Here are $20$ realizations how varying the added noise power affected the reconstruction similarity.