Vector norm, matrix norm (벡터 노름, 행렬 노름)

오늘은 norm에 대해서 알아보도록 하겠습니다.

 

Vector norm

 

벡터 노름이라고하면, 어떤 벡터를 길이나 사이즈같은 양적인 수치로 mapping하기 위한 함수(||.|| : V → R)입니다.

 

그러면 벡터공간(Vector space) V와 scalar a에 대하여 정의합니다. 벡터 노름은 다음 세가지 조건을 충족시켜야 합니다.

 

$$\mathsf{1.}\Vert \mathsf{u}\mathsf{+}\mathsf{v}\Vert \le \Vert \mathsf{u}\Vert \mathsf{+}\Vert \mathsf{v}\Vert$$

$$\mathsf{2.}\Vert \mathrm{a}\mathsf{v}\Vert \mathsf{=}\mid \mathrm{a}\mid \Vert \mathsf{v}\Vert$$

$$\mathsf{3.}\mathsf{If}\Vert \mathsf{v}\Vert \mathsf{=}\mathsf{0}\mathsf{,}\mathsf{then}\mathsf{v}\mathsf{=}\mathsf{0}$$

 

$$\mathsf{where}\mathsf{u}\mathsf{,}\mathsf{v}\in \mathsf{V}\mathsf{and}\mathrm{a}\in \mathbb{R}$$

 

즉 이 3가지 조건을 충족시키면 norm이라고 정의될 수 있는것입니다.

 

예를들면 우리가 잘 알고있는 absolute value가 있습니다. 번역하면 절댓값이죠. 이 절댓값은 사실상 ||x||이지만, 특별히 one dimensional vector space에서의 norm으로 |x|로 사용됩니다.

즉 L1 norm의 특별한 케이스입니다.

 

그럼 L1 norm이 뭔지, 또 그밖의 norm들은 무엇이 있는지 간단하게 알아보도록 합시다.

벡터공간(vector space) V의 임의의 벡터 x에 대해 생각하겠습니다.

 

L1 norm

 

$$\Vert \mathsf{x}{\Vert }_{\mathsf{1}}\mathsf{:=}\sum _{\mathsf{i}\mathsf{=}\mathsf{1}}^{\mathsf{n}}\mid {\mathsf{x}}_{\mathsf{i}}\mid$$

L1 norm은 위와같이 정의됩니다. 이 norm을 이용한 distance로 유명한 맨해튼 거리(L1 distance) 가 있습니다.

 

L2 norm

 

$$\Vert \mathsf{x}{\Vert }_{\mathsf{2}}\mathsf{:=}\sqrt{\sum _{\mathsf{i}\mathsf{=}\mathsf{1}}^{\mathsf{n}}{\mathsf{x}}_{\mathsf{i}}^{\mathsf{2}}}$$

 

가장 많이 쓰이고 많이 알 것이라고 생각되는 norm 입니다. 바로 Uclidean norm입니다. 가장 직관적으로 이해하기가 쉽습니다. 벡터의 길이 라고 생각하면 쉽게 이해될 것입니다.

 

위와같이 정의되긴하지만 다르게 아래처럼 자기자신과의 dot product로도 쓰일 수 있습니다.

 

$$\Vert \mathsf{x}{\Vert }_{\mathsf{2}}\mathsf{:=}\sqrt{\mathsf{x}\cdot \mathsf{x}}$$

 

p-norm

 

위의 L1, L2 norm을 일반화 한 것입니다. 실수 p에대해서 정의되고 Lp norm 이라고도 합니다.

 

벡터 x = (x1, x2, ... ,xn)에 대해서

 

$$\Vert \mathsf{x}{\Vert }_{\mathsf{p}}\mathsf{:=}{(\sum _{\mathsf{i}\mathsf{=}\mathsf{1}}^{\mathsf{n}}\mid \mathsf{x}{\mid }^{\mathsf{p}})}^{\mathsf{1}\mathsf{/}\mathsf{p}}$$

이와같이 정의됩니다.

 

 

이 중에서도 특이한 케이스로 p가 무한대  일때는 다음과같이 정의하고, maximum norm 이라고 부릅니다.

 

$$\Vert \mathsf{x}{\Vert }_{\mathrm{\infty }}\mathsf{:=}\underset{\mathsf{i}}{max}\mid {\mathsf{x}}_{\mathsf{i}}\mid$$

 

 

---

 

Matrix norm

행렬 노름 마찬가지로 벡터 노름과 같이 반드시 충족해야하는 특성들이 몇가지 있습니다.

 

$$\mathsf{\text{ For all Scalars}}\alpha \in \mathbb{R}\mathsf{\text{and for all matrices}}\mathsf{A}\mathsf{,}\mathsf{B}\in {\mathbb{R}}^{\mathsf{mxn}}$$

$$\mathsf{1.}\Vert \alpha \mathsf{A}\Vert \mathsf{=}\mid \alpha \mid \Vert \mathsf{A}\Vert$$

$$\mathsf{2.}\Vert \mathsf{A}\mathsf{+}\mathsf{B}\Vert \le \Vert \mathsf{A}\Vert \mathsf{+}\Vert \mathsf{B}\Vert$$

$$\mathsf{3.}\Vert \mathsf{A}\Vert \ge \mathsf{0}$$

$$\mathsf{4.}\Vert \mathsf{A}\Vert \mathsf{=}\mathsf{0}⟺\mathsf{A}\mathsf{=}{\mathsf{0}}_{\mathsf{m}\mathsf{,}\mathsf{n}}$$

 

추가적으로 square matirces에 대해서는 한 가지더 특성이 추가됩니다.

$$\Vert \mathsf{AB}\Vert \le \Vert \mathsf{A}\Vert \Vert \mathsf{B}\Vert \mathsf{for}\mathrm{\forall }\mathsf{A}\mathsf{and}\mathsf{B}\in {\mathsf{K}}^{\mathsf{mxn}}$$

 

다음으로 matrix norm을 정의하기위해서 Operator norm을 알아봅시다.

 

Operator norm (or induced norm)

 

 linear operator의 'size'를 측정하기 위한 수단입니다. 즉 A라는 operator가 주어질 때 이것을 양적으로 크기를 나타내기위해 vector norm을 응용하게됩니다. 그래서 vector norm에서 유도된 것이 induced norm입니다.

A라는 operator가 x를 변환시키는데 (A : V → W), 변환시키는 값은 bounded 되어있고 그것은 ||x||의 c 배와 같거나 더 작다 라는것 입니다.

글로만 보면 어려우니 수식으로 된 정의를 함께 보도록 하겠습니다.

 

다음의 수식들은 모두 동치입니다.

 

$$\Vert \mathsf{A}{\Vert }_{\mathsf{op}}\mathsf{=}inf\{\mathsf{c}\ge \mathsf{0}\mid \Vert \mathsf{Ax}\Vert \le \mathsf{c}\Vert \mathsf{x}\Vert \mathsf{for}\mathrm{\forall }\in {\mathsf{K}}^{\mathsf{n}}\}\mathsf{-}\mathsf{(}\mathsf{1}\mathsf{)}$$

$$\mathsf{=}sup\{\Vert \mathsf{Ax}\Vert \mid \mathsf{v}\in {\mathsf{K}}^{\mathsf{n}}\mathsf{with}\Vert \mathsf{x}\Vert \mathsf{=}\mathsf{1}\}\mathsf{-}\mathsf{(}\mathsf{2}\mathsf{)}$$

$$\mathsf{=}sup\{\frac{\Vert \mathsf{Ax}\Vert }{\Vert \mathsf{x}\Vert }\mid \mathsf{v}\in {\mathsf{K}}^{\mathsf{n}}\mathsf{with}\mathsf{x}\ne \mathsf{0}\}\mathsf{-}\mathsf{(}\mathsf{3}\mathsf{)}$$

 

위의 (1)의 inf에서 아래의 sup로 넘어가는 과정은 ||Ax|| ≤ c||x|| 에서 양변을 ||x||로 나누어주고 생각하면 쉬울 것 입니다.

또한 (2)이 되는 이유는 벡터 x의 norm을 λ라고 생각해봅시다.

 

$$\frac{\Vert \mathsf{Ax}\Vert }{\Vert \mathsf{x}\Vert }\mathsf{=}\frac{\lambda \Vert \mathsf{A}\frac{\mathsf{x}}{\lambda }\Vert }{\lambda \Vert \frac{\mathsf{x}}{\lambda }\Vert }$$

 

그렇다면 위와같이 나타낼 수 있는데 , λ약분하고나면 v/λ는 크기가 1인 벡터 이므로, 분모는 1이 되고 나머지 v/λ는 크기가 1인 임의의 벡터로 치환될 수 있습니다.

 

이제는 matrix norm 의 종류를 몇가지 살펴보고 끝내겠습니다.

 

matrix norm induced by L1 vector norm

 

$$\Vert \mathsf{A}{\Vert }_{\mathsf{1}}\mathsf{=}\underset{\mathsf{1}\le \mathsf{j}\le \mathsf{n}}{max}\sum _{\mathsf{i}\mathsf{=}\mathsf{1}}^{\mathsf{m}}\mid {\mathsf{a}}_{\mathsf{ij}}\mid$$

간단하게 matrix의 column의 합의 최댓값을 나타내는 norm 입니다.

 

matrix norm induced by L2 vector norm

 

$$\Vert \mathsf{A}{\Vert }_{\mathsf{2}}\mathsf{=}{\sigma }_{\mathsf{max}}\mathsf{(}\mathsf{A}\mathsf{)}$$

위의 시그마는 A 의 largest singular value를나타내는 값 입니다. singular value를 구하는 방법은 이전의 포스팅을 참고해 주세요 .

 

저는 이 부분이 공부하면서 왜이렇게 되는지 궁금했던터라, 이 글을 보는 다른분들도 궁금해 하실수도 있으므로 아래에 증명도 함께 하겠습니다.

 

$$\mathsf{Why}\Vert \mathsf{A}{\Vert }_{\mathsf{2}}\mathsf{=}{\sigma }_{\mathsf{max}}\mathsf{(}\mathsf{A}\mathsf{)}\mathsf{?}$$

$$\Vert \mathsf{A}{\Vert }_{\mathsf{2}}\mathsf{=}\underset{\Vert \mathsf{x}{\Vert }_{\mathsf{2}}\mathsf{=}\mathsf{1}}{sup}\Vert \mathsf{Ax}{\Vert }_{\mathsf{2}}$$

$$\mathsf{=}\underset{\Vert \mathsf{x}{\Vert }_{\mathsf{2}}\mathsf{=}\mathsf{1}}{sup}\mathsf{(}{\mathsf{x}}^{\mathsf{T}}{\mathsf{A}}^{\mathsf{T}}\mathsf{Ax}{\mathsf{)}}^{\frac{\mathsf{1}}{\mathsf{2}}}$$

$$\mathsf{=}\underset{\Vert \mathsf{x}{\Vert }_{\mathsf{2}}\mathsf{=}\mathsf{1}}{sup}\mathsf{(}{\mathsf{x}}^{\mathsf{T}}{\mathsf{Q}}^{\mathsf{T}}\wedge \mathsf{Qx}{\mathsf{)}}^{\frac{\mathsf{1}}{\mathsf{2}}}$$

$$\mathsf{=}\underset{\Vert \mathsf{y}{\Vert }_{\mathsf{2}}\mathsf{=}\mathsf{1}}{sup}\mathsf{(}{\mathsf{y}}^{\mathsf{T}}\wedge \mathsf{y}{\mathsf{)}}^{\frac{\mathsf{1}}{\mathsf{2}}}\mathsf{for}\mathsf{y}\mathsf{=}\mathsf{Qx}$$

$$\mathsf{=}{\sigma }_{\mathsf{max}}\mathsf{(}\mathsf{A}\mathsf{)}$$

 

 

그럼 안녕 !

 

Reference

[1]https://en.wikipedia.org/wiki/Norm_(mathematics)

[2]https://en.wikipedia.org/wiki/Matrix_norm

[3]https://www.math.uh.edu/~jingqiu/math4364/iterative_linear_system.pdf