Research map / Learning theory and algorithms / Matrix and tensor methods
On Sparse Canonical Correlation Analysis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies sparse canonical correlation analysis (SCCA) with exact zero-norm constraints, giving a combinatorial reformulation, complexity results for low-rank cases, and an exact MISDP branch-and-cut algorithm with closed-form cuts.
Problem
Canonical correlation analysis is hard to interpret in high-dimensional settings; existing sparse CCA methods relax the cardinality (l0) constraints into convex penalties, so exact sparsity is not enforced and global optimality is unclear.
Approach
Reformulates SCCA exactly as a combinatorial submatrix-selection problem over the largest singular value of selected blocks of A, B, C, proves NP-hardness via sparse PCA/SVD/regression, shows low-rank cases are polynomially solvable when sparsity exceeds ranks, and gives a mixed-integer SDP reformulation solved by branch-and-cut with closed-form cuts; no positive-definiteness assumption on B, C is
Key results
- Exact low-rank algorithm (Algorithm 1) solves breast cancer instance with n=19,672 and m=2,149 to optimality in about one second when s1 and s2 are at least the ranks (89).
- Branch-and-cut solves SCCA to optimality for synthetic instances up to n=m=120 in full-rank settings, while greedy and local search match optimal values on most solved cases with zero gap.
- Local search attains larger correlation than the compared SCCA methods in 16 of 22 test cases while enforcing exact sparsity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use exact-sparsity local search instead of methods [41], [37], or [10] | SCCA · 22 synthetic, UCI, and breast cancer test cases | correlation | Helped |
| Enforce exact zero-norm constraints with local search | SCCA · 22 synthetic, UCI, and breast cancer test cases | sparsity | Helped |
| Use local search instead of [37] | SCCA · Synthetic n=m=40, s1=s2=5 | correlation: 0.659 -> 0.695 | Helped |
| Use local search instead of [10] | SCCA · Synthetic n=m=100, s1=s2=10 | correlation: 0.938 -> 0.940 | Helped |
| Use local search instead of [10] | SCCA · Synthetic n=m=20, s1=s2=5 | correlation: 0.256 -> 0.244 | Hurt |
| Use local search instead of [10] | SCCA · Synthetic n=m=40, s1=s2=5 | correlation: 0.696 -> 0.695 | Hurt |
| Apply the exact low-rank algorithm when sparsity levels meet covariance ranks | SCCA · Breast cancer, n=19,672, m=2,149, s1=s2=100 | time (seconds) | Helped |
| Increase the number of basis-vector pairs | Multiple SCCA branch-and-cut · UCI datasets | time (seconds) | Hurt |
Surprising findings
- The CCA SDP relaxation is exact, giving a sufficient sparsity condition (s1 >= rank(B), s2 >= rank(C)) under which SCCA equals CCA.
Limitations
- Exact branch-and-cut struggles to scale beyond about n=m=120 in full-rank cases, with weak initial gaps causing unsolved instances.
- The polynomial-time exact algorithm only applies when sparsity levels are at least the ranks of B and C; otherwise only approximation algorithms are used.
- General SCCA is NP-hard and may not be mixed-integer convex quadratic representable.
Experimental setup
Datasets: UCI datasets (dermatology, spambase, digits, buzz, gas, slice) breast cancer gene expression dataset synthetic Gaussian data
Benchmarks: synthetic data (n,m up to 120) six UCI datasets breast cancer dataset (n=19,672, m=2,149)
Metrics: canonical correlation value optimality gap (%) MIP gap (%) running time (s) sparsity (zero-norm count)
Baselines: Greedy algorithm Convex relaxation (CCA / continuous MISDP relaxation) Penalized matrix decomposition SCCA [41] Linearized Bregman SCCA [10] SCCA method [37]
Builds on: sparse PCA sparse SVD Benders decomposition penalized matrix decomposition for sparse CCA
Closest papers by meaning
- A Simple and Provable Algorithm for Sparse Diagonal CCA (ICML 2016 · similarity 0.93)
- L0-Sparse Canonical Correlation Analysis (ICLR 2022 · similarity 0.92)
- Large-Scale Sparse Kernel Canonical Correlation Analysis (ICML 2019 · similarity 0.92)
- Unconstrained Stochastic CCA: Unifying Multiview and Self-Supervised Learning (ICLR 2024 · similarity 0.89)
- Unpaired Canonical Correlation Analysis (NeurIPS 2026 · similarity 0.87)
- Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.