Oblivious Subspace Injection Is Not Enough for Relative Error
This work clarifies the theoretical limitations of OSI for practitioners and theorists relying on relative error guarantees in randomized linear algebra.
The paper shows that oblivious subspace injection (OSI) alone does not guarantee relative error bounds for randomized low-rank approximation and least-squares regression, despite providing constant-factor guarantees. Counterexamples demonstrate failure for sketch-and-solve least squares and randomized SVD in Frobenius norm, but adding upper control on the optimal residual recovers near-relative-error bounds.
Oblivious subspace injection (OSI) was introduced by Camaño, Epperly, Meyer, and Tropp in 2025 as a much weaker sketching property than oblivious subspace embedding (OSE) that still yields constant-factor guarantees for randomized low-rank approximation and sketch-and-solve least-squares regression. At the Simons Institute in Berkeley during a workshop in October 2025, it was asked whether OSIs also imply relative error bounds rather than just constant-factor guarantees. We show that, from a theoretical standpoint, OSI alone does not yield OSE-style relative-error guarantees whose failure probability is controlled solely by the OSI failure parameter, even though OSI sketches often perform extremely well in practice. We provide counterexamples showing this for sketch-and-solve least squares and for randomized SVD in the Frobenius norm. The missing ingredient from a sketch satisfying only OSI is upper control on the optimal residual or tail component, and when one ensures the sketch has this additional property, a near-relative-error bound is recovered. We also show that there is a natural $\ell_p$ analogue of OSI giving constant-factor sketch-and-solve bounds.