{"id":"arxiv/2604.10215","url":"https://arxiv.org/abs/2604.10215","tags":["math.NA","cs.DS"],"score":0,"title":"Oblivious Subspace Injection Is Not Enough for Relative Error","domain":"math.NA","source":"arxiv","authors":["Alex Townsend","Chris Wang"],"reviews":0,"subject":"math.NA","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-11","reactions":{}}