Search
Duplicate

선형대수/ 대각합(Trace), 행렬 노름(matrix norm), 조건수(condition numbers)

대각합(Trace)

•
행렬의 대각합(trace)는 정사각행렬 A∈Mn×n(F)\bold{A} \in M_{n \times n}(F)에서만 정의 가능하다.
•
n×nn \times n 행렬 A\bold{A}의 대각합(trace)는 모든 대각성분의 합이고 tr(A)\text{tr}(\bold{A})로 표기한다.
tr(A)=∑i=1nAii\text{tr}(\bold{A}) = \sum_{i=1}^{n} A_{ii}
•
대각합은 다음의 속성을 갖는다. 여기서 A,B∈Rn×n\bold{A}, \bold{B} \in \mathbb{R}^{n \times n}는 정사각 행렬이고 c∈Rc \in \mathbb{R}는 스칼라이다.
◦
마지막의 λi\lambda_i는 행렬 A\bold{A}의 고유값을 의미한다. 행렬의 trace는 고윳값들의 합과 같다.
tr(A)=tr(A⊤)tr(A+B)=tr(A)+tr(B)tr(cA)=c⋅tr(A)tr(AB)=tr(BA)tr(A)=∑i=1nλi (where λi are the eigenvalues of A)\begin{aligned} \text{tr}(\bold{A}) &= \text{tr}(\bold{A}^\top) \\ \text{tr}(\bold{A} + \bold{B}) &= \text{tr}(\bold{A}) + \text{tr}(\bold{B}) \\ \text{tr}(c\bold{A}) &= c \cdot \text{tr}(\bold{A}) \\ \text{tr}(\bold{A}\bold{B}) &= \text{tr}(\bold{B}\bold{A}) \\ \text{tr}(\bold{A}) &= \sum_{i=1}^{n} \lambda_i \ (\text{where } \lambda_i \text{ are the eigenvalues of } \bold{A})\end{aligned}
•
정사각 행렬 A,B,C∈Rn×n\bold{A, B, C} \in \mathbb{R}^{n \times n}에 대해 다음이 성립하는데, 이것을 순환 순열 속성(cyclic permutation property)라 한다.
tr(ABC)=tr(BCA)=tr(CAB)\text{tr}(\bold{ABC}) = \text{tr}(\bold{BCA}) = \text{tr}(\bold{CAB})
•
이를 이용하여 스칼라 내적 x⊤Ax\bold{x}^\top\bold{A}\bold{x}을 작성해서 trace trick을 유도할 수 있다. —벡터는 열 혹은 행이 11인 행렬로 볼 수 있다.
x⊤Ax=tr(x⊤Ax)=tr(xx⊤A)\bold{x}^\top \bold{A} \bold{x} = \text{tr}(\bold{x}^\top \bold{A} \bold{x}) = \text{tr}(\bold{x}\bold{x}^\top \bold{A})
•
때로 행렬 A\bold{A}을 추정하는 것은 매우 비쌀 수 있다. 그러나 행렬-벡터 곱 Av\bold{A}\bold{v}를 추정하는 것은 저렴할 수 있다. 이 경우 v\bold{v}는 E[vv⊤]=I\mathbb{E}[\bold{v}\bold{v}^\top] = \bold{I}인 확률 벡터로 가정한다. 그러면 다음의 항등식(identity)을 사용하여 몬테 카를로 근사를 tr(A)\text{tr}(\bold{A})에 만들 수 있다. 이것을 Hutchinson trace estimator라고 부른다.
tr(A)=tr(AE[vv⊤])=E[tr(Avv⊤)]=E[tr(v⊤Av)]=E[v⊤Av]\text{tr}(\bold{A}) = \text{tr}(\bold{A} \mathbb{E}[\bold{v}\bold{v}^\top]) = \mathbb{E}[\text{tr}(\bold{A}\bold{v}\bold{v}^\top)] = \mathbb{E}[\text{tr}(\bold{v}^\top\bold{A}\bold{v})] = \mathbb{E}[\bold{v}^\top\bold{A}\bold{v}]

행렬 노름(matrix norm)

•
행렬의 노름은 여러 형태로 정의가 가능한데, 널리 쓰이는 것은 pp 제곱을 1/p1/p 제곱근을 구하는 것이나 —이것은 frobenius 형식이다— 열이나 행에 대해 절대값의 합 중 최대값을 사용하는 방법 등이 있다. 아래는 행렬 노름에 대한 몇 가지 예시이다.
•
행렬 A\bold{A}의 노름을 어떤 단위 노름(unit norm) 입력을 늘릴 수 있는 최대량으로 정의할 수 있다.
∥A∥p=max⁡x≠0∥Ax∥p∥x∥p=max⁡∥x∥=1∥Ax∥p\|\bold{A}\|_p = \max_{\bold{x} \neq 0} {\|\bold{A} \bold{x}\|_p \over \|\bold{x}\|_p} = \max_{\|\bold{x}\| = 1}\|\bold{A}\bold{x}\|_p
•
p=2p = 2인 경우 다음과 같다.
◦
여기서 λmax⁡(M)\lambda_{\max}(\bold{M})은 M\bold{M}의 가장 큰 고유값(eigenvalue)이고, σi\sigma_i는 ii번째 특이값(singular value)이다.
∥A∥2=λmax⁡(A⊤A)=max⁡iσi\|\bold{A}\|_2 = \sqrt{\lambda_{\max}(\bold{A}^\top\bold{A})} = \max_i \sigma_i
•
Trace 노름은 다음과 같이 정의된다.
∥A∥∗=tr(A⊤A)=∑iσi\|\bold{A}\|_* = \text{tr}(\sqrt{\bold{A}^\top\bold{A}}) = \sum_i \sigma_i
•
여기서 ATA\sqrt{\bold{A}^T\bold{A}}는 행렬 제곱근이다. 특이값이 항상 음이 아니기 때문에 다음을 갖는다.
∥A∥∗=∑i∣σi∣=∥σ∥1\|\bold{A}\|_* = \sum_i |\sigma_i| = \|\sigma\|_1
•
이를 regularizer로 사용하여 많은 특이값들을 0으로 만들 수 있고, low rank 행렬을 만들 수 있다.
•
더 일반적으로 Schatten p-norm을 다음처럼 정의한다.
∥A∥p=(∑iσip(A))1/p\|\bold{A}\|_p = \left( \sum_i \sigma_i^p(\bold{A}) \right)^{1/p}
•
만일 행렬을 벡터로 생각하면 행렬 노름을 벡터 노름의 측면에서 정의할 수 있다. ∥A∥=∥vec(A)∥\|\bold{A}\| = \|\text{vec}(\bold{A})\|.
◦
만일 벡터 노름이 2-노름이면, 이에 해당하는 행렬 노름은 Frobenius 노름이 된다.
∥A∥F=∑i=1m∑j=1naij2=tr(A⊤A)=∥vec(A)∥2\|\bold{A}\|_F = \sqrt{\sum_{i=1}^m \sum_{j=1}^n a_{ij}^2} = \sqrt{\text{tr}(\bold{A}^\top\bold{A})} = \|\text{vec}(\bold{A})\|_2
•
만일 A\bold{A}가 평가하기 비싼데, Av\bold{A}\bold{v}는 (확률 벡터 v\bold{v}에 대해) 저렴하다면, 다음과 같이 Hutchinson 추적 추정기를 사용하여 Frobenius 노름에 확률적 근사(stochastic approximation)을 생성 할 수 있다.
◦
아래 식에서 v∼N(0,I)\bold{v} \sim \mathcal{N}(\bold{0}, \bold{I})
∥A∥F2=tr(A⊤A)=E[v⊤A⊤Av]=E[∥Av∥22]\|\bold{A}\|_F^2 = \text{tr}(\bold{A}^\top\bold{A}) = \mathbb{E}[\bold{v}^\top \bold{A}^\top\bold{A}\bold{v}] = \mathbb{E}[\|\bold{A}\bold{v}\|_2^2]

조건수(Condition numbers)

•
행렬 A\bold{A}의 조건 수(condition number)는 A\bold{A}를 포함한 모든 계산이 수치적으로 얼마나 안정적인지를 나타내는 척도이다. 다음과 같이 정의된다.
◦
여기서 ∥A∥\|\bold{A}\|는 행렬의 노름이다.
κ(A)≜∥A∥⋅∥A−1∥\kappa(\bold{A}) \triangleq \|\bold{A}\| \cdot \|\bold{A}^{-1}\|
•
κ(A)≥1\kappa(\bold{A}) \geq 1임을 보일 수 있다.(조건 수는 사용하는 노름에 의존한다. 달리 명시하지 않는한 ℓ2\ell_2 노름을 가정한다.)
◦
κ(A)\kappa(\bold{A})이 작은 경우(1에 가까운) 조건이 양호하다고(well-conditioned) 말한다.
◦
κ(A)\kappa(\bold{A})이 크면 조건이 나쁘다고(ill-conditioned) 한다.
◦
큰 조건수의 의미는 A\bold{A}가 특이(singular)라는 뜻이다.
•
이는 행렬식의 크기보다 특이점에 대한 근접성(nearness)를 더 잘 측정한다.

참조

•
Made with