SPARSE CCA: ADAPTIVE ESTIMATION AND COMPUTATIONAL BARRIERS

• 成果类型: Article
• 署名作者: Gao, Chao; Ma, Zongming; Zhou, Harrison H.
• 署名单位: University of Chicago; University of Pennsylvania; Yale University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/16-AOS1519
• 发表日期: 2017
• 页码: 2074-2101
• 关键词: principal-components; Lasso; rates; PCA

摘要

Canonical correlation analysis is a classical technique for exploring the relationship between two sets of variables. It has important applications in analyzing high dimensional datasets originated from genomics, imaging and other fields. This paper considers adaptive minimax and computationally tractable estimation of leading sparse canonical coefficient vectors in high dimensions. Under a Gaussian canonical pair model, we first establish separate minimax estimation rates for canonical coefficient vectors of each set of random variables under no structural assumption on marginal covariance matrices. Second, we propose a computationally feasible estimator to attain the optimal rates adaptively under an additional sample size condition. Finally, we show that a sample size condition of this kind is needed for any randomized polynomial-time estimator to be consistent, assuming hardness of certain instances of the planted clique detection problem. As a byproduct, we obtain the first computational lower bounds for sparse PCA under the Gaussian single spiked covariance model.