Sparse CCA: Adaptive Estimation and Computational Barriers

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.

• Publication year

  2014

• Venue

  arXiv: Methodology

• Publication date

  2014-09-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/16-AOS1519arXiv 1409.8565
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computational Lower Bounds for Community Detection on Random Graphs

  2014cited by this paper
• Minimax estimation in sparse canonical correlation analysis

  2014influential reference
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time

  2014cited by this paper
• Statistical and computational trade-offs in estimation of sparse principal components

  2014influential reference
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression

  2014cited by this paper
• Inferring gene-gene interactions and functional modules using sparse canonical correlation analysis

  2014cited by this paper
• Canonical correlation coefficients of high-dimensional normal vectors: finite rank case

  2014cited by this paper
• The Group Square-Root Lasso: Theoretical Properties and Fast Algorithms

  2013cited by this paper
• Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

  2013influential reference
• Computational Barriers in Minimax Submatrix Detection

  2013influential reference
• Sparse CCA via Precision Adjusted Iterative Thresholding

  2013cited by this paper
• Fantope Projection and Selection: A near-optimal convex relaxation of sparse PCA

  2013cited by this paper
• MINIMAX BOUNDS FOR SPARSE PCA WITH NOISY HIGH-DIMENSIONAL DATA.

  2012cited by this paper
• Optimal detection of sparse principal components in high dimension

  2012cited by this paper
• Statistical algorithms and a lower bound for detecting planted cliques

  2012cited by this paper
• Sparse PCA: Optimal rates and adaptive estimation

  2012influential reference
• Identification of human triple-negative breast cancer subtypes and preclinical models for selection of targeted therapies.

  2011cited by this paper
• Sparse Principal Component Analysis and Iterative Thresholding

  2011cited by this paper
• Scaled sparse linear regression

  2011cited by this paper
• Average-case complexity of detecting cliques

  2010cited by this paper
• Dementia induces correlated reductions in white matter integrity and cortical thickness: A multivariate neuroimaging study with sparse canonical correlation analysis

  2010cited by this paper
• Introduction to the non-asymptotic analysis of random matrices

  2010cited by this paper
• Templates for convex cone problems with applications to sparse signal recovery

  2010influential reference
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming

  2010cited by this paper
• Oracle Inequalities and Optimal Inference under Group Sparsity

  2010cited by this paper
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions

  2009cited by this paper
• A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis.

  2009cited by this paper
• Molecular Characterization of Breast Cancer with High-Resolution Oligonucleotide Comparative Genomic Hybridization Array

  2009cited by this paper
• Sparse canonical methods for biological data integration: application to a cross-platform study

  2009cited by this paper
• Sparse canonical correlation analysis for identifying, connecting and completing gene-expression networks

  2009cited by this paper
• Sparse Canonical Correlation Analysis with Application to Genomic Data Integration

  2009cited by this paper
• Sparse canonical correlation analysis

  2009cited by this paper
• Gene expression profiling of the tumor microenvironment during breast cancer progression

  2009cited by this paper
• Computational Complexity: A Modern Approach

  2009cited by this paper
• SIMULTANEOUS ANALYSIS OF LASSO AND DANTZIG SELECTOR

  2008cited by this paper
• MULTIVARIATE ANALYSIS AND JACOBI ENSEMBLES: LARGEST EIGENVALUE, TRACY-WIDOM LIMITS AND RATES OF CONVERGENCE.

  2008cited by this paper
• A greedy approach to sparse canonical correlation analysis

  2008cited by this paper
• Model selection and estimation in regression with grouped variables

  2006cited by this paper
• An Introduction to Multivariate Statistical Analysis

  2004cited by this paper
• Gene Expression Profiling for Molecular Characterization of Inflammatory Breast Cancer and Prediction of Response to Chemotherapy

  2004cited by this paper
• A Direct Formulation for Sparse PCA Using Semidefinite Programming

  2004cited by this paper
• Multivariate Analysis

  1998cited by this paper
• Assouad, Fano, and Le Cam

  1997cited by this paper
• Complexity and Real Computation

  1997cited by this paper
• Matrix computations (3rd ed.)

  1996cited by this paper
• On matrix approximation problems with Ky Fank norms

  1993cited by this paper
• Asymptotic methods in statistical theory

  1986cited by this paper
• Finite Exchangeable Sequences

  1980cited by this paper
• Perturbation bounds in connection with singular value decomposition

  1972influential reference
• An Introduction to Multivariate Statistical Analysis

  1959cited by this paper
• On the numerical solution of heat conduction problems in two and three space variables

  1956influential reference
• Relations Between Two Sets of Variates

  1936cited by this paper

• A Smooth Locally Exact Penalty Method for Optimization Problems over Generalized Stiefel Manifolds

  2026cites this paper
• MULTI-MODAL AND MULTI-REGION DISTANCE MODEL FOR NEUROIMAGING: APPLICATION TO ABCD STUDY

  2026cites this paper
• Provable Subspace Identification of Nonlinear Multi-view CCA

  2026cites this paper
• Combinatorial Sparse PCA Beyond the Spiked Identity Model

  2026cites this paper
• On optimal distinguishers for Planted Clique

  2025cites this paper
• StablePCA: Learning Shared Representations across Multiple Sources via Minimax Optimization

  2025cites this paper
• Research on Cancer Prediction Based on Feature Optimization and Multimodal Fusion

  2025cites this paper
• Nonlinear Sparse Generalized Canonical Correlation Analysis for Multi-view High-dimensional Data

  2025cites this paper
• High Dimensional Sparse Canonical Correlation Analysis for Elliptical Symmetric Distributions

  2025cites this paper
• Provable Affine Identifiability of Nonlinear CCA under Latent Distributional Priors

  2025cites this paper
• Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps

  2024cites this paper
• CLCLSA: Cross-omics linked embedding with contrastive learning and self attention for integration with incomplete multi-omics data

  2024cites this paper
• Uncertainty-induced Incomplete Multi-Omics Integration Network for Cancer Diagnosis

  2024cites this paper
• Generalized Eigenvalue Problems with Generative Priors

  2024cites this paper
• SGUQ: Staged Graph Convolution Neural Network for Alzheimer’s Disease Diagnosis using Multi-Omics Data

  2024cites this paper
• Optimal estimation of misclassification rate for two-class clustering with sub-Gaussian noises

  2024cites this paper
• De-biased sparse canonical correlation for identifying cancer-related trans-regulated genes

  2024influential citation
• CoCA: Cooperative Component Analysis

  2024cites this paper
• A Multilinear Least-Squares Formulation for Sparse Tensor Canonical Correlation Analysis

  2024cites this paper
• Oja's Algorithm for Streaming Sparse PCA

  2024cites this paper
• Sparse PCA Beyond Covariance Thresholding

  2023cites this paper
• Federated Sufficient Dimension Reduction Through High-Dimensional Sparse Sliced Inverse Regression

  2023cites this paper
• On Sparse Canonical Correlation Analysis

  2023cites this paper
• On statistical inference with high-dimensional sparse CCA.

  2023cites this paper
• Sparse higher order partial least squares for simultaneous variable selection, dimension reduction, and tensor denoising

  2023cites this paper
• Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials

  2023cites this paper
• Computational Inference for Directions in Canonical Correlation Analysis

  2023cites this paper
• Do Algorithms and Barriers for Sparse Principal Component Analysis Extend to Other Structured Settings?

  2023cites this paper
• Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles

  2023cites this paper
• CLCLSA: Cross-omics Linked embedding with Contrastive Learning and Self Attention for multi-omics integration with incomplete multi-omics data

  2023cites this paper
• Hardness Self-Amplification: Simplified, Optimized, and Unified

  2023cites this paper
• Optimal Sparse Sliced Inverse Regression via Random Projection

  2023influential citation
• Branch-and-bound algorithm for optimal sparse canonical correlation analysis

  2023cites this paper
• CLCLSA: Cross-omics Linked embedding with Contrastive Learning and Self Attention for multi-omics integration with incomplete multi-omics data

  2023cites this paper
• Planted Bipartite Graph Detection

  2023cites this paper
• Efficient and Fast Joint Sparse Constrained Canonical Correlation Analysis for Fault Detection

  2022cites this paper
• Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis

  2022cites this paper
• Trace Lasso Regularization for Adaptive Sparse Canonical Correlation Analysis via Manifold Optimization Approach

  2022cites this paper
• Higher degree sum-of-squares relaxations robust against oblivious outliers

  2022influential citation
• Multi-view information fusion using multi-view variational autoencoder to predict proximal femoral fracture load

  2022cites this paper
• Canonical Correlation Analysis and Partial Least Squares for identifying brain-behaviour associations: a tutorial and a comparative study.

  2022cites this paper
• (cid:96) 0 -S PARSE C ANONICAL C ORRELATION A NALYSIS

  2022influential citation
• Optimal estimation for lower bound of the packing number

  2022cites this paper
• Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms

  2022cites this paper
• $\ell_1$-norm constrained multi-block sparse canonical correlation analysis via proximal gradient descent

  2022cites this paper
• A SIEVE STOCHASTIC GRADIENT DESCENT ESTIMATOR FOR ONLINE NONPARAMETRIC REGRESSION IN SOBOLEV ELLIPSOIDS.

  2021cites this paper
• A Note on Sparse Generalized Eigenvalue Problem

  2021cites this paper
• Optimal Convex Lifted Sparse Phase Retrieval and PCA With an Atomic Matrix Norm Regularizer

  2021cites this paper
• An Efficient Convex Formulation for Reduced-Rank Linear Discriminant Analysis in High Dimensions

  2021cites this paper
• Advanced topics in Sliced Inverse Regression

  2021cites this paper
• Estimation of canonical correlation directions: From Gaussian to sub-Gaussian population

  2021cites this paper
• Fault Detection Based on Canonical Correlation Analysis with Rank Constrained Optimization

  2021cites this paper
• Inferring Hidden Structures in Random Graphs

  2021cites this paper
• Random Subgraph Detection Using Queries

  2021cites this paper
• On Support Recovery With Sparse CCA: Information Theoretic and Computational Limits

  2021influential citation
• Logspace Reducibility From Secret Leakage Planted Clique

  2021cites this paper
• Sparse reduced‐rank regression for exploratory visualisation of paired multivariate data

  2021cites this paper
• Average-Case Communication Complexity of Statistical Problems

  2021cites this paper
• Sparse GCA and Thresholded Gradient Descent

  2021influential citation
• A Penalty-Free Infeasible Approach for a Class of Nonsmooth Optimization Problems Over the Stiefel Manifold

  2021cites this paper
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors

  2021cites this paper
• Sample canonical correlation coefficients of high-dimensional random vectors with finite rank correlations

  2021cites this paper
• High-dimensional sparse single–index regression via Hilbert–Schmidt independence criterion

  2021influential citation
• Sparse Partial Least Squares for Coarse Noisy Graph Alignment

  2021cites this paper
• Statistical and Computational Rates in Graph Logistic Regression

  2020cites this paper
• Agnostic Estimation for Misspecified Phase Retrieval Models

  2020cites this paper
• Permutation inference for canonical correlation analysis

  2020cites this paper
• Sample canonical correlation coefficients of high-dimensional random vectors: Local law and Tracy–Widom limit

  2020cites this paper
• Statistical inference in high-dimensional matrix models

  2020cites this paper
• An Inexact Manifold Augmented Lagrangian Method for Adaptive Sparse Canonical Correlation Analysis with Trace Lasso Regularization

  2020influential citation
• Imbalanced Sparse Canonical Correlation Analysis

  2020cites this paper
• Sparse Generalized Canonical Correlation Analysis: Distributed Alternating Iteration-Based Approach

  2020cites this paper
• Probabilistic canonical correlation analysis for sparse count data

  2020influential citation
• Reducibility and Statistical-Computational Gaps from Secret Leakage

  2020cites this paper
• Computationally efficient sparse clustering

  2020cites this paper
• Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits

  2020influential citation
• Estimating Principal Components under Adversarial Perturbations

  2020cites this paper
• Eigenvectors from Eigenvalues Sparse Principal Component Analysis

  2020cites this paper
• Tensor factor model estimation by iterative projection

  2020cites this paper
• tSSNALM: A fast two-stage semi-smooth Newton augmented Lagrangian method for sparse CCA

  2020cites this paper
• Computational Barriers to Estimation from Low-Degree Polynomials

  2020cites this paper
• Link Prediction with Matrix Logistic Regression”

  2020cites this paper
• Significance testing for canonical correlation analysis in high dimensions.

  2020cites this paper
• An Alternating Manifold Proximal Gradient Method for Sparse Principal Component Analysis and Sparse Canonical Correlation Analysis

  2020cites this paper
• Fusion Lasso and Its Applications to Cancer Subtype and Stage Prediction

  2020cites this paper
• The Strongish Planted Clique Hypothesis and Its Consequences

  2020cites this paper
• Sparse generalized canonical correlation analysis via linearized Bregman method

  2020cites this paper
• $\ell_0$-based Sparse Canonical Correlation Analysis

  2020cites this paper
• Eigenvector-based sparse canonical correlation analysis: Fast computation for estimation of multiple canonical vectors

  2020cites this paper
• Minimax Quasi-Bayesian Estimation in Sparse Canonical Correlation Analysis via a Rayleigh Quotient Function

  2020influential citation
• Sparse reduced-rank regression for exploratory visualization of paired multivariate datasets

  2020influential citation
• An iterative penalized least squares approach to sparse canonical correlation analysis

  2019influential citation
• An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA

  2019influential citation
• Finding a planted clique by adaptive probing

  2019cites this paper
• More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning

  2019cites this paper
• Universality of Computational Lower Bounds for Submatrix Detection

  2019cites this paper
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries

  2019cites this paper
• Optimal estimation in high-dimensional and nonparametric models

  2019influential citation
• Adversarially Robust Low Dimensional Representations

  2019cites this paper
• High-Dimensional Statistics

  2019cites this paper