Basic Linear Algebra : Singular Value Decomposition (SVD)

Singular Value Vecomposition (SVD) ขยายความจากวิธี eigendecomposition [1] ซึ่งใช้ได้กับ orthogonal matrix [3] เท่านั้น ให้สามารถ decompose matrix ที่มีขนาด $m\times n$ ได้ด้วยสมการ

$$\begin{array}{}\text{(1)}& M=U\mathrm{\Sigma }{A}^T\end{array}$$

เมื่อ

M คือ matrix ขนาด $n\times d$

U คือ orthogonal matrix ขนาด $n\times d$

$\mathrm{\Sigma }$ คือ diagonal matrix ขนาด $d\times d$

A คือ orthogonal matrix ขนาด $d\times d$

รูปที่ 1

รูปที่ 1 แสดงให้แนวคิดของ SVD จะเห็นว่า matrix M สามารถถูกแยก (decomposition) ออกเป็น 3 matrix ย่อย คือ U,Sigma และ A อาจมองได้ว่า element ของ M คือ span ของ dot product ระหว่าง column mantrix กับ row matrix ก็ได้

$$M=\sum _{i=1}^d{\sigma }_i{u}_i{a}_i^T$$

ยกต้วอย่าง ถ้ามี M = $\left[\begin{array}{cccc}1& 1& 0& 2\\ 1& 1& 1& 2\\ 2& 0& 1& 1\end{array}\right]$ จะแยก M ออกเป็น $$M=\left[\begin{array}{ccc}0.54& 0.71& -0.45\\ 0.54& -0.71& -0.45\\ 0.64& 0.00& 0.77\end{array}\right]\cdot \left[\begin{array}{ccc}3.57& 0.00& 0.00\\ 0.00& 2.00& 0.00\\ 0.00& 0.00& 1.12\end{array}\right]\cdot \left[\begin{array}{cccc}0.66& 0.30& 0.48& 0.48\\ 0.00& 0.00& -0.71& 0.71\\ 0.00& -0.81& -0.13& -0.13\end{array}\right]$$ ลองคำนวณแยกกัน $$\begin{array}{rl}{C}_1& =3.57\left[\begin{array}{c}0.54\\ 0.54\\ 0.64\end{array}\right]\cdot \left[\begin{array}{cccc}0.66& 0.30& 0.48& 0.48\end{array}\right]\\ \\ & =\left[\begin{array}{cccc}1.28& 0.59& 0.94& 0.94\\ 1.28& 0.59& 0.94& 0.94\\ 1.52& 0.7& 1.11& 1.11\end{array}\right]\\ \\ C_2& =2.00\left[\begin{array}{c}-0.45\\ -0.45\\ 0.77\end{array}\right]\cdot \left[\begin{array}{cccc}0.00& 0.00& -0.71& 0.71\end{array}\right]\\ \\ & =\left[\begin{array}{cccc}0.& 0.& -1.& 1.\\ 0.& 0.& 1.& -1.\\ 0.& 0.& 0.& 0.\end{array}\right]\\ \\ C_3& =1.12\left[\begin{array}{c}0.71\\ -0.71\\ 0.00\end{array}\right]\cdot \left[\begin{array}{cccc}0.56& -0.81& -0.13& -0.13\end{array}\right]\\ \\ & =\left[\begin{array}{cccc}-0.28& 0.41& 0.06& 0.06\\ -0.28& 0.41& 0.06& 0.06\\ 0.48& -0.7& -0.11& -0.11\end{array}\right]\\ \\ \therefore C_1+C_2+C_3& =M\end{array}$$

ก่อนที่จะเข้าเนื้อหาของที่มาของสมการ (1) มาทำความรู้จักกับ singular values กันก่อน

ถ้า M เป็น matrix ขนาด $n\times d$ และกำหนดให้ ${\lambda }_1,{\lambda }_2,{\lambda }_3,...,{\lambda }_d$ เป็น Eigen values ของ $M^T\cdot M$ โดย ${\lambda }_1\ge {\lambda }_2\ge {\lambda }_3...\ge {\lambda }_d\ge 0$ และ ${\sigma }_1=\sqrt{{\lambda }_1},{\sigma }_2=\sqrt{{\lambda }_2},{\sigma }_3=\sqrt{{\lambda }_3},...,{\sigma }_d=\sqrt{{\lambda }_d}$ เรียก ${\sigma }_1,{\sigma }_2,{\sigma }_3,...,{\sigma }_d$ ว่า "singular values" ของ A

การคำนวณ SVD

เพื่อให้เข้าใจที่มาของสมการ (1) จะเริ่มด้วยทบทวนการ decompose vector ในระบบ $R^2$ ก่อน

รูปที่ 2

ในรูปที่ 2 $\overrightarrow{v}$ ถูกแยก (decomposed) ออกเป็น ${\overrightarrow{v}}_x$ และ ${\overrightarrow{v}}_y$ ซึ่งเป็น projection บนแกน x,y ตามลำดับ $$\overrightarrow{v}={\overrightarrow{v}}_x+{\overrightarrow{v}}_y$$ และกำหนดให้

${\overrightarrow{a}}_x=\left[\begin{array}{c}1\\ 0\end{array}\right]$ และ ${\overrightarrow{a}}_y=\left[\begin{array}{c}0\\ 1\end{array}\right]$ เป็น unit vector บนแกน x และ y (basis) ตามลำดับ

$\theta$ คือมุมระหว่าง $\overrightarrow{v}$ กับแกน x $\gamma$ คือมุมระหว่าง $\overrightarrow{v}$ กับแกน y

จะได้ว่า $$\begin{array}{rl}\overrightarrow{v}\cdot {\overrightarrow{a}}_x& =\Vert \overrightarrow{v}\Vert \Vert {\overrightarrow{a}}_x\Vert cos\theta \\ \\ & =\Vert \overrightarrow{v}\Vert \frac{\Vert {\overrightarrow{v}}_x\Vert }{\Vert \overrightarrow{v}\Vert }\\ \\ \text{(2)}& \overrightarrow{v}\cdot {\overrightarrow{a}}_x& =\Vert {\overrightarrow{v}}_x\Vert =S_x\end{array}$$ ทำนองเดียวกัน $$\begin{array}{rl}\overrightarrow{v}\cdot {\overrightarrow{a}}_y& =\Vert \overrightarrow{v}\Vert \Vert {\overrightarrow{a}}_y\Vert cos\gamma \\ \\ & =\Vert \overrightarrow{v}\Vert \frac{\Vert {\overrightarrow{v}}_y\Vert }{\Vert \overrightarrow{v}\Vert }\\ \\ \text{(3)}& \overrightarrow{v}\cdot {\overrightarrow{a}}_y& =\Vert {\overrightarrow{v}}_y\Vert =S_y\end{array}$$ หมายเหตุ $\Vert {\overrightarrow{a}}_x\Vert =1,\Vert {\overrightarrow{a}}_y\Vert =1$

หากกรณีที่มี vector จำนวนมาก และอยู่ในระบบที่มี basis เป็น $\left[\begin{array}{c}{a}_1^x\\ a_2^x\end{array}\right]$ และ $\left[\begin{array}{c}{a}_1^y\\ a_2^y\end{array}\right]$ (ดูเรื่อง การย้าย basis of vector ใน [6] ประกอบ)  แสดงในรูปที่ 3(a)-(b)

รูปที่ 3

อ้างอิงจากสมการ (2),(3) พิจารณาที่ ${\overrightarrow{v}}_1$ $$\begin{array}{rl}{\overrightarrow{v}}_1\cdot {\overrightarrow{a}}^x& =S_1^x\\ {\overrightarrow{v}}_1\cdot {\overrightarrow{a}}^y& =S_1^y\\ \\ \text{(4)}& \left[\begin{array}{c}{v}_1^x\\ v_1^y\end{array}\right]\cdot \left[\begin{array}{c}{a}_1^x\\ a_2^x\end{array}\right]& =S_1^x\\ \text{(5)}& \left[\begin{array}{c}{v}_1^x\\ v_1^y\end{array}\right]\cdot \left[\begin{array}{c}{a}_1^y\\ a_2^y\end{array}\right]& =S_1^y\end{array}$$

สมการ (4),(5) สามารถถูกรวมเข้าด้วยกัน แล้วเขียนในรูปแบบของ matrix - vector multiplication ได้ $$\begin{array}{}\text{(6)}& \left[\begin{array}{cc}{v}_1^x& v_1^y\end{array}\right]\cdot \left[\begin{array}{cc}{a}_1^x& a_2^x\\ a_1^y& a_2^y\end{array}\right]=\left[\begin{array}{cc}{S}_1^x& S_1^y\end{array}\right]\end{array}$$

ถ้า ${\overrightarrow{v}}_2=\left[\begin{array}{c}{v}_2^x\\ v_2^y\end{array}\right]$ ถูกเพิ่มเข้าไปในระบบ สมการที่ (6) จะเปลี่ยนเป็น $$\begin{array}{}\text{(7)}& \left[\begin{array}{cc}{v}_1^x& v_1^y\\ v_2^x& v_2^y\end{array}\right]\cdot \left[\begin{array}{cc}{a}_1^x& a_2^x\\ a_1^y& a_2^y\end{array}\right]=\left[\begin{array}{cc}{S}_1^x& S_1^y\\ S_2^x& S_2^y\end{array}\right]\end{array}$$

พิจารณาสมการ (6)และ (7) ถ้ามีการเพิ่ม vector เข้าไปเรื่อย ๆ รูปแบบทั่วไปของสมการที่ (7) จะกลายเป็น $$\begin{array}{}\text{(8)}& \left[\begin{array}{cc}{v}_1^x& v_1^y\\ v_2^x& v_2^y\\ ⋮& ⋮\end{array}\right]\cdot \left[\begin{array}{cc}{a}_1^x& a_2^x\\ a_1^y& a_2^y\end{array}\right]=\left[\begin{array}{cc}{S}_1^x& S_1^y\\ S_2^x& S_2^y\\ ⋮& ⋮\end{array}\right]\end{array}$$

เขียนสมการ (8) ในรูปแบบอย่างง่ายคือ $$\begin{array}{}\text{(9)}& V\cdot A=S\end{array}$$ ถ้าให้ d = จำนวน dimension (axis) ข้อมูล และ n = จำนวน data points หรือ จำนวน vectors จะได้ขนาดของ matrix ในสมการ (9) ดังนี้

V เป็น rectangle matrix ขนาด $n\times d$

A เป็น square matrix ขนาด $d\times d$

S เป็น rectangle matrix ขนาด $n\times d$

พิจารณา matrix A ในสมการ (9) จะเห็นว่า row vector คือ unit vector ที่อยู่บน axis แต่ละ axis ซึ่งจะตั้งฉากต่อกันทุก axis นั่นคือ matrix A เป็น orthogonal matrix [7] นั่นคือ $A^{-1}=A^T$ อาศัยคุณสมบัตินี้ จะเขียนสมการ (9) ใหม่ได้เป็น $$\begin{array}{rl}V\cdot A& =S\\ V\cdot A\cdot A^{-1}& =S\cdot A^T\\ \text{(10)}& V& =S\cdot A^T\end{array}$$

มาถึงขั้นตอนนี้ จะเริ่มเห็นได้ว่าสมการ (10) มีลักษณะคล้ายกับสมการ (1) แต่ยังไม่เหมือนทีเดียว ตัวที่ขาดไปคือ U และ $\mathrm{\Sigma }$

มาพิจารณาดู S , elements ในแต่ละ column vectors ของ S คือค่าของ norm ของ projected vectors บนแต่ละ axis $$\left[\begin{array}{ccc}{S}_1^x& S_1^y& \cdots \\ S_2^x& S_2^y& \cdots \\ ⋮& ⋮& ⋮\end{array}\right]$$ หากต้องการทำให้แต่ละ column vector อยู่ในรูปของ unit vector ก็เพียงแต่หารแต่ละ column vector ด้วย norm ของแต่ละ column vector เอง $$\begin{array}{r}\left[\begin{array}{ccc}\frac{S_1^x}{{\sigma }_1}& \frac{S_1^y}{{\sigma }_2}& \cdots \\ \frac{S_2^x}{{\sigma }_1}& \frac{S_2^y}{{\sigma }_2}& \cdots \\ ⋮& ⋮& ⋮\end{array}\right]\end{array}$$

เมื่อ ${\sigma }_n$ คือ norm ของ column vector ที่ n นั่นคือ S จะถูกแยกออก

$$\begin{array}{rl}\left[\begin{array}{ccc}{S}_1^x& S_1^y& \cdots \\ S_2^x& S_2^y& \cdots \\ ⋮& ⋮& ⋮\end{array}\right]& =\left[\begin{array}{ccc}\frac{S_1^x}{{\sigma }_1}& \frac{S_1^y}{{\sigma }_2}& \cdots \\ \frac{S_2^x}{{\sigma }_1}& \frac{S_2^y}{{\sigma }_2}& \cdots \\ ⋮& ⋮& ⋮\end{array}\right]\cdot \left[\begin{array}{ccc}{\sigma }_1& 0& \cdots \\ 0& {\sigma }_2& \cdots \\ ⋮& ⋮& {\sigma }_n\end{array}\right]\\ \end{array}$$

หมายเหตุ $\sigma$ ไม่จำเป็นต้องใช้ norm ของ column vector การใช้ค่าคงที่อื่นจะได้ผลเช่นเดียวกัน ค่าที่นิยมใช้คือ Eigen value ($\lambda$ )โดย ${\sigma }^2=\lambda$

เขียนให้อยู่ในรูปแบบอย่างง่ายเป็น $$S=U\cdot \mathrm{\Sigma }$$ เมื่อ U เป็น orthogonal matrix (column vectors ตั้งฉากต่อกัน) ขนาด $n\times d$ และ $\mathrm{\Sigma }$ เป็น diagonal matrix ขนาด $d\times d$ นำเอา $U,\mathrm{\Sigma }$ ไปแทน S ใน (10) จะได้

$$\begin{array}{}\text{(11)}& V=U\mathrm{\Sigma }{A}^T\end{array}$$

เนื่องจาก A เป็น orthogonal matrix เราจึงอาจได้เห็นการเขียนสมการที่ (11) ในอีกรูปแบบคือ

$$\begin{array}{}\text{(12)}& V=U\mathrm{\Sigma }{A}^{-1}\end{array}$$

การคำนวณหา A ในสมการ (11),(12) จาก $$V=U\mathrm{\Sigma }{A}^T$$ dot product ด้วย $V^T$ $$\begin{array}{rl}{V}^T\cdot V& =V^T\cdot (U\mathrm{\Sigma }{A}^T)\\ V^T\cdot V& =(U\mathrm{\Sigma }{A}^T{)}^T\cdot (U\mathrm{\Sigma }{A}^T)\\ V^T\cdot V& =(A^T{)}^T{\mathrm{\Sigma }}^T{U}^{T}U\mathrm{\Sigma }{A}^T\\ V^T\cdot V& =A\mathrm{\Sigma }\mathrm{\Sigma }{A}^T\\ V^T\cdot V& =A{\mathrm{\Sigma }}^2{A}^T\end{array}$$ dot product ด้วย A $$\begin{array}{rl}{V}^T\cdot V\cdot A& =A{\mathrm{\Sigma }}^2{A}^{T}A\\ \text{(13)}& V^T\cdot V\cdot A& =A{\mathrm{\Sigma }}^2\end{array}$$

พิจารณาสมการ (13) จะเห็นว่ามีรูปแบบเดียวกับการหา Eigen value / Eigen vector เทียบเคียงดังนี้

1. $V^{T}V$ เป็น square matrix

2. A คือ matrix ที่มี column vectors คือ Eigen vectors ของ $V^{T}V$

3. ${\mathrm{\Sigma }}^2$ เป็น diagonal matrix ที่สร้างจาก Eigen values ของ $V^{T}V$ $$\begin{array}{rl}{\mathrm{\Sigma }}^2& =\left[\begin{array}{cccc}{\sigma }_1^2& 0& 0& \cdots \\ 0& {\sigma }_2^2& 0& \cdots \\ 0& 0& {\sigma }_3^2& \cdots \\ ⋮& ⋮& ⋮& {\sigma }_n^2\end{array}\right]=\left[\begin{array}{cccc}{\lambda }_1& 0& 0& \cdots \\ 0& {\lambda }_2& 0& \cdots \\ 0& 0& {\lambda }_3& \cdots \\ ⋮& ⋮& ⋮& {\lambda }_n\end{array}\right]\end{array}$$ โดย ${\lambda }_i={\sigma }_i^2$ เมื่อกลับไปพิจารณานิยามของ singular values ที่กล่าวไว้แล้วข้างต้น $Sigma$ คือ matrix ของ singular values ของ $V$ นั่นเอง

กล่าวโดยสรุปคือ

1) A หาได้จาก Eigen vector ของ $V^{T}V$

2) $\mathrm{\Sigma }$ สร้างจาก Eigen values ของ $V^{T}V$

การหา U ในสมการ (11),(12)

จาก $$V=U\mathrm{\Sigma }{A}^T$$ dot product ด้วย A ทั้งสองข้าง $$\begin{array}{rl}VA& =(U\mathrm{\Sigma }{A}^T)A\\ & =U\mathrm{\Sigma }\end{array}$$ dot product ด้วย ${\mathrm{\Sigma }}^{-1}$ทั้งสองข้าง $$\begin{array}{rl}VA{\mathrm{\Sigma }}^{-1}& =U\mathrm{\Sigma }{\mathrm{\Sigma }}^{-1}\\ \text{(14)}& U& =VA{\mathrm{\Sigma }}^{-1}\end{array}$$

A และ $\mathrm{\Sigma }$ หาได้จากวิธีการที่กล่าวมาแล้วในสมการ (13) และเนื่องจาก $\mathrm{\Sigma }$ เป็น orthogonal matrix ดังนั้น ${\mathrm{\Sigma }}^{-1}=\left[\begin{array}{cccc}\frac{1}{{\sigma }_1}& 0& 0& ...\\ 0& \frac{1}{{\sigma }_2}& 0& ...\\ 0& 0& \frac{1}{{\sigma }_3}& ...\\ ⋮& ⋮& ⋮& \frac{1}{{\sigma }_n}\end{array}\right]$

SVD นับว่าเป็นพื้นฐานสำคัญอันหนึ่งของ linear algebra ถูกนำไปใช้งานหลายด้านโดยเฉพาะ unsupervised machine learning ตัวอย่างที่มักถูกอ้างถึงบ่อยคือ Principle Componenet Analysis (PCA), ลดขนาดของภาพ, ระบบแนะนำสินค้าสมาชิก ฯลฯ ตัวอย่างการประยุกต์จะของกล่าวถึงในตอนต่อไป แต่ในตอนนี้ขอจบด้วย python code ที่เป็นการสรุปเนื้อหาที่กล่าวถึงในตอนนี้ดังนี้

    
import numpy as np
    
def SS_SVD(M):
    # construct square matrix (covariance matrix of itself)
    v_val,v_vec = np.linalg.eig(M.T @ M)
    
    # to store right singular matrix indecies
    i = []

    temp1 = v_val.copy()
    temp2 = v_val.copy()
    
    # singular values need to be sorted.
    temp1.sort()
    temp1 = temp1[::-1]
    
    for s in temp1 :
    	# to include only more than zero elements
        if np.round(s,4) > 0 :
            i.append(np.where(temp2==s)[0])
    
    # construct right singular matrix
    VV = v_vec[:,i]
    VV = VV.reshape((VV.shape[0],VV.shape[1]))
    
    # construct left singular matrix
    UU = []
    for j in range(VV.shape[1]):
        ui = (M @ VV[:,j])/np.sqrt(temp1[j])
        UU.append(ui)
    UU = np.array(UU)
    UU = UU.reshape((UU.shape[0],UU.shape[1]))
    
    # construct sigular matrix 
    singular_mat = np.diag(np.sqrt(temp1[:VV.shape[1]]))
    
    return UU.T,singular_mat,VV.T 
    
  

เอกสารอ้างอิง

[1] https://smarter-machine.blogspot.com/2021/03/basic-linear-algebra-eigendecomposition.html

[2] https://en.wikipedia.org/wiki/Singular_value_decomposition

[3] https://smarter-machine.blogspot.com/2021/03/basic-linear-algebra-orthogonal-matrix.html

[4] https://smarter-machine.blogspot.com/2021/02/basic-linear-algebra-vector-part.html#dot_pro

[5] https://smarter-machine.blogspot.com/2021/03/basic-linear-algebra-eigendecomposition.html

[6] https://smarter-machine.blogspot.com/2021/03/basic-linear-algebra-basis-of-vector.html

[7] https://smarter-machine.blogspot.com/2021/03/basic-linear-algebra-orthogonal-matrix.html

[8] https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Dimensionality_Reduction/Singular_Value_Decomposition

[9] https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Dimensionality_Reduction/Singular_Value_Decomposition