[PML intro] Ch7 Linear Algebra (Sec.7.1 Introduction - 3)

지난 포스팅의 [PML intro] Ch7 Linear Algebra (Sec.7.1 Introduction - 2)에서는 벡터공간(Vector Space)에 대한 설명을 하였습니다. 이를 통해, 선형독립, 생성공간, 기저, 선형사상과 행렬 사이의 관계, 치역과 영공간, 선형 사영에 대한 필수적인 개념들을 정말 간단하게 알아보았습니다. 오늘은 벡터와 행렬의 크기를 측정하는 방법인 노름(Norm)에 대해서 알아보도록 하겠습니다. 

 

1. 벡터 노름(Vector Norm)

벡터 노름 $||\mathbf{x}||$는 벡터의 길이를 재는 척도라고 볼 수 있습니다. 더 엄밀하게 이야기하면 노름이란 다음 4가지 성질을 만족하는 함수 $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$를 말합니다. 

 

- 비음성(non-negativity): 모든 $\mathbf{x} \in \mathbb{R}^{n}$에 대해 $f(\mathbb{x}) \ge 0$이다.

- 양의 정부호성 (definiteness): $f(\mathbf{f}) = 0$이면 그리고 그럴 때에 한해 $\mathbf{x} = 0$이다.

- 절댓값 동차성 (absolute value homogeneity): 모든 $\mathbf{x} \in \mathbb{R}^{n}$과 $t \mathbb{R}$에 대해서 $f(t\mathbf{x}) = |t|f(\mathbf{x})$이다. 

- 삼각부등식 (triangle inequality): 모든 $\mathbf{x}, \mathbf{y} \in \mathbb{R}^{n}$에 대해 $f(\mathbf{x} + \mathbf{y}) \le f(\mathbf{x}) + f(\mathbf{y})$이다. 

 

자주 사용되는 노름들로 다음들이 있습니다. 

 

- $p$-노름: $p \ge 1$에 대해서 $||\mathbf{x}||_{p} = (\sum_{i = 1}^{n} |x_{i}|^{p})^{\frac{1}{p}}$

- 2-노름 (유클리드 노름; Euclidean Norm): $||\mathbf{x}||_{2} = (\sum_{i = 1}^{n} |x_{i}|^{2})^{\frac{1}{2}} = \sqrt{\sum_{i = 1}^{n} x^{2}_{i}}$

- 1-노름: $||\mathbf{x}||_{1} = (\sum_{i = 1}^{n} |x_{i}|^{1})^{\frac{1}{1}} = \sum_{i = 1}^{n} |x_{i}|$

- $\infty$-노름 (Max Norm): $||\mathbf{x}||_{\infty} = \text{max}_{i} |x_{i}|$

- 0-노름 (유사 노름; Pseudo Norm): $||\mathbf{x}||_{0} = \sum_{i = 1}^{n} \mathbb{I} (|x_{i}| > 0)$

 

다만 마지막에 소개한 0-노름 또는 유사노름은 동차성을 만족하지 않기 때문에 엄밀한 의미에서의 노름이라고 볼 수는 없으므로 유사 노름(Pseudo Norm)이라고 부릅니다. 이 값은 결국 $\mathbf{x}$안의 0이 아닌 원소의 개수를 세는 것과 동일합니다. 이때, 확장된 실수 공간 (Extended Real Number Space) 상에서 $0^{0} = 0$이라고 정의한다면 $||\mathbf{x}||_{0} = (\sum_{i = 1}^{n} x_{i}^{0}$이라고도 쓸 수 있습니다. 

 

2. 행렬 노름(Matrix Norm)

행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$을 선형함수 $f(\mathbf{x}) = \mathbf{A}\mathbf{x}$로 생각해보도록 하겠습니다. 이때, $\mathbf{A}$의 induced norm을 "단위 노름 입력을 $f$가 최대로 얼마나 늘릴 수 있는가"로 정의할 수 있습니다. 즉, 다음과 같이 쓸 수 있죠. 

 

$$||\mathbf{A}||_{p} = \text{max}_{\mathbf{x} \neq 0} \frac{||\mathbf{A}\mathbf{x}||_{p}}{||\mathbf{x}||_{p}} = \text{max}_{||\mathbf{x}||_{p} = 1} ||\mathbf{A}\mathbf{x}||_{p}$$

 

일반적으로 $p = 2$인 경우를 많이 사용하며 다음과 같이 유도됩니다. 

 

$$||\mathbf{A}||_{2} = \sqrt{\lambda_{\text{max}} (\mathbf{A}^{T}\mathbf{A})} = \text{max}_{i} \sigma_{i}$$

 

여기서 $\lambda_{\text{max}} (\mathbf{M})$은 행렬 $\mathbf{M}$의 최대 고윳값을 의미하며 $\sigma_{i}$는 행렬 $\mathbf{A}$의 $i$번째 특이값 (singular value)를 의미합니다. 

 

핵 노름(nuclear norm) 또는 트레이스 노름(trace norm)은 다음과 같이 정의됩니다. 

 

$$||\mathbf{A}||_{*} = \sqrt{\text{tr} (\mathbf{A}^{T}\mathbf{A})} = \sum_{i} \sigma_{i} = ||\mathbf{\sigma}||_{1}$$

 

이 값을 정규화로 사용하면 많은 특이값들이 0이 되도록 유도하여 저랭크(low-rank) 행렬을 만드는 경향이 있습니다. 

 

다음으로 Schatten $p$-노름은 더 일반적인 행렬 노름의 정의로 다음과 같이 정의됩니다. 

 

$$||\mathbf{A}||_{p} = \left( \sum_{i} \sigma_{i} (\mathbf{A})^{p} \right)^{\frac{1}{p}}$$

 

또는 행렬을 벡터로 취급하여 노름을 계산하는 Frobenius 노름도 있습니다. 이는 매우 간단하게 모든 원소들의 제곱의 합으로 구할 수 있습니다. 결국 벡터 노름의 2-노름과 동일하죠.

 

$$||\mathbf{A}||_{2} = \sqrt{\sum_{i = 1}^{m} \sum_{j = 1}^{n} a_{ij}^{2}}$$

 

하지만 엄청 큰 행렬을 다루는 경우 Frobenius 노름을 구하는 것은 연산량이 많이 소모됩니다. 따라서, 이를 근사하는 Hutchinson trace estimator를 활용할 수 있습니다. 이에 대한 자세한 내용은 향후에 더 자세히 알아보도록 하겠습니다.