010. Overview & SVD

Overview & SVD

Spectral Decomposition

$$\begin{array}{rl}A=\left(\begin{array}{ccccc}{a}_{11}& & \cdots & & a_{1n}\\ ⋮& \ddots & & & ⋮\\ a_{i1}& & \ddots & & a_{1n}\\ ⋮& & & \ddots & ⋮\\ a_{m1}& & \cdots & & a_{mn}\end{array}\right)=(a_{ij})& =\left(\begin{array}{c}{r}_1\\ ⋮\\ r_m\end{array}\right)\\ & \\ & =\left(\begin{array}{ccc}{c}_1& \cdots & c_m\end{array}\right)\end{array}$$

for symmetric matrix $A$:

$$A_{p\times p}=\Gamma \Lambda {\Gamma }^T=\sum _{j=1}^p{\lambda }_j{\gamma }_j{\gamma }_j^T$$ $$\begin{array}{rlrl}& \Lambda =diag\{{\lambda }_1,\cdots ,{\lambda }_p\}& & ={\left(\begin{array}{ccc}{\lambda }_1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & {\lambda }_p\end{array}\right)}_{p\times p}\\ & \Gamma & & ={\left(\begin{array}{ccc}{\gamma }_1,& \cdots ,& {\gamma }_p\end{array}\right)}_{p\times p}\end{array}$$

where ${\gamma }_j$ is evec of $A$. Therefore $\Gamma$ is orthogonal Matrix.

let symmetric Matrix of rank $r$, $A_{p\times p}$, $(r\le p)$. Then there exists orthogonal Matrix ${\Gamma }_{p\times p}$, which means ${\Gamma }^T\Gamma =I_p$ and

$$A=\Gamma \Lambda {\Gamma }^T=\Gamma \left(\begin{array}{cc}{\Lambda }_1& 0\\ 0& 0\end{array}\right){\Gamma }^T={\Gamma }_1{\Lambda }_1{\Gamma }_1^T$$

at here, by letting ${\delta }_i=$ i-th ev, $i=1,\cdots ,r$, then

$$\begin{gathered} \Gamma =\left(\begin{array}{c}\{{\Gamma }_1{\}}_{p\times r},\{{\Gamma }_0{\}}_{p\times (p-r)}\end{array}\right) \\ \Lambda =diag\{{\lambda }_1,\cdots ,{\lambda }_r\}={\left(\begin{array}{ccc}{\lambda }_1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & {\lambda }_r\end{array}\right)}_{r\times r} \end{gathered}$$

then ${\Gamma }_1^T{\Gamma }_1=I_r,{\Gamma }_1^T{\Gamma }_0=0$ and

$$A^2=A^{\prime }A=A{A}^{\prime }=({\Gamma }_1{\Lambda }_1{\Gamma }_1^T{)}^{\prime }{\Gamma }_1{\Lambda }_1{\Gamma }_1^T={\Gamma }_1{\Lambda }_1{\Gamma }_1^T\ast {\Gamma }_1{\Lambda }_1{\Gamma }_1^T={\Gamma }_1{\Lambda }_1^2{\Gamma }_1^T$$

let $\{{\gamma }_i{\}}_{p\times 1}$ be i-th column vector of $\Gamma$. then

$${\gamma }_i^{\prime }{\gamma }_i=\{\begin{array}{llc}1& & i=j\\ 0& & i\ne j\end{array}$$

thus

$$\begin{array}{rlrl}A& ={\Gamma }_1{\Lambda }_1{\Gamma }_1^T& & =\sum _{i=1}^r{\lambda }_i{\gamma }_i{\gamma }_i^{\prime }\\ A^{\prime }A& ={\Gamma }_1{\Lambda }_1^2{\Gamma }_1^T& & =\sum _{i=1}^r{\lambda }_i^2{\gamma }_i{\gamma }_i^{\prime }\\ A{A}^{\prime }& =& & \\ {\gamma }_k^{\prime }A& ={\lambda }_k{\gamma }_k^{\prime }{\gamma }_k{\gamma }_k^{\prime }& & ={\lambda }_k{\gamma }_k^{\prime }\\ A{\gamma }_k& ={\lambda }_k{\gamma }_k{\gamma }_k^{\prime }{\gamma }_k& & ={\lambda }_k{\gamma }_k\end{array}$$

remark

let orthogonal Matrix $\Gamma$, therefore ${\Gamma }^{\prime }\Gamma =I$, and $\det (\Gamma )=|\Gamma |=1$.

let symmetric Matrix $A_{p\times p}$ with full rank. then by SVD,

$$\det (A)=|A|=|\Gamma ||\Lambda ||{\Gamma }^T|=|\Lambda |=\left|\begin{array}{ccc}\lambda & \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & {\lambda }_p\end{array}\right|=\prod _{i=1}^p{\lambda }_i$$

let symmetric Matrix $A_{p\times p}$ with full rank. then by SVD,

$$\exists n\in \mathbb{R}:A^n=(\Gamma \Lambda {\Gamma }^{\prime })\ast (\Gamma \Lambda {\Gamma }^{\prime })\cdots (\Gamma \Lambda {\Gamma }^{\prime })=\Gamma {\Lambda }^n{\Gamma }^{\prime }$$

in particular, a Cov Matrix $\Sigma$ can be written by

$$\begin{gathered} \Sigma =\Gamma \Lambda {\Gamma }^T=\sum _{i=1}^r{\lambda }_i{\gamma }_i{\gamma }_i^{\prime } \\ {\Sigma }^{-1}=\Gamma {\Lambda }^{-1}{\Gamma }^T=\sum _{i=1}^r{\lambda }_i^{-1}{\gamma }_i{\gamma }_i^{\prime } \\ {\Sigma }^{-\frac{1}{2}}=\Gamma {\Lambda }^{-\frac{1}{2}}{\Gamma }^T=\sum _{i=1}^r{\lambda }_i^{-\frac{1}{2}}{\gamma }_i{\gamma }_i^{\prime } \end{gathered}$$

Singular value Decomposition: General-version

decomposition of any aribtrary Matrix with rank $r$, $A_{n\times p}={\Gamma }_{n\times r}\Lambda {△}_{p\times r}^{\prime }={\sum }_{j=1}^r{\lambda }_j{\gamma }_j{\delta }_j^{\prime }$.

$\Lambda =diag({\lambda }_1,\cdots ,{\lambda }_r),{\lambda }_j>0$. 이때 ${\lambda }_i$는 $A{A}^{\prime }$나 $A^{\prime }A$의 non-zero ev.

$\Gamma$ 와 $△$는 $A{A}^{\prime }$와 $A^{\prime }A$의 corresponding $r$ evec으로 구성. 따라서 Both ${\Gamma }^{\prime }\Gamma ={△}^{\prime }△=I_r$, i.e., are column orthogonal.

thus

$$\begin{array}{rlrl}A& =\Gamma \Lambda {△}^T& & =\sum _{i=1}^r{\lambda }_i{\gamma }_i{\delta }_i^{\prime }\\ A^{\prime }A& =△{\Lambda }^2{△}^T& & =\sum _{i=1}^r{\lambda }_i^2{\delta }_i{\delta }_i^{\prime }\\ A{A}^{\prime }& =\Gamma {\Lambda }^2{\Gamma }^T& & =\sum _{i=1}^r{\lambda }_i^2{\gamma }_i{\gamma }_i^{\prime }\\ {\gamma }_k^{\prime }A& ={\gamma }_k^{\prime }\Gamma \Lambda {△}^T& & ={\lambda }_k{\delta }_k^{\prime }\\ A{\delta }_k& =\Gamma \Lambda {△}^T{\delta }_k& & ={\lambda }_k{\gamma }_k\end{array}$$

a	b
\begin{alignat}{2} A &= \Gamma \Lambda \triangle^T &&=\sum_{i=1}^r \lambda_i \pmb \gamma_i \pmb \delta_i ' \\ A'A &= \triangle \Lambda^2 \triangle^T &&=\sum_{i=1}^r \lambda_i^2 \pmb \delta_i \pmb \delta_i ' \\ AA'&= \Gamma \Lambda^2 \Gamma^T &&=\sum_{i=1}^r \lambda_i^2 \pmb \gamma_i \pmb \gamma_i ' \\ \gamma_k ' A &= \gamma_k ' \Gamma \Lambda \triangle^T &&= \lambda_k \pmb \delta_k ' \\ A \delta_k &= \Gamma \Lambda \triangle^T \delta_k &&= \lambda_k \pmb \gamma_k \end{alignat}	<br>\begin{alignat}{2} A &= \Gamma_1 \Lambda_1 \Gamma^T_1 &&=\sum_{i=1}^r \lambda_i \pmb \gamma_i \pmb \gamma_i ' \\ A'A &= \Gamma_1 \Lambda_1^2 \Gamma^T_1 &&=\sum_{i=1}^r \lambda_i^2 \pmb \gamma_i \pmb \gamma_i ' \\ AA'&= && \\ \gamma_k ' A &= \lambda_k \gamma_k ' \gamma_k \gamma_k ' &&= \lambda_k \pmb\gamma_k ' \\ A \gamma_k &= \lambda_k \gamma_k \gamma_k ' \gamma_k &&= \lambda_k \pmb \gamma_k \end{alignat}<br>
c	d

therefore, generalized inverse matrix, G-inverse Matrix $A^{-}$ will be

$$\begin{array}{rlrl}A& =\Gamma \Lambda {△}^T& & =\sum _{i=1}^r{\lambda }_i{\gamma }_i{\delta }_i^{\prime }\\ A^{-}& =△{\Lambda }^{-1}{\Gamma }^{\prime }& & =\sum _{i=1}^r{\lambda }_i^{-1}{\delta }_i{\gamma }_i^{\prime }\\ A{A}^{-}A& =\Gamma \Lambda {△}^T\ast △{\Lambda }^{-1}{\Gamma }^{\prime }\ast \Gamma \Lambda {△}^T& & =\sum _{i=1}^r{\lambda }_i{\gamma }_i{\delta }_i^{\prime }=A\end{array}$$

Singular value Decomposition: Another-version

rank $r$ arbitrary Matrix $A_{n\times p}={\Gamma }_{n\times r}\Lambda {△}_{p\times r}^T={\sum }_{i=1}^r{\lambda }_i^{\frac{1}{2}}{\gamma }_i{\delta }_i^{\prime }$

$\Lambda =diag({\lambda }_1^{\frac{1}{2}},\cdots ,{\lambda }_r^{\frac{1}{2}}),{\lambda }_j^{\frac{1}{2}}>0$. 이때 ${\lambda }_i$는 $A{A}^{\prime }$와 $A^{\prime }A$의 non-zero ev.

$\Gamma ,△$는 $A{A}^{\prime }$와 $A^{\prime }A$의 corresponding $r$ evec으로 구성. 따라서 Both ${\Gamma }^{\prime }\Gamma ={△}^{\prime }△=I_r$, i.e., are column orthogonal.

Quadratic Forms

for symmetric Matrix $A_{p\times p}$, vector $x\in {\mathbb{R}}^p$:

$$Q(x)=x^{\prime }Ax=\sum _{i=1}^p\sum _{j=1}^p{a}_{ij}{x}_i{x}_j\text{\hspace{1em}(quadratic form)}$$ $$\begin{array}{rl}\forall x\ne 0:Q(x)& >0\\ & \\ \forall x\ne 0:Q(x)& \ge 0\end{array}\text{\hspace{1em}(positive definite)(positive semi-definite)}$$

if corresponding quadratic form $Q(\cdot )$ is positive definite(semi-definite), $A$ is called positive definite(semi-definite). This is written by $A>0(\ge 0)$.

propositions

if $A=A^{\prime }$, and $Q(x)=x^{\prime }Ax$ is corresponding quadratic form, then $\exists y={\Lambda }^{T}x:Q(x)=x^{\prime }Ax={\sum }_{i=1}^p{\lambda }_1{y}_i^2$, ${\lambda }_i$ is ev of $A$.

$$A>0⟺\forall {\lambda }_i>0,i=1,\cdots ,p$$ $$A>0⟹|A|>0,\exists A^{-1}$$

$A=A^{\prime },B=B^{\prime },B>0$, then maximum of $\frac{x^{\prime }Ax}{x^{\prime }Bx}$ is given by the largest ev of $B^{-1}A$.

the vector which maximizes(minimizes) $\frac{x^{\prime }Ax}{x^{\prime }Bx}$ is the corresponding evec of $B^{-1}A$ for largest(smallest) ev of $B^{-1}A$.

more generally, for ev of $B^{-1}A$, ${\lambda }_1,\cdots ,{\lambda }_p$,

$$\max \left(\frac{x^{\prime }Ax}{x^{\prime }Bx}\right)={\lambda }_1\ge \cdots \ge {\lambda }_p=\min \left(\frac{x^{\prime }Ax}{x^{\prime }Bx}\right)$$

if $x^{\prime }Bx=1$, then

$$\max \left(x^{\prime }Ax\right)={\lambda }_1\ge \cdots \ge {\lambda }_p=\min \left(x^{\prime }Ax\right)$$

Partitioned Matrices

$A_{n\times p},B_{p\times n}$ and $n\ge p$. then

$$\left|\begin{array}{cc}-\lambda I_n& -A\\ B& I_p\end{array}\right|=(-\lambda {)}^{n-p}\ast \left|BA-\lambda I_n\right|=\left|AB-\lambda I_n\right|$$

for $A_{n\times p},B_{p\times n}$, the non-zero ev of $AB$ and $BA$ are the same and have the same multiplicity. if $x$ is evec of $AB$ for an ev $\lambda \ne 0$, then $y=Bx$ is an evec of $BA$.

for $A_{n\times p},B_{q\times n},a_{p\times 1},b_{q\times 1}$, if $rank\left(AabB\right)\le 1$, then non-zero ev, if it exists, equals $b^{\prime }BAa$ with evec $Aa$.

Geometrical Aspects

mutually orthogonal $x_1,\cdots ,x_k⟺\forall i,j:x_i^{\prime }{x}_j$

In that case, $X=\left(x_1,\cdots ,x_k\right)$ has rank $k$, and $X^{\prime }X$ is a diagonal Matrix with $x_i^{\prime }{x}_i$ in the i-th diagonal position.

let’s consider bivariate data $(x_i,y_i),i=1,\cdots ,n$, and let ${\tilde{x}}_i=x_i-\bar{x},{\tilde{y}}_i=y_i-\bar{y}$. then correlation b/w $x$ and $y$ is

$$\frac{{\sum }_{i=1}^n(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\left[{\sum }_{i=1}^n(x_i-\bar{x}{)}^2\right]\ast \left[{\sum }_{i=1}^n(y_i-\bar{y}{)}^2\right]}}=\frac{{\tilde{x}}^{\prime }\tilde{y}}{\Vert \tilde{x}\Vert \ast \Vert \tilde{y}\Vert }=\cos (\theta )$$

where $\theta$ is the angle b/w the deviation vectors $\tilde{x}$ and $\tilde{y}$.

For two dimensions, the rotation can be expressed:

\begin{alignat}{2} \pmb y &= \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} &&= \begin{pmatrix} \cos(\theta) & \sin(\theta) \\ -\sin(\theta) & \cos(\theta) \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} && = \Gamma \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \\ &= \Gamma \pmb x \tag{clockwise rotation} \\ \\ \pmb y & &&= \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} &&= \Gamma ' \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \\ & = \Gamma ' \pmb x \tag{counter-clockwise rotation} \end{alignat}

Column, Row and Null Space

Matrix $X_{n\times p}$:

$$\begin{array}{rlrl}\mathcal{C}(X)& =\{x\in {\mathbb{R}}^n|\exists a\in {\mathbb{R}}^{p}s.t.Xa=x\}& & \subseteq {\mathbb{R}}^n\\ \mathcal{N}(X)& =\{y\in {\mathbb{R}}^p|Xy=0\}& & \subseteq {\mathbb{R}}^p\\ \mathcal{R}(X)& =\{z\in {\mathbb{R}}^p|\exists b\in {\mathbb{R}}^{n}s.t.X^{\prime }b=z\}& & \subseteq {\mathbb{R}}^p\\ & =\mathcal{C}(X^{\prime })& & \end{array}\text{\hspace{1em}(column (range) space)(null space)(row space)(column space of X‘)}$$

Spaces by Singular Value Decomposition: General-version,

Matrix $X_{n\times p}$ with $rank(X)=r$:

$$\begin{array}{rl}X& =\Gamma \Lambda {△}^T\\ & =\sum _{i=1}^r{\lambda }_i{\gamma }_i{\delta }_i^{\prime }\\ \mathcal{C}(X)& =\{{\gamma }_1,\cdots ,{\gamma }_r\}\\ \mathcal{N}(X)& =\{{\delta }_{r+1},\cdots ,{\delta }_p\}\\ \mathcal{R}(X)& =\{{\delta }_1,\cdots ,{\delta }_r\}\end{array}$$

• note: Matrix $X_{n\times p}$ with $rank(X)=r$

$$\begin{array}{rl}\mathcal{N}(X)& =\mathcal{C}(X^{\prime }{)}^{\perp }=\mathcal{R}(X{)}^{\perp }\\ \mathcal{N}(X{)}^{\perp }& =\mathcal{C}(X^{\prime })=\mathcal{R}(X)\\ & \\ & \\ \mathcal{C}(X^{\prime }X)& =\mathcal{C}(X^{\prime })=\mathcal{R}(X)\\ & \\ & \\ \dim \left(\mathcal{C}(X)\right)& =\dim \left(\mathcal{R}(X)\right)\\ =rank(X)& =rank(X^{\prime })=rank(X^{\prime }X)\\ & =r\le \min (n,p)\end{array}$$

$X^{\prime }X$ has full rank (is nonsingular) $⟺$ if $X$ has full column rank ($X$ has linearly independent columns).