저순위 행렬 근사값의 빠른 계산

행렬 A가 주어졌을 때, 저순위의 좋은 근사값을 찾는 것이 종종 바람직합니다. 우리는 A가 강한 스펙트럼 특성을 가질 때, 즉 관심 있는 특이값이 A와 유사한 크기와 항목을 가진 랜덤 행렬의 특이값보다 현저하게 클 때 이러한 근사의 계산을 가속화하는 간단한 기법을 소개합니다. 우리의 기술은 A의 항목을 독립적으로 샘플링하고/또는 양자화하여 비제로 항목의 수와/또는 그 표현의 길이를 줄임으로써 계산을 가속화하는 방법입니다. 우리의 분석은 샘플링 및 양자화의 행위가 A에 독립적인 확률 변수가 0 평균과 유한 분산을 가진 랜덤 행렬 N을 추가하는 것으로 볼 수 있다는 점에 기반합니다. N이 매우 약한 스펙트럼 특성을 가질 확률이 높기 때문에, A + N에 대한 저순위 근사를 계산할 때 샘플링 및 양자화의 효과가 거의 사라짐을 증명할 수 있습니다. 우리는 Frobenius 및 2-노름 모두에서 우리의 근사의 질에 대한 높은 확률 경계를 제시합니다.