Affine and convex sets - norm

Norm ball과 Norm cone에 대해서 공부하기전에 먼저 norm에 대해서 먼저 알아보자. 

 

norm이란 n차원 실수집합에서 1차원 실수집합으로 대응되는 함수로 아래의 성질을 만족한다.

$$ \text{A function} \;f \; : \; \mathbf{R}^n \to \; \mathbf{R} \; \text{with} \; \mathbf{dom} f = \mathbf{R}^n \; \text{is called a norm if} $$

$$ \text{(1)} \quad f(x) \geq 0 \; \text{for all} \; x \in \mathbf{R} $$

$$ \text{(2)} \quad f(x) =0 \; \text{only if} \; x = 0 $$

$$ \text{(3)} \quad f(tx) = \lVert t \rVert f(x), \; \text{for all} \; x \in R^n \; and \; t \in \mathbf{R} $$

$$ \text{(4)} \quad f(x+y) \leq f(x) + f(y), \; \text{for all } \; x,y \in  \mathbf{R}^n $$

 

일반적으로 norm에 대한 표기는 $ \lVert x \rVert _\text{symb} $으로 표현하며, 많이 알려져 있는 Euclidean norm의 경우 $ f(x) = \lVert x \rVert_2$ 이런 식으로 표기된다.

 

또한 norm을 통해 벡터 $x$의 길이(length)를 측정할 수 있으며, 서로 다른 두 벡터의 거리도 측정가능하다.

 

두 벡터의 거리는 $ dist = \lVert x-y \rVert \; $로 정의가 된다.

 

norm값이 1보다 작거나 같은 벡터들의 집합을 unit ball이라고 하며, 수학적으로는 아래와 같이 표기할 수 있다.

$$ B \; = \; \left\{ x \in R^n \; | \; \lVert x \rVert \leq 1 \right\} $$

unit ball은 convex이며, closed, bounded, non-empty interior하다는 특징을 지니고 있다.

 

실제로 자주 사용 되는 norm 중 $ l_p-norm$을 알아보자. $ l_p-norm$은 아래와 같이 정의 된다.

$$ \lVert x \rVert _p = \left( \left\vert x_1 \right\vert^p +\text{. . . } +\left\vert x_n \right\vert^p\right)^\text{1/p} $$

$l_1-norm$은 $ \lVert x \rVert_1 = \left\vert x_1 \right\vert+ \text{. . . } + \left\vert x_n \right\vert$로 정의 되며,

 

$l_2-norm$인 경우 우리가 잘 알고 있는 Euclidean norm이 된다.

 

$l_\infty - norm$은 $\; \lim_{p \to \infty}\lVert  \rVert_p = \max \left\{\left\vert x_1 \right\vert, \; \left\vert x_2 \right\vert, \; \text{. . .  ,}\; \left\vert x_n \right\vert \right\}$로 정의 된다.

 

그림 및 자료 출처 : Boyd, S., Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.