Skip to content
Preprint

Streaming PCA: averaging from a geometric perspective

Sep 2026 · 0 citations
Mathematics

TL;DR

The main goal is to develop a procedure based on Oja's algorithm that is optimal without prior knowledge of the eigengap, which is otherwise needed to tune the learning rates effectively.

Abstract

We study principal component analysis (PCA) under memory constraints, a setting that is increasingly important in large-scale data analysis. Our focus is on Oja's algorithm, which is a one-pass, memory-efficient algorithm requiring only $O(p)$ storage in the rank-one case and $O(pk)$ storage for $k$- PCA. The main goal is to develop a procedure based on Oja's algorithm that is optimal without prior knowledge of the eigengap, which is otherwise needed to tune the learning rates effectively. We do this by first introducing a geometric perspective on the convergence of $k$-PCA: by embedding the Oja iterates into the exterior space, we establish an exact equivalence between $k$-PCA in the ambient space and $1$-PCA in the exterior space. This geometric viewpoint enables us to establish several convergence guarantees, including one based only on a single learning-rate schedule. Building on this geometric perspective, we develop an averaging theory for $k$-PCA and show that the resulting averaged estimator is adaptive: it achieves the nearly optimal convergence rate without prior knowledge of the eigengap. As an application, we construct memory-efficient estimators for elliptical component analysis (ECA) \cite{han2014scale,han2018eca}. Simulation studies and real data analysis are conducted to demonstrate the benefits of our proposed algorithms.

View source

Similar papers

#machine learning Preprint Sep 2026

Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis

DeepMVSA is proposed, which re-expresses the minimum-volume principle in neural implicit form and proves a non-asymptotic sample-complexity bound of the polynomial-time benchmark order for a localized surrogate estimator.

Jun Li, Yan-Long Guo, Zhao-Zhao Zeng · 0 citations

Riemannian Difference-of-Convex Optimization for K-Means Clustering

This paper replaces the cardinality constraint with a difference-of-convex (DC) penalty and establishes a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold.

Meng Xu, Bo Jiang, Han-Fu Zhang et al. · 0 citations
Preprint Oct 2026

Efficient Mass Matrix Estimation with Gaussian Cooling

We introduce an algorithm for efficiently preconditioning log-concave and log-smooth distributions that scales logarithmically with the condition number of the underlying distribution. Based on Gaussian cooling, our multistage method approximately samples from a sequence of well-conditioned distributions to construct a...

Jake Hofgard, Michael A. Lindsey · 0 citations
#machine learning Preprint Oct 2026

Adaptive Mean Estimation by In-Context Learning: A Gradient-Flow Analysis

This work studies how statistical adaptivity is learned in a controlled location-estimation problem, and combines attention experts through either a softmax mixture of experts or a gated linear unit (GLU), and analyze stagewise gradient flow.

Martin Eppert, K. Balasubramanian, Subhro Ghosh et al. · 0 citations
Preprint Aug 2026

A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings

It is proved that sketching dimension m = O(k^{3/2}/\epsilon^2) suffices for subspace embedding with a Khatri-Rao sketching matrix with any fixed order $d$.

Lorenzo Beretta, Cameron Musco · 1 citation
Preprint Aug 2026

Online Differentially Private Consistent Clustering

A generic reduction is given that transforms the (sensitive) input stream into a private stream, which is a semi-coreset of the input stream, which implies that any (non-private) online clustering algorithm, run as a post-processing step, can achieve good utility for the original clustering objective.

Edith Cohen, Vadym Doroshenko, Badih Ghazi et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.