Pith. sign in

REVIEW 2 major objections 4 minor 66 references

The Phase Transition in Online PCA Depends on $n/d\log(d)$, not $n/d$

T0 review · 2 major / 4 minor · reviewed 2026-07-31 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For Oja's streaming PCA, positive recovery of the top eigenvector from a random start requires n/(d log d) to exceed an explicit constant γ*, with an exact critical distribution; below it the overlap vanishes.

desk verdict This paper has the right answer and likely the right proof strategy, but a centering error in Lemma 3.2 makes the proof as written technically false; the fix should be routine. read the letter →

arxiv 2607.23914 v2 pith:G4Y62YTJ submitted 2026-07-27 math.ST eess.SPmath.PRstat.MLstat.TH

Apratim Dey This is my paper · ORCID
classification math.STeess.SPmath.PRstat.MLstat.TH MSC 62H2560F0560G42
keywords onlinePCAOja'salgorithmphasetransitionspikedcovariancemodelsamplecomplexityhigh-dimensionalstatisticsrandominitializationstochasticgradientdescent
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper shows that Oja's algorithm—the standard one-pass method for streaming PCA—has a sharp phase transition governed by n/(d log d), not the usual n/d. For data drawn from a spiked covariance model with random initialization, the overlap between the estimator and the true top eigenvector tends to 0 whenever n/(d log d) is below a critical constant γ*, and tends to an explicit positive plateau ρ* above it. At the critical sample size n = γ* d log d + η d, the limiting overlap is random, described by a formula involving a single standard Gaussian variable. The result separates online from offline PCA: streaming requires a log d factor more samples to escape the noise floor, and it also quantifies how step size trades off search time against final accuracy.

What carries the argument

The central object is the scalar overlap recursion for ρ_k = ⟨v̂_k, v0⟩, reduced in Lemma 3.2 to ρ_k = (1 + α/d)ρ_{k−1} − βρ_{k−1}³/d + M_k/d + R_k/d², with α = δ(θ² − δ/2) and β = δθ²(1 + δ/2). The proof then uses two simplifications: in the subcritical regime the martingale noise M_k is asymptotically equivalent to iid products δ A_k C_k, and once the overlap has risen above the O(d^{−1/2}) floor, the discrete recursion is approximated by the logistic ODE ρ′ = ρ(α − βρ²). The linear factor (1 + α/d)^{n−k} ≈ exp(α(n−k)/d), accumulated over n ≈ γ* d log d steps, carries the signal across the transition, while the cubic term parks the limit at ρ* = sqrt(α/β).

What would settle it

Run Oja at d = 10^4 with θ = 2, δ = 1 (γ* ≈ 0.14, ρ* ≈ 0.76) over many independent random starts: if the median |overlap| leaves 0 substantially before n = γ* d log d, or if it saturates at a value measurably different from ρ* for n much larger than γ* d log d, the predicted threshold or plateau fails. Also test the δ > 2θ² prediction (e.g., θ = 1, δ = 2.5): if overlap recovers for very large n instead of tending to 0, Theorem 3.3 is wrong.

Watch

Extended reading notes

Core claim

Let X_k be iid N(0, Σ) with Σ = θ² v0 v0ᵀ + I, and run Oja's update ṽ_k = v̂_{k−1} + (δ/d)⟨X_k, v̂_{k−1}⟩X_k, v̂_k = ṽ_k/‖ṽ_k‖, starting from v̂_0 uniform on the sphere. The paper proves that as n,d → ∞ with n/(d log d) → γ ∈ (0,∞), the absolute overlap |⟨v̂_n, v0⟩| converges in probability to 0 if γ < γ*, and to ρ* if γ > γ*, where γ* = 1/(δ(2θ² − δ)) and ρ* = sqrt((θ² − δ/2)/(θ²(1 + δ/2))). At n = [γ* d log d + η d], the absolute overlap converges weakly to ρ* |G| exp(η/2γ*) / sqrt(ρ*⁴ + G² exp(η/γ*)) with G ∼ N(0,1). If δ > 2θ², the linear gain is negative and the overlap tends to 0 for every n,d. The paper also proves that the same threshold, plateau, and critical law hold for a spher

Load-bearing premise

The proof rests on the approximation that the true martingale noise in the overlap recursion can be replaced by iid Gaussian products and the discrete dynamics by a logistic ODE, with errors that stay negligible after being amplified by exp(α(n−k)/d) over roughly γ* d log d steps; if those neglected terms are not negligible, the exact constants γ* and ρ* would change.

Editorial extensions

If this is right

  • Positive overlap from a random start is impossible when n is merely linear in d; the sample complexity of Oja from random initialization is Θ(d log d), with explicit prefactor γ*.
  • Above the threshold, more samples do not improve the estimator: the overlap saturates at ρ* < 1, and the only way to push ρ* closer to 1 is to shrink δ, which increases γ* and lengthens the search phase.
  • At δ* = θ², the threshold γ* equals 1/θ⁴, the same functional form as the classical offline PCA transition; the two transitions coincide positionally even though their time scales differ by log d.
  • At criticality the limiting overlap is random with a closed-form law, so the transition occupies a Θ(d) window in n and individual runs near the threshold are not reproducible in value.
  • The same γ*, ρ*, and critical distribution hold for the spherical-gradient variant of Oja, so the result is insensitive to the choice of normalization in the update.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the d log d law extends beyond Gaussian data, then any single-pass stochastic-gradient estimator initialized near uniform on the sphere should need a log d factor more samples than its offline counterpart; testing with sub-Gaussian or heavy-tailed distributions would reveal whether the constants shift with higher moments.
  • The random critical law suggests that the first escape from the noise floor is a random event; a testable prediction is that individual trajectories at n = n* are concentrated near 0 or near ρ*, while the averaged law follows the Gaussian formula.
  • The tradeoff between γ* and ρ* offers a practical rule for choosing δ: δ = θ² minimizes the sample threshold but gives a plateau that decreases with θ, while smaller δ buys accuracy only at the cost of more samples before the search phase ends.
  • The finite-d experiments in the paper already show the transition sharpening with d; a sharper falsifiable test would estimate γ* from the crossing of median overlap curves across several (θ, δ, d) and compare the fitted values with the formula γ*(θ, δ).
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper analyzes Oja's online PCA algorithm on the Gaussian spiked covariance model with random initialization and step size δ/d. It claims a sharp phase transition in the scaling n/(d log d): below γ_* the overlap with the signal vanishes, above γ_* it converges to ρ_*, and in an O(d) window around criticality the overlap has an explicit Gaussian-mixture limit. The proof is based on an approximate one-dimensional recursion for the signed overlap, a martingale approximation that replaces the noise by i.i.d. products, and a comparison with the logistic ODE after a search phase of length γ_* d log d. The same constants and critical law are claimed for a spherical-gradient variant. Numerical experiments and QQ plots are provided in support.

Significance. If the results are correct, they establish that random-initialized Oja requires Θ(d log d) samples for any nonvanishing overlap, in contrast to offline PCA's Θ(d) scaling, and they give exact constants and a non-Gaussian critical distribution. This is a substantial contribution to the high-dimensional theory of online PCA and stochastic gradient descent. The paper is commendably concrete: the constants γ_* and ρ_* are explicit closed-form expressions, the critical law is stated exactly, the logistic-ODE solution is used rather than a qualitative approximation, and the simulations validate the predicted thresholds, plateaus, and Gaussian QQ behavior. The derivation is not circular: the constants come from the recursion, not from the data.

major comments (2)
  1. [Lemma 3.2, Eq. (16)] The claimed martingale property of M_k is false as stated. In the last term of Eq. (16), the centering constant is θ^2ρ_{k-1}^2+1, but E[B_k^2 ||D_k||^2/d | F_{k-1}] = (θ^2ρ_{k-1}^2+1)(d-2)/d. Consequently E[M_k|F_{k-1}] = δ^2 ρ_{k-1}(θ^2ρ_{k-1}^2+1)/d ≠ 0. This is a lower-order O(ρ/d^2) contribution to the recursion after division by d, so the main constants and conclusions are probably unaffected. However, Lemma 6.2 explicitly treats S_k = M_k − δ A_k C_k as a martingale difference, so the proof of the central approximation is not valid as written. The fix is to center the last term using the correct conditional mean and absorb the difference into R_k, or to carry the nonzero mean through Lemma 6.2. Given that this lemma underlies Theorems 3.4–3.6, the proof needs correction before publication.
  2. [Lemmas 6.2 and 6.3] The L^2 bounds that justify replacing M_k by δ A_k C_k omit the squared-mean contribution that appears once S_k is not a true martingale difference. With E[S_k|F_{k-1}] = O(ρ_{k-1}/d), the omitted term is of order n^2 e^{2α n/d}/d^5, which tends to zero at the relevant scalings, so the lemma is salvageable; but the proof should state and estimate this term. In addition, Lemma 6.3's displayed variance computation drops a factor of d: ∑_{k=0}^n c_d^{2k} ∼ d(e^{2α n/d}−1)/(2α), so the second equality should contain an extra 1/d. Without that factor, the expression diverges; restoring it gives the stated limit γ_*δ^2(θ^2+1). These are proof errors in exactly the estimates that feed the critical law, and they should be fixed explicitly.
minor comments (4)
  1. [Lemma 6.1] In the proof, for α<0 the intermediate term C/(2α d) exp(2αk/d) is negative; the α<0 case should be bounded separately. The final bound E|ρ_k|^3 ≤ C exp(3αk/d)/d^{3/2} remains true, but the displayed derivation is not valid as written.
  2. [Tables 7 and 8] The table headers list δ=0.2 for both tables, but the reported γ_* and ρ_* values correspond to δ=0.6 and δ=1, respectively (compare Figure 6). The labels should be corrected.
  3. [Abstract and Eq. (10)] The formula for γ_* is ambiguous as typeset: it should read γ_* = 1/[2δ(θ^2 − δ/2)_+] or equivalently 1/[δ(2θ^2 − δ)_+], not '1/2δ(θ^2−δ/2)_+'.
  4. [Lemma 6.6] The Gronwall argument is applied with a right-hand side that depends on k (through √k and k). The argument works because the bound is monotone in k, but this should be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the phase-transition constants are derived from the Oja recursion itself, not fitted to data or imported from self-citations.

full rationale

The central derivation is self-contained. Lemma 3.2 (Eq. 8) obtains the recursion ρ_k = (1+α/d)ρ_{k-1} - βρ_{k-1}^3/d + M_k/d + R_k/d^2 by a Taylor expansion of the Oja update (7); the constants α=δ(θ²-δ/2), β=δθ²(1+δ/2), and hence γ*=1/(2α), ρ*=sqrt(α/β), are algebraic consequences of this expansion, not fit parameters. Theorems 3.4-3.6 then follow by propagating these recursions via Lemmas 6.1-6.6, with explicit error bounds (e.g., Lemma 6.2 bounds the replacement M_k≈δA_kC_k by a vanishing L2 bound; Lemma 6.6 bounds the discrete-to-ODE approximation). The BBP identity γ*(θ,δ*)=1/θ^4 is presented as an observed 'curious connection' after the theorems and plays no role in the derivations, so it is not a renamed input. There are no self-citation chains: the cited Gronwall inequality (Ben Arous et al. 2021) is proved in the paper (Lemma 6.4), and the author is not an author of that cited work. The only caveat noted by the reviewer is technical, not circular: the proof of Lemma 3.2 claims E[M_k|F_{k-1}]=0 but the term involving B_k^2||D_k||^2/d is centered with (θ²ρ²+1) rather than its exact conditional mean (θ²ρ²+1)(d-2)/d, leaving a small O(ρ/d²) bias. This is a correctness/approximation concern for the proof as written, but it is not a reduction of the prediction to its inputs, and the claimed constants are not defined in terms of the target overlap. Hence circularity score 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted: θ and δ are inputs inherited from the problem, and the thresholds γ*, ρ* are derived, not calibrated to the simulations. The derivation relies on the Gaussian spiked model, uniform random initialization, and Oja's specific step-size normalization. No new physical or algorithmic entities are introduced.

assumptions (4)
  • domain assumption X_k iid N(0,Σ), Σ=θ²v0v0^T+I (Johnstone spiked covariance)
    Assumed at start of Section 3; Lemma 3.1's independence and chi-square structure rely on Gaussianity and isotropy of the noise subspace.
  • domain assumption Initialization v̂0 ~ Unif(S^{d−1}) independent of the data
    Used for Eρ0²=1/d and d^{1/2}ρ0 ⇒ N(0,1); the phase-transition statements are for random initialization, and the critical window changes with informative starts.
  • domain assumption Constant step-size scaling δ/d with δ>0 fixed, and α=δ(θ²−δ/2)>0 for Theorems 3.4–3.6
    Theorem 3.3 covers α<0 separately; all threshold formulas and proofs for the main phase transition assume the positive-drift regime δ<2θ².
  • standard math Standard martingale CLT, Slutsky's lemma, continuous mapping, and discrete Gronwall lemma
    These are invoked throughout Section 6 without proof; they are standard background but are necessary for the critical-window distribution and the ODE approximation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Phase Transition in Online PCA Depends on $n/d\log(d)$, not $n/d$." pith.science (2026). https://pith.science/paper/G4Y62YTJ

@misc{pith2026260723914,
  author       = {Pith},
  title        = {Pith review of: The Phase Transition in Online PCA Depends on $n/d\log(d)$, not $n/d$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G4Y62YTJ}},
  note         = {Machine review of arXiv:2607.23914}
}
abstract

High dimensional statistical theory has established the importance of constant aspect ratio, when the number of dimensions ($d$) and samples ($n$) satisfy $n,d\to\infty$ with $n/d\to \gamma\in(0,\infty)$, in understanding the limits of canonical estimation problems. In particular, for estimating the top eigenvector of a $d\times d$ population covariance matrix from $n$ iid samples, the BBP phase transition gives a precise threshold -- a simple functional of the aspect ratio -- such that the top sample principal component attains nonzero asymptotic correlation with the truth only when the leading population eigenvalue exceeds it. In this paper, we show that for online / streaming algorithms the story is very different, and constant aspect ratio is insufficient for nonzero overlap. We study Oja's algorithm, the most popular method for online PCA. Let $\Sigma=\theta^2 v_0v_0^\top+I\in\mathbb{R}^{d\times d}$, and run Oja's algorithm with step size $\delta/d$ on $n$ iid samples $X_k\sim\mathcal{N}(0,\Sigma)$, with output $\hat v_n$. Then, as $n,d\to\infty$ with $n/d\log d\to\gamma\in(0,\infty)$, we establish a phase transition: $|\langle\hat v_n,v_0\rangle|\to 0$ when $\gamma<\gamma_*$, and $\to\rho_*$ when $\gamma>\gamma_*$. Here $\rho_*=\rho_*(\theta,\delta)=\sqrt{(\theta^2-\delta/2)_+/\theta^2(1+\delta/2)}$ and $\gamma_*=\gamma_*(\theta,\delta)=1/2\delta(\theta^2-\delta/2)_+$. Further, at criticality, when $n=[\gamma_*d\log d+\eta d]$ and $d\to\infty$, $\eta\in\mathbb{R}$, the correlation is random: $|\langle\hat v_n,v_0\rangle|\stackrel{w}{\to}\rho_*|G|\exp(\eta/2\gamma_*)/\sqrt{\rho_*^4+G^2\exp(\eta/\gamma_*)}$ where $G\sim\mathcal{N}(0,1)$. This is in stark contrast to ordinary high dimensional PCA, where nonzero overlap is possible at constant $n/d$ and improves as $n/d$ increases.

Figures

Figures reproduced from arXiv: 2607.23914 by the authors.

Figure 1
Figure 1. Plot of ρ∗(θ, δ) as a function of δ for different values of θ. When δ > 2θ 2 , i.e. α < 0, ρ∗(θ, δ) = 0. Larger θ’s show better correlation at any δ. 0.3 0.4 0.5 0.6 0.7 0 1 2 3 θ ρ*(θ, δ*) [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Plot of ρ∗(θ, δ∗) as a function of θ, where δ∗ = θ 2 is the optimal δ minimizing γ∗(θ, δ). The curve is decreasing in θ. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Performance of Oja’s algorithm for θ = 1 and δ ∈ {0.1, 0.2} across different d. x-axis is rescaled to n/n∗ so that the vertical red dotted line shows the phase transition threshold at 1. Horizontal dotted line shows ρ∗. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: Performance of Oja’s algorithm for θ = 1 and δ ∈ {0.6, 1} across different d. x-axis is rescaled to n/n∗ so that the vertical red dotted line shows the phase transition threshold at 1. Horizontal dotted line shows ρ∗. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]
Figure 5
Figure 5. Figure 5: Performance of Oja’s algorithm for θ = 2 and δ ∈ {0.1, 0.2} across different d. x-axis is rescaled to n/n∗ so that the vertical red dotted line shows the phase transition threshold at 1. Horizontal dotted line shows ρ∗. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: Performance of Oja’s algorithm for θ = 2 and δ ∈ {0.6, 1} across different d. x-axis is rescaled to n/n∗ so that the vertical red dotted line shows the phase transition threshold at 1. Horizontal dotted line shows ρ∗. 16 [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]
Figure 7
Figure 7. Figure 7: QQ plots of transformed (signed) overlaps at [PITH_FULL_IMAGE:figures/full_fig_p017_7.png]
Figure 8
Figure 8. Figure 8: Performance of spherical Oja for θ = 1 and δ ∈ {0.1, 0.2} across different d. x-axis is rescaled to n/n∗ so that the vertical red dotted line shows the phase transition threshold at 1. Horizontal dotted line shows ρ∗. 21 [PITH_FULL_IMAGE:figures/full_fig_p021_8.png]
Figure 9
Figure 9. Figure 9: Performance of spherical Oja for θ = 1 and δ ∈ {0.6, 1} across different d. x-axis is rescaled to n/n∗ so that the vertical red dotted line shows the phase transition threshold at 1. Horizontal dotted line shows ρ∗. 22 [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]
Figure 10
Figure 10. Figure 10: Performance of spherical Oja for θ = 2 and δ ∈ {0.1, 0.2} across different d. x-axis is rescaled to n/n∗ so that the vertical red dotted line shows the phase transition threshold at 1. Horizontal dotted line shows ρ∗. 23 [PITH_FULL_IMAGE:figures/full_fig_p023_10.png]
Figure 11
Figure 11. Figure 11: Performance of spherical Oja for θ = 2 and δ ∈ {0.6, 1} across different d. x-axis is rescaled to n/n∗ so that the vertical red dotted line shows the phase transition threshold at 1. Horizontal dotted line shows ρ∗. 24 [PITH_FULL_IMAGE:figures/full_fig_p024_11.png]
Figure 12
Figure 12. Figure 12: QQ plots of transformed (signed) overlaps for spherical Oja at [PITH_FULL_IMAGE:figures/full_fig_p025_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 3 linked inside Pith

  1. [1]

    High-dimensional analysis of semidefinite relaxations for sparse principal components

    Arash A Amini and Martin J Wainwright. High-dimensional analysis of semidefinite relaxations for sparse principal components. In 2008 IEEE international symposium on information theory, pp.\ 2454--2458. IEEE, 2008

    2008

  2. [2]

    Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices

    Jinho Baik, G \'e rard Ben Arous, and Sandrine P \'e ch \'e . Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices . The Annals of Probability, 33 0 (5): 0 1643 -- 1697, 2005. doi:10.1214/009117905000000233. URL https://doi.org/10.1214/009117905000000233

    doi:10.1214/009117905000000233 2005

  3. [3]

    Online stochastic gradient descent on non-convex losses from high-dimensional inference

    Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22 0 (106): 0 1--51, 2021

    2021

  4. [4]

    High-dimensional limit theorems for sgd: Effective dynamics and critical scaling

    Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for sgd: Effective dynamics and critical scaling. Advances in neural information processing systems, 35: 0 25349--25362, 2022

    2022

  5. [5]

    The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

    Florent Benaych-Georges and Raj Rao Nadakuditi. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Advances in Mathematics, 227 0 (1): 0 494--521, 2011

    2011

  6. [6]

    The singular values and vectors of low rank perturbations of large rectangular random matrices

    Florent Benaych-Georges and Raj Rao Nadakuditi. The singular values and vectors of low rank perturbations of large rectangular random matrices. Journal of Multivariate Analysis, 111: 0 120--135, 2012

    2012

  7. [7]

    Probability and measure

    Patrick Billingsley. Probability and measure. John Wiley & Sons, 2017

    2017

  8. [8]

    Online principal components analysis

    Christos Boutsidis, Dan Garber, Zohar Karnin, and Edo Liberty. Online principal components analysis. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pp.\ 887--901. SIAM, 2014

    2014

Show all 66 references
  1. [9]

    Online principal component analysis in high dimension: Which algorithm to choose? International Statistical Review, 86 0 (1): 0 29--50, 2018

    Herv \'e Cardot and David Degras. Online principal component analysis in high dimension: Which algorithm to choose? International Statistical Review, 86 0 (1): 0 29--50, 2018

    2018

  2. [10]

    Information-theoretically optimal sparse pca

    Yash Deshpande and Andrea Montanari. Information-theoretically optimal sparse pca. In 2014 IEEE International Symposium on Information Theory, pp.\ 2197--2201. IEEE, 2014

    2014

  3. [11]

    Sparse pca via covariance thresholding

    Yash Deshpande and Andrea Montanari. Sparse pca via covariance thresholding. Journal of Machine Learning Research, 17 0 (141): 0 1--41, 2016

    2016

  4. [12]

    Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing

    David Donoho and Jared Tanner. Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367 0 (...

    1906

  5. [15]

    Streaming pca: Matching matrix bernstein and near-optimal finite sample guarantees for oja’s algorithm

    Prateek Jain, Chi Jin, Sham M Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming pca: Matching matrix bernstein and near-optimal finite sample guarantees for oja’s algorithm. In Conference on learning theory, pp.\ 1147--1164. PMLR, 2016

    2016

  6. [16]

    On the distribution of the largest eigenvalue in principal components analysis

    Iain M Johnstone. On the distribution of the largest eigenvalue in principal components analysis. The Annals of statistics, 29 0 (2): 0 295--327, 2001

    2001

  7. [17]

    On consistency and sparsity for principal components analysis in high dimensions

    Iain M Johnstone and Arthur Yu Lu. On consistency and sparsity for principal components analysis in high dimensions. Journal of the American Statistical Association, 104 0 (486): 0 682--693, 2009

    2009

  8. [18]

    Pca in high dimensions: An orientation

    Iain M Johnstone and Debashis Paul. Pca in high dimensions: An orientation. Proceedings of the IEEE, 106 0 (8): 0 1277--1292, 2018

    2018

  9. [19]

    Method of stochastic approximation in the determination of the largest eigenvalue of the mathematical expectation of random matrices

    T Krasulina. Method of stochastic approximation in the determination of the largest eigenvalue of the mathematical expectation of random matrices. Automatation and remote control, 2: 0 50--56, 1970

    1970

  10. [20]

    Streaming pca for markovian data

    Syamantak Kumar and Purnamrita Sarkar. Streaming pca for markovian data. Advances in Neural Information Processing Systems, 36: 0 64650--64662, 2023

    2023

  11. [22]

    Diffusion approximations for online principal component estimation and global convergence

    Chris Junchi Li, Mengdi Wang, Han Liu, and Tong Zhang. Diffusion approximations for online principal component estimation and global convergence. Advances in Neural Information Processing Systems, 30, 2017

    2017

  12. [24]

    Bootstrapping the error of oja's algorithm

    Robert Lunde, Purnamrita Sarkar, and Rachel Ward. Bootstrapping the error of oja's algorithm. Advances in neural information processing systems, 34: 0 6240--6252, 2021

    2021

  13. [25]

    Multivariate analysis

    Kanti V Mardia, John T Kent, and Charles C Taylor. Multivariate analysis. John Wiley & Sons, 2024

    2024

  14. [26]

    Estimation of low-rank matrices via approximate message passing

    Andrea Montanari and Ramji Venkataramanan. Estimation of low-rank matrices via approximate message passing . The Annals of Statistics, 49 0 (1): 0 321 -- 345, 2021. doi:10.1214/20-AOS1958. URL https://doi.org/10.1214/20-AOS1958

    2021 doi

  15. [27]

    Online pca with optimal regret

    Jiazhong Nie, Wojciech Kotlowski, and Manfred K Warmuth. Online pca with optimal regret. Journal of Machine Learning Research, 17 0 (173): 0 1--49, 2016

    2016

  16. [28]

    Simplified neuron model as a principal component analyzer

    Erkki Oja. Simplified neuron model as a principal component analyzer. Journal of mathematical biology, 15 0 (3): 0 267--273, 1982

    1982

  17. [29]

    On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix

    Erkki Oja and Juha Karhunen. On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix. Journal of mathematical analysis and applications, 106 0 (1): 0 69--84, 1985

    1985

  18. [30]

    Optimality and sub-optimality of pca i: Spiked random matrix models

    Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra. Optimality and sub-optimality of pca i: Spiked random matrix models. The Annals of Statistics, 46 0 (5): 0 2416--2451, 2018

    2018

  19. [32]

    An introduction to ordinary differential equations

    James C Robinson. An introduction to ordinary differential equations. Cambridge University Press, 2004

    2004

  20. [33]

    Online learning for sparse pca in high dimensions: Exact dynamics and phase transitions

    Chuang Wang and Yue M Lu. Online learning for sparse pca in high dimensions: Exact dynamics and phase transitions. In 2016 IEEE Information Theory Workshop (ITW), pp.\ 186--190. IEEE, 2016

    2016

  21. [35]

    Randomized online pca algorithms with regret bounds that are logarithmic in the dimension

    Manfred K Warmuth and Dima Kuzmin. Randomized online pca algorithms with regret bounds that are logarithmic in the dimension. Journal of Machine Learning Research, 9 0 (10): 0 2287--2320, 2008

    2008

  22. [36]

    The Annals of statistics , volume=

    On the distribution of the largest eigenvalue in principal components analysis , author=. The Annals of statistics , volume=. 2001 , publisher=

    2001

  23. [37]

    The Annals of Probability , number =

    Jinho Baik and G. The Annals of Probability , number =. 2005 , doi =

    2005

  24. [38]

    Advances in Mathematics , volume=

    The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices , author=. Advances in Mathematics , volume=. 2011 , publisher=

    2011

  25. [39]

    Proceedings of the IEEE , volume=

    PCA in high dimensions: An orientation , author=. Proceedings of the IEEE , volume=. 2018 , publisher=

    2018

  26. [40]

    Journal of mathematical biology , volume=

    Simplified neuron model as a principal component analyzer , author=. Journal of mathematical biology , volume=. 1982 , publisher=

    1982

  27. [41]

    Journal of mathematical analysis and applications , volume=

    On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix , author=. Journal of mathematical analysis and applications , volume=. 1985 , publisher=

    1985

  28. [42]

    2014 , publisher=

    Martingale limit theory and its application , author=. 2014 , publisher=

    2014

  29. [43]

    Lecture notes, University of Chicago Department of Statistics , year=

    The Martingale Central Limit Theorem , author=. Lecture notes, University of Chicago Department of Statistics , year=

  30. [44]

    2004 , publisher=

    An introduction to ordinary differential equations , author=. 2004 , publisher=

    2004

  31. [45]

    2024 , publisher=

    Multivariate analysis , author=. 2024 , publisher=

    2024

  32. [46]

    Journal of Machine Learning Research , volume=

    Online stochastic gradient descent on non-convex losses from high-dimensional inference , author=. Journal of Machine Learning Research , volume=

  33. [47]

    Journal of Multivariate Analysis , volume=

    The singular values and vectors of low rank perturbations of large rectangular random matrices , author=. Journal of Multivariate Analysis , volume=. 2012 , publisher=

    2012

  34. [48]

    The Annals of Statistics , volume=

    Optimality and sub-optimality of PCA I: Spiked random matrix models , author=. The Annals of Statistics , volume=. 2018 , publisher=

    2018

  35. [49]

    2016 IEEE Information Theory Workshop (ITW) , pages=

    Online learning for sparse PCA in high dimensions: Exact dynamics and phase transitions , author=. 2016 IEEE Information Theory Workshop (ITW) , pages=. 2016 , organization=

    2016

  36. [50]

    arXiv preprint arXiv:1712.04332 , year=

    Scaling limit: Exact and tractable analysis of online learning algorithms with applications to regularized regression and PCA , author=. arXiv preprint arXiv:1712.04332 , year=

    arXiv

  37. [51]

    Journal of the American Statistical Association , volume=

    On consistency and sparsity for principal components analysis in high dimensions , author=. Journal of the American Statistical Association , volume=. 2009 , publisher=

    2009

  38. [52]

    Journal of Machine Learning Research , volume=

    Sparse PCA via covariance thresholding , author=. Journal of Machine Learning Research , volume=

  39. [53]

    2014 IEEE International Symposium on Information Theory , pages=

    Information-theoretically optimal sparse PCA , author=. 2014 IEEE International Symposium on Information Theory , pages=. 2014 , organization=

    2014

  40. [54]

    2008 IEEE international symposium on information theory , pages=

    High-dimensional analysis of semidefinite relaxations for sparse principal components , author=. 2008 IEEE international symposium on information theory , pages=. 2008 , organization=

    2008

  41. [55]

    The Annals of Statistics , number =

    Andrea Montanari and Ramji Venkataramanan , title =. The Annals of Statistics , number =. 2021 , doi =

    2021

  42. [56]

    Proceedings of the National Academy of Sciences , volume =

    Gen Li and Wei Fan and Yuting Wei , title =. Proceedings of the National Academy of Sciences , volume =. 2023 , doi =. https://www.pnas.org/doi/pdf/10.1073/pnas.2302930120 , abstract =

    2023 doi

  43. [57]

    Automatation and remote control , volume=

    Method of stochastic approximation in the determination of the largest eigenvalue of the mathematical expectation of random matrices , author=. Automatation and remote control , volume=

  44. [58]

    Journal of Machine Learning Research , volume=

    Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension , author=. Journal of Machine Learning Research , volume=. 2008 , publisher=

    2008

  45. [59]

    Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Online principal components analysis , author=. Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2014 , organization=

    2014

  46. [60]

    Conference on learning theory , pages=

    Streaming pca: Matching matrix bernstein and near-optimal finite sample guarantees for oja’s algorithm , author=. Conference on learning theory , pages=. 2016 , organization=

    2016

  47. [61]

    Journal of Machine Learning Research , volume=

    Online PCA with optimal regret , author=. Journal of Machine Learning Research , volume=

  48. [62]

    arXiv preprint arXiv:1905.12115 , year=

    AdaOja: Adaptive learning rates for streaming PCA , author=. arXiv preprint arXiv:1905.12115 , year=

    1905 arXiv

  49. [63]

    Advances in neural information processing systems , volume=

    Bootstrapping the error of Oja's algorithm , author=. Advances in neural information processing systems , volume=

  50. [64]

    International Statistical Review , volume=

    Online principal component analysis in high dimension: Which algorithm to choose? , author=. International Statistical Review , volume=. 2018 , publisher=

    2018

  51. [65]

    Advances in Neural Information Processing Systems , volume=

    Streaming pca for markovian data , author=. Advances in Neural Information Processing Systems , volume=

  52. [66]

    arXiv preprint arXiv:2506.12655 , year=

    Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA , author=. arXiv preprint arXiv:2506.12655 , year=

    arXiv

  53. [67]

    arXiv preprint arXiv:2511.18273 , year=

    Time-uniform concentration bounds for iterative algorithms , author=. arXiv preprint arXiv:2511.18273 , year=

  54. [68]

    Advances in neural information processing systems , volume=

    High-dimensional limit theorems for sgd: Effective dynamics and critical scaling , author=. Advances in neural information processing systems , volume=

  55. [69]

    arXiv preprint arXiv:2512.13634 , year=

    Universality of high-dimensional scaling limits of stochastic gradient descent , author=. arXiv preprint arXiv:2512.13634 , year=

  56. [70]

    Advances in Neural Information Processing Systems , volume=

    Diffusion approximations for online principal component estimation and global convergence , author=. Advances in Neural Information Processing Systems , volume=

  57. [71]

    2017 , publisher=

    Probability and measure , author=. 2017 , publisher=

    2017

  58. [72]

    Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume=

    Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing , author=. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume=. 2009 , publisher=

    2009

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.