A Correlation-Gap Bound for Nonlinear Gaussian PCA
Data Structures and AlgorithmsInformation Theory
Summary
The authors look at a famous method called PCA, which is best at simplifying Gaussian data in a linear way. They study a puzzle from Mallat and Zeitouni about whether the standard PCA basis stays nearly the best even if you adaptively pick which parts to keep for each data point. The authors show that as data dimensions get very large, the usual PCA basis is almost just as good as any other choice, within a small margin that shrinks with dimension size. Their proof uses a new technique involving mathematical concepts like majorization and matroids to compare different bases rigorously.
Authors
Minbo Gao, Zhengfeng Ji, Chenghua Liu
Abstract
Principal component analysis (PCA) is optimal for the linear reconstruction of Gaussian data, a foundational property underlying its central role in algorithms and signal processing. Its nonlinear analogue, however, is notoriously subtle: in 2011, Mallat and Zeitouni conjectured that the Karhunen--Loève (KL) basis remains optimal even when the retained coordinates are chosen adaptively per sample, a property that would theoretically justify the ubiquitous pipeline of PCA followed by sparse thresholding. In this paper, we establish a $1+O(1/\sqrt{d})$-approximate version of the retained-energy form of the Mallat--Zeitouni conjecture, showing that the KL basis is within this factor of the optimal basis. This dimension-free comparison depends only on the number of retained coordinates and shows that the possible advantage of optimizing over all orthonormal bases vanishes as $d$ grows. It complements the universal-constant reconstruction-error comparison of Litvak and Tikhomirov (Ann. Appl. Probab., 2018), while providing a comparison naturally suited for algorithmic analysis. Our proof rests on a clean, conceptual reduction: we relax arbitrary rotations to a deterministic threshold bound via Schur--Horn majorization, and identify the remaining loss with the correlation gap of the rank-$d$ uniform matroid over Gaussian level sets.