0
$\begingroup$

Looking around at various proofs of the singular value decomposition, I have seen two main approaches:

  1. The first looks at the "maximal stretching" of the unit sphere under a linear map $T\colon V \to U$, i.e. the vector $v \in V$ with $\|v\| = 1$ for which the "stretching" $\|Tv\|$ is largest. Once we find this vector, we ignore the subspace spanned by this vector and continue inductively in the orthogonal complement.

    I have seen this approach taken in Trefethen and Bau's Numerical Linear Algebra and this blog post.

  2. The second applies the spectral theorem to $\sqrt{T^*T}$ (or $T^*T$) to get an orthonormal basis of $V$. Then we define vectors in $U$ and show that they are orthonormal and the whole thing has the SVD property.

    I have seen this approach taken in Axler's Linear Algebra Done Right.

(The only place I've seen that talks about both approaches is this post by Qiaochu Yuan.)

I am having trouble seeing how the two approaches arrive at the same two bases. Approach (1) is clearer to me visually (transforming the unit sphere into an ellipsoid), so maybe my confusion is that I don't see how approach (2) finds the same bases.

Looking at Axler's book, the main dependencies in the proof of SVD are (all numbers from the third edition):

  • Singular value decomposition (7.51)
    • Spectral theorem on $\sqrt{T^*T}$ (7.24, (a)→(b): normal implies existence of orthonormal basis consisting of eigenvectors)
      • Schur's theorem (6.38)
        • Gram–Schmidt procedure (6.31)
        • Existence of upper-triangular matrix with respect to some basis (5.27)
          • Existence of eigenvalue (5.21)

In other words, approach (2) starts with the basis given by the upper-triangular matrix, then modifies that basis using the Gram–Schmidt procedure. What I don't understand, for example, is that the Gram–Schmidt procedure begins by picking one of the vectors, and this vector ends up in the final orthonormal list of vectors, so what if we picked the "wrong" vector?

$\endgroup$
  • 1
    $\begingroup$ Keep in mind that if there are repeated singular values, the orthogonal basis vectors that you end up with aren't uniquely determined. When the singular values are distinct the orthogonal basis vectors are unique (up to sign.) $\endgroup$ – Brian Borchers Aug 30 '18 at 2:50
1
$\begingroup$

Consider a basis with respect to which an operator has an upper-triangular matrix. The first vector of that basis must be an eigenvector for the operator. Then applying Gram--Schmidt to the basis modifies that first basis vector only by a scalar multiple, thus again giving an eigenvector. This should explain why you cannot pick the ''wrong'' vector.

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