Greedy randomized block Kaczmarz method for matrix equation AXB=C and its applications in color image restoration

기술 요약: 행렬 방정식 $AXB = C$를 위한 탐욕적 무작위 블록 카츠마르크 방법 및 색상 이미지 복원에의 응용

문제 정의
본 논문은 $A \in \mathbb{R}^{m \times p}$, $B \in \mathbb{R}^{q \times n}$, $C \in \mathbb{R}^{m \times n}$인 대규모 행렬 방정식 $AXB = C$의 해법을 다룬다. 이 방정식은 이미지 처리, 안정성 분석, 제어 이론, 머신러닝 회귀를 포함한 공학적 응용 분야에서 빈번하게 발생한다. 대규모 시스템의 경우 직접적인 방법(direct methods)은 실용적이지 않은 반면, 전통적인 반복법(예: 경사 하강법 기반, Jacobi, Gauss-Seidel)은 각 단계마다 전체 계수 행렬을 저장하고 계산해야 하므로 높은 저장 공간과 계산 요구량을 발생시킨다. 저자들은 행(row)-액션 및 열(column)-액션 방법, 특히 서브 블록(sub-blocks)을 통해 전체 행렬에 대한 접근을 피하는 카츠마르크 방법(Kaczmarz method)을 확장한 방법을 연구한다.

방법론
저자들은 $AXB = C$에 대한 카츠마르크 프레임워크를 기반으로 적응된 일련의 반복 알고리즘을 제안한다:

1. 블록 카츠마르크 (ME-BK): 행 인덱스 $i_k$를 순차적으로 선택($i_k = (k \mod m) + 1$)하는 결정론적 순환 방식이다. 업데이트는 선택된 $A$의 행에 의해 정의된 초평면(hyperplane) 위로 현재 추정치를 투영한다.
2. 탐욕적 무작위 블록 카츠마르크 (ME-GRBK): 잔차(residual)가 큰 행을 선호하는 확률 기준에 따라 행을 선택하는 확률적 방법이다. 구체적으로, 최대 정규화 잔차와 전역 잔차 노름(global residual norm)에 기반한 임계값 $\zeta_k$를 정의한다. $\|R_k^{i,:}\|_2^2 \ge \zeta_k \|A_{i,:}\|_2^2 \|R_k\|_F^2$를 만족하는 행들이 후보 집합 $J_k$를 형성하며, 이 중 제곱 잔차에 비례하는 확률로 행이 선택된다.
3. 완화된 탐욕적 무작위 블록 카츠마르크 (ME-RGRBK): ME-GRBK의 확장형으로, 더 유연한 인덱스 집합 선택을 위해 확률 기준에 완화 계수(relaxation factor) $\theta \in (0, 1)$를 도입하였다.
4. 최대 가중 잔차 블록 카츠마르크 (ME-MWRBK): 가중 잔차 $\frac{\|R_k^{i,:}\|_2^2}{\|A_{i,:}\|_2^2}$를 최대화하는 행 인덱스를 선택하는 ME-GRBK의 결정론적 버전이다.

이 알고리즘들은 벡터화(vectorization)를 통해 크로네커 곱(Kronecker product) 구조를 암시적으로 활용하며, $AA^T$와 $B^TB$를 사전 계산함으로써 잔차 행렬 $R_k = C - AX_kB$를 효율적으로 업데이트한다.

주요 기여

• ME-BK의 수렴성: 본 논문은 시스템이 일치(consistent)할 때, 결정론적 ME-BK 방법이 $X^* + X_0 - A^+AX_0BB^+$ (여기서 $X^* = A^+CB^+$는 유일한 최소 노름 해)로 수렴함을 입증한다. 이는 $AXB=C$에 대한 블록 카츠마르크 방법의 수렴성이 이전에 조사되지 않았던 공백을 메운다.
• 탐욕적 변형들의 수렴성: 저자들은 시스템이 일치할 때 ME-GRBK, ME-RGRBK, ME-MWRBK 방법이 기대값(expectation) 측면에서 유일한 최소 노름 해인 $A^+CB^+$로 수렴함을 증명한다.
• 수렴 속도: 이론적 분석을 통해 탐욕적 및 완화된 방법의 수렴 계수가 기존의 무작위 블록 카츠마르크(ME-RBK, [12]) 방법보다 엄격히 작음(더 빠른 수렴을 의미)을 보여준다.
• 기존 연구와의 차별점: 저자들은 자신들의 접근 방식이 [11]의 방법과 다르다는 점을 명확히 한다. [11]은 방정식을 두 개의 확률적 인덱스를 요구하는 $mn$개의 하위 시스템으로 변환하는 반면, 본 논문은 방정식을$m$개의 하위 시스템($A_{i,:}XB = C_{i,:}$)으로 변환하여 반복당 하나의 확률적 인덱스만을 요구한다.

결과
MATLAB을 사용하여 University of Florida 컬렉션 및 무작위 생성기를 통한 다양한 행렬 집합(희소 및 밀집, 풀 랭크 및 랭크 결핍)에 대해 수치 실험을 수행하였다.

• 수렴 검증: ME-BK의 특정 해 형태에 대한 이론적 수렴이 6개의 행렬 집합에 대해 검증되었다.
• 성능 비교: 반복 횟수(IT) 및 CPU 시간 측면에서 제안된 ME-GRBK, ME-RGRBK, ME-MWRBK 방법은 ME-RBK 방법을 지속적으로 능가하였다.
  • 풀 열/행 랭크 시스템의 경우, 행렬 집합과 방법에 따라 약 2배에서 13배 사이의 속도 향상을 보였다.
  • 랭크 결핍 시스템의 경우, 1.35배에서 4.29배 사이의 속도 향상을 보였다.
  • ME-MWRBK(결정론적)가 일반적으로 가장 높은 속도 향상을 달성하였으며, ME-RGRBK와 ME-GRBK가 그 뒤를 바짝 쫓았다.
• 이미지 복원에의 응용: 제안된 방법들을 $B = AXA_c^T + E$로 모델링된 색상 이미지 복원(디블러링)에 적용하였다. 테스트 이미지("face", "bird", "mandril", "barbara")를 사용했을 때, 제안된 방법들은 ME-RBK에 비해 현저히 높은 최대 신호 대 잡음비(PSNR)와 구조적 유사도 지수(SSIM)를 달s성하였다. 예를 들어, "face" 이미지의 경우 ME-RBK는 PSNR 27.02를 기록한 반면, ME-MWRBK는 33.72를 달성하였다.

의의
본 논문은 제안된 방법들이 기존의 무작위 블록 카츠마르크 방법들에 비해 대규모 행렬 방정식 $AXB=C$를 해결하는 데 있어 더 효율적이고 효과적인 접근 방식을 제공한다고 주장한다. 탐욕적 선택 전략과 결정론적 변형을 도입함으로써, 저자들은 이론적 및 수치적으로 우수한 수렴 속도를 입증하였다. 색상 이미지 복원에 대한 성공적인 적용은 대규모 데이터와 저장 공간 제약이 중요한 실제 공학 문제에서 이 알고리즘들의 실용적 유용성을 검증한다. 본 연구는 카츠마르크 유형의 방법의 적용 범위를 일반 선형 시스템을 넘어 일반 행렬 방정식으로 확장한다.