A1204
Title: Optimal iterative algorithms for structured PCA with invariant noise
Authors: Rishabh Dudeja - University of Wisconsin--Madison (United States) [presenting]
Songbin Liu - Chinese Academy of Sciences (China)
Junjie Ma - Chinese Academy of Sciences (China)
Abstract: The problem of recovering a low-rank signal matrix is considered from a noisy observed matrix corrupted with additive noise. When the noise matrix is i.i.d. Gaussian, a rich line of work has characterized the information-theoretic limits for this problem and determined the smallest possible estimation error achievable by computationally efficient estimators. The i.i.d. noise model constrains the eigenvalue spectrum of the observed matrix to follow the semi-circle law, which may not accurately represent all datasets. A flexible generalization of the i.i.d. Gaussian noise model, known as the rotationally invariant noise model, is studied, which can capture noise spectrums beyond the semi-circle law. A new class of approximate message-passing algorithms is developed for this problem, and their dynamics are characterized. These algorithms leverage prior knowledge about the noise and signal structures by iteratively applying non-linear denoisers to the eigenvalues of the observed matrix and the previous iterates. The optimal choices are identified for these denoisers, and evidence is provided, suggesting that the resulting algorithm is a natural candidate for the optimal computationally efficient algorithm by showing that it achieves the smallest possible estimation error among a broad class of iterative algorithms under a given iteration budget.
