Sparse CCA: Adaptive Estimation and Computational Barriers

Abstract

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. First, we 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. The result is faithful to the Gaussian models used in the paper. As a byproduct, we obtain the first computational lower bounds for sparse PCA under the Gaussian single spiked covariance model.

References in corpus (5)

• A greedy approach to sparse canonical correlation analysis
• Inferring gene-gene interactions and functional modules using sparse canonical correlation analysis
• Sparse CCA via Precision Adjusted Iterative Thresholding
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Canonical correlation coefficients of high-dimensional Gaussian vectors: finite rank case

Cited by in corpus (15)

• Statistical and computational trade-offs in estimation of sparse principal components
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Sparse CCA via Precision Adjusted Iterative Thresholding
• Minimax estimation in sparse canonical correlation analysis
• Average-case Hardness of RIP Certification
• Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
• Canonical correlation coefficients of high-dimensional Gaussian vectors: finite rank case
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Optimal link prediction with matrix logistic regression
• Statistical Limits of Convex Relaxations
• Tensor SVD: Statistical and Computational Limits
• Detection of Planted Solutions for Flat Satisfiability Problems
• Optimal Estimation of Slope Vector in High-dimensional Linear Transformation Model
• Integrative analysis of transcriptomic and metabolomic data via sparse canonical correlation analysis with incorporation of biological information