Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product with Applications to Image and Video Restoration

1. 문제 정의 (Problem Statement)

• 배경: 컬러 이미지 복원, 비디오 디블러링 (deblurring), 초분광 영상, 고차원 편미분방정식 (PDE) 이산화 등 다양한 분야에서 다중 선형 시스템 (Multilinear Systems) 이 발생합니다.
• 수학적 모델: 이러한 문제는 다음과 같은 텐서 방정식으로 표현됩니다.
  $$\Phi(X) = C$$
  여기서 $\Phi$는 아인슈타인 곱 (Einstein product, $*_N$) 을 통해 정의된 선형 텐서 연산자이며, $X$는 복원하려는 미지의 텐서, $C$는 관측된 (블러링되거나 노이즈가 섞인) 텐서입니다.
• 기존 방법의 한계:
  • 고전적인 텐서 글로벌 GMRES (Generalized Minimal Residual) 또는 Golub-Kahan 방법은 Frobenius 내적과 완전한 텐서 직교화 (Orthogonalization) 에 의존합니다.
  • 고차원 텐서 (예: 컬러 이미지, 비디오) 의 경우 차원이 매우 커지므로 ($n = \prod I_k$), 직교화 과정의 계산 비용이 prohibitive(부담스러울 정도로 큼) 해져 대규모 문제 해결이 어렵습니다.
  • 행렬화 (Vectorization) 를 사용하면 데이터의 본질적인 다차원 구조가 파괴되고 메모리 및 계산 비용이 급증합니다.

2. 제안된 방법론 (Methodology)

저자들은 계산 비용을 줄이면서 수렴 특성을 유지하기 위해 **스케치된 아인슈타인 내적 (Sketched Einstein Inner Product)**을 기반으로 한 무작위 텐서 크릴로프 부분공간 방법을 제안합니다.

2.1. 스케치된 아인슈타인 내적 (Sketched Einstein Inner Product)

• 개념: 모드별 (mode-wise) 무작위 투영 행렬 ($\Theta_k, \Psi_l$) 을 사용하여 고차원 텐서를 저차원 텐서 공간으로 압축 (Sketching) 합니다.
• 정의: 텐서 $X, Y$에 대해 스케치된 내적은 다음과 같이 정의됩니다.
  $$\langle X, Y \rangle_\Theta = \langle S(X), S(Y) \rangle_F$$
  여기서 $S(\cdot)$는 텐서 부분공간을 저차원 공간으로 매핑하는 스케치 연산자입니다.
• 이점: 이 방식은 부분공간 임베딩 (Subspace Embedding) 성질을 만족하여, 원래의 기하학적 구조와 내적 관계를 $\epsilon$ 오차 범위 내에서 보존하면서도 차원을 획기적으로 줄입니다.

2.2. 무작위 텐서 글로벌 Arnoldi 과정 및 GMRES

• 알고리즘: 기존 글로벌 Arnoldi 과정을 수정하여, 텐서 곱 연산 시 스케치된 아인슈타인 내적을 사용합니다.
  • Sketched Global Arnoldi: 직교화 과정에서 $W = S(\Phi(V_j))$를 계산하고, 스케치된 내적 $\langle V_i, W \rangle_\Theta$를 사용하여 헤센베르크 (Hessenberg) 행렬을 구성합니다.
  • RTG-GMRES (Randomized Tensor Global GMRES): 축소된 헤센베르크 행렬을 통해 최소 잔차 문제를 해결하여 근사 해를 구합니다.
• Tikhonov 정규화: ill-posed 문제 (노이즈가 있는 경우) 를 안정화하기 위해 축소된 공간에서 Tikhonov 정규화 문제를 풉니다.
  $$\min_y \| \beta e_{m+1}^1 - \hat{H}_m y \|_2^2 + \mu \|y\|_2^2$$
  정규화 파라미터 $\mu$는 GCV (Generalized Cross-Validation) 또는 L-curve 기법을 통해 선택됩니다.

2.3. 블록 크릴로프 방법 (Block Krylov Subspace Methods)

• 컬러 이미지 (RGB) 나 비디오와 같은 다중 채널 데이터를 효율적으로 처리하기 위해 블록 GMRES와 블록 Golub-Kahan 알고리즘을 스케치된 아인슈타인 곱 프레임워크로 확장했습니다.
• 텐서 QR 분해와 블록 직교화 과정을 스케치된 내적 기준으로 수행합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 프레임워크 제안: 아인슈타인 곱과 무작위 스케칭 (Randomized Sketching) 을 결합하여 고차원 텐서 방정식을 효율적으로 풀 수 있는 RTG-GMRES 및 Sketched Block Golub-Kahan 알고리즘을 개발했습니다.
2. 계산 효율성 극대화: 고차원 텐서의 직교화 비용을 줄이면서도, 텐서 부분공간 임베딩 이론을 통해 수렴성과 해의 정확도를 보장합니다.
3. 이론적 분석: 잔차 오차 한계 (Residual bounds), 섭동 분석 (Perturbation analysis), 그리고 축소된 공간에서의 Tikhonov 정규화 해에 대한 이론적 근거를 제시했습니다.
4. 실제 적용: 컬러 이미지 및 비디오 복원이라는 구체적인 응용 분야에 대해 알고리즘의 유효성을 입증했습니다.

4. 실험 결과 (Numerical Results)

저자들은 MATLAB 환경에서 흐릿하고 노이즈가 섞인 RGB 이미지 및 비디오 복원 실험을 수행했습니다.

• 비교 대상:
  1. 기존 텐서 블록 GMRES (스케칭 없음)
  2. 기존 텐서 블록 Golub-Kahan (스케칭 없음)
  3. 제안된 스케치된 블록 GMRES 및 Golub-Kahan
• 성능 지표: PSNR (Peak Signal-to-Noise Ratio), 상대 오차 (RE), CPU 시간.
• 결과 요약:
  • 정확도: 스케칭을 적용한 방법들은 스케칭을 적용하지 않은 기존 방법들과 비교할 수 있거나 오히려 약간 더 높은 PSNR을 보여주었습니다. (예: 노이즈 레벨 $10^{-3}$에서 Golub-Kahan 의 PSNR 은 24.37 vs 24.42).
  • 계산 시간: 스케칭을 적용함으로써 CPU 시간이 약 40~60% 단축되었습니다.
    • 예시: 노이즈 레벨 $10^{-3}$에서 기존 GMRES 는 8.28 초, 스케치된 GMRES 는 4.22 초로 감소.
    • 예시: 노이즈 레벨 $10^{-2}$에서 기존 Golub-Kahan 은 1.58 초, 스케치된 Golub-Kahan 은 0.70 초로 감소.
  • 결론: 스케칭은 해의 품질을 저하시키지 않으면서 대규모 고차원 문제를 해결하는 데 있어 계산 자원을 크게 절감하는 효과적인 전략임을 입증했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 고차원 데이터 처리의 혁신: 벡터화를 피하면서 텐서의 다차원 구조를 유지한 채, 무작위 스케칭을 통해 계산 복잡도를 획기적으로 낮췄습니다.
• 실용적 가치: 고해상도 이미지 및 비디오 복원과 같이 계산 자원이 제한적이거나 실시간 처리가 필요한 분야에서 기존 반복법의 대안으로 매우 유망합니다.
• 안정성: Tikhonov 정규화와 결합하여 노이즈가 있는 ill-posed 문제에서도 안정적인 복원 성능을 발휘함을 확인했습니다.

요약하자면, 이 논문은 무작위 스케칭 기법을 텐서 크릴로프 방법론에 도입함으로써, 고차원 이미지/비디오 복원 문제에서 계산 효율성을 극대화하면서도 정확도를 유지하는 새로운 표준을 제시했습니다.