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)$.


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$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.