Rethinking PCA Through Duality

• URL: http://arxiv.org/abs/2510.18130v1
• Date: Mon, 20 Oct 2025 21:56:14 GMT
• Title: Rethinking PCA Through Duality
• Authors: Jan Quan, Johan Suykens, Panagiotis Patrinos,
• Abstract summary: We revisit the fundamentals of self-attention and principal component analysis.<n>We present several novel formulations and provide new theoretical insights.<n>We describe new algorithms for reconstruction and reconstruction of errors.
• Score: 5.692250278586933
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Exponential Convergence of CAVI for Bayesian PCA [0.7929564340244416]
  Probabilistic principal component analysis (PCA) and its Bayesian variant (BPCA) are widely used for dimension reduction in machine learning and statistics.<n>In our paper, we prove a precise exponential convergence result in the case where the model uses a single principal component (PC)<n>We also leverage recent tools to prove exponential convergence of CAVI for the model with any number of PCs.
  arXiv  Detail & Related papers  (2025-05-22T02:44:00Z)
• Solve sparse PCA problem by employing Hamiltonian system and leapfrog method [0.0]
  We propose a novel sparse PCA algorithm that imposes sparsity through a smooth L1 penalty.<n> Experimental evaluations on a face recognition dataset-using both k-nearest neighbor and kernel ridge regressions-demonstrate that the proposed sparse PCA methods consistently achieve higher classification accuracy than conventional PCA.
  arXiv  Detail & Related papers  (2025-03-30T06:39:11Z)
• Tight Stability, Convergence, and Robustness Bounds for Predictive Coding Networks [60.3634789164648]
  Energy-based learning algorithms, such as predictive coding (PC), have garnered significant attention in the machine learning community. We rigorously analyze the stability, robustness, and convergence of PC through the lens of dynamical systems theory.
  arXiv  Detail & Related papers  (2024-10-07T02:57:26Z)
• Black-Box $k$-to-$1$-PCA Reductions: Theory and Applications [19.714951004096996]
  We analyze black-box deflation methods as a framework for designing $k$-PCA algorithms. Our main contribution is significantly sharper bounds on the approximation parameter degradation of deflation methods for $k$-PCA. We apply our framework to obtain state-of-the-art $k$-PCA algorithms robust to dataset contamination.
  arXiv  Detail & Related papers  (2024-03-06T18:07:20Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Fair principal component analysis (PCA): minorization-maximization algorithms for Fair PCA, Fair Robust PCA and Fair Sparse PCA [6.974999794070285]
  We propose a new iterative algorithm to solve the fair PCA (FPCA) problem. The proposed algorithm relies on the relaxation of a semi-orthogonality constraint which is proved to be tight at every iteration of the algorithm. We numerically compare the performance of the proposed methods with two of the state-of-the-art approaches on synthetic data sets and a real-life data set.
  arXiv  Detail & Related papers  (2023-05-10T08:14:32Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• A novel approach for Fair Principal Component Analysis based on eigendecomposition [10.203602318836444]
  We propose a novel PCA algorithm which tackles fairness issues by means of a simple strategy comprising a one-dimensional search. Our findings are consistent in several real situations as well as in scenarios with both unbalanced and balanced datasets.
  arXiv  Detail & Related papers  (2022-08-24T08:20:16Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  We develop a doubly robust off-policy AC (DR-Off-PAC) for discounted MDP. DR-Off-PAC adopts a single timescale structure, in which both actor and critics are updated simultaneously with constant stepsize. We study the finite-time convergence rate and characterize the sample complexity for DR-Off-PAC to attain an $epsilon$-accurate optimal policy.
  arXiv  Detail & Related papers  (2021-02-23T18:56:13Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.