Randomized Methods for Kernelized DMD

기술 요약: 커널화된 DMD를 위한 무작위 기법 (Randomized Methods for Kernelized DMD)

문제 정의
동적 모드 분해(Dynamic Mode Decomposition, DMD)는 비선형 시스템의 순차적인 스냅샷으로부터 지배적인 역학을 추출하는 데 사용되는 데이터 기반 방법이다. 그러나 높은 상태 차원($N$)과 많은 수의 스냅 snapshots ($M$)를 가진 대규모 데이터셋에 DMD를 적용하는 것은 상당한 계산적 병목 현상을 야기한다. 커널 트릭(kernel trick)을 사용하여 큰 $N$ 문제를 완화하는 커널화된 DMD(Kernelized DMD, KDMD)는 새로운 제약을 도입한다. 즉, 이 알고리즘은 두 개의 $M \times M$ 고유값 문제(eigenproblems)를 풀어야 한다. 이는 스냅샷 수에 따라 성능이 저하되는 결과를 초래하여, 긴 궤적 데이터셋에 대한 KDMD의 적용 가능성을 제한한다. Random Fourier Features(RFF)나 oASIS 알고리즘과 같은 기존의 무작위 접근 방식들은 느린 수렴 속도나 수치적 불안정성 문제를 겪는다. 구체적으로, oASIS는 대각 피보팅(diagonal pivoting)에 의존하는데, 이는 특정 반례에서 정확한 근사치를 반환하는 데 실패할 수 있으며, 피보티드 부분 숄레스키 분해(pivoted partial Cholesky factorization)에 비해 수치적으로 불안정하다.

방법론
본 논문은 계산을 가속화하고 수치적 안정성을 향상시키기 위해 RPCholesky 알고리즘(Randomly Pivoted Partial Cholesky)을 KDMD 프레임워크에 통합할 것을 제안한다.

1. RPCholesky를 통한 커널 근사: 전체 $M \times M$ 그라미안 행렬(Gramian matrix) $G$를 계산하고 관련 고유값 문제를 푸는 대신, 저자들은 RPCholesky를 사용하여 저계수 근사 $G \approx FF^*$를 생성한다. 이 방법은 순수하게 탐욕적인(greedy) 대각 피보팅 전략 대신, 잔차 행렬의 대각 요소로부터 유도된 확률 분포를 기반으로 피벗 인덱스 $I = \{i_1, \dots, i_S\}$를 선택한다. 이는 큰 대각 요소의 "활용(exploitation)"과 더 작은 요소의 "탐색(exploration)" 사이의 균형을 맞춘다.
2. 알고리즘 통합: 제안된 무작위 샘플링 기반 KDMD(Algorithm 2)는 $G$의 전체 고유값 분해를 더 작은 $S \times S$ 행렬 $F^*F$의 고유값 분해로 대체한다. 생성된 인자들은 축소된 커널 행렬 $\hat{K}$를 구성하고 DMD 모드 및 고유함수를 계산하는 데 사용된다.
3. 데이터 기반 잔차: 무작위 설정에서의 핵심 구성 요소는 특정 데이터 기반 잔차 공식의 유도이다. SVD 기반 DMD에서 사용되는 표준 잔차 계산은 무작위 KDMD 출력에 직접 적용할 수 없으므로, 저자들은 RP-Cholesky 실행 중에 얻은 피벗 선택 정보($A[:, I]$ 및 $G[:, I]$)를 활용하는 새로운 잔차 $r(i)$ (식 7)를 유도한다. 이를 통해 재구성 품질에 기반하여 지배적인 모드를 정렬하고 선택할 수 있다.
4. 계산 최적화: 저자들은 순차적 데이터 행렬 $X$와 $Y$에 대해 커널 행렬을 하나의 더 큰 행렬 $D = [X, Y]$로부터 조립할 수 있음을 언급한다. 이를 통해 RPCholesky 알고리즘을 $D$에 한 번만 실행하여 $G$와 $A$에 필요한 하위 블록들을 추출함으로써, 이러한 행렬들을 전체적으로 조립하는 비용을 피할 수 있다.

주요 기여

• 알고리즘 제안: 본 논문은 KDMD에 RPCholesky 알고리즘의 적용을 소개하며, oASIS 및 대각 피보팅을 사용하는 Nyström 근사에 대한 안정적인 대안을 제공한다.
• 안정성 및 정렬: 저자들은 RPCholesky가 기존의 무작위 KDMD 방법들보다 더 나은 안정성 보장을 제공함을 입증한다. 결정적으로, 유도된 데이터 기반 잔차가 DMD 모드의 의미 있는 정렬을 가능하게 함을 보여주는데, 이는 oASIS 기반 피보팅에서는 일관되지 않거나 불규칙했던 기능이다.
• 복잡도 분석: 본 논문은 무작위 KDMD 접근 방식이 $O(M^3)$ (표준 KDMD의 경우)에서 $O(SMN + S^2M + S^3)$로 계산 비용을 줄인다는 복잡도 분석을 제공한다. 여기서 $S$는 무작위 샘플의 수이다. 이는 $M$이 큰 데이터셋을 처리할 수 있게 한다.
• 잔차 공식화: 무작위 KDMD 모드를 위한 특정 잔차 메트릭을 유도하여, 전체 커널 행렬을 요구하지 않고도 지배적인 역학을 선택할 수 있게 한다.

결과
제안된 방법의 효능은 세 가지 벤치마크 문제에 대해 평가되었다:

1. 실린더 주위의 유동 (Flow Around a Cylinder): 층류 유동 시뮬레이션($N=89351, M=150$)의 압력 데이터를 사용하여, RPCholesky 기반 KDMD는 표준 DMD 및 KDMD와 시각적으로 유사한 모드를 생성하였으며, 잔차 또한 표준 KDMD와 유사했다. 반면, oASIS 방법은 동일한 거동을 반영하지 못하는 불규칙한 잔차를 생성하여 효과적인 모드 정렬을 방해했다.
2. 비강제 더핑 방정식 (Unforced Duffing Equation): 합성 데이터셋($10000 \times 7700$)을 사용한 스트레스 테스트 결과, 무작위 KDMD 알고리즘들(RPCholesky, oASIS, RFF)은 샘플 수 $S$가 증가함에 따라 유사한 상대적 재구성 오차를 달성했다. 그러나 RPCholesky 방법은 oASIS에 비해 모드 정렬에서 우수한 안정성을 보여주었다. 계산 시간 분석을 통해 모든 무작위 변형들이 $S$에 대해 유사하게 스케일링됨을 확인했다.
3. 해수면 온도 데이터셋: 대규모 실제 데이터셋($2276$개의 스냅샷,$10^6$개의 데이터 포인트)에 적용했을 때, RPCholesky KDMD는 지배적인 모드들을 성공적으로 식별했다. 주목할 점은, 제안된 알고리즘에 의해 생성된 모드들이 기대되는 물리적 구조(독립적인 첫 번째 모드와 그 뒤를 잇는 복소 공액 쌍)를 따랐던 반면, RFF EDMD 접근 방식는 이러한 쌍(pairwise) 정렬을 생성하는 데 실패했다는 것이다.

의의
본 논문은 RPCholesky와 KDMD의 결합이 기존 무작위 커널 방법들의 특정 안정성 및 정렬 문제를 해결한다고 주장한다. 탐욕적인 대각 피보팅을 적응형 무작위 샘플링으로 대체함으로써, 이 방법은 정보의 활용과 탐색 사이의 균형을 달성한다. 주요 의의는 KDMD가 전체 $M \times M$ 커널 행렬을 조립하거나 저장할 필요 없이, 개선된 수치적 안정성과 데이터 기반 잔차를 통한 신뢰할 수 있는 모드 선택 메커 p리즘을 갖추고 더 큰 스냅샷 수($M$)를 처리할 수 있게 한다는 점에 있다. 저자들은 이를 대규모 데이터 기반 역학 시스템 분석을 가속화하기 위한 실행 가능한 도구로 제시한다.