{"id":"7398a0a3-cf53-4bd4-b111-c2c8b6f9d26f","arxiv_id":"2412.11963","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A random-order streaming algorithm approximates the top eigenvector with near-linear memory whenever the spectral gap is constant, and a lower bound shows the heavy-row parameter is unavoidable.","lead":"This paper gives streaming algorithms that approximate the main direction of a data matrix when rows arrive in random order, using memory tied to the number of unusually large rows. It also proves that remembering those large rows is unavoidable, and it narrows the spectral gap needed in earlier work.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.7 relies on an unproved stable-rank preservation claim for the row-norm sampled light matrix; if false, the sampled stream may be too short for Theorem 2.6.","rationale":"I read the paper in good faith and focused on the formal chain proving Informal Theorem 1.1. Theorem 2.7 is the key step that removes the equal-norm assumption: it partitions into heavy and light rows, stores heavy rows, row-norm samples the light rows to make equal-norm rows, and then invokes Theorem 2.6. The invocation requires the sampled stream length to satisfy the lower bound in Theorem 2.6, which is proportional to α^{-4}ρ(Blight)log^6d. The proof asserts ρ(Blight) ≈ ρ(Alight) and a matching row count without proving it. This is the weakest point because if the assertion failed, the block power method would not see enough sampled rows, and the O(h·d·polylog d) space claim at constant gap would not follow. My analysis shows the assertion is actually provable: the sampled rows all have identical norm, so the Frobenius norm of Blight equals the number of sampled rows times a constant, and the number of sampled rows concentrates about C ε^{-2}ρ(Alight)log d; Theorem 2.1 already bounds the spectral norm of the sampled covariance. Thus the gap is a missing proof, not an error. The reader's weakest_assumption identifies exactly this missing stable-rank preservation, so I agree. I considered other potential issues: the R≤C1log²d restriction in Theorem 2.7 is handled by Section 4 for larger gaps; Lemma 2.3's application of the Wang-Xi inequality has an exponent typo but the conclusion is unaffected with a larger t constant; the lower bound and Oja hard instance appear sound aside from minor typos. None of these threaten the central claim as much as the stable-rank assertion. Since the concern is real and fixable, the conditional verdict should stay; I recommend no change to the reader's verdict.","tokens_in":18653,"tokens_out":39182,"duration_ms":300834,"concrete_test":"Add a formal lemma: under the row-norm sampling of Theorem 2.7 with all p_i<1, show with probability 1-1/poly(d) that (i) the number of sampled rows n′ lies in [(1/2)Cε^{-2}ρ(Alight)log d, (3/2)Cε^{-2}ρ(Alight)log d] via Chernoff, (ii) each sampled row has norm ε‖Alight‖_2/√(C log d), so ‖Blight‖_F² = n′ℓ² = Θ(‖Alight‖_F²), and (iii) by Theorem 2.1, ‖Blight‖_2² = (1±ε)‖Alight‖_2². Conclude ρ(Blight) = Θ(ρ(Alight)). Then verify that with ε = α²/log^{5/2}d and a sufficiently large constant C in the sampling probability, n′ ≥ c α^{-4}ρ(Blight)log^6d holds, so Theorem 2.6 applies.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Informal Theorem 1.1) depends on Theorem 2.7, whose proof needs the row-norm sampled matrix Blight to have enough rows to apply Theorem 2.6. The proof states 'ρ(Blight) ≈ ρ(Alight) and the number of rows in Blight is Θ(ρ(Alight)·log d·ε^{-2}), and therefore Θ(ρ(Blight)·log d·ε^{-2})' without proof. This is load-bearing: Theorem 2.6 requires the stream length to be n = Ω(α^{-4} ρ(Blight) η log^6 d), with η=1 after sampling. If ρ(Blight) were significantly larger than ρ(Alight), the actual number of sampled rows, which is proportional to ρ(Alight), could fall short. The missing step is a concentration argument: each sampled row has norm exactly ℓ = ε‖Alight‖_2/√(C log d), so ‖Blight‖_F² = n′ℓ², and n′ concentrates around C ε^{-2} ρ(Alight) log d; Theorem 2.1 already gives ‖Blight^T Blight - Alight^T Alight‖_2 ≤ ε‖Alight‖_2². Together these imply ρ(Blight) = Θ(ρ(Alight)) with high probability. The assertion is plausible and likely true, but it is not proven in the text, and the main theorem's space bound at constant gap rests on it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies single-pass streaming algorithms for approximating the top right singular vector of an n×d matrix A whose rows arrive in uniformly random order. The main claim (Informal Theorem 1.1) is that if the spectral gap parameter R = σ₁(A)²/σ₂(A)² is at least a sufficiently large constant and the stream contains at most h heavy rows (rows with Euclidean norm at least ‖A‖_F/(√d polylog d)), then there is a randomized algorithm using O(h·d·polylog d) bits that outputs a unit vector with correlation 1 - O(1/√R) to the top singular vector, with probability at least 4/5. The paper also proves a lower bound of Ω(hd/R) bits for achieving correlation 1 - Ω(1/R²), and analyzes the Price–Xun Oja-based algorithm, improving its required gap to O(log²d) in arbitrary order and O(log d) in random order, while presenting a hard instance at R = O(log d/log log d) for that algorithm.","tokens_in":18853,"tokens_out":8318,"duration_ms":68898,"significance":"If the main theorem is correct, it establishes that single-pass near-linear memory suffices for top-eigenvector approximation in random-order streams even at constant spectral gap, substantially improving the prior Ω(log n·log d) gap requirement of Price–Xun for adversarial orders. The heavy-row parameterization is natural, and the lower bound shows that dependence on h is necessary. The improvements to the Price–Xun analysis and the concrete hard instance for Oja's algorithm are also potentially valuable, though the hard-instance proof has a serious algebraic issue. The paper is clearly written and builds on appropriate tools (Magdon-Ismail row sampling, Wang–Xi singular-value inequalities, and the Price–Xun lower-bound instance), but the proof of the central theorem contains an unproved stable-rank preservation step and a scaling mismatch between the algorithm and the lemma it invokes.","major_comments":[{"comment":"The proof asserts 'ρ(Blight) ≈ ρ(Alight)' and uses this to conclude that the number of rows in Blight is Θ(ρ(Blight)·log d·ε^{-2}), which is then fed into Theorem 2.6's stream-length condition. No proof of this stable-rank preservation is given. Theorem 2.1 provides a spectral-norm bound on the sampled Gram matrix, but stable rank depends on both the Frobenius norm and the spectral norm. One needs an additional concentration argument, for example using the fact that each sampled row has norm exactly ℓ = ε‖Alight‖₂/√(C log d), so ‖Blight‖_F² = n′ℓ² with n′ concentrated around C ε^{-2} ρ(Alight) log d, together with the spectral bound ‖Blight^T Blight - Alight^T Alight‖₂ ≤ ε‖Alight‖₂². Without this step, the invocation of Theorem 2.6 is not justified, and the main theorem's space bound at constant gap rests on this assertion.","section":"§2.3, proof of Theorem 2.7"},{"comment":"There is a mismatch between the lemma used and the object computed by the algorithm. Lemma 2.3 requires matrices B_j satisfying ‖A^T A - B_j^T B_j‖₂ ≤ ε‖A‖₂², while Theorem 2.1 guarantees ‖A^T A - (1/p)B_j^T B_j‖₂ ≤ ε‖A‖₂² for an unscaled sampled block B_j. Algorithm 1's update acc ← acc + ⟨a_i, z_ρ⟩ a_i computes B_j^T B_j z without the 1/p rescaling. Since the subsequent normalization step makes the iteration invariant to an overall scalar factor 1/p, the analysis can be repaired by applying Lemma 2.3 to C_j = (1/√p)B_j, but the paper should state this explicitly. As written, the event claimed in the proof (involving unscaled B_j) does not match the quantity analyzed in Lemma 2.3.","section":"§2.2, Lemma 2.3 vs Algorithm 1"},{"comment":"The inequality 'exp(η/R)/(1+η/R)^R ≥ poly(d)' appears to be reversed for the stated parameter regime. For η ≥ R((c′d^{1/2})^{1/R} - 1) and R = O(log d/log log d), one has η/R ≈ (c′d^{1/2})^{1/R} ≈ √(log d), so (1+η/R)^R ≈ d^{1/2} while exp(η/R) ≈ exp(√(log d)). The ratio is therefore exp(√(log d) - (1/2)log d) = 1/poly(d), not poly(d). Consequently, the claimed lower bound |⟨z_n,e₃⟩| ≥ poly(d)·|⟨z_n,e₁⟩| does not follow from the preceding algebra, and the hard-instance argument for Oja's algorithm is not established as written.","section":"§5, proof of Theorem 5.1"}],"minor_comments":[{"comment":"The statement 'R = Ω(1)' and 'a sufficiently large constant C' should be made quantitative in the formal theorem; the current wording leaves the threshold unspecified.","section":"Abstract and Theorem 1.1"},{"comment":"The justification for guessing ‖A‖₂ relies on all nonzero entries having magnitude between 1/poly(nd) and poly(nd), but the number of nonzero entries also needs to be polynomially bounded for the interval bound to hold; this should be stated explicitly.","section":"§2.1"},{"comment":"The symbol 'greaterorsimilar' (rendered as a corrupted token) should be replaced with a standard notation such as ≳ or ≥ with a defined constant.","section":"§4.2"},{"comment":"The notation 'R = O_c(log d/log log d)' is nonstandard; please define it, for example by stating that the hidden constant may depend on the target correlation c.","section":"§5"},{"comment":"The theorem assumes R²·h = O(d), but the proof introduces 'h ≤ cd/R²' without connecting the constant c to the statement; please make the constant explicit and consistent.","section":"§3, Theorem 3.1 and proof"},{"comment":"The failure probability in the theorem is stated as 1 - (1/2)^{4R+4}, while the proof uses δ ≤ (1/2)^{k+4} with k = 4R; align these notations.","section":"§3, proof of Theorem 3.1"}],"recommendation":"major_revision","confidential_remarks":"The main upper-bound claim is plausible and likely fixable, but the unproved stable-rank assertion in Theorem 2.7 and the scaling mismatch in the block power method are real gaps. The error in the Oja hard-instance proof (Section 5) is more concerning because the stated inequality is numerically backwards; if it cannot be repaired, the authors should remove or substantially caveat that contribution. The lower-bound section appears sound in structure, though the presentation of the constants needs polishing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First: this is a real result. The random-order model plus block power method with non-overlapping sketches gives the first near-linear-space algorithm for top eigenvector at constant spectral gap, parameterized by heavy rows, and the lower bound shows the heavy-row dependence is necessary. The Price-Xun gap improvements and the hard instance for Oja are useful additions. The proofs are detailed and the external tools are appropriate; there is no self-citation loop.\n\nThe paper is in good shape, but I would not accept it without minor revisions. The reader's three concerns are real but uneven. The stable-rank assertion in Theorem 2.7 is unproved but it is not hard: each sampled row has norm exactly ℓ, so ||B_light||_F^2 concentrates around ρ(A_light)||A_light||_2^2, and Theorem 2.1 gives the spectral norm bound; together they give ρ(B_light)=Θ(ρ(A_light)). One-paragraph fix. The 1/p scaling inconsistency between Lemma 2.3 and Algorithm 1 is mostly notational: the unnormalized power method product differs from the scaled one by the scalar 1/p^t, which cancels in the final unit vector. The proof should say so, but the algorithm is not wrong. The Oja hard instance is the weakest spot. The proof uses exp(η/R) where the algebra gives exp(η/(2R)), and the claimed minimum point of the ratio shifts; making the argument work requires the constant c in R = O_c(log d/log log d) to be small enough. This looks fixable, but as written the theorem and proof do not match.\n\nNet: the main theorem is probably correct, the lower bound is sound, and the soft spots are presentation and small-constant bookkeeping rather than architecture. A serious referee should be assigned; the right decision after review would be conditional acceptance with requests for the missing concentration argument and a cleanup of the Oja proof. The paper is worth a reading group slot.","headline":"Genuine advance in streaming PCA; main theorem holds up, but the Oja hard instance needs a small-constant fix.","tokens_in":19469,"tokens_out":11261,"would_cite":true,"duration_ms":87317,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A random-order streaming algorithm approximates the top eigenvector with O(h d polylog(d)) bits even at constant spectral gap.","keywords":["streaming algorithms","top eigenvector","random order streams","block power method","row norm sampling","spectral gap","heavy rows","lower bounds"],"falsifier":"Construct an $n\\times d$ matrix $A_{\\mathrm{light}}$ whose rows all fall below the heavy threshold but are concentrated on few coordinates, so $\\rho(A_{\\mathrm{light}})$ is large; run the row-norm sampling at the theorem's $\\varepsilon$ and measure the stable rank of the sampled-and-rescaled matrix. If $\\rho(B_{\\mathrm{light}}) \\ll \\rho(A_{\\mathrm{light}})$ for a valid instance, the asserted approximation $\\rho(B_{\\mathrm{light}})\\approx\\rho(A_{\\mathrm{light}})$ fails and the stream-length guarantee in Theorem 2.6 no longer covers the light stream.","tokens_in":18358,"feed_emoji":"📈","tokens_out":8106,"duration_ms":69321,"temperature":0.7,"pith_summary":"This paper establishes that the top eigenvector of a worst-case matrix can be approximated from a single pass over its rows, provided the rows arrive in a uniformly random order, using memory that is near-linear in the dimension and controlled by the number of heavy rows. The main result is that when the spectral gap parameter $R=\\sigma_1(A)^2/\\sigma_2(A)^2$ exceeds a large constant and the stream has at most $h$ heavy rows, a randomized algorithm using $O(h d \\operatorname{polylog}(d))$ bits outputs a unit vector with squared correlation $1-O(1/\\sqrt{R})$ to the top eigenvector. This matters because arbitrary-order streaming algorithms previously needed $R=\\Omega(\\log n\\log d)$ for comparable guarantees, leaving constant-gap instances open. The paper also gives a lower bound $\\Omega(h d/R)$ for higher-accuracy output, showing the dependence on heavy rows is inherent.","feed_headline":"Constant spectral gap now enough for one-pass eigenvector approximation","feed_subtitle":"A block power method handles heavy rows separately and reaches the top eigenvector with near-linear memory.","key_machinery":"The central mechanism is a block power method carried by non-overlapping approximate quadratic forms. In a random-order stream, consecutive disjoint blocks of rows are statistically identical, so the first $y_j$ rows of block $j$ form a row-norm sample of the full stream, and the sampled-and-rescaled matrix $B_j$ satisfies $(1/p)B_j^TB_j \\approx A^TA$ in spectral norm. The product $M=(B_t^TB_t)\\cdots(B_1^TB_1)$ is then applied to a Gaussian vector, and the Wang-Xi singular-value inequality is used to bound $\\|M\\|_F$, showing that $M$ has stable rank close to 1 with its top singular vector near $v_1$. Heavy rows are stored exactly and treated separately, so the subsampled blocks see only light rows.","core_discovery":"On the paper's own terms, the central discovery is that the random-order assumption turns a single stream into many independent-looking passes. The algorithm fixes a sampling probability $p$, partitions the stream into $t=\\Theta(\\log d)$ non-overlapping blocks, and within each block keeps only a random subset of rows while rescaling them. Because the original order is uniformly random, the subset in each block is also uniform, and the row-norm sampling theorem guarantees each block matrix $B_j$ satisfies $\\|(1/p)B_j^TB_j - A^TA\\|_2 \\le \\varepsilon\\|A\\|_2^2$. Multiplying these matrices sequentially onto one Gaussian vector implements $t$ power-method iterations in one pass. Heavy rows are stored explicitly so that a single large row cannot be missed by the subsampling, and a Gaussian sketch selects the best of several power-method candidates. The paper further proves that any algorithm obtaining correlation $1-\\Omega(1/R^2)$ needs $\\Omega(hd/R)$ bits, so the $h$ factor in the upper bound is necessary.","pith_inferences":["If the paper is right, a natural practical recipe is to shuffle the data rows, store only rows of unusually large norm, and run the block power method; for many real matrices with few outliers, this would give one-pass PCA with near-linear memory even at small eigengaps.","The random-order assumption is what makes the non-overlapping blocks interchangeable; a direct empirical comparison against arbitrary-order sketches on permuted real datasets with $R$ near 1 would test whether this idealized assumption is the bottleneck.","The same block-sampling mechanism may extend to top-$k$ subspace recovery under a gap between the $k$-th and $(k+1)$-th singular values, since the Wang-Xi singular-value inequality used here is not rank-one specific.","The lower bound leaves a gap between the upper correlation $1-O(1/\\sqrt{R})$ and the lower-bound regime $1-\\Omega(1/R^2)$; whether the intermediate accuracy can be met with less than $hd/R$ bits is unresolved."],"forward_implications":["If the main theorem is right, single-pass top-eigenvector approximation at constant spectral gap is possible in near-linear memory whenever the number of heavy rows is small.","The space lower bound shows the algorithm's $h$ dependence cannot be removed while guaranteeing correlation $1-\\Omega(1/R^2)$.","Subsampling before the earlier arbitrary-order algorithm lowers its gap requirement to $\\Omega(\\log^2 d)$ in arbitrary order and $\\Omega(\\log d)$ in random order.","The constructed hard instance blocks Oja-type updates at gap $\\Theta(\\log d/\\log\\log d)$, so the constant-gap success is not obtained by tuning a single learning-rate Oja algorithm.","When the stream has no heavy rows, the same block method uses only $O(d\\operatorname{polylog}(d))$ bits."],"supporting_citations":[{"why":"Supplies the row-norm sampling theorem used to produce each approximate quadratic form $B_j^TB_j$.","marker":"Magdon-Ismail [2010]"},{"why":"Gives the singular-value inequality (Theorem 2.4) that bounds the Frobenius norm of the block product $M$.","marker":"Wang and Xi [1997]"},{"why":"The prior arbitrary-order streaming algorithm and lower-bound instance that this paper subsamples, improves, and extends with a random-order hard instance.","marker":"Price and Xun [2024]"},{"why":"Matrix Bernstein inequality used in the proof of the row-sampling spectral-norm guarantee.","marker":"Tropp [2015]"},{"why":"Randomized power method that the block method adapts to the single-pass streaming setting.","marker":"Gu [2015]"}],"fun_headline_variants":["Random order streams crack eigenvector with constant gap","One-pass top eigenvector: random order beats worst-case","Heavy rows don't break random-order eigenvector streaming","Subsampling blocks turn one stream into power iterations","Random order enables near-linear memory eigenvector top"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that row-norm sampling preserves the stable rank (squared Frobenius norm over squared spectral norm) of the light matrix; the paper asserts $\\rho(B_{\\mathrm{light}})\\approx\\rho(A_{\\mathrm{light}})$ without proof, and Theorem 2.6's required stream length depends on that preservation.","fun_headline_variants_meta":{"raw":{"variants":["Random order streams crack eigenvector with constant gap","One-pass top eigenvector: random order beats worst-case","Heavy rows don't break random-order eigenvector streaming","Subsampling blocks turn one stream into power iterations","Random order enables near-linear memory eigenvector top"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000187,"raw_usage":{"total_tokens":1454,"prompt_tokens":1198,"completion_tokens":256,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":814,"completion_tokens_details":{"reasoning_tokens":180}},"tokens_in":814,"tokens_out":256,"duration_ms":3299,"temperature":1.0,"reasoning_tokens":180,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:26:16.222699+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct an $n\\times d$ matrix $A_{\\mathrm{light}}$ whose rows all fall below the heavy threshold but are concentrated on few coordinates, so $\\rho(A_{\\mathrm{light}})$ is large; run the row-norm sampling at the theorem's $\\varepsilon$ and measure the stable rank of the sampled-and-rescaled matrix. If $\\rho(B_{\\mathrm{light}}) \\ll \\rho(A_{\\mathrm{light}})$ for a valid instance, the asserted approximation $\\rho(B_{\\mathrm{light}})\\approx\\rho(A_{\\mathrm{light}})$ fails and the stream-length guarantee in Theorem 2.6 no longer covers the light stream.","supporting_citations":[{"cited_title":"Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound","cited_arxiv_id":"1008.0587","evidence_quote":"Supplies the row-norm sampling theorem used to produce each approximate quadratic form $B_j^TB_j$."},{"cited_title":"Some inequalities for singular values of matrix products","cited_arxiv_id":null,"evidence_quote":"Gives the singular-value inequality (Theorem 2.4) that bounds the Frobenius norm of the block product $M$."},{"cited_title":"Spectral guarantees for adversarial streaming PCA","cited_arxiv_id":null,"evidence_quote":"The prior arbitrary-order streaming algorithm and lower-bound instance that this paper subsamples, improves, and extends with a random-order hard instance."},{"cited_title":"An introduction to matrix concentration inequalities","cited_arxiv_id":null,"evidence_quote":"Matrix Bernstein inequality used in the proof of the row-sampling spectral-norm guarantee."}],"review_version":1}