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

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

Problem Statement
The paper addresses the challenge of efficiently estimating the backward error, $\mu$, for linear least-squares problems with multiple right-hand sides:
$$\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}$. The backward error $\mu$ is defined as the minimum norm of perturbations $[E, \theta F]$ such that the approximate solution $X$ becomes an exact solution to the perturbed system $(A+E)^T(A+E)X = (A+E)^T(B+F)$.

Direct computation of $\mu$ is prohibitively expensive for iterative solvers because it requires solving a large eigenvalue problem or a generalized eigenvalue problem. While estimates exist (such as the Karlson-Waldén estimate), they are often expensive to compute exactly or lack guaranteed bounds (i.e., they are not strictly upper or lower bounds). The paper seeks a method to derive reliable, computationally cheap estimates, specifically focusing on lower bounds that can serve as stopping criteria for iterative methods like LSQR and LSMR.

Methodology
The core methodology relies on expressing the backward error in terms of a generalized eigenvalue problem within the framework of indefinite linear algebra.

1. Variational Formulation: The paper first establishes a variational equation for the backward error $\mu(A, R_\theta)$, where $R_\theta$ is a transformed residual matrix. It expresses $\mu$ as a maximization problem over an indefinite manifold defined by the constraint $X^T J_{n,d} X = -I_d$, where $J_{n,d} = \text{diag}(I_n, -I_d)$.
   $$\mu(A, R_\theta) = \sup_{X^T J_{n,d} X = -I_d} \left( \|R_\theta\|_F^2 - \|[A, R_\theta]X\|_F^2 \right)^{1/2}$$
2. Hyperbolic CS Decomposition: To solve this optimization problem, the authors utilize the hyperbolic CS decomposition (an indefinite analogue of the CS decomposition for unitary matrices). This decomposition allows the optimization over the matrix $X$ to be decoupled into optimizations over orthogonal matrices and diagonal scaling matrices.
3. Decomposition Theorem: By applying this decomposition, the paper derives a theorem showing that the backward error for a problem with $d$ right-hand sides can be decomposed into the sum of $d$ smaller backward error problems, each involving a single right-hand side.
4. Lower Bound Construction: Leveraging this decomposition, the authors propose a sketching-based lower bound. By computing a single test vector $p$ using a sketched matrix $SA$ (where $S$ is a sketching matrix), they can evaluate the single-right-hand-side backward error formula. This provides a provable lower bound on the true backward error.

Key Contributions

• Theorem 1 (Decomposition): The primary theoretical contribution is the decomposition of the backward error $\mu(A, R_\theta)$ into a sum of smaller terms:
  $$\mu(A, R_\theta) = \max_{P, Q} \left( \sum_{i=1}^k \mu^2(Ap_i, R_\theta q_i) \right)^{1/2}$$
  where $P$ and $Q$ are matrices with orthonormal columns. This reduces the complexity of the problem to a series of scalar optimizations.
• Exact Expression for Single Right-Hand Side: The paper provides a stable, closed-form expression for the backward error in the single right-hand side case, $\mu(a, r)$, which depends on the norms of the sum and difference of the vectors:
  $$\mu(a, r) = \frac{2|a^T r|}{\|a+r\|_2 + \|a-r\|_2}$$
• Sketching-Based Lower Bound: The authors propose a new lower bound for iterative methods. By using a sketching matrix $S$ to compute an approximate direction $p$, they can evaluate the single-right-hand-side formula to obtain a value $\mu(Ap/\|p\|_2, r_\theta)$.
  • This value is provably a lower bound on the true backward error.
  • The paper proves that this lower bound is of quality comparable to the sketched Karlson-Waldén estimate, specifically satisfying the inequality:
    $$\frac{1-\eta^2}{1+\eta^2} \nu(A, r_\theta) \leq \mu(Ap/\|p\|_2, r_\theta) \leq \mu(A, r_\theta)$$
    where $\eta$ represents the distortion of the sketch and $\nu$ is the Karlson-Waldén estimate.
• Iterative Refinement and Recycling: The paper discusses methods to improve this estimate via iterative refinement of the vector $p$ and "recycling" the computed vector $Ap$ across iterations to reduce computational cost.

Results
Numerical experiments were conducted using the LSMR solver on a matrix from the SuiteSparse collection with a high condition number ($\approx 3.5 \times 10^{16}$). The results indicate:

• The proposed lower bound is consistently comparable in accuracy to the sketched Karlson-Waldén estimate.
• In cases with cheaper sketches (smaller $n_{sketch}$), the proposed lower bound was sometimes more accurate than the sketched Karlson-Waldén estimate.
• The "recycled" lower bound (reusing $Ap$ across iterations) remained close to the true backward error for a significant portion of the iteration history, suggesting utility as a cheap error monitor.
• Iterative refinement of the vector $p$ improved accuracy only when the sketch size was very large ($16n$), suggesting that for standard sketch sizes, the added computational cost may not be justified.
• Attempts to construct upper bounds using similar techniques were found to be only marginally better than existing simple bounds (like $\|A^T r\|_2 / \|r\|_2$) and still significantly overestimated the true error.

Significance and Claims
The paper claims its primary significance is theoretical: it provides a decomposition of the backward error that naturally leads to computable lower bounds.

• Reliability: Unlike the sketched Karlson-Waldén estimate, which is not guaranteed to be an upper or lower bound, the proposed method yields a strict lower bound. This is valuable for stopping criteria, as it guarantees that the true error is at least as large as the estimate.
• Efficiency: The method allows for the conversion of a sketch-based estimate into a lower bound with comparable quality but with the added guarantee of being a bound.
• Modesty: The authors are modest regarding upper bounds, noting that their attempts to produce upper bounds in a similar manner were "generally unsuccessful." They acknowledge that the decomposition for multiple right-hand sides involves optimizing over two matrices ($P$ and $Q$), which is more complex than the single vector optimization required for the lower bound. Future work is suggested to address the multiple right-hand side case and to investigate why finding good upper bounds appears more difficult than finding good lower bounds.