ROIPCA: An online memory-restricted PCA algorithm based on rank-one updates

• URL: http://arxiv.org/abs/1911.11049v2
• Date: Wed, 7 Jun 2023 11:06:28 GMT
• Title: ROIPCA: An online memory-restricted PCA algorithm based on rank-one updates
• Authors: Roy Mitz, Yoel Shkolnisky
• Abstract summary: We propose two online PCA algorithms that are based on rank-one updates. We show the relation between fROIPCA and an existing popular gradient algorithm for online PCA. We demonstrate numerically the advantages of our algorithms over existing state-of-the-art algorithms in terms of accuracy and runtime.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Principal components analysis (PCA) is a fundamental algorithm in data analysis. Its memory-restricted online versions are useful in many modern applications, where the data are too large to fit in memory, or when data arrive as a stream of items. In this paper, we propose ROIPCA and fROIPCA, two online PCA algorithms that are based on rank-one updates. While ROIPCA is typically more accurate, fROIPCA is faster and has comparable accuracy. We show the relation between fROIPCA and an existing popular gradient algorithm for online PCA, and in particular, prove that fROIPCA is in fact a gradient algorithm with an optimal learning rate. We demonstrate numerically the advantages of our algorithms over existing state-of-the-art algorithms in terms of accuracy and runtime.

Related papers

• 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)
• Streaming Kernel PCA Algorithm With Small Space [24.003544967343615]
  Streaming PCA has gained significant attention in recent years, as it can handle large datasets efficiently. We propose a streaming algorithm for Kernel problems based on the traditional scheme by Oja. Our algorithm addresses the challenge of reducing the memory usage of PCA while maintaining its accuracy.
  arXiv  Detail & Related papers  (2023-03-08T13:13:33Z)
• An online algorithm for contrastive Principal Component Analysis [9.090031210111919]
  We derive an online algorithm for cPCA* and show that it maps onto a neural network with local learning rules, so it can potentially be implemented in energy efficient neuromorphic hardware. We evaluate the performance of our online algorithm on real datasets and highlight the differences and similarities with the original formulation.
  arXiv  Detail & Related papers  (2022-11-14T19:48:48Z)
• Robust PCA for Anomaly Detection and Data Imputation in Seasonal Time Series [0.0]
  We develop an online version of the batch temporal algorithm in order to process larger datasets or streaming data. We empirically compare the proposed approaches with different RPCA frameworks and show their effectiveness in practical situations.
  arXiv  Detail & Related papers  (2022-08-03T11:57:26Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  The area under the ROC curve (AUC) is one of the most widely used performance measures for classification models in machine learning. We develop an efficient approximated gradient descent method based on recent practical envelope smoothing technique. Our proposed algorithm can also be used to minimize the sum of some ranked range loss, which also lacks efficient solvers.
  arXiv  Detail & Related papers  (2022-03-03T03:46:18Z)
• Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
  Conditional gradient methods (CGM) are widely used in modern machine learning. Most efforts focus on reducing the number of iterations as a means to reduce the overall running time. We show the first algorithm, where the cost per iteration is sublinear in the number of parameters, for many fundamental optimization algorithms.
  arXiv  Detail & Related papers  (2021-11-30T05:40:14Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)
• 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.