What is the proof that SVM can be used to solve the least squares problem with norm equality constraint?

Question

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?

Answer 1

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$.

Answer 2

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$).