Research map / Learning theory and algorithms / Matrix and tensor methods
Rethinking PCA Through Duality
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.
Revisits PCA through difference-of-convex (Toland) duality, deriving new kernelizable dual pairs, linking DCA on variance maximization to simultaneous iteration (QR algorithm), and a kernelizable dual for l1-robust PCA.
Problem
Classical PCA formulations lack a unified optimization view; kernelizability and out-of-sample extension are not established for many PCA-like formulations, and robust l1 PCA has no kernelizable dual beyond one component.
Approach
Applies difference-of-convex duality to several PCA formulations built on Schatten p-norms; shows unitarily invariant primal terms yield kernelizable, out-of-sample applicable duals; shows DCA on variance maximization equals simultaneous iteration; derives a kernelizable dual for l1 reconstruction-error robust PCA.
Key results
- Formulation (n) solved by ZeroFPR in about 210 ms versus about 3849 ms for the slowest variance-based formulation at (4000,2000,20,1e-3), and comparable to or faster than SVDS (808 ms) and KrylovKit (1130 ms) on that setting.
- For (4500,4500,20,1e-3), PG on formulation (n) takes 309 ms versus 2986 ms for SVDS and 3845 ms for KrylovKit.
- The paper proves DCA on variance maximization coincides with simultaneous iteration (up to orthogonal transformation), giving linear rate and global convergence with probability one from random initialization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the newly proposed PCA formulations (n)–(o) with first-order methods instead of classical variance-based formulations | PCA · PCA timing experiments | runtime | Helped |
| Use the primal or dual formulation according to the data matrix shape | ZeroFPR and PG for PCA · PCA timing experiments | runtime | Mixed |
| Use the first-order methods as the number of principal components varies, when involved matrix dimensions are sufficiently large | PCA · Varying number of principal components | runtime | Helped |
Surprising findings
- Variance-based formulations solved by first-order methods perform poorly, while newly derived dual formulations outperform state-of-the-art eigensolvers.
- The classical power-method-like DCA iteration for PCA is exactly simultaneous iteration, linking it to the QR algorithm.
Limitations
- Kernelizability and out-of-sample results require the primal term to be unitarily invariant, which excludes some formulations.
- Kernel methods scale as N^2 in the kernel matrix size; mitigations such as Nystrom are not explored here.
- DCA-based algorithms return only an orthonormal basis of the eigenspace rather than individual eigenvectors.
Experimental setup
Datasets: synthetic Gaussian matrices
Benchmarks: synthetic random data matrices timing (N,d,s,epsilon) settings
Metrics: runtime (milliseconds)
Baselines: SVDS (ARPACK) KrylovKit ZeroFPR proximal gradient
Builds on: Toland duality difference-of-convex algorithm simultaneous iteration Eckart-Young-Mirsky theorem Burer-Monteiro factorization
Closest papers by meaning
- Extending Kernel PCA through Dualization: Sparsity, Robustness and Fast Algorithms (ICML 2023 · similarity 0.91)
- Stochastic PCA with $\ell_2$ and $\ell_1$ Regularization (ICML 2018 · similarity 0.89)
- Attention-based PCA (NeurIPS 2026 · similarity 0.88)
- Unveiling the Hidden Structure of Self-Attention via Kernel Principal Component Analysis (NeurIPS 2024 · similarity 0.87)
- Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.87)
- Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity (ICML 2025 · similarity 0.85)
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.