Truncated SVD

• $\bold{A}$의 특잇값 분해(SVD)를 $\bold{A} = \bold{USV}^\top$라 놓고, $\hat{\bold{A}}_K = \bold{U}_K \bold{S}_K \bold{V}_K^\top$라 하자. 여기서 $\bold{U}$와 $\bold{V}$의 첫 $k$개 컬럼을 사용한다. 이것은 $\|\bold{A} - \hat{\bold{A}}_K\|_F^2$을 최소화한다는 점에서 최적의 rank $k$ 근사로 표시될 수 있다.
• 만일 $K = r = \text{rank}(\bold{A})$라면 이 분해로 인해 발생하는 오류가 없다. 그러나 $K < r$이면 약간의 에러가 발생하는데 이것을 Truncated SVD라고 부른다.
• 만일 특잇값들이 자연 데이터에서 빠르게 죽으면 에러는 작아진다.
  • rank $K$ 근사를 사용하여 $N \times D$ 행렬을 표현하는데 필요한 총 파라미터의 숫자는 다음과 같다.

$$ NK +KD + K = K(N+D+1) $$

• 이 rank-$K$ 근사에서 오류는 다음과 같이 주어진다.
  • 여기서 $\sigma_k$는 $\bold{A}$의 $k$번째 특이값이다.

$$ \|\bold{A} - \hat{\bold{A}}\|F = \sum{k = K+1}^r \sigma_k $$

LU factorization

• 어떤 정사각 행렬 $\bold{A}$을 하삼각행렬 $\bold{L}$과 상삼각행렬 $\bold{U}$의 곱으로 분해할 수 있다. 예를 들어 다음과 같다.

$$ \left[\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix}\right] = \left[\begin{matrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{matrix}\right] \left[\begin{matrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{matrix}\right]
$$

• $\bold{L}$과 $\bold{U}$는 가우스-조던 소거법을 하는 과정에서 구할 수 있다.
  • $\bold{U}$를 구하기 위해 수행하는 소거를 lower triangle 행렬로 표현할 수 있는데, $\bold{U}$를 얻는 동안 반복적으로 곱해진 모든 lower trinagle matrix를 곱하면 또 lower triangle 행렬이 되기 때문에 이것을 $\bold{L}$로 합치면 최종적으로 $\bold{A} = \bold{LU}$로 만들수 있는데 이게 바로 LU decomposition이 된다.
• 일반적으로 이 분해를 생성하기 전에 행렬의 요소들을 순열해야 할 필요가 있다. 이것을 위해 $a_{11} = 0$일 가정한다.
  • $a_{11} = l_{11} u_{11}$ 이기 때문에 $l_{11}$나 $u_{11}$ 둘 중 하나는 0이어야 한다는 것을 의미하지만 이는 $\bold{L}$이나 $\bold{U}$이 특이라는 것을 암시한다.
  • 이것을 피하기 위해 이 알고리즘의 첫 번째 단계는 행을 첫 번째 요소가 0이 아니도록 간단하게 재정렬할 수 있다. 이것을 차후 단계에서도 반복한다. 이 절차를 다음처럼 나타낼 수 있다.
  • 1행의 맨 앞이 0이면 맨 앞이 0이 아닌 다른 행이랑 바꾸면 되는데, 이 교체 연산을 아예 행렬로 만들어서 $\bold{A}$와 곱하게 한다. 그 행렬을 permutation matrix라고 한다.

$$ \bold{PA} = \bold{LU} $$

• 여기서 $\bold{P}$는 순열 행렬(permutation matrix)이다. 예컨대 만일 행 $i$가 행 $j$로 순열되면 $\bold{P}_{ij} = 1$인 정사각 이진 행렬이다. 이것을 partial pivoting이라고 한다.
  • $\bold{P}$는 orthogonal 하기 때문에 $\bold{P}^{-1} = \bold{P}^\top$가 성립한다.
• $\bold{P}$를 이용해서 $\bold{LU}$ decomposition 하는것을 $\bold{PLU}$ decomposition이라고 한다.
• $\bold{LU}$ decomposition의 결과에 대해 $\bold{L}$과 $\bold{U}$의 대각 요소가 1이 아닌 경우 그것을 1로 만들어주는 행렬 $\bold{D}$를 만들어 줄 수 있는데, 이것을 $\bold{LDU}$ decomposition이라고 한다.
  • 여기서 $\bold{D}$는 대각 요소만 존재하는 대각 행렬이고, 놀랍게도 $\bold{L}$과 $\bold{U}$의 대각 성분을 동시에 1로 만들어준다.

Gram-Schmidt Orthogonalization

• 선형 독립이지만 orthogonal 하지 않은 벡터가 존재할 때, 그것들 orthogonal 하게 만드는 절차를 Gram-Schmit Orthogonalization 라고 한다.
• 아이디어는 벡터 하나를 normalize 한 후에 나머지 벡터들을 차례로 이전 모든 벡터와 직교하게 만드는 것으로 절차는 다음과 같다.
  1. 먼저 벡터 하나를 normalize 해서 orthonormal한 벡터를 만들고,
     • $\bold{q}{1} = {\bold{w}{1} \over \|\bold{w}_{1}\|}$
  2. normalize된 벡터를 이용해서 다음 벡터에서 처음 벡터와 평행한 성분을 제거해서 처음 벡터와 수직인 벡터를 만들고
     • $\bold{v}{2} = \bold{w}{2} - \langle \bold{w}{2}, \bold{q}{1} \rangle \bold{q}_{1}$
       • $\langle \bold{w}{2}, \bold{q}{1} \rangle$ 을 내적하면 $\bold{w}{2}$를 $\bold{q}{1}$에 투영하는 벡터의 크기(스칼라)가 나온다.
       • 그렇게 구한 크기에 다시 $\bold{q}{1}$을 곱하면 $\bold{q}{1}$에 대해 방금 구한 크기만큼 scale한 벡터가 만들어지고, 이게 바로 $\bold{w}{2}$를 $\bold{q}{1}$에 투영한 벡터가 된다.
       • $\bold{w}{2}$를 $\bold{q}{1}$에 투영한 벡터를 다시 $\bold{w}{2}$에서 빼주면 결국 $\bold{w}{2}$에서 $\bold{q}_{1}$와 수직인 성분만 남는다. 이것을 화살표로 그려보면 이해가 쉽다.
  3. 2에서 만든 벡터를 normalize해서 다음 orthonormal 벡터를 만들고
     • $\bold{q}{2} = {\bold{v}{2} \over \|\bold{v}_{2}\|}$
  4. 그 다음 벡터를 선택해서 이전의 모든 orthogonal 벡터에 대해 투영하고 원래 벡터에서 빼는 2-3의 과정을 반복한다. 모든 벡터가 orthonormal 벡터가 될 때까지.