Why is the solution the eigenvector corresponding to the smallest eigenvalue of of (A^T)A?
motoole2
The goal here is to minimize the objective $||A x ||^2 = x^T A^T A x$ subject to $||x||^2 = 1$. In order to find the $x$ that minimizes this objective, we compute the derivative of our objective with respect to $x$, set the result to $0$, and then solve for $x$.
After computing the derivative and setting the result to zero, we get the following expression: $2 A^T A x = 0$. The solution to this expression will be given by the smallest eigenvector of $A^T A$.
ADog
Thanks for the explanation! As a followup, does the solution always yield $2A^TAx = 0$, or does it just give the closest result to 0?
motoole2
To keep the math simple, my explanation above assumed that $A^T A$ is not full rank, and therefore that there always exists an $x$ such that $2A^TAx = 0$. In general, this is not always the case, so we have to be a little more careful.
A more precise explanation would involve rewriting the optimization problem $\min ||Ax||$ s.t. $||x||=1$ using the method of Lagrange multipliers as follows: $x^T A^T A x - \lambda (1 - x^T x)$ (done to find the minima of an objective function subject to equality constraints). Next, we can compute its derivatives with respect to $x$: $2 A^T A x - 2\lambda x = 0$, or equivalently $A^T A x = \lambda x$. The critical points (solutions to this equation) are given by eigenvectors $x$ and eigenvalues $\lambda$. Moreover, the eigenvector $x$ that minimizes the objective $||Ax||^2 = x^T A^T A x = \lambda x^T x = \lambda ||x|| = \lambda$ is the smallest of the eigenvectors.
motoole2
Oh! I suppose that I should also answer the question explicitly. :-) This solution will give the closest result to 0.
Why is the solution the eigenvector corresponding to the smallest eigenvalue of of (A^T)A?
The goal here is to minimize the objective $||A x ||^2 = x^T A^T A x$ subject to $||x||^2 = 1$. In order to find the $x$ that minimizes this objective, we compute the derivative of our objective with respect to $x$, set the result to $0$, and then solve for $x$.
After computing the derivative and setting the result to zero, we get the following expression: $2 A^T A x = 0$. The solution to this expression will be given by the smallest eigenvector of $A^T A$.
Thanks for the explanation! As a followup, does the solution always yield $2A^TAx = 0$, or does it just give the closest result to 0?
To keep the math simple, my explanation above assumed that $A^T A$ is not full rank, and therefore that there always exists an $x$ such that $2A^TAx = 0$. In general, this is not always the case, so we have to be a little more careful.
A more precise explanation would involve rewriting the optimization problem $\min ||Ax||$ s.t. $||x||=1$ using the method of Lagrange multipliers as follows: $x^T A^T A x - \lambda (1 - x^T x)$ (done to find the minima of an objective function subject to equality constraints). Next, we can compute its derivatives with respect to $x$: $2 A^T A x - 2\lambda x = 0$, or equivalently $A^T A x = \lambda x$. The critical points (solutions to this equation) are given by eigenvectors $x$ and eigenvalues $\lambda$. Moreover, the eigenvector $x$ that minimizes the objective $||Ax||^2 = x^T A^T A x = \lambda x^T x = \lambda ||x|| = \lambda$ is the smallest of the eigenvectors.
Oh! I suppose that I should also answer the question explicitly. :-) This solution will give the closest result to 0.
That makes sense, thanks!