Question

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_C = X_C (X_C' X_C)^{-1} X_C'$. Squared error using columns indexed by C can be computed as $RSS(C) := y'(I_n - X_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_j'X_j)^{-1} (I_n - H_C) X_j X_j' (I_n -H_C)')(I_n - H_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_n - H_C)$.

Answer 1

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$