5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.