Matrix Approximation
4.5장을 통해 행렬 $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 를 3개의 행렬($\boldsymbol{U\Sigma V}^\top$) 곱으로 분해하는 SVD에 대해 알아봤습니다. 이때, 행렬 $\boldsymbol{U}\in\mathbb{R}^{m\times m}$ 과 $\boldsymbol{V}\in\mathbb{R}^{n\times n}$ 는 orthogonal이며, $\boldsymbol{\Sigma}$ 는 주대각 성분이 singular value인 행렬입니다.
이번 장에서는 Full SVD factorization을 수행하는 대신, 행렬 $\boldsymbol{A}$ 를 더 간단한(low-rank) 행렬 $\boldsymbol{A}_i$ 들의 합으로 SVD를 나타내는 것에 대해 살펴봅니다. 이는 matrix approximation으로 full SVD 보다 연산량이 적습니다.
Rank-1 행렬 $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 은 다음과 같이 구성합니다.
\[\boldsymbol{A}_i := \boldsymbol{u}_i\boldsymbol{v}_i^\top \tag{4.90}\]이는 $\boldsymbol{U}$ 와 $\boldsymbol{V}$ 의 i번째 orthogonal column vector의 외적(outer product) 입니다.
위 그림은 스톤헨지 사진을 행렬 $\boldsymbol{A}\in\mathbb{R}^{1432\times1910}$ 로 나타낸 것이며 식 (4.90)에 의해 정의되는 몇 가지 외적 $\boldsymbol{A}_i$ 을 보여줍니다.
Rank $r$ 의 행렬 $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 은 rank-1 행렬 $\boldsymbol{A}_i$ 의 합으로 다음과 같이 나타낼 수 있습니다.
\[\boldsymbol{A} = \sum_{i=1}^r \sigma_i\boldsymbol{u}_i\boldsymbol{v}_i^\top = \sum_{i=1}^r\sigma_i\boldsymbol{A}_i \tag{4.91}\]위 식은 $\boldsymbol{A}_i$ 와 singular value $\sigma_i$ 의 가중합으로 표현됩니다. Singular value matrix $\boldsymbol{\Sigma}$ 의 대각 구조는 오직 일치하는 left/right-singular vectors $\boldsymbol{u}_i\boldsymbol{v}_i^\top$ 과 곱해지고 대응되는 singular value $\sigma_i$ 로 scaling 되기 때문에 성립합니다. $\boldsymbol{\Sigma}$ 는 대각행렬이기 때문에 $i \neq j$ 인 모든 $\sum_{ij}\boldsymbol{u}_i\boldsymbol{v}_j^\top$ 항은 사라집니다. 또한, $i > r$ 인 모든 항은 대응되는 singular value가 0이기 때문에 사라지게 됩니다.
식 (4.90)에서 rank-1 행렬 $\boldsymbol{A}_i$ 를 도입했고, 이들 더해서 rank-r 행렬 $\boldsymbol{A}$ 를 얻었습니다. 만약 모든 행렬 $\boldsymbol{A}_i, i = 1, \dotsc, r$ 이 더해지지 않고 중간값 $k < r$ 까지 더해진다면, $\boldsymbol{A}$ 의 rank-r approximation 을 얻게 됩니다.
\[\hat{\boldsymbol{A}}(k) := \sum_{i=1}^k\sigma_i\boldsymbol{u}_i\boldsymbol{v}_i^\top = \sum_{i=1}^k\sigma_i\boldsymbol{A}_i \tag{4.92}\]이때, $\text{rk}(\hat{\boldsymbol{A}}(k)) = k$ 입니다. 아래 그림은 원본 이미지 $\boldsymbol{A}$ 의 low-rank approximations $\hat{\boldsymbol{A}}(k)$ 를 보여줍니다.
위 그림을 잘 살펴보면 rank-5 approximation로 갈수록 바위의 모양이 더 명확해진다는 것을 알 수 있습니다. 원본 이미지에서는 $1,432\times1,910=2,735,120$ 개의 값이 필요하지만, rank-5 approximation에서는 오직 5개의 singular values와 5개의 left/right-singular vectors만 저장하면 됩니다. 따라서, rank-5 approximation에서는 $5\cdot(1,432 + 1,910 + 1) = 16,715$ 개의 숫자만 저장하면 되고 이는 원본의 0.6% 정도 입니다.
$\boldsymbol{A}$ 와 $\boldsymbol{A}$ 의 rank-$k$ approximation $\hat{\boldsymbol{A}}(k)$ 의 차이(error)를 측정하려면 norm의 개념이 필요합니다 (3.1장 참조). 3.1장에서는 vector에 대한 norm을 사용하여 vector의 length를 측정했습니다. 이를 통해서 행렬에 대한 norm을 정의할 수 있습니다.
Definition 4.23 (Spectral Norm of a Matrix).
모든 $\boldsymbol{x}\in\mathbb{R}^n\backslash\lbrace\boldsymbol{0}\rbrace$ 에 대해, 행렬 $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 의 spectral norm 은 다음과 같이 정의됩니다.
\[\|\boldsymbol{A}\|_2 := \max_x \frac{\|\boldsymbol{Ax}\|_2}{\|x\|_2} \tag{4.93}\]
우항에 있는 벡터에 대한 Euclidean norm에서 아래 첨자가 2인 것과 유사하게, 좌항의 행렬의 norm에도 아래첨자를 적어줍니다. 식 (4.93)의 spectral norm은 vector $\boldsymbol{x}$ 에 행렬 $\boldsymbol{A}$ 를 곱했을 때의 최대 길이를 결정합니다.
Theorem 4.24. $\boldsymbol{A}$ 의 spectral norm 은 $\boldsymbol{A}$ 의 가장 큰 singular value $\sigma_1$ 입니다.
Theorem 4.24는 아래에서 Example을 통해 증명하도록 하겠습니다.
Theorem 4.25 (Eckart-Young Theorem). Rank-r인 행렬 $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 과 rank-k인 행렬 $\boldsymbol{B}\in\mathbb{R}^{m\times n}$ 이 있고 $k \leq r$ 일 때, 다음의 식이 성립합니다.
\[\begin{align*} \hat{\boldsymbol{A}}(k) &= \arg\min{}_{\text{rk}(B)=k} \|\boldsymbol{A} -\boldsymbol{B}\|_2 \tag{4.94} \\ \|\boldsymbol{A}-\hat{\boldsymbol{A}}(k)\|_2 &= \sigma_{k+1} \tag{4.95} \end{align*}\]
Eckart-Young theorem은 rank-k approximation을 사용하여 $\boldsymbol{A}$ 를 근사했을 때, error가 얼만큼 발생하는지 나타냅니다. SVD를 통해 얻은 rank-k approximation은 full-rank matrix $\boldsymbol{A}$ 로부터 더 낮은 차원인 최대 rank-k 행렬로의 projection으로 해석할 수 있습니다. 모든 가능한 projections 에서 SVD는 $\boldsymbol{A}$ 와 rank-k approximation 간의 error(by spectral norm)를 최소화합니다.
식 (4.95)가 왜 성립하는지 이해하기 위해 몇 가지 단계를 되돌아가보도록 하겠습니다. $\boldsymbol{A} - \hat{\boldsymbol{A}}(k)$ 간의 차이는 rank-k approximation에 사용되고 남은 나머지 rank-1 행렬들의 합이라는 것을 확인할 수 있습니다.
\[\boldsymbol{A}-\hat{\boldsymbol{A}}(k) = \sum_{i=k+1}^r\sigma_i\boldsymbol{u}_i\boldsymbol{v}_i^\top \tag{4.96}\]Theorem 4.24에 의해, 이 difference matrix의 spectral norm이 $\sigma_{k+1}$ 라는 것을 알 수 있습니다. 이제 식 (4.94)를 조금 더 자세히 살펴보겠습니다. 만약 또 다른 행렬 $\boldsymbol{B}$ ($\text{rk}(\boldsymbol{B}) \leq k$) 가 다음을 만족한다면,
\[\|\boldsymbol{A}-\boldsymbol{B}\|_2 < \|\boldsymbol{A}-\hat{\boldsymbol{A}}(k)\|_2 \tag{4.97}\]적어도 (n-k)-차원인 null space $Z\subseteq\mathbb{R}^n$ 이 존재합니다. 만약 $\boldsymbol{x} \in Z$ 라면 $\boldsymbol{Bx} = 0\boldsymbol{0}$ 을 만족하며, 이는 다음 식을 만족시킵니다.
\[\|\boldsymbol{Ax}\|_2 = \|(\boldsymbol{A}-\boldsymbol{B})\boldsymbol{x}\|_2 \tag{4.98}\]그리고 행렬의 norm에 Cauchy-Schwartz inequality (3.17)를 적용하여 다음의 식을 얻습니다.
\[\|\boldsymbol{Ax}\|_2 \leq \|\boldsymbol{A}-\boldsymbol{B}\|_2\|\boldsymbol{x}\|_2 < \sigma_{k+1}\|\boldsymbol{x}\|_2 \tag{4.99}\]그러나 $\|\boldsymbol{Ax}\|_2 \geq \sigma_{k+1}\|\boldsymbol{x}\|_2$ 인 (k+1)-차원의 subspace가 존재하며, 이 subspace는 $\boldsymbol{A}$ 의 right-sigular vectors $\boldsymbol{v}_j, j \leq k+1$ 에 의해 span 됩니다. 두 spaces에 nonzero vector가 존재해야 하기 때문에 두 spaces의 차원을 더하면 $n$보다 큰 값이 나옵니다. 이는 2.7.3장의 rank-nullity theorem (Theorem 2.24)와 모순됩니다. (완벽히 이해는 되지 않는 부분입니다 ㅠ.ㅠ)
Eckart-Young theorem은 SVD를 사용하여 principled,optimal한 방식으로 rank-$r$ 인 행렬 $\boldsymbol{A}$ 를 rank-$k$ 행렬 $\hat{\boldsymbol{A}}$ 로 줄일 수 있다는 것을 의미합니다. 이는 rank-$k$ 행렬로의 approximation을 lossy compression의 한 형태로 해석할 수 있습니다. 따라서, 행렬의 low-rank approximation은 image processing, noise filtering, regularization of ill-posed problems 와 같은 머신러닝 applications에서 사용됩니다. 또한, 10장에서 살펴볼 dimensionality reduction이나 PCA에서 핵심적인 역할을 수행합니다.
Example 4.15 (Finding Structure in Movie Ratings and Comsumers)
\[\begin{align*} \boldsymbol{A}_1 &= \boldsymbol{u}_1\boldsymbol{v}_1^\top = \begin{bmatrix}-0.6710\\-0.7197\\-0.0939\\-0.1515\end{bmatrix}\begin{bmatrix}-0.7367&-0.6515&-0.1811\end{bmatrix} \tag{4.100a} \\ &= \begin{bmatrix}0.4943&0.4372&0.1215\\0.5302&0.4689&0.1303\\0.0692&0.0612&0.0170\\0.1116&0.0987&0.0274\end{bmatrix} \tag{4.100b} \end{align*}\]
4.5장에서 살펴본 Example 4.14에서 살펴본 original data matrix를 low-rank approximation을 사용하여 근사해보도록 하겠습니다. Example 4.14에서 첫 번째 singular value는 science fiction theme와 science fiction을 선호하는 사람들에 대한 notion을 포착했습니다. 따라서 movie-rating matrix의 rank-1 decomposition에 오직 첫 번째 singular value term만을 사용하여, 다음과 같이 predicated ratings를 얻을 수 있습니다.이렇게 구한 rank-1 approximation $\boldsymbol{A}_1$ 은 Ali(첫 번째 열)와 Beatrix(두 번째 열)가 Star Wars(첫 번째 행)나 Bladerunner(두 번째 행) 와 같은 science fiction 영화를 좋아한다는 것을 말해줍니다 (각 요소의 값이 0.4 이상). 그러나, Chandra(세 번재 열)의 ratings를 예측하는 것은 실패했습니다.
이는 자연스러운 결과인데, 첫 번째 singular value에서 Chandra가 좋아하는 타입의 영화는 포착되지 않았기 때문입니다. 두 번째 singular value에 대해 rank-1 approximation을 적용하면 chandra가 좋아하는 영화 타입을 좋아하는 사람들에 대해 예측 ratings를 구할 수 있습니다.
\[\begin{align*} \boldsymbol{A}_2 &= \boldsymbol{u}_2\boldsymbol{v}_2^\top = \begin{bmatrix}0.0236\\0.2054\\-0.7705\\-0.6030\end{bmatrix}\begin{bmatrix}0.0852&0.1762&-0.9807\end{bmatrix} \tag{4.101a} \\ &= \begin{bmatrix}0.0020&0.0042&-0.0231\\0.0175&0.0362&-0.2014\\-0.0656&-0.1358&0.7556\\-0.0514&-0.1063&0.5914\end{bmatrix} \tag{4.101b} \end{align*}\]두 번째 rank-1 approximation $\boldsymbol{A}_2$ 에서는 Chandra가 선호는 영화에 대한 rating을 담고 있다는 것을 알 수 있습니다. 위에서 구한 두 rank-1 approximation을 통해 rank-2 approximation $\hat{\boldsymbol{A}}(2)$ 를 도출해낼 수 있는데, 두 rank-1 approximation을 다음과 같이 결합하면 됩니다.
\[\hat{\boldsymbol{A}}(2) = \sigma_1\boldsymbol{A}_1 + \sigma_2\boldsymbol{A}_2 = \begin{bmatrix}4.7801&4.2419&1.0244\\5.2252&4.7522&-0.0250\\0.2493&-0.2743&4.9724\\0.7495&0.2756&4.0278\end{bmatrix} \tag{4.102}\]$\hat{\boldsymbol{A}}(2)$ 는 original ratings 테이블과 유사합니다.
\[\boldsymbol{A} = \begin{bmatrix}5&4&1\\5&5&0\\0&0&5\\1&0&4\end{bmatrix} \tag{4.103}\]이러한 결과는 $\boldsymbol{A}_3$ 을 무시할 수 있다는 것을 의미하며, 데이터 테이블에는 세 번째 movie theme나 세 번째 movie lover 카테고리가 없다는 것으로 해석할 수 있습니다. 또한, 이 예제에서 movie theme/movie-lover 의 전체 space는 science fiction/French art house movie/lover로 span되는 2차원 space라는 것을 의미합니다.