9-24-2024 - SVD

Decomposition

$${\mathbf{A}}_{n\times n};\mathbf{A}=\mathbf{PD}{\mathbf{P}}^{-1}$$

In this decomposition, all the matrices have the same dimension. However, in SVD, this is no longer going to be the case.

$${\mathbf{A}}_{m\times n};\mathbf{A}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^T$$

where $\mathbf{U}$ is an $m\times m$ orthogonal matrix (left singular vectors), $\mathbf{\Sigma }$ is an $m\times n$ rectangularly diagonal matrix (singular values), $\mathbf{V}$ is an $n\times n$ orthogonal matrix (right singular vectors).

Essentially, SVD factors a matrix into three distinct matrices: a rotation, a scaling + dimension adjusting, and another rotation.

Since $\mathbf{V}$ is orthogonal, it holds that ${\mathbf{V}}^T={\mathbf{V}}^{-1}$.

Unit vectors of $\mathbf{U}$ must be unit vectors and orthogonal to each other,

$$\mathbf{U}=\left[\begin{array}{ccc}{\mathbf{u}}_1|& \dots & |{\mathbf{u}}_m\end{array}\right]$$

and unit vectors of $\mathbf{V}$ must be unit vectors and orthogonal to each other.

$$\mathbf{V}=\left[\begin{array}{ccc}{\mathbf{v}}_1|& \dots & |{\mathbf{v}}_n\end{array}\right]$$

$\mathbf{\Sigma }$ is closest possible to diagonal (rectangularly diagonal), so e.g.

$$\mathbf{\Sigma }=\mathrm{diag}(\{{\sigma }_i\})=\left[\begin{array}{ccccc}{\sigma }_1& 0& 0& 0& 0\\ 0& {\sigma }_2& 0& 0& 0\\ 0& 0& {\sigma }_3& 0& 0\\ 0& 0& 0& {\sigma }_4& 0\end{array}\right]$$

Order the singular values in decreasing order - the largest singular values contain most of the information about the matrix.

Applications

Approximate a matrix by looking at the first x singular values (e.g. 100), which represent the 100 most informational pieces of the matrix. e.g. image compression

10-1-2024

$\mathbf{A}$ is $m\times n$ m may be diff than n; $k=\min \left\{m,n\right\}$

$$\mathbf{A}=\mathbf{U\Sigma }{\mathbf{V}}^T$$

Assume $\mathbf{A}$ is given and we have also been given $\mathbf{U}$, $\mathbf{V}$, $\mathbf{\Sigma }$ so that

$$\mathbf{AV}=\mathbf{U\Sigma }(1)$$ $${\mathbf{U}}^T\mathbf{A}=\mathbf{\Sigma }{\mathbf{V}}^T(2)$$

Rewrite (1) as follows:

$$\mathbf{A}{\vec{\mathbf{v}}}_1={\sigma }_1{\vec{\mathbf{u}}}_1$$ $$⋮$$ $$\mathbf{A}{\vec{\mathbf{v}}}_k={\sigma }_k{\vec{\mathbf{u}}}_k$$ $$\mathbf{A}{\vec{\mathbf{v}}}_{k+1\dots n}=\vec{0}$$

Rewrite (2) as follows:

$$\begin{array}{r}{\mathbf{A}}^T\mathbf{U}={\mathbf{V\Sigma }}^T\\ {\mathbf{A}}^T{\vec{\mathbf{u}}}_1={\sigma }_1{\vec{\mathbf{v}}}_1\\ ⋮\\ {\mathbf{A}}^T{u}_k={\sigma }_k{v}_k\\ {\mathbf{A}}^T{u}_{k+1\dots m}=\vec{0}\end{array}$$

Remember: if $k=m$ then “no 0 equations” in (2); if $k=n$ then “no 0 equations” in (1).

Consider the $n\times n$ symmetric matrix ${\mathbf{A}}^T\mathbf{A}=\mathbf{V}{\mathbf{\Sigma }}^T{\mathbf{U}}^T\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^T=\mathbf{V}{\mathbf{\Sigma }}^T\mathbf{\Sigma }{\mathbf{V}}^T$and the $m\times m$ symmetric matrix

$$\mathbf{A}{\mathbf{A}}^T=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^T\mathbf{V}{\mathbf{\Sigma }}^T{\mathbf{U}}^T=\mathbf{U}\mathbf{\Sigma }{\mathbf{\Sigma }}^T{\mathbf{U}}^T$$

Any square symmetric matrix has eigenvalues and an orthogonal diagonalization. For every symmetric matrix, there are two canonical symmetric matrices associated with them: the two above. If there is an SVD, then these diagonalizations are closely related. The product $\mathbf{\Sigma }{\mathbf{\Sigma }}^T$ is diagonal up to ${\sigma }_k$ then followed by zeros. $\mathbf{\Sigma }{\mathbf{\Sigma }}^T$ is $m\times m$, ${\mathbf{\Sigma }}^T\mathbf{\Sigma }$ is $n\times n$.

The eigenvalues are also nonnegative because they are square.

Fact

$\mathbf{A}{\mathbf{A}}^T$ is symmetric and has non-negative eigenvalues. Proof:

$$\begin{array}{r}({\mathbf{AA}}^T{)}^T=({\mathbf{A}}^T{)}^T{\mathbf{A}}^T=\mathbf{A}{\mathbf{A}}^T\end{array}$$

Let $(\lambda ,v)$ be an eigenpair for $A{A}^T$.

$$\begin{array}{r}\mathbf{A}{\mathbf{A}}^T\vec{\mathbf{v}}=\lambda \vec{\mathbf{v}}\\ {\vec{\mathbf{v}}}^T\mathbf{A}{\mathbf{A}}^T\vec{\mathbf{v}}={\vec{\mathbf{v}}}^T\lambda \vec{\mathbf{v}}\\ |{\mathbf{A}}^T\vec{\mathbf{v}}{|}^2=\lambda |\vec{\mathbf{v}}{|}^2\\ \therefore \lambda \ge 0\end{array}$$

Now

Take general $\mathbf{A}$ - want to construct its SVD.

Step 0

Given $\mathbf{A}:m\times n$.

Step 1

Orthogonally diagonalize.

$$\begin{array}{r}{\mathbf{A}}^T\mathbf{A}=\mathbf{V}{\mathbf{D}}_1{\mathbf{V}}^T\\ \mathbf{A}{\mathbf{A}}^T=\mathbf{U}{\mathbf{D}}_2{\mathbf{U}}^T\end{array}$$

We know: ${\mathbf{D}}_1,{\mathbf{D}}_2\ge 0$. We claim that ${\mathbf{D}}_1=\mathrm{diag}({\sigma }_1^2,\dots {\sigma }_k^2,0,\dots ,0)n\times n$ and ${\mathbf{D}}_2=\mathrm{diag}({\sigma }_1^2,\dots {\sigma }_k^2,0,\dots ,0{)}_{m\times m}$.

Proof

Suppose $(\lambda ,\vec{\mathbf{v}})$ is an eigenpair for ${\mathbf{A}}^T\mathbf{A}$. (Sub-claim) Observe that $\left(\lambda ,\frac{\mathbf{A}\vec{\mathbf{v}}}{\sqrt{\lambda }}\right)$ is an eigenpair for $\mathbf{A}{\mathbf{A}}^T$.

Proof of Sub-claim

by assumption ${\mathbf{A}}^T\mathbf{A}\vec{\mathbf{v}}=\lambda \vec{\mathbf{v}}$ which implies that $\lambda ={\sigma }^2$. multiply by $\mathbf{A}$ on left

$$\begin{array}{r}\mathbf{A}{\mathbf{A}}^T\mathbf{A}\vec{\mathbf{v}}=\mathbf{A}(\lambda \vec{\mathbf{v}})\\ \mathbf{A}{\mathbf{A}}^T(\mathbf{A}\vec{\mathbf{v}})=\lambda (\mathbf{A}\vec{\mathbf{v}})\\ \mathbf{W}\vec{\mathbf{w}}=\lambda \vec{\mathbf{w}}\end{array}$$

$Av$ is an eigenvector with eigenvalue $\lambda$.

Remark: note if $\vec{\mathbf{v}}$ is a unit vector, $\Vert \frac{\mathbf{A}\vec{\mathbf{v}}}{\sqrt{\lambda }}\Vert =\frac{1}{\lambda }{\vec{\mathbf{v}}}^T{\mathbf{A}}^T\mathbf{A}\vec{\mathbf{v}}=\frac{1}{\lambda }{\vec{\mathbf{v}}}^T\lambda \vec{\mathbf{v}}=\Vert \vec{\mathbf{v}}{\Vert }^2=1$.

What we have just shown is:

$$\begin{array}{r}({\sigma }_1^2,{\vec{\mathbf{v}}}_1)\\ ⋮\\ ({\sigma }_k^2,{\vec{\mathbf{v}}}_k)\end{array}$$

are unit eigenpairs for ${\mathbf{A}}^T\mathbf{A}$, and

$$\begin{array}{r}({\sigma }_1^2,\frac{\mathbf{A}{\vec{\mathbf{v}}}_1}{{\sigma }_1})\\ ⋮\\ ({\sigma }_1^2,\frac{\mathbf{A}{\vec{\mathbf{v}}}_k}{{\sigma }_k})\end{array}$$

are unit eigenpairs for $\mathbf{A}{\mathbf{A}}^T$. Go back to the original rewritings - if we divide by ${\sigma }_1$, it’s exactly what we get. So

$$\begin{array}{r}({\sigma }_1^2,{\vec{\mathbf{u}}}_1)\\ ⋮\\ ({\sigma }_1^2,{\vec{\mathbf{u}}}_k)\end{array}$$

are unit eigenpairs for $\mathbf{A}{\mathbf{A}}^T$. So we HAVE shown that $\mathbf{A}$ has to be of the form $\mathbf{A}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^T$. $Q.E.D.$