Finding accurate eigenvalues and eigenvectors of positive semi-definite matrices given a subspace

기술적 요약: 부분공간이 주어졌을 때 양의 준정부호 행렬의 정확한 고유값과 고유벡터 찾기

문제 제기
이 논문은 수치 선형대수의 고전적인 문제를 다룹니다: $n \times n$ 크기의 양의 준정부호 (PSD) 행렬 $A$와 $A$의 주된 고유공간을 근사하는 $k$차원 부분공간 $Q$(직교 정규 기저 행렬 $Q \in \mathbb{R}^{n \times k}$로 표현됨) 가 주어졌을 때, 어떻게 하면 고정밀도의 고유값과 고유벡터를 추출할 수 있을까요? 레이레이 - 리츠 (RR) 방법은 이 작업을 위한 표준 접근법이지만, 저자들은 $A$가 PSD 라는 특정 구조적 특성을 활용하여 계산 복잡도를 증가시키지 않고도 RR 이 제공하는 것보다 더 높은 정확도를 달성할 수 있는지 조사합니다.

방법론
이 논문은 $N$을 $A$와의 행렬 - 벡터 곱셈 비용이라고 할 때, 동일한 $O(Nk + nk^2)$의 계산 복잡도를 공유하는 세 가지 투영 기반 방법을 비교합니다:

1. 레이레이 - 리츠 (RR): 투영된 행렬 $Q^\top A Q$의 고유값을 계산하는 표준 방법입니다. 근사 고유값은 $\hat{\lambda}_i^{(RR)} = \lambda_i(Q^\top A Q)$입니다.
2. SVD 추출: 이 방법은 PSD 행렬에 대한 고유값과 특이값의 동등성을 활용합니다. 한쪽 면 투영 $AQ$의 특이값을 계산합니다. 근사 고유값은$\hat{\lambda}_i^{(SVD)} = \sigma_i(AQ)$입니다.
3. 니스트롬 (Nyström) 방법: 이 방법은 $A_{\langle Q \rangle} = AQ(Q^\top AQ)^\dagger (AQ)^\top$로 표시되는 $A$의 저차원 근사를 구성하고, 이 근사에서 고유값을 추출합니다. 근사 고유값은 $\hat{\lambda}_i^{(Nys)} = \lambda_i(A_{\langle Q \rangle})$입니다.

저자들은 $Q$를 $A$의 주된 불변 부분공간 $U_1$에 대한 $\epsilon$-근사로 모델링하여 이러한 방법들을 이론적으로 분석합니다. 그들은 섭동 분석, 슈어 여인수, 그리고 PSD 행렬의 성질을 활용하여 고유값 근사에 대한 오차 한계를 유도합니다.

주요 기여 및 이론적 결과

• 주된 고유값에 대한 정확도 계층: 이 논문은 주된 고유값 (행렬 $A$의 가장 큰 고유값에 해당하는 것들) 을 근사하는 정확도에 대한 엄격한 순서를 확립합니다. 저자들은 근사 고유값에 대해 다음 부등식을 증명합니다:
  $$\lambda_i(A) \geq \lambda_i(A_{\langle Q \rangle}) \geq \sigma_i(AQ) \geq \lambda_i(Q^\top A Q)$$
  결과적으로 절대 오차는 다음을 만족합니다:
  $$|\lambda_i(A) - \hat{\lambda}_i^{(RR)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(SVD)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(Nys)}|$$
  이는 니스트롬이 가장 정확한 추정을 제공하며, 그 다음이 SVD 추출이며, RR 이 가장 정확도가 낮음을 보여줍니다.

• 니스트롬의 고차 정확도: 저자들은 니스트롬이 RR 및 SVD 추출에 비해 고차 정확도를 달성함을 보여주는 정량적 오차 한계를 유도합니다. 구체적으로, $A$의 스펙트럼이 급격히 감소할 때 (즉, $\lambda_1 \gg \lambda_{k+1}$), 주된 고유값에 대한 니스트롬 방법의 오차는 RR 및 SVD 추출의 오차보다 $\lambda_1(A)/\lambda_{k+1}(A)$에 비례하는 인자만큼 작을 수 있습니다. 이 개선은 임의로 커질 수 있습니다.

• 후미 고유값에 대한 역전: 이 논문은 후미 (가장 작은) 고유값을 대상으로 할 때 상황이 역전된다고 지적합니다. 이 영역에서 니스트롬 방법은 성능이 저하되며, RR 이 가장 정확한 방법이 됩니다. 저자들은 이것이 부분공간 $\text{span}(AQ)$(니스트롬 및 SVD-$\tilde{U}$에서 사용됨) 이 $\text{span}(Q)$에 비해 주된 불변 부분공간 $U_1$에 대한 더 나은 근사이지만, 후미 불변 부분공간 $U_2$에 대한 더 나쁜 근사이기 때문이라고 설명합니다.

• 후미 고유값을 위한 해결책: 후미 고유값에 대한 니스트롬의 낮은 성능을 해결하기 위해, 저자들은 시프트 - 플립 (shift-and-flip) 전략을 제안합니다. 이동된 행렬 $\gamma I - A$(여기서 $\gamma \geq \lambda_{\max}(A)$) 의 주된 고유쌍을 계산함으로써, 니스트롬 방법을 적용하여 원래 행렬의 후미 고유값을 효과적으로 복원할 수 있습니다.

결과 및 수치 실험
이론적 발견은 수치 실험을 통해 검증되었습니다:

• 주된 고유값: $A$의 스펙트럼이 급격히 감소할 때 (지수적 감소), 니스트롬 방법은 RR 및 SVD 추출을 크게 능가하며, 오차 기울기는 고차 수렴을 나타냅니다. 스펙트럼이 느리게 감소할 때 (대수적 또는 선형), 니스트롬의 이점은 감소하지만 여전히 존재합니다.
• 고유벡터: 고유벡터 근사에서도 유사한 경향이 관찰됩니다. 부분공간 $\text{span}(AQ)$(니스트롬 및 SVD-$\tilde{U}$) 을 활용하는 방법은 $\text{span}(Q)$(RR 및 SVD-$Q\tilde{V}$) 에 제한된 방법들보다 더 정확한 주된 고유벡터를 제공합니다.
• 후미 고유값: 실험은 후미 고유값에 대해서는 RR 이 우월하며, 시프트 - 플립 기법이 사용되지 않는 한 니스트롬은 실패함을 확인시켜 줍니다.

의의 및 주장
이 논문은 문헌에 존재하는 명백한 불일치를 해결했다고 주장합니다: RR 은 min-max 특성화 및 부분공간 투영의 관점에서 최적임이 알려져 있지만, 이 최적성은 PSD 성질을 명시적으로 활용할 때 더 정확한 고유값 근사의 존재를 배제하지는 않습니다.

이 연구의 주요 의의는 PSD 행렬의 경우, 니스트롬 방법이 주된 고유쌍을 추출하기 위한 표준 레이레이 - 리츠 방법보다 우월한 대안이며, 추가적인 계산 비용 없이 훨씬 더 높은 정확도를 제공한다는 것을 입증한 것입니다. 저자들은 이 개선이 머신러닝의 커널 행렬이나 주성분 분석의 공분산 행렬과 같이 급격히 감소하는 스펙트럼을 가진 행렬을 다루는 응용 분야에서 특히 중요하다고 강조합니다. 논문은 이론적 한계가 실수 행렬에 대해 유도되었지만 유사한 결과가 복소수 행렬에도 성립한다고 겸손하게 언급합니다.