Rethinking PCA Through Duality

AI summary

Overview

• Research area: Machine learning methodology and optimization theory, specifically dimensionality reduction (principal component analysis), convex/nonconvex duality, kernel methods, and numerical linear algebra.
• Technical level: Advanced. The paper operates with difference-of-convex (DC) duality (Toland duality), Schatten p-norms, subdifferentials of unitarily invariant functions, and convergence analysis of the difference-of-convex algorithm (DCA).
• One-sentence scope: The paper re-derives PCA and a robust PCA variant through difference-of-convex duality, yielding new kernelizable and out-of-sample-applicable primal-dual formulations and a new optimization interpretation of the classical simultaneous iteration / QR algorithm.

What This Paper Is About

PCA is one of the oldest and most widely used dimensionality reduction techniques, and it has recently regained attention because self-attention in transformers has been linked to kernel PCA. The authors revisit PCA from first principles using the difference-of-convex framework, which pairs a nonconvex primal problem with a dual problem that often admits a simpler or kernel-compatible structure. Their goal is to derive new equivalent formulations of PCA and robust PCA, determine when those formulations can be computed through a kernel matrix, and connect the resulting algorithms to classical numerical linear algebra methods such as simultaneous iteration and the QR algorithm.

Key Contributions

1. Three novel DC dual pairs for PCA. The authors derive the formulations shown in Figure 2 (labeled (l) through (q)) and compare simple gradient methods against existing solvers. They further show that if one function in the primal is unitarily invariant, the DC dual is kernelizable and out-of-sample applicable. Additional DC dual pairs follow from Proposition 3.3 and Remark 3.4.

2. A link between simultaneous iteration and DCA. They show that simultaneous iteration (reference 77, Algorithm 28.3) is an instance of DCA applied to the variance maximization objective of PCA, and that this is connected to the QR algorithm for computing eigenvalues of dense matrices. Existing work had only connected DCA to the power method without normalization for the single leading component (reference 71, Prop. 4); the new result covers the multi-component case.

3. A kernelizable robust PCA formulation. Starting from the least absolute deviation formulation of robust subspace recovery, they present a novel DC formulation whose dual is kernelizable, and they show that DCA applied to the primal is related to approaches based on iteratively reweighted least squares.

Main Findings

• Three fundamental DC dual pairs are established (Figure 2): the pair (l)-(m), the pair (n)-(o), and the pair (p)-(q). The pairs (l) and (n) share the same minimizers, as do (o) and (q).
• The pair (l)-(m) is a known formulation: the authors state it has been studied for one component in references [9, 36, 5] and extended to multiple components in reference [74]. The pairs (n)-(o) and (p)-(q) are, to the authors' knowledge, novel.
• Relation of (l) to the variance maximization formulation: (l) is equivalent to formulation (d); the constraint set is identified as the convex hull of the Stiefel manifold, which is the closed unit ball of the spectral norm.
• Optimal value of (l): by Proposition 3.2 the optimal value is −½ Σ_{i=1}^{s} σ_i(X)², and the first s columns of an eigenvector matrix of XᵀX achieve the optimum.
• The pair (n)-(o) is described as arguably more fundamental because of its symmetry; each formulation captures a trade-off between Schatten p-norms.
• Another new pair follows from formulation (k): Proposition 3.3 gives a DC dual with a primal ¼‖W‖_{S₄}⁴ − ½‖XW‖_{S₂}² and a dual ½‖H‖_{S₂}² − ¾‖XᵀH‖_{S_{4/3}}^{4/3}.
• Kernelizability for unitarily invariant G: Proposition 3.5 shows that when the primal function G = g ∘ σ is unitarily invariant, the DC dual can be written using only the kernel matrix K = XXᵀ, with the term g*(√λ(HᵀKH)). The paper notes that all the described formulations are kernelizable because they are based on Schatten p-norms, which are unitarily invariant. When s = 1, the eigenvalue quantity reduces to the scalar HᵀKH.
• Out-of-sample applicability: Theorem 3.8 gives a formula W*ᵀx̃ = V Diag(μ ⊙ λ^{−1/2}) Vᵀ H*ᵀ X x̃ for projecting a new data point, where μ ∈ ∂g*(√λ). The relevant matrix V Diag(μ ⊙ λ^{−1/2}) Vᵀ H*ᵀ ∈ ℝ^{s×N} only needs to be computed once after training.
• DCA algorithms for the main formulations: Algorithm 1 (for formulation (d)) iterates a compact SVD of XᵀXW⁽ᵏ⁾ and sets W⁽ᵏ⁺¹⁾ = U⁽ᵏ⁾V⁽ᵏ⁾ᵀ. Algorithm 2 (for formulation (g)) is the kernel version, iterating a compact SVD of KH⁽ᵏ⁾. When s = 1, the SVD reduces to vector normalization and the iterations correspond to the power method.
• Connection to simultaneous iteration (Theorem 3.11): Algorithms 1 and 2 correspond to simultaneous iteration applied to XᵀX and XXᵀ respectively, up to orthogonal transformation. As a corollary, they inherit the linear rate and convergence to global optimality with probability one from the known convergence result for simultaneous iteration (reference 77, Theorem 28.4).
• Proximal gradient interpretation: the proximal gradient method used in the experiments corresponds to DCA applied to (G + (1/2)‖·‖²) − (F + (1/2)‖·‖²), which the authors connect to simultaneous iteration on an identity-shifted covariance or kernel matrix, thereby naturally incorporating regularization.
• Algorithms for Proposition 3.3: Algorithms 3 and 4 use a nonlinear preconditioning through the singular values, updating with (Σ⁽ᵏ⁾)^{1/3} in the primal and (Λ⁽ᵏ⁾)^{−1/3} in the dual. Algorithm 4 is a kernelizable dual algorithm using only K.
• Robust PCA (Proposition 4.1): starting from the reconstruction error formulation (c) of PCA as a linear autoencoder, the authors replace the squared error with an l₁ penalty on reconstruction errors (least absolute deviation). The DC dual is kernelizable, written as a sum over √((XXᵀ)_{i,i}(1 + ‖H_{i,:}‖²)) minus tr(√(HᵀXXᵀH)). Because the associated G is the indicator function of the spectral unit norm ball, which is unitarily invariant, the problem is out-of-sample applicable. Algorithms 5 and 6 give the primal and dual DCA iterations, and Appendix D relates the primal algorithm to an iteratively reweighted least squares scheme.
• Experiments: Table 1 reports timing results for various methods applied to PCA formulations, with a problem setting written as (N, d, s, ε) denoting a data matrix X ∈ ℝ^{N×d} with entries sampled from a standard normal distribution, s principal components, and stopping tolerance ε. The only fully visible example entry is (4000, 2000, 20, 10⁻³); the second entry is truncated at (2000,. Timings are reported in milliseconds, and timings longer than 5 seconds are not displayed. The full table and the remaining experimental results are not contained in the provided content.

Methodology in Plain English

The authors begin from the collection of standard PCA formulations shown in Figure 1 (labeled (a) through (k)), which include low-rank matrix approximation, constrained reconstruction-error objectives, and variance maximization objectives. They then apply difference-of-convex duality (Toland duality, Proposition 2.3), which turns a nonconvex minimization of the form "convex function minus convex function" into a dual problem of a similar form while preserving the optimal value. Because the primal problems involve squared, square-rooted, or fourth-power-scaled terms, simple algebraic transformations (squaring, taking square roots, positive scaling) produce duals with quite different structure; those transformations are what generate the new pairs.

To make the duals practical for kernel methods, the authors restrict attention to cases where certain functions are unitarily invariant, i.e., unchanged under multiplication by orthogonal matrices on either side. Such functions can be written as a function of the singular values, allowing the data matrix in the dual to be replaced by a kernel matrix. For out-of-sample projection, they derive a closed-form expression using an eigendecomposition of an s × s matrix, which is small in practice.

To solve the resulting optimization problems, they apply the difference-of-convex algorithm, which fits into the majorization-minimization framework and reduces, for these problems, to repeated compact SVDs or eigendecompositions. They then compare timing results of these algorithms and simple gradient methods against existing solvers on synthetic Gaussian data, as described in Table 1.

Why This Matters

The paper connects three areas that are usually treated separately: classical PCA, convex duality theory, and numerical linear algebra (the QR algorithm and simultaneous iteration). By showing that repeated SVD steps in a DC algorithm reproduce the behaviour of simultaneous iteration, it provides an optimization perspective on a longstanding numerical method, similar in spirit to the connection between conjugate gradients and accelerated gradient descent. It also extends kernelizability and out-of-sample capability to a family of PCA-like problems defined by unitarily invariant functions, and it supplies a kernelizable dual for a robust, l₁-based PCA whose out-of-sample behaviour had not previously been considered. The motivation from self-attention and kernel PCA links this theoretical work to the architecture underlying modern transformers.

Real-world applications suggested by the techniques involved:

• Dimensionality reduction and feature extraction on high-dimensional data, where PCA is a standard tool across machine learning, signal processing, and computer vision.
• Robust subspace recovery on data contaminated by noise or outliers, using the l₁ formulation of reconstruction errors.
• Nonlinear pattern discovery through kernel PCA, where the kernel trick avoids explicitly computing features in a possibly infinite-dimensional space.
• Analysis and interpretation of attention-based models, since self-attention has been shown to correspond to projections onto principal component axes in a feature space.

Industry relevance: the QR algorithm is described in the paper as one of the top ten algorithms of the 20th century and still the de facto industry standard in high-performance computing libraries and software such as MATLAB. Kernel PCA and robust PCA are widely deployed in machine learning pipelines, so new dual formulations with kernel and out-of-sample support may be of interest to practitioners who need robust or nonlinear variants of standard PCA.

Future Directions

• Further exploration of the DC dual pairs. The authors note that four more analogous DC dual pairs can be formulated by swapping X with Xᵀ (Remark 3.4), and that their decomposition of the primal changes the dual dramatically; systematically characterizing which duals are most useful for which objectives remains an open direction.
• Robustness and out-of-sample extensions in the kernel setting. The authors point out that previous work extending DC duality to robust PCA did not consider the out-of-sample extension; their formulation does, but further development of robust kernel objectives that retain interpretability is a natural next step.
• Tighter convergence analysis. The paper relies on existing DCA convergence results (sublinear in general, linear under growth conditions) and on the convergence properties of simultaneous iteration; sharper rates specific to the PCA dual pairs are a natural extension.
• Broader empirical evaluation. The provided content is truncated in the experiments section, so the full comparative evaluation of the new algorithms against state-of-the-art solvers is a matter for the complete paper; extending those comparisons to real datasets and to the kernel and robust settings would clarify when the new formulations are preferable.

Target Audience

Optimization researchers interested in DC programming and primal-dual formulations, numerical linear algebra researchers interested in the QR algorithm and simultaneous iteration, and machine learning researchers working on dimensionality reduction, kernel methods, and the theoretical interpretation of attention mechanisms. The paper assumes familiarity with convex analysis, matrix norms, and spectral methods, so it is best suited to graduate students and researchers with a strong mathematical background rather than beginners.

Authors’ abstract

Motivated by the recently shown connection between self-attention and (kernel) principal component analysis (PCA), we revisit the fundamentals of PCA. Using the difference-of-convex (DC) framework, we present several novel formulations and provide new theoretical insights. In particular, we show the kernelizability and out-of-sample applicability for a PCA-like family of problems. Moreover, we uncover that simultaneous iteration, which is connected to the classical QR algorithm, is an instance of the difference-of-convex algorithm (DCA), offering an optimization perspective on this longstanding method. Further, we describe new algorithms for PCA and empirically compare them with state-of-the-art methods. Lastly, we introduce a kernelizable dual formulation for a robust variant of PCA that minimizes the $l_1$ deviation of the reconstruction errors.