pith. machine review for the scientific record. sign in

arxiv: 2605.09211 · v1 · submitted 2026-05-09 · 🧮 math.NA · cs.NA

Recognition: no theorem link

A Variational Equation and Lower Bound for the Linear Least-Squares Backward Error

Eric Hallman

Pith reviewed 2026-05-12 02:40 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords linear least-squaresbackward errorvariational equationgeneralized eigenvalue problemsketchingiterative methodsnumerical stability
0
0 comments X

The pith

The linear least-squares backward error satisfies a variational equation obtained from a generalized eigenvalue problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the backward error in linear least-squares problems admits a new variational characterization by rewriting the error quantity as a generalized eigenvalue problem and invoking results from indefinite linear algebra. For systems with several right-hand sides the same equation shows the total backward error equals the sum of independent smaller backward-error subproblems. The derivation also supplies a sketching-based lower bound whose quality is provably comparable to the existing sketched Karlson-Waldén estimate, with direct consequences for the design of stopping criteria in iterative least-squares solvers.

Core claim

By expressing the backward error as the solution of a generalized eigenvalue problem and applying indefinite linear algebra, the paper obtains a variational equation that governs the linear least-squares backward error; when multiple right-hand sides are present this equation decomposes the error into a sum of smaller independent problems, and the same framework yields a new sketching lower bound comparable in quality to the sketched Karlson-Waldén estimate.

What carries the argument

The variational equation for the backward error, derived by recasting the error quantity as a generalized eigenvalue problem.

If this is right

  • The backward error for multiple-right-hand-side problems factors exactly into a sum of independent smaller backward-error problems.
  • Stopping criteria for iterative least-squares methods can be constructed directly from the variational equation.
  • A sketching-based lower bound of quality comparable to the sketched Karlson-Waldén estimate becomes available for large-scale problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The decomposition property could be exploited to design block-iterative solvers that monitor error on individual right-hand sides separately.
  • The same variational perspective might be tested on related problems such as total-least-squares or regularized least-squares.
  • The sketching lower bound offers a practical route to cheap a-posteriori error checks inside existing iterative libraries.

Load-bearing premise

The backward error can be expressed as a generalized eigenvalue problem to which standard results from indefinite linear algebra apply directly.

What would settle it

A concrete least-squares instance for which the proposed variational equation fails to recover the known backward error value, or a numerical example in which the new sketching lower bound falls outside the provably comparable quality range relative to the Karlson-Waldén estimate.

Figures

Figures reproduced from arXiv: 2605.09211 by Eric Hallman.

Figure 1
Figure 1. Figure 1: Relative backward error estimates (left) and ratios compared to the [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
read the original abstract

This paper derives a new variational equation for the linear least-squares backward error by expressing the backward error in terms of a generalized eigenvalue problem and using results from indefinite linear algebra. For problems with multiple right-hand sides, the variational equation also shows that the backward error can be decomposed as a sum of smaller backward error problems. Applications to stopping criteria for iterative methods are considered, and a new sketching-based lower bound is proposed which is provably of quality comparable to the sketched Karlson-Wald\'{e}n estimate.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. The manuscript derives a new variational equation for the linear least-squares backward error by expressing the backward error in terms of a generalized eigenvalue problem and applying results from indefinite linear algebra. For multiple right-hand sides it shows a decomposition of the backward error into a sum of smaller independent problems. Applications to stopping criteria for iterative solvers are discussed, and a sketching-based lower bound is proposed whose quality is provably comparable to the sketched Karlson-Waldén estimate.

Significance. If the derivation is correct, the work supplies a new theoretical tool for backward-error analysis of least-squares problems that unifies variational and eigenproblem viewpoints and yields an explicit decomposition for multiple right-hand sides. The sketching lower bound, being provably comparable to an existing estimate, offers a practical route to efficient a-posteriori error control in large-scale settings. The explicit use of indefinite-linear-algebra results is a notable technical contribution if the mapping is shown to be rigorous.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the clear summary of its contributions, and the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation uses external indefinite linear algebra results

full rationale

The paper's central derivation expresses the linear least-squares backward error as the solution to a generalized eigenvalue problem and applies known results from indefinite linear algebra to obtain a variational equation. For multiple right-hand sides it derives a decomposition into smaller problems. A sketching lower bound is introduced with a stated provable comparability to the Karlson-Waldén estimate. None of these steps reduce by construction to fitted parameters, self-citations, or renamed inputs within the paper; the load-bearing mathematics relies on external theorems rather than internal redefinition or self-referential fitting. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on expressing the backward error as a generalized eigenvalue problem, which assumes standard properties of such problems hold in this context.

axioms (1)
  • domain assumption Results from indefinite linear algebra apply to the formulation of the linear least-squares backward error.
    The paper uses these results to derive the variational equation from the generalized eigenvalue problem.

pith-pipeline@v0.9.0 · 5370 in / 1309 out tokens · 53144 ms · 2026-05-12T02:40:00.226310+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    T. A. Davis and Y. Hu. The University of Florida Sparse Matrix Collection. Acm transactions on mathematical software (toms), 38(1):1–25, 2011

    work page 2011

  2. [2]

    E. N. Epperly, M. Meier, and Y. Nakatsukasa. Fast randomized least- squares solvers can be just as accurate and stable as classical direct solvers. Communications on Pure and Applied Mathematics, 79(2):293–339, 2026

    work page 2026

  3. [3]

    D. C.-L. Fong.Minimum-residual methods for sparse least-squares using Golub-Kahan bidiagonalization. PhD thesis, Stanford University, 2011

    work page 2011

  4. [4]

    D. C.-L. Fong and M. Saunders. LSMR: An iterative algorithm for sparse least-squares problems.SIAM Journal on Scientific Computing, 33(5):2950–2971, 2011

    work page 2011

  5. [5]

    G. H. Golub and C. F. Van Loan.Matrix Computations. The Johns Hopkins University Press, Baltimore, 4th edition, 2013

    work page 2013

  6. [6]

    Gratton, P

    S. Gratton, P. Jir´ anek, and D. Titley-Peloquin. On the accuracy of the Karlson–Wald´ en estimate of the backward error for linear least squares problems.SIAM Journal on Matrix Analysis and Applications, 33(3):822– 836, 2012

    work page 2012

  7. [7]

    Gratton, P

    S. Gratton, P. Jir´ anek, and D. Titley-Peloquin. Simple backward error bounds for linear least-squares problems.Linear Algebra and its Applica- tions, 439(1):78–89, 2013

    work page 2013

  8. [8]

    J. F. Grcar. Optimal sensitivity analysis of linear least squares.Lawrence Berkeley National Laboratory, Report LBNL-52434, 99:27–34, 2003

    work page 2003

  9. [9]

    E. Hallman. Estimating the backward error for the least-squares prob- lem with multiple right-hand sides.Linear Algebra and its Applications, 605:227–238, 2020. 17

    work page 2020

  10. [10]

    Hallman and M

    E. Hallman and M. Gu. LSMB: Minimizing the backward error for least- squares problems.SIAM Journal on Matrix Analysis and Applications, 39(3):1295–1317, 2018

    work page 2018

  11. [11]

    P. Henrici. Two remarks on the Kantorovich inequality.The American Mathematical Monthly, 68(9):904–906, 1961

    work page 1961

  12. [12]

    N. J. Higham. J-orthogonal matrices: Properties and generation.SIAM review, 45(3):504–519, 2003

    work page 2003

  13. [13]

    Jir´ anek and D

    P. Jir´ anek and D. Titley-Peloquin. Estimating the backward error in LSQR. SIAM Journal on Matrix Analysis and Applications, 31(4):2055–2074, 2010

    work page 2055

  14. [14]

    Karlson and B

    R. Karlson and B. Wald´ en. Estimation of optimal backward perturbation bounds for the linear least squares problem.BIT Numerical Mathematics, 37(4):862–869, 1997

    work page 1997

  15. [15]

    S. P. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. A. Davis, M. Hender- son, Y. Hu, and R. Sandstrom. The SuiteSparse Matrix Collection website interface.Journal of Open Source Software, 4(35):1244, 2019

    work page 2019

  16. [16]

    Kovaˇ c-Striko and K

    J. Kovaˇ c-Striko and K. Veseli´ c. Trace minimization and definiteness of symmetric pencils.Linear Algebra and its Applications, 216:139–158, 1995

    work page 1995

  17. [17]

    Martinsson and J

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

    work page 2020

  18. [18]

    C. C. Paige and M. A. Saunders. LSQR: An algorithm for sparse linear equations and sparse least squares.ACM Transactions on Mathematical Software (TOMS), 8(1):43–71, 1982

    work page 1982

  19. [19]

    J.-G. Sun. Optimal backward perturbation bounds for the linear least- squares problem with multiple right-hand sides.IMA Journal of Numerical Analysis, 16(1):1–11, 1996

    work page 1996

  20. [20]

    Wald´ en, R

    B. Wald´ en, R. Karlson, and J.-G. Sun. Optimal backward perturbation bounds for the linear least squares problem.Numerical Linear Algebra with Applications, 2(3):271–286, 1995. 18

    work page 1995