SVD의 직관은 무엇입니까? (SVD)에 대해 읽었습니다. 거의 모든

단일 값 분해 (SVD)에 대해 읽었습니다. 거의 모든 교과서에서 주어진 사양으로 행렬을 세 개의 행렬로 분해한다고 언급되어 있습니다.

그러나 행렬을 그러한 형태로 나누는 직관은 무엇입니까? 차원 축소를위한 PCA 및 기타 알고리즘은 알고리즘에 뛰어난 시각화 속성이 있지만 SVD에서는 그렇지 않다는 점에서 직관적입니다.

답변

행렬 (실제, )
의 SVD를
로 쓰십시오. 여기서 는 이고, 는 대각선 이고 는 입니다. 행렬 와 의 열의 관점에서 우리는
$X$

X

$X$ $n \times p$

n \times p

$n\times p$

X = U D V^{T}

$X = U D V^T$ $U$

U

$U$ $n \times p$

n \times p

$n\times p$ $D$

D

$D$ $p \times p$

p \times p

$p\times p$ $V^{T}$

V^{T}

$V^T$ $p \times p$

p \times p

$p\times p$ $U$

U

$U$ $V$

V

$V$ $X = \sum_{i = 1}^{p} d_{i} u_{i} v_{i}^{T}$

X = \sum_{i = 1}^{p} d_{i} u_{i} v_{i}^{T}

$X=\sum_{i=1}^p d_i u_i v_i^T$ . 이것은 가 랭크 -1 행렬 의 합으로 쓰여진 것을 보여줍니다 . 순위 -1 매트릭스는 어떻게 생겼습니까? 보자 :
행이 비례하고, 열이 비례한다. $X$

X

$X$ $p$

p

$p$

(\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}) (\begin{matrix} 4 & 5 & 6 \end{matrix}) = (\begin{matrix} 4 & 5 & 6 \\ 8 & 10 & 12 \\ 12 & 15 & 18 \end{matrix})

$\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} \begin{pmatrix} 4 & 5 & 6 \end{pmatrix} = \begin{pmatrix} 4 & 5 & 6 \\ 8 & 10 & 12 \\ 12 & 15 & 18 \end{pmatrix}$

이제 를 흑백 이미지의 그레이 스케일 값을 포함하는 것으로 생각하십시오 . 매트릭스의 각 항목은 하나의 픽셀을 나타냅니다. 예를 들어 비비의 다음 그림 : $X$

X

$X$

그런 다음이 이미지를 R로 읽고 라이브러리를 사용하여 결과 구조의 행렬 부분을 가져옵니다 pixmap.

결과를 재현하는 방법에 대한 단계별 가이드가 필요한 경우 여기 에서 코드를 찾을 수 있습니다 .

SVD를 계산하십시오.

baboon.svd  <-  svd(bab) # May take some time

$512 \times 512$

512 \times 512

$512 \times 512$ $512$

512

$512$ $512$

512

$512$ $1$

1

$1$ $20$

20

$20$

baboon.1  <-  sweep(baboon.svd$u[,1,drop=FALSE],2,baboon.svd$d[1],"*") %*%
                   t(baboon.svd$v[,1,drop=FALSE])

baboon.20 <-  sweep(baboon.svd$u[,1:20,drop=FALSE],2,baboon.svd$d[1:20],"*") %*%
                   t(baboon.svd$v[,1:20,drop=FALSE])

다음 두 이미지가 생성됩니다.

왼쪽에서 순위 1 이미지의 세로 / 가로 줄무늬를 쉽게 볼 수 있습니다.

$20$

20

$20$

매우 흥미로운 점은 원본 이미지의 일부를 세로 / 가로 선, 주로 대각선 코털과 질감, 눈의 중첩으로 표현하기 어려운 부분입니다!

답변

$A$

A

$A$ $m \times n$

m \times n

$m \times n$ $m \geq n$

m \geq n

$m \geq n$ $v$

v

$v$ $A$

A

$A$

\begin{aligned} (1) & v_{1} = & \arg max_{v \in R^{n}} ‖ A v ‖_{2} \\ subject to ‖ v ‖_{2} = 1. \end{aligned}

$\begin{align} \tag{1}v_1 = \,\,& \arg \max_{v \in \mathbb R^n} \quad \| A v \|_2 \\ & \text{subject to } \, \|v\|_2 = 1. \end{align}$ $v_{1}$

v_{1}

$v_1$ $A$

A

$A$

\begin{aligned} v_{2} = & \arg max_{v \in R^{n}} ‖ A v ‖_{2} \\ subject to ⟨ v_{1}, v ⟩ = 0, \\ ‖ v ‖_{2} = 1. \end{aligned}

$\begin{align} v_2 = \,\,& \arg \max_{v \in \mathbb R^n} \quad \| A v \|_2 \\ & \text{subject to } \,\langle v_1, v \rangle = 0, \\ & \qquad \qquad \, \, \, \, \|v\|_2 = 1. \end{align}$ $v_{1}, \dots, v_{n}$

v_{1}, \dots, v_{n}

$v_1, \ldots, v_n$ $R^{n}$

R^{n}

$\mathbb R^n$ $R^{n}$

R^{n}

$\mathbb R^n$ $A$

A

$A$

합시다 (따라서 는 방향으로 의 폭발력을 정량화합니다 ). 단위 벡터 가 되도록 정의
되었다고 가정하자
식 (2)로 행렬 표기를 사용하여 간결하게 표현 될 수있다
은 IS 매트릭스 열째가 , 은 IS 그 행렬 열은 이며 $σ_{i} = ‖ A v_{i} ‖_{2}$

σ_{i} = ‖ A v_{i} ‖_{2}

$\sigma_i = \|A v_i \|_2$ $σ_{i}$

σ_{i}

$\sigma_i$ $A$

A

$A$ $v_{i}$

v_{i}

$v_i$ $u_{i}$

u_{i}

$u_i$

\begin{matrix} (2) & A v_{i} = σ_{i} u_{i} for i = 1, \dots, n . \end{matrix}

$\tag{2} A v_i = \sigma_i u_i \quad \text{for } i = 1, \ldots, n.$

\begin{matrix} (3) & A V = U Σ, \end{matrix}

$\tag{3} A V = U \Sigma,$ $V$

V

$V$ $n \times n$

n \times n

$n \times n$ $i$

i

$i$ $v_{i}$

v_{i}

$v_i$ $U$

U

$U$ $m \times n$

m \times n

$m \times n$ $i$

i

$i$ $u_{i}$

u_{i}

$u_i$ $Σ$

Σ

$\Sigma$ 는 IS 가진 대각 행렬 토륨 대각선 엔트리이다 . 행렬 는 직교하므로 (3)의 양변에 를 곱하여 를 얻을 수

우리는 이제 거의 제로 노력 으로 의 SVD를 도출 한 것으로 보일 수 있습니다 . 지금까지 어떤 단계도 어려웠습니다. 그러나 그림의 중요한 부분이 빠져 있습니다. 우리는 가 직교 하다는 것을 아직 알지 못합니다 . $n \times n$

n \times n

$n \times n$ $i$

i

$i$ $σ_{i}$

σ_{i}

$\sigma_i$ $V$

V

$V$ $V^{T}$

V^{T}

$V^T$

A = U Σ V^{T} .

$A = U \Sigma V^T.$ $A$

A

$A$ $U$

U

$U$

중요한 사실은 누락 된 부분입니다 이 직교 함 :
이것이 사실이 아니라면
이라고 주장합니다 문제에 최적이 아닙니다 (1). 실제로, (4)가 만족되지 않으면, 방향으로 약간 섭동 함으로써 을 개선 하는 것이 것이다. $A v_{1}$

A v_{1}

$A v_1$ $A v_{2}$

A v_{2}

$A v_2$

\begin{matrix} (4) & ⟨ A v_{1}, A v_{2} ⟩ = 0. \end{matrix}

$\tag{4} \langle A v_1, A v_2 \rangle = 0.$ $v_{1}$

$v_{1}$

$v_1$ $v_{1}$

v_{1}

$v_1$ $v_{2}$

v_{2}

$v_2$

(모순을 위해) (4)가 만족되지 않는다고 가정하십시오. 경우 직교 방향으로 약간 교란된다 의 규범 변경되지 않는다 (또는 최소한의 표준의 변경 무시할). 지구 표면을 걷더라도 지구 중심으로부터의 거리는 변하지 않습니다. 그러나 방향으로 교란되어 상기 벡터 에서 교란되는 비 직교 방향 등의 표준의 변경 있다 무시할 . 의 규범 $v_{1}$

v_{1}

$v_1$ $v_{2}$

v_{2}

$v_2$ $v_{1}$

v_{1}

$v_1$ $v_{1}$

v_{1}

$v_1$ $v_{1}$

v_{1}

$v_1$ $v_{2}$

v_{2}

$v_2$ $A v_{1}$

A v_{1}

$A v_1$ $A v_{2}$

A v_{2}

$A v_2$ $A v_{1}$

A v_{1}

$A v_1$ $A v_{1}$

A v_{1}

$A v_1$ 무시할 수없는 양으로 증가 될 수 있습니다. 이는 이 문제 (1)에 적합하지 않다는 것을 의미하며 이는 모순입니다. 나는이 주장을 좋아한다 : 1) 직관이 매우 분명하다. 2) 직관은 엄격한 증거로 직접 변환 될 수 있습니다. $v_{1}$

v_{1}

$v_1$

비슷한 주장은 이 과 직교 함을 나타냅니다 . 벡터 은 쌍으로 직교합니다. 이것은 단위 벡터 이 쌍으로 직교하도록 선택 될 수 있음을 의미하며, 이는 상기 행렬 가 직교 행렬 임을 의미한다 . 이것으로 SVD 발견이 완료됩니다. $A v_{3}$

A v_{3}

$A v_3$ $A v_{1}$

A v_{1}

$A v_1$ $A v_{2}$

A v_{2}

$A v_2$ $A v_{1}, \dots, A v_{n}$

A v_{1}, \dots, A v_{n}

$A v_1, \ldots, A v_n$ $u_{1}, \dots, u_{n}$

u_{1}, \dots, u_{n}

$u_1, \ldots, u_n$ $U$

U

$U$

위의 직관적 인 주장을 엄격한 증거로 변환하려면 이 방향으로 교란되면 교란 벡터

가 실제로 단위 벡터가 아니라는 사실에 직면해야합니다 . (표준은 입니다.) 엄격한 증거를 얻으려면

벡터 진정 단위 벡터이다. 당신은 쉽게 표시 할 수 있습니다 (4)은 충분히 작은 값 다음, 만족하지 않는 경우에, 우리는 한

( 의 표시가 있다고 가정) $v_{1}$

v_{1}

$v_1$ $v_{2}$

v_{2}

$v_2$

{\tilde{v}}_{1} = v_{1} + ϵ v_{2}

$\tilde v_1 = v_1 + \epsilon v_2$ $\sqrt{1 + ϵ^{2}}$

\sqrt{1 + ϵ^{2}}

$\sqrt{1 + \epsilon^2}$

{\bar{v}}_{1} (ϵ) = \sqrt{1 - ϵ^{2}} v_{1} + ϵ v_{2} .

$\bar v_1(\epsilon) = \sqrt{1 - \epsilon^2} v_1 + \epsilon v_2.$ ${\bar{v}}_{1} (ϵ)$

{\bar{v}}_{1} (ϵ)

$\bar v_1(\epsilon)$ $ϵ$

ϵ

$\epsilon$

f (ϵ) = ‖ A {\bar{v}}_{1} (ϵ) ‖_{2}^{2} > ‖ A v_{1} ‖_{2}^{2}

$f(\epsilon) = \| A \bar v_1(\epsilon) \|_2^2 > \| A v_1 \|_2^2$ $ϵ$

ϵ

$\epsilon$ 올바른 선택). 이것을 표시하려면 . 이는 이 문제 (1)에 적합하지 않다는 것을 의미하며 이는 모순입니다. $f^{'} (0) \neq 0$

f^{'} (0) \neq 0

$f'(0) \neq 0$ $v_{1}$

v_{1}

$v_1$

(그런데, 여기 SVD에 대한 Qiaochu Yuan의 설명을 읽는 것이 좋습니다 . 특히, 위에서 논의한 “Key lemma # 1″을 살펴보십시오. Qiaochu가 말했듯이 키 lemma # 1은 “기술의 핵심입니다” 특이 값 분해 “).

답변

친구 하루의 시간을 가지고이 강의를보십시오 :
https://www.youtube.com/watch?v=EokL7E6o1AE

이 녀석은 매우 직설적입니다. 결국에는 모두 모이기 때문에 건너 뛰지 않는 것이 중요합니다. 처음에는 조금 느리게 보일지라도, 그는 중요한 포인트를 고정하려고 노력하고 있습니다.

다른 설명을 읽을 때 혼란 스러웠 기 때문에 모든 사람이하는 세 가지 행렬을 제공하는 것이 아니라 요약 해 드리겠습니다. 그 행렬은 어디에서 왔으며 왜 그렇게 설정합니까? 강의는 그것을 못 박는 다! 모든 행렬 (영원성 기록)은 동일한 차원의 기본 행렬로 구성한 다음 회전하고 늘릴 수 있습니다 (선형 대수의 기본 정리). 사람들이 던지는 세 가지 행렬 각각은 초기 행렬 (U), 스케일링 행렬 (시그마) 및 회전 행렬 (V)을 나타냅니다.

스케일링 매트릭스는 어떤 회전 벡터가 지배적인지를 보여 주며, 이것을 단일 값이라고합니다. 분해는 U, 시그마 및 V에 대해 해결됩니다.

How IT

언제든지 물어보세요.

SVD의 직관은 무엇입니까? (SVD)에 대해 읽었습니다. 거의 모든

답변

답변

답변

답변