GKB Methods for X-Ray Computed Tomography with an Unmatched Back Projector

기술 요약: 독보적인 백 프로젝터를 이용한 GKB 방식의 X-선 컴퓨터 단층 촬영법

문제 정의
대규모 X-선 컴퓨터 단층 촬영(CT)에서, 측정된 데이터 $b$로부터 이미지 $x$를 재구성하는 문제는 선형 역문제 $Ax \approx b$로 정식화된다. 실제 구현 시, 순방향 프로젝터($A$)와 역방향 프로젝터($B$)는 물리적 근사에 기반한 서로 다른 이산화 기법을 사용하여 생성되는 경우가 많다. 결과적으로 $B$는 $A$의 전치 행렬과 동일하지 않으며($B \neq A^\top$), 이는 "불일치 프로젝터 쌍(unmatched projector pair)"을 생성한다.

이러한 불일치는 일관되지 않은 정규 방정식(normal equations)을 초래한다. 이러한 불일치 시스템의 최소제곱 정식화에 적용되는 표준 반복 솔버인 켤레 기울기법(CG) 및 일반화 최소 잔차법(GMRES)은 종종 의미 있는 재구성을 생성하는 데 실패한다. 이러한 시스템을 처리하기 위해 사전 조건화된 GMRES 변형(AB-GMRES 및 BA-GMRES)이 제안되었으나, 이들은 "반수렴(semiconvergence)" 문제를 겪는다. 반수렴 현상이란, 솔루션이 초기에는 실제 이미지에 가깝게 수렴하다가, 작은 특이값(singular values)과 관련된 성분들이 포함됨에 따라 노이즈를 증폭시키며 이후 발산하는 현상을 말한다. 또한, GMRES의 투영된 시스템은 상부 헤센베르크(upper Hessenberg) 행렬을 포함하므로, 크릴로프 부공간(Krylov subspace)의 차원이 커짐에 따라 계산 비용이 많이 들 수 있다.

방법론
본 논문은 불일치 프로젝터 쌍을 처리하기 위해 골럽-카한 비직교화(Golub–Kahan Bidiagonalization, GKB) 방법을 응용한 두 가지 새로운 알고리즘인 AB-GKB와 BA-GKB를 제안한다. 시스템을 상부 헤 Hessenberg 행렬로 투영하는 GMRES와 달리, GKB는 희소 하부 쌍직각(sparse lower bidiagonal) 행렬($C_k$)을 생성하는 저차원 부공간으로 문제를 투영한다.

제안된 방법의 기능은 다음과 같다:

• AB-GKB: 시스템 $ABx = Bb$에 GKB 과정을 적용한다($B$를 우측 사전 조건자로 취급). 솔루션은 $x = BQ_k u_k$를 통해 복구된다(여기서 $Q_k$는 직교 기저이고 $u_k$는 투영된 쌍직각 시스템의 해이다).
• BA-GKB: 시스템 $BAx = Bb$에 GKB 과정을 적용한다($B$를 좌측 사전 조건자로 취급). 솔루션은 $x = Q_k u_k$를 통해 복구된다.

두 알고리즘 모두 $AB$또는$BA$의 합성 연산자를 명시적으로 형성하는 것을 피하며, 대신$A$, $B$ 및 그들의 전치 행렬을 이용한 연속적인 행렬-벡터 곱셈에 의존한다. 투영된 소규모 문제는 쌍직각 행렬 $C_k$의 특이값 분해(SVD)를 사용하여 해결된다. 저자들은 반수렴을 완화하기 위해 두 가지 정지 기준인 **불일치 원리(Discrepancy Principle, DP)**와 **잔차 규격 정체(Residual Norm Stagnation, RNS)**를 조사한다.

주요 기여

1. 알고리즘 제안: 불일치 프로젝터 쌍을 가진 CT 문제를 위해 특별히 설계된 GKB의 사전 조건화 형태로서 AB-GKB 및 BA-GKB를 도입하였다.
2. 이론적 복잡도 분석: 제안된 GKB 방법과 기존의 AB/BA-GMRES 방법 간의 부동 소수점 연산(FLOPS)을 상세히 비교하였다. 분석 결과, GMRES 방법이 반복당 계산량(필요한 연산 횟수) 측면에서는 더 빠르지만, GKB 방법은 GMRES의 헤센베르크 행렬($H_k$)보다 더 희소한 투영 행렬($C_k$)을 생성한다는 점을 밝혀냈다. 쌍직각 행렬 $C_k$의 SVD는 헤센베르크 $H_k$의 SVD($O(k^4)$)보다 훨씬 저렴하게($O(k^3)$) 수행된다.
3. 수치적 검증: 다양한 노이즈 수준과 시스템 차원(과결정 또는 저결정 시스템)을 가진 세 가지 CT 팬텀 예시(128x128, 180x180, 256x256)에 대해 광범위한 테스트를 수행하였다.
4. 정지 기준 평가: DP와 RNS를 비교 평가하여, DP가 상대 재구성 오차(RRE)의 최소치 근처에서 반복을 일관되게 종료시킨다는 것을 입증하였다.

결과
다양한 CT 시나리오에 걸친 수치 실험을 통해 다음과 같은 관찰 결과가 도출되었다:

• 반수렴 동작: 제안된 GKB 방법들은 AB-GMRES 및 BA-GMRES에 비해 반수렴 현상에 대해 더 큰 회복력을 보였다. GMRES 방법들은 종종 몇 번의 반복(예: 710회) 만에 급격히 발산한 반면, GKB 방법들은 노이즈 증폭이 지배적이 되기 전까지 더 긴 시간 동안(예: 40100회 반복) 안정화 상태를 유지했다.
• 재구성 품질: 상대 재구성 오차(RRE) 측면에서, GKB 방법들은 적절한 시점에 반복을 멈춘다는 전제하에, 특히 후기 반복 단계에서 GMRES 방법들보다 일반적으로 더 낮은 오차율을 달려냈다.
• 계산 비용: 이론적 분석과 일치하게, GMRES 방법들이 총 실행 시간 측면에서 더 빨랐다. 고정된 반복 횟수에 대해 GMRES는 더 적은 FLOPS를 요구했다. 구체적으로, AB-GMRES는 AB-GKB 비용의 약 3/5을 소요했고, BA-GMRES는 BA-GKB의 약 절반의 비용을 소요했다.
• 정지 기준: 불일치 원리(DP)가 RNS보다 우수한 것으로 판명되었다. DP는 모든 방법에서 일관되게 최적의 RRE 근처에서 반복을 중단시킨 반면, RNS는 알고리즘에 따라 너무 빨리 혹은 너무 늦게 종료되어 최적화되지 못한 재구성을 초래했다.
• 시스템 차원: AB와 BA 공식의 상대적 효율성은 시스템이 과결정($m > n$)인지 저결정($m < n$)인지에 따라 달라졌다. 과결정 사례에서는 BA 기반 방법이 일반적으로 더 빨랐고, 저결정 사례에서는 AB 기반 방법이 더 많은 비용이 들었다.

의의 및 주장
본 논문은 제안된 AB-GKB 및 BA-GKB 알고리즘이 GMRES 기반 접근 방식보다 반복당 계산 비용은 더 높지만, 불일치 프로젝터 문제에 대해 안정성 및 솔루션 품질 측면에서 뚜렷한 이점을 제공한다고 주장한다. GKB에 의해 생성된 쌍직각 행렬의 희소성을 활용함으로써, 이 방법들은 반수렴의 시작을 지연시켜 크릴로프 부공간 방법의 정확도 잠재력을 손실하지 않으면서도 더 안정적인 재구성을 가능하게 하는 견고한 대안을 제공한다.

저자들은 이러한 방법들의 효과가 정지 기준의 선택에 크게 의존한다는 점을 강조하며, 노이즈 오염이 솔루션을 저하시키기 전에 반복을 종료하는 가장 신뢰할 수 있는 메커니즘으로 불일치 원리(DP)를 식별하였다. 결론적으로, 이 알고리즘들은 일치하는 프로젝터를 사용할 수 없는 대규모 CT 역문제에서 안정적인 솔루션을 제공하는 데 효과적이지만, 향후 효율성을 더욱 높이기 위해 고급 정규화 기법과의 통합에 초점을 맞출 수 있다고 밝혔다.