Unpaired Canonical Correlation Analysis

AI summary

Overview

• Research area: Multiview / multimodal statistical machine learning (specifically canonical correlation analysis, unpaired data alignment, and combinatorial optimization).
• Technical level: Advanced. The paper is theory-heavy, relying on singular value majorization, nuclear and Frobenius norms, permutation matrices, and the Quadratic Assignment Problem (QAP), though the resulting algorithm is simple enough to describe in a paragraph.
• Scope: The paper defines the Unpaired CCA problem, proves that a practically solvable linear-kernel QAP formulation recovers the correct pairing, and introduces UCCA, the first method that learns maximally correlated linear projections from strictly unpaired data.

What This Paper Is About

Canonical Correlation Analysis (CCA) finds maximally correlated linear components between two views of data, but it requires each sample in one view to have a known corresponding sample in the other. This paper asks whether the same maximally correlated projections can be recovered when no paired samples exist at all during training — only two independent, unpaired sets of observations. The authors answer yes, by showing that the correct underlying pairing can be approximated through the Quadratic Assignment Problem and then handed to standard CCA.

Key Contributions

1. A theoretical connection between Unpaired CCA and the Quadratic Assignment Problem. The authors define a proxy pairing, Maximum Correlation Pairing over the orthogonal group (MCP_{O(d)}), and prove it reduces to a linear-kernel QAP over the cross-similarity matrices, QAP(XX^T, YY^T) (Theorem 1).
2. A practical, attainable relaxation. They show MCP_{O(d)} can be relaxed to a pairing over the scaled Frobenius sphere, MCP_{S_F}, reformulating both as maximization over the nuclear norm (||X^T P Y||_*) and Frobenius norm (||X^T P Y||_F) of the permuted cross-correlation matrix respectively, and prove these two pairings coincide under a mild assumption (Theorem 2).
3. The UCCA algorithm. An anchor-based, scalable procedure (whitening, K-Means centroid anchors, QAP matching, then standard CCA on the matched anchors) that operates entirely without paired data.
4. Empirical validation. Across six dataset configurations from four real-world datasets, UCCA is reported as the only method that consistently recovers the underlying correlation, significantly outperforming unpaired alignment baselines and often approaching the paired CCA upper bound.

Main Findings

• QAP value tracks CCA correlation: On a 10-sample synthetic dataset, evaluating all 10! possible pairings revealed a direct positive relationship between the QAP value and total correlation (Figure 1a). This is the empirical anchor for the theory.
• Singular value majorization holds in practice: Figure 3a shows, on the Flickr dataset (8,000 samples), that partial cumulative sums of singular values strictly decrease as the permutation diverges from the ground-truth permutation P*, confirming Assumption 1.
• The two pairings coincide empirically: Figure 6 reports Kendall Tau distances between MCP_{S_F} (found by an approximate QAP solver) and the estimated MCP_{O(d)} on the Handwritten benchmark (PC-PA) anchors across 100 initializations; the distances are heavily concentrated at zero, holding Theorem 2 in practice.
• UCCA beats unpaired baselines on total correlation: Figure 5 shows UCCA consistently extracting highly correlated components across six distinct dataset configurations, reporting the total correlation captured by the top two learned components, and often approaching the paired CCA upper bound.
• Cross-view classification: In Table 1, training a kNN classifier on one view's embeddings and testing on the other, UCCA scores 0.292 ± 0.074 (PC-KL), 0.315 ± 0.025 (PC-PA), 0.564 ± 0.022 (KL-PA), and 0.849 ± 0.021 (SNARE), versus the paired CCA reference values of 0.562 ± 0.000, 0.516 ± 0.000, 0.629 ± 0.000, and 0.887 ± 0.000 respectively. On COCO, UCCA reaches 0.232 ± 0.016, matching the paired CCA figure of 0.232 ± 0.009 and placing second to J-MDS-CCA's 0.237 ± 0.079 — the paper describes this as "comparable performance on the fifth" configuration.
• Runtime is manageable despite QAP being NP-hard: Figure 7 reports total runtime of only several minutes per dataset, and UCCA outperforms baselines even with fewer clustering repetitions.
• More unpaired data helps: Figure 8 shows UCCA is robust to unbalanced views and that its consistency and performance increase with the volume of available unpaired data, peaking when the maximum amount of data is accessible.

Methodology in Plain English

The authors begin by assuming the two unpaired datasets are related by an unknown permutation, meaning a scrambled version of the true one-to-one correspondence. The obvious idea — pick the permutation that maximizes total correlation directly — breaks down when the two views are not already aligned, because it is sensitive to arbitrary rotations (Figure 2b). So they allow an orthogonal projection to be optimized alongside the permutation (MCP_{O(d)}), making the criterion rotation-invariant (Figure 2c).

Optimizing over permutations and orthogonal matrices at the same time is computationally prohibitive, so they relax the projection class to the scaled Frobenius sphere. This relaxation turns the problem into a QAP instance, which is NP-hard but has efficient approximate solvers. They then prove that this relaxed pairing equals the original orthogonal-group pairing under a weak-majorization assumption on the singular values of the permuted cross-correlation matrix — an assumption they show holds exactly when one view is an isometry of the other and holds with probability 1 as n → ∞ for any random permutation.

The resulting algorithm, UCCA, is a short pipeline: whiten both datasets, select k representative anchors within each modality using K-Means centroids, match the anchors with the linear-kernel QAP formulation, repeat this several times for robustness and concatenate the matched anchors, then treat the matched anchors as pseudo-pairs and run standard CCA to obtain the final projection matrices. No correspondence between actual data samples is ever used.

Why This Matters

This work bridges classical statistical multiview learning and the growing field of unpaired data learning. Most prior methods that use unpaired data still depend on some complementary alignment signal — a handful of exact pairs (weakly supervised), initial paired training (semi-supervised), shared class labels, or hand-designed task-specific objectives. UCCA is, to the authors' knowledge, the first method to learn maximally correlated projections in a strictly unpaired setting, with a theoretical argument rather than a heuristic behind it.

Real-world applications implied by the paper's framing:

• Single-cell multi-omics integration, where measuring multiple modalities on the same cell is often infeasible (the SNARE benchmark).
• Image–text representation learning, where caption–image pairs are expensive to collect at scale (the Flickr and COCO benchmarks).
• Neuroimaging, where aligning recordings across subjects or modalities typically lacks exact correspondence.
• Multimodal representation learning generally, including the joint-embedding style objectives used in modern large models, which depend heavily on massive paired corpora.

Industry relevance: any setting where two data streams describe the same underlying entities but were collected separately — medical records across hospitals, sensor streams with unregistered clocks, or user profiles across platforms — could benefit from recovering shared correlated structure without paying the cost of manual pairing.

Future Directions

• Closing the gap to paired CCA. The authors explicitly state that a performance gap remains relative to the paired CCA upper bound, which they describe as the theoretical upper bound.
• Extending to multi-view settings. The current framework focuses on the bi-view case; the authors flag multi-view extension as compelling because the difficulty of acquiring cross-modal correspondences scales with the number of views.
• Anchor selection and count. The paper's ablations validate K-Means centroids as anchors and the number of anchors used, but anchor design remains a tunable design choice that could be studied further (App. B.8).
• Non-linear extensions. The theory and method are linear; whether the QAP connection carries over to non-linear variants is left open.

Target Audience

Researchers and graduate students in statistical machine learning, multiview/multimodal representation learning, and optimization — particularly those working on unpaired data settings, optimal transport for alignment, or applications in single-cell biology, neuroimaging, and vision-language modeling. Practitioners who need CCA-like shared spaces but cannot obtain paired samples will find the algorithm section directly actionable; readers primarily interested in applications will find the QAP-based theory and the majorization assumption the main barrier to entry.

Authors’ abstract

Canonical Correlation Analysis (CCA) is a fundamental method for multiview shared space learning. However, its strict reliance on paired data poses a significant limitation, as such data is often difficult to obtain or entirely unavailable. In this paper, we present Unpaired CCA (UCCA), a novel method that learns linear projections to maximize the correlation of the true underlying pairing without access to any paired samples during training. We first establish theoretical results connecting the Quadratic Assignment Problem (QAP) to CCA. Leveraging these theoretical insights, we derive a practical method to maximize correlation exclusively from unpaired data. To the best of our knowledge, UCCA is the first approach to learn maximally correlated projections in a strictly unpaired setting. We validate UCCA on real-world multi-modal datasets, demonstrating that it significantly outperforms recent unpaired alignment baselines in recovering the underlying true correlation. This work fills a critical gap between traditional statistical multiview learning and the growing field of unpaired data learning.