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)yVert^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)$.
No comments:
Post a Comment