Efficient adaptive randomized algorithms for fixed-threshold low-rank matrix approximation

Qiaohua Liu; Yuejuan Yu

REVIEW 3 major objections 4 minor 1 cited by

Efficient adaptive randomized algorithms for fixed-threshold low-rank matrix approximation

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read An adaptive randomized algorithm provably finds the numerical rank of a large matrix by deflating it block by block, with spectral and Frobenius error bounds.

desk verdict Genuinely novel blocked adaptive deflation with spectral stopping, but the main theorem is conditional on a gap the algorithm never verifies and the abstract outruns the data. read the letter →

arxiv 2508.07553 v1 pith:QRS3EBEB submitted 2025-08-11 math.NA cs.NA

Qiaohua Liu , Yuejuan Yu This is my paper · ORCID

classification math.NAcs.NA MSC 68W2060B2015A18

keywords randomizedlow-rankapproximationrank-revealingfixedthresholdnumericalrangedeflationQBsingularvaluethresholdingbackgroundestimation

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 aims to settle a practical question: given only a threshold $\theta$, how do you compute, in one adaptive pass, the rank of a large matrix above $\theta$ and an orthonormal basis for the corresponding subspace? Existing fixed-precision randomized methods stop on Frobenius-norm residuals, which misbehave when the singular values have a heavy tail, and the standard sparse-SVD package cannot reveal the rank automatically. The authors propose a blocked randomized deflation: build the basis block by block, strip each block off with $(I-QQ^T)A$, and stop when the computed eigenvalues of the small matrix $Q^TAA^TQ$ drop below $\theta^2$. Their central theorem says that if the computed block is within distance $\varepsilon<1$ of the true numerical subspace and the gap between the last retained and first discarded singular value exceeds $2\varepsilon\|A\|_2$, the deflated matrix still has exactly $\mathrm{rank}_\theta(A)-b$ and preserves all sub-threshold singular values to within $\varepsilon\|A\|_2$. That guarantee is what makes the stopping rule trustworthy, and it is backed by experiments on synthetic data, document retrieval, image compression, and video background estimation.

What carries the argument

The object that carries the argument is the deflated matrix $B = (I - Q_\ell Q_\ell^T)A$ built from a block $Q_\ell$ obtained by randomized subspace iteration with power $q$, and the metric that controls everything is the subspace distance $\varepsilon = d(R(Q_\ell), R_\theta(A))$ between the computed block and the true numerical range of the current residual. The crucial inequality is that the singular values of $B$ differ from those of the exact projection onto the true subspace by at most $\varepsilon\|A\|_2$, so a spectral gap larger than $2\varepsilon\|A\|_2$ forces exactly $b$ singular values to fall below $\theta$ and keeps the tail intact. The twice-orthogonalization operator $\mathr

What would settle it

Run blarank (Algorithm 2.3, without twice-orthogonalization) on the Type II synthetic matrix of Section 4.1 at $q=1$, $b=20$: it reports computed rank 22 or 800 instead of the true 20 and a range error of 1.00, showing that under floating-point arithmetic the deflation step fails to preserve the numerical rank whenever the tail singular values decay slowly.

Watch

Extended reading notes

Core claim

The central claim is that numerical rank can be revealed by recursion without ever computing the full SVD. Theorem 3.4 states that if a computed block basis $Q_1$ satisfies $\varepsilon = d(R(Q_1), R_\theta(A)) < 1$ and the threshold $\theta$ satisfies $\sigma_k - \varepsilon\|A\|_2 > \theta > \sigma_{k+1} + \varepsilon\|A\|_2$, then $B = (I - Q_1Q_1^T)A$ keeps every singular value of $A$ below $\theta$ with absolute error at most $\varepsilon\|A\|_2$, and $\mathrm{rank}_\theta(B) = \mathrm{rank}_\theta(A) - b$. The proof splits $Q_1 = \check{Q}_1 + \ddot{Q}_1$ into its projection onto the numerical range and a tail contamination of norm $\varepsilon$, shows the numerical-range projection $\

Load-bearing premise

The whole guarantee rests on a strong spectral gap: the gap between the last singular value above the threshold and the first one below it must be larger than twice the distance from the computed basis to the true numerical subspace, so the computed basis must be quite accurate.

Editorial extensions

If this is right

For any matrix satisfying the gap condition, sblarank returns the exact numerical rank and an orthonormal basis of the numerical range, with absolute error in the retained singular values controlled by $\varepsilon\|A\|_2$.
The spectral residual $\|(I-QQ^T)A\|_2$ is bounded in terms of $\sigma_{k+1}$ plus gap-dependent factors, giving a reliable stopping criterion even when Frobenius-based criteria fail on heavy-tailed singular value distributions.
Each block costs $O(mnb)$ per pass plus low-order terms, so the total cost scales like $O(mnr)$ with $r$ the numerical rank, comparable to the blocked randQB family but with rank revealing built in.
The two-sided bounds on the singular values of $Q_\ell^T A$ mean the deflated randomized approximation can serve as a cheap approximate singular value thresholding step inside optimization loops such as robust PCA.

Reading between the lines

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

The proofs assume exact arithmetic; the empirical failure of blarank on Type II matrices suggests the twice-orthogonalization in sblarank is not a cosmetic stabilizer but a load-bearing component for floating-point correctness, and a roundoff analysis would be a natural extension.
A testable consequence of Theorem 3.4 is that the maximum tolerable gap violation is $2\varepsilon\|A\|_2$; for heavy-tailed distributions, increasing $q$ or shrinking the block size should shrink $\varepsilon$ below the gap, something the experiments support but the paper does not prove.
The error bound $|\tilde{\sigma}_j - \sigma_{b(\ell-1)+j}| \le \varepsilon_{\ell-1}\|A\|_2$ suggests a cheaper stopping rule than the eigenvalue test used in the algorithms, worth testing as an alternative termination criterion.
The deflation view connects directly to approximate singular value thresholding: replacing the exact SVT step by one application of sblarank yields a randomized proximal operator whose accuracy is controlled by the same gap condition.

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

Here's my take on Liu-Yu.

What's actually new: the blocked adaptive deflation scheme. Instead of larank's one-vector-at-a-time deflation, they build Q block by block and stop when the projected eigenvalues cross below the squared threshold. The load-bearing result, Theorem 3.4, is a conditional perturbation statement: if the computed block basis Q1 is within ε of the true numerical range Rθ(A) and the two-sided gap σ_k − ε‖A‖₂ > θ > σ_{k+1} + ε‖A‖₂ holds, then deflating by Q1 reduces the numerical rank by exactly b and keeps the tail singular values within ε‖A‖₂. That's a clean, useful theorem, and the proof outline is credible despite some indexing slips. Corollary 3.5 extends it to blocks. The complexity analysis is sensible, and the experiments show sblarank is fast on images and video. The benchmarks are external, and the bounds have no fitted constants—good practice.

Where it gets soft. The theorem's hypotheses are never shown to hold for the algorithm's actual output. The only random bound for ε, Theorem 3.2, involves ‖Ω₂Ω₁⁻¹‖, which is heavy-tailed and can push ε over the needed gap. For Type II matrices, σ_{b+1}/σ_b is about 0.75, so the promised ε is not small enough to make the theorem bite. And indeed blarank fails precisely there: Table 4.2 gives rank 22–29 instead of 20 and range error 1.00. The variant that actually works, sblarank, uses reorth2, which is only empirically justified and is not covered by the analysis. The stopping rule also has no theorem: no result shows that the first projected eigenvalue below θ² marks the true numerical rank unless the full-block hypotheses already hold. The abstract overstates the case: it promises "more reliable" behavior than the Lanczos method and Lee-Li-Zeng, but Table 4.3 shows sblarank returning rank 19 when the SVD gives 25. Those are real gaps, not manufactured ones.

The paper is still worth referee time. The idea is novel, the conditional analysis is a legitimate contribution, and the failures are honestly visible in the tables. What's missing is a bridge—a computable check of the gap condition, a probabilistic analysis of the stopping rule, or at least a reworked abstract that doesn't promise more than the theory and experiments support.

Who is this for? Researchers in randomized NLA and practitioners who need an adaptive spectral-threshold rank finder. I'd bring it to a reading group and would send it to review, but I wouldn't cite it yet in my own work; the gap condition needs to be addressed first.

Referee Report

3 major / 4 minor

Summary. The paper proposes two blocked adaptive randomized algorithms, blarank (Algorithm 2.3) and sblarank (Algorithm 2.4), for fixed-threshold low-rank matrix approximation. The basis Q of the approximate numerical range Rθ(A) is built block by block through an implicit deflation procedure with power iteration. The main theoretical results (Theorem 3.2, Theorem 3.4, Corollary 3.5, Theorem 3.6) give subspace-distance and error bounds, and prove that under a spectral-gap condition the deflated matrix has numerical rank reduced by exactly the block size b. Numerical experiments on synthetic matrices, information-retrieval data, image compression, and background estimation compare the algorithms with lansvd/PROPACK and larank.

Significance. The algorithmic idea is attractive and potentially useful: it is pass-efficient, avoids oversampling, uses implicit power iteration, and is built on existing rigorous randomized subspace bounds. The conditional perturbation theorem (Theorem 3.4) is a plausible and useful structural result. The paper explicitly builds on external benchmarks (Saibaba 2019, Gu 2015, Lee-Li-Zeng 2009) and contains no fitted constants, so there is no circularity concern. However, the central guarantee is not connected to the implemented stopping rule, and the paper's own experiments show failures exactly in the heavy-tailed cases emphasized in the introduction. Consequently, the contribution is promising but the main claims are not yet fully established.

major comments (3)

[§3, Theorem 3.4 and Corollary 3.5; Algorithms 2.3/2.4] The rank-decrease guarantee is conditional on ε = d(R(Q1), Rθ(A)) and on the two-sided gap σk − ε‖A‖₂ > θ > σk+1 + ε‖A‖₂. The paper never proves that the Q produced by Algorithm 2.3 or 2.4 satisfies these hypotheses, nor that the algorithm can verify them. In particular, the stopping rule at Algorithm 2.3/2.4 line 11 checks eigenvalues of Q_i^T A A^T Q_i, but no theorem shows that a crossing below θ² in this projected matrix coincides with rankθ(P⊥_i A) = rankθ(A) − bi. The theorem is therefore not connected to the actual stopping criterion. A theorem stating the exact conditions under which the line-11 test yields the correct rank, together with a high-probability bound on ε for the actual iterates, is needed.
[§4, Table 4.2] On Type II matrices, the un-stabilized blarank returns computed ranks 22, 29, 24, 25 instead of the true rank 20 (rows q = 1, 2, 3; b = 10, 20), with range error 1.00. This directly contradicts the paper's claim that the algorithm reveals the correct numerical rank, in exactly the heavy-tail regime the introduction identifies as motivating the work. The text acknowledges that 'larank, blarank fail' in some situations but does not reconcile this with Theorem 3.4 / Corollary 3.5. The theorem's gap hypothesis uses ratios such as σ_{k+1}/σ_b, while the actual first-block quality depends on the worse ratio σ_{b+1}/σ_b ≈ 0.75 for b = 10; this mismatch needs to be addressed explicitly.
[§2, Algorithm 2.4; §4, Table 4.3] The method that works empirically in the difficult cases is sblarank, which differs from blarank only by the reorth2 twice-orthogonalization step. The paper states that sblarank is 'mathematically equivalent' to blarank, but no rounding-error analysis is given to show that reorth2 maintains the assumptions ε < 1 and the spectral-gap condition in finite precision. Moreover, Table 4.3 shows that even sblarank returns rank 19 at θ = 20%‖A‖ on Cranfield while the SVD has numerical rank 25; the theoretical results do not cover this regime. Thus the reliability of the actually recommended algorithm is currently supported only empirically, and the theoretical claims need to be narrowed or supplemented by a stability analysis.

minor comments (4)

[§3, Theorem 3.4 proof] The indexing after applying Lemma 3.3 mixes j and b: the line 'σ′_{k−j+1}=σ′_{k−b+2}=...=σ′_k=0' should use a single index (j = b), and later 'ˇσ_{k−j+1}' should be 'ˇσ_{k−b+1}'. This makes the proof harder to follow.
[Algorithm 2.4, line 11] The eigenvalue check writes 'ˆΛ(t, t)' but should be 'ˆΛ_i(t, t)' to match Algorithm 2.3 and the preceding line.
[§4, Tables 4.3 and 4.4] The column structure of these tables is difficult to parse (especially the svd and larank columns). Please state explicitly, for each column, the method and its parameters, and list the true SVD rank used for comparison.
[§2, complexity paragraph] The sentence 'Flop counting is a necessarily crude approach...' appears to be an incomplete quote and the preceding sentence is cut off ('however, it does not ne cessarily mean larank is the most eﬃcient, since'). Please complete or remove the dangling text.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the rank-deflation theorem is a conditional perturbation result with independent randomized bounds; self-citations are peripheral.

full rationale

The central result, Theorem 3.4, is a conditional statement: if the computed block basis Q1 satisfies ε = d(R(Q1), Rθ(A)) < 1 and the singular values obey σ_k − ε∥A∥2 > θ > σ_{k+1} + ε∥A∥2, then the deflated matrix B reduces the numerical rank by exactly b and preserves the tail singular values within ε∥A∥2. This is not circular: the assumed subspace alignment and spectral gap are hypotheses, not consequences of the conclusion, and the proof uses only the SVD decomposition (3.7), perturbation theory, and the independent Lemma 3.3 of Lee–Li–Zeng. The randomized subspace-distance bound (3.3) is derived from the standard identity for power iteration and from Gu's Lemma 3.1 and Saibaba's Theorem 2.1, which are external results with stated assumptions and no constants fitted to this paper's experiments. The algorithm's stopping rule is not proven to always match the true numerical rank, and Tables 4.2–4.3 indeed show failures on heavy-tail cases; however, a gap between the theorem's hypotheses and the algorithm's practical behavior is a correctness risk, not circular reasoning. The only self-citations, [21,27,28], appear in a general list of randomized methods and are not used in any proof or as a load-bearing premise. Hence no step in the derivation reduces to its own inputs or to a fitted parameter renamed as a prediction.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central proof rests on external probabilistic and subspace-iteration bounds plus a gap assumption on the matrix's singular values; no new physical or mathematical entities are introduced.

free parameters (3)

block size b = b = 5, 10, 15, 20 in experiments
User-chosen algorithmic parameter; the theory's gap condition and error bounds depend on b.
power parameter q = q = 1, 2, 3 in experiments
User-chosen algorithmic parameter; higher q improves subspace alignment but increases cost.
threshold θ = θ = 5%, 10%, 20% of ||A||2 in experiments
User-chosen tolerance; the algorithm stops when the estimated spectral residual falls below θ.

assumptions (5)

standard math Lemma 3.1 Gaussian concentration bound from Gu 2015
Used to control ||Ω2Ω1^{-1}|| with probability 1-δ, appearing in Theorem 3.2 and Theorem 3.6.
standard math Theorem 2.1 subspace iteration bounds from Saibaba 2019
Provides the base error and singular value bounds for randomized QB with power scheme, extended to non-oversampled blocks.
standard math Lemma 3.3 deflation singular value preservation from Lee-Li-Zeng 2009
Asserts that deflating a basis in the numerical range removes exactly the expected singular values and preserves the tail, used in Theorems 3.4 and 3.6.
domain assumption Spectral gap condition σ_k - σ_{k+1} > 2ε||A||2
Required in Theorems 3.4 and 3.6 to keep above-threshold and below-threshold singular values separated after perturbation; can fail for heavy-tailed matrices.
domain assumption Exact arithmetic in the deflation sequence
The theory assumes computed Qj are exactly orthonormal to previous blocks; the stabilized version uses reorth2 to enforce this in finite precision, but no floating-point error analysis is given.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient adaptive randomized algorithms for fixed-threshold low-rank matrix approximation." pith.science (2026). https://pith.science/paper/QRS3EBEB

@misc{pith2026250807553,
  author       = {Pith},
  title        = {Pith review of: Efficient adaptive randomized algorithms for fixed-threshold low-rank matrix approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QRS3EBEB}},
  note         = {Machine review of arXiv:2508.07553}
}

abstract

The low-rank matrix approximation problems within a threshold are widely applied in information retrieval, image processing, background estimation of the video sequence problems and so on. This paper presents an adaptive randomized rank-revealing algorithm of the data matrix $A$, in which the basis matrix $Q$ of the approximate range space is adaptively built block by block, through a recursive deflation procedure on $A$. Detailed analysis of randomized projection schemes are provided to analyze the numerical rank reduce during the deflation. The provable spectral and Frobenius error $(I-QQ^T)A$ of the approximate low-rank matrix $\tilde A=QQ^TA$ are presented, as well as the approximate singular values. This blocked deflation technique is pass-efficient and can accelerate practical computations of large matrices. Applied to image processing and background estimation problems, the blocked randomized algorithm behaves more reliable and more efficient than the known Lanczos-based method and a rank-revealing algorithm proposed by Lee, Li and Zeng (in SIAM J. Matrix Anal. Appl. 31 (2009), pp. 503-525).

Figures

Figures reproduced from arXiv: 2508.07553 by the authors.

**Figure 4.** [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗

**Figure 4.** [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p019_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Adaptive, Matrix-Free Low-Rank Approximation
math.NA 2026-07 accept novelty 5.5 of 10

Adaptive matrix-free randomized QB algorithms determine rank on the fly via sketched residual indicators and pruning, meeting Frobenius or spectral tolerances to machine precision with near-optimal ranks.

Reference graph

Works this paper leans on

39 extracted references · 38 canonical work pages · cited by 1 Pith paper

[1]

heavy-tail

Introduction. In many image processing, information retrieval and scientiﬁc comp uting appli- cations, it is of great importance to compute a low-rank approximat ion to a large data matrix. Usually, the problem of low-rank matrix approximation falls into two categorie s: • The ﬁxed-rank problem, where the rank parameter k is given; • The ﬁxed-threshold, w...

arXiv 2025
[2]

In this section, we ﬁrst introduce the basic randomized SVD algorithm and its blocked version

Blocked randomized algorithms. In this section, we ﬁrst introduce the basic randomized SVD algorithm and its blocked version. Algorithm 2.1 (RSVD) Basic randomized SVD algorithm Input: m × n matrix A with m ≥ n, integer k > 0, oversampling parameter p ≥ 4 and ℓ = k + p ≪ n. Output: A rank- k approximation ˆAk. 1: Draw a random n × ℓ Gaussian matrix Ω via ...

work page
[3]

orth” in step 9 of blarank with “ reorth2

Moreover, it can be shown that the numerical rank of A − Q1QT 1 A is reduced by b from that of A (see the analysis in Theorem 3.4). Similarly, one can compute Q2 in the numerical range of A − Q1QT 1 A, which is also in the numerical range of A. Here Q2 and Q1 are mutually column-orthonormal, since Q1 is in the left kernel space of A − Q1QT 1 A. The numeri...

work page
[4]

As stated in ( 2.1)-(2.4), the quality of column-orthonormal matrix Q plays crucial roles in the accuracy of the algorithm

Approximate subspace and numerical rank decrease. As stated in ( 2.1)-(2.4), the quality of column-orthonormal matrix Q plays crucial roles in the accuracy of the algorithm. The accuracy o f the computed range space depends on how well the space R(Q) aligns with the space R(U(k)) spanned by the k dominant left singular vectors of A. If these two spaces we...

work page
[5]

Mandril” and “Cranﬁeld

Numerical experiments. In this section, we use the blarank and sblarank algorithms to calculate the numerical rank, numerical range and matrix approximation err or of a matrix with a low numerical rank. Existing larank [18] and Lanczos-based PROPACK [ 17] are compared for the same purpose. Since the PROPACK can not automatically determine the singular val...

work page
[6]

This paper proposed eﬃcient adaptive randomized rank-revealing a lgorithms for ﬁxed-threshold low-rank approximation problems

Conclusion. This paper proposed eﬃcient adaptive randomized rank-revealing a lgorithms for ﬁxed-threshold low-rank approximation problems. Based on a deﬂa tion process, the algorithm generates basis matrix Q := [Q Q ℓ] of A block by block, and each block can align well with those subblocks in the left singular matrix of A, provided the singular value gap ...

work page
[7]

D. S. Bernstein , Matrix Mathematics: Theory, Facts, and Formulas , 2nd edn. Princeton University Press, Princeton and Oxford (2009) pages

work page 2009
[8]

M. W. Berry and R. D. Fierro , Low-rank orthogonal decompositions for information retri eval applications, Numer. Linear Algebra Appl., 3 (1996), pp. 301-328. pages 15

work page 1996

Show all 39 references

[9]

Bertsekas, Constrained Optimization and Lagrange Multiplier Method , Academic Press, (1982) pages 17

D. Bertsekas, Constrained Optimization and Lagrange Multiplier Method , Academic Press, (1982) pages 17

1982
[10]

Brutzer, B

S. Brutzer, B. H ¨ oferlin, and G. Heidemann , Evaluation of background subtraction techniques for video surveillance . IEEE Compu. Vis. Patt. Recog., 32:14 (2011), pp. 1937-1944. pa ges 18

2011
[11]

J. F. Cai, E. J. Cand ` es, and Z.W. Shen , A singular value thresholding algorithm for matrix completion. SIAM J. Optim., 20:4 (2010), pp. 1956-1982. pages 2

2010
[12]

E. J. Cand ` es, X. Li, Y. Ma, and J. Wright , Robust principal component analysis? J. Assoc. Comput. Mach., 58 (2011), pp. 11:1-11:37. pages 17

2011
[13]

T. F. Chan , Rank revealing QR factorizations , Linear Algebra Appl., 88/89 (1987), pp. 67-82. pages

1987
[14]

Chandrasekaran and I

S. Chandrasekaran and I. C. F. Ipsen , On rank-revealing QR factorisations , SIAM J. Matrix Anal. Appl., 15 (1994), pp. 592-622. pages

1994
[15]

pa ges 15

Cornell SMART System, ftp://ftp.cs.cornell.edu/pub/smart. pa ges 15
[16]

Gu and S.C

M. Gu and S.C. Eisenstat , Eﬃcient algorithms for computing a strong rank-revealing Q R factor- ization, SIAM J. Sci. Comput., 17 (1996), pp. 848-869. pages

1996
[17]

R. D. Fierro and P. C. Hansen , Low-rank revealing UTV decompositions , Numer. Algorithms, 15 (1997), pp. 37-55. pages

1997
[18]

R. D. Fierro, P. C. Hansen, and P. S. K. Hansen , UTV tools: MATLAB templates for rank-revealing UTV decompositions, Numer. Algorithms, 20 (1999), pp. 165-194. pages 3

1999
[19]

G. H. Golub and C. F. V an Loan , Matrix Computations(4ed.), Johns Hopkins University Press, Baltimore (2013) pages 1, 4, 7, 8

2013
[20]

Gu , Subspace iteration randomization and singular value probl ems, SIAM J

M. Gu , Subspace iteration randomization and singular value probl ems, SIAM J. Sci. Comput. 37 (2015), pp. A1139-A1173. pages 2, 3, 4, 6, 8

2015
[21]

Halko, P

N. Halko, P. G. Martinsson, and J. A. Tropp , Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decomposi tions, SIAM Rev. 53 (2011), pp. 217-288. pages 2, 3, 4

2011
[22]

Y. P. Hong and C. T. Pan , Rank-revealing QR factorizations and the singular value de composition, Math. Comput., 58 (1992), pp. 213-232. pages

1992
[23]

R. M. Larsen , PROPACK-Software for large and sparse SVD calculations , http://sun. stan- ford.edu/˜rmunk/PROPACK/ pages 2, 13
[24]

T. L. Lee, T. Y. Li, and Z. G. Zeng , A rank-revealing method with updating, downdating, and applications. Part II , SIAM J. Matrix Anal. Appl. 31 (2009), pp. 503-525. pages 3, 6, 7, 10, 13, 15 ADAPTIVE RANDOMIZED ALGORITHMS FOR FIXED-THRESHOLD LOW-R ANK MATRIX APPROXIMATION21

2009
[25]

T. L. Lee, T. Y. Li, and Z. G. Zeng , RankRev: a Matlab package for computing the numerical rank and updating/downdating , Numer. Algorithms, 77 (2018), pp. 559-576. pages 3, 15

2018
[26]

Liberty, F

E. Liberty, F. Woolfe, P. Martinsson, V. Rokhlin, and M. Tyge rt, Randomized algo- rithms for the low-rank approximation of matrices , Proceedings of the National Academy of Sciences, 104(2007), pp. 20167-20172. pages 2

2007
[27]

Q. H. Liu, S. T. Ling, and Z. G. Jia , Randomized quaternion singular value decomposition for low-rank matrix approximation , SIAM J. Sci. Comput., 44:2 (2022), pp. A870-A900. pages

2022
[28]

M. W. Mahoney , Randomized algorithms for matrices and data , Found. Trends Mach. Learn., 3(2011), pp. 123-224. pages

2011
[29]

P. G. Martinsson, V. Rokhlin, and M. Tygert , A randomized algorithm for the decomposition of matrices , Appl. Comput. Harmon. Anal., 30 (2011), pp. 47-68. pages

2011
[30]

P. G. Martinsson and S. Voronin , A randomized blocked algorithm for eﬃciently computing rank-revealing factorization of matrices , SIAM J. Sci. Comput., 38(2016), pp. S485-S507. pages 2, 3, 4, 5, 6

2016
[31]

C. T. Pan , On the existence and computation of rank-revealing LU facto rizations, Linear Algebra Appl., 316 (2000), pp. 199-222. pages

2000
[32]

C. T. Pan and P. T. P. Tang , Bounds on singular values revealed by QR factorizations , BIT, 39 (1999), pp. 740-756. pages

1999
[33]

Ren, R-R Ma, Q

H. Ren, R-R Ma, Q. H. Liu, and Z.-J. Bai , Randomized quaternion QLP decomposition for low-rank approximation, J. Sci. Comput., 92 (2022), 80. pages 2

2022
[34]

H. Ren, G. Y. Xiao, and Z.-J. Bai , Single-pass randomized QLP decomposition for low-rank approximation, Calcolo, 59 (2022), 49. pages 2

2022
[35]

A. K. Saibaba , Randomized subspace iteration: Analysis of canonical angl es and unitarily invariant norms, SIAM J. Matrix Anal. Appl., 40:1 (2019), pp. 23-48. pages 4

2019
[36]

Woolfe, E

F. Woolfe, E. Liberty, V. Rokhlin, and M. Tygert , A fast randomized algorithm for the approximation of matrices , Appl. Comput. Harm. Anal., 25:3(2008), pp. 335-366. pages 2

2008
[37]

Wu and H

K. Wu and H. Simon , Thick-restart Lanczos method for large symmetric eigenval ue problems , SIAM J. Matrix Anal. Appl., 22 (2000), pp. 602-616. pages 2

2000
[38]

W. J. Yu, Y. Gu, and Y. H. Li , Eﬃcient randomized algorithms for the ﬁxed-precision low- rank matrix approximation, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 1339-1359. pages 2, 3, 5

2018
[39]

Zha and H

H. Zha and H. D. Simon , On updating problems in latent semantic indexing , SIAM J. Sci. Comput., 21 (1999), pp. 782-791. pages 15

1999

Pith tools

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

[1] [1]

heavy-tail

Introduction. In many image processing, information retrieval and scientiﬁc comp uting appli- cations, it is of great importance to compute a low-rank approximat ion to a large data matrix. Usually, the problem of low-rank matrix approximation falls into two categorie s: • The ﬁxed-rank problem, where the rank parameter k is given; • The ﬁxed-threshold, w...

arXiv 2025

[2] [2]

In this section, we ﬁrst introduce the basic randomized SVD algorithm and its blocked version

Blocked randomized algorithms. In this section, we ﬁrst introduce the basic randomized SVD algorithm and its blocked version. Algorithm 2.1 (RSVD) Basic randomized SVD algorithm Input: m × n matrix A with m ≥ n, integer k > 0, oversampling parameter p ≥ 4 and ℓ = k + p ≪ n. Output: A rank- k approximation ˆAk. 1: Draw a random n × ℓ Gaussian matrix Ω via ...

work page

[3] [3]

orth” in step 9 of blarank with “ reorth2

Moreover, it can be shown that the numerical rank of A − Q1QT 1 A is reduced by b from that of A (see the analysis in Theorem 3.4). Similarly, one can compute Q2 in the numerical range of A − Q1QT 1 A, which is also in the numerical range of A. Here Q2 and Q1 are mutually column-orthonormal, since Q1 is in the left kernel space of A − Q1QT 1 A. The numeri...

work page

[4] [4]

As stated in ( 2.1)-(2.4), the quality of column-orthonormal matrix Q plays crucial roles in the accuracy of the algorithm

Approximate subspace and numerical rank decrease. As stated in ( 2.1)-(2.4), the quality of column-orthonormal matrix Q plays crucial roles in the accuracy of the algorithm. The accuracy o f the computed range space depends on how well the space R(Q) aligns with the space R(U(k)) spanned by the k dominant left singular vectors of A. If these two spaces we...

work page

[5] [5]

Mandril” and “Cranﬁeld

Numerical experiments. In this section, we use the blarank and sblarank algorithms to calculate the numerical rank, numerical range and matrix approximation err or of a matrix with a low numerical rank. Existing larank [18] and Lanczos-based PROPACK [ 17] are compared for the same purpose. Since the PROPACK can not automatically determine the singular val...

work page

[6] [6]

This paper proposed eﬃcient adaptive randomized rank-revealing a lgorithms for ﬁxed-threshold low-rank approximation problems

Conclusion. This paper proposed eﬃcient adaptive randomized rank-revealing a lgorithms for ﬁxed-threshold low-rank approximation problems. Based on a deﬂa tion process, the algorithm generates basis matrix Q := [Q Q ℓ] of A block by block, and each block can align well with those subblocks in the left singular matrix of A, provided the singular value gap ...

work page

[7] [7]

D. S. Bernstein , Matrix Mathematics: Theory, Facts, and Formulas , 2nd edn. Princeton University Press, Princeton and Oxford (2009) pages

work page 2009

[8] [8]

M. W. Berry and R. D. Fierro , Low-rank orthogonal decompositions for information retri eval applications, Numer. Linear Algebra Appl., 3 (1996), pp. 301-328. pages 15

work page 1996