5
$\begingroup$

Apologies that this turned out a little long.

I have studied the Singular Value Decomposition in Fundamental of Matrix Computations by Watkins and I couldn't to solve the Exercise 4. 1. 16 which is a demonstration of the following theorem:

(Watkins) Theorem 4.1.1 (SVD Theorem) Let $A\in \mathbb{R}^{n \times m}$ be a nonzero matrix with rank $r$. Then $A$ can be expressed as a product \begin{equation} A = U \Sigma V^{T} \end{equation} where $U \in \mathbb{R}^{n \times n}$ and $V \in \mathbb{R}^{m \times m}$ are orthogonal, and $\Sigma \in \mathbb{R}^{n \times m}$ is a rectangular "diagonal" matrix \begin{equation} \Sigma = \left( \begin{array}{cccccc} {\sigma_{1}} & {} & {} & {} & {} & {}\\ { } & {\sigma_2} & {} & {} & {} & {}\\ {} & {} & {\ddots} & {} & {} & {}\\ {} & {} & {} & {\sigma_r} & { } & {} \\ {} & {} & {} & {} & { } & {\ddots} \end{array} \right) \;\;\; \sigma_{1}\geq \sigma_2 \geq \cdots\geq \sigma_r > 0. \end{equation}

The Exercise is:

(Watkins) Exercise 4.1.16 In this exercise you will prove Theorem 4.1.1 by induction on $r$, the rank of $A$.

(a) Suppose $A \in \mathbb{R}^{n \times m}$ has rank 1. Let $u_1 \in \mathbb{R}^{n}$ be a vector in $R(A)$ such that $|| u_1 ||_2 = 1$. Show that every column of $A$ is a multiple of $u_1$. Show that $A$ can be written in the form $ A = \sigma_1 u_1 v_{1}^{T}$, where $v_1 \in \mathbb{R}^{m}$, $|| u_1 ||_2 = 1$, and $\sigma_1 > 0$.

(b) Continuing from part (a), demonstrate that there is an orthogonal matrix $U \in \mathbb{R}^{n \times n}$ whose first column is $u_1$. (For example, $U$ can be a reflector that maps the unit vector $e_1$ to $u_1$.) Similarly there is an orthogonal $V \in \mathbb{R}^{m \times m}$ whose first column is $v_1$. Show that $A = U \Sigma V^{T}$, where $\Sigma \in \mathbb{R}^{n \times m}$ has only one nonzero entry, $\sigma_1$, in position $(1,1)$. Thus every matrix of rank 1 has an $SVD$.

(c) Now suppose $A \in \mathbb{R}^{n \times m}$ has rank $r > 1$. Let $v_1$ be a unit vector in the direction of maximum magnification by $A$, i.e., $|| v_1 ||_2 = 1$, and $|| A v_1 ||_2 = \max_{|| v ||_{2} = 1} || Av||_2$. Let $\sigma_{1}=\left\|A v_{1}\right\|_{2}=\|A\|_{2}$, and let $u_1 = \sigma_{1}^{-1}Av_1$. Let $\tilde{U} \in \mathbb{R}^{n \times n}$ and $\tilde{V} \in \mathbb{R}^{m \times m}$ be orthogonal matrices with first column $u_1$ and $v_1$, respectively. Let $\tilde{A} = \tilde{U}^{T} A \tilde{V}$, so that $A = \tilde{U} \tilde{A} \tilde{V}^{T}$. Show that $\tilde{A}$ has the form \begin{equation} \tilde{A}=\left[ \begin{array}{cc}{\sigma_{1}} & {z^{T}} \\ {0} & {\hat{A}}\end{array}\right], \end{equation} where $z \in \mathbb{R}^{m-1}$ and $\hat{A} \in \mathbb{R}^{(n-1) \times (m-1)}$.

(d) Show that in matrix $\tilde{A}$ above the vector $z$ must be zero. You may do this as follows: Let $w=\left[ \begin{array}{c}{\sigma_{1}} \\ {z}\end{array}\right] \in \mathbb{R}^{m}$. Show that $\|\tilde{A} w\|_{2} /\|w\|_{2} \geq \sqrt{\sigma_{1}^{2}+z^{T} z}$. Then show that this inequality forces $z = 0$. Thus \begin{equation} \tilde{A}=\left[ \begin{array}{cc}{\sigma_{1}} & {0} \\ {0} & {\hat{A}}\end{array}\right]. \end{equation}

(e) Show that $\hat{A}$ has rank $r-1$. By the induction hypothesis $\hat{A}$ has an SVD $\hat{A} = \hat{U} \hat{\Sigma} \hat{V}^{T}$. Let $\sigma_2 \geq \sigma_3 \geq \cdots \sigma_r$ denote the positive main-diagonal entries of $\hat{\Sigma}$. Show that $\sigma_1 \geq \sigma_2$. Embed the SVD $\hat{A} = \hat{U} \hat{\Sigma} \hat{V}^{T}$ in larger matrices to obtain an SVD of $A$. Then use the equation $A = \tilde{U} \tilde{A} \tilde{V}^{T}$ to obtain an SVD of $A$.


Question:

I know the exercise is well done (it's a step by step that I should probably complete the demonstration easily). But I could not do it and it also did not help me what I read in the book of Strang and Golub that I took to help me solve this exercise. So, I'd like to understand the solutions this Theorem/Exercise.

$\endgroup$
8
  • $\begingroup$ I think it may be better if you split this question up for each subpart but someone more experienced than me may disagree $\endgroup$
    – user3417
    May 29, 2019 at 20:33
  • $\begingroup$ @Shogun sorry, but I can't understand your comment. Did you mean that there are many items and consequently many doubts? Unfortunately, I asked the whole question because here you can help me. And only with a book I couldn't understand. I am very difficult in this discipline (Watkins, Golub, Trefethen, ...). $\endgroup$ May 30, 2019 at 4:20
  • 1
    $\begingroup$ I'm saying each part on it's own might make a good question however in retrospect they all kind of require each other. I'd note that I believe that this is actually answered in Trefethan and Bau in the section about the SVD to a degree. $\endgroup$
    – user3417
    May 30, 2019 at 4:24
  • 1
    $\begingroup$ I may answer this later today however I'm busy at the moment. $\endgroup$
    – user3417
    May 30, 2019 at 18:52
  • 1
    $\begingroup$ I'll attempt to clean that up but that is c-e $\endgroup$
    – user3417
    May 31, 2019 at 19:21

1 Answer 1

1
$\begingroup$

Ok, suppose that $A = U \Sigma V^{T}$ . First of all consider how the SVD is calculated. The construction of the SVD uses the following idea

We get the left singular vectors $U$ by computing the covariance matrix

$$ AA^{T} = U \Sigma V^{T}( U \Sigma V^{T})^{T} = U \Sigma V^{T} (V \Sigma^{T} U^{T}) $$

now note that $V^{T}V = I$ so we have

$$ U \Sigma V^{T} (V \Sigma^{T} U^{T}) = U \Sigma \Sigma^{T} U^{T} $$

note that $\Sigma$ is a diagonal matrix and $ \sigma_{jj}^{T} = \sigma_{jj}$ so

$$ U \Sigma \Sigma^{T} U^{T} = U \Sigma \Sigma U^{T}$$

now the singular values $\sigma_{i}^{2} = \lambda_{i}$ so you can write

$$ U \Lambda^{\frac{1}{2}} \Lambda^{\frac{1}{2}} U^{T} = U \Lambda U^{T} $$

Similarly, the right singular vectors $V$ are given as

$$ A^{T}A = (U \Sigma V^{T})^T (U \Sigma V^{T}) = V \Lambda V^{T} $$

Note that you can write this like

$$ V^{T} A^{T}A V = \begin{pmatrix} v_{1}^{T} \\ v_{2}^{T} \\ \vdots \\ v_{m}^{T} \end{pmatrix} \left( A^{T}A v_{1}, A^{T}A v_{2} , \cdots A^{T} A v_{m} \right) = \begin{pmatrix} v_{1}^{T} \\ v_{2}^{T} \\ \vdots \\ v_{m}^{T} \end{pmatrix} \left( \lambda_{1} v_{1}, A^{T}A v_{2} , \cdots A^{T} A v_{m} \right) = \begin{pmatrix} \lambda_{1} & \textrm{z}^{*} \\ 0 & \textrm{B} \end{pmatrix} $$

where by induction we have $ B = \hat{V}{S} \hat{V}^{T}$

$$ V^{T} A^{T}A V = \begin{pmatrix} \lambda_{1} & z^{*} \\ 0 & \hat{V}{S} \hat{V}^{T}\end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & \hat{V} \end{pmatrix} \begin{pmatrix} \lambda & z^{*} \\ 0 & S \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \hat{V} \end{pmatrix}^{T} $$

We use the same idea for $\tilde{A} = \tilde{U}^{T} A \tilde{V}$

$$ \tilde{U}^{T} A \tilde{V} = \begin{pmatrix} \tilde{u}_{1}^{T} \\ \tilde{u}_{2}^{T} \\ \vdots \\ \tilde{u}_{m}^{T} \end{pmatrix} \left(A \tilde{v}_{1} , A \tilde{v}_{2} , \cdots A \tilde{v}_{m} \right) \\ = \begin{pmatrix} \tilde{u}_{1}^{T} \\ \tilde{u}_{2}^{T} \\ \vdots \\ \tilde{u}_{m}^{T} \end{pmatrix} \left(\sigma \tilde{v}_{1} , A \tilde{v}_{2} , \cdots A \tilde{v}_{m} \right) = \begin{pmatrix} \sigma_{1} & z^{*} \\ 0 & \hat{A} \end{pmatrix} $$

with $\hat{A} = \hat{U} \hat{\Sigma} \hat{V}^{T}$ we have

$$ \begin{pmatrix} 1 & 0 \\ 0 & \hat{U} \end{pmatrix} \begin{pmatrix} \sigma_{1} & z^{*} \\ 0 & \hat{A} \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \hat{V} \end{pmatrix}^{T} $$

The point is to continue along the lower part of the diagonal and prove $z^{*}$ is equal to $0$.

$$ \bigg\| \begin{bmatrix} \sigma_{1} & z^{*} \\ 0 & \hat{A} \end{bmatrix} \begin{bmatrix} \sigma_{1} \\ z \end{bmatrix} \bigg\|_{2} \geq \sigma_{1}^{2} + z^{*} z = \left( \sigma_{1}^{2} + z^{*}z\right)^{\frac{1}{2}} \bigg\| \begin{bmatrix} \sigma_{1} \\ z \end{bmatrix} \bigg\|_{2} $$

Now, note we're working with $\| \tilde{A}\| = \| \tilde{U}^{T} A \tilde{V} \|$ and $\| \tilde{A}\|_{2} \geq \left( \sigma_{1} + z^{*}z \right)^{\frac{1}{2}} $. Since $\| \tilde{A}\| = \| \tilde{U}^{T} A \tilde{V} \|$ we know that $\|\tilde{A}\| = \|A \| = \sigma_{1}$ which forces $z^{*} = 0$

Once you have done this we then have

$$ A = \tilde{U} \tilde{A} \tilde{V}^{T} = \begin{pmatrix} 1 & 0 \\ 0 & \hat{U} \end{pmatrix} \begin{pmatrix} \sigma_{1} & 0 \\ 0 & \hat{A} \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \hat{V} \end{pmatrix}^{T} $$

Since this gives the form for a general matrix $A \in \mathbb{R}^{n \times m}$ and we have that $\hat{A} \in \mathbb{R}^{ (n -1) \times (m-1)}$ we know it has a SVD just like that...

I'm pretty sure I've messed up the $\hat{A}, \tilde{A}$ somewhere along here..

$\endgroup$
1
  • 1
    $\begingroup$ I have much to thank you for. Tonight I will read all the details and if you have any doubts I put here. I jumped a little bit this subject and keep going in a book. When I finished my read about pseudoinverse I will return this. Again, Thanks too much! $\endgroup$ May 31, 2019 at 19:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .