Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I've seen it claimed that the solution to the minimization problem:
$$\begin{align*} \arg \min_{b} \quad & {\left\| A b \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| b \right\|}_{2} = 1 \end{align*}$$
is given by first finding the singular value decomposition of A, $$\textbf{A} = \bf{U \Sigma V}$$ And then taking the column of $\bf{V}$ corresponding to the smallest singular value.
Can someone present a proof that this is so?
Norm $\| \cdot \|$ is invariant under unitary transformation so:
$$\|Ab\| =\| U\Sigma V^* b\| = \|\Sigma b'\|$$
Where $b' = V^* b$, so $\|b'\| = \|V^* b\| = \|b\| = 1$.
Next we have that:
$$\text{argmin}_b \|\Sigma V^* b\| = V\text{argmin}_{b'} \| \Sigma b' \|$$
This is because $V^*$ maps unit sphere onto unit sphere.
And that $b'$ which minimizes $\|\Sigma b'\|$ is $(0,\dots,0,1)^T$.
Finally $V (0,\dots,0,1)^T$ is equal to the last column of $V$.
Note that if $A = U\Sigma V$, then $A^* A = V^*\Sigma^*U^*U\Sigma V = V^*\Sigma^*\Sigma V$. Therefore, the eigenvalues of $A^*A$ are equal to square of the absolute values of the singular values of $A$. Also the minmization problem can be seen as $$ \underset{b: \;||b||=1}{argmin} \; ||Ab||= \underset{b: \;||b||=1}{argmin}\;||Ab||^2 = \underset{b: \;||b||=1}{argmin}\; b^*(A^*A) b $$ This is equivalent to finding the eigenvector corresponding to the minimum eigenvalue of $A^TA$, which is precisely the column in $V$ corresponding to the minimum eigenvalue in the diagonal matrix $\Sigma^*\Sigma$ (which is in turn the absolute square of the minimum singular value of $A$).
