A fast solver for ill-conditioned linear systems using randomized stable solutions of its blocks

문제 정의
본 논문은 $A \in \mathbb{R}^{m \times n}$ 및 $b \in \mathbb{R}^{m \times 1}$인 일관된 선형 방정식 계 $Ax = b$를 해결하는 과제를 다룹니다. 주요 초점은 희소 시스템(sparse systems), 밀집 최소제곱 문제(dense least-squares problems), 그리고 현저하게 과결정(over-determined)되거나 미결정(under-determined)된 경우를 포함하여 매우 불량한 조건수(highly ill-conditioned)를 가진 시스템에 맞춰져 있습니다. 저자들은 GMRES와 같은 표준 반복법이 이러한 시스템에서 어려움을 겪는 이유가 잔차 노름(residual norm)을 최소화하는 것이 반드시 불량한 조건의 문제에서 상대 오차(relative error)의 수렴을 보장하지 않기 때문임을 강조합니다. 또한, 전통적인 전처리 기법(예: ILU, Jacobi)은 매우 큰 조건수를 가진 행렬에 적용될 때 수치적 불안정성, 피벗 붕괴(pivot breakdowns), 또는 과도한 채우기(excessive fill-in)로 인해 고통받을 수 있으며, 강력한 가속이 가장 필요한 시점에 정확히 실패하곤 합니다.

방법론
저자들은 **정규화된 직교성 및 잔차 기반 블록-카츠마르크(Regularized Orthogonality and Residual based Block-Kaczmarz, ROR-BK)**라고 명명된 향상된 알고리즘을 제안합니다. 이 방법은 무작위 블록-카츠마르크 프레임워크를 기반으로 구축되었으며, 안정성과 수렴성을 개선하기 위해 세 가지 특정 향상 기법을 도입했습니다:

1. 동적 잔차 기반 집계(Dynamic Residual-Based Aggregation): 고정된 블록에만 의존하는 대신, 이 방법은 각 반복 단계에서 현재 잔차 벡터를 기반으로 방정식의 하위 집합을 동적으로 집계합니다. 구체적으로, 각 단계에서 잔차 노름을 더 효과적으로 최소화하는 것을 목표로 하여 제곱 잔차에 가장 크게 기여하는 행들을 선택해 하나의 블록을 형성합니다.
2. 효과적인 상호 직교성 샘플링(Effective Mutual Orthogonality Sampling): 이 방법은 블록 쌍 간의 직교성 개념(Simple Orthogonal Block-Kaczmarz 또는 SOBK에서 사용됨)을 단일 블록이 다른 모든 블록에 대해 갖는 "효과적 직교성(effective orthogonality)"으로 일반화합니다. 블록 중심점들 사이의 유효 각도의 코사인 값을 나타내는 대칭 행렬 $C$가 계산됩니다. 그 후, 시스템의 나머지 부분에 대해 높은 누적 직교성을 가진 블록들을 선호하는 분포에 따라 확률적으로 블록을 샘플링합니다.
3. 정규화(Regularization): 특히 블록이 계수 결핍(rank-deficient) 상태이거나 조건이 좋지 않을 때 수치적 안정성을 보장하기 위해, 블록 업데이트는 정규화된 유사 역행렬을 사용합니다. 표준 무어-펜로즈 역행렬 $B^\dagger = B^T(BB^T)^{-1}$ 대신, 이 방법은 $B^T(BB^T + \mu I)^{-1}$ 형태의 정규화된 형태를 사용하며, 여기서 $\mu$는 작은 양의 상수입니다. 이는 확률적 근접 점 알고리즘(stochastic proximal point algorithm)으로 해석됩니다.

알고리즘은 직교성이 샘플링된 블록을 사용하는 업데이트와 잔차 기반의 동적 블록을 사용하는 업데이트를 교대로 수행하며 작동합니다. 저자들은 이 방법이 유연한 GMRES(FAB-GMRES) 솔버를 위한 내부 반복(inner iteration, preconditioner)으로 기능할 수 있음을 입증했습니다.

주요 기여

• 알고리즘 혁신: 잔차 기반 동적 블록 선택, 전역 직교성 인지 샘플링, 그리고 Tikhonov 스타일의 정규화를 블록-카츠마르크 프레임워크 내에서 결합한 ROR-BK의 도입.
• 이론적 분석: 방법론이 블록이 수치적으로 계수 결핍 상태일 때도 안정적인 수렴을 달아낸다는 수렴 분석(정리 2.3 및 2.4)을 제공합니다. 이는 오차 감소가 정규화 매개변수 $\mu$와 블록 행렬의 최소 비영(non-zero) 고윳값에 의해 제한됨을 확립합니다. 정리 2.4는 최대 잔차를 기준으로 블록을 선택하는 것이 오차의 상한 및 하한을 개선한다고 주장합니다.
• 전처리 전략: 명시적이고 잠재적으로 불안정한 외부 전처리기를 사용할 필요 없이, 불량한 조건의 시스템을 가속화하기 위해 ROR-BK를 pre-solver 또는 내부 반복으로 사용하는 제안.

결과
저자들은 ROR-BK를 다음 모델들과 비교하는 광범로한 수치 실험을 수행했습니다:

• 무작위 솔버: Simple Orthogonal Block-Kaczmarz (SOBK) 및 Tail Averaged Regularized Block Kaczark (TA-ReBlocK-U).
• 크릴로프 부공간 솔버: 다양한 전처리기(Jacobi, ILU, Robust Incomplete Factorization(RIF) 등)를 사용한 LSQR 및 다양한 GMRES 변형(AB/BA-GMRES).

성능 결과:

• 속도 및 반복 횟수: 다양한 테스트 행렬(University of Florida 컬렉션의 희소 행렬 및 무작위 생성 밀집 행렬 포함) 전반에 걸쳐, ROR-BK는 SOBK 및 TA-ReBlocK-U보다 일관되게 적은 반복 횟수와 적은 CPU 시간을 요구했습니다. CPU 시간 측면에서 SOBK 대비 1.23배에서 5.17배, TA-ReBlocK-U 대비 최대 49.08배의 속도 향상을 보였습니다.
• 불량 조건 시스템: 조건수가 $10^{20}$에 달하는 매우 불량한 조건의 시나리오에서, 많은 크릴로프 솔버와 그 전처리된 버전들은 반복 제한 내에 수렴하지 못하거나 큰 상대 오차를 생성하며 실패했습니다. ROR-BK는 이러한 경우에도 성공적으로 수렴했으며, 종종 더 낮은 상대 오차를 달려냈습니다.
• 실제 응용: 노이즈가 있는 데이터와 심각하게 미결정된 시스템을 포함하는 영상 재구성 문제(평행 빔 토모그래피 및 MRI)에 대해 방법을 테스트했습니다. ROR-BK는 다른 솔버들이 불안정성이나 실패를 겪는 시나리오에서 특히 뛰어난 PSNR(Peak Signal-to-Noise Ratio) 및 SSIM(Structural Similarity Index) 성능을 보여주었습니다.

의의 및 주장
본 논문은 ROR-BK가 명시적인 전처리기 없이도 불량한 조건의 행렬 $A$를 해결하는 데 있어 유망한 대안을 제공한다고 주장합니다. 저자들은 전처리기가 행렬의 조건수를 줄이는 것을 목표로 하지만, 문제 자체의 조건수를 줄이지는 못하며 오히려 수치적 불안정성을 유발할 수 있다고 주장합니다. 시스템을 블록으로 분할하고 효과적 직교성과 정규화를 활용함으로써, ROR-BK는 공변 방정식(covariant equations)을 잠재적으로 조건이 좋은 하위 문제들로 분산시킵니다.

저자들은 이 방법을 정방 행렬(square), 과결정, 미결정 시스템을 위한 견고한 솔버로 포지셔닝합니다. 또한, 표준 전처리 기법이 피벗 붕괴나 계수 결핍으로 인해 실패하는 경우, GMRES와 같은 다른 반복법을 가속화하기 위한 pre-solver 또는 내부 반복으로서의 유용성을 제안합니다. 이 연구는 잔차 기반의 동적 특성과 직교성 샘플링의 결합이 높은 조건수의 선형 시스템에서 빠르고 안정적인 수렴을 제공하는 단순하면서도 효과적인 메커니즘임을 강조합니다.