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

Eric Hallman · 2026

Read A Variational Equation and Lower Bound for the Linear Least-Squares Backward Error by Eric Hallman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-09211.txt.

Introduction

Hallman finds a fresh variational formula for the linear least squares backward error, the smallest perturbation that makes an approximate solution exact. The derivation expresses the error through a generalised eigenvalue problem, drawing on results from indefinite linear algebra. With several right hand sides, the equation breaks the backward error down into smaller component problems.

Backward error matters for stopping rules of iterative solvers, which halt once the error falls below a user chosen tolerance. Direct computation is prohibitively expensive, since it demands solving a large eigenvalue problem, so cheap and reliable estimates are prized. Hallman also proposes a new sketching based lower bound, matching the sketched Karlson-Waldén estimate in quality. Stopping criteria for iterative methods, including LSQR and LSMR, are considered. The equation gives practitioners a principled way to judge when an iterative solution is good enough.

Catalog record

CREATOREric Hallman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.09211

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Variational Equation and Lower Bound for the Linear Least-Squares Backward Error Eric Hallman Abstract 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én estimate. Keywords : Linear least squares, backward error, generalized eigenvalue problem, stopping criteria, iterative methods, LSQR, LSMR, Karlson-Waldén estimate MSC Classification : 15A06, 15A18, 15A22, 15A42, 65F10 1 Introduction Given an approximate solution X to the linear least-squares problem \min_{X\in\mathbb{R}^{n\times d}}\|AX-B\|_{F}, where A\in\mathbb{R}^{m\times n} and B\in\mathbb{R}^{m\times d} , this paper considers the problem of efficiently estimating the backward error \mu\equiv\min_{E,F}\left\{\|[E,\theta F]\|_{F}\,:\,(A+E)^{T}(A+E)X=(A+E)^{T}(B+F)\right\}. (1) Here, E and F are perturbations such that X is an exact solution to the perturbed least-squares problem, and \theta\in(0,\infty] is a weighting parameter. In principle, the backward error can be used in stopping criteria for iterative least-squares solvers, where the solver halts once \mu falls below a user-defined tolerance. In practice, computing \mu directly requires solving a large eigenvalue problem and so is prohibitively expensive in this context. It is therefore desirable to find estimates that are both cheap and reliable; see [ 14 , 13 , 7 , 10 , 2 ] for some prior work on this topic. A key term appearing in expressions for the backward error is R_{\theta}\equiv R\begin{bmatrix}X\\ -\theta^{-1}I\end{bmatrix}^{\dagger},\quad\text{where}\quad R\equiv B-AX, where A^{\dagger} denotes the Moore-Penrose inverse of A . It represents the optimal backward error for the consistent problem, R_{\theta}=\argmin_{[E,\theta F]}\left\{\|[E,\theta F]\|_{F}\,:\,(A+E)X=B+F\right\}, provided a valid perturbation exists. This requires the following condition: Condition 1 . The approximate solution X satisfies \mathcal{R}(R^{T})\subseteq\mathcal{R}([X^{T},\theta^{-1}I]) . It is sufficient to have \theta<\infty , or for X to have full column rank. Under this condition, the backward error may be expressed as \mu=\mu(A,R_{\theta})\equiv\min_{Y}\left(\|YY^{\dagger}A\|_{F}^{2}+\|(I-YY^{\dagger})R_{\theta}\|_{F}^{2}\right)^{\frac{1}{2}}. (2) If 1 is not satisfied, the analysis is slightly more complicated [ 19 , Thm. 5.1] but still requires solving a problem of the same type as Eq. 2 . We find it useful to study the binary function \mu(A,R_{\theta}) as opposed to the definition Eq. 1 from which it was derived, and so will use the term “backward error” to refer to \mu(A,R_{\theta}) for the remainder of the paper. Remark 1 . It can be seen from Eq. 2 that \mu(A,R_{\theta}) is invariant under right rotations of its inputs. We can therefore assume without loss of generality that A and R_{\theta} both have full column rank. Accordingly, sometimes R(\theta^{-2}I+X^{T}X)^{-1/2} is used in place of R_{\theta} in the literature, or \theta r/\sqrt{1+\theta^{2}\|x\|_{2}^{2}} for problems with a single right-hand side. The main contribution of this work is the following theorem, which elegantly decomposes the backward error as a sum of smaller backward error problems: Theorem 1 . Let A\in\mathbb{R}^{m\times n} and R_{\theta}\in\mathbb{R}^{m\times d} . Then with \mu(A,R_{\theta}) defined as in Eq. 2 and k\equiv\min(n,d) , \mu(A,R_{\theta})=\max_{\begin{subarray}{c}P^{T}P=I_{k}\\ Q^{T}Q=I_{k}\end{subarray}}\left(\sum_{i=1}^{k}\mu^{2}(Ap_{i},R_{\theta}q_{i})\right)^{\frac{1}{2}}, (3) where P=[p_{1},\ldots,p_{k}]\in\mathbb{R}^{n\times k} and Q=[q_{1},\ldots,q_{k}]\in\mathbb{R}^{d\times k} . Each summand can be evaluated cheaply and stably; Theorem 3 gives an exact expression. We also consider some potential applications of Theorem 1 to stopping criteria for iterative methods. The main point of comparison in this regard is the sketched Karlson-Waldén estimate [ 2 ] , which uses subspace embedding techniques to estimate the highly accurate Karlson-Waldén estimate [ 14 , 6 ] . The room for improvement is admittedly limited, as the sketched Karlson-Waldén estimate was found in [ 2 ] to be highly accurate in practice. Still, there is one notable difference: any estimate derived from Eq. 3 is a lower bound on the backward error, while the sketched Karlson-Waldén estimate is not necessarily an upper or lower bound. The rest of the paper is organized as follows: Section 2 provides background including notations and some lemmas. Section 3 proves an intermediate result that involves expressing the backward error in terms of a generalized eigenvalue problem. Section 4 gives the proof of the main result, along with some results for problems with a single right-hand side. Section 5 considers applications to error bounds and stopping criteria. Section 6 includes the results of some numerical experiments, and Section 7 offers our concluding remarks. 2 Background It was shown in [ 19 , Thm. 4.2] that the backward error can be expressed as \mu(A,R_{\theta})=\left(\|R_{\theta}\|_{F}^{2}+\operatorname{tr}_{-}(AA^{T}-R_{\theta}R_{\theta}^{T})\right)^{\frac{1}{2}}, (4) where \operatorname{tr}_{-}(X) denotes the sum of the negative eigenvalues of X . This value can be attained in Eq. 2 by having YY^{\dagger} project onto the negative eigenspace of AA^{T}-R_{\theta}R_{\theta}^{T} . This matrix has rank at most n+d . If m\gg n\gg d then the cost of computing \mu(A,R_{\theta}) can be reduced using a QR factorization or SVD of A [ 20 , 14 ] , but this is generally not practical in the context of iterative solvers. Three simple upper bounds on \mu(A,R_{\theta}) are obtained by evaluating Eq. 2 for Y=0 , Y=A , and Y=R_{\theta} . The first choice yields \mu\leq\|R_{\theta}\|_{F} , but this is not an especially useful upper bound since the residual does not necessarily converge to zero. The second is too costly to compute to be used for stopping rules, although efforts to estimate it are made in [ 13 ] . The third equals \|A^{T}r\|_{2}/\|r\|_{2} for problems with a single right-hand side, and it is used in stopping rules for iterative solvers LSQR [ 18 ] and LSMR [ 3 ] . However, it is possible for these three bounds to simultaneously overestimate \mu by a factor depending on the condition number of A [ 7 ] . The proofs in this work are often simplified by assuming that [A,R_{\theta}] has full column rank, then invoking a continuity argument. This argument can be made precise via the following lemma: Lemma 1 . The backward error as defined in Eq. 2 satisfies \lim_{\epsilon\rightarrow 0}\mu\left(\begin{bmatrix}A\\ \epsilon I\\ 0\end{bmatrix},\begin{bmatrix}R_{\theta}\\ 0\\ \epsilon I\end{bmatrix}\right)=\mu(A,R_{\theta}). Proof. Use Eq. 4 and the fact that eigenvalues are continuous. ∎ 2.1 The Karlson-Waldén estimate The Karlson-Waldén estimate was derived in [ 14 , (2.6)] as the solution to a maximization problem \displaystyle\nu(A,r_{\theta}) \displaystyle\equiv\max_{\|p\|_{2}=1}\frac{|p^{T}A^{T}r_{\theta}|}{(\|Ap\|_{2}^{2}+\|r_{\theta}\|_{2}^{2})^{1/2}} \displaystyle=\|(A^{T}A+\|r_{\theta}\|_{2}^{2}I)^{-1/2}A^{T}r_{\theta}\|_{2}, where the maximum is attained by p\propto(A^{T}A+\|r_{\theta}\|_{2}^{2}I)^{-1}A^{T}r_{\theta} . For multiple right-hand sides, the estimate can be defined additively: if W=[w_{1},\ldots,w_{d}] is a set of right singular vectors for R_{\theta} , then \nu(A,R_{\theta})\equiv\left(\sum_{i=1}^{d}\nu^{2}(A,R_{\theta}w_{i})\right)^{\frac{1}{2}}. (5) It can alternately be defined in terms of a minimal perturbation [ 10 , (14)] \nu(A,R_{\theta})=\min_{E,F}\{\|[E,F]\|_{F}\ :\ A^{T}F+E^{T}R_{\theta}=-A^{T}R_{\theta}\}, which shows that \nu(A,R_{\theta}) , like \mu(A,R_{\theta}) , is symmetric in its inputs and invariant under right rotations of the inputs. The Karlson-Waldén estimate is always accurate, satisfying [ 10 , Thm. 4.8] 1\leq\frac{\mu(A,R_{\theta})}{\nu(A,R_{\theta})}\leq\sqrt{1+\|AA^{\dagger}R_{\theta}R_{\theta}^{\dagger}\|_{2}}\leq\sqrt{2}. The \sqrt{2} bound cannot be improved in general [ 6 ] . For the single right-hand side case the asymptotic accuracy of \nu(A,r_{\theta}) was proved in [ 8 , Thm. 4.8] , and [ 6 , Cor. 3.2] gives an asymptotic bound that is tighter than the one stated above. 2.1.1 The sketched Karlson-Waldén estimate The Karlson-Waldén estimate is still too expensive to use directly

Read the complete text