English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This work provides improved guarantees for streaming principle componentanalysis (PCA). Given $A_1, \ldots, A_n\in \mathbb{R}^{d\times d}$ sampledindependently from distributions satisfying $\mathbb{E}[A_i] = \Sigma$ for$\Sigma \succeq \mathbf{0}$, this work provides an $O(d)$-space linear-timesingle-pass streaming algorithm for estimating the top eigenvector of $\Sigma$.The algorithm nearly matches (and in certain cases improves upon) the accuracyobtained by the standard batch method that computes top eigenvector of theempirical covariance $\frac{1}{n} \sum_{i \in [n]} A_i$ as analyzed by thematrix Bernstein inequality. Moreover, to achieve constant accuracy, ouralgorithm improves upon the best previous known sample complexities ofstreaming algorithms by either a multiplicative factor of $O(d)$ or$1/\mathrm{gap}$ where $\mathrm{gap}$ is the relative distance between the toptwo eigenvalues of $\Sigma$.  These results are achieved through a novel analysis of the classic Oja'salgorithm, one of the oldest and most popular algorithms for streaming PCA. Inparticular, this work shows that simply picking a random initial point $w_0$and applying the update rule $w_{i + 1} = w_i + \eta_i A_i w_i$ suffices toaccurately estimate the top eigenvector, with a suitable choice of $\eta_i$. Webelieve our result sheds light on how to efficiently perform streaming PCA bothin theory and in practice and we hope that our analysis may serve as the basisfor analyzing many variants and extensions of streaming PCA.

Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm