Matrix Norm and Condition Number

https://en.wikipedia.org/wiki/Condition_number

Matrix Norm

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}\|$$

 

좀 더 자세히 말하면, 이는 Operator norm (or induced norm)이라고 불리는 것으로 matrix를 linear transform으로 보고 해당 변환이 얼마나 input vector의 norm을 "증가시키는지"를 norm으로 표현함.

사용하는 vector norm (L-p Norm에서 p의 값에 따라 다름)의 종류에 따라 값이 달라짐.

 

참고로 Matrix Norm 으로 더 많이 사용되는 것은 Frobenius norm임:

$$\|A\|_\text{Frobenius} = \sqrt{\sum_{i,j} |a_{i,j}|^2}$$

---

참고: Norm이란?

https://dsaint31.tistory.com/254#Norm%20(%EB%85%B8%EB%A6%84)-1-5

[Math] Vector (1)

---

Condition number (조건수)

행렬의 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과 같이 처리 (정확히는 ill conditioned problem)되기 싶다.
• well-posed라고 해도 연산과정에 피할 수 없는 round-off error로 인해 matrix가 singular로 바뀌기 쉽다는 애기임.

---

Condition Number(조건수) 유도.

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}\| $$

---

Singular value ratio: Condtion Number

위의 설명은 개념을 반영한 설명이고,

가장 일반적으로 condtion number를 구하는 방법은 SVD(singular value decomposition)을 통한 singular value $\sigma$들을 구하고, 그중 최대값과 최소값의 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)