Convergence rates for pivoted QR and LU

Technical Summary: Convergence Rates for Pivoted QR and LU

Problem Statement
Pivoted QR and pivoted LU decompositions are widely used greedy algorithms for computing low-rank approximations of matrices and functions. While these methods demonstrate strong practical performance, their theoretical justification has historically relied on worst-case bounds that contain exponentially growing factors (e.g., $4^k$ or $2^k$). These bounds suggest that convergence is only guaranteed when singular values decay geometrically at a rate sufficient to overcome the exponential factors (e.g., $\rho < 1/4$). However, in practice, these algorithms often converge effectively even under more modest singular value decay (algebraic or slower geometric decay). The paper addresses the gap between these pessimistic worst-case bounds and observed practical behavior by deriving convergence rates that depend directly on the decay of singular values or function regularity, without exponential penalty factors.

Methodology
The core of the analysis relies on two primary components:

1. Approximate Greedy Pivoting: The authors relax the requirement for exact greedy pivoting (selecting the absolute maximum entry or column norm) to approximate greedy pivoting. In this scheme, the selected pivot $p_{k+1}$ satisfies $|p_{k+1}| \ge \gamma \|E^{(k)}\|_{\max}$ (for LU) or $\rho_{k+1} \ge \gamma \|E^{(k)}\|_{2,\infty}$ (for QR), where $0 < \gamma \le 1$ is a quality constant.
2. Pivot-Product Identities and Determinant Bounds: The analysis utilizes classical identities linking the product of pivots to the determinant of a submatrix formed by the selected indices.
   • For LU, $\det(A_{I_n, J_n}) = \prod_{j=1}^n p_j$.
   • For QR, $(\det(G_n))^{1/2} = \prod_{j=1}^n \rho_j$, where $G_n$ is the Gram matrix of selected columns.

By combining these identities with the approximate pivoting condition, the authors bound the minimum residual over the first $n$ iterations by the geometric mean of the first $n$ singular values (for matrices) or by bounds on the determinant of sampled submatrices (for functions).

Key Contributions and Results

1. Matrix Case (Pivoted QR and LU)
The paper establishes that the error of these algorithms is controlled by the geometric mean of the leading singular values, $\left(\prod_{j=1}^n \sigma_j(A)\right)^{1/n}$.

• Algebraic Decay: If singular values decay algebraically as $\sigma_k(A) = O(k^{-p})$, the residuals for both LU and QR converge at the same algebraic rate $O(k^{-p})$. This contrasts with previous bounds that required exponential decay to guarantee convergence.
• Geometric Decay: If singular values decay geometrically as $\sigma_k(A) = O(\rho^k)$, the residuals converge at the geometric rate $O(\rho^{k/2})$.
• Robustness: These results hold under approximate greedy pivoting, with the error bound scaled only by a multiplicative constant $\gamma^{-1}$.

2. Functional Case (Pivoted LU for Functions)
The analysis is extended to approximating bivariate functions $f(x, y)$ via separable expansions. The algorithm selects pivot points $(x_k, y_k)$ to minimize the residual in the $L^\infty$ norm.

• Regularity-Based Rates: The convergence rates are derived by bounding the determinants of sampled submatrices $[f(x_i, y_j)]$ based on the smoothness of $f$.
  • Hölder/Differentiable Functions: For functions with $q_x$ derivatives in $x$ and $q_y$ in $y$ (with Hölder continuity $\alpha_x, \alpha_y$), the paper derives algebraic convergence rates. Specifically, if $f$ is merely $\alpha_x$-Hölder in one variable with $\alpha_x > 1/2$, convergence is guaranteed. Mixed regularity yields improved rates (e.g., $O(n^{-(2q-1/2)})$ for $q$-times differentiable functions with mixed derivatives).
  • Analytic Functions: For functions analytic in Bernstein ellipses with parameters $\rho_x, \rho_y > 1$, the paper establishes geometric convergence. Under one-sided analyticity, the rate is $O(\rho^{-n/2})$; under joint analyticity, it improves to $O((\rho_x \rho_y)^{-n/2})$. These results hold for any $\rho > 1$, improving upon previous requirements of $\rho > 4$.

Significance and Claims
The paper claims to provide a theoretical explanation for the robust performance of pivoted QR and LU algorithms in regimes where traditional worst-case bounds are uninformative.

• New Theoretical Bounds: The authors state that the LU convergence rates under singular value decay are new. For QR, while similar rates exist in the reduced-basis literature (via Kolmogorov widths), this work provides estimates with smaller explicit constants and linear dependence on the pivot quality $\gamma^{-1}$, rather than quadratic.
• Functional Approximation: The paper presents the first general convergence rate results for pivoted LU applied to functions that do not require assumptions of analyticity or positive definiteness.
• Algorithmic Robustness: A significant finding is that the analysis accommodates approximate greedy pivoting seamlessly. This suggests that heuristic pivot selection strategies (common in practice to reduce computational cost) retain the same convergence rates as exact pivoting, up to a constant factor.

The authors conclude that the dominant cost in these algorithms is often the pivot search, and their results support the use of approximate pivoting strategies without sacrificing convergence rates. Future work is noted to extend these smoothness-based estimates to higher dimensions and broader function classes.