Low-rank Approximation

Definition:

• SVD is mainly used to find Dyads in low rank matrix for approximate data to a lower-rank matrix
• From the SVD result, a $m\times n$ matrix with rank $k\le m,n$ if it can be written as $P{Q}^{⊺}$, with $P=[p_1,...,p_k]\in {\mathbb{R}}^{m\times k}$ and $Q=[q_1,...,q_k]\in {\mathbb{R}}^{n\times k}$, the matrix can be expressed as a sum of $k$ dyads, $P{Q}^{⊺}={\sum }_{i=1}^k{p}_i{q}_i^{⊺}$
• Geometric intepretation:
  • If a $m\times n$ matrix $A$ can be written as a single dyad: $A=p{q}^{⊺}$, this mean that every column (and row) is proportional to a single vector $p:A{e}_j=(q^{⊺}{e}_j)p$ for $j=1,...,n$
    • where $p\in {\mathbb{R}}^m$ and $q\in {\mathbb{R}}^n$
    • and $e_j$ is the $i$-th unit vector in ${\mathbb{R}}^m$
  • If each column represents a data point, all these points are on a line going through 0 with $\mathbf{span}\{p\}$
• Sum of Dyads:
  • If $A$ can be expressed as a sum of $k$ dyads: then each column is a linear combination of $k$ vectors:
    • $A{e}_j={\sum }_{i=1}^k(q_i^{⊺}{e}_j)p_i,j=1,...,n$
  • If each column represents a data points, all these pints are on a subspace, $span\{p_1,...,p_k\}$. In practice, it is better if the $p_i$ ’s are independent, as then each dyad brings in “new information”
• Dyads in low rank matrix

Rank-one approximation:

• ${\min }_{p,q}||A-p{q}^{⊺}|{|}_F^2$, can be used via SVD

Low-rank approximation:

• Approximate with $k<<m,n$ rank, thereby create a new dataset with information close enough to the old dataset
• We use SVD as it provides the closest subspace in Frobenius/Euclidean norm and cheaper with independent components
• Let $A\in {\mathbb{R}}^{m,n}$ be a given matrix, with $rank(A)=r>0$.
• Consider the problem of approximating A with a matrix of lower rank, which is ${\min }_{A_k\in {\mathbb{R}}^{m,n}}||A-A_k|{|}_F^2$ subject $rank(A_k)=k$ where $1\le k\le r$
• Let $A=U\sum ^{~}{V}^{⊺}={\sum }_{i=1}^r{\sigma }_i{u}_i{v}_i^{⊺}$
• Then only take sum of first $k$ terms which is $A_k={\sum }_{i=1}^k{\sigma }_i{u}_i{v}_i^{⊺}$
• Define ratio of retained/total infor: ${\eta }_k=\frac{||A_k|{|}_F^2}{||A|{|}_F^2}=\frac{{\sigma }_1^2+...+{\sigma }_k^2}{{\sigma }_1^2+...+{\sigma }_r^2}$
• Then the relative (squared) norm approximation error: $e_k=\frac{||A-A_k|{|}_F^2}{||A|{|}_F^2}=\frac{{\sigma }_{k+1}^2+...+{\sigma }_r^2}{{\sigma }_1^2+...+{\sigma }_r^2}=1-{\eta }_k$
• Plot differen ${\eta }_k$ as a function of $k$ will show which value of $k$ is good enough

Low-dimensional representation of data:

• Given a $n\times m$ data matrix $X=\left[x_1,\dots ,x_m\right]$, and the SVD-based rank- $k$ approximation $\tilde{X}$ to $X$, we have $X=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T=US{V}^T\approx \tilde{X}=\sum _{i=1}^k{\sigma }_i{u}_i{v}_i^T=\tilde{U}\tilde{S}{\tilde{V}}^T$ where:
  • $\nabla \tilde{U}=\left[u_1,\dots ,u_k\right]\in {\mathbb{R}}^{n\times k}$
  • $\nabla \tilde{V}=\left[v_1,\dots ,v_k\right]\in {\mathbb{R}}^{m\times k}$
  • $\tilde{S}=\mathrm{diag}\left({\sigma }_1,\dots ,{\sigma }_k\right)\in {\mathbb{R}}^{k\times k}$
• Thus: projecting data points, for any data point $x_j:x_j=X{e}_j\approx x_j^{\prime }:=\tilde{X}{e}_j=\tilde{U}\tilde{S}{\tilde{V}}^T{e}_j=\tilde{U}{h}_j$ where:
  • $h_j:=\tilde{S}{\tilde{V}}^T{e}_j={\left({\sigma }_i{v}_i{}^T{e}_j\right)}_{1\le i\le k}\in {\mathbb{R}}^k$
• Vector $h_j$ is a low-dimensional representation of data point $x_j$. More compactly: $X\approx \tilde{U}H,H=\tilde{S}{\tilde{V}}^T\in {\mathbb{R}}^{k\times m}$
• We may also project features (rows $f_i^{⊺}$ of $X,1\le i\le n$) using the same derivation as before, with $X^{⊺}$ instead of $X:X=\left(\begin{array}{c}{f}_1^{⊺}\\ .\\ .\\ f_n^{⊺}\end{array}\right)$ with $f_i\approx V{S}^{⊺}{U}^{⊺}{e}_i,1\le i\le n$
  • More compact: $X^{⊺}\approx \tilde{V}H,H={\tilde{S}}^{⊺}{\tilde{U}}^{⊺}$

SVD-based auto-encoder:

• For any data point: $x_j\approx \tilde{X}{e}_j=\tilde{U}{h}_j$ for $h_j:=\tilde{S}{\tilde{V}}^{⊺}{e}_j\in {\mathbb{R}}^k$
• Thus, any data point can be encoded to lower dimension
• Given a low-dimensional representation $h$ of $x$, we can decode, i.e. go back to the approximation $x\prime$, via $x^{\prime }=\tilde{U}$

Power iteration:

• Solve the problem ${\min }_{p,q}||A-p{q}^{⊺}|{|}_F^2:p\in {\mathbb{R}}^n,q\in {\mathbb{R}}^m$, alternatively over $p,q$
• Each step is a simple closed-form formula
• Convergence improved when formulated as an iteration over normalized vectors: setting $u=p||p|{|}_2,v=q/||q|{|}_2$:
  • $u=\frac{Av}{||Av|{|}_2}$ and $v=\frac{A^{⊺}u}{||A^{⊺}u|{|}_2}$
• Works extrememly well for large, sparse A as there are empty information easily cut