11. 벡터, 함수, 행렬의 노름

강의 내용

https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/resources/lecture-8-norms-of-vectors-and-matrices/

Lecture 8: Norms of Vectors and Matrices | Matrix Methods in Data Analysis, Signal Processing, and Machine Learning | Mathematic

 

벡터 Norm

$||v||_P = \sqrt{ |v_1|^P + \cdots + |v_n|^P }^{(\frac{1}{P})}$

$||v||_0 = $ 0 이 아닌 성분의 개수! -> 희소성에 대한 질문

근데 $||v||_0$ 와 $||2v||_0$ 의 값은 동일함! 기본적인 Norm 규칙에 부합하지않는다. 그래서 $p$ 는 1 ~ $\infty$ 로 정의한다.

 

2차원 벡터 Norm의 기하학적 의미

$||v||_2 = 1$ -> 반지름이 1인 원을 의미한다.

$||v||_1 = 1$ -> (1,0), (0,1), (-1,0), (0, -1) 을 지나는 다이아몬드 형태를 의미한다.

$||v||_{\infty}$ -> $||v||_1$ 을 두배한 정사각형을 띈다.

그래서 $P$ 가 1부터 점점 커지면 $\infty$ 모습에 가까워진다.

 

$||v||_0$ -> $x$ 축과 $y$ 축들은 1 인점이있고, 두 축이 교차하는 원점은 2 인 값을 갖는다.

$||v||_{\frac{1}{2}}$ -> 는 $||v||_2$ 의 원의 $||v||_1$ 의 대칭으로 안으로 들어간 형태를 갖는다.

 

- $p \geq 1$  에 대해서 모든 $||v||_P$ 는 Convex 하다.

 

$||v||_S$

대칭인 양의 정부호 행렬 $S$ 에 대해서 $||v||_S = \sqrt{v^TSv} $ ( 에너지의 제곱근 )

$v^TSv=1$ 의 형태는 어떻게될까?

2차원에서 $ S = \begin{bmatrix}  2 & 0 \\  0 & 3 \\ \end{bmatrix}$ 형태를 띌때, $v^TSv = 2v_1^2+3v_2^2=1$ 은 타원의 형태를 띈다.

이는 $||v||_2$ 의 변형이라고 볼 수 있다.

 

---

$\min ||x||_1 or \min ||x||_2 , Ax = b$ 문제를 풀어보자.

$Ax = c_1x_1 + c_2 x_2 = b$ 이고 이는 직선을 나타낸다.

아래 빨간색원은 $||x||_2 = 1$ 원이고 $1$ 이란 값이 조절되면서 검은색 직선 $Ax=b$ 에 접하는 최소값을 찾는다.

아래 파란색 다이아몬드는 $||x||_1 = 1$ 의 그래프이고, 값이 조절되면서 직선 $Ax = b$ 에 접하는 최소값을 찾는다.

 

아래는 $\min ||x||_1$ 을 나타내고 이는 Sparse 하다.

 

아래는 $\min ||x||_2$ 을 나타낸 것이다.

그림에서 보듯이 $l_1$ 은 Sparse 한 벡터를 만든다. 직선에 겹쳐지더라도 Sparse 한 벡터를 만들 수 있다.

---

 

행렬 $A$ 에 대한 Norm

 

$||A||_2 = \max \frac{||Ax||_2}{||x||} = \sigma_1$

앞서보았듯이 $||A||_2 = \sigma_1$ 은 어디서 만들어지는 걸까?

 

행렬 L2 Norm $||A||_2$  은 벡터 $||x||_2$ 로 부터 나온다. 이를 어떻게 만들까?

$\frac{||Ax||_2}{||x||_2}$ 를 볼때,

$A$ 가 $x$ 의 크기를 7배증가시키는 행렬이라면, 그 값은 그대로 Blow up 하는 비율이 된다. 

그러니깐 $\frac{||Ax||_2}{||x||_2}$ 는 $A$ 가 벡터 $x$ 를 얼마나 Blow up 하는 비율을 의미한다.

그래서 $\max \frac{||Ax||_2}{||x||}$ 는 $A$ 가 모든 $x$ 에 대해 얼마나 키우는가? 하는 값이다. 그 값이 $||A||_2$ 이다.

 

$\frac{||Ax||_2}{||x||_2}$ 의 최대값인 $A$ 의 Blow up 비율의 최대는 $\sigma_1$ 이라는 것이고, $x = v_1$ 일때를 의미한다.

 

$\frac{||Av_1||_2}{||v_1||_2}$ 에서 $||v_1||_2 = 1$, $||Av_1||_2 =  ||\sigma_1 u_1||_2 = \sigma_1$

즉 $\frac{||Av_1||_2}{||v_1||_2} = \sigma_1$ 이다.

 

 

$||A||_F = \sqrt{|a_1| + \cdots + |a_r| } = \sqrt{\sigma_1^2 + \cdots + \sigma_r^2} $

프로비니우스 Norm 에서 각 원소의 제곱합이 각 특이값의 제곱합과 같은 이유는 뭘까?

$A = U\Sigma V^T$ 에서 $U$, $V$ 는 딱히 제약이 없다. 즉 $U = V = I$ 이면 $A$ 의 모든 원소의 제곱합은 $\Sigma$ 의 모든 원소의 제곱합과 같다.

 

Nuclear Norm

$||A||_N = \sigma_1 + \cdots + \sigma_r $

 

 

---

내용 정리

 

0 이아닌 벡터 $v$ 의 Norm은 양수인 $||v||$ 이다. 즉 벡터의 길이이다.

Norm 을 측정하는 방식은 다양하지만, 벡터, 행렬, 함수 등 모든 노름은 반드시 두 가지 특성을 만족한다.

$v$ 에 $c$ 를 곱한다. (재척도구성) : $||cv|| = |c| ||v||$
$v$ 에 $w$ 를 곱한다. (삼각부등식) : $||v+w|| \leq ||v|| + ||w||$

 

벡터 Norm 은 3 가지가 중요하고 특별하다.

벡터 $v$ 는 $R^n$ 혹은 $C^n$ 에 있다.

$l^2$ Norm = 유클리드 Norm : $||v||_2 = \sqrt{ |v_1|^2 + \cdots + |v_n|^2 }$
$l^1$ Norm = 1-Norm : $||v||_1 = |v_1| + \cdots + |v_n|$
$l^{\infty}$ Norm = 최대 Norm : $||v||_{\infty} = \max ( |v_1|, \cdots , |v_n| )$

 

---

직선 $a_1v_1 + a_2v_2 = 1$ 위에서 $||v||_p$ 의 최소

 

직선 $3v_1+4v_2=1$ 위에 점중 (0,0) 에 가장 가까운 점은 무엇일까?

위 질문에 대한 Norm 에 달려있고, 어떤 Norm 이냐에 따라 그 해가 다르다.

 

위에서 봤듯이 $l^1$ 은 마름모꼴, $l^2$ 는 원, $l^{\infty}$ 는 정사각형이 직선에 닿을 때까지 확정한다.

즉 $3v_1+4v_2=1$ 위의 벡터 (v_1, v_2) 들로 $||v||_p$ 를 최소화하라.



$l^1$ 의 최소해는 많이 봤듯이 매우 중요한 희소한 특징을 가진다.

$l^2$ 의 최소해는 각 성분들이 매우 작고 비슷해 그다지 흥미롭지않다.

이러한 직선(고차원에서의 초평면)은 제약조건 $Av=b$ 를 푸는 벡터를 가진다.

 

---

내적과 각

 

보통 첨자없이 $||v||$ 로 쓰면 $l^2$ Norm 을 뜻한다. 그만큼 특별하다는 의미이다.

 

각 벡터의 내적 (v,w) 은 벡터 사이의 각을 연결한다.

$v\cdot w = v^Tw = ||v|| ||w|| \cos \theta$

위 식을 통해서 코시-슈바르츠 $|v^Tw| \leq ||v|| ||w||$, 삼각 부등식 $ ||v+w|| \leq ||v|| + ||w||$ 이 유도된다.

즉 $l^2$ Norm 을 통해서 내적과 각을 연결하는 만큼 중요하다는 의미이다.

 

그럼 다른 Norm 으로 내적과 각을 연결할 수 있을까?

---

S-Norm

 

$l^1$, $l^{\infty}$ Norm 에는 내적이 없다. 하지만 다른 Norm 에는 맞는 내적을 찾을 수 있다.

임의의 대칭인 양의 정부호 행렬 $S$,
$||v||_S^2 = v^TSv$ 는 $R^n$ 에서 $v$ 의 Norm (S-Norm) 을 준다.
$(v,w)_S = v^TSw$ 는 $R^n$ 에서 $v$,$w$ 에 대해 S-Norm을 준다.

여기서 $S = A^TA$ 로 분해되고, 벡터의 내적은 $(v,w)_S = v^TSw = v^TA^TAw = (Av)^T(Aw)$ 으로 분해될 수 있다.

이것은 행렬 $A$로 가중된 $v$, $w$ 의 $l^2$ 과 정확히 동일하다.

---

함수의 Norm 과 내적

 

함수 $f(x)$ 는 함수공간에서 벡터이다. 이 아이디어는 차원을 유한차원에서 무한차원으로 확장시킨다. ( 실수범위는 무한하기 때문에 )

벡터공간에 대한 필요조건은 선형 결합을 허용하는 것이고, 이 또한 함수의 선형결합으로 확장된다.

 

무한차원으로 확장될때, 생기는 새로운 의문은 Norm 과 관련이 있다. 

 

$l^2$ Norm 에서 특별한벡터 $v_n = (1, \frac{1}{2}, \cdots, (\frac{1}{2})^n, 0, 0, \cdots)$ 들은

$n \to \infty$, $N \to \infty$ 일때, $||v_n - v_N|| \to 0$ 으로 가까워진다. ( 그렇다고함, 잘모르겠음 )

벡터공간이 완비이기 위해서는 수렴하는 모든 수열 $v_n$ 이 공간 내에 극한 $v_{\infty}$ 가 있어야한다. 즉, $||v_n - v_{\infty}|| \to 0$ 이다. ( 그렇다고함, 잘모르겠음 )

 

1. 뒤의 성분이 모두 0 인 무한벡터 $v = (v_1, \cdots, v_N, 0, 0, \cdots)$ 으로 이루어진 공간은 완비가 아니다.
2. $||v||^2 = |v_1|^2 + |v_2|^2 + \cdots < \infty$ 를 만족하는 벡터의 공간은 완비이다. $v_{\infty} = (1, 1/2, 1/4, 1/8, \cdots)$ 같은 벡터는 이러한 공간에 포함되지만, 1번 식의 공간에는 포함되지 않는다. 성분들이 0 으로 끝나지 않는다.

 

• 바나흐 공간 Banach space 은 식 1 과 2 를 만족하는, Norm $||v||$ 를 가진 완비벡터공간이다.
• 힐베르트 공간 Hilbert space 는 $(v, v)$ 가 $||v||^2$ 과 같은 내적을 가지는 바나흐 공간이다.

이러한 공간은 벡터에 성분이 무한히 많으면 무한차원이다. -> 함수로 이어짐

• $l^1$ 은 Norm 이 $||v||_1 = |v_1| + |v_2| + \cdots$ 인 바나흐 공간이다.
• $l^2$ 는 내적 $(v,w) = v_1w_1 + v_2w_2 + \cdots$ 가 있으므로 힐베르트 공간이다.
• $l^{\infty} 는 Norm 이 $||v||_{\infty} = \max ( |v_1|, |v_2|, \cdots) $ 인 바나흐 공간이다.

 

여기서 벡터를 $0 \leq x \leq 1$ 에서 정의된 함수 $f(x)$ 로 생각할 수 있다. (여기서 벡터는 무한차원)

• $L_1[0,1]$ 은 $||f||_1 = \int_0^1|f(x)| \mathrm{d} x$ 를 만족하는 바나흐 공간이다.
• $L_2[0,1]$ 는 $(f,g) = \int_0^1 f(x)g(x) \mathrm{d} x $ 와 $||f||_2^2 = \int_0^1 |f(x)|^2 \mathrm{d} x$ 를 만족하는 힐베르트 공간이다.
• $L_{\infty}[0,1]$ 는 $||f||_{\infty} = \max (|f(x)|) $ 를 만족하는 바나흐 공간이다.

여기서 각 Norm 에서 성분의 총합과 함수의 적분이 유사하다는 것을 알 수 있다.

 

(대충은 이해가는데 애매함, 마지막 결론에 집중함)

---

함수의 매끈함

함수공간은 다양하게 정의된다. 특정한 매끈함을 가지는 모든 함수를 모아 한 함수공간으로 만들기도 한다.

그 예로 모든 연속함수로 이루어진 공간 $C[0,1]$ 이 있다.

 

$f(x)$ 가 $0 \leq x \leq 1$ 에서 연속이면, $f$ 는 $C[0,1]$ 에 속하고, $||f||_C = \max |f(x)| $ 이다.($l^{\infty}$ 와 유사)

(어떻게 어떻게 이렇게 증명되나봄)

 

매끈함 정도를 $C^1[0,1]$ 이나 $C^2[0,1]$ 만큼 높혀본다면, 함수는 1계 미분이나, 2계 미분도 연속이어야 한다.

이 두 공간은 바나흐 공간이지만, 힐베르트 공간은 아니다. 이 노름은 내적에서 비롯되지 않는다.

 

• $||f||_{C^1} = ||f||_C + || \frac{\mathrm{d} f}{\mathrm{d} x} ||_C
• $||f||_{C^2} = ||f||_C + || \frac{\mathrm{d^2} f}{\mathrm{d} x^2} ||_C

힐베르트 공간 $H^1$ 이 필요하다면 일반적인 $L^2$ 공간 ( $H^0$ ) 을 만들어야 한다.

• $||f||_{H^1}^2 = ||f||^2 + || \frac{\mathrm{d} f }{\mathrm{d} x} ||^2$
• $(f,g)_{H^1} = \int_0^1 f(x) g(x) \mathrm{d} x + \int_0^1 \frac{\mathrm{d} f}{\mathrm{d} x} \frac{\mathrm{d} g}{\mathrm{d} x} \mathrm{d} x$

예를 들어보자

• 무한벡터 $v = (1, 1/2, 1/3, 1/4, \cdots)$ 는 $l^2$, $l^{\infty}$ 에 존재하지만, $l^1$ 에는 존재하지 않는다. 이 벡터의 모든 성분의 합은 발산하기 때문이다.
• 계단함수는 $L^1, L^2, L^{\infty}$ 에는 존재하지만, $C$ 에는 존재하지 않는다. 연속이 아니기때문
• 램프 함수 $\max(0, x)$ 는 $C$ 와 $H^1$ 에 있지만, $C^1$에는 없다. 함수의 기울기가 불연속이기 때문

(여기까지 여차저차 이해했는데, 이 함수공간이 어떻게 쓰일지 궁금함)

 

---

행렬 노름

 

행렬 공간은 벡터 공간의 모든 법칙을 따른다. 행렬 노름도 벡터 노름의 법칙을 따르고, 추가로 곱셈에 대한 새로운 법칙이 성립한다.

- $A$ 가 0 이아닌 행렬이면 $||A|| > 0$ 이다.
- $||cA|| = |c| ||A||$ 이고, $||A+B|| \leq ||A|| + ||B||$
- $||AB|| \leq ||A|| ||B||$ 이다.

---

프로베니우스 노름

$||A||_F^2 = |a_{11}|^2 + \cdots + |a_{1n}^2| + \cdots + |a_{mn}^2|$

프로베니우스 노름은 성분이 $mn$ 개인 벡터의 $l^2$ 노름 이다.

 

행렬은 긴 벡터로 생각하는 프로베니우스노름에 대해 기본적인 벡터 노름에 대한 식은 성립하고, 행렬곱에 관한 식이 성립하는 지 확인하자.

 

먼저 랭크가 1 인 행렬 $AB$ 를 생각해보면,

$AB = ab^T = \begin{bmatrix} a_1 \\ \vdots \\ a_m \end{bmatrix} \begin{bmatrix} b_1 & \cdots & b_n \\ \end{bmatrix}$

$||AB||_F^2 = ||ab^T||_F^2 =\begin{matrix} |a_1|^2(|b_1|^2 + \cdots + |b_n|^2) \\ \cdots + \\ |a_m|^2(|b_1|^2 + \cdots + |b_n|^2)  \end{matrix} = ||a||_F^2 ||b||_F^2 $ 를 만족한다.

 

이를 확장해서 행렬 $AB$ 를 랭크 1 인 행렬의 합으로 표현하자.

$||AB||_F = ||a_1b_1^T + \cdots + a_nb_n^T ||_F \\ \leq ||a_1b_1^T||_F + \cdots + ||a_nb_n^T||_F \\ = ||a_1||_F||b_1||_F + \cdots + ||a_n||_F ||b_n||_F \\ \leq (||a_1||_F^2 + \cdots + ||a_n||_F^2)^{1/2}(||b_1||_F^2 + \cdots + ||b_n||_F^2)^{1/2} \\ = ||A||_F ||B||_F $

 

먼저 열과 행의 곱의 합으로 나누고, 행렬합의 노름은 각 행렬의 합 노름보다 작거나 같은 부등식을 이용하고, 각 벡터의 노름으로 분해후,  코시-슈바르츠 부등식을 이용해 변환하면 프로베니우스 노름은 행렬곱에 관한 식이 성립함을 알 수 있다.

 

그리고 프로베니우스 노름의 전에 봤던 특이값에 관한 식도 살펴보자.

먼저, 직교행렬 $Q$ 에, $Qx$ 는 $x$ 와 동일한 $l^2$ 를 가진다.

• $||Qx||_2 = ||x||_2$
• $Q$ 에 $B$ 열을 곱하면 $QB$ 의 각 열은 위와같이 직교행렬과 벡터의 곱으로 표현되고, 각 벡터의 $l^2$ Norm의 합 으로  표현되는 프로비니우스 노름은 ,$||QB||_F = ||B||_F$ 를 만족한다.

이것이 $A = U\Sigma V^T$ 와 프로베니우스 노름을 연결짓는다.

$||A||_F = ||U\Sigma V^T||_F =  ||\Sigma V^T||_F = ||\Sigma||_F = \sqrt{\sigma_1^2 + \cdots + \sigma_r^2}$
또는 $A^TA$ 를 통해 모든 원소의 제곱합을 대각성분을 취하는 것으로 변형시킨다.
$||A||_F^2 = $ (모든 원소의 제곱합) $= A^TA$의 대각합 = (고유값의 합) = $\sigma_1^2 + \cdots + \sigma_r^2$

---

벡터 노름 $||v||$ 에서 행렬 노름 $||A||$ 로

$R^n$ 에 있는 임의의 벡터 $v$ 에 대한 노름 $||v||$ 에 대해서, 성장인자를 측정한 $||Av||$ 와 $||v||$ 를 비교하여 $A$ 를 곱할 때 생성된 크기의 증가나 감소를 확인한다. 여기서 가장 큰 성장인자를 가지는 벡터 $v$ 를 선택하면 벡터 $v$ 는 중요한 행렬 노름 $||A||$ 를 준다. 즉 벡터 노름이 행렬 노름을 이끈다.

$||A|| = \max_{v \neq 0} \frac{||Av||}{||v||}$ = 가장 큰 성장 지수

가장 큰 비율 $||A||$ 는 모든 행렬 노름 조건을 만족한다. $||v||$ 가 이미 벡터 노름 조건을 만족하기 때문이다.

$\frac{||Av||}{||v||}$ 의 최대가 $||A||$ 이기 때문에 식 $||Av|| \leq ||A|| ||v||$ 를 만족한다. 그러므로 $||AB|| \leq ||A|| ||B||$ 를 만족한다.

 

위에서 살펴본 세가지 벡터노름 $l^1$, $l^2$, $l^{\infty}$ 들은 행렬 노름 $||A||_1$ , $||A||_2$, $||A||_{\infty}$ 를 만든다.

이들 모두 $||AB|| \leq ||A|| ||B||$ 를 만족한다.

$l^1$ 노름 : $||A||_1$ = $A$ 열에 대한 가장 큰 $l^1$ 노름
$l^2$ 노름 : $||A||_2 = $ $A$ 의 가장 큰 특이값 $\sigma_1$
$l^{\infty}$ 노름 : $||A||_{\infty}$ = $A$ 의 행에 대한 가장 큰 $l^1$ 노름

$||A||_2 = \max ||Av||_2 / ||v||_2 = \sigma_1$ 이라는 사실은 중요하고 $A = U\Sigma V^T$ 에서 기인한다.

직교행렬 $U$, $V^T$ 가 $l^2$ 에 영향을 주지않아 $||A||_2 = ||\Sigma||_2 = \sigma_1$ 을 이끈다. 여기서 행렬의 $l^2$ 노름은 프로베니우스 노름과 다르다.

 

$||A||_{\infty} = ||A_1^T||_1$,          $ ||A||_2^2 \leq ||A||_1 ||A||_{\infty}$

3가지 행렬 노름은 위와 같은 연관성을 가진다. $A$ 의 열은 $A^T$ 의 행으로 첫번째 식이 성립함을 알 수 있고,

$A$ 의 첫번째 특이벡터 $v$ 에 대해서, $A^TAv = \sigma_1^2 v$ 를 만족하고, $l^1$ 노름을 취하면,

$$ \sigma_1 ||v||_1 = ||A^TAv||_1 \leq ||A^T||_1 ||Av||_1 \leq ||A||_{\infty} ||A||_1 ||v||_1 $$

$\simga_1 = ||A||_2$ 이므로 $||A||_2^2 \leq ||A||_{\infty} ||A||_1$ 임을 알 수 있다.

 

---

핵 노름 Nuclear Norm

$||A||_N$ 은 특이값에서 바로 구할 수 있다.

$l^2$ 와 프로베니우스와 마찬가지로 $A=U\Sigma V^T$ 에서 시작하고, $U$, $V$ 에 영향을 받지않는다.

$||A||_N = \sigma_1 + \cdots + \sigma_r$,        $||A||_F^2 = \sigma_1^2 + \cdots + \sigma_r^2$,        $||A||_2 = \sigma1$

행렬의 데이터가 누락되었을때, 핵 노름이 행렬완성의 핵심이다.

$||A^TA||_N = ||A||_F^2$ 를 만족한다.