Repository logo
 

Sparse principal component analysis via axis-aligned random projections


Type

Article

Change log

Authors

Wang, T 
Samworth, RJ 

Abstract

We introduce a new method for sparse principal component analysis, based on the aggregation of eigenvector information from carefully-selected axis-aligned random projections of the sample covariance matrix. Unlike most alternative approaches, our algorithm is non-iterative, so is not vulnerable to a bad choice of initialisation. We provide theoretical guarantees under which our principal subspace estimator can attain the minimax optimal rate of convergence in polynomial time. In addition, our theory provides a more refined understanding of the statistical and computational trade-off in the problem of sparse principal component estimation, revealing a subtle interplay between the effective sample size and the number of random projections that are required to achieve the minimax optimal rate. Numerical studies provide further insight into the procedure and confirm its highly competitive finite-sample performance.

Description

Keywords

Dimensionality reduction, Eigenspace estimation, Ensemble learning, Sketching, Statistical and computational trade-offs

Journal Title

Journal of the Royal Statistical Society. Series B: Statistical Methodology

Conference Name

Journal ISSN

1369-7412
1467-9868

Volume Title

82

Publisher

Oxford University Press (OUP)
Sponsorship
Engineering and Physical Sciences Research Council (EP/N014588/1)
Engineering and Physical Sciences Research Council (EP/P031447/1)
Engineering and Physical Sciences Research Council (EP/J017213/1)
The research of the first and third authors was supported by an Engineering and Physical Sciences Research Council (EPSRC) grant EP/N014588/1 for the centre for Mathematical and Statistical Analysis of Multimodal Clinical Imaging. The second and third authors were supported by EPSRC Fellowship EP/J017213/1 and EP/P031447/1, and grant RG81761 from the Leverhulme Trust.