# Is this formulation of the Singular Value Decomposition standard?

In customary formulations of the Singular Value Decomposition or SVD that I have seen, (e.g., Wikipedia or Gil Strang's textbooks) it is always stated in terms of writing an $m \times n$ matrix $M$ (say of rank $r$) as a product $U \Lambda V$, where $U$ and $V$ are orthogonal $m \times m$ and $n \times n$ matrices and $\Lambda$ is a diagonal $m \times n$ matrix with non-negative "singular values" on the diagonal, $s_1 \ge s_2 \ge \ldots \ge s_r >0$ and the rest zero. Looking back over the many times I have taught linear algebra to both undergraduates and graduate students, I realized that I have not once covered the SVD, and even though I consider myself pretty knowledgeable about linear algebra, I have never felt comfortable with the statement of SVD or felt that I understood it in a more than formal way. (I might add that many theoretical linear algebra texts do not mention the SVD and many of my more theoretically minded colleagues do not even recognize the term.) But a few days ago, a social scientist friend of mine asked me about
a problem he was interested in; one that involved the SVD in an essential way. After thinking about it for a while, I realized that SVD can be reformulated as a statement about linear transformations that, to me at least, seems a lot more conceptual and geometric:

If $T$ is a linear map, say of rank $r$, between finite dimensional inner-product spaces $V$ and $W$, then there are orthonormal bases $v_1, \ldots, v_m$ for $V$ and $w_1, \ldots, w_n$ for $W$ and $r$ positive numbers $s_1 \ge s_2 \ge \ldots \ge s_r$, such that $T v_i$ equals $s_i w_i$ if $i \le r$ and equals zero if $i > r$.

I certainly realize that this is a pretty obvious reformulation of SVD, once you see it (and
those poor misguided souls who prefer matrices to linear transformations may even see it as a step backwards :-), but my question is whether there is some standard source for this reformulation that I can reference.

-
By a strange coincidence, I'm about to teach it precisely this way this afternoon ... –  Loop Space Oct 25 '10 at 7:43
It seems that the more "applied" you get, the more occasion you have to think about the SVD. The "purest" mathematicians seem to be the ones "do not even recognize [that] term". In some contexts, it also seems as if the "pure" assume that matrices are square. Once I wrote down the matrix $A(A^T A)^{-1} A^T$ and a highly respected "pure" mathematician told me that's the identity matrix. So it is, if $A$ has as many columns as rows. –  Michael Hardy Nov 10 '10 at 17:52
Michael, since you're a statistician, do you think there might be sample bias in your observations about the iniquities of pure mathematicians (here and elsewhere)? –  Yemon Choi Nov 10 '10 at 18:24
Well, I wouldn't have actually called this an "iniquity". –  Michael Hardy Nov 10 '10 at 19:20

I just looked in Wikipedia (http://en.wikipedia.org/wiki/Singular_value_decomposition). There is a very thorough discussion, including a section "Geometric meaning" in which your interpretation is clearly explained. Well, there $K^n$, where $K = \mathbb R$ or $K = \mathbb C$ is used, instead of arbitrary inner product spaces, but I suppose you'll agree that the difference is not essential.

-
OUCH ! You are absolutely correct. Somehow I missed that section---or rather I guess that I never got down that far in the Wikipedia article, perhaps because it comes well after the explanation in terms of matrices and a long section on applications. Many thanks. –  Dick Palais Oct 24 '10 at 19:41

The singular values do have a sound geometrical meaning. The first one is nothing but the operator norm of $T$, that is the maximum dilation coefficient $$\frac{\|Tx\|}{\|x\|}.$$ The next ones can be seen also as maximum of dilation coefficients, provided you replace lines by subspaces. For instance $$s_k=\max_{\dim F=k}\min\left\{\frac{\|Tx\|}{\|x\|};x\in F,x\ne0\right\}.$$ In terms of the exterior algebra over $\mathbb C^k$ ($k=m$ or $n$), you have $$s_1\cdots s_k=\sup\left\{\frac{\|Tx_1\wedge\cdots\wedge Tx_k\|}{\|x_1\wedge\cdots\wedge x_k\|};x_1,\ldots,x_k\in F\right\}.$$

Notice also that there is a $p$-adic version of the SVD decomposition. See K. S. Kedlaya. $p$-adic differential equations. Cambridge Studies in Advanced Mathematics, 125. Cambridge University Press, Cambridge, 2010

Edit. I should have also given the formula $$s_1+\cdots+s_k=\max\{{\rm Tr}(PTQ); P\hbox{ and } Q \hbox{ are unitary projectors of rank } k\}.$$ This has the interesting consequence that $T\mapsto s_1+\cdots+s_k$ is a convex function.

Edit (bis). Actually, $T\mapsto s_1\cdots s_k$ is rank-one convex. This means that it is convex along every line $A+{\mathbb R} B$ for which $B-A$ is a rank-one matrix.

-
I recognized the definition of $s_k$ as Courant-Fischer, but I was not aware of the formula for the product $s_1\cdots s_k$. This is really fascinating! Are there any interesting applications of that formula that would be easily readable? –  Thierry Zell Nov 10 '10 at 13:02
@Thierry. See my edits. –  Denis Serre Nov 10 '10 at 14:22
@Denis: very interesting. You should write a book about this :) –  Piero D'Ancona Nov 10 '10 at 14:28
Also worth noting here is that the trace-norm $s_1+\cdots+s_k$ is the convex function "closest" to the numerically intractable matrix rank function. –  Suvrit Nov 10 '10 at 14:46
@Piero. You don't miss any occasion of variation to your favorite joke. More seriously, see exercises 108, 109 in umpa.ens-lyon.fr/~serre/DPF/exobis.pdf . –  Denis Serre Nov 10 '10 at 15:13

The book "Numerical Linear Algebra" by Trefethen and Bau, also introduces the SVD in this way. The relevant chapters (4 and 5) seem to be complete in Google books. The exposition is not tainted by the 'numerical' in the title.

I don't understand why the SVN isn't given more emphasis in standard introductions to linear algebra. It seems to give a good intuitive decomposition of a linear operator. I would expect it to be a useful theoretical tool even if numerical issues are not being considered.

-
The first five chapters of the book are available online: people.maths.ox.ac.uk/~trefethen/text.html –  Ramsay Oct 24 '10 at 21:15
A week ago I might have demurred from that second statement, but now I think I have to agree. My clouded eyes have been opened. :-) BTW, I really like the way that Trefethan and Bau express the key point (page 32) : "The SVD makes it possible for us to say that every matrix is diagonal---if only we choose the proper bases for the domain and range spaces." –  Dick Palais Oct 24 '10 at 21:21
That quote by itself is not the best summary of the SVD. That quote by itself is the best summary of the rank theorem (by which I mean that every linear transformation can have matrix [I_k 0; 0 0]). SVD says that the rank theorem still holds if we insist that all our isomorphisms are isometries, providing we replace the identity submatrix by a diagonal one. –  Loop Space Oct 25 '10 at 7:43
Trivial, but at least doable! My main gripe with things like SVD is that so often they are presented as things that can actually be computed (Jordan canonical form is another example) whereas to actually do it involves finding eigenvalues which is, as the Norwegians know very well, impossible. Of course, the fact that it exists is tremendously important but for reasons other than actually being able to compute it. –  Loop Space Oct 26 '10 at 7:15
That all depends on what you mean by "computed". It can certainly be computed in a practical sense, in that there are programs that can compute the SVD of a matrix (over C^n). More theoretically, I also expect that it's possible to construct an algorithm that provably computes the SVD to any accuracy. It is not clear to me what the relevance is of the fact that you cannot write down the SVD in closed form. The Jordan canonical form is a very different beast because it is discontinuous. –  Jitse Niesen Nov 10 '10 at 10:17

This formulation, or something very close to it (I don't have the book with me) is in Axler's Linear Algebra Done Right.

-
You can also find it in Treil's Linear Algebra Done Wrong, section 3.3 (pdf of book: math.brown.edu/~treil/papers/LADW/LADW.pdf ). –  alex Oct 24 '10 at 20:06
So it seems that whether you do things right or wrong, the linear transformation formulation I mentioned IS the way to go. :-) BTW, when you say it is in Treil, are you referring to the formula (3.1) on page 168? –  Dick Palais Oct 24 '10 at 21:05
Right - I actually meant Proposition 3.6 just above that. –  alex Oct 24 '10 at 23:40

It's in my favourite linear algebra book Advanced Linear Algebra by Steven Roman, chapter 17 (called Singular Values and the Moore-Penrose inverse).

-