REVIEW 3 major objections 9 minor 13 references
What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?
T0 review · 3 major / 9 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read The paper proposes an iteration that applies a sketched inverse to the sketching error rather than to the eigenvector, establishing linear-quadratic convergence whose linear factor is proportional to the sketch distortion and, for top-k…
desk verdict A genuinely new error-powered fixed-point iteration and a clean final-gap rate, but the main theorem's entry condition is never verified for the implemented heuristic shift. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the EPSI update $u_{k+1} = (\hat{A} - \lambda(u_k)I)^{-1}(\hat{A} - A)u_k / \|\cdot\|$, which the paper interprets as Newton's method on the Lagrangian form $F(u,\lambda) = \tfrac12 u^{\top}Au - \tfrac{\lambda}{2}(u^{\top}u - 1)$ with the Hessian replaced by $\hat{A} - \lambda I$. The true eigenvector is a fixed point for every $\hat{A}$, so $\hat{A}$ acts purely as a preconditioner; its quality is measured by $\eta$ in the Loewner bound $A - 3\eta I \preceq \hat{A} \preceq A - \eta I$. The paper builds $\hat{A}$ from a rank-$\ell$ Nystr\"om approximation, subtracts a heuristic shift $c \approx 2\eta$ to make it invertible and satisfy the bound, and uses the Woodbury identity to invert $(I-UU^{\top})\hat{A}(I-UU^{\top}) - \lambda I$ in $O(n\ell^2 + \ell^3)$. A final orthogonalization step, projection onto the current k-dimensional subspace followed by SVD, removes the dependence on intermediate spectral gaps.
What would settle it
Compute $\hat{A} - A$ and $A - \hat{A}$ for a representative preconditioner built with the paper's shift rule; if either matrix has an eigenvalue below the claimed tolerance, the entry condition $A - 3\eta I \preceq \hat{A} \preceq A - \eta I$ fails and the theorem's assumptions are not met. Alternatively, run Lazy-EPSI on a matrix with slow intermediate gaps and observe whether the convergence factor is genuinely independent of intermediate gaps and improves linearly with sketch size.
Extended reading notes
Core claim
The central claim is that inverse power iteration for eigenproblems can be preconditioned by sketching the error term instead of the iterate: $u_{k+1} = (\hat{A} - \lambda(u_k)I)^{-1}(\hat{A} - A)u_k$, normalized. Because $(\hat{A} - \lambda_* I)^{-1}(\hat{A} - A)v_* = v_*$ whenever $Av_* = \lambda_* v_*$, the exact eigenvector is a fixed point for any symmetric $\hat{A}$, so the approximate solver never needs to be refined as the iteration approaches the solution. Under the two-sided Loewner bound $A - 3\eta I \preceq \hat{A} \preceq A - \eta I$, EPSI converges linear-quadratically with linear rate on the order of $\eta/(\lambda_1 - \lambda_2)$. The k-vector extension Lazy-EPSI adds an orthogonalization step that makes the linear factor depend only on $\lambda_k/(\lambda_k - \lambda_{k+1})$; with a sketched low-rank preconditioner and the Woodbury identity, each iteration costs $O(k(n\ell^2 + \ell^3 + mn))$.
Load-bearing premise
The proof assumes the implemented preconditioner, built from the sketched low-rank approximation with a heuristic shift, satisfies the two-sided matrix bound $A - 3\eta I \preceq \hat{A} \preceq A - \eta I$ for some known $\eta$; the paper does not prove that the heuristic shift enforces this bound.
Editorial extensions
If this is right
- Sketch quality becomes a convergence accelerator rather than an accuracy ceiling: improving $\eta$ by increasing the sketch size speeds the iteration up linearly, while the final approximation error is not tied to the solver's precision.
- Lazy-EPSI's per-iteration cost is $O(k(n\ell^2 + \ell^3 + mn))$ and its linear rate uses only the gap $\lambda_k/(\lambda_k - \lambda_{k+1})$, so problems with clustered intermediate eigenvalues but a clear top-k cutoff are no harder than subspace iteration with the same gap.
- The fixed-point property removes the need for increasingly accurate inner solves, which is the main computational bottleneck in approximate shifted inverse iteration.
- The negative shift in the sketched preconditioner makes the method invertible and stable, and the analysis provides a convergence guarantee for a Davidson-type preconditioned eigensolver that uses a randomized low-rank approximation.
- Because the linear rate improves at least linearly with the sketch size, doubling the sketch width gives a proportional improvement in the convergence factor, matching the behavior of sketch-and-precondition methods for least squares.
Reading between the lines
- A testable extension is to replace the Nystr\"om preconditioner by other randomized low-rank approximations, since the proof relies only on the two-sided Loewner bound; the shift would need to be chosen from the corresponding error estimate.
- The same fixed-point mechanism should transfer to asymmetric SVD by sketching $A^{\top}A$, which the paper mentions but does not analyze, suggesting a streaming k-SVD variant.
- One implicit consequence is that the quadratic term can dominate in early iterations when $\eta$ is small, so practical initializations from a rank-$\ell$ approximation may converge faster than the worst-case linear bound alone predicts.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript introduces Error-Powered Sketched Inverse Iteration (EPSI), the iteration u_{k+1} ∝ ( − λ(u_k)I)^{-1}( − A)u_k for the top eigenpair of a positive semidefinite matrix A, together with a block variant Lazy-EPSI (Algorithm 2) for top-k eigenspaces; here  is a sketch-based approximation of A, specifically the Nyström approximation with a subtracted shift. The paper's central claims are (i) the true eigenvector is a fixed point of EPSI for any choice of Â, (ii) EPSI is a genuine sketch-and-precondition method whose linear convergence factor is proportional to the distortion η of Â, and (iii) Lazy-EPSI converges at a rate depending only on the final spectral gap λ_k/(λ_k − λ_{k+1}), with at least linear improvement in the sketch size. The main theorems (Theorem 2.2 for the 1-SVD case and Theorem 2.4 for Lazy-EPSI) assume the two-sided Loewner bound A − 3ηI ⪯  ⪯ A − ηI, and the proof of Theorem 2.2 additionally assumes that  is diagonalized by the eigenbasis of A. The paper proposes to realize the Loewner bound by subtracting a heuristic shift c from the Nyström eigenvalue matrix, but provides no proof connecting the implemented operator to the theorem assumptions.
Significance. The ideal-analysis core of the paper is attractive and, if the hypotheses could be verified for a concrete preconditioner, the results would be a genuine advance: the fixed-point property (Lemma 1) is a clean structural insight that separates the preconditioning effect from the accuracy of the approximate solver; Theorem 2.4's dependence on λ_k/(λ_k − λ_{k+1}) rather than on intermediate gaps is the correct target and matches the subspace-iteration literature; Lemma 2 gives a concrete Woodbury-based implementation with O(nℓ² + ℓ³) cost per correction; and the numerical section is reasonably broad, comparing against subspace iteration and Davidson's method on synthetic and real matrices. The derivations in Lemmas 2.1 and 2.3 are largely self-contained and checkable under the stated ideal assumptions. However, the bridge between these theorems and the implemented algorithm is the weakest point: the entry condition (the two-sided Loewner bound with a known, algorithmically controlled η) is asserted rather than proved, so the advertised sketch-size dependence and the stated contraction rates are not currently established for the operator actually used in the code.
major comments (3)
- [§2.2.1, Lemma 3 and the following Remark] The entry condition of the main theorems is never verified for the implemented algorithm. Theorem 2.2 and Theorem 2.4 assume the two-sided Loewner bound A − 3ηI ⪯  ⪯ A − ηI with a known η, but the only support offered for the Nyström-based preconditioner is Lemma 3, which bounds E‖A − Â_nys‖ ≤ (3 + 4e²/p√(sr_p(A)))λ_p in expectation; the sentence preceding Lemma 3 claims that the Nyström approximation satisfies A − ηI ⪯  ⪯ A + ηI 'for some η', but the lemma does not establish such a deterministic Loewner bound. The Remark after Lemma 3 proposes to subtract c ≈ 2η from the computed diagonal matrix Λ̂, which yields  = U_nys(Λ̂ − cI)U_nys^T; since U_nys is only column-orthonormal, this is not a shift of Â_nys by −cI, and no bound is given on the action of this operator on the complement of the sketch subspace. Closing the gap requires (i) a high-probability spectral-norm bound on A − Â_nys with explicit constants, (ii) a proof that the chosen shift c lies in the required interval, and (iii) an explicit relation between η and the sketch size ℓ; none of these appears. The Remarks after Theorem 2.2 and Theorem 2.4, which assert that the Nyström initialization lies in the η-neighborhood required by the locality assumptions, are likewise unsupported. Since the linear contraction factors in both theorems are proportional to η and the advertised 'at least linear in sketch size' rate is obtained only by linking η to ℓ, this missing verification is load-bearing.
- [§2.1, Lemma 2.1 and Theorem 2.2] The hypothesis that  'shares a same column space with A' is used in the proof of Lemma 2.1 as the conclusion that  = VTV^T, which is simultaneous diagonalizability of  and A; equality of column spaces does not imply this, and the rank-ℓ Nyström operator  = U_nys(Λ̂ − cI)U_nys^T has range of dimension at most ℓ, which is not the column space of A when ℓ < rank(A). Consequently, Theorem 2.2 does not apply to the operator produced by Algorithm 1 together with the shift described in the Remark after Lemma 3, and the convergence guarantee for the implemented 1-SVD EPSI iteration is unproven. The authors should either prove the theorem under a hypothesis that the Nyström preconditioner actually satisfies, or explicitly present Theorem 2.2 as an idealized-analysis statement with a separate treatment of the implemented operator.
- [§2.2.2, proof of Theorem 2.4] The constant bookkeeping in the proof of Theorem 2.4 is not justified. The equation 'c0 = (1 + cλ1k‖V2^T Uq‖/η)(1 − 4(λ1 − λk+1)‖V2^T Uq‖/η) = 1 + cλ1k‖V2^T Uq‖/η for some small constant c' is not an equality: expanding the product gives 1 + a − b − ab, and only an inequality 1 + a − b − ab ≤ 1 + a is immediate. More importantly, contraction of the linear term requires c0 · (3.5√2η/(λk − λk+1)) < 1, and since c0 > 1 whenever ‖V2^T Uq‖F > 0, the stated condition η < (λk − λk+1)/(3.5√2) does not by itself guarantee contraction; an explicit margin condition on η together with a smallness condition on ‖V2^T Uq‖F is required. The theorem's conclusion that the linear term dominates the convergence therefore needs a repaired derivation.
minor comments (9)
- [§2.2.1, Remark after Lemma 3] The sentence 'To achieve a negative shift on ˆA such that A − 3ηI ⪯ ˆA ⪯ 1 − ηI' contains a typo: the right-hand side should be A − ηI.
- [§2.1, Lemma 2.1 and proof of Theorem 2.2] The bound stated in Lemma 2.1 uses the denominator 1/(1 − 3ε), while the proof derives 1/(1 − (λ1/η)ε) under the condition λ1ε/η < 1; these are different quantities, and the same 1/(1 − 3ε) reappears in the proof of Theorem 2.2, so the statements and derivations should be reconciled.
- [§2.1 and §2.2.1] The heuristic for the shift is stated in two incompatible ways: 'c ≈ λ̂_k²/λ̂_1' in the description of preconditioners in Section 2.1 and 'c ≈ 2η' in the Remark after Lemma 3; a single, precisely defined shift-selection rule is needed.
- [§2.2.2, proof of Theorem 2.4] In the chain '|λ_i − λ̂_i| ≤ ‖(λ_iI − Λ1)V1^T û_{q+1}‖ + λ_{k+1}‖V2^T û_{q+1}‖² ≤ 18λ1‖V2^T Û^all_{q+1}‖', the final bound appears to drop a square: Lemma 4 gives the first term as O(‖V2^T U‖²), so the displayed bound should be quadratic in ‖V2^T Û^all_{q+1}‖.
- [§2.2.1, Algorithm 2] Step 3 of Algorithm 2 ('EPSI Iteration: Update first k eigenspace estimation U') does not specify the update rule; the text should make explicit that Steps 4–8 constitute the EPSI update, or renumber accordingly.
- [§4, Figures 2 and 6] Several figure captions are under-specified: Figures 2 and 6 do not state which curves correspond to Lazy-EPSI versus subspace iteration, and the text 'Lines with different color show the convergence of the i-th eigenvalue estimation error' does not identify the colors; please provide legends and state the y-axis quantity (absolute or relative eigenvalue error) consistently.
- [Abstract and §1.1] The abstract and the contribution list claim a convergence rate that 'improves at least linearly with the sketch size', but the theorems state rates in terms of η and no proposition links η to the sketch size ℓ with explicit probability and constants; please either add such a statement or soften the claim accordingly.
- [§1.2 and §2.2.1] The shift discussion after Lemma 3 relies implicitly on one-sided properties of the Nyström approximation (such as 0 ⪯ Â_nys ⪯ A), but these are never stated; please state and prove the one-sided bound explicitly, since the Loewner analysis depends on it.
- [Throughout] The manuscript contains numerous typos ('semi-positive definite', 'qudractic', 'eigenvlaue', 'initilization', 'depsite', and the malformed inequality in the Remark after Lemma 3); the manuscript requires a careful proofreading pass before resubmission.
Circularity Check
No significant circularity: the convergence analysis is conditional on an assumed Loewner bound, and the heuristic shift leaves a validity gap rather than closing a circular loop.
full rationale
No circular derivation is apparent. The EPSI iteration is defined as ( − λ(u)I)^{-1}( − A)u, and Lemma 1's fixed-point property follows by direct cancellation of ( − λ*I) once Au* = λ*u* is substituted; this is a designed algebraic identity, not a fitted or imported prediction. The convergence results (Lemma 2.1, Theorems 2.2 and 2.4) are proven from the explicitly stated two-sided Loewner assumption A − 3ηI ⪯  ⪯ A − ηI, with η an external distortion parameter, and the rates then follow from matrix inequalities and perturbation arguments rather than from reusing the conclusion. The Nyström approximation error bound in Lemma 3 is cited from [FTU23], an independent external source, and is not presented as the authors' own theorem. The only self-citation, [XL24], supports a background remark about iterative sketching methods and is not load-bearing for the EPSI derivation. The main weakness is that the shifted Nyström preconditioner  = Â_nys − cI is never proven to satisfy the required Loewner bound for a known η; the remark that one can subtract c ≈ 2η based on eigendecay is an unverified heuristic, and Theorem 2.2's same-column-space condition is not established for the rank-ℓ Nyström preconditioner. These are unverified-assumption gaps that create correctness risk, not circular reductions: the advertised rate is conditional on assumptions that are not established, rather than being forced by construction or by a self-citation chain.
Assumptions & free parameters
free parameters (2)
- shift c =
c ≈ 2η, also stated as c ≈ λ̂_k²/λ̂_1
- distortion η =
not measured; defined by A - 3ηI ⪯ Â ⪯ A - ηI
assumptions (4)
- ad hoc to paper The practical Nyström preconditioner after shift, Â = Â_nys - cI, satisfies A - 3ηI ⪯ Â ⪯ A - ηI with a known η.
- ad hoc to paper  shares the same column space as A.
- domain assumption Distinct top-k eigenvalues λ1 > ... > λk and a local initial guess satisfying ε ≤ η/(26(λ1-η)).
- standard math Nyström error bound of Lemma 3, imported from FTU23.
Cite this review
Pith. "Pith review of What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?." pith.science (2026). https://pith.science/paper/I6OZGSJF
@misc{pith2026250207993,
author = {Pith},
title = {Pith review of: What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?},
year = {2026},
howpublished = {\url{https://pith.science/paper/I6OZGSJF}},
note = {Machine review of arXiv:2502.07993}
}
read the original abstract
Randomized sketching accelerates large-scale numerical linear algebra by reducing computational complexity. While the traditional sketch-and-solve approach reduces the problem size directly through sketching, the sketch-and-precondition method leverages sketching to construct a computational friendly preconditioner. This preconditioner improves the convergence speed of iterative solvers applied to the original problem, maintaining accuracy in the full space. Furthermore, the convergence rate of the solver improves at least linearly with the sketch size. Despite its potential, developing a sketch-and-precondition framework for randomized algorithms in low-rank matrix approximation remains an open challenge. We introduce the Error-Powered Sketched Inverse Iteration (EPSI) Method via run sketched Newton iteration for the Lagrange form as a sketch-and-precondition variant for randomized low-rank approximation. Our method achieves theoretical guarantees, including a convergence rate that improves at least linearly with the sketch size.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[8]
Sub-sampled newton methods i: globally convergent algorithms
[RKM16a] Farbod Roosta-Khorasani and Michael W Mahoney. Sub-sampled newton methods i: globally convergent algorithms. arXiv preprint arXiv:1601.04737 ,
-
[1998]
Randomized matrix computations: Themes and variations
[KT24] Anastasia Kireeva and Joel A Tropp. Randomized matrix computations: Themes and variations. arXiv preprint arXiv:2402.17873 ,
-
[2001]
27 [JKM+15] Chi Jin, Sham M Kakade, Cameron Musco, Praneeth Netrapalli, and Aaron Sidford. Robust shift-and-invert preconditioning: Faster and more sample efficient algorithms for eigenvector computation. arXiv preprint arXiv:1510.08896 ,
-
[2002]
An implementation of a randomized algorithm for principal component analysis
[SKT14] Arthur Szlam, Yuval Kluger, and Mark Tygert. An implementation of a randomized algorithm for principal component analysis. arXiv preprint arXiv:1412.3510 ,
-
[2008]
Improved approximation algorithms for large matrices via random pro- jections
[Sar06] Tamas Sarlos. Improved approximation algorithms for large matrices via random pro- jections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS’06), pages 143–152. IEEE,
work page 2006
-
[2011]
Randomized numerical linear algebra: A perspective on the field with an eye to software
[MDM+23] Riley Murray, James Demmel, Michael W Mahoney, N Benjamin Erichson, Maksim Mel- nichenko, Osman Asif Malik, Laura Grigori, Piotr Luszczek, Micha l Derezi´ nski, Miles E Lopes, et al. Randomized numerical linear algebra: A perspective on the field with an eye to software. arXiv preprint arXiv:2302.11474 ,
-
[2015]
Randomized Iterative Solver as Iterative Refinement: A Simple Fix Towards Backward Stability
[XL24] Ruihan Xu and Yiping Lu. Randomized iterative solver as iterative refinement: A simple fix towards backward stability. arXiv preprint arXiv:2410.11115 ,
-
[2016]
Sub-sampled newton methods ii: Local convergence rates
[RKM16b] Farbod Roosta-Khorasani and Michael W Mahoney. Sub-sampled newton methods ii: Local convergence rates. arXiv preprint arXiv:1601.04738 ,
Show all 13 references
-
[2017]
First efficient convergence for streaming k-pca: a global, gap-free, and near-optimal rate
[AZL17b] Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-pca: a global, gap-free, and near-optimal rate. In 2017 IEEE 58th Annual Symposium on Foun- dations of Computer Science (FOCS) , pages 487–492. IEEE,
2017
-
[2018]
Randomized algorithms for low-rank matrix ap- proximation: Design, analysis, and applications
[TW23] Joel A Tropp and Robert J Webber. Randomized algorithms for low-rank matrix ap- proximation: Design, analysis, and applications. arXiv preprint arXiv:2306.12418 ,
-
[2020]
Iterative hessian sketch with momentum
[OPA19] Ibrahim Kurban Ozaslan, Mert Pilanci, and Orhan Arikan. Iterative hessian sketch with momentum. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pages 7470–7474. IEEE,
2019
-
[2021]
Sketch and project: Randomized iterative methods for linear systems and inverting matrices
[Gow16] Robert M Gower. Sketch and project: Randomized iterative methods for linear systems and inverting matrices. arXiv preprint arXiv:1612.06013 ,
-
[2024]
Fast and simple pca via convex optimization
[GH15] Dan Garber and Elad Hazan. Fast and simple pca via convex optimization. arXiv preprint arXiv:1509.05647,
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.