RSVD(Reduced Singular Value Decomposition)

우선 SVD는 \(A = U \sum V\)의 형식인 것을 전 게시물에서 확인할 수 있었다. 이때 A는 일반 행렬(mxn)이며, 이 A를 orthogonal matrix인 U, V(서로 다르거나 같을 수 있음)와 main diagonal matrix인 \(\sum\)으로 이때 rank(A) = k라 두면 아래와 같은 간단한 식으로 정리를 할 수 있는데, 이를 Reduced Singular Value Decomposition이라고도 한다.

위의 식을 \(A = U_1\sum_1 V_1\)로 나타내면 각각 m×k, k×k, k×n 크기의 행렬이 되고 \(\sum_1\)의 diagonal entries들은 양수이기 때문에(맨 하단에 증명) invertible하다. 또한 해당 식은 아래로 간단히 표기할 수 있는데 이를 A의 reduced singular value expansion이라고도 한다. reduced singular value expansion을 통해 RSVD를 계산을 한다.

---

RSVD는 시각 정보를 압축하여 저장 공간을 줄이고 전자 전송 속도를 향상시키기에 visual information을 압축하는데 많이 사용된다.

시각 이미지를 압축하는 첫 단계는 이를 숫자 행렬로 표현하는 것이며, 이를 통해 필요한 경우 시각 이미지를 복원할 수 있다. 예를 들어, 흑백 사진은 픽셀 배열로 스캔된 후 각 픽셀에 회색 수준에 따라 숫자 값을 할당하여 행렬로 저장된다.

행렬 A의 크기가 m×n이라면, A의 각 항목을 개별적으로 저장할 수 있지만, 대안으로 RSVD를 계산하여 저장 공간을 절약할 수 있다. (특히 충분히 작은 특이값을 제외하고 r 순위 근사를 이용하면, 원래 A보다 훨씬 적은 숫자를 필요로 하여 압축 효율성을 높인다.)

아래의 그림은 원래 지문과 26:1 비율로 압축된 디지털 데이터에서 복원된 지문을 보여준다.

 

이 사진은 FBI가 1924년에 약 1억 개 이상의 지문을 수집한 것 중 하나로, 저장 비용 절감을 위해 1993년부터 로스알라모스 국립연구소, 국가기술표준원 등과 협력하여 지문을 디지털 형식으로 저장하기 위한 순위 기반 압축 방법을 개발하였다고 한다.

 

 

 

 

 

※ reference : ELEMENTARY LINEAR ALGEBRA - Howard Anton, Chris Rorres