[DeepLearningBook] Chapter 2 : Linear Algebra

이 책 내용을 정리한 포스트입니다.

https://www.deeplearningbook.org/,

Ian Goodfellow and Yoshua Bengio and Aaron Courville, An MIT Press book

책 전체 목차

contents



Scalars, Vectors, Matrices and Tensors

  • Scalars: 선형대수에서 다루는 다른 객체들은 여러개의 숫자들의 array로 이루어져있지만, 스칼라는 single number다. 소문자 이탤릭체로 표기한다. 사용할 때는 어떤 종류의 수인지 정해주어야 한다. 예를들면, “Let $s \in \mathbb{R}$ be the slope of the line”은 실수 스칼라 변수를 정의하는 것이고, “Let $n \in \mathbb{N}$ be the number of units”은 자연수 스칼라 변수를 정의하는 것이다.
  • Vectors: 벡터는 숫자들의 array다. 소문자 볼드체로 표기한다. 벡터의 인자들은 문자와 아래첨자 인덱스를 이용해 나타낸다. 의 첫번째 인자는 , 두번째 인자는 … 이런 식으로 표기한다. 벡터를 공간상의 하나의 점이라고 생각하면, 각각의 인자는 각 차원축에서의 값을 나타낸다. 간혹 아래첨자 인덱스를 이용해서 벡터를 다룰 때가 있다. 특정 인덱스의 인자만 뽑고 싶을 때는 으로 정의하고 를 사용하면 , , 을 의미한다. 혹은 특정 인덱스를 제외한 벡터인자들을 뽑고 싶을 때는 -기호를 이용하는데, $\boldsymbol{x}_{-1}$은 벡터 $\boldsymbol{x}$ 에서 첫번째 인자를 제외한 모든 인자를 의미하고, , ,을 제외한 인자들을 의미한다.
  • Matrices: 행렬은 숫자들의 2-D array다. 인자들은 2개의 아래첨자 인덱스를 갖는다. 대문자 볼드체로 표기한다. m행 n열을 갖는 행렬은 으로 표기한다. 인자를 나타낼 때는 볼드체가 아닌 으로 표기하는데, $i$행의 모든 열을 표기할 때는 “:”을 이용하여 으로 표기한다. $f(\boldsymbol{A})_{i,j}$는 행렬 $\boldsymbol{A}$에 함수 $f$를 적용하고난 후의 $(i,j)$인덱스의 인자를 의미한다.
  • Tensors: 일반적으로는 grid에 정렬되어있는 숫자들의 array를 텐서라고 한다. 행렬보다 높은 차원의 인덱스를 가진 array를 포함하는 개념이다. 텐서 “A”는 $\mathbf{A}$로 표기하며, 텐서의 $(i,j,k)$ 인덱스의 인자는 $A_{i,j,k}$로 표기한다.

중요한 행렬 연산중 하나는 transpose(전치)다. transpose란, main diagonal(주대각선)을 중심으로 뒤집는 것이다. 행과 열의 인덱스가 뒤바뀐다. DLB-02-01

벡터도 한 열짜리 행렬로 볼 수 있다. 벡터의 transpose는 한 행의 행렬이 된다. 열벡터를 글로 표기할때는 transpose를 이용하여 $\boldsymbol{x} = \left[ x_1,x_2,x_3 \right]^{\top}$ 이렇게 표기한다. 반면 스칼라는 하나의 숫자이기 때문에 transpose를 취한것과 취하지 않은것의 차이가 없다.

행렬간의 합 : $\boldsymbol{C} = \boldsymbol{A} + \boldsymbol{B}$, $C_{i,j} = A_{i,j}+B_{i,j}$

스칼라 $a,c$와 행렬 $\boldsymbol{B}$의 합과 곱 : $\boldsymbol{D} = a \cdot \boldsymbol{B}$ + c, $D_{i,j} = a \cdot B_{i,j}+c$

딥러닝에서는 일반적인 표기와는 살짝 다른걸 사용하기도 한다. 예를 들면 행렬 $\boldsymbol{A}$ 와 벡터 $\boldsymbol{b}$의 합이다. 이 때 벡터 $\boldsymbol{b}$는 행렬 $\boldsymbol{A}$의 모든 행에 더해지는데, 이를 broadcasting이라 한다.

Multiplying Matrices and Vectors

두 행렬을 곱하는 matrix product 행렬곱에서, $\boldsymbol{A}$와 $\boldsymbol{B}$를 곱할 때,$\boldsymbol{A}$의 열과 $\boldsymbol{B}$의 행 수가 같아야한다. $\boldsymbol{A}$의 shape이 $m \times n$이고 $\boldsymbol{B}$의 shape이 $n \times p$ 일때 두 행렬의 행렬곱 $\boldsymbol{C}$의 shape은 $m \times p$가 된다.

두 행렬을 곱할 때, 행렬곱이 아니라 인자들끼리의 곱을 할 수 있는데, 이를 elelment-wise product 또는 Hadamard product라고 하고, $\boldsymbol{A}\odot\boldsymbol{B}$로 표기한다.

두 벡터간 dot product를 할 때는 $\boldsymbol{x}^{\top}\boldsymbol{y}$으로 표기한다. 또한 벡터간 dot product는 교환법칙 $\boldsymbol{x}^{\top}\boldsymbol{y} = \boldsymbol{y}^{\top}\boldsymbol{x}$ 이 성립한다.

행렬곱은 교환법칙이 항상 성립하진 않고, 다음과 같은 성질을 지닌다.

Identity and Inverse Matrices

Identity matrix는 어떠한 벡터에 곱해도 그 벡터를 변화시키지 않는 행렬이다. 주대각성분은 1이고 나머지 성분은 모두 0이다. $\boldsymbol{I}_n \in \mathbb{R}^{n \times n}$이고, 이다. 행렬 $\boldsymbol{A}$에 역행렬 $\boldsymbol{A^{-1}}$을 곱하면 $\boldsymbol{I}_n$이다. ($\boldsymbol{A}^{-1}\boldsymbol{A} = \boldsymbol{I}_n$) 그러나 항상 역행렬이 존재하는 것은 아니다.

Linear Dependence and Span

Matrix equation to Vector equation

Matrix equation을 vector equation으로 쓸 수 있다. Vector equation을 통해 방정식 해의 성격에 대해 알 수 있다.

Span

주어진 벡터들의 선형결합으로 생성할 수 있는 모든 벡터의 집합. 즉, 벡터 스페이스가 된다. DLB-02-02 Edwith 인공지능을 위한 선형대수 슬라이드

위 그림에서 표시된 영역은 주어진 벡터 의 선형결합 으로 생성할 수 있는 영역 span이다. 주어진 벡터 갯수(방정식 갯수)가 많으면 span이 넓게 생성된다.

만약 가 주어진 벡터들의 선형결합으로 생성된 span에 속한다면 해가 존재하지만, 속하지 않는다면 해가 존재하지 않는다. 즉, Span일때만 해가 존재한다.

해가 존재할 때, 하나만 존재할지 여러개 존재할지는 선형 독립과 연관되어있다.

  • 해가 여러개 존재한다면 는 linear dependent하다. 만약 $a_3 \in $ Span라면, (로 $a_3$를 만들어낼 수 있다면) $a_3$는 어떤 값$(x_3)$이 곱해지든 상관 없으므로 해가 여러개 존재하는 것이다.
  • 해가 하나만 존재한다면 는 linear independent하다.
  • 해가 존재할 필요충분 조건은, 공간을 Span으로 만들어내기 위한 $m$개의 vector가 linear independent해야 한다는 것이다.

$\boldsymbol{Ax} = \boldsymbol{b}$ 을 풀기위해 역행렬을 사용한다면, $\boldsymbol{b}$에 대해서 하나 이하의 해가 있어야 한다. $\boldsymbol{A}$행렬은 $m \times m$ 정사각 행렬이어야하고, 각 열벡터는 서로 linearly independent 해야한다. linearly dependent해서 역행렬을 구할 수 없는 행렬을 singular matrix라 한다. singular matrix는 역행렬이 아닌 다른 방법을 통해 해를 구하여야 한다.

Norms

벡터의 크기를 표현하기위해 Norm이란 함수를 사용한다. 수식적으로 $L^p$ norm은 다음과 같이 주어진다.

Norm은 벡터를 비음수 값으로 맵핑시켜주는 함수다.직관적으로, vector $\boldsymbol{x}$의 norm은 원점으로부터 point $\boldsymbol{x}$까지의 거리라고 볼 수 있다. 포괄적으로 Norm은 다음과 같은 특성을 만족하는 모든 함수다.

  • $f(\boldsymbol{x}) = 0 \Rightarrow \boldsymbol{x} = \boldsymbol{0}$
    • 원점으로부터 거리가 0인 (크기가 0인) 벡터는 영벡터다.
  • $f(\boldsymbol{x}+\boldsymbol{y}) \leq f(\boldsymbol{x}) + f(\boldsymbol{y})$ (the triangle inequality)
    • 합벡터의 원점으로부터의 거리(크기)는 각각 크기의 합보다 작거나 같다.
  • $\forall \alpha \in \mathbb{R}, f(\alpha \boldsymbol{x}) = \left\vert \alpha \right\vert f(\boldsymbol{x})$
    • 벡터에 실수배를 하면 크기도 실수배 된다.

$L^2$ norm

$L^2$ norm은 Euclidean norm으로도 불리는데, 원점으로부터 벡터 포인트까지의 Euclidean distance를 나타낸다. 머신러닝에서는 흔히 아래첨자 2를 생략하고 $\lVert \boldsymbol{x} \rVert$ 로 표기한다.

$L^2$ norm보다는 squared $L^2$ norm ($ = \boldsymbol{x}^{\top}\boldsymbol{x}$)이 주로 쓰인다. 루트 안에 들어가있는 것보다는 꺼내져있는 것이 수학적으로 연산하기 편리하기 때문이다. 예를 들어, squared $L^2$ norm은 미분을 하게 되면 각각의 인자에 대해 미분을 할 수 있는데, $L^2$ norm은 전체에 대해 미분을 해야한다.

$L^1$ norm

때로는 zero작지만 nonzero인 값을 구별하기 위해 $L^1$ norm을 사용한다. $L^1$ norm은 벡터 인자들의 값이 변한 만큼 변한다. 간혹 어떤 저자는 nonzero인 인자의 수를 세기 위해 $L^0$ norm이라고 부르며 사용하는데, 이는 엄밀히 말하면 norm이 아니다. 벡터에 실수배를 했을 때 크기가 실수배만큼 증가하지 않기 때문이다. 따라서 nonzero인자의 수를 세기 위해 $L^1$ norm 을 사용한다.

$L^{\infty}$ norm

머신러닝에서 자주 쓰이는 norm에는 max norm이라고 불리우는 $L^{\infty}$ norm이 있다. 벡터에서 가장 큰 절댓값을 norm으로 구한다.

Frobenius norm (size of matrix)

벡터의 크기가 아니라 행렬의 크기를 구하는 경우도 있다. 이는 벡터의 $L^2$ norm과 유사하게 구할 수 있다.

Dot product

두 벡터의 dot product도 norm으로 표현할 수 있다.

$\theta$는 $\boldsymbol{x}$ 와 $\boldsymbol{y}$ 사이의 각이다.

Special Kinds of Matrices and Vectors

몇몇 특이한 행렬과 벡터들은 유용하게 쓰인다.

Diagonal $\boldsymbol{D}$

대각행렬은 주대각 성분 ($i=j$)을 제외하고는 모든 인자의 값이 0인 행렬이다. identity matrix도 주대각 성분의 값이 1인 대각행렬의 일종이다. 표기할 때는 $diag(\boldsymbol{v})$로 하며, $\boldsymbol{v}$ 는 주대각 성분들을 나타낸 벡터다. 대각행렬과 벡터 $\boldsymbol{x}$의 곱인 $diag(\boldsymbol{v})\boldsymbol{x}$는 벡터 $\boldsymbol{v}$와 벡터 $\boldsymbol{x}$의 element-wise 곱 $\boldsymbol{v} \odot \boldsymbol{x}$이다.

대각행렬의 역행렬 또한 유용하게 사용된다. $diag(\boldsymbol{v})^{-1} = diag(\left[ 1/v_1,…,1/v_n \right]^{\top})$이다.

대각행렬이 정사각행렬이 아닌 경우, 벡터 $\boldsymbol{x}$와 곱하면 scaling과 함께 벡터의 인자를 버리거나 zero값들을 concat해줄 수 있다.

Symmetric

대칭행렬은 주대각 성분을 기준으로 대칭이므로 transpose한것과 원래의 행렬이 같다.

대칭행렬은 주로 인자들의 인덱스의 순서에 상관이 없을 때 사용된다. 예를 들면, distance는 $i$와 $j$간의 distance와 $j$와 $i$간의 distance가 같기 때문에 대칭행렬로 나타낼 수 있다.

Unit vector

단위벡터는 크기(norm)가 1인 벡터다.

Orthogonal

벡터 $\boldsymbol{x}$와 $\boldsymbol{y}$가 $\boldsymbol{x}^{\top}\boldsymbol{y}$이면 서로 orthogonal(직교)한다. 벡터가 orthogonal 하면서 unit norm을 가지면(크기가 1이면) orthonormal이라고 표현한다.

Orthogonal matrix는 행들이 서로 orthonormal하고 열들이 서로 orthonormal한 정사각 행렬이다.

역행렬을 단지 transpose로 구할 수 있다는 연산상의 이점으로 많이 사용된다. 행렬의 행과 열들이 orthogonal 하기만 한지, orthonormal하기까지 한지 주의해서 정의하고 사용해야 한다. orthogonal 하기만한 행렬은 따로 이름이 없다.

Eigendecomposition

많은 수학적인 객체(스칼라, 벡터, 행렬, 텐서 등)들은 그것들을 보편적인 성분으로 쪼개서 볼 때 그 특성에 대한 이해를 돕기도 한다. 예를 들면 12 라는 숫자는 $12 = 2 \times 2 \times 3$ 으로 소인수분해로 쪼개서 볼때 이 숫자에 대한 (5로는 나누어지지 않고 3으로는 나누어진다는 등의) 성질을 알 수 있다.
소인수 분해로 숫자를 쪼개어 보듯이 행렬 또한 쪼개어 봄으로써 행렬의 성질을 파악하고 이용할 수 있는데, 이 중 매우 흔히 사용되는 방법이 eigen decomposition이다. eigen decomposition에서는 행렬을 eigenvector와 eigenvalue로 분해한다. square matrix $\boldsymbol{A}$ 의 eigenvector는 아래와같이 정의된다.

여기서 $\boldsymbol{v}$는 nonzero vector이고, 행렬 $\boldsymbol{A}$와 곱해지면 스케일만 바뀔 뿐이다. 이때 스칼라 $\lambda$를 이 eigenvector에 대응되는 eigenvalue라고 한다. (left eigenvector으로 $\boldsymbol{v}^\top\boldsymbol{A} = \lambda\boldsymbol{v}^\top$ 을 사용할 수도 있지만 주로 right eigenvector를 사용한다.) 만약 $\boldsymbol{A}$ 가 $n$개의 선형 독립적인 eigenvector 과 그에 대응되는 eigenvalue 를 갖고있다면, 우리는 이를 아래와 같이 eigendecomposition으로 표현할 수 있다.

이때 $\boldsymbol{V}=\left[\boldsymbol{v}^{(1)},…,\boldsymbol{v}^{(n)}\right]$이고, $\boldsymbol{\lambda} = \left[\lambda_1,…,\lambda_n \right]$으로, 각각 concat한 것이다. 우리는 이를 이용하여 아래처럼 행렬의 성질을 분석할 수 있다.

DLB-02-03

모든 행렬이 eigenvalue와 eigenvector로 분해되는 것은 아니다. 어떤 경우엔 decomposition결과가 복소수를 포함하고 있을 수 있다. 그러나 이 책에서는 실수로만 분해되는 real symmetric matrix만 다룬다.

$\boldsymbol{Q}$는 eigenvector 들의 concat matrix이면서, orthogonal matrix다. 따라서 위의 그림처럼 eigenvalue $\lambda_i$는 $\boldsymbol{v}^{(i)}$방향으로의 scaling이라고 볼 수 있다. real symmetric matrix $\boldsymbol{A}$가 항상 eigendecompositon이 가능하다고 해도, 이게 항상 unique하다는 보장은 없다. 같은 eigenvalue에 둘 이상의 eigenvector가 존재할 수 있다. convention에 따라 $\boldsymbol{\Lambda}$는 내림차순으로 정렬하여 표기한다. 따라서 eigenvalue가 unique한 경우에 eigendecomposition 또한 unique하다.

eigendecomposition은 행렬에 대한 유용한 정보들을 제공해준다. 행렬이 singular하다는 것과 eigenvalues가 하나라도 0인 것은 서로 필요충분조건이다. real symmetric matrix의 eigendecomposition은 $f(\boldsymbol{x}) = \boldsymbol{x}^\top\boldsymbol{Ax}$ 형태의 quadratic 수식을 $\Vert\boldsymbol{x}\Vert_2=1$ 에 대해 최적화 할 때도 사용된다. $\boldsymbol{x}$ 가 $\boldsymbol{A}$의 eigenvector라면 함수 $f$ 값은 eigenvalue에 대응하는 값을 갖게 된다. $f$의 최솟값은 eigenvalue중 최솟값이고, $f$의 최댓값은 eigenvalue중 최댓값이다.

eigenvalue 가 모두 양수인 matrix는 positive definite라고 한다. eigenvalue 가 모두 0 이상인 matrix는 positive semidefinite라고 한다. 마찬가지로, eigenvalue 가 모두 음수인 matrix는 negative definite라고 한다. eigenvalue 가 모두 0 이하인 matrix는 negative semidefinite라고 한다.

positive semidefinite matrix는 $\forall \boldsymbol{x}, \boldsymbol{x}^\top\boldsymbol{Ax}\geq 0$을 보장하고, positive definite matrix는 여기에 $\boldsymbol{x}^\top\boldsymbol{Ax}=0 \Rightarrow \boldsymbol{x}=0$ 또한 보장한다.

Singular Value Decomposition

singular value decomposition(SVD)란 행렬을 singular vectorssingular values로 분해하는 것을 말한다. SVD는 matrix에 대해 위에서 살펴본 eigendecomposition 와 같은 정보를 제공해준다. 그러나 SVD가 더 일반적인 응용성이 좋다. 모든 real matrix가 SVD가 가능하지만, eigendecomposition은 꼭 그런것은 아니다. 예를 들어, 행렬이 정사각행렬이 아니라면 eigendecomposition은 불가능하지만 SVD는 가능하다. $\boldsymbol{A} = \boldsymbol{V}\text{diag}(\boldsymbol{\lambda})\boldsymbol{V}^{-1}$ 로 분해했던 eigendecomposition과 유사하지만, SVD는 아래와 같이 세가지 matrix들의 곱으로 표현한다.

$\boldsymbol{A}$ 가 $m\times n$ 행렬이라 했을 때, $\boldsymbol{U}$는 $m \times m$ 행렬이고, $\boldsymbol{D}$ 는 $m \times n$ 행렬, $\boldsymbol{V}$는 $n \times n$ 행렬이다. 세가지 행렬은 각각 특별한 구조로 정의되어 있다. $\boldsymbol{U}$와 $\boldsymbol{V}$는 orthogonal matrix로 정의된다. $\boldsymbol{D}$는 diagonal matrix 대각행렬로 정의되며, 꼭 정사각행렬일 필요는 없다. $\boldsymbol{D}$는 matrix $\boldsymbol{A}$의 singular value라고 한다. $\boldsymbol{U} = \boldsymbol{AA}^\top$는 left-singular vector이고, $\boldsymbol{V}=\boldsymbol{A}^\top\boldsymbol{A}$는 right-singular vector 이다. $\boldsymbol{A}$의 nonzero singular value는 $\boldsymbol{A}^\top\boldsymbol{A}$ 또는 $\boldsymbol{A}\boldsymbol{A}^\top$의 eigenvalue 의 square root와 같다. SVD의 가장 유용한 특징은 이제 살펴볼 내용처럼 nonsquare matrix에도 역행렬을 구하는데 이용할 수 있다는 것이다.

The Moore-Penrose Pseudoinverse

역행렬은 정사각행렬이 아닌 행렬에 대해서는 정의되지 않는다. 아래와 같은 선형방정식을 풀기 위해서는 left-inverse $\boldsymbol{B}$를 곱하면 된다.

그러나 문제에 따라서 $\boldsymbol{A}$와 $\boldsymbol{B}$사이에 unique한 맵핑이 되지 않을 수 있다. $\boldsymbol{A}$가 길쭉한 행렬이면 방정식의 해가 존재하지 않을 수도 있다. $\boldsymbol{A}$가 넓쩍하다면 해가 여러개일 수 있다.

아래와같이 정의되는 Moore-Penrose pseudoinverse는 이런 상황에서 도움이 된다.

pseudoinverse는 실제 연산할 때는 위의 수식보다는 아래 식을 이용한다.

$\boldsymbol{U,D,V}$는 $\boldsymbol{A}$의 SVD에서 나온 식이고, pseudoinverse $\boldsymbol{D}^+$는 $\boldsymbol{D}$에서 nonzero인 인자를 역수를 취한 다음 transpose를 취한 행렬이다.

$\boldsymbol{A}$ 가 열이 행보다 많은 행렬이라면 둘 이상의 solution중 pseudoinverse를 이용한 solution이 minimal Euclidean norm $\Vert\boldsymbol{x}\Vert_2$을 가진 $\boldsymbol{x} = \boldsymbol{A}^+\boldsymbol{y}$다. $\boldsymbol{A}$ 가 행이 열보다 많은 행렬이라면 solution이 없을 수도 있다. 이 경우 psuedoinverse를 사용한 solution은 Euclidean norm $\Vert\boldsymbol{Ax} - \boldsymbol{y}\Vert_2$ 가 가장 작은, $\boldsymbol{y}$에 가장 가까운 solution이 된다.

The Trace Operator

trace operator는 행렬의 대각성분을 모두 더하는 연산자다.

trace operator는 다양한 이유에서 유용하다. 표기하기 난해한 연산들을 trace operator와 행렬들의 곱으로 표현할 수 있다. 예를 들면 행렬의 Frobenius norm은 아래와 같이 표기할 수 있다.

trace operator는 또한 유용한 identity가 많아 수식을 조작하기 편하다. 예를 들면 transpose operator에 대해 invariant한 특성이다.

여러 square matrix들의 곱의 trace는 맨 끝의 행렬을 앞으로 옮겨도 같은 결과가 나온다.

이를 일반화시켜 정리하면,

이러한 특성은 행렬의 형태가 달라도 성립한다. 예를 들어 $\boldsymbol{A} \in \mathbb{R}^{m\times n}$ 이고, $\boldsymbol{B} \in \mathbb{R}^{n\times m}$ 이어도 아래와 같은 식이 성립한다. ($\boldsymbol{AB} \in \mathbb{R}^{m\times m}$ , $\boldsymbol{BA} \in \mathbb{R}^{n\times n}$ )

또다른 성질은, 스칼라는 그 자체가 trace라는 것이다. 즉, $a = \text{Tr}(a)$이다.

The Determinant

정사각행렬의 판별식 determinant 는 $\text{det}(\boldsymbol{A})$ 로 표기한다. 이는 행렬을 입력으로 받아 실수의 스칼라 값을 출력하는 일종의 함수다. determinant는 모든 eigenvalue의 곱과 같다. determinant의 절댓값은 행렬이 공간을 얼마나 늘리고 축소시키는지에 대한 지표가 될 수 있다. 예를 들어 determinant가 0 이면, 공간은 한차원 이상 축소될 수 있다. 만약 determinant가 1이면 transformation은 공간을 유지시킨다.

Example: Principal Components Analysis

간단한 머신러닝 알고리즘의 일종인 principal components analysis(PCA)는 선형대수의 기초적인 지식만으로도 유도해낼 수 있다.

$m$개의 $\mathbb{R}^n$ 차원의 데이터 포인트 가 있다고 하자. 이 때 lossy compression을 하려고 한다. lossy compression란, 원본의 데이터 정보를 약간 손실하더라도 차원을 줄이는 것을 의미한다. 이때 손실되는 정보를 최소로 하는 방법에 대해 알아보자.

각각의 포인트 $\boldsymbol{x}^{(i)} \in \mathbb{R}^n$을 저차원의 벡터 $\boldsymbol{c}^{(i)} \in \mathbb{R}^l$에 맵핑시킨다. 이때 $l$은 $n$보다 작다. 이렇게 맵핑시키는 함수 $f(\boldsymbol{x}) = c$ 가 있다고 가정하면, 복원시키는 (decoding) 함수는 $\boldsymbol{x}\approx g(f(\boldsymbol{x}))$로 주어진다.

PCA는 decoding 함수로 정의된다. 구체적으로 여기서는 벡터를 원래 차원으로 되돌리기 위해 행렬곱으로써 정의한다. $g(\boldsymbol{c}) = \boldsymbol{Dc}$ 라고 하자. 이 때, $\boldsymbol{D} \in \mathbb{R}^{n\times l}$ 이다. 최적의 decoder를 찾는 것은 어려울 수 있으나, PCA에서는 $\boldsymbol{D}$의 모든 열이 서로 orthogonal하다는 constraint를 줘서 문제를 쉽게 만든다. ($l=n$이 아닌 이상 $\boldsymbol{D}$를 orthogonal matrix라고 부르지는 않는다.) 또한 unique한 solution을 만들기 위해 $\boldsymbol{D}$의 열들은 unit norm을 갖는다고 constraint를 둔다.

이제 문제를 풀기 위해, 우선 optimal poiunt $\boldsymbol{c}^\ast$를 어떻게 정의할 것인지 정해야 한다. 여기서는 복원했을때 원래의 데이터와 거리가 가장 가까운 것을 optima로 둔다. 거리를 $L^2$ norm을 이용하면 아래와 같이 정의된다.

$L^2$ norm의 정의를 이용해서 정리하면,

$\boldsymbol{x}^\top g(\boldsymbol{c})$는 스칼라값으로, transpose해도 같다. 위 식을 $\boldsymbol{c}$에 대한 항들로 정리하면 아래와 같다.

$g(\boldsymbol{c})$를 위에서 정한 행렬곱으로 다시 바꾸고 $\boldsymbol{D}$가 unit norm을 갖도록 constraint를 줬던 것을 적용하면 아래와 같이 전개된다.

4장에서 다루듯, 최적값에서의 미분값은 0 인 것을 이용하여 아래와 같이 전개한다.

이처럼 단순히 행렬곱을 이용하여 $\boldsymbol{x}$를 인코딩할 수 있다. 인코딩 함수는 아래와 같다.

PCA의 복원 연산은 아래와 같다.

이제는 인코딩 행렬 $\boldsymbol{D}$를 구해야 한다. 이를 위해 원본 데이터와 복원된 데이터 사이의 $L^2$ norm을 최소화 하는 방법을 사용한다. $\boldsymbol{D}$는 모든 데이터 포인트에 대해 동일하게 적용되기 때문에, 모든 차원과 모든 포인트에서 Frobenius norm을 최소화한다.

우선 $l=1$ 이라 놓고 알고리즘을 전개해보자. 이 경우 $\boldsymbol{D}=\boldsymbol{d}$로, single vector가 된다. 이제 single vector와 scalar의 transpose를 이용하여 위 식을 다시 전개하면, 아래와 같다.

여기서 $\boldsymbol{x}$ 대신 모든 데이터를 쌓은 $\boldsymbol{X}\in \mathbb{R}^{m\times n}$을 사용하면 summation을 쓰지 않고 아래와 같이 전개된다.

위에서 언급했던 trace operator 의 유용한 성질을 이용하여 전개하면 아래와 같다.

이를 쭉 풀어서 정리한 후 $\boldsymbol{d}$에 무관한 항을 지우고 trace operator가 뒷행렬을 앞으로 두어도 같은 값이라는 성질을 이용하면 아래와 같이 전개된다.

$\boldsymbol{d}^\top\boldsymbol{d}=1$로 두었던 constraint를 적용하면,

이것의 최적화는 eigendecomposition으로 풀 수 있다. $\boldsymbol{d}$를 $\boldsymbol{X}^\top\boldsymbol{X}$의 최대 eigenvalue를 갖는 eigenvector로 사용한다면 풀릴 것이다. 이 유도식은 $l=1$일때를 다룬 것이고, first principal component를 다룬 것이다. single vector $\boldsymbol{d}$ 대신 원래대로 matrix $\boldsymbol{D}$를 사용했을 때, 가장 큰 eigenvlaue에 해당한다. 직접 풀어서 증명해보길 권장한다.