해당 포스트는 computer vision과 관련하여 필요한 선형대수 내용을 정리한 것이다. 모든 내용을 숙지하면 좋지만 해당 시리즈를 읽으며 필요한 부분을 그때마다 찾아 읽어도 좋을 것 같다.
1. Vector Space
어떤 set V가 다음과 같은 vector summation과 scalar multiplication에 대해 닫혀있을 때, set V를 linear space 또는 vector space (over the field R)이라고 한다.
+:V×V→V
⋅:R×V→V
이를 통해 0과 음의 원소의 존재 (+연산을 이용), α(βu)=(αβ)u 와 같은 결합법칙(scalar multiplication을 이용) 등을 유추할 수 있으며, (α+β)v=αv+βv,andα(v+u)=αv+αu 와 같은 분배법칙 또한 두 연산의 조합으로 유추할 수 있다.
이러한 vector space V의 subset인 W가 V와 마찬가지로 vector summation과 scalar multiplication에 대해 닫혀있으며 0을 포함하고 있을때 W를 subspace라고 한다.
2. Matrix
행렬(matrix)는 여러 변수를 다루는 시스템 등을 나타낼 수 있으며, 어떠한 변환을 나타내기도 한다. 여기서는 행렬과 관련된 여러 용어와 성질들을 간단히 소개한다.
A=⎝⎜⎜⎛a11⋮am1⋯⋱⋯a1n⋮amn⎠⎟⎟⎞
Row: (a11⋯a1n),(a21⋯a2n),⋯,(am1⋯amn) 등을 같은 행에 있다고 한다.
Row vector: (a11⋯a1n),(a21⋯a2n),⋯,(am1⋯amn) 등 같은 행에 있는 원소들을 하나의 벡터로 보았을 때, 이들을 행벡터라고 한다.
Inverse matrix(역 행렬):A−1로 표현하며, AA−1=A−1A=I가 되는 행렬
Transpose: 행렬의 행과 열을 서로 바꾼것
AT=⎝⎜⎜⎛a11⋮a1n⋯⋱⋯am1⋮amn⎠⎟⎟⎞
Diagonal matrix: square matrix 행렬의 대각성분, a11,⋯,ann을 제외한 나머지 성분이 0인 행렬
3. Linear Independence and Basis
Vector들의 집합 S={v1,...,vk}⊂V에 의해 span 되는 subspace는 S에 속해있는 vector들로 구성할 수 있는 모든 linear combinations으로 이루어진 subspace를 의미하며, 다음과 같이 표현할 수 있다.
span(S)={v∈V∣v=i=1∑kαivi}
또한 set S가 다음을 만족하면 linearly independent하다고 하며, 이는 S에 속해있는 어떤 vector v를 나머지 다른 vector들의 linear combination으로 나타낼 수 없다는 의미이다.
i=1∑kαivi=0→αi=0∀i
Vector들의 집합 B={v1,...,vn}이 linearly independent하며 space V를 span할 수 있을 때 B를 space V의 basis라고 하며, basis는 linearly independent vector들의 최대 집합이다.
이러한 basis는 아래와 같은 성질을 가지고 있다.(아래에서 B와 B'은 linear space V의 basis들입니다.)
B와 B'은 같은 수의 원소(vector)를 포함하고 있으며, 이 숫자 n을 space V의 dimension(차원)이라고 한다.
V에 속해있는 모든 vector v는 basis vector들(B에 속해있는 vector들)의 linear combination에 의해 unique하게 표현된다.(즉 basis vector들로 해당 vector v를 표현하는 방법은 한가지 뿐입니다.)
B의 모든 vector들은 또다른 basis인 bi′∈B′ 의 linear combination으로 다음과 같이 표현될 수 있다.
bi′=j=1∑nαjibj
위의 세번째 성질에서 나타나는 coefficient αji를 이용하여 basis transform을 나타내는 matrix A를 만들 수 있으며, B′=BA⇔B=B′A−1이라고 할 수 있다.
4. Inner Product
Vector space에서는 다음과 같은 inner product라는 연산을 정의할 수 있다.
⟨⋅,⋅⟩:V×V→R
이러한 inner product는 다음과 같은 세가지 성질을 갖는다.
⟨u,αv+βw⟩=α⟨u,v⟩+β⟨u,w⟩ (linear)
⟨u,v⟩=⟨v,u⟩ (symmetric)
⟨v,v⟩≥0,and⟨v,v⟩=0⇔v=0 (positive definite)
내적을 통해 다음과 같이 vector의 norm(vector의 길이를 계산)과 metric(두 vector간 거리를 계산)을 계산할 수도 있다.
∣⋅∣:V→R,∣v∣=⟨v,v⟩(norm)
d:V×V→R,d(v,w)=∣v−w∣=⟨v−w,v−w⟩(metric)
이와 같이 space V에서 scalar product로 생성되는 metric을 Hilbert space라고 한다.
V=Rn에서 basis가 canonical basis B=In일 경우 아래와 같이 canonical inner product를 정의할 수 있다.(In을 identity matrix(단위행렬)에서 대각성분들이 n인 행렬)
⟨x,y⟩=xTy=i=1∑nxiyj
또한 이로부터 L2-norm(또는 Euclidean norm)을 정의할 수 있다.
∣x∣2=xTx=x12+⋅⋅⋅+xn2
그리고 위에서 정의했던 basis transform A를 이용하여 다른 coordinate에서의 cannonical inner product를 계산할 수 있다.
Canonical basis B에서 B'사이의 basis transform가 A일때, B=B′A−1이라고 할 수 있으며, 새로운 coordinate x', y'의 cannonical inner product는 다음과 같다.
⟨x,y⟩=xTy=(Ax′)T(Ay′)=x′TATAy′≡⟨x′,y′⟩ATA
위의 식에서 두번째 term과 세번째 term 사이에 x=Ax′,y=Ay′의 관계가 존재한다.
이 부분에 대해서는 다음과 같이 이해를 해도 좋을 것 같다.
어떤 point를 basis B′={b1′,b2′}의 coordinate에서 바라본 좌표가 x′=(α′,β′)T이라고 하면, 이 point의 정확한 위치는 α′b1′+β′b2′라고 할 수 있고, 이를 정리하면 다음과 같다.
B′=[b1′b2′]
α′b1′+β′b2′=B′(α′β′)=B′x′
이때, B′=BA이므로 위의 수식은 다음과 같이 정리될 수 있다.
B′x′=BAx′
만약 해당 point를 B의 coordinate에서 보았을 때, 해당 point의 위치는 Bx의 형태로 나타날 것으므로 위의 식에서 Ax′ 부분이 x에 해당함을 알 수 있다.
즉, basis transform matrix가 주어졌을 때, 이를 주어진 vector에 곱함으로써 다른 좌표계에서의 해당 vector의 좌표값을 얻을 수 있다.
추가적으로 내적을 이용하여 두 vector의 orthogonal(직교)를 다음과 같이 정의할 수 있다.
⟨v,w⟩=0
5. Kronecker Product and Stack of a Matrix
두 matrix A∈R(m×n)과 A∈R(k×l)이 주어졌을때 이들의 Kronecker product를 다음과 같이 정의할 수 있다.
A⊗B≡⎝⎜⎜⎛a11B⋮am1B⋯⋱⋯a1nB⋮amnB⎠⎟⎟⎞∈Rmk×nl
또한 주어진 A∈Rm×n의 stack As는 다음과 같이 A에 속해있는 n개의 column vector들을 쌓은 것으로 정의할 수 있다.
As≡⎝⎜⎜⎛a1⋮an⎠⎟⎟⎞∈Rmn
위의 두 notation을 통해 아래와 같이 기존의 식으로 새롭게 표현할 수 있다.
uTAv=(v⊗u)TAs
6. Linear Transformations and Matrices
Linear transform은 두 linear space V, W 사이의 map L:V→W로 정의되며, 다음과 같은 성질을 가지고 있어야 한다.
L(x+y)=L(x)+L(y)∀x,y∈V
L(αx)=αL(x)∀x∈V,α∈R
또한 space V에 적용되는 linear transform L은 V의 basis vector들로 정의 될 수 있으며, canonical basis {e1,⋯,en}의 경우에는 다음과 같다.
L(x)=Ax∀x∈VA=(L(e1),⋯,L(en))∈R(m×n)
이때 실수로 정의되는 모든 m x n matrix들은 M(m,n)으로 표시한다.
7. The Linear Groups GL(n) and SL(n)
여러가지 linear transformation 중 몇몇은 집합 G와 함께 group을 이루기도 한다.
group은 연산 ∘:G×G→G와 set G가 함께 구성하며, 다음과 같은 성질을 가지고 있어야 한다.
closed: g1∘g2∈G∀g1,g2∈G
assoc: (g1∘g2)∘g3=g1∘(g2∘g3)∀g1,g2,g3∈G
neutral: ∃e∈G:e∘g=g∘e=g∀g∈G
invers: ∃g−1∈G:g∘g−1=g−1∘g=e∀g∈G
이러한 정의에 몇가지 특성을 추가하여 다음과 같은 group들을 정의할 수도 있다.
모든 invertible(non-singular) real n x n matrix들은 matrix multiplication과 함께 group을 이루며, 이러한 group을 general linear group(일반선형군) GL(n)이라고 합니다. 즉 GL(n)은 det(a)=0인 모든 A∈M(n)을 포함하고 있다.
이러한 A∈GL(n) 중 det(a) = 1 인 matrix들이 이루고 있는 group을 special linear group(특수선형군) SL(n)이라고 한다.
또한 어떤 group G와 GL(n) 사이에 injective(단사) transformation, R:G→GL(n)이 존재할 경우 G는 matrix representation을 가지고 있다고 하며, 다음과 같은 연산도 가능한다.
R(e)=In×nR(g∘h)=R(g)R(h)∀g,h∈G
이때, map R을 group homomorhphism이라고도 한다.
이러한 matrix representation은 추상적인 group을 분석할 때 이에 해당하는 matrix group의 성질을 살핌으로써 좀 더 직관적인 분석이 가능하도록 한다.
예를 들어 어떤 객체의 회전에 대한 group의 경우 neutral element는 회전이 없는 변환, inverse는 역회전, 여러 matrix의 곱은 회전의 반복 등에 대응한다.
다음은 몇가지 자주 등장하는 group에 대한 설명이다.
7-1. The Affine Group A(n)
Affine transformation L:Rn→Rn은 matrix A∈GL(n)과 vector b∈Rn에 의해 다음과 같이 정의된다.
L(x)=Ax+b
이와 같은 affine transformation의 set을 affine group of dimentsion n이라고 하며, A(n)으로 나타낸다.
위의 정의된 식에 따르면 b=0이 아닌 이상 L은 linear하지 않지만 x∈Rn을 (x1)∈Rn+1과 같이 나타내는 homogeneous coordinates를 사용하면 다음과 같이 linear mapping으로 표현할 수 있다.
L:Rn+1→Rn+1(x1)→(A0b1)(x1)
이때 A와 b로 이루어진 matrix를 affine matrix라고 하며, 이는 GL(n+1)에 속하고, 이러한 affine matrix들의 집합은 GL(n+1)의 subgroup이다.
7-2. The Orthogonal Group O(n)
Matrix A∈M(n)이 다음과 같이 inner product를 보존하는 경우 orthogonal 하다고 한다.
⟨Ax,Ay⟩=⟨x,y⟩∀x,y∈Rn
모든 orthogonal matrix들의 set은 othogonal group O(n)를 이루며, 이는 GL(n)의 subgroup이다.
Othogonal matrix R을 cononical inner product에 적용할 경우 ⟨Rx,Ry⟩=xTRTRy=xTy∀x,y∈Rn가 되어야 하므로 RTR=RRT=I라는 결론이 나오며, 이를 이용하면 O(n)을 다음과 같이 정의할 수도 있다.
O(n)={R∈GL(n)∣RtR=I}
이로부터 det(R)∈{±1}을 만족할 경우 det(RTR)=(det(R))2=det(I)=1을 유추할 수 있고, O(n)의 subgroup이 det(R)∈{±1}를 만족할 경우 이 subgroup을 special orthogonal group SO(n)이라고 하며, SO(n)=O(n)∩SL(n) 이다.(특히 SO(3)은 3차원에서의 모든 회전 변환 matrix의 group이다.)
또한 RtR=I의 는 R의 각 row vector 또는 각 column vector 끼리 orthogonal함을 의미하며, 두 orthogonal matrix A,B의 곱인 AB 또한 orthognal하다.
(AB)TAB=BTATAB=BTIB=BTB=I
그리고 inner product를 보존하는 성질에 따라서 orthogonal matrix에 의한 변환은 벡터의 크기를 보존한다.
∣Rx∣=⟨Rx,Rx⟩=xTx=∣x∣
7-3. The Euclidean Group E(n)
Euclidean transformation은 다음과 같이 orthogonal matrix와 vector로 정의 된다.
L:Rn→Rnx→Rx+T
이러한 transformation의 집합을 Eculidean group E(n)이라고 하며, 이는 affine group A(n)의 subgroup이다.
Eucliean transformation을 homogeneous coordinates로 나타내면 다음과 같다.
E(n)={(R0T1)∣R∈O(n),T∈Rn}
이때 R∈SO(n)이면 special Euclidean group SE(n)이라고 하고, 특히 SE(3)은 rigid-body motion을 나타낸다.
8. Range, Span, Null Space and Kernel, and Rank
A∈Rm×n을 Rn에서 Rm으로의 linear map을 정의하는 matrix라고 할 때, A의 range 또는 span은 A에 의해 변환되어 도달할 수 있는 Rm의 subspace로 정의되며, 즉, matrix A의 range는 A의 column vector들의 span이라고 할 수 있고, 다음과 같이 나타낼 수 있다.
range(A)={y∈Rm∣∃x∈Rn:Ax=y}
Matrix A의 null space 또는 kernel은 A에 의해 0으로 mapping되는 vector들의 집합이며, 즉, A의 row vector들에 orthogonal한 vector의 집합이고, 다음과 같이 나타낼 수 있다.
null(A)≡ker(A)={x∈Rn∣Ax=0}
Matrix A의 rank는 range의 dimension이다.
rank(A)=dim(range(A))
Matrix A∈Rm×n의 rank는 다음과 같은 성질을 갖는다.
차원정리: rank(A)+dim(ker(A))=rank(A)+nullity(A)=n
0≤rank(A)≤min(m,n)
rank(A) = rank(AT)
rank(A)는 A의 row vector(또는 column vector) 중 서로 linearly independent한 vector들의 최대 갯수와 같다.
rank(A)는 A의 minor 중 0이 아닌 것들의 hightest order와 같으며, 여기서 minor of order k는 A의 k x k submatrix의 determinant이다.
A∈Cn×n이 complex matrix라고 할 때, 다음을 만족하는 0이 아닌 vector v∈Cn을 A의 (right) eigenvector라고 하며, λ를 A의 eigenvalue라고 한다.
Av=λvwithλ∈C
이와 비슷하게 vTA=λvT를 만족하는 v를 A의 left eigenvector라고 하기도 하며, matrix A의 모든 eigenvalue들의 집합을 spectrum σ(A)라고 한다.
또한 D가 matrix A의 eigenvalue들을 포함하는 diagonal matrix(대각행렬)이고, V가 각 eigenvalue에 대응하는 eigenvector를 column으로 가지고 있는 matrix라고 할 때, 위의 정의로부터 AV=VD 가 만족함을 유추할 수 있다.
그리고 A∈Rn×n인 square matrix일 경우 다음과 같은 성질을 갖는다.
Av=λv인 λ∈R이 존재할 경우, left-eigenvector η∈Rn 또한 존재한다.(즉, ηTA=ληT를 만족하는 η가 존재하며, σ(A)=σ(AT)이다.)
서로 다른 eigenvalue에 대응하는 eigenvector들은 서로 linearly independent한다.
모든 eigenvector σ(A)는 characteristic polynomial(특성방정식) det(λI−A)=0의 해이며, 따라서 det(A)는 모든 eigenvalue의 곱과 같다.(이때, 중근이 발생하는 경우 해당 eigenvalue는 여러번 곱해주어야 한다.)
어떤 nonsingular matrix P에 대해 B=PAP−1일 경우 σ(B)=σ(A)이다. (닮음변환)
Eigenvalue가 복소수일 경우, 해당 eigenvalue의 conjugate 또한 eigenvalue이다.
Eigenvalue의 합과 행렬의 대각성분의 합(trace)는 같다.
또한 matrix A를 하나의 좌표 변환으로 사용한다면, eigenvector는 A를 통해 좌표변환을 하여도 방향이 바뀌지 않고 크기만 변하는(스칼라 배만 되는) vector, eigentvalue는 vector의 크기 변화율로 이해할 수도 있다.
11. Symmetric Matrices
어떤 matrix S∈Rn×n이 ST=S를 만족할 경우 matrix S를 symmetric하다고 한다.
이때 symmetric matrix S가 xTSx≥0라면 이를 positive semi-definite라고 하고(S≥0라고 표시), xTSx>0if∀x=0이면 positive definte(S>0라고 표시)라고 한다.
S∈Rn×n가 real symmetric matrix라고 하면 다음의 성질을 갖는다.
S의 모든 eigenvalue들은 실수이다.
서로 다른 eigenvalue에 대응하는 eigenvector들은 서로 othogonal한다.
언제나 Rn의 basis 형태의 n개의 orthonormal한 eigenvector들의 존재하며, V=(v1,⋯,vn)∈O(n)을 eigenvector들이 이루는 orthogonal matrix, Λ=diag(λ1,⋯,λn)을 eigenvalue들이 이루는 diagonal matrix라고 할때, S=VΛVT이다.
모든 eigenvalue가 positive(nonnegative)라면 S는 positive (semi-)definite이다.
S가 positive semi-definite이고, λ1,λn이 각각 최대, 최소의 eigenvalue라면, λ1=max∣x∣=1⟨x,Sx⟩λn=min∣x∣=1⟨x,Sx⟩
12. Norms of Matrices
어떤 matrix A∈Rm×n의 norm을 정의하는 방법은 여러가지가 있지만 대표적인 방법으로 2가지 정도를 생각해 볼 수 있다.
첫번째로 induced 2-norm의 경우 다음과 같이 정의된다.
∥A∥2≡∣x∣2=1max∣Ax∣2=∣x∣2=1max⟨x,ATAx⟩
다음으로 Frobenius norm은 다음과 같이 정의된다.
∥A∥f≡i,j∑Aij2=trace(ATA)
일반적으로는 위의 두 norm이 서로 같지 않음에 주의하여야 한다.
또한 ATA는 symmetric, positive semi-definite하기 때문에 ATA=Vdiag(σ12,⋯,σn2)VT,σ12≥σn2≥0이며, 다음을 유추할 수 있다.
∥A∥2=σ1∥A∥f=trace(ATA)=σ12+⋯+σn2
13. Skew-symmetric Matrices
어떤 matrix A∈Rn×n이 AT=−A를 만족하는 경우, A를 skew-symmetric 또는 anti-symmetric하다고 한다.
만약 A가 real skew-symmetric일 때, 다음과 같은 성질을 갖는다.
A의 모든 eigenvalue은은 0이거나 복소수 성분만 가지고 있는 수(purely imaginary)이다.
A=VΛVT를 만족하는 orthogonal matrix V가 존재하며, 이때 Λ는 block-diagonal matrix이고 Λ=diag(A1,⋯,Am,0,⋯,0), 각 Ai는 다음과 같은 형태의 skew-symmetric matrix이다.
Ai=(0−aiai0)∈R2×2i=1,⋯,m
특히, 모든 skew-symmetric matrix의 rank는 짝수이다.
Computer vision 분야에서 skew-symmetric matrix는 vector u∈R3의 hat operator로 다음과 같이 주어진다.
u^=⎝⎜⎛0u3−u2−u30u1u2−u10⎠⎟⎞∈R3×3
이러한 hat operator는 R3 vector의 space에서 R3×3의 skew-symmetric matrix의 space로의 linear operator이며, 이를 이용하여 다음과 같이 vector의 cross product, 외적을 나타낼 수 있다.
u^v=(uTv^)T=u×v
위의 경우 u=0일 때, rank(u^)=2이며, u^u=uTu^=0이므로 u^의 null space는 u에 의해 span된다.
또한 다음의 성질을 갖는다.
M이 임의의 3×3행렬일 경우 (Mx)×(My)=M∗(x×y)이며, 이는 MxM=M∗x^로 쓸 수 있음 (M∗은 여인수행렬)