2021-1ํ•™๊ธฐ, ๋Œ€ํ•™์—์„œ โ€˜ํ†ต๊ณ„์  ๋ฐ์ดํ„ฐ๋งˆ์ด๋‹โ€™ ์ˆ˜์—…์„ ๋“ฃ๊ณ  ๊ณต๋ถ€ํ•œ ๋ฐ”๋ฅผ ์ •๋ฆฌํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ์ง€์ ์€ ์–ธ์ œ๋‚˜ ํ™˜์˜์ž…๋‹ˆ๋‹ค :)

7 minute read

2021-1ํ•™๊ธฐ, ๋Œ€ํ•™์—์„œ โ€˜ํ†ต๊ณ„์  ๋ฐ์ดํ„ฐ๋งˆ์ด๋‹โ€™ ์ˆ˜์—…์„ ๋“ฃ๊ณ  ๊ณต๋ถ€ํ•œ ๋ฐ”๋ฅผ ์ •๋ฆฌํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ์ง€์ ์€ ์–ธ์ œ๋‚˜ ํ™˜์˜์ž…๋‹ˆ๋‹ค :)

Set-upPermalink


formulas.

1. UUT=โˆ‘i=1nuiuiT, where U=(u1,โ€ฆ,un)โˆˆRnร—n

2. UDUT=โˆ‘i=1ndiuiuiT, where D=diag(di)

ํ–‰๋ ฌ๊ณฑ์„ ํ‘œํ˜„ํ•˜๋Š” ์œ ์šฉํ•œ ๋ฐฉ์‹์ด๋‹ˆ ์ต์ˆ™ํ•ด์ง€๋ฉด ์ข‹๋‹ค! ์•ž์œผ๋กœ ๋‚˜์˜ค๋Š” ๋‚ด์šฉ์—์„œ ์ž์ฃผ ๋“ฑ์žฅํ•œ๋‹ค!


Definition. Orthogonal Matrix

An <orthogonal matrix> U is a matrix such that UUT=UTU=In.


Spectral DecompositionPermalink


Theorem. Spectral Decomposition; Eigen Decomposition

For a real symmetric matrix AโˆˆRnร—n, there exists a diagonal matrix D=diag(d1,โ€ฆ,dn) and an orthogonal matrix U s.t. A=UDUT.

์ฆ‰, ๋ชจ๋“  symmetric matrix๋Š” UDUT์˜ ํ˜•ํƒœ๋กœ decompose ๊ฐ€๋Šฅํ•จ์„ ๋งํ•œ๋‹ค!


Note.

  • Each di is an real eigenvalue of A.
  • ui is the eigenvector associated with di, where U=(u1,โ€ฆ,un).
  • A=UDUT=โˆ‘i=1ndiuiuiT

<Spectral Decomposition>์€ ๊ธฐํ•˜ํ•™์  ์ดํ•ด๊ฐ€ ์ˆ˜๋ฐ˜๋˜์–ด์•ผ ํ•œ๋‹ค.

๋จผ์ €, orthogonal matrix U์— ๋Œ€ํ•ด U๋Š” ์„ ํ˜•๋ณ€ํ™˜์—์„œ ์ผ์ข…์˜ rotation matrix์˜ ์—ญํ• ์„ ํ•œ๋‹ค.

xโŸถUx

์ด์ œ Ax๋ฅผ ํ•ด์„ํ•˜๊ธฐ ์œ„ํ•ด UDUTx๋ฅผ ๋‹จ๊ณ„๋ณ„๋กœ ํ•ด์„ํ•ด๋ณด์ž.

1. UTx; ํšŒ์ „์„ ํ†ตํ•ด ์ขŒํ‘œ์ถ• ๋ณ€ํ™˜

UT๋Š” ํšŒ์ „ ๋ณ€ํ™˜์„ ์ˆ˜ํ–‰ํ•œ๋‹ค. ๋”ฐ๋ผ์„œ, e1, e2 ์ขŒํ‘œ๊ณ„ ์œ„์— ์žˆ๋˜ x๋ฅผ u1, u2 ์ขŒํ‘œ๊ณ„๋กœ ํšŒ์ „ ๋ณ€ํ™˜ํ•œ๋‹ค.

์ด๋•Œ, u1, u2๋Š” UT์˜ ๊ฐ ์—ด์œผ๋กœ์จ A์˜ eigen vector์ด๋‹ค.

๊ทธ๋ฆฌ๊ณ  UTx๋ฅผ ๊ณ„์‚ฐํ•ด๋ณด๋ฉด,

UTx=(u1,u2)โ‹…x=((xTu1)โ‹…u1(xTu2)โ‹…u2)

๊ฐ€ ๋˜๊ณ , ์ด๊ฒƒ์€ x๋ฅผ u1, u2 ์ถ•์œผ๋กœ <projection>ํ•œ ๊ฒƒ๊ณผ ๊ฐ™๋‹ค.

2. D(UTx); ์Šค์นผ๋ผ ๊ณฑ

D๋Š” diagnomal matrix์ด๊ธฐ ๋•Œ๋ฌธ์— u1, u2 ๋ฐฉํ–ฅ์˜ ๋ฒกํ„ฐ์— ๋Œ€ํ•œ ์Šค์นผ๋ผ ๊ณฑ์„ ํ•˜๋Š” ์—ญํ• ์ด๋‹ค.

3. U(DUTx); ์›๋ž˜์˜ ์ขŒํ‘œ์ถ•์œผ๋กœ ์—ญ-ํšŒ์ „

๋งˆ์ง€๋ง‰์œผ๋กœ ์ฒ˜์Œ์— ๊ณฑํ•œ UT์˜ ์—ญ-ํšŒ์ „ ๋ณ€ํ™˜์ธ U๋ฅผ ์ ์šฉํ•ด ๋‹ค์‹œ e1, e2์˜ ์ขŒํ‘œ๊ณ„๋กœ ๋˜๋Œ๋ ค ์ค€๋‹ค.

๊ทธ๋ž˜์„œ ์‹์„ ์ •๋ฆฌํ•˜๋ฉด, ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

UDUTx=UD(u1Txโ‹ฎunTx)=U(d1u1Txโ‹ฎdnunTx)=d1u1u1Tx+โ‹ฏ+dnununTx

Singular Value DecompositionPermalink

<Sepctral Theorem>์€ ๋Œ€์นญ ํ–‰๋ ฌ์— ๋Œ€ํ•ด์„œ ๊ธฐ์ˆ ํ•œ ์ •๋ฆฌ์˜€๋‹ค. ์ด๊ฒƒ์„ ์ผ๋ฐ˜์ ์ธ ํ˜•ํƒœ์˜ ํ–‰๋ ฌ๋กœ ์ผ๋ฐ˜ํ™”ํ•œ ๊ฒƒ์ด ๋ฐ”๋กœ <ํŠน์ด๊ฐ’ ๋ถ„ํ•ด Singular Value Decomposition>์ด๋‹ค. ๐Ÿ˜Ž


Theorem. Singular Value Decomposition

For any nร—p matrix A, there exist matrices UโˆˆRnร—n, DโˆˆRnร—p, and VโˆˆRpร—p s.t.

A=UDVT

where

  • D=diag(d1,โ€ฆ,dp) with diโ‰ฅ0
    • djs are called <singular value> of A.
  • U is an orthogonal matrix from AAT=U(ฮฃฮฃT)UT
  • V is an orthogonal matrix from ATA=V(ฮฃTฮฃ)VT

Low Rank ApproximationPermalink

SVD๋ฅผ ์ž˜ ์ด์šฉํ•˜๋ฉด, ํ–‰๋ ฌ A์— ๋Œ€ํ•œ <Low Rank Approximation> Ak๋ฅผ ์œ ๋„ํ•  ์ˆ˜ ์žˆ๋‹ค.

Let A=UDVT and assume that nโ‰ซp, then

A=[||u1โ‹ฏun||][d1โ‹ฑdpO][โˆ’v1Tโˆ’โ‹ฎโˆ’vpTโˆ’]=d1u1v1T+โ‹ฏ+dpupvpT

์ด๋•Œ, ํ‘œ๊ธฐ์˜ ํŽธ์˜๋ฅผ ์œ„ํ•ด singular value di์— ๋Œ€ํ•ด descending order๋กœ ํ‘œ๊ธฐ๋ฅผ ํ•œ๋‹ค.

whered1โ‰ฅd2โ‹ฏโ‰ฅdp

์ฃผ๋ชฉํ•  ์ ์€ ์‹์˜ ์šฐ๋ณ€์˜ uiviT์€ rank-1 matrix๋ผ๋Š” ์ ์ด๋‹ค. ์ฆ‰, SVD๋ฅผ ํ•˜๊ฒŒ ๋˜๋ฉด ํ–‰๋ ฌ A๋ฅผ rank-1์˜ matrix๋กœ ๋ถ„ํ•ดํ•œ ๊ฒƒ์ด ๋œ๋‹ค.

์ด์ œ ์œ„์˜ ๊ฒฐ๊ณผ๋ฅผ ๊ฐ€์ง€๊ณ  Approximation Ak๋ฅผ ์œ ๋„ํ•  ์ˆ˜ ์žˆ๋‹ค.

Ak=[||u1โ‹ฏuk||][d1โ‹ฑdkO][โˆ’v1Tโˆ’โ‹ฎโˆ’vkTโˆ’]=d1u1v1T+โ‹ฏ+dkukvkT

์ฆ‰, Ak๋Š” A๋ฅผ SVD๋กœ ๋ถ„ํ•ดํ•ด ํ‘œํ˜„ํ•œ ๊ฒƒ์—์„œ ์•ž์˜ k๊ฐœ์˜ rank-1 matrix๋ฅผ ๋ชจ์€ ๊ฒƒ์ด๋‹ค! ์šฐ๋ฆฌ๊ฐ€ di๋ฅผ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•ด ํ‘œํ˜„ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์—, ๋’ค๋กœ ๊ฐˆ์ˆ˜๋ก ์ž‘์€ dj๋ฅผ ์–ป๊ฒŒ ๋˜์–ด ์žˆ๋‹ค. ๊ทธ๋ž˜์„œ Ak๋Š” ์•ž์˜ k๊ฐœ di๋งŒ์„ ์„ ํƒํ•ด A๋ฅผ ๊ทผ์‚ฌํ•œ ๊ฒƒ์ด๋‹ค!

์ด๋•Œ, <Low Rank Approximation>์˜ error๋Š” ์•„๋ž˜์™€ ๊ฐ™์ด <Frobenius norm>์œผ๋กœ ์ •์˜ํ•œ๋‹ค.

โ€–Aโˆ’Akโ€–F2=tr((Aโˆ’Ak)T(Aโˆ’Ak))=dk+12+dk+22+โ‹ฏ+dp2

๊ทธ๋ž˜์„œ, ๋งŒ์•ฝ ๋’ท๋ถ€๋ถ„์˜ dk+1,โ‹ฏdp์˜ ํฌ๊ธฐ๊ฐ€ ์ž‘๋‹ค๋ฉด, Low Rank Approx๋Š” ์ถฉ๋ถ„ํžˆ ์ •ํ™•ํ•œ ๊ทผ์‚ฌ๋ฅผ ์ˆ˜ํ–‰ํ•จ์„ ๋ณด์žฅํ•  ์ˆ˜ ์žˆ๋‹ค!!

ps. ์ด๋Ÿฐ Low Rank Approx๋Š” ์ƒ๊ฐ๋ณด๋‹ค ์ž์ฃผ ์‚ฌ์šฉ๋˜๋Š” ๊ธฐ๋ฒ•์ด๋ผ๊ณ  ํ•œ๋‹ค.

ps. Netflix์˜ ์ถ”์ฒœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ Contest์—์„œ ์ด SVD๋ฅผ ํ™œ์šฉํ•ด Low Rank Approx๋ฅผ ํ•˜๋Š” ์ถ”์ฒœ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•œ ํŒ€์ด ์šฐ์Šน์„ ์ฐจ์ง€ํ–ˆ๋‹ค๊ณ  ํ•œ๋‹ค.


์ง€๊ธˆ๊นŒ์ง€ ํ–‰๋ ฌ์„ ๋ถ„ํ•ดํ•˜๋Š” ๋‘ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ธ <Spectral Decomposition>๊ณผ <Singular Value Decomposition>๋ฅผ ์‚ดํŽด๋ดค๋‹ค. ์ด ๋‘ ๊ฐœ๋…์€ ์ด์–ด์ง€๋Š” ๋‚ด์šฉ์ธ ํ–‰๋ ฌ์˜ <Nonnegative Definite>, <Positive Definite>๋ฅผ ์ •์˜ํ•  ๋•Œ ๋ฐ”ํƒ•์ด ๋œ๋‹ค.

๐Ÿ‘‰ Supp-1: Linear Algebra - 4