Upper and Lower Bounds on the Performance of Kernel PCA

• URL: http://arxiv.org/abs/2012.10369v1
• Date: Fri, 18 Dec 2020 17:19:31 GMT
• Title: Upper and Lower Bounds on the Performance of Kernel PCA
• Authors: Maxime Haddouche and Benjamin Guedj and Omar Rivasplata and John Shawe-Taylor
• Abstract summary: We contribute lower and upper bounds on the efficiency of kernel PCA. Two bounds are for fixed estimators, and two are for randomized estimators through the PAC-Bayes theory. We dissect the bounds to highlight strengths and limitations of the kernel PCA algorithm.
• Score: 15.745403317380282
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Principal Component Analysis (PCA) is a popular method for dimension reduction and has attracted an unfailing interest for decades. Recently, kernel PCA has emerged as an extension of PCA but, despite its use in practice, a sound theoretical understanding of kernel PCA is missing. In this paper, we contribute lower and upper bounds on the efficiency of kernel PCA, involving the empirical eigenvalues of the kernel Gram matrix. Two bounds are for fixed estimators, and two are for randomized estimators through the PAC-Bayes theory. We control how much information is captured by kernel PCA on average, and we dissect the bounds to highlight strengths and limitations of the kernel PCA algorithm. Therefore, we contribute to the better understanding of kernel PCA. Our bounds are briefly illustrated on a toy numerical example.

Related papers

• Sparse PCA with Oracle Property [115.72363972222622]
  We propose a family of estimators based on the semidefinite relaxation of sparse PCA with novel regularizations. We prove that, another estimator within the family achieves a sharper statistical rate of convergence than the standard semidefinite relaxation of sparse PCA.
  arXiv  Detail & Related papers  (2023-12-28T02:52:54Z)
• Empirical Bayes Covariance Decomposition, and a solution to the Multiple Tuning Problem in Sparse PCA [2.5382095320488673]
  Sparse Principal Components Analysis (PCA) has been proposed as a way to improve both interpretability and reliability of PCA. We present a solution to the "multiple tuning problem" using Empirical Bayes methods.
  arXiv  Detail & Related papers  (2023-12-06T04:00:42Z)
• Accelerating Wireless Federated Learning via Nesterov's Momentum and Distributed Principle Component Analysis [59.127630388320036]
  A wireless federated learning system is investigated by allowing a server and workers to exchange uncoded information via wireless channels. Since the workers frequently upload local to the server via bandwidth-limited channels, the uplink transmission from the workers to the server becomes a communication bottleneck. A one-shot distributed principle component analysis (PCA) is leveraged to reduce the dimension of the dimension of the communication bottleneck.
  arXiv  Detail & Related papers  (2023-03-31T08:41:42Z)
• Kernel PCA for multivariate extremes [0.0]
  We show that kernel PCA can be a powerful tool for clustering and dimension reduction. We give theoretical guarantees on the performance of kernel PCA based on an extremal sample. Our findings are complemented by numerical experiments illustrating the finite performance of our methods.
  arXiv  Detail & Related papers  (2022-11-23T17:50:06Z)
• Bayes-optimal limits in structured PCA, and how to reach them [21.3083877172595]
  We study the paradigmatic matrix model of principal components analysis (PCA), where a rank-one matrix is corrupted by additive noise. We provide the first characterization of the Bayes-optimal limits of inference in this model. We propose a novel approximate message passing algorithm (AMP), inspired by the theory of Adaptive Thouless-Anderson-Palmer equations.
  arXiv  Detail & Related papers  (2022-10-03T21:31:41Z)
• Sparse PCA on fixed-rank matrices [0.05076419064097732]
  We show that, if the rank of the covariance matrix is a fixed value, then there is an algorithm that solves sparse PCA to global optimality. We also prove a similar result for the version of sparse PCA which requires the principal components to have disjoint supports.
  arXiv  Detail & Related papers  (2022-01-07T15:05:32Z)
• FAST-PCA: A Fast and Exact Algorithm for Distributed Principal Component Analysis [12.91948651812873]
  Principal Component Analysis (PCA) is a fundamental data preprocessing tool in the world of machine learning. This paper proposes a distributed PCA algorithm called FAST-PCA (Fast and exAct diSTributed PCA)
  arXiv  Detail & Related papers  (2021-08-27T16:10:59Z)
• Kernel Mean Estimation by Marginalized Corrupted Distributions [96.9272743070371]
  Estimating the kernel mean in a kernel Hilbert space is a critical component in many kernel learning algorithms. We present a new kernel mean estimator, called the marginalized kernel mean estimator, which estimates kernel mean under the corrupted distribution.
  arXiv  Detail & Related papers  (2021-07-10T15:11:28Z)
• Turning Channel Noise into an Accelerator for Over-the-Air Principal Component Analysis [65.31074639627226]
  Principal component analysis (PCA) is a technique for extracting the linear structure of a dataset. We propose the deployment of PCA over a multi-access channel based on the algorithm of gradient descent. Over-the-air aggregation is adopted to reduce the multi-access latency, giving the name over-the-air PCA.
  arXiv  Detail & Related papers  (2021-04-20T16:28:33Z)
• 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)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime. We show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. We prove that the Overlap Gap Property (OGP) holds in a significant part of the hard regime.
  arXiv  Detail & Related papers  (2020-06-18T17:18:02Z)

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.