# Sparse CCA: Adaptive Estimation and Computational Barriers

arXiv: https://arxiv.org/abs/1409.8565 · HTML: https://mlsanity.com/paper/1409.8565/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2014.

## Built on by (most cited first, 25 of 25)

- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [Oja's Algorithm for Streaming Sparse PCA](https://mlsanity.com/paper/2402.07240/) (2024)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Sparse GCA and Thresholded Gradient Descent](https://mlsanity.com/paper/2107.00371/) (2021)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [Generalized Eigenvalue Problems with Generative Priors](https://mlsanity.com/paper/2411.01326/) (2024)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [CLCLSA: Cross-omics Linked embedding with Contrastive Learning and Self Attention for multi-omics integration with incomplete multi-omics data](https://mlsanity.com/paper/2304.05542/) (2023)
- [Sparse Partial Least Squares for Coarse Noisy Graph Alignment](https://mlsanity.com/paper/2104.02810/) (2021)
- [ℓ1-norm constrained multi-block sparse canonical correlation analysis via proximal gradient descent](https://mlsanity.com/paper/2201.05289/) (2022)
- [Multi-view information fusion using multi-view variational autoencoders to predict proximal femoral strength](https://mlsanity.com/paper/2210.00674/) (2022)
- [Federated Sufficient Dimension Reduction Through High-Dimensional Sparse Sliced Inverse Regression](https://mlsanity.com/paper/2301.09500/) (2023)
- [Do algorithms and barriers for sparse principal component analysis extend to other structured settings?](https://mlsanity.com/paper/2307.13535/) (2023)
- [SGUQ: Staged Graph Convolution Neural Network for Alzheimer's Disease Diagnosis using Multi-Omics Data](https://mlsanity.com/paper/2410.11046/) (2024)
- [Nonlinear Sparse Generalized Canonical Correlation Analysis for Multi-view High-dimensional Data](https://mlsanity.com/paper/2502.18756/) (2025)
- [Provable Affine Identifiability of Nonlinear CCA under Latent Distributional Priors](https://mlsanity.com/paper/2510.04758/) (2025)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms](https://mlsanity.com/paper/2202.04061/) (2022)
- [Provable Subspace Identification of Nonlinear Multi-view CCA](https://mlsanity.com/paper/2602.23785/) (2026)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)

## Abstract (arXiv)

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.