Orthogonal matching pursuit

Explain a signal with as few atoms as possible

Given a dictionary D whose columns are candidate features (or atoms), and a target y, we want a coefficient vector with only a few nonzero entries. Orthogonal matching pursuit (OMP) builds that support one column at a time.

Implement omp(D, y, k). It returns a coefficient vector of length d with at most k nonzero entries.

1. Start with an empty support and residual r = y.
2. Pick the column with the largest absolute inner product |D^T r| among columns not yet selected. Ties go to the smallest index.
3. Solve least squares of y on the selected columns. Update the residual to y - D_S x_S.
4. Repeat k times, then write the least-squares coefficients into their positions.

Constraints

• D is 2-D with n rows, y has length n.
• 0 <= k <= d, otherwise raise ValueError.
• k = 0 returns all zeros.
• Do not modify the inputs.

Hints