AdaOja improves Oja's algorithm for streaming PCA with adaptive learning rates.
problem Lack of standardized learning rates in Oja's algorithm for streaming PCA.
method Proposes AdaOja, a novel learning rate scheme for Oja's method.
result AdaOja outperforms common learning rate choices and performs comparably to state-of-the-art algorithms.
New derivation shows how a three-factor learning rule is derived from Oja's rule.
problem Deriving a three-factor learning rule from Oja's rule.
method Using frame theory to systematically derive EGHR-PCA from Oja's rule.
result A principled derivation of a biologically plausible learning rule.
Oja's rule improves neural network training without engineered tricks.
problem Training deep neural networks with biological constraints.
method Incorporating Oja's plasticity rule into error-driven training.
result Stable, efficient learning in feedforward and recurrent architectures.
The paper uses diffusion approximations to analyze and optimize online principal component estimation.
problem Optimizing online principal component estimation from streaming data.
method Diffusion approximation tools applied to Oja's iteration for principal component analysis.
result The Oja's iteration for the top eigenvector generates a continuous-state discrete-time Markov chain over the unit sphere.
A new single-pass algorithm improves sparse PCA under limited computational resources.
problem Sparse PCA with limited computational budget.
method Thresholding Oja's algorithm output.
result Achieves minimax error bound in O(d) space and O(nd) time.
We quantify uncertainty in Oja's algorithm's leading eigenvector estimation.
problem Estimating the error of Oja's algorithm's leading eigenvector from streaming data.
method Combining U-statistics, high-dimensional central limit theorems, and multiplier bootstrap.
result Established a weighted χ² approximation for the error between the eigenvector and algorithm output.
Paper improves Oja's algorithm for Markovian data streams.
problem Estimating the top eigenvector of a covariance matrix from Markovian data.
method Improves Oja's algorithm for streaming PCA with Markovian dependence.
result First sharp rate for Oja's algorithm on entire data stream, removing sample size dependence.
We efficiently find top k eigenvectors in streaming PCA with global convergence.
problem Finding top k eigenvectors in streaming PCA with limited space.
method Developed global convergence for Oja's algorithm and a faster variant Oja++.
result Achieved global convergence rate matching information theoretic lower bound.
Gen-Oja efficiently computes principal vectors and canonical correlations in streaming data.
problem Principal Generalized Eigenvector computation and Canonical Correlation Analysis in stochastic settings.
method Gen-Oja is a simple and efficient algorithm that leverages two-time-scale stochastic approximation and fast-mixing Markov chains.
result Gen-Oja achieves optimal convergence rates for these problems.
Paper presents a new method for efficient deep learning with over-complete dictionaries.
problem Learning an over-complete basis for optimal reconstruction without optimization.
method Multiscale Residual Mixture of PCA with a hierarchical approach.
result Exponential decrease of error with depth in a recursive deep approach.
Low-precision streaming PCA estimates the leading eigenvector with limited precision.
problem Estimating the leading eigenvector in a streaming setting with limited precision.
method Oja's algorithm with linear and nonlinear stochastic quantization.
result A batched version of the quantized variants achieves the lower bound on quantization error up to logarithmic factors.
New algorithm reduces kernel PCA to O ( n ) O(\sqrt{n}) O ( n ) features for streaming data.
problem Efficiently performing kernel PCA on large datasets.
method Random Fourier features and Oja's algorithm for streaming.
result Achieves O ( 1 / ε 2 ) O(1/ε^2) O ( 1/ ε 2 ) sample complexity with O ( n ) O(\sqrt{n}) O ( n ) features. Analysis of three subspace estimation algorithms under incomplete data.
problem Estimating subspace from incomplete observations in high dimensions.
method High-dimensional analysis of Oja's method, GROUSE, and PETRELS.
result The time-varying principal angles converge weakly to deterministic processes with proper time scaling.
Robust PCA method works under uncertain covariance.
problem Principal component analysis under uncertain covariance.
method Robust streaming PCA with temporal uncertainty set.
result Noisy power method is rate-optimal in our setting.
Improved streaming PCA algorithm matches matrix Bernstein guarantees.
problem Efficiently estimating the top eigenvector of a covariance matrix in streaming data.
method Oja's algorithm with a suitable choice of step size.
result Streaming algorithm nearly matches batch method's accuracy and reduces sample complexity.
Online PCA phase transition depends on n / d log ( d ) n/d\log(d) n / d log ( d ) , not just n / d n/d n / d .
problem Understanding the phase transition in online PCA.
method Study of Oja's algorithm for online PCA.
result Phase transition in correlation between estimated and true eigenvector.
New implicit Krasulina's k-PCA update avoids QR-decomposition and improves convergence.
problem Online k-PCA problem with orthonormality constraint.
method Derived an implicit form of Krasulina's update that bypasses orthonormality constraint.
result The new update avoids costly QR-decomposition and yields superior convergence.
We consider a situation in which we see samples in R d \mathbb{R}^d R d drawn i.i.d. from some distribution with mean zero and unknown covariance A. We wish to compute the top eigenvector of A in an incremental fashion - with an algorithm that maintains an estimate of the top eigenvector in O(d) space, and incrementally adju…
EigenGame reinterprets PCA as a game to find eigenvectors.
problem Finding principal components efficiently and accurately.
method EigenGame treats PCA as a Nash equilibrium game, using gradient-based updates.
result EigenGame algorithm combines Oja's rule and Gram-Schmidt orthogonalization.
The paper tackles efficient dimensionality reduction for time series data using stochastic optimization.
problem Estimating the principle component of stationary time series data with nonconvex and dependent data points.
method Proposes a variant of Oja's algorithm combined with downsampling to control bias in stochastic gradient.
result Proves asymptotic rate of convergence and near optimal sample complexity for the proposed algorithm.
Paper explores stochastic algorithms for PCA, focusing on convergence and runtime.
problem Finding top k eigen vectors of data covariance matrix.
method Revisits and analyzes stochastic approaches to PCA optimization.
result Stochastic methods offer comparable or superior empirical performance to direct non-convex methods.
We study the problem of recovering the subspace spanned by the first k k k principal components of d d d -dimensional data under the streaming setting, with a memory bound of O ( k d ) O(kd) O ( k d ) . Two families of algorithms are known for this problem. The first family is based on the framework of stochastic gradient descent. Nevertheles…
A neuron is a basic physiological and computational unit of the brain. While much is known about the physiological properties of a neuron, its computational role is poorly understood. Here we propose to view a neuron as a signal processing device that represents the incoming streaming data matrix as a sparse vector of …
pPCA speeds up PCA by priming initial estimates for faster, more accurate results.
problem Improving the speed and accuracy of principal component analysis (PCA).
method pPCA is a two-step algorithm: first, an approximate-PCA method primes the data, then exact PCA is applied in the span of the initial estimate.
result pPCA improves accuracy significantly with a small computational cost, outperforming other methods across various datasets.
AgFlow speeds up model selection in penalized PCA.
problem Efficient model selection in penalized PCA for HDLSS settings.
method Implicit regularization effect of gradient flow to reduce computation complexity.
result AgFlow achieves the complete solution path of L2-penalized PCA.
A new method for streaming PCA provides confidence intervals for eigenvector entries.
problem Uncertainty quantification for individual entries in streaming PCA.
method Oja's algorithm, Bernstein-type concentration bound, Central Limit Theorem, subsampling algorithm.
result Sharp concentration bound and Central Limit Theorem for streaming PCA entries.
New algorithm learns principal subspace from random samples.
problem Learning principal subspace from small random submatrices.
method Stochastic gradient descent algorithm for neural networks.
result Algorithm can handle infinite rows and columns.
Improved online PCA algorithm learns from evolving norm of parameter vector.
problem Discarding evolving norm in online PCA leads to suboptimal learning.
method Implicitly Normalized Online PCA (INO-PCA) removes unit-norm constraint.
result Parameter norm evolution leads to improved learning behavior.
Algorithm estimates principal eigenvector with adaptive sensing, improving over non-adaptive methods.
problem Estimating principal eigenvector with limited scalar measurements.
method Compressed variant of Oja's algorithm using two adaptive measurements per sample.
result Convergence rate of O ( λ 1 λ 2 d 2 / ( Δ 2 t ) ) \mathcal{O}(λ_1λ_2 d^2 / (Δ^2 t)) O ( λ 1 λ 2 d 2 / ( Δ 2 t )) after t t t iterations, matching information-theoretic lower bound. A simple power iteration with momentum achieves optimal PCA in stochastic settings.
problem Accelerating PCA in the stochastic setting with limited data.
method A simple variant of the power iteration with momentum.
result Achieves optimal sample and iteration complexity of O ( 1 / Δ ) \mathcal{O}(1/\sqrt{Δ}) O ( 1/ Δ ) .