Pith. sign in

REVIEW 2 major objections 5 minor 28 references

RCLUPPr: a new randomized CholeskyQR with LU preconditioning

T0 review · 2 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read RCLUPPr proves that factoring a tall-skinny matrix with LU before sketching yields QR factors with near-optimal orthogonality and residual, even for severely ill-conditioned inputs.

desk verdict The paper gives the first real rounding-error analysis of RCLUPPr and the numerics are broad, but Theorem 3.3's key hypotheses (8)-(9) are never checked, so the claim that the analysis 'rigorously proves' broader applicability is only conditional. read the letter →

arxiv 2607.15561 v1 pith:RT2AJ3W4 submitted 2026-07-17 math.NA cs.NA

Haoran Guan , Zhenyu Zou , Yufeng Wei , Yipei Chen , Peiting You , Yuwei Fan This is my paper · ORCID
classification math.NAcs.NA MSC 65F2565G50
keywords QRfactorizationrandomizednumericallinearalgebraCholeskyLUpreconditioningroundingerroranalysismixed-precisionarithmeticmatrixsketchingill-conditionedmatrices
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 proves a rounding-error bound for RCLUPPr, a randomized CholeskyQR algorithm that computes the QR factorization of tall-skinny matrices. The key idea is to run LU decomposition with partial pivoting on the input matrix first, and only then apply a random sketch to the L factor — the reverse of the earlier RCLUPP. Under conditions on the sketch and on the computed LU factors, RCLUPPr's Q and R satisfy near-optimal orthogonality and residual bounds with probability at least (1-p)^2, in single, double, and mixed precision. The practical payoff is that RCLUPPr reaches matrices with condition numbers far beyond those that break RCholeskyQR or RCLUPP, whose sketching-first order lets sketching error infect the preconditioner. Experiments on optimal-control, plasma-simulation, and control-theory matrices confirm the analysis and show speedups from multi-sketching and an adaptive fallback.

What carries the argument

The load-bearing mechanism is the LUPP-before-sketch ordering: Algorithm 6 computes [L,U,P] = LU(X) first, then sketches only L; the proof expands the computed preconditioner through the error chain (1)–(5) and bounds ||Y^{-1}||_2 ≤ 1.12/√(1-ϵ) · 1/(σn(Lhat)σn(Uhat)), which combined with (8)-(9) forces ||ΩP X Y^{-1} - H||_2 ≤ 0.19 and therefore bounds κ2(W) by 1.28/(0.8√((1-ϵ)/(1+ϵ)) - 0.08). CholeskyQR2 on W then yields the final orthogonality and residual bounds.

What would settle it

Run RCLUPPr in double precision on arrowhead matrices with κ2(X) from 10^15 to 10^30, checking condition (9) after each LU; if a matrix satisfying (6)–(9) yields orthogonality error above 6(mnu+n(n+1)u) or NaN, Theorem 3.3 is false. Conversely, if the failure rate grows to near 100% as κ2(X) reaches 10^35 even when (9) holds, the 'markedly better applicability' claim would be limited.

Watch

Extended reading notes

Core claim

The central claim is that, for full-rank X in R^{m×n}, RCLUPPr computes factors Qhat and Rhat satisfying ||Qhat^T Qhat - I_n||_F ≤ 6(mnu + n(n+1)u) and ||Qhat Rhat - X||_F ≤ Δres with probability at least (1-p)^2, provided the random sketch is an (ϵ,p,n) oblivious l2-subspace embedding with the distortion ratio above a threshold and the computed LU factors meet the conditioning inequalities (8)-(9). The analysis shows the error in sketching perturbs only the L factor, so the condition number of the preconditioned matrix W = X Y^{-1} stays bounded independently of κ2(X) up to order 1/(n^2 u). This extends the reach of CholeskyQR-type algorithms to severely ill-conditioned matrices and to mixe

Load-bearing premise

The whole guarantee rests on the random sketch being a strong enough subspace embedding and, crucially, on the computed LU factors actually satisfying the conditioning inequalities (8)–(9); those inequalities are not consequences of κ2(X), and Table 7 shows they fail for about a quarter of severe cases.

Editorial extensions

If this is right

  • If Theorem 3.3's conditions hold, RCLUPPr's Q is orthogonal to within 6(mnu + n(n+1)u) and its residual is bounded by Δres — the same order as RCLUPP, but with the applicability threshold on κ2(X) relaxed from roughly O(1) or O(1/(n^2 u)^{1/2}) to O(1/(n^2 u)).
  • In mixed-precision architecture, keeping the LU preconditioning step in double precision (dRCLUPPr) avoids the numerical breakdown that strikes the single-precision variant on highly ill-conditioned arrowhead matrices.
  • The robustness tests show a 100% success rate over 1000 trials for κ2(X) up to 10^10 and roughly 75% for κ2(X) around 10^27, exceeding the (1-p)=0.4 guarantee; this is the first robustness assessment of randomized CholeskyQR-type algorithms.
  • Multi-sketching reduces CPU time by up to about 42% for large sketch sizes, and the adaptive RCLUpPr variant is roughly 40–50% faster while keeping stability; these are practical accelerations validated on real-world matrices.

Reading between the lines

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

  • Inference: Because condition (9) is a property of the realized LU factors, not of κ2(X), one could compute κ2(Lhat)κ2(Uhat) after the LU step and decide adaptively whether to proceed or to fall back to a more robust path — turning the paper's sufficient condition into a data-dependent guard that could push the success rate toward 100%.
  • Inference: The LUPP-before-sketch ordering suggests a similar fix for other CholeskyQR variants: any preconditioner computed in high precision before sketching should inherit the same immunity to sketching error, e.g., replacing LU with a rank-revealing or column-pivoted factorization.
  • Inference: The residual bound of order ||X||_F·n√(n)u suggests RCLUPPr could serve as a drop-in replacement in iterative refinement schemes for least-squares problems, where a cheap, stable QR factor of a very ill-conditioned matrix is needed.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper presents a rounding-error analysis of RCLUPPr, a randomized CholeskyQR-type algorithm that first performs LUPP decomposition on the tall-skinny input X and then applies matrix sketching, Householder QR, and CholeskyQR2. The main theoretical result, Theorem 3.3, claims that under Assumptions 3.1–3.2 and conditions (6)–(9), the computed factors satisfy an orthogonality bound of order mnu + n(n+1)u and a residual bound Δres with probability at least (1−p)^2. The paper compares these bounds with those for RCholeskyQR, LC2, and RCLUPP, and reports numerical experiments in single, double, and mixed precision, including real-world matrices, robustness tests, and acceleration strategies such as multi-sketching and an adaptive variant. The residual bound in Theorem 3.3 suffers from a definitional inconsistency with the factor k, and the central applicability claim is conditional on computed-LU-factor hypotheses that are neither verified experimentally nor implied by κ2(X).

Significance. If the main theorem were correct and unconditional in the claimed sense, the paper would make a useful contribution: a CholeskyQR-type algorithm with provably wider applicability to ill-conditioned matrices in mixed precision would be valuable, and the numerical investigation is unusually thorough, covering real industrial matrices, robustness over many trials, and practical optimizations. The proof strategy is standard and clearly structured, building on known rounding-error lemmas. However, the residual bound has a concrete algebraic inconsistency, and the theorem's hypotheses are not tied to the input matrix X in a way that supports the abstract's claim of rigorously proved broader applicability. These issues affect the core contribution and require careful correction before the claims can be accepted.

major comments (2)
  1. [§3.3.2, Eqs. (63)–(64)] Equation (63) derives ∥Yhat∥F ≤ ∥X∥F / (0.8√(1+ε) − 0.084√(1−ε)) and defines k as the denominator. Equation (64) then bounds ∥Δx∥F using k as a multiplier, which is dimensionally inconsistent: the correct factor is 1/k, not k. The theorem statement also defines k = 0.8√(1+ε) − 0.1√(1−ε), which differs from the proof's value 0.084. This inconsistency directly affects the stated residual bound (11), the comparison in Table 3, and the claim that the residual is O(n²u) or controlled by a benign constant; as written, the residual bound is not established.
  2. [§3.1, Assumptions 3.1–3.2 and (6)–(9); §4.1, Eq. (79)] Theorem 3.3 is conditional on (8)–(9), which bound κ2(Lhat) and κ2(Lhat)κ2(Uhat) for the computed LU factors. These conditions are not implied by κ2(X); the one-directional argument in §4.1 uses κ2(X) ≤ a1 κ2(Lhat)κ2(Uhat), which does not show that every matrix with moderate κ2(X) satisfies (8)–(9). The numerical experiments in §5 report success/failure versus κ2(X) but never compute κ2(Lhat), κ2(Uhat), t, or check (8)–(9). Table 7 even shows roughly 25% failures for κ2(X) ≈ 1e27, indicating that the conditions can be violated in the reported regime. Thus the abstract's claim of ‘rigorously proves markedly better applicability’ to ill-conditioned matrices is not established as a statement about κ2(X); at most, the paper proves conditional stability when the LU factors are well behaved, and Remark 1's assertion that actual instances are ‘far less restrictive’ is unquantified.
minor comments (5)
  1. [§3, preamble] The text refers to ‘Δlu in (39)’ before equation (39) is introduced; the reference should be to equation (1).
  2. [§2.2, sketch-size formula] The formula for the Gaussian sketch size, s = η · logn · log 1p / ε², is missing parentheses and is ambiguous; please clarify the dependence on n, p, and ε.
  3. [§5.1.1] In the single-precision discussion, the sentence ‘RCLUPPr achieves numerical stability comparable to that of LC2 and RCLUPP’ would benefit from a qualifier explaining that this is in the tested parameter range; as written it could be read as unconditional.
  4. [Acknowledgement] ‘We express our great attitude to Professor Zhonghua Qiao’ should read ‘gratitude’.
  5. [Throughout] Several table captions and main text items have spacing artifacts such as ‘T able’ and ‘RCLUPPr’ vs. ‘RCLUPr’; a careful copyedit is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation chain is conditional on explicit assumptions and external rounding-error lemmas, and no fitted quantity is repackaged as a prediction.

full rationale

The central result, Theorem 3.3, is a conditional error analysis: it proves bounds on orthogonality and residual under Assumptions 3.1-3.2 and conditions (6)-(9). These hypotheses involve the random sketch Omega and the computed LU factors Lhat, Uhat; they are not equivalent to the target inequalities (10)-(11), so the theorem does not assume its own conclusion. The proof is built on external lemmas from Higham, Yamamoto et al., Terao/Ozaki/Ogita, and Higgins et al. (Lemmas 2.2-2.5, 2.8-2.9, [3, Theorem 3.3]), rather than on a self-referential chain. The self-citations to the authors' prior work [1] are used for the provenance of RCLUPPr and for comparison bounds for RCLUPP (e.g., [1, (4.25)], [1, Table 1]); these are disclosed, and they are not the mechanism by which RCLUPPr's own error bounds are derived. No fitted constant is later reported as a prediction, and the numerical experiments are independent of the proof. The main limitation is that (8)-(9) are not verified in the experiments, and Table 7 shows failures at very large condition numbers, so the practical regime of the theorem is not fully established; however, this is a question of whether the theorem's hypotheses are satisfied, not circularity.

Assumptions & free parameters 2 free parameters · 8 assumptions · 0 invented entities

No physical entities are invented. The paper's parameters are random-sketch settings and proof conditions, not fitted constants. The main burden is Assumption 3.2 and (6)-(9), which are sufficient conditions tailored to make the proof go through; the robustness experiments in Table 7 suggest these conditions are violated in roughly 25% of extreme ill-conditioned trials.

free parameters (2)
  • a1 = unspecified constant 'slightly greater than 1'
    Introduced in Section 4.1 (Eq. (79)) to convert the bound on kappa_2(Lhat)kappa_2(Uhat) into a bound on kappa_2(X); its value is not quantified, so Table 1's RCLUPPr row is qualitative.
  • experimental sketch parameters epsilon, p, s = epsilon=0.5, p=0.6, s=2n (values vary per test)
    User-set parameters in the numerical experiments, not fitted to data. They affect the probability guarantees but are not tuned to make the central claim fit the results.
assumptions (8)
  • standard math Higham rounding-error bounds (Lemmas 2.2-2.5): matrix multiplication, LU, triangular solve, Householder QR
    Used throughout Section 3 to bound Delta_lu, Delta_s, Delta_h, Delta_y, Delta_x.
  • standard math Weyl's theorem and standard singular-value inequalities
    Invoked in Lemmas 3.8, 3.9 and the proof of Theorem 3.3 to bound singular values of sums and products.
  • standard math Oblivious l2-subspace embedding property of the Gaussian sketch (Definition 2.7, Lemma 2.9)
    Provides the norm and singular-value distortion bounds (1-epsilon)^{1/2} etc. used in Lemmas 3.5-3.10.
  • domain assumption X is tall-skinny with full column rank: m >= n and rank(X) = n
    Stated at the start of the paper and used to ensure the QR factorization and CholeskyQR2 are well-defined.
  • ad hoc to paper Assumption 3.2: sqrt((1-epsilon)/(1+epsilon)) > max(12.8 sqrt(mn)u + n(n+1)u + 0.1, 10.44 n sqrt(n)u + 0.1, 0.105)
    A paper-specific sufficient condition chosen to make the constants in the proof work; it is not a standard theorem.
  • ad hoc to paper Conditions (6)-(9): m sqrt(n)u <= 1/64, c1 s n sqrt(n) u_b <= 1/64, and bounds on kappa_2(Lhat), kappa_2(Lhat)kappa_2(Uhat)
    These are sufficient conditions for Theorem 3.3 and are not verified for the test matrices in Section 5. They are load-bearing for the proof.
  • ad hoc to paper Assumption 3.1: steps 2-4 run with higher precision u_b, while LUPP, triangular solve, and CholeskyQR2 run with u
    This is the mixed-precision implementation assumption used in Lemmas 3.4-3.10.
  • standard math Yamamoto et al. CholeskyQR2 error bound [3, Theorem 3.3]
    Used directly at the end of the orthogonality proof (3.3.1) to convert a bound on kappa_2(W) into the final orthogonality bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of RCLUPPr: a new randomized CholeskyQR with LU preconditioning." pith.science (2026). https://pith.science/paper/RT2AJ3W4

@misc{pith2026260715561,
  author       = {Pith},
  title        = {Pith review of: RCLUPPr: a new randomized CholeskyQR with LU preconditioning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RT2AJ3W4}},
  note         = {Machine review of arXiv:2607.15561}
}
abstract

In this work, we present the comprehensive rounding error analysis of RCLUPPr proposed in \cite{RCLUPP}, which is a novel randomized CholeskyQR-type algorithm performing LU decomposition with partial pivoting (LUPP decomposition) directly on the tall-skinny $X\in\mathbb{R}^{m\times n}$ with $m \ge n$ and $\mbox{rank}(X)=n$. In contrast to the existing RCLUPP in \cite{RCLUPP}, which applies matrix sketching before LUPP decomposition, RCLUPPr places LUPP decomposition as a preconditioning step first, significantly reducing error propagation. Our analysis rigorously proves that RCLUPPr enjoys markedly better applicability to the ill-conditioned matrices than the existing CholeskyQR-type algorithms and remains stable and accurate in the mixed-precision arithmetic. We further propose practical acceleration strategies in the real implementations of RCLUPPr. Extensive numerical experiments on the real-world problems confirm the theoretical results in this work, demonstrating the robustness and practicality of RCLUPPr in the single, double, and the mixed-precision architecture.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 4 linked inside Pith

  1. [1]

    arxiv preprint arXiv:2412.06551 (2024)

    Fan, Y., Guan, H., Qiao, Z.: A new randomized CholeskyQR based on LU decomposition with partial pivoting. arxiv preprint arXiv:2412.06551 (2024)

    arXiv 2024

  2. [2]

    In: 2014 5th Workshop on Latest Advances in Scalable Algorithms for Large-scale Systems, pp

    Fukaya, T., Nakatsukasa, Y., Yanagisawa, Y., Yamamoto, Y.: CholeskyQR2: a simple and communication-avoiding algorithm for computing a tall-skinny QR factorization on a large-scale parallel system. In: 2014 5th Workshop on Latest Advances in Scalable Algorithms for Large-scale Systems, pp. 31–38 (2014). IEEE

    2014

  3. [3]

    Electronic Transactions on Numerical Analysis 44(01) (2015)

    Yamamoto, Y., Nakatsukasa, Y., Yanagisawa, Y., Fukaya, T.: Roundoff error analysis of the CholeskyQR2 algorithm. Electronic Transactions on Numerical Analysis 44(01) (2015)

    2015

  4. [4]

    Journal of Scientific Computing 104(2) (2025)

    Fan, Y., Guan, H., Qiao, Z.: An Improved Shifted CholeskyQR Based on Columns. Journal of Scientific Computing 104(2) (2025)

    2025

  5. [5]

    SIAM Journal on Scientific Computing 42(1), 477–503 (2020)

    Fukaya, T., Kannan, R., Nakatsukasa, Y., Yamamoto, Y., Yanagisawa, Y.: Shifted Cholesky QR for computing the QR factorization of ill-conditioned matrices. SIAM Journal on Scientific Computing 42(1), 477–503 (2020)

    2020

  6. [6]

    Parallel Computing 92, 102571 (2020)

    Terao, T., Ozaki, K., Ogita, T.: LU-Cholesky QR algorithms for thin QR decomposition. Parallel Computing 92, 102571 (2020)

    2020

  7. [7]

    SIAM review 53(2), 217–288 (2011)

    Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review 53(2), 217–288 (2011)

    2011

  8. [8]

    Acta Numerica 29, 403–572 (2020) 31

    Martinsson, P.G., Tropp, J.A.: Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica 29, 403–572 (2020) 31

    2020

Show all 28 references
  1. [9]

    arxiv preprint arXiv:2210.09953 (2022)

    Balabanov, O.: Randomized CholeskyQR factorizations. arxiv preprint arXiv:2210.09953 (2022)

    2022 arXiv

  2. [10]

    arxiv preprint arxiv:2111.11148 (2021)

    Fan, Y., Guo, Y., Lin, T.: A Novel Randomized XR-Based Preconditioned CholeskyQR Algorithm. arxiv preprint arxiv:2111.11148 (2021)

    2021 arXiv

  3. [11]

    Numerische Math- ematik 157, 1695–1737 (2025)

    Higgins, A., Szyld, D., Boman, E., Yamazaki, I.: Analysis of Randomized Householder-Cholesky QR factorization with multisketching. Numerische Math- ematik 157, 1695–1737 (2025)

    2025

  4. [12]

    SIAM Journal on Scientific Computing 37, 307–330 (2015)

    Yamasaki, I., Tomov, S., Dongarra, J.: Mixed-precision Cholesky QR factorization and its case studies on Multicore CPU with Multiple GPUs. SIAM Journal on Scientific Computing 37, 307–330 (2015)

    2015

  5. [13]

    The Johns Hopkins University Press, Baltimore (2013)

    Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. The Johns Hopkins University Press, Baltimore (2013)

    2013

  6. [14]

    Higham, N.J.: Accuracy and Stability of Numerical Algorithms, second ed. edn. SIAM, Philadelphia, PA, USA (2002)

    2002

  7. [15]

    SIAM Journal on Scientific Computing 44(3), 1450–1474 (2022)

    Balabanov, O., Grigori, L.: Randomized Gram–Schmidt Process with Application to GMRES. SIAM Journal on Scientific Computing 44(3), 1450–1474 (2022)

    2022

  8. [16]

    In: Proceedings of the Forty- Fifth Annual ACM Symposium on Theory of Computing

    Meng, X., Mahoney, M.W.: Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In: Proceedings of the Forty- Fifth Annual ACM Symposium on Theory of Computing. STOC ’13, pp. 91–100. Association for Computing Machinery, New York...

    2013

  9. [17]

    Foundations and Trends in Theoretical Computer Science 10(1–2), 1–157 (2014)

    Woodruff, D.P.: Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science 10(1–2), 1–157 (2014)

    2014

  10. [18]

    In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp

    Sarlos, T.: Improved Approximation Algorithms for Large Matrices via Random Projections. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 143–152 (2006)

    2006

  11. [19]

    Tr¨ oltzsch, F.: Optimal Control of Partial Differential Equations: Theory, Methods, and Applications vol. 112. American Mathematical Soc., ??? (2010)

    2010

  12. [20]

    SIAM Journal on Optimization13(2), 321– 334 (2002)

    Kunisch, K., R¨ osch, A.: Primal-dual active set strategy for a general class of constrained optimal control problems. SIAM Journal on Optimization13(2), 321– 334 (2002)

    2002

  13. [21]

    Physics of Plasmas 20(1), 013507 (2013) https://doi.org/10.1063/1

    Turner, M.M., Derzsi, A., Donk´ o, Z., Eremin, D., Kelly, S.J., Lafleur, T., Mussenbrock, T.: Simulation benchmarks for low-pressure plasmas: Capacitive discharges. Physics of Plasmas 20(1), 013507 (2013) https://doi.org/10.1063/1. 4775084

    2013 doi

  14. [22]

    Journal of Computational Physics 159(1), 1–11 (2000)

    Hagelaar, G.J., Pitchford, L.: Speeding up fluid models for gas discharges by 32 implicit treatment of the electron energy source term. Journal of Computational Physics 159(1), 1–11 (2000)

    2000

  15. [23]

    Linear Algebra and its Applications 418, 886–890 (2006)

    Borobia, A.: Constructing matrices with prescribed main-diagonal submatrix and characteristic polynomial. Linear Algebra and its Applications 418, 886–890 (2006)

    2006

  16. [24]

    2015 12th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCW AMTIP), 473–475 (2015)

    Li, Z., Wang, Y., Li, S.: The inverse eigenvalue problem for generalized Jacobi matrices with functional relationship. 2015 12th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCW AMTIP), 473–475 (2015)

    2015

  17. [25]

    Linear Algebra and its Applications 416, 336–347 (2006)

    Peng, J., Hu, X., Zhang, L.: Two inverse eigenvalue problems for a special kind of matrices. Linear Algebra and its Applications 416, 336–347 (2006)

    2006

  18. [26]

    Springer Publishing Company, Incorporated, ??? (2012)

    Tveito, A., Langtangen, H.P., Nielsen, B.F., Cai, X.: Elements of Scientific Computing. Springer Publishing Company, Incorporated, ??? (2012)

    2012

  19. [27]

    ArXiv abs/1505.07570 (2015)

    Wang, S.: A practical guide to randomized matrix computations with matlab implementations. ArXiv abs/1505.07570 (2015)

    2015 arXiv

  20. [28]

    Theoretical Computer Science 312(1), 3–15 (2004)

    Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. Theoretical Computer Science 312(1), 3–15 (2004). Automata, Lan- guages and Programming 33

    2004

Pith tools

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