Orthogonal Matching Pursuit

Say you have a hundred candidate signals and want a model using only a handful. The lasso approaches this with a single penalized optimization that pushes some coefficients to zero as a side effect. Orthogonal matching pursuit (OMP) instead builds the sparse model one variable at a time, explicitly, by repeatedly asking "which remaining feature explains the most of what I haven't explained yet?"

The analogy: assembling witnesses one at a time

Reconstructing an event by calling witnesses one by one, you first find whoever's account covers the most of the story. Then you look specifically for whoever best explains the parts the first witness left out — no point in a second witness who repeats the first. You repeat this, re-checking the combined story each time, stopping once enough witnesses explain the whole thing.

The mechanics: pick, project, subtract, repeat

Start with residual $r^{(0)} = y$. At each step: pick the feature most correlated with the current residual, $j^* = \arg\max_j |x_j^\top r^{(t-1)}|$; add it to the active set; refit $y$ by OLS on all active features; recompute the residual from that refit.

In plain English: at every round OMP finds whatever remaining signal best explains the error the current model still makes, adds it, then redoes the whole regression on everyone selected so far — the refitting keeps the residual uncorrelated with everything already picked, so the algorithm never wastes a pick on redundant information.

Worked example: three rounds of picking

With target $y$ and three candidates — momentum, value, volume — round 1 selects momentum (highest raw correlation with $y$) and refits, leaving residual $r^{(1)}$. Round 2 correlates value and volume with $r^{(1)}$, not $y$: value now wins, even if volume was individually more correlated with raw $y$, because volume largely duplicates what momentum already explains. Refitting on {momentum, value} gives $r^{(2)}$. If a stopping rule caps the model at two features, volume is never included — everything it offered was already captured once value came in.

Step through the trajectory above: each step moves toward whatever direction most reduces the current error, exactly the "explain what's left" logic OMP applies to picking features rather than positions.

What this means in practice

OMP gives a small, explicit, auditable feature set with a clear step-by-step story for each inclusion — useful when you need to explain a signal-selection process to a risk committee. Being greedy, it can't undo an early pick that turns out poor once later features are added, unlike the lasso's full solution path.