Norms

Definition

vector space $V$ 상에서의 함수 혹은 연산 값을 norm이라고 한다.

그 함수 혹은 연산은 $\left\vert\left\vert \cdot\right\vert\right\vert : V\rightarrow\mathbb{R}$ 와 같이 연산된 값이 하나의 스칼라 값으로 나타나게 된다.

즉, 간단히 설명하자면 vector $\mathbf{x}$의 길이는 norm으로 표현되고, $\left\vert\left\vert \mathbf{x}\right\vert\right\vert \in \mathbb{R}$로 나타낼 수 있다.

Conditions

• Homogeneous : $\lVert\lambda\mathbf{x} \rVert = \left\vert \lambda \right\vert\lVert\mathbf{x} \rVert$
  벡터에 스칼라 값을 곱한 것을 norm을 취하나, norm을 취한 벡터에 스칼라 값을 곱하나 결과는 같다.

• Triangle inequality : $\lVert \mathbf{x+y}\rVert\le\lVert \mathbf{x}\rVert +\lVert \mathbf{y}\rVert$
  

• Positive Definite : $\lVert \mathbf{x}\rVert\ge0$ 그리고, $\lVert \mathbf{x}\rVert= 0$이라고 함은, $\mathbf{x}=0$일 때를 의미한다.
  (앞으로 나올 부등호에서 0을 포함한 것은 중요한 포인트이다. x=0을 만족해야만 한다.)

다양한 Norms

General form으로 P-norm이라고 지칭한다.

• notation : $\lVert\mathbf{x_p}\rVert\equiv\sqrt[p]{\sum_{i=1}^nx_i^p}$

Manhattan Norm(L1-norm)

$\lVert\mathbf{x_1}\rVert\equiv\sum_{i=1}^n\left\vert x_i\right\vert$

Euclidean Norm(L2-norm)

$\lVert\mathbf{x_p}\rVert\equiv\sqrt{\sum_{i=1}^nx_i^2}=\sqrt{\mathbf{x^T}\mathbf{x}}$

이후에는 학습적으로 L2-norm을 "norm"이라고 간주한다.(단, 논문이나 기타 공식적인 문서를 예외다. 정확히 무슨 norm인지 표시해줘야 한다.)

Dot Product

Definition

$\mathbf{x\cdot y}\equiv\mathbf{x^T\cdot y}=\sum_{i=1}^nx_iy_i$

즉, 스칼라 곱이라고 생각하면 쉽다. 두 벡터의 곱이 하나의 스칼라 값이 나온다. 앞으로는 세 번째 수식이 아닌 두 번째 수식에 익숙해져야 한다.

Dot Product $\neq$ Inner Product(내적)

사실, Dot Product $\in$ (General) Inner Product 관계이다.

Bilinear mapping

Definition

두개의 arguments(벡터)를 받아서 출력(매핑)시키는 것을 뜻한다.(i.e. $\mathbf\Omega(x,y)$)

Conditions

두 가지 조건을 모두 만족해야 한다.

• $\mathbf{\Omega(\lambda x+\psi y,z)=\lambda\Omega(x,z)+\psi\Omega(y,z)}$
  '스칼라를 곱하고 더한 것'의 매핑과 '매핑하고 스칼라를 곱하고 더한 것'의 값이 같아야 한다.
• $\mathbf{\Omega( x,\lambda y+\psi z)=\lambda\Omega(x,y)+\psi\Omega(x,z)}$
  Bilinear하므로 뒤에서 한 것의 값도 같아야 한다.

Symmetric & Positive Definite

Bilinear mapping이 특정 조건을 만족할 경우, 어떠한 특성을 가지고 있는 Bilinear mapping이라고 설명할 수 있다.

단, Bilinear mapping을 $\mathbf{V}$X$\mathbf{V}\rightarrow\mathbb{R}$ 인 경우로 한정한다. 즉 두 벡터 스페이스에서 각각의 벡터를 뽑아서 연산했을 때, 하나의 스칼라 값이 나오는 경우로 한정 짓는다.

• Bilinear mapping이 Symmetric하다
  ($\Omega$ is "Symmetric")고 표현되려면,
  If $\mathbf{\Omega(x,y)=\Omega(y,x)}$ for all $\mathbf{x,y}\in\mathbf{V}$

i.e.) 내적 $x\cdot y=y\cdot x$

• Bilinear mapping이 Positive Definite하다($\Omega$ is "Positive Definite")고 표현되려면,
  If $\forall\mathbf{x}\in\mathbf{V}-\{0\}: \mathbf{\Omega(x,x)>0}$ and $\mathbf{\Omega(0,0)=0}$
  전체 벡터 스페이스에서 0이 제외되었을 때는 Bilinear mapping 값이 0보다 클 때, 그리고 (0,0)의 Bilinear mapping이 0일 때
  (즉, 0을 제외해서는 결과 값이 0이 되면 안되고 0일 경우에는 결과 값이 0이 될 때)

General Inner Product

Definition

Positive definite 하고 Symmetric한 bilinear mapping을 의미한다.

Notation : $\mathbf{<x,y>}$
i.e : 내적

Inner Product Space

$\mathbf(V,<\cdot,\cdot>)$의 페어를 의미한다 <>는 연산을 의미한다.
i.e : $\mathbf{V}$ 가 $\mathbb{R}^n$이고, <>이 dot product라면,
이 때의 Inner Product Space를 'Uclidean vector space'라고 한다.

Inner Product이지만 Dot Product가 아닌 경우

Example

$\mathbf{V}=\mathbb{R^2}$
$\mathbf{<x,y>}\equiv x_1y_1-(x_1y_2+x_2y_1)+2x_2y_2 \in \mathbb{R}$

만약 Dot Product라면 $x_1y_1+x_2y_2$ 형식을 띄게 된다.

1) Bilinear Mapping인가? Yes
$\because \mathbf{V}$ X $\mathbf{V}\rightarrow \mathbb{R}$

2) Symmetric한 B.M 인가? Yes
$\because x_1y_1-(x_1y_2+x_2y_1)+2x_2y_2= y_1x_1-(y_1x_2+y_2x_1)+2y_2x_2 \iff \mathbf{<x,y>=<y,x>}$

3) Positive Definite한 B.M 인가? Yes

$\because \mathbf{<0,0>}=0 \\ \mathbf{<x,x>}$ > 0 $(\mathbf{V}-\{0\})$
$x_1, x_2$를 넣어보고 식을 정리하면 아래 식을 얻을 수 있고 0보다 크다는 것을 알 수 있다.

$(x_1-x_2)^2+x^2 >0$

Derivation of Matrix of Inner Product

Inner product를 매트릭스의 형태로 변형시키는 과정을 알아보자.

inner product : Symmetric & Positive Definite

ordered basis B = $b_1, \cdots, b_n$

basis의 linear combination으로 벡터 스페이스 상의 모든 벡터를 표시할 수 있고

$\psi, \lambda$를 coordinate로 표시할 수 있다. (Coordinate with respect to Basis)
$\mathbf{x^{'}}=[\psi_1,\cdots,\psi_n]^T$
$\mathbf{y^{'}}=[\lambda_1,\cdots,\lambda_n]^T$

inner product의 bilinearity를 사용한다면,

$<x,y>=<\sum_{i=1}^n\psi_i\mathbf{b}_i,\sum_{i=1}^n\lambda_i\mathbf{b}_i>=\sum_{i=1}^n\sum_{i=1}^n\psi_i<\mathbf{b_i,b_j}>\lambda_j = \mathbf{x^{'T}Ay^{'}} \in \mathbb{R}$

$A_{ij}\equiv<b_i,b_j>$

A는 basis에 대해서 i,j에 element를 갖는 스칼라로 구성된 매트릭스가 된다.

basis만 존재한다면, 벡터 스페이스에서 추출한 모든 벡터에 대해 A 매트릭스 하나만으로 inner product를 계산할 수 있게 되는 것이다.

Symmetric & Positive Definite Matrix

$A_{ij} \equiv <\mathbf{b_i,b_j}>$

Properties

• Symmetric Matrix
  $\because A_{ij}=<b_i,b_j>=<b_j,b_i>=A_{ji}$

• Positive Definite Matrix
  $\forall \mathbf{x}-\{0\}: \mathbf{x^TAx}>0$

• Null space of A $(\in \mathbb{R})$는 오직 0으로만 구성되어 있다.
  $\mathbf{x^TAx}>0 \ (\forall \mathbf{x}\neq0)$
  null space는 기본적으로 $A\mathbf{x}=0$성립하는 x의 non trivial solution을 찾아야 한다. x가 0이 아니면 식이 성립을 안하기 때문에
  Null space는 x=0인 trivial solution 외의 값은 존재할 수 없다는 의미.

• $A$의 Diagonal element는 0보다 크다(positive)

Additional(If possible,)

• Positive Semi-definite Matrix
  $\forall \mathbf{x}-\{0\}: \mathbf{x^TAx}\ge0$

Lengths and Distances

• Norm & Inner product
  $\lVert \mathbf{x}\rVert\equiv\sqrt{<\mathbf{x,x}>}$
  Norm = Inner product에 square(루트)를 씌운 것. (length)

• Cauchy-Schwarz Inequality
  $|\mathbf{<x,y>}|\le\lVert\mathbf{x}\rVert\lVert\mathbf{y}\rVert$

• Distance
  두 점 간의 norm 형태