일반화된 1계 급수 행렬 감지를 위한 교대 최소화: 무작위 초기화로부터의 정확한 예측

초록 우리는 비선형적으로 변환되고 잡음에 의해 손상된 i.i.d. 가우시안, 1계 측정값을 가진 1계 행렬의 인자를 추정하는 문제를 고려한다. 비선형성에 대한 두 가지 전형적인 선택을 고려하여, 우리는 무작위 초기화에서 시작하는 이 비볼록 최적화 문제에 대한 자연스러운 교대 업데이트 규칙의 수렴 특성을 연구한다. 우리는 고차원 문제에서도 정확한 결정론적 일단계 재귀를 유도하여 알고리즘의 샘플 분할 버전의 샤프한 수렴 보장을 제시한다. 특히 무한 샘플 모집단 업데이트는 유용한 정보를 제공하지 않으며 단일 단계에서의 정확한 복구를 제안하지만, 알고리즘—및 우리의 결정론적 일단계 예측—은 무작위 초기화에서 기하급수적으로 빠르게 수렴한다. 우리의 샤프한 비점근 해석은 비선형성과 잡음 수준이 수렴 행동에 미치는 영향을 포함하여 이 문제의 여러 다른 세부적인 특성을 드러낸다. 기술적인 수준에서, 우리의 결과는 각 반복이 n개의 관찰로 수행될 때 n^-1/2의 순서 내의 변동 속에서 우리의 결정론적 일단계 업데이트로 경험적 오류 재귀를 예측할 수 있음을 보여줌으로써 가능해진다. 우리의 기술은 고차원 M-추정에 관한 문헌에서 기원한 Leave-One-Out 도구를 활용하며 무작위 데이터로 다른 고차원 최적화 문제에서 무작위 초기화로부터 복잡한 반복 알고리즘을 정확하게 분석할 수 있는 경로를 제공한다.