A Tensor Greedy Double-Block Extended Kaczmarz Method for Inconsistent Tensor Linear Systems under the t-product

기술 요약: t-product 하의 불일치 텐서 선형 시스템을 위한 텐서 그리디 더블 블록 확장 카차르츠 방법

문제 정의
본 논문은 $\mathcal{A} * \mathcal{X} = \mathcal{B}$ 형태의 불일치 3차 텐서 선형 시스템을 해결하는 문제를 다룬다. 여기서 $\mathcal{A} \in \mathbb{R}^{N_1 \times N_2 \times N_3}$, $\mathcal{B} \in \mathbb{R}^{N_1 \times K \times N_3}$이며, $*$는 Kilmer와 동료들이 도입한 t-product를 의미한다. 색상 이미지 복원 및 MRI 디블러링(deblurring)과 같은 실제 응용 분야에서, 시스템은 노이즈($\mathcal{B} = \mathcal{A} * \mathcal{X}^* + \mathcal{E}$)로 인해 불일치하는 경우가 많다. 목표는 고유한 최소 노름 최소제곱해 $\mathcal{X}^* = \mathcal{A}^\dagger * \mathcal{B}$를 찾는 것이다. 무작위 확장 카차르츠(Randomized Extended Kaczmarz, REK) 방법은 불일치 행렬 시스템을 효과적으로 처리하지만, 기존의 텐서 확장 방식(TREK, TREBK, TREGBK 등)은 텐서 슬라이스의 정적이고 미리 정의된 분할에 의존하며, 이는 문제의 특정 구조나 잔차 분포에 최적으로 적응하지 못할 수 있다.

방법론
저자들은 텐서 그리디 더블 블록 확장 카차르츠(Tensor Greedy Double-Block Extended Kaczmarz, TGDBEK) 방법을 제안한다. 이 알고리즘은 행렬 기반의 그리디 더블 블록 확장 카차르츠(GDBEK)를 텐서 t-product 환경으로 확장한 것이다. 핵심 방법론은 각 단계 $k$에서 두 개의 결합된 반복 프로세스를 포함한다:

1. 쌍대 변수 업데이트 ($\mathcal{Z}$): 알고리즘은 우변 $\mathcal{B}$를 $\mathcal{A}$의 범위(range)로 투영하기 위해 보조 텐서 $\mathcal{A}$를 업데이트한다. 이는 그리디 기준에 따라 $\mathcal{A}$의 측면 슬라이스(lateral slices, 열) 블록을 선택함으로써 수행된다.
2. 원 프라임 변수 업데이트 ($\mathcal{X}$): 알고리즘은 수정된 우변 $(\mathcal{B} - \mathcal{Z})$를 사용하여 해 $\mathcal{X}$를 업데이트한다. 이는 현재 추정치의 잔차(residual)를 기반으로 $\mathcal{A}$의 수평 슬라이스(horizontal slices, 행) 블록을 선택하는 과정을 포함한다.

핵심 혁신: 동적 그리디 선택
정적이고 미리 분할된 블록을 사용하는 기존의 텐서 블록 방법(TREBK, TREGBK, TREABK)과 달리, TGDBEK는 매 반복마다 행 및 열 슬라이스의 활성 블록을 동적으로 구성한다.

• 선택 전략: 알고리즘은 잔차 노름(residual norm) 기반의 그리디 선택 전략을 채택한다. 이는 가장 큰 잔차 노름과 관련된 슬라이스들을 식별한다.
• 임계값 파라미터 ($\eta$): $\eta \in (0, 1]$ 범위의 직관적인 단일 파라미터가 활성 블록의 크기를 제어한다. 특정 슬라이스의 정규화된 제곱 잔차 기여도가 모든 슬라이스 중 최대 기여도의 $\eta$ 배를 초과하는 경우 해당 슬라이스가 활성 블록에 포함된다. 이를 통해 고정된 분할 없이도 문제의 상태에 따라 블록 크기가 동적으로 적응할 수 있게 한다.

이론적 기여
본 논문은 TGDBEK 방법이 프로베니우스 노름(Frobenius norm) 하에서 고유한 최소 노름 최소제곱해로 선형 수렴함을 입증한다.

• 수렴 분석: 저자들은 쌍대 반복 수열 $\{\mathcal{Z}^{(k)}\}$이 $\mathcal{B}$의 \mathcal{\mathcal{A}$의 범위에 직교하는 성분으로 선형 수렴함을 증명한다.
• 주요 정리: 원 프라임 반복 수열 $\{\mathcal{X}^{(k)}\}$ 또한 선형 수렴함이 밝혀졌다. 수렴 속도는 텐서 $\mathcal{A}$의 내재적 기하학적 파라미터, 구체적으로 텐서 블록 조건수 $\kappa_{block}(\mathcal{A})$와 최소 활성 블록 특이값에 의존한다. 증명은 피타고라스 정리의 텐서 아날로그와 블록 순환 행렬(block circulant matrix)의 프로베니우스 노름과 텐서 노름 사이의 관계를 포함한 t-product의 성질에 기반한다.

수치 결과
합성 밀집(dense) 및 희소(sparse) 텐서 시스템과 실제 이미지 디블러링 문제(컬러 이미지 및 3D 볼륨 MRI)에 대해 광범위한 수치 벤치마크를 수행하였다. TGDBEK 방법은 최신 솔버인 TREK, TREBK, TREGBK와 비교되었다.

• 성능 지표: 연구는 상대 제곱 오차(RSE) 허용 오차 $10^{-5}$에 도달하기 위한 반복 횟수(IT)와 CPU 실행 시간을 평가하였다.
• 밀집 시스템: TGDBEK는 일관되게 가장 적은 반복 횟수와 가장 적은 CPU 시간을 요구하였다. 예를 들어, $n=80$인 밀집 시스템에서 TGDBEK는 44회 반복 만에 수렴한 반면, TREBK와 TREGBK는 각각 247회, 217회의 반복이 필요했다. TREK는 반복 예산 내에 수렴하지 못하는 경우가 많았다.
• 희소 시스템: SuiteSparse 컬렉션에서 유도된 희소 텐서에 대해, TGDBEK는 경쟁 모델들보다 훨씬 적은 반복 횟수로 수렴하며 탁월한 효율성을 보여주었다.
• 이미지 디블러링: 컬러 이미지 디블러링에서 TGDBEK는 1000회 반복 내에 규정된 허용 오차($10^{-5}$)에 도달한 유일한 방법이었으며, 503회 반복에서 최종 RSE $1.00 \times 10^{-5}$를 달축성했다. 다른 방법들은 이 허용 오차에 도달하지 못했다. MRI 디블러링에서는 TGDBEK가 수렴하는 다른 방법들과 동일한 재구성 품질(PSNR/SSIM)을 보이면서도, 실제 실행 시간(wall-clock time) 측면에서 더 빠르게 솔루션을 달성하였다.
• 파라미터 민감도: 임계값 $\eta$를 변화시키는 실험 결과, $\eta$의 범위 $[0.1, 0.6]$가 수렴 속도와 반복당 계산 비용 사이의 최적의 절충안을 제공함을 확인하였다.

의의 및 주장
본 논문은 TGDBEK가 엄격하게 사전 정의된 블록 분할의 필요성을 제거함으로써 기존의 텐서 카차르츠 솔버들을 실질적으로 능가한다고 주장한다. 잔차 에너지에 따라 활성 블록 크기를 동적으로 조정함으로써, 이 방법은 가장 필요한 곳에 계산 자원을 집중한다. 저자들은 이러한 접근 방식이 최신 방법들과 비교하여 최대 5배의 반복 횟수 감소와 최대 2.5배의 실제 CPU 시간 감소를 이끌어낸다고 단언한다. 본 연구는 t-product 설정에서의 그리디 전략에 대한 이론적 토대를 제공하며, 영상 처리 응용 분야에서 발생하는 대규모 불일치 텐서 시스템을 해결하는 데 있어 실질적인 효과를 입증한다.

향후 연구 방향
저자들은 세 가지 잠재적인 연구 방향을 제시한다:

1. 큰 블록 크기에 대한 계산 복잡도를 줄이기 위해 평균화 전략을 사용하는 투영 불필요(projection-free/pseudoinverse-free) 변형 모델 개발.
2. 잔차 감소에 따라 진화하는 적응형 및 동적 임계값 시퀀스($\eta_k$) 조사.
3. 일반화된 튜플 t-product 하에서의 **고차 텐서($p \ge 4$)**로의 프레임워크 일반화.