mxn 크기의 2차원 배열로 주어지는 영상은 M(=mxn) 크기의 벡터 하나로 바꿀 수 있다. 만일 영상이 N개가 있다면, 전체 데이터의 크기는 MxN이다.
MxN 데이터에 대해 기저를 찾아보자.
일반적으로 MxN 벡터 집합에 대한 KL 기저(basis)를 계산하는 것은 O(MN^2)의 연산과 O(MN)의 메모리를 요구한다. 이러한 계산량은 데이터의 실시간 처리를 위해서는 상당히 크다.
KL 변환: N개의 (images) 벡터 (Ai),i=1...N가 주어질 때, K (K<N)개의 직교(orthonomal) 기저벡터의 집합을 찾는 것이다. 단, 기저 Uj에 의해 확장(span)된 공간에 사영(projection)된 원 데이터의 좌표로 재생한 데이터는 원 데이터를 잘 근사해야 한다.
행렬 A는 크기가 MxN (M>>N)이다.
A의 특이값 분해(SVD: Singular Value Decomposition)를 이용하여 기저벡터를 얻는다. 이때, KL 기저는 (특이값이 0이 되지 않는) K개의 왼쪽 특이 벡터(U의 첫번째 K개의 열)이다.
R-SVM[1]은 SVD를 수정한 것으로 M>>N일 때 효과적이다:
(1) A = QR: qr분해를 통해 (열)직교(column-orthonormal) Q(MxN) 행렬, 상 삼각 행렬 R(NxN)을 얻는다. 계산량은 4MN^2이다.
(2) R = Ua.Da.Va': 표준 SVD알고리즘으로 R을 특이값 분해 한다. 계산량은 O(N^3)이다.
(3) U = Q.Ua, 계산량은 2MN^2이다.
정리해서 다시 쓰면,
A = QR = Q(Ua.Da.Va') = (Q.Ua).Da.Va' = UDV'
이다. 따라서, U = Q.Ua이다.
계산량을 살펴보면 (1)과 (3)이 6MN^2이고, (2)가 N^3이다. 즉 (1),(3)번이 좌우하고 (2)는 무시할 만하다.
(예1) 간단하게 테스트해 보자.
>> clear; clc;
>> A = rand(10,9); % 행렬 A를 10x9크기로 생성
>> [u0,d0,v0] = svd(A); % 행렬의 특이값 분해
>>
>> [q,r] = qr(A); % A 행렬의 QR 분해
>> [u1,d1,v1] = svd(r); % r의 특이값 분해
>> q*u1 % u0와 같음, 즉, u0.d0.v0' = (q*u1).d1.v1'이다.
>> d1 % d0와 같음
(1) A = QR: qr분해를 통해 (열)직교(column-orthonormal) Q(MxN) 행렬, 상 삼각 행렬 R(NxN)을 얻는다. 계산량은 4MN^2이다.
(2) R = Ua.Da.Va': 표준 SVD알고리즘으로 R을 특이값 분해 한다. 계산량은 O(N^3)이다.
(3) U = Q.Ua, 계산량은 2MN^2이다.
정리해서 다시 쓰면,
A = QR = Q(Ua.Da.Va') = (Q.Ua).Da.Va' = UDV'
이다. 따라서, U = Q.Ua이다.
계산량을 살펴보면 (1)과 (3)이 6MN^2이고, (2)가 N^3이다. 즉 (1),(3)번이 좌우하고 (2)는 무시할 만하다.
(예1) 간단하게 테스트해 보자.
>> clear; clc;
>> A = rand(10,9); % 행렬 A를 10x9크기로 생성
>> [u0,d0,v0] = svd(A); % 행렬의 특이값 분해
>>
>> [q,r] = qr(A); % A 행렬의 QR 분해
>> [u1,d1,v1] = svd(r); % r의 특이값 분해
>> q*u1 % u0와 같음, 즉, u0.d0.v0' = (q*u1).d1.v1'이다.
>> d1 % d0와 같음
[1] G. Golub and C. Van Loan, Matrix Computation. Johns Hopkins Univ. Press, 1992.
댓글 없음:
댓글 쓰기