A Sketched Generalized Krylov Subspace Method for Large-Scale Regularization

기술 요약: 대규모 정규화를 위한 스케치된 일반화된 크릴로프 부공간 방법 (A Sketched Generalized Krylov Subspace Method)

문제 정의
본 논문은 행렬 $A$가 심각하게 불량 조건(ill-conditioned)이고 $b$에 노이즈가 포함된 형태의 대규모 불량 설정 최소제곱 문제 $\min_{x} \|Ax - b\|_2^2$를 다룹니다. 해를 안정화하기 위해 티코노프 정규화(Tikhonov regularization)가 사용되며, 이는 다음과 같은 페널티 문제를 유도합니다:
$$\min_{x \in \mathbb{R}^n} \left\{ \|Ax - b\|_2^2 + \lambda \|Lx\|_2^2 \right\},$$
여기서 $L$은 사전 정보를 인코딩하는 일반적인 정규화 행렬입니다. 표준 형태의 티코노프($L=I$)를 위한 효율적인 방법들은 존재하지만, 일반적인 $L$을 다루는 것은 계산적으로 매우 까다롭습니다. 일반화된 크릴로프 부공간(Generalized Krylov Subspace, GKS) 방법 [28]은 티코노프 범함수의 그래디언트를 사용하여 탐색 공간을 확장함으로써 일반적인 $L$을 처리하도록 제안되었습니다. 그러나 부공간 차원이 증가함에 따라, GKS는 두 가지 결정적인 계산 병목 현상에 직면합니다:

1. Thin QR 분해: 매 반복마다 투영된 행렬 $AV_k$와 $LV_k$의 QR 분해를 업데이트하는 작업.
2. 재직교화(Reorthogonalization): 수치적 안정성을 유지하기 위해 새로운 기저 벡터를 이전의 모든 열에 대해 명시적으로 재직교화하는 작업은 전체 내적 계산을 필요로 합니다.

이러한 연산들은 반복 횟수와 문제의 크기에 따라 불리하게 스케일링되어, 대규모 역문제(inverse problems)에 대한 GKS의 확장성을 제한합니다.

방법론: 스케치된 GKS (sGKS)
저자들은 스케칭(무작위 차원 축소)을 활용하여 가장 비용이 많이 드는 단계들을 가속화하면서도 근사 품질을 보존하는 GKS 방법의 무작위 변형인 sGKS를 제안합니다. 이 방법론은 두 가지 주요 관찰에 기초합니다:

1. 명시적 재직교화의 제거: 저자들은 GKS 알고리즘이 (선형 시스템을 위한 클래식한 아노몰디/란초스 관계에 의존하는 고전적 크릴로프 방법과 달리) 핵심 단계에서 기저 벡터의 직교성에 본질적으로 의존하지 않는다는 점을 관찰했습니다. 결과적으로, sGKS는 기저의 명시적 재직교화 과정을 건너뜁니다. sGks는 직교 기저 $V_k$를 유지하는 대신, 가공되지 않은(raw) 그래디언트 벡터들을 추가하여 형성된 비직교 기저 $W_k$를 유지합니다. 이를 통해 $O(d_k^2 n)$의 재직교화 비용을 제거합니다 (여기서 $d_k$는 부공간 차원입니다).

2. 투영된 문제에 대한 Sketch-and-Solve: 투영된 티코노프 문제의 해결 및 QR 분해 업데이트 비용을 줄이기 위해, sGKS는 스케칭 연산자 $S_A$와 $S_L$을 사용합니다.

   • 투영된 최소제곱 문제는 전체 $A W_k$ 및 $L W_k$ 대신 압축된 행렬 $S_A A W_k$ 및 $S_L L W_k$ 상에서 해결됩니다.
   • QR 분해는 $s \times d_k$ 크기의 이러한 스케치된 행렬들에 대해 수행되며, 랭크-원 확장(rank-one extensions)을 통해 점진적으로 업데이트됩니다.
   • 사용되는 스케칭 연산자는 무작위 부분 추출 트랜스폼(Subsampled Randomized Trigonometric Transforms, SRTT)인 Oblivious Subspace Embeddings이며, 이는 부공간 자체가 아닌 부공간 차원에만 의존합니다.

주요 기여

• 알고리즘 설계: 일반 형태의 티코노프 정규화를 위한 GKS 프레임워크에 무작위 스케칭을 통합한 sGKS의 개발.
• 이론적 분석:
  • 동등성: 스케칭이 투영된 해결 과정에서 생략될 경우, sGKS가 수학적으로 표준 GKS와 동일한 반복값(iterates)을 생성함을 증명했습니다 (Proposition 1).
  • 준최적성(Quasi-Optimality): 스케칭이 적용될 때, 이 방법이 준최적의 잔차 노름(residual norms)을 산출하며, 오차가 스케칭 연산자의 임베딩 품질($\epsilon$)에 의해 제어됨을 입증했습니다 (Proposition 2).
  • 반복 정밀화(Iterative Refinement): 기저의 직교성 상실이 심각해지는 경우(수치적 랭크 결핍으로 이어지는 경우), 투영된 해결 단계에 소수의 반복 정밀화(IR) 단계를 포함하면 기저의 스펙트럼 특성을 복구하고 스케치되지 않은 방법의 전체 정확도를 회복할 수 있음을 보여줍니다.
• 계산 효율성: 비싼 풀 랭크(full-rank) QR 업데이트와 재직교화를 압축된 행렬에 대한 저렴한 연산으로 대체함으로써 반복당 비용을 줄였습니다.

수치 결과
저자들은 네 가지 대규모 역문제에 대해 sGKS를 평가했습니다:

1. 이미지 디블러링(Image Deburring): 다양한 스케치 차원($s$)을 사용한 sGKS는 표준 GKS와 대등한 재구성 품질을 달exp합니다. 더 큰 $s$는 GKS와 거의 구별할 수 없는 수렴 궤적을 보이는 반면, 더 작은 $s$는 약간 더 높은 최종 오차를 보이지만 더 빠른 수렴을 보입니다.
2. X-선 CT 재구성: $n=250,000$개의 미지수와 대규모 정규화 연산자($p \approx 500,000$)를 가진 문제에서, sGKS는 GKS의 재구성 정확도(RRE $\approx 0.183$)와 일치하면서도 실제 실행 시간(wall-clock time)을 크게 단축했습니다. 이러한 속도 향상은 재직교화를 제거하고 QR 업데이트 비용을 $O(p)$에서 $O(s)$로 줄인 데서 기인합니다.
3. 지진파 도달 시간 토모그래피(Seismic Travel-Time Tomography): 희소한 과결정 시스템(overdetermined system)에서 sGKS는 정확도와 속도 모두에서 하이브리드 LSQR 방법을 능가합니다. 여기서 표준 GKS 대비 속도 향상은 완만하지만(그래디언트 계산이 지배적이므로), sGKS는 LSQR 변형들보다 우수한 재구성 품질을 유지하면서도 10%의 시간 단축을 제공합니다.
4. 동적 CT(Dynamic CT): 거대한 정규화 연산자를 가진 시공간(space-time) 정식화에서, QR 및 재직교화 비용은 표준 GKS 런타임의 지배적인 요소입니다. 여기서 sGKS는 표준 GKS 대비 3배의 속도 향상을 달성했습니다. 반복 정밀화(IR)를 포함하면 sGKS는 스케치되지 않은 GKS의 정확한 수렴 궤적과 최적의 정규화 파라미터를 회복할 수 있는 반면, IR이 없는 sGKS는 약간 더 높은 오차에서 정체됩니다.

의의 및 주장
본 논문은 sGKS가 일반 행렬을 사용하는 대규모 정규화를 위한 확장 가능한 대안이라고 주장합니다. 그 의의는 다음과 같습니다:

• 확장성: 기존 GKS를 매우 큰 문제에 적용하는 것을 제한했던 계산적 병목 현상(재직교화 및 풀 랭크 QR 업데이트)을 제거합니다.
• 정확도 보존: 원래 방법의 재구성 품질을 유지하며, 기저의 직교성이 상실되더라도 반복 정밀화를 통해 전체 정확도를 회복할 수 있다는 이론적 보증과 경험적 증거를 제시합니다.
• 범용성: 제안된 방식은 특정 스케칭 연산자의 선택에 독립적이며, 표준 형태의 문제뿐만 아니라 일반적인 정규화 행렬 $L$에 적용 가능합니다.

저자들은 sGKS가 속도와 정확도 사이의 트레이드오프를 조절하기 위한 스케칭 파라미터($s$)를 도입하지만, 표준 투영법이 계산적으로 불가능한 대규모 역문제를 해결하기 위한 견고한 프레임워크를 제공한다고 결론짓습니다. 향례 연구로는 적응형 스케치 차원 선택 및 비선형 역문제로의 확장이 제안되었습니다.