Feeds:
Posts
Comments

Archive for March, 2017

Singular value decomposition

Posted in math.SP on March 13, 2017| 4 Comments »

As a warm-up to the subject of this blog post, consider the problem of how to classify n \times m matrices M \in \mathbb{R}^{n \times m} up to change of basis in both the source (\mathbb{R}^m) and the target (\mathbb{R}^n). In other words, the problem is to describe the equivalence classes of the equivalence relation on n \times m matrices given by

\displaystyle M \sim N \Leftrightarrow M = PNQ^{-1}, P \in GL_n(\mathbb{R}), Q \in GL_m(\mathbb{R}).

It turns out that the equivalence class of M is completely determined by its rank r = \text{rank}(M). To prove this we construct some bases by induction. For starters, let x_1 \in \mathbb{R}^m be a vector such that y_1 = M x_1 \neq 0; this is always possible unless M = 0. Next, let x_2 \in \mathbb{R}^m be a vector such that y_2 = M x_2 is linearly independent of y_1; this is always possible unless \text{rank}(M) = 1.

Continuing in this way, we construct vectors x_1, \dots x_r \in \mathbb{R}^m such that the vectors y_1 = M x_1, \dots y_r = M x_r \in \mathbb{R}^n are linearly independent, hence a basis of the column space of M. Next, we complete the x_i and y_i to bases of M in whatever manner we like. With respect to these bases, M takes a very simple form: we have M x_i = y_i if 1 \le i \le r and otherwise M x_i = 0. Hence, in these bases, M is a block matrix where the top left block is an r \times r identity matrix and the other blocks are zero.

Explicitly, this means we can write M as a product

\displaystyle M = PDQ^{-1}, P \in GL_n(\mathbb{R}), Q \in GL_m(\mathbb{R})

where D has the block form above, the columns of P are the basis of \mathbb{R}^n we found by completing M x_1, \cdots M x_r, and the columns of Q are the basis of \mathbb{R}^m we found by completing x_1, \cdots x_r. This decomposition can be computed by row and column reduction on M, where the row operations we perform give P and the column operations we perform give Q.

Conceptually, the question we’ve asked is: what does a linear transformation T : X \to Y between vector spaces “look like,” when we don’t restrict ourselves to picking a particular basis of X or Y? The answer, stated in a basis-independent form, is the following. First, we can factor T as a composite

\displaystyle X \xrightarrow{p} \text{im}(T) \xrightarrow{i} Y

where \text{im}(T) is the image of T. Next, we can find direct sum decompositions X \cong \text{im}(T) \oplus X' and Y \cong \text{im}(T) \oplus Y' such that p is the projection of X onto its first factor and i is the inclusion of the first factor into Y. Hence every linear transformation “looks like” a composite

\displaystyle \text{im}(T) \oplus X' \xrightarrow{p_{\text{im}(T)}} \text{im}(T) \xrightarrow{i_{\text{im}(T)}} \text{im}(T) \oplus Y

of a projection onto a direct summand and an inclusion of a direct summand. So the only basis-independent information contained in T is the dimension of the image \text{im}(T), or equivalently the rank of T. (It’s worth considering the analogous question for functions between sets, whose answer is a bit more complicated.)

The actual problem this blog post is about is more interesting: it is to classify n \times m matrices M \in \mathbb{R}^{n \times m} up to orthogonal change of basis in both the source and the target. In other words, we now want to understand the equivalence classes of the equivalence relation given by

\displaystyle M \sim N \Leftrightarrow M = UNV^{-1}, U \in O(n), V \in O(m).

Conceptually, we’re now asking: what does a linear transformation T : X \to Y between finite-dimensional Hilbert spaces “look like”?

(more…)

Read Full Post »