 |  |  |  |  |
Bringing the SVD to Life
by Gilbert Strang
The singular value decomposition is wonderful, but it is not so easy to teach. In desperation, I usually factor some low-rank matrices. Readers might be interested in two full-rank examples that connect the SVD to the derivative of sin kx. I believe they could help.
Symmetric positive definite matrices are one of the highlights of a linear algebra course. The equivalence of positive pivots, positive eigenvalues, and positive determinants brings the whole subject together. We need the matrix ATA for least squares and projections, and it is the key to the SVD.
The singular value decomposition is the other half of this high point. A= UΣVT gives perfect bases for the four fundamental subspaces. The first r columns of U and V are orthonormal bases for the column space and row space of A. The remaining m – r and n– r columns are ortho-normal bases for the nullspaces of AT and A. The key equation AV= UΣ says that A is diagonalized by these bases: Each Avk= σkuk. The positive eigenvalues of ATA and AAT are the squares of the singular values σk in the diagonal matrix Σ. Nothing better could be imagined, except that examples tend to be small and artificial and quite unimpressive to students.
That is the downside of the SVD. We can invent matrices and compute UΣVΤ. We can identify Σ and V from the eigenvalues and eigenvectors in AΤAvk= (σk)2vk. And we can produce uk= Avk/σk as eigenvectors of AAΤ. The quick proof is so typical of linear algebra: Multiply by A and move the parentheses in (AAΤ)(Avk) = (σk)2(Avk). But bringing the factorization to life is much harder than its proof, especially if time is running out on the course.
My hope lies with a simple difference matrix. Put 1’s on the diagonal and –1’s on the subdiagonal of an n+ 1 by n matrix A. Then AΤA is the –1,2,–1 second difference matrix toeplitz([2–1zeros(1,n–2)]). Its pivots, 2/1, 3/2, 4/3, . . . , are perfect examples for elimination, giving 2,3,4,. . . as the principal determinants. But the SVD requires eigenvectors. My point is that the eigenvectors of these matrices are attractive and important too.
Expressed in words, Avk= σkuk says that the difference of a discrete sine is a discrete cosine. With (n + 1)h= π, the sine and cosine eigenvectors are
vk = (sin kh, sin 2kh, . . . , sin nkh)
uk = (cos kh/2, cos 3kh/2, . . . , cos (n + .5)kh)
A typical difference is sin 2kh– sin kh. This equals 2 sin kh/2 cos 3kh/2. Identities like that give the scalar form of the SVD, and Avk= 2 sin kh/2uk is the vector form. Far better is the matrix form, with the discrete cosine and sine transforms used as U and V:
SVD Example 1: A = (DCT) Σ(DST)Τ
The cosine vector un+1= (1, . . . ,1) from the nullspace of AΤ is conventionally placed in column 0 (displeasing MATLAB) of the DCT matrix. All columns of the DCT and DST matrices are normalized to unit vectors (luckily, ||uk|| = ||vk|| above).
That matrix AΤA builds in the Dirichlet conditions v(0) = v(π) = 0. The matrix AAΤ with (1, . . . ,1) in its nullspace changes to Neumann conditions u'(0) = u'(π) = 0.
By dropping the last row of A to form a square matrix B, we get a second example that combines Dirichlet at one end with Neumann at the other. The 1,1 entry of BΤB and the n,n entry of BBΤ change from 2 to 1. The effective meshlength H comes from (n + .5)H= π. Each vector uk just reverses the components of vk:
vk= (sin (k– .5)H, sin 2(k – .5)H, . . .)
The same identities produce Bvk= [2 sin (k – .5)H/2] uk with the new v and u. The matrix form has the “half-point”discrete cosine and sine transforms:
SVD Example 2: B = (DCTH) Σ (DSTH)
The real magic is that the discrete eigenvectors just sample the sine and cosine eigenfunctions of the continuous problems. Once again, and probably forever, Fourier sets the best example.
Gilbert Strang is a professor of mathematics at MIT.
« Back to Jan/Feb 2006 Index