# Question about orthogonal matching pursuit

Let y be a n-vector, X a n-by-p matrix of full rank (p < n) and b a p-vector, so that y = Xb + e, for some noise vector e. I am not sure how to show reduction of error in orthogonal matching pursuit method at some step k.

More precisely, let H_C be a projection matrix defined by the columns of X indexed by the set $C \subset \{1, ..., p\}$ of cardinality k, i.e. $H&#95;C = X&#95;C (X&#95;C' X&#95;C)^{-1} X&#95;C'$. Squared error using columns indexed by C can be computed as $RSS(C) := y'(I&#95;n - X&#95;C)y$, where I_n is the identity matrix. Next, the procedure selects the column of X (say column j) that is not in C, so that $RSS(C \cup \{j\})$ is minimized over j. Let $D := C \cup \{j\}$.

My question is how to rigorously show that $$RSS(C) - RSS(D) = \Vert((X&#95;j'X&#95;j)^{-1} (I&#95;n - H&#95;C) X&#95;j X&#95;j' (I&#95;n -H&#95;C)')(I&#95;n - H&#95;C)y\Vert^2\ ?$$

Intuitively, y is projected into the space orthogonal to the space spanned by columns indexed by C, which gives residuals after the step k. Next, a new column is chosen so that the decrease in RSS is maximal. This decrease in RSS is computed by projecting residuals onto the space spanned by $X_j(I&#95;n - H&#95;C)$.

-

## 1 Answer

Hi, I have been puzzled by the same problem for a long time and I finally got to a solution which i hope is rigorous enough; but if you find anything wrong with it let me know. We want to solve the following least-squares problem: $min w.r.t. x, \alpha,$ $|| y- X_C x - X_j\alpha||^2$

To solve the above differentiate partially w.r.t $\alpha$ and x and solve the resulting equations simultaneously. You get $\alpha = X_j^T(I-H_C)y/|| (I-H_c)X_j||^2$

and $X_c*x= H_c*(y-X_j*\alpha)$

So net projection $= X_c*x + X_j * \alpha = H_c* y + (I-H_c)*X_j*\alpha$ and so error after projecting= $y - X_C* x - X_j*\alpha = = (I-H_C)*y - (I-H_C)*X_j*\alpha$ So $RSS(D)= RSS(C) + \alpha^2 *||(I-H_C)*X_j||^2-2*\alpha*|y^T*(I-H_C)*X_j|$ $RSS(D)=RSS(C)- |y^T*(I-H_C)*X_j|^2/||(I-H_C)*X_j||^2$ $RSS(C)-RSS(D)=|y^T*(I-H_C)*X_j|^2/||(I-H_C)*X_j||^2$

-