Math 6420 • PDE

Consider the error function
\[
  E(\mathbf{w})=\sum_{p=1}^{P}(y_p-\mathbf{w}\cdot\mathbf{x}_p)^2
\]
where \(\mathbf{w}\) and \(\mathbf{x}_p\) are \(N\)-component vectors, \(N\ge P\), and
\(y_p,\mathbf{x}_p\) are prescribed.
\begin{enumerate}
\item[(a)] Show that if \(\mathbf{w}_0\) is a minimizer of \(E\) then
\[
  [X^TX]\mathbf{w}_0=X^T\mathbf{y}
\]
where \(X_{pj}=[\mathbf{x}_p]_j\), \(j=1,\ldots,N\), \(X^T\) is the transpose of the matrix \(X\),
and \(\mathbf{y}=(y_1,\ldots,y_P)^T\).
\item[(b)] Suppose that the weight vector \(\mathbf{w}\) is updated at each time step \(m\)
using the gradient decent algorithm
\[
  w_j(m+1)=w_j(m)-\eta\frac{\partial E(\mathbf{w}(m))}{\partial w_j(m)}.
\]
Show that \(\mathbf{w}(m)\to\mathbf{w}_0\) as \(m\to\infty\) provided that the rate parameter
\(\eta\) satisfies
\[
  |1-\eta\lambda_j|<1,\qquad j=1,\ldots,N
\]
where \(\lambda_j\) are the eigenvalues of the symmetric \(N\times N\) matrix \(X^TX\).
[Hint: Explicitly calculate \(\partial E/\partial w_j\), use part (a) to rewrite the
difference equation in terms of \(\Delta\mathbf{w}(m)=\mathbf{w}(m)-\mathbf{w}_0\), and then
diagonalize. Assume that \(X^TX\) is invertible so that \(\mathbf{w}_0\) is unique].
\end{enumerate}