Singular Value Decomposition
Introduction.
Let be a linear map between finite dimensional vectors spaces, endowed with scalar products.
The Singular Value Decomposition theorem, shows us that we can find ortho-normal bases of respectively,
so that the matrix representation of with respect to has only diagonal entries: ,
Furthermore the bases can be arranged in a way that
In this note, we are going to explore an abstract "coordinate free" version of SVD that can be expressed without choices of bases.
Instead, we are going to study the eigenvalues of the self-adjoint operators on and on .
By the Spectral Decomposition Theorem, the vector spaces decompose
as orthogonal direct sums of the Eigenspaces of respectively: .
How does look like in a basis that is adjusted to this decompositions?
Proposition
- The map induces linear maps , i.e. .
- The map induces linear maps , i.e. .
- For the maps , are inverse isometries between the Eigenspaces .
Proof
1) For , we have
2) For , we have
3) For we have by definition of .
4) Clear from 3.
5) by properties of the adjoint. Similarly .
Corollary (SVD). We find orthogonal bases of with respect to which has only diagonal entries .
Proof
We recover the SVD from the Proposition, by choosing orthogonal basis for each Eigenspace .
For , we get a ONB for as .
Choose , and arbitrary in . Now for and a basis vector we have for
. For we have . QED.
Corollary. Choosing a basis of , that is adjusted to the Eigenspaces , in descending order,
the linear map f is represented by a block diagonal matrix with entries :
Where, and .
In particular is an isomorphisom for .
Application - Least Squares via Duality
Regular least squares problems can commonly be written as a minimization problem of the form:
Where is an injective linear map, and .
We can translate this minimization problem on to a minimization problem on by considering:
Since is injective, is surjective. So a global minimum of will map to a global minimum of under .
Now can be explicitly minimized by noting that:
Where are the components of in . This function
is minized by with and , i.e.
We obtain the following formula for the solution
We claim that is given by following explicit formula .
Indeed, , where operats as .
Hence as