 Solution

An error of order $ϵ$ in a squared singular value can become an error of order $\sqrt{ϵ}$ after taking its square root. To keep $A$ nonsingular as required, take $0<ϵ<1/2$ andThen $\Vert A{\Vert }_2=1$, and the computed eigendecomposition has exactly the permitted backward error:Nevertheless the second computed singular value has errorBy 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 $\hat{U}=I_2$ giveswhich has no uniform $O(ϵ)$ 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\hat{V}{\hat{\Sigma }}^{-1}$ exactly for these perturbed factors gives $\mathrm{diag}(1,ϵ/\sqrt{{ϵ}^2+ϵ})$, whose second column has length tending to zero. Its product with $\hat{\Sigma }{\hat{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.