Accelerating Randomized Algorithms for Low-Rank Matrix Approximation

Bo Fu; Dandan Jiang; Weiwei Xu

REVIEW 4 major objections 6 minor 31 references

Accelerating Randomized Algorithms for Low-Rank Matrix Approximation

T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Replacing the dense Gaussian matrix with standardized Bernoulli, sparse sign, or sparse Gaussian matrices inside farPCA yields the same low-rank approximation error at lower computational cost.

desk verdict The sparse test matrices look genuinely useful and the experiments are consistent, but Theorem 3's proof does not establish the Gaussian error bounds it claims, so the paper needs major revision before the theory can be trusted. read the letter →

arxiv 2506.03859 v1 pith:MM5DALDB submitted 2025-06-04 stat.CO

Dandan Jiang , Bo Fu , Weiwei Xu This is my paper

classification stat.CO MSC 65F5560B20

keywords low-rankmatrixapproximationrandomizednumericallinearalgebrasparserandommatricesstandardizedBernoullisignGaussianfixed-precisiontheory

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

The paper sets out to prove that the dense standard Gaussian matrix inside the fast adaptive randomized PCA algorithm (farPCA) can be swapped for three cheaper sparse test matrices — the standardized Bernoulli matrix, the sparse sign matrix, and the sparse Gaussian matrix — with no asymptotic loss of accuracy. The key mechanism is a convergence-in-distribution theorem: when multiplied by the right singular vector matrix $V_A$ of the target matrix, each sparse matrix behaves like a standard Gaussian matrix as the dimension grows, on the assumption that every entry of $V_A$ is uniformly small (condition (3.1)). Under that assumption the three accelerated algorithms, farPCASB, farPCASS, and farPCASG, inherit both the classical Halko error bounds and the paper's own tighter asymptotic bounds, so a fixed-precision solver on a large dense matrix should see the same output rank and error as farPCA at a lower computational cost. The paper additionally derives these tighter bounds for the Gaussian-based algorithm itself, using random matrix theory to control the pseudo-inverse of a Gaussian matrix more precisely than the classical analysis.

What carries the argument

The load-bearing object is the standardized Bernoulli matrix $\Omega$ with entries $(b_{ij}-p)/\sqrt{p(1-p)}$, along with its two companions: the sparse sign matrix $\Xi$ with entries $\pm 1/\sqrt{p}$ or 0, and the sparse Gaussian matrix $\Psi = B \circ G/\sqrt{p}$. The argument that carries the paper is Theorem 1: when left-multiplied by an orthogonal matrix $U$ satisfying condition (3.1), each row of $U\Omega$ is a sum of independent, identically scaled terms, and the Lyapunov central limit theorem makes the row converge in distribution to a standard normal; zero covariance between distinct entries then gives joint asymptotic Gaussianity. That converts the sparse matrix into a stand-in for the rotationally invariant Gaussian matrix inside the farPCA loop. The second mechanism is the Marchenko–Pastur law applied to the pseudo-inverse of a Gaussian matrix, which yields the asymptotic norm bounds in Lemma 6 and, through Lemma 2's splitting of the error into $\sigma_{k+1}$ plus a term involving $\Phi_2 \Phi_1^\dagger$, produces the tightened error bounds of Theorem 2 that the sparse variants then inherit via Theorem 3.

What would settle it

Compute $V_A^{\top}\Omega$ for a diagonal $V_A$ ($n = 5000$, $p = \ln(n)/n$): each entry of the product is a single standardized Bernoulli variable, far from normal, so the central-limit argument fails at the level of individual entries; in the fixed-precision loop this breakdown shows up as a success rate of 37% for farPCASB and farPCASS in the authors' Table 3, against roughly 100% for Gaussian farPCA.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the random process $V_A^{\top}\Omega$, $V_A^{\top}\Xi$, and $V_A^{\top}\Psi$ — where $\Omega$, $\Xi$, and $\Psi$ are respectively the standardized Bernoulli, sparse sign, and sparse Gaussian matrices — converges in distribution to a standard Gaussian matrix as $n \to \infty$, elementwise and jointly, whenever the orthogonal matrix $V_A$ satisfies $\max_{i,j} |u_{ij}| \le \varepsilon_n \to 0$. Since farPCA's error behaviour is governed by the action of the random test matrix on the right singular vectors, this convergence lets the sparse matrices inherit farPCA's guarantees: Theorem 3 states that with probability 1 the Halko bounds (4.8)–(4.11) hold for all three accelerated algorithms, and as $k$ and $h$ grow, the tighter asymptotic bounds (4.12)–(4.15) also hold. In the same framework the paper derives these tighter bounds for the Gaussian process itself, using the Marchenko–Pastur law to show $\|G^\dagger\|_F \to \sqrt{\gamma/(1-\gamma)}$ and $\lim \|G^\dagger\| \le 1/\sqrt{n(1-\sqrt{\gamma})^2}$, which removes the constant slack in the classical analysis. Numerically, the three algorithms report the same output rank and relative Frobenius error as farPCA while cutting time by roughly 25% at power parameter $P = 1$ and approaching 50% at $P = 0$ on dense matrices of size up to 30000.

Load-bearing premise

The whole argument rests on the assumption that no entry of the right singular vector matrix $V_A$ stays large as the dimension grows; when $V_A$ has a block-structured form, the entries of $V_A^{\top}\Omega$ are no longer sums of many tiny terms, and the sparse test matrices stop behaving like Gaussians.

Editorial extensions

If this is right

For large dense matrices, fixed-precision low-rank approximation becomes cheaper without sacrificing output quality: the three accelerated algorithms return the same rank and relative Frobenius error as Gaussian farPCA at the same tolerance.
The safe window of sparsity is quantified: parameter $p$ should be at least $\max\{10^{-3}, \ln(n)/n\}$ for the standardized Bernoulli variant and $\max\{10^{-3}, 10/n\}$ for the sparse sign and sparse Gaussian variants; smaller $p$ risks rank deficiency and repeated iterations.
The tighter asymptotic error bounds (4.12)–(4.15) apply not only to farPCA but, by the same splitting argument, to any Gaussian-based randomized algorithm whose error analysis passes through the pseudo-inverse of the test matrix, including randQB variants.
When the right singular vectors are block-diagonal rather than delocalized, the equivalence breaks: at $p = \ln(n)/n$ success rates fall to 37–42%, so the acceleration is dependable only when condition (3.1) holds.

Reading between the lines

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

Condition (3.1) is an incoherence-type condition; for data whose singular vectors are localized (for example, matrices with block structure), a practitioner should either raise $p$ toward $10^{-1}$ or fall back to the Gaussian matrix, a boundary visible in the paper's own stability table.
Because the theorem only uses mean-zero, variance-one i.i.d. entries, any three-point or sparse discrete distribution with these moments should also converge to Gaussian behaviour after multiplication by $V_A$, opening a wider family of cheap sketches that need no new error analysis.
An adaptive strategy that monitors the sketch's effective rank during the iteration and increases $p$ when the basis shows signs of deficiency would sit naturally on top of this framework, and is indeed flagged as future work in the paper.
The speedup grows with dimension and with the power parameter $P$, since the dominant matrix-matrix products become sparse; for very large matrices the savings could exceed the 25–50% seen at $n = 5000$–$30000$, provided condition (3.1) holds.

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.

Desk Editor's Note

read the letter

Short version: the empirical case is real, and the sparse test matrices are worth knowing about, but Theorem 3 does not prove what it claims. The proof gap is load-bearing, not cosmetic.

The genuinely new piece here is the standardized Bernoulli matrix and its use inside farPCA, along with sparse Gaussian and sparse sign variants. The experiments are extensive and convincing: fixed-rank, fixed-precision, real image data, sensitivity to p, and a stability section. Across the board the sparse algorithms save roughly 10-50% time with essentially identical errors. That is a useful incremental speedup for dense low-rank approximation, and the practical recommendation (farPCASB for robustness, farPCASG for balance) is well supported by the numerics.

The trouble is the theory. Theorem 3 transfers Halko's Gaussian error bounds by saying V_A^T Upsilon is 'asymptotically equivalent' to a Gaussian, based on Theorem 1 and Propositions 1-2. But those results only give convergence in distribution of entries. The error functional in Lemma 2 contains a pseudo-inverse and a product, which is not a bounded continuous function; convergence in distribution does not imply convergence of its expectation or tail probabilities without uniform integrability or moment convergence, neither of which is shown. So the central guarantee, that farPCASB/SS/SG inherit the Halko bounds, is not established even when condition (3.1) holds. The asymptotic bounds (4.12)-(4.15) have a similar issue: the proof of Theorem 2 uses E||G^dagger||_F^2 -> k/h, but Lemma 6 only gives an almost sure limit, and even that limit seems to be sqrt(k(k+h))/h, not k/h. The 'with probability 1' phrasing around expectation bounds is also sloppy. These are fixable, but only with real work.

The reach of condition (3.1) is also narrower than the paper claims. The text calls it mild and says failures are 'rarely encountered,' yet Table 3 shows success rates of 37-42% for farPCASB and farPCASS at the recommended p = ln(n)/n when V_A is block-diagonal. That directly contradicts the practical reassurance and should temper the abstract's 'superior alternative' wording.

Who is this for? Practitioners who want a cheap drop-in test matrix and are willing to rely on the empirical evidence, and theorists who want to close the gap. The paper deserves a serious referee because the empirical contribution is solid and the theoretical issues are addressable with a major revision. I would send it to review, but I would not cite the theoretical bounds in my own work until the proof is repaired.

Recommendation: major revision, with the burden placed on the authors to either prove the transfer of error bounds under the right conditions or explicitly relabel Theorem 3 as an empirical conjecture. Also, they should present Section 5.5 as a genuine limitation rather than a footnote.

Referee Report

4 major / 6 minor

Summary. The paper proposes replacing the standard Gaussian test matrix inside the farPCA algorithm with a standardized Bernoulli matrix, a sparse sign matrix, or a sparse Gaussian matrix, yielding algorithms farPCASB, farPCASS, and farPCASG. The main theoretical claim is that, under a condition on the maximum entry of the right singular vector matrix (condition (3.1)), these test matrices become asymptotically equivalent to a standard Gaussian matrix, so that the Halko et al. error bounds and the paper's new random-matrix-theory bounds transfer to the accelerated algorithms. The authors also derive asymptotic norm bounds for the pseudo-inverse of a Gaussian matrix via the Marchenko-Pastur law. Numerical experiments on synthetic and real dense matrices show that the accelerated algorithms achieve essentially the same accuracy as farPCA at reduced runtime.

Significance. If the theoretical claims were rigorously established, the practical contribution would be solid: dense low-rank approximation is a core tool, and the experiments show about 25-50% runtime savings at the same accuracy for several test matrices, including a real image dataset. The standardized Bernoulli construction and the cost analysis via Hoeffding concentration are useful ideas, and the random-matrix-theory bounds (Theorem 2) are a potentially valuable refinement of the Gaussian theory. However, the central theoretical transfer in Theorem 3 is not proven as written, and the paper's own stability experiments in Section 5.5 show that condition (3.1) is not benign for structured matrices. The numerics support a modest, qualified practical claim, but not the unqualified statement that the three algorithms 'can serve as a superior alternative to farPCA.' No code or data are provided, so reproducibility of the experiments cannot be independently checked.

major comments (4)

[§3.1, Theorem 1] The proof of Theorem 1 establishes only that each entry (UΩ)_ij converges marginally to N(0,1) and that the entries are pairwise uncorrelated. It does not establish joint normality of the whole matrix UΩ, so the statement that 'UΩ converges in distribution to a standard Gaussian matrix' is unsupported. Pairwise uncorrelated asymptotically normal random variables need not be jointly normal, and the claim that uncorrelatedness plus normal marginals gives asymptotic independence is not valid without joint convergence, e.g. via the Cramér-Wold device or a multivariate Lindeberg-Feller CLT. Propositions 1 and 2 are asserted to follow by identical steps, so they inherit this gap. Since Theorem 3 and the 'asymptotically equivalent to V_A^T G' premise depend on full distributional equivalence of the test matrix, this is a load-bearing issue.
[§4, Theorem 3] Even if the joint distributional convergence were granted, the proof of Theorem 3 transfers the Gaussian error bounds (4.8)-(4.15) by appealing to asymptotic equivalence. Those bounds involve E‖Σ_2 Φ_2 Φ_1^†‖, E‖Φ_1^†‖_F, and tail probabilities of ‖Σ_2 Φ_2 Φ_1^†‖; these functionals are not bounded continuous functions of the entries of Φ, and convergence in distribution does not imply convergence of expectations or tail probabilities without uniform integrability or moment convergence, neither of which is shown. In addition, (4.8)-(4.11) are fixed-l, fixed-n non-asymptotic Gaussian statements while Theorem 1 is asymptotic in n, and (4.12)-(4.15) are asymptotic in k; the proof does not explain how these regimes are reconciled. The statement that (4.8) and (4.9) hold 'with probability 1' is also misconceived, since these are expectation inequalities; the same wording is not appropriate for (4.12)-(4.13).
[§5.5, Table 3 and Concluding Remark] The paper repeatedly calls condition (3.1) mild and 'rarely encountered' (Remark 1 and Section 6), but the paper's own Table 3 contradicts this for structured matrices. For a 5000×5000 matrix with block-diagonal V_A and d=5000 (i.e., a diagonal V_A), the recommended p=ln(n)/n yields success rates of only 37-42% for farPCASB and farPCASS, and similar rates for farPCASG and farPCAB. Such singular vector structure violates (3.1) and is not exotic in applications involving clustered, sparse, or piecewise-constant data. The abstract, introduction, and concluding remark should therefore be substantially qualified, or the recommended p1 and p2 values need to be adapted to the structure of V_A. As written, the practical claim that the three algorithms 'can serve as a superior alternative to farPCA' overstates the theorem's reach.
[§4, Lemma 6 and Theorem 2] The random-matrix-theory refinement asserts, from weak convergence of the empirical spectral distribution and a.s. support bounds, that ‖G†‖_F → sqrt(γ/(1−γ)) and then uses E‖Φ_1^†‖_F^2 = k/h and E‖Φ_1^†‖ ≤ (sqrt(k+h)−sqrt(k))^{-1} inside Theorem 2. Almost sure convergence of a norm does not imply convergence of its expectation without dominated convergence or uniform integrability, and no such control is provided. Moreover, the integral ∫ x^{-1} dF_{GG^T/n}(x) involves an unbounded integrand on [0,∞); the Portmanteau argument requires a uniform almost-sure lower bound on λ_min(GG^T/n) away from zero for all sufficiently large n, which is not established by the Marchenko-Pastur law alone. These gaps are independent of the sparse-matrix transfer and affect the validity of the claimed 'tighter' bounds for farPCA itself.

minor comments (6)

[Abstract and Section 1] The text contains several presentation errors: 'overwhelming methods' should be 'widely used methods'; 'reamed to the three acceleration algorithms' should be 'extended'; 'speculates' should be 'suggests'; and the '⇌' or '/interleave' symbols should be replaced by standard norm notation.
[§3.1, proof of Theorem 1] The inequality 'max_h {X_h} ≤ max_h{|u_ih|} max{...}' should be stated with max_h |X_h| on the left; as written it is not valid when X_h can be negative.
[§2.2 and §3.1] The cost expressions TAlg2.1 and TAlg3.1 refer to Algorithm 1 and Algorithm 2, but the numbering is inconsistent with the displayed algorithms; the notation should be renamed to avoid confusion.
[§4, Theorem 3] The phrase 'with probability 1, (4.8) and (4.9) hold' is inappropriate for expectation inequalities; the intended meaning should be restated, e.g. as 'the same expectation bounds hold asymptotically' or by explicitly separating the a.s. convergence statements from the expectation bounds.
[§5.3 and §5.5] The 'success rate' used in Figure 3 and Table 3 is not defined; the authors should state explicitly what constitutes a successful trial (e.g., reaching the tolerance within the maximum number of iterations) and how failures are counted.
[§5.5, Table 3] The parameter d is defined as the number of blocks, so d=5000 for n=5000 corresponds to a diagonal V_A; this should be stated in the caption or text so that the violation of condition (3.1) is transparent to the reader.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: sparse-matrix error bounds are an attempted transfer from external Gaussian bounds, not a fit or a self-citation chain.

full rationale

The paper's central derivation is not circular. Theorem 1 is a CLT for V_A^T Omega with the Lyapunov condition under assumption (3.1), and it is proved directly rather than assumed. Propositions 1 and 2 extend the same argument to sparse sign and sparse Gaussian matrices. The error bounds in Lemmas 6-7 and Theorem 2 come from external results (Halko et al. and the Marchenko-Pastur law), not from the authors' own fitted values. Theorem 3 attempts to transfer these bounds to the sparse algorithms by asserting asymptotic equivalence of V_A^T Upsilon to V_A^T G; that transfer is formally under-supported (convergence in distribution of entries does not by itself imply convergence of the error functional involving pseudo-inverses), but this is a correctness gap rather than circularity, because the conclusion is not identical to the assumption. The only overlap with the authors' prior work is reference [29] (Xu, Xu and Jing), which motivates the use of Bernoulli test matrices; it is not load-bearing for the present theorem, and the standardized Bernoulli matrix is defined independently. No fitted parameter is relabeled as a prediction: the sparsity parameter p is user-selected and the reported error curves are experimental measurements. Overall, the derivation chain rests on external benchmarks and stated assumptions, so no circular step reaches the threshold for flagging.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The contributed theory leans on standard CLT and RMT results plus two paper-specific moves: condition (3.1) restricting the singular vectors, and an unproved transfer of Gaussian error bounds to sparse matrices. One free parameter p sets the sparsity/stability trade-off and is chosen empirically.

free parameters (1)

p (sparsity probability parameter) = p1=max{10^-3, ln(n)/n} for farPCASB; p2=max{10^-3, 10/n} for farPCASS, farPCASG and farPCAB
Controls sparsity, speed, and stability of the three test matrices. The paper recommends these values empirically (Sections 5.1 and 5.3); no optimal p is derived, and Table 3 shows small p causes failures when V_A is structured.

assumptions (6)

standard math Lyapunov central limit theorem (Lemma 1)
Used in Theorem 1 to prove marginal normality of each entry of UΩ; standard result.
standard math Berry-Esseen theorem
Used for the convergence rate (3.2) in Theorem 1; standard result.
standard math Marchenko-Pastur law (Lemma 5)
Basis for Lemma 6's asymptotic bounds on the pseudo-inverse of a Gaussian matrix; standard random matrix theory.
domain assumption Condition (3.1) on the singular vectors of A
The paper assumes max|u_ij|≤ε_n→0 for V_A. It is load-bearing for the distributional equivalence and fails for sparse or block-structured singular vectors (Section 5.5).
ad hoc to paper Transfer of Gaussian error bounds to asymptotically Gaussian test matrices
Theorem 3 assumes convergence in distribution of V_A^TΥ to a Gaussian matrix is enough to inherit Halko's finite-sample expected and probabilistic error bounds. No proof is supplied, and distributional convergence alone does not generally control expectations of unbounded quantities such as pseudo-inverse norms.
ad hoc to paper Expectation of squared pseudo-inverse norm follows from almost sure convergence
Lemma 6 states almost sure norm convergence; Theorem 2's proof uses E‖Φ_1^†‖_F^2 = k/h as an exact equality without a uniform integrability argument.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Accelerating Randomized Algorithms for Low-Rank Matrix Approximation." pith.science (2026). https://pith.science/paper/MM5DALDB

@misc{pith2026250603859,
  author       = {Pith},
  title        = {Pith review of: Accelerating Randomized Algorithms for Low-Rank Matrix Approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MM5DALDB}},
  note         = {Machine review of arXiv:2506.03859}
}

abstract

Randomized algorithms are overwhelming methods for low-rank approximation that can alleviate the computational expenditure with great reliability compared to deterministic algorithms. A crucial thought is generating a standard Gaussian matrix $\mathbf{G}$ and subsequently obtaining the orthonormal basis of the range of $\mathbf{AG}$ for a given matrix $\mathbf{A}$. Recently, the \texttt{farPCA} algorithm offers a framework for randomized algorithms, but the dense Gaussian matrix remains computationally expensive. Motivated by this, we introduce the standardized Bernoulli, sparse sign, and sparse Gaussian matrices to replace the standard Gaussian matrix in \texttt{farPCA} for accelerating computation. These three matrices possess a low computational expenditure in matrix-matrix multiplication and converge in distribution to a standard Gaussian matrix when multiplied by an orthogonal matrix under a mild condition. Therefore, the three corresponding proposed algorithms can serve as a superior alternative to fast adaptive randomized PCA (\texttt{farPCA}). Finally, we leverage random matrix theory (RMT) to derive a tighter error bound for \texttt{farPCA} without shifted techniques. Additionally, we extend this improved error bound to the error analysis of our three fast algorithms, ensuring that the proposed methods deliver more accurate approximations for large-scale matrices. Numerical experiments validate that the three algorithms achieve asymptotically the same performance as \texttt{farPCA} but with lower costs, offering a more efficient approach to low-rank matrix approximation.

Figures

Figures reproduced from arXiv: 2506.03859 by the authors.

**Figure 2.** Comparison of relative Frobenius-norm errors and [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗

**Figure 3.** Success rates and execution times of farPCASB, farPCASS, farPCASG, and farPCAB for Matrix 1 sized 5000×5000 across varying values of p in 100 trials. est rank that fulfills the specified accuracy threshold. We set block size b = min{max{20, ⌊min(m, n)/100⌋}, 50} and power parameter P = 1 or 5. The maximum number of iterations is set to ⌈n/2b⌉. The results from a single execution are shown in [PITH_FULL_IMAGE:figur… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

31 extracted references · 29 canonical work pages

[1]

Bai, Z., Silverstein, J.W.: Spectral analysis of large d imensional random matrices, vol. 20. Springer (2010)

work page 2010
[2]

In: Proc

Benjamin Erichson, N., Brunton, S.L., Nathan Kutz, J.: C ompressed singular value decomposition for image and video processin g. In: Proc. IEEE Int. Conf. Comput. Vis. Workshops, pp. 1880–1888 (2017 )

work page 2017
[3]

SIAM (2010)

Bhattacharya, R.N., Rao, R.R.: Normal approximation an d asymptotic expansions. SIAM (2010)

work page 2010
[4]

John Wiley & S ons (2017)

Billingsley, P.: Probability and measure. John Wiley & S ons (2017)

work page 2017
[5]

Candes, E., Recht, B.: Exact matrix completion via conve x optimiza- tion. Commun. ACM 55(6), 111–119 (2012)

work page 2012
[6]

Linear Al gebra Appl

Chan, T.F.: Rank revealing qr factorizations. Linear Al gebra Appl. 88, 67–82 (1987)

work page 1987
[7]

In: Proc

Clarkson, K.L., Woodruﬀ, D.P.: Numerical linear algebra in the stream- ing model. In: Proc. 41st Annu. ACM Symp. Theory Comput., pp. 205–214 (2009) 29

work page 2009
[8]

Durrett, R.: Probability: theory and examples, vol. 49. Cambridge Univ. Press (2019)

work page 2019

Show all 31 references

[9]

In: Proc

Feng, X., Yu, W.: A fast adaptive randomized pca algorith m. In: Proc. IJCAI, pp. 3695–3704 (2023)

2023
[10]

JHU p ress (2013)

Golub, G.H., Van Loan, C.F.: Matrix computations. JHU p ress (2013)

2013
[11]

Gu, M.: Subspace iteration randomization and singular value problems. SIAM J. Sci. Comput. 37(3), A1139–A1173 (2015)

2015
[12]

Gu, M., Eisenstat, S.C.: Eﬃcient algorithms for comput ing a strong rank-revealing qr factorization. SIAM J. Sci. Comput. 17(4), 848–869 (1996)

1996
[13]

SIAM Rev

Halko, N., Martinsson, P.G., Tropp, J.A.: Finding stru cture with ran- domness: Probabilistic algorithms for constructing appro ximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011)

2011
[14]

Hallman, E.: A block bidiagonalization method for ﬁxed -accuracy low- rank matrix approximation. SIAM J. Matrix Anal. Appl. 43(2), 661– 680 (2022)

2022
[15]

arXiv pre print arXiv:2009.13726 (2020)

Huang, H.: Rank of sparse bernoulli matrices. arXiv pre print arXiv:2009.13726 (2020)

2020 arXiv
[16]

Kaloorazi, M.F., de Lamare, R.C.: Compressed randomiz ed utv de- compositions for low-rank matrix approximations. IEEE J. S el. Top. Signal Process. 12(6), 1155–1169 (2018)

2018
[17]

IEEE Trans

Kaloorazi, M.F., de Lamare, R.C.: Subspace-orbit rand omized decom- position for low-rank matrix approximations. IEEE Trans. S ignal Pro- cess. 66(16), 4409–4424 (2018)

2018
[18]

In: Proc

Li, P., Hastie, T.J., Church, K.W.: Very sparse random p rojections. In: Proc. 12th ACM SIGKDD Int. Conf. Knowl. Discov. Data Mini ng, pp. 287–296 (2006)

2006
[19]

, Tygert, M.: Randomized algorithms for the low-rank approximation of ma trices

Liberty, E., Woolfe, F., Martinsson, P.G., Rokhlin, V. , Tygert, M.: Randomized algorithms for the low-rank approximation of ma trices. Proc. Natl. Acad. Sci. 104(51), 20167–20172 (2007)

2007
[20]

Mahoney, M.W., Drineas, P.: Cur matrix decompositions for improved data analysis. Proc. Natl. Acad. Sci. 106(3), 697–702 (2009) 30

2009
[21]

Acta Numer

Martinsson, P.G., Tropp, J.A.: Randomized numerical l inear algebra: Foundations and algorithms. Acta Numer. 29, 403–572 (2020)

2020
[22]

Martinsson, P.G., Voronin, S.: A randomized blocked al gorithm for eﬃciently computing rank-revealing factorizations of mat rices. SIAM J. Sci. Comput. 38(5), S485–S507 (2016)

2016
[23]

Rokhlin, V., Szlam, A., Tygert, M.: A randomized algori thm for princi- pal component analysis. SIAM J. Matrix Anal. Appl. 31(3), 1100–1124 (2010)

2010
[24]

Tropp, J.A., Yurtsever, A., Udell, M., Cevher, V.: Prac tical sketching algorithms for low-rank matrix approximation. SIAM J. Matr ix Anal. Appl. 38(4), 1454–1485 (2017)

2017
[25]

Tropp, J.A., Yurtsever, A., Udell, M., Cevher, V.: Stre aming low- rank matrix approximation with an application to scientiﬁc simulation. SIAM J. Sci. Comput. 41(4), A2430–A2463 (2019)

2019
[26]

Wainwright, M.J.: High-dimensional statistics: A non -asymptotic view- point, vol. 48. Cambridge Univ. Press (2019)

2019
[27]

Woolfe, F., Liberty, E., Rokhlin, V., Tygert, M.: A fast randomized algorithm for the approximation of matrices. Appl. Comput. Harmonic Anal. 25(3), 335–366 (2008)

2008
[28]

I EEE Trans

Xie, Y., Dong, Y., Qiu, J., Yu, W., Feng, X., Tang, J.: Ske tchne: Embedding billion-scale networks accurately in one hour. I EEE Trans. Knowl. Data Eng. 35(10), 10666–10680 (2023)

2023
[29]

Xu, C., Xu, W., Jing, K.: Fast algorithms for singular va lue decompo- sition and the inverse of nearly low-rank matrices. Nat. Sci . Rev. 10(6), nwad083 (2023)

2023
[30]

Yu, W., Gu, Y., Li, Y.: Eﬃcient randomized algorithms fo r the ﬁxed- precision low-rank matrix approximation. SIAM J. Matrix An al. Appl. 39(3), 1339–1359 (2018)

2018
[31]

arXiv preprint arXiv:2010.00712 (2020) 31

Zhang, J., Saab, R.: Faster binary embeddings for prese rving euclidean distances. arXiv preprint arXiv:2010.00712 (2020) 31

2020 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Bai, Z., Silverstein, J.W.: Spectral analysis of large d imensional random matrices, vol. 20. Springer (2010)

work page 2010

[2] [2]

In: Proc

Benjamin Erichson, N., Brunton, S.L., Nathan Kutz, J.: C ompressed singular value decomposition for image and video processin g. In: Proc. IEEE Int. Conf. Comput. Vis. Workshops, pp. 1880–1888 (2017 )

work page 2017

[3] [3]

SIAM (2010)

Bhattacharya, R.N., Rao, R.R.: Normal approximation an d asymptotic expansions. SIAM (2010)

work page 2010

[4] [4]

John Wiley & S ons (2017)

Billingsley, P.: Probability and measure. John Wiley & S ons (2017)

work page 2017

[5] [5]

Candes, E., Recht, B.: Exact matrix completion via conve x optimiza- tion. Commun. ACM 55(6), 111–119 (2012)

work page 2012

[6] [6]

Linear Al gebra Appl

Chan, T.F.: Rank revealing qr factorizations. Linear Al gebra Appl. 88, 67–82 (1987)

work page 1987

[7] [7]

In: Proc

Clarkson, K.L., Woodruﬀ, D.P.: Numerical linear algebra in the stream- ing model. In: Proc. 41st Annu. ACM Symp. Theory Comput., pp. 205–214 (2009) 29

work page 2009

[8] [8]

Durrett, R.: Probability: theory and examples, vol. 49. Cambridge Univ. Press (2019)

work page 2019