= Solution
An error of order $\epsilon$ in a squared <singular value> can become an error of order $\sqrt\epsilon$ after taking its square root. To keep $A$ nonsingular as required, take $0<\epsilon<1/2$ and
$$
A=\operatorname{diag}(1,\epsilon),\qquad
\widehat V=I_2,\qquad
\widehat\Sigma=\operatorname{diag}(1,\sqrt{\epsilon^2+\epsilon}).
$$
Then $\|A\|_2=1$, and the computed <eigendecomposition> has exactly the permitted <backward error>:
$$
\|A^TA-\widehat V\widehat\Sigma^2\widehat V^T\|_2
=\|\operatorname{diag}(0,-\epsilon)\|_2=\epsilon.
$$
Nevertheless the second computed <singular value> has error
$$
\sqrt{\epsilon^2+\epsilon}-\epsilon
=\sqrt\epsilon\bigl(\sqrt{1+\epsilon}-\sqrt\epsilon\bigr)
\sim\sqrt\epsilon.
$$
By the <singular value perturbation bound>, every product with these computed <singular values> and exactly <orthonormal> outer factors has <spectral norm> error at least this large. In particular, even the favorable choice $\widehat U=I_2$ gives
$$
\boxed{\|A-\widehat U\widehat\Sigma\widehat V^T\|_2
=\sqrt{\epsilon^2+\epsilon}-\epsilon\sim\sqrt\epsilon},
$$
which has no uniform $O(\epsilon)$ bound in <big O notation>. Therefore <backward stability> for the <eigendecomposition> of the <Gram matrix> does not imply <backward stability> for the <singular value decomposition>.
There is a related loss of <orthonormality> in the raw formula: evaluating $A\widehat V\widehat\Sigma^{-1}$ exactly for these perturbed factors gives $\operatorname{diag}(1,\epsilon/\sqrt{\epsilon^2+\epsilon})$, whose second column has length tending to zero. Its product with $\widehat\Sigma\widehat V^T$ equals $A$, but its diagonal factors are consequently not a <singular value decomposition>. The paper's idealized <orthonormality> assumption lets us isolate the unavoidable <singular value> error even if this additional problem is repaired.
Back to article page
