[LA] Matrix Norm and Condition Number

Vector의 Norm을 이용한 Matrix의 Norm의 정의는 다음과 같음.

 

$$\|A\|=\underset{\textbf{x}\ne\textbf{0}}{\text{max}} \frac{\|A\textbf{x}\|}{\|\textbf{x}\|}$$

• $\textbf{x}$ : 임의의 column vector.

 

위의 Matrix의 Norm에 대한 정의로부터 다음이 성립.

$$\|A\textbf{x}\|\le\|A\|\|\textbf{x}\|$$

 

Condition number (조건수)

행렬의 조건수는 방정식 $A\textbf{x}=\textbf{b}$ 의 민감도를 나타내는 지표임.

• 행렬 $A$ 의 조건수가 크면 (←민감한 경우) 일정한 크기의 input의 상대 오차에 대해서 solution(해)의 상대 오차가 커질 수 있고 (ill-conditioned라고 한다),
• 반대로 작으면 solution의 상대 오차도 작아지게됨(이 경우를 well-conditioned라고 부름).

기계학습 적인 관점에서 말하면, condition number가 클 경우 작은 오차(혹은 noise)에 대해 매우 민감하게 반응하므로 overfitting이 일어나기 쉽다. 다른 데이터 셋으로 학습시 모델이 매우 다른 파라메터(solution에 해당)를 가지게 됨. 전통적인 linear system으로 애기하면, codition number가 클 경우, 사실상 ill-pose inverse problem과 같이 처리되기 싶다. well-posed라고 해도 연산과정에 피할 수 없는 round-off error로 인해 matrix가 singular로 바뀌기 쉽다는 애기임.

 

조건수 유도.

Linear system에서 input $\textbf{b}$가 오차가 발생하여, $(\textbf{b} +\Delta \textbf{b})$로 주어질 경우, solution $\textbf{x}$도 다음과 같은 출력오차를 가지게 됨 : $(\textbf{x}+\Delta \textbf{x})$.

 

즉, 아래의 등식이 성립.

$$A(\textbf{x}+\Delta \textbf{x})=(\textbf{b} +\Delta \textbf{b}) \Rightarrow \Delta \textbf{x} = A^{-1}\Delta \textbf{b}$$

 

위 식에 Matrix의 Norm을 이용하면, 다음과 같은 부등식이 성립.

$$\Delta \textbf{x} = A^{-1}\Delta \textbf{b} \Rightarrow \| \Delta \textbf{x} \| \le \|A^{-1}\| \|\Delta \textbf{b}\| \tag{1}$$

 

원래의 linear system에서 다음이 또한 성립.

$$A\textbf{x}=\textbf{b} \Rightarrow \textbf{b}=A\textbf{x} \Rightarrow \|\textbf{b}\|=\|A\| \|\textbf{x}\| \tag{2}$$

 

부등식 1과 2로부터 다음이 성립함.

$$\frac{\|\Delta \textbf{x}\|}{\|A\| \|\textbf{x}\|} \le \frac{ \|A^{-1}\| \|\Delta \textbf{b}\|}{ \|\textbf{b}\|} \\\\ \frac{\|\Delta \textbf{x}\|}{ \|\textbf{x}\|} \le \|A\| \|A^{-1}\| \frac{\|\Delta \textbf{b}\|}{ \|\textbf{b}\|}$$

 

위에 따르면, input 의 상대오차$\frac{  \|\Delta \textbf{b}\|}{ \|\textbf{b}\|}$에 따른 solution의 상대오차 $\frac{\Delta \|\textbf{x}\|}{ \|\textbf{x}\|}$의 정도가 $\|A\| \|A^{-1}\|$에 의해서 결정되며 이를 Condition number (조건수)라고 한다.

$$\text{cond}(A) = \| A \| \| A^{-1}\| $$

 

 

하지만, 가장 일반적으로 condtion number를 구하는 방법은 SVD(singular value decomposition)을 통한 singular value들을 구하고, 그중 최대값과 최소값의 ratio를 구하는 것임.

$$\text{cond}(A) = \frac{| \sigma_\text{max}(A) |}{|\sigma_\text{min}(A)|}$$

• $\sigma(A)$ : Matrix $A$의 singular value.

 

Reference

https://ghebook.blogspot.com/2021/03/matrix-norm-and-condition-number.html

행렬 노름과 조건수(Matrix Norm and Condition Number)

https://dsaint31.tistory.com/entry/Round-off-Error-vs-Truncation-Error-1

Round-off Error vs. Truncation Error

https://dsaint31.tistory.com/entry/Math-ill-posed-well-posed-ill-conditioned-well-conditioned-matrix-or-problem

[Math] ill-posed, well-posed, ill-conditioned, well-conditioned matrix (or problem)