On the Error-Propagation of Inexact Hotelling's Deflation for Principal Component Analysis

• URL: http://arxiv.org/abs/2310.04283v2
• Date: Wed, 29 May 2024 16:17:24 GMT
• Title: On the Error-Propagation of Inexact Hotelling's Deflation for Principal Component Analysis
• Authors: Fangshuo Liao, Junhyung Lyle Kim, Cruz Barnum, Anastasios Kyrillidis,
• Abstract summary: This paper mathematically characterizes the error propagation of the inexact Hotelling's deflation method. We explicitly characterize how the errors progress and affect subsequent principal component estimations.
• Score: 8.799674132085935
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Principal Component Analysis (PCA) aims to find subspaces spanned by the so-called principal components that best represent the variance in the dataset. The deflation method is a popular meta-algorithm that sequentially finds individual principal components, starting from the most important ones and working towards the less important ones. However, as deflation proceeds, numerical errors from the imprecise estimation of principal components propagate due to its sequential nature. This paper mathematically characterizes the error propagation of the inexact Hotelling's deflation method. We consider two scenarios: $i)$ when the sub-routine for finding the leading eigenvector is abstract and can represent various algorithms; and $ii)$ when power iteration is used as the sub-routine. In the latter case, the additional directional information from power iteration allows us to obtain a tighter error bound than the sub-routine agnostic case. For both scenarios, we explicitly characterize how the errors progress and affect subsequent principal component estimations.

Related papers

• Principal Component Analysis When n < p: Challenges and Solutions [0.0]
  Principal Component Analysis is a key technique for reducing the complexity of high-dimensional data. Standard principal component analysis performs poorly as a dimensionality reduction technique in high-dimensional scenarios. We propose a novel estimation called pairwise differences covariance estimation.
  arXiv  Detail & Related papers  (2025-03-21T22:33:52Z)
• $e^{\text{RPCA}}$: Robust Principal Component Analysis for Exponential Family Distributions [11.13032534597243]
  We propose a new method called Robust Principal Component Analysis for Exponential Family ($etextRPCA$) We present a novel alternating direction method of multiplier optimization algorithm for efficient $etextRPCA$ decomposition. The effectiveness of $etextRPCA$ is then demonstrated in two applications: the first for steel sheet defect detection, and the second for crime activity monitoring in the Atlanta metropolitan area.
  arXiv  Detail & Related papers  (2023-10-30T17:51:30Z)
• Revisiting Rotation Averaging: Uncertainties and Robust Losses [51.64986160468128]
  We argue that the main problem of current methods is the minimized cost function that is only weakly connected with the input data via the estimated epipolar. We propose to better model the underlying noise distributions by directly propagating the uncertainty from the point correspondences into the rotation averaging.
  arXiv  Detail & Related papers  (2023-03-09T11:51:20Z)
• Quasi-parametric rates for Sparse Multivariate Functional Principal Components Analysis [0.0]
  We show that the eigenelements can be expressed as the solution to an optimization problem. We establish a minimax lower bound on the mean square reconstruction error of the eigenelement, which proves that the procedure has an optimal variance in the minimax sense.
  arXiv  Detail & Related papers  (2022-12-19T13:17:57Z)
• Signal Decomposition Using Masked Proximal Operators [9.267365602872134]
  We consider the well-studied problem of decomposing a vector time series signal into components with different characteristics. We propose a simple and general framework in which the components are defined by loss functions (which include constraints) We give two distributed methods which find the optimal decomposition when the component class loss functions are convex.
  arXiv  Detail & Related papers  (2022-02-18T18:05:33Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning.
  arXiv  Detail & Related papers  (2021-06-28T00:38:54Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
  Many machine learning applications involve learning representations that achieve two competing goals. Minimax game-theoretic formulation represents a fundamental tradeoff between accuracy and invariance. We provide an information-theoretic analysis of this general and important problem under both classification and regression settings.
  arXiv  Detail & Related papers  (2020-12-19T15:24:04Z)
• A Framework for Private Matrix Analysis [20.407204637672887]
  We give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis, and linear regression. We also initiate and show efficient differentially private algorithms for two important variants of principal component analysis.
  arXiv  Detail & Related papers  (2020-09-06T08:01:59Z)
• 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)
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives [50.12802772165797]
  The averaging technique combines all iterative solutions into a single solution. Experiments have demonstrated trade-off and the effectiveness of averaging compared with other averaging schemes.
  arXiv  Detail & Related papers  (2020-03-09T18:14:00Z)
• Nonlinear Functional Output Regression: a Dictionary Approach [1.8160945635344528]
  We introduce projection learning (PL), a novel dictionary-based approach that learns to predict a function that is expanded on a dictionary. PL minimizes an empirical risk based on a functional loss. PL enjoys a particularily attractive trade-off between computational cost and performances.
  arXiv  Detail & Related papers  (2020-03-03T10:31:17Z)

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.