Dimensions of $U$ in SVD

942 Views Asked by At

In SVD we have

$$M=U\Sigma V^T$$

where the columns of $U$ are the eigenvectors of $MM^T$.

If $M$ is $m \times n$, is it necessary that $U$ be $m \times m$ or can it be $m \times r$? In other words, is there a case where we do not have a full set of eigenvectors for $M M^T$, because they are linearly dependent or because the eigenvalues are $0$, or for any other reason?

2

There are 2 best solutions below

7
On BEST ANSWER

Let $r$ be the rank of $m\times n$ matrix $M$.

Then a typical SVD makes the matrices of the form: $$\begin{array}{|c|c|}\hline\\ \\ \quad \,M\,\quad\\ \\ \\ \hline\end{array}= \begin{array}{|c|c|}\hline \\ \\ \quad U_r\quad& \quad U_r^\perp\quad \\ \\ \\ \hline\end{array} \begin{array}{|c|c|}\hline \\ \quad\Sigma_r\quad&0 \\ \\ \hline \\ 0&0 \\\hline\end{array} \begin{array}{|cc|}\hline\\ \quad\,V_n^{\perp*}\,\quad\\ \\ \hline \quad V_n^*\quad\\\hline\end{array}$$ In this form $U_r$ are orthogonal unit vectors that span the range of $M$, and $U_r^\perp$ forms the completion to an orthonormal basis. Similarly $V_n$ is a set of orthonormal vectors that spans the null space of $M$, and $V_n^\perp$ completes it to an orthonormal basis.

Note that $U$ is always an $m\times m$ unitary matrix here.

However, we can create a so called 'economic' SVD as well, which is not the official SVD: $$\begin{array}{|c|c|}\hline\\ \\ \quad\,M\,\quad\\ \\ \\ \hline\end{array}= \begin{array}{|c|c|}\hline \\ \\ \quad U_r\quad\\ \\ \\ \hline\end{array} \begin{array}{|c|c|}\hline \\ \quad\Sigma_r\quad \\ \\\hline\end{array} \begin{array}{|cc|}\hline\\ \quad\,V_n^{\perp*}\,\quad\\ \\ \hline \end{array}$$

Now $U_r$ is an $m\times r$ matrix. And we have: $$M=U\Sigma V^*=U_r\Sigma_r V_n^{\perp*}$$ where $U_r$, $\Sigma_r$, and $V_n^{\perp}$ are each of the same full rank $r$.

0
On

The question asks about the four fundamental subspaces. So, start with...

Fundamental Theorem of Linear Algebra

A matrix $\mathbf{A} \in \mathbb{C}^{m\times n}_{\rho}$ induces four fundamental subspaces. These are range and null spaces for both the column and the row spaces. $$ \begin{align} % \mathbf{C}^{n} = \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} \oplus \color{red}{\mathcal{N} \left( \mathbf{A} \right)} \\ % \mathbf{C}^{m} = \color{blue}{\mathcal{R} \left( \mathbf{A} \right)} \oplus \color{red} {\mathcal{N} \left( \mathbf{A}^{*} \right)} % \end{align} $$

$\color{blue}{Range}$ spaces are colored in blue, $\color{red}{null}$ spaces in red.

The singular value decomposition (SVD) provides an orthonormal basis for the four fundamental subspaces.

Define SVD

Start with a nonzero matrix $\mathbf{A}\in\mathbb{C}^{m\times n}_{\rho}$, where the matrix rank $\rho<m$ and $\rho<n$. The singular value decomposition, guaranteed to exist, is $$ \mathbf{A} = \mathbf{U} \, \Sigma \, \mathbf{V}^{*} = \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] % \left[ \begin{array}{c} \mathbf{S} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{V}_{\mathcal{N}}}^{*} \end{array} \right]. $$ The codomain matrix $\mathbf{U}\in\mathbb{C}^{m\times m}$, and the domain matrix $\mathbf{V}\in\mathbb{C}^{n\times n}$ are unitary: $$ \mathbf{U}^{*}\mathbf{U} = \mathbf{U}\mathbf{U}^{*} = \mathbf{I}_{m}, \quad \mathbf{V}^{*}\mathbf{V} = \mathbf{V}\mathbf{V}^{*} = \mathbf{I}_{n}. $$ The column vectors of the domain matrices provide orthormal bases for the four fundamental subspaces: $$ \begin{array}{ll} % matrix & subspace \\\hline % \color{blue}{\mathbf{U}_{\mathcal{R}}}\in\mathbb{C}^{m\times\rho} & \color{blue}{\mathcal{R}\left(\mathbf{A}\right)} \\ % \color{blue}{\mathbf{V}_{\mathcal{R}}}\in\mathbb{C}^{n\times\rho} & \color{blue}{\mathcal{R}\left(\mathbf{A}^{*}\right)} \\ % \color{red}{\mathbf{U}_{\mathcal{N}}}\in\mathbb{C}^{m\times m-\rho} & \color{red}{\mathcal{N}\left(\mathbf{A^{*}}\right)} \\ % \color{red}{\mathbf{V}_{\mathcal{N}}}\in\mathbb{C}^{n\times n-\rho} & \color{red}{\mathcal{N}\left(\mathbf{A}\right)} % \end{array} $$ There are $\rho$ singular values which are ordered and real: $$ \sigma_{1} \ge \sigma_{2} \ge \dots \ge \sigma_{\rho}>0. $$ and are the square root of non-zero eigenvalues of the product matrices $\mathbf{A}^{*}\mathbf{A}$ and $\mathbf{A}\mathbf{A}^{*}$. These singular values form the diagonal matrix of singular values $$ \mathbf{S} = \text{diagonal} (\sigma_{1},\sigma_{1},\dots,\sigma_{\rho}) \in\mathbb{R}^{\rho\times\rho}. $$ The $\mathbf{S}$ matrix is embedded in the sabot matrix $\Sigma\in\mathbb{R}^{m\times n}$ whose shape insures conformability.

SVD in terms of vectors

$$ \begin{align} \mathbf{A} &= \mathbf{U} \, \Sigma \, \mathbf{V}^{*} \\ % &= % U \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] % Sigma \left[ \begin{array}{cccc|cc} \sigma_{1} & 0 & \dots & & & \dots & 0 \\ 0 & \sigma_{2} \\ \vdots && \ddots \\ & & & \sigma_{\rho} \\\hline & & & & 0 & \\ \vdots &&&&&\ddots \\ 0 & & & & & & 0 \\ \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{V}_{\mathcal{N}}}^{*} \end{array} \right] \\ % & = % U \left[ \begin{array}{cccccccc} \color{blue}{u_{1}} & \dots & \color{blue}{u_{\rho}} & \color{red}{u_{\rho+1}} & \dots & \color{red}{u_{m}} \end{array} \right] % Sigma \left[ \begin{array}{cc} \mathbf{S}_{\rho\times \rho} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{v_{1}^{*}} \\ \vdots \\ \color{blue}{v_{\rho}^{*}} \\ \color{red}{v_{\rho+1}^{*}} \\ \vdots \\ \color{red}{v_{n}^{*}} \end{array} \right] % \end{align} $$

Note that the singular values only correspond to $\color{blue}{range}$ space vectors.

The column vectors form spans for the subspaces: $$ \begin{align} % R A \color{blue}{\mathcal{R} \left( \mathbf{A} \right)} &= \text{span} \left\{ \color{blue}{u_{1}}, \dots , \color{blue}{u_{\rho}} \right\} \\ % R A* \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} &= \text{span} \left\{ \color{blue}{v_{1}}, \dots , \color{blue}{v_{\rho}} \right\} \\ % N A* \color{red}{\mathcal{N} \left( \mathbf{A}^{*} \right)} &= \text{span} \left\{ \color{red}{u_{\rho+1}}, \dots , \color{red}{u_{m}} \right\} \\ % N A \color{red}{\mathcal{N} \left( \mathbf{A} \right)} &= \text{span} \left\{ \color{red}{v_{\rho+1}}, \dots , \color{red}{v_{n}} \right\} \\ % \end{align} $$

The full SVD provides an orthonormal span for not only the two null spaces, but also both range spaces.