Why are solution to ridge regression always expressed using matrix notation?

Question

Consider the following ridge regression problem: minimize the loss function $$\sum_{i=1}^n ||y_i - w^T x_i||_2^2 + \lambda ||w||_2^2$$ with respect to the weight vector $w$. Taking derivative with respect to $w$, I get $$\sum_{i=1}^n 2(y_i - w^T x_i)(-x_i) + 2\lambda w$$ which implies $$w =(\sum_{i=1}^n (y_i - w^T x_i)(x_i)) / 2\lambda. $$ Is this wrong? I know that the solution is $$(X^TX - \lambda I)^{-1}X^Ty.$$

Answer 1

Your derivative is okay. Just remember to put all the $w$-terms on the same side of the equation $$\eqalign{ \sum_i x_i y_i &= \lambda w + \sum_i x_i x_i^Tw \cr }$$ Then pull $w$ out of the summation, since it's independent of $i$ $$\eqalign{ \sum_i y_i x_i &= \Big(\lambda I + \sum_i x_ix_i^T\Big)w \cr }$$ At this point, dispose of the summations in favor of matrix notation $$\eqalign{ X^Ty &= \big(\lambda I + X^TX\big)w \cr }$$ where $x_i$ is the $i^{th}$ column of $X,\,$ and $\,y_i$ is the $i^{th}$ component of $y$.

Answer 2

Your solution has $w$ on both sides of the equation, and furthermore, $w$ is inside the summation, which is a problem.

I recommend taking a look at section 2 of Andrew Ng's CS 229 course notes. In short, using matrix math allows you to use properties of the gradient of a trace, which allows for a straightforward derivation. Note that his course notes are for standard least squares, but getting ridge regression is basically the same.

Answer 3

I think you are asking something different to the question title than in your post body.

Regarding the question in the title:

Most algorithms needed to be coded. Using matrix notation greatly simplifies the coding as well as emphasizes the points that the algorithm can be immediately vectorized (take advantage of linear algebra libraries). Also less indexing usually translates in less typing which is always welcome. :)

Regarding the question in the post:

1. Usually one expresses this cost function with a $\frac{1}{2}$ scalar ahead of it exactly to get rid of the $2$'s in the expression.
2. Usually the expression is $(X^T X + \lambda I)^{-1}X^Ty$ (notice the sign of $\lambda$). You use "$+$" in your original expression but "$-$" afterwards.
3. See the great answers by whuber and Brian Borchers here and here respectively. They use matrix notation to derive the ridge regression problem.
4. You essentially want to take advantage of the following notational property to go from scalar to matrix notation: $\sum_{i}^n (y_i - X_i w)^2 = (y -Xw)^T (y-Xw)$. (Similarly $\lambda ||w||_2^2 = \lambda w^T w$.)
5. No you are not wrong. You are really close; just move a sign out of the summation and you are almost there! You want your derivative to equate $-2X^T(y-Xw) + 2\lambda w$ (in matrix notation).