An NPDo Approach for Principal Joint SVD-type Block Diagonalization

기술 요약: 주된 결합 SVD 형식 블록 대각화를 위한 NPDo 접근법

문제 정의
본 논문은 주된 결합 SVD 형식 블록 대각화 (pjbsvd) 문제를 다룹니다. $N$개의 행렬 $B_\ell \in \mathbb{C}^{n_1 \times n_2}$가 주어졌을 때, 각각 $n_1 \times k$ 및 $n_2 \times k$ 차원을 갖는 직교 행렬 쌍 $(U, V)$를 찾는 것이 목적입니다 (여기서 $1 \le k \le \min\{n_1, n_2\}$). 이때 변환된 행렬 $U^H B_\ell V$가 동시에 그리고 최적으로 지정된 블록 대각 구조에 근접하도록 합니다.

표준 결합 SVD(여기서 $k = \min\{n_1, n_2\}$이고 블록은 $1 \times 1$임) 와 달리, pjbsvd 는 $k < \min\{n_1, n_2\}$를 허용하므로 오직 주성분만 관심 있는 대규모 문제에 적합합니다. 또한, 블록 구조는 $k$의 분할 $\tau_k = (k_1, \dots, k_t)$로 정의됩니다. 구체적인 목표는 모든 행렬에 걸쳐 블록 대각 부분의 집단적 "질량"(프로베니우스 노름의 제곱) 을 최대화하는 것입니다:
$$\max_{(U,V) \in \text{St}(k,n_1) \times \text{St}(k,n_2)} f(U, V) := \sum_{\ell=1}^N \| \text{BDiag}_{\tau_k}(U^H B_\ell V) \|_F^2$$
여기서 $\text{St}(k, n)$은 복소수 스테ifel 다양체를 나타냅니다. 특수한 경우로는 주된 결합 SVD(pjsvd)(모든 $k_i=1$) 와 주된 결합 압축($t=1$) 이 포함됩니다.

방법론
저자들은 NPDo(직교 극분해에 직교 극인자 의존성을 수반하는 비선형 극분해) 기반의 수치적 접근법을 제안합니다. 이 방법은 다음과 같은 이론적 및 알고리즘적 프레임워크에 의존합니다:

1. KKT 조건 및 극분해: 목적 함수의 최적성 조건은 직교 인자 $U$와 $V$에 의존하는 행렬 값 함수 $H_1(U, V)$ 및 $H_2(U, V)$를 포함하는 두 개의 결합된 극분해 방정식으로 이어집니다.
2. 교대 SCF(ASCF) 반복: 핵심 알고리즘 (알고리즘 3.1) 은 교대 자기일관장 (SCF) 반복을 통해 이러한 결합된 방정식을 풉니다. 각 단계에서 알고리즘은 기울기 행렬 $H_1$ 및 $H_2$의 직교 극인자를 계산하여 $U$와 $V$를 업데이트합니다.
   • 야코비형 업데이트: 이전 반복의 값에 기반하여 $U$와 $V$를 동시에 업데이트합니다.
   • 가우스 - 자이델형 업데이트: 동일한 반복 내에서 먼저 $U$를 업데이트한 후, 새로운 $U$를 사용하여 $V$를 업데이트합니다.
3. 가속화 (LOCG): 효율성을 향상시키기 위해 저자들은 국소 최적 켤레 기울기 (LOCG) 가속화 (알고리즘 3.2) 를 도입합니다. 이는 현재 반복점과 잔차 기울기에 의해 생성된 축소 부분공간을 구성하고, 이 부분공간 내에서 문제의 더 작은 버전을 풀며, 그 해를 다시 투영하는 과정을 포함합니다.
4. 복소수 대 실수: 공식은 복소수 스테ifel 다양체에 대해 제시되었으나, 변환 없이 실수 행렬에 직접 적용될 수 있음이 지적됩니다.

주요 기여

• 공식화: 본 논문은 부분/주된 결합 SVD 형식 블록 대각화 문제를 공식화하여, 기존 결합 SVD 개념을 출력 차원 $k$가 입력 차원보다 작고 블록이 $1 \times 1$보다 클 수 있는 경우로 확장합니다.
• 알고리즘 개발: 교대 SCF 반복을 활용하여 이 특정 문제에 맞춘 NPDo 접근법을 도입합니다. 저자들은 두 가지 변형 (야코비 및 가우스 - 자이델) 과 가속화된 LOCG 버전을 제공합니다.
• 수렴 분석:
  • 가우스 - 자이델: 가우스 - 자이델형 ASCF 반복이 목적 함수가 각 단계에서 단조 증가하면서 정상점에 전역 수렴함을 증명합니다.
  • 야코비: 야코비 경우 목적 함수의 단조 증가가 보장되지는 않지만, 저자들은 중간 쌍의 수열의 수렴을 분석하고 특정 조건 하에서 정상점으로의 수렴을 보입니다.
  • 확장: 수렴 이론은 특정 연속성 및 기울기 성질을 만족하는 스테ifel 다양체 위의 더 일반적인 최적화 문제에 적용 가능함이 입증되었습니다.
• 수치적 효율성: 제안된 방법들은 대규모 행렬을 효율적으로 처리하도록 설계되었으며, 일반적인 목적의 다양체 최적화 패키지의 일반적인 한계인 복잡한 문제를 실수 문제로 변환할 필요가 없습니다.

결과
무작위로 생성된 데이터셋에 대해 다양한 노이즈 수준 ($\eta$) 과 차원 ($n$은 최대 1000) 으로 수치 실험이 수행되었습니다.

• 효과성: 결과 행렬 $U^H B_\ell V$의 히트맵은 알고리즘이 행렬 질량을 지정된 블록 대각 구조로 성공적으로 집중시킴을 확인시켜 줍니다.
• 수렴: 모든 방법이 $10^{-8}$ 미만의 KKT 잔차를 달성했습니다. 가속화된 버전 (accNPDo) 은 일관되게 가장 작은 잔차를 보였습니다.
• 성능:
  • LOCG 가속화된 버전 (accNPDo) 은 특히 더 큰 문제 크기의 경우 표준 NPDo 보다 훨씬 빨랐습니다.
  • 특정 경우인 pjsvd(블록 크기 $1 \times 1$) 에서는 가우스 - 자이델 변형이 야코비 변형보다 현저히 빨랐습니다. 그러나 일반적인 블록 대각화 (pjbsvd) 의 경우 가우스 - 자이델과 야코비 간의 성능 차이는 덜 두드러졌습니다.
  • 목적 함수 값은 방법에 따라 서로 다른 정상점으로 수렴했는데, 이는 문제의 비볼록성을 나타냅니다.

의의 및 주장
저자들은 이 작업을 범용 최적화 기법이 아닌 특수화된 수치 선형대수 접근법으로 위치시킵니다. 그들은 문제의 특정 구조 (스테ifel 다양체 위의 결합된 트레이스의 합) 를 활용함으로써 NPDo 접근법이 다음과 같은 이점을 제공한다고 주장합니다:

1. 간단함과 임베딩 가능성: 알고리즘은 구현이 직관적이며 대규모 애플리케이션에 통합하기에 적합합니다.
2. 견고성: 가우스 - 자이델 변형은 단조적인 목적 함수 개선을 보장하는 전역 수렴성을 제공합니다.
3. 확장성: $k \ll \min\{n_1, n_2\}$인 경우를 처리할 수 있는 능력은 고차원 데이터에서 주성분을 추출해야 하는 현대의 빅데이터 응용에 이 방법을 실용적으로 만듭니다.
4. 변환 회피: 기존 많은 솔버들이 복소수 다양체 문제를 실수 문제로 변환해야 하는 것과 달리, 이 접근법은 복소수 스테ifel 다양체 위에서 직접 작동합니다.

본 논문은 현재 공식이 $U$와 $V$에 대해 동일한 열 수와 대칭적인 블록 분할을 강제하지만, 근본적인 이론과 방법은 더 일반적인 설정에서도 유효하다고 결론지으며, 이러한 일반화에 대한 실제 응용은 아직 탐구되어야 한다고 덧붙입니다.