Supp-1: Linear Algebra - 3
2021-1ํ๊ธฐ, ๋ํ์์ โํต๊ณ์ ๋ฐ์ดํฐ๋ง์ด๋โ ์์ ์ ๋ฃ๊ณ ๊ณต๋ถํ ๋ฐ๋ฅผ ์ ๋ฆฌํ ๊ธ์ ๋๋ค. ์ง์ ์ ์ธ์ ๋ ํ์์ ๋๋ค :)
Set-upPermalink
formulas.
1.
2.
ํ๋ ฌ๊ณฑ์ ํํํ๋ ์ ์ฉํ ๋ฐฉ์์ด๋ ์ต์ํด์ง๋ฉด ์ข๋ค! ์์ผ๋ก ๋์ค๋ ๋ด์ฉ์์ ์์ฃผ ๋ฑ์ฅํ๋ค!
Definition. Orthogonal Matrix
An <orthogonal matrix>
Spectral DecompositionPermalink
Theorem. Spectral Decomposition; Eigen Decomposition
For a real symmetric matrix
์ฆ, ๋ชจ๋ symmetric matrix๋
Note.
- Each
is an real eigenvalue of . is the eigenvector associated with , where .
<Spectral Decomposition>์ ๊ธฐํํ์ ์ดํด๊ฐ ์๋ฐ๋์ด์ผ ํ๋ค.
๋จผ์ , orthogonal matrix
์ด์
1.

์ด๋,
๊ทธ๋ฆฌ๊ณ
๊ฐ ๋๊ณ , ์ด๊ฒ์

2.

3.
๋ง์ง๋ง์ผ๋ก ์ฒ์์ ๊ณฑํ

๊ทธ๋์ ์์ ์ ๋ฆฌํ๋ฉด, ์๋์ ๊ฐ๋ค.
Singular Value DecompositionPermalink
<Sepctral Theorem>์ ๋์นญ ํ๋ ฌ์ ๋ํด์ ๊ธฐ์ ํ ์ ๋ฆฌ์๋ค. ์ด๊ฒ์ ์ผ๋ฐ์ ์ธ ํํ์ ํ๋ ฌ๋ก ์ผ๋ฐํํ ๊ฒ์ด ๋ฐ๋ก <ํน์ด๊ฐ ๋ถํด Singular Value Decomposition>์ด๋ค. ๐
Theorem. Singular Value Decomposition
For any
where
with s are called <singular value> of .
is an orthogonal matrix from is an orthogonal matrix from
Low Rank ApproximationPermalink
SVD๋ฅผ ์ ์ด์ฉํ๋ฉด, ํ๋ ฌ
Let
์ด๋, ํ๊ธฐ์ ํธ์๋ฅผ ์ํด singular value
์ฃผ๋ชฉํ ์ ์ ์์ ์ฐ๋ณ์
์ด์ ์์ ๊ฒฐ๊ณผ๋ฅผ ๊ฐ์ง๊ณ Approximation
์ฆ,
์ด๋, <Low Rank Approximation>์ error๋ ์๋์ ๊ฐ์ด <Frobenius norm>์ผ๋ก ์ ์ํ๋ค.
๊ทธ๋์, ๋ง์ฝ ๋ท๋ถ๋ถ์
ps. ์ด๋ฐ Low Rank Approx๋ ์๊ฐ๋ณด๋ค ์์ฃผ ์ฌ์ฉ๋๋ ๊ธฐ๋ฒ์ด๋ผ๊ณ ํ๋ค.
ps. Netflix์ ์ถ์ฒ ์๊ณ ๋ฆฌ์ฆ Contest์์ ์ด SVD๋ฅผ ํ์ฉํด Low Rank Approx๋ฅผ ํ๋ ์ถ์ฒ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ ํ์ด ์ฐ์น์ ์ฐจ์งํ๋ค๊ณ ํ๋ค.
์ง๊ธ๊น์ง ํ๋ ฌ์ ๋ถํดํ๋ ๋ ๊ฐ์ง ๋ฐฉ๋ฒ์ธ <Spectral Decomposition>๊ณผ <Singular Value Decomposition>๋ฅผ ์ดํด๋ดค๋ค. ์ด ๋ ๊ฐ๋ ์ ์ด์ด์ง๋ ๋ด์ฉ์ธ ํ๋ ฌ์ <Nonnegative Definite>, <Positive Definite>๋ฅผ ์ ์ํ ๋ ๋ฐํ์ด ๋๋ค.