대규모 고유공간 추정을 위한 부분표본 Davis-Kahan 경계
A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation
한국어 초록
Davis-Kahan 정리는 스펙트럼 분석의 기본 도구로, 대칭 행렬과 그 섭동(perturbation) 행렬의 고유공간(eigenspace) 사이의 거리를 정량적으로 제어할 수 있게 해 준다. 그러나 행렬의 차원이 클 경우 주요 고유벡터를 계산하는 데 드는 비용이 커서, 현대의 대규모 응용에서 스펙트럼 기법을 실제로 활용하는 데 제약이 따른다. 본 논문은 이 문제를 해결하기 위해 독립 베르누이 샘플링(independent Bernoulli sampling) 기법을 제안하고, 부분표본 행렬의 주요 좌특이벡터(left singular vector)가 저랭크 대칭 행렬의 목표 부분공간을 충실하게 근사함을 증명한다. 핵심 결과는 샘플링 확률에 직접 의존하는 명시적인 오차 경계를 제시하는 부분표본 Davis-Kahan 경계이다. 이 경계는 다음과 같은 트레이드오프를 보여 준다. 계산 비용은 샘플링 확률에 선형적으로 비례하여 증가하는 반면, 통계적 오차는 샘플링 확률의 제곱근에 반비례하여 감소한다. 따라서 본 결과는 Davis-Kahan 정리를 부분표본 설정으로 확장하여, 대규모 대칭 행렬에 대한 확장 가능한 스펙트럼 분석을 가능하게 한다.
원문 초록
The Davis-Kahan theorem is a fundamental tool in spectral analysis, providing quantitative control over the distance between the eigenspaces of a symmetric matrix and its perturbation. However, when the matrix dimension is large, computing leading eigenvectors is computationally expensive, limiting the practical use of spectral methods in modern large-scale applications. This paper addresses this problem by proposing an independent Bernoulli sampling scheme and proves that the leading left singular vectors of the subsampled matrix faithfully approximate the target subspace of a low-rank symmetric matrix. Our main result is a subsampled Davis-Kahan bound that gives an explicit error bound depending directly on the sampling probability. The bound reveals the trade-off: the computational cost scales linearly with the sampling probability, while the statistical error scales as the inverse square root of the sampling probability. Our result thus extends the Davis-Kahan theorem to the subsampled setting, enabling scalable spectral analysis of large-scale symmetric matrices.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.09211v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.