Oblivious Subspace Injection Is Not Enough for Relative Error

Alex Townsend, Christopher Wang · 2026

Read Oblivious Subspace Injection Is Not Enough for Relative Error by Alex Townsend, Christopher Wang (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-2604-10215.txt.

Introduction

Townsend and Wang show oblivious subspace injection alone does not guarantee relative-error bounds. It is weaker than embedding yet gives constant bounds for sketch-and-solve least squares. Asked at a 2025 Simons Institute workshop whether it implies error bounds, the team answers no, with counter-cases for least squares and random SVD. Failure chance cannot be set by the injection failure value, though such sketches often perform well. The missing piece is control on the leftover; with that trait, a near bound follows.

Catalog record

CREATORAlex Townsend, Christopher Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56765
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Oblivious Subspace Injection Is Not Enough for Relative Error Thanks: Submitted to the editors August 10, 2026. Alex Townsend, Christopher Wang Abstract 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 ℓ p \ell_{p} analogue of OSI giving constant-factor sketch-and-solve bounds. keywords oblivious subspace injection, randomized numerical linear algebra, least-squares regression, randomized SVD, \ell_{p} regression Funding. The work of A. T. was supported by NSF CAREER (DMS-2045646) and by the Defense Advanced Research Projects Agency (DARPA) through The Right Space (TRS) Disruption Opportunity (DARPA-PA-24-04-07). The work of C. W. was supported by the NSF GRFP under grant DGE-2139899. † † runningheads: Oblivious Subspace Injection Is Not Enough for Relative Error / Townsend and Wang AMS 65F20, 65F25, 65F55 1 Introduction Randomized sketching is a central tool in modern numerical linear algebra for reducing the computational cost of large-scale problems; see, e.g., Mahoney [ 10 ] , Woodruff [ 23 ] , and Martinsson–Tropp [ 11 ] . The basic idea is to compress a high-dimensional dataset into a much smaller representation by multiplying it with a random sketching matrix. If designed appropriately, this compressed representation preserves the essential geometric structure of the original problem, enabling fast approximate solutions with provable guarantees. For a large matrix A\in\mathbb{R}^{n\times d} (with n>d ) and a vector b\in\mathbb{R}^{n} , instead of solving the least squares problem x_{\star}\in\operatorname*{argmin}_{x\in\mathbb{R}^{d}}\left\lVert Ax-b\right\rVert_{2} , one forms a smaller sketched problem. Given a sketch \Omega\in\mathbb{R}^{n\times k} , the sketch-and-solve estimator is \widetilde{x}\in\operatorname*{argmin}_{x\in\mathbb{R}^{d}}\left\lVert\Omega^{\top}(Ax-b)\right\rVert_{2}. Likewise, for low-rank approximation, given A\in\mathbb{R}^{n\times d} , a target rank r , and a sketch \Omega\in\mathbb{R}^{d\times k} with k\geq r , one forms the sample matrix Y=A\Omega and the associated rangefinder approximation \widetilde{A}=(A\Omega)(A\Omega)^{+}A, where + denotes the Moore–Penrose pseudoinverse. The goal in both settings is to replace a large problem by a smaller one while still obtaining a high-quality approximation. The classical theory of sketching is built on the notion of an oblivious subspace embedding (OSE). Fix integers 1\leq s\leq n and k\geq 1 , embedding parameters \alpha\in(0,1] and \beta\geq 1 , and a failure parameter \rho\in[0,1) . A random matrix \Omega\in\mathbb{R}^{n\times k} is an (s,\alpha,\beta,\rho) -OSE if, for every s -dimensional subspace V\subseteq\mathbb{R}^{n} , \mathbb{P}\!\left\{\alpha\left\lVert x\right\rVert_{2}^{2}\leq\left\lVert\Omega^{\top}x\right\rVert_{2}^{2}\leq\beta\left\lVert x\right\rVert_{2}^{2}\quad\text{for all }x\in V\right\}\geq 1-\rho. This property ensures that the sketch preserves the geometry of every low-dimensional subspace of the prescribed dimension. For sketch-and-solve least squares, one applies the OSE with s=\dim\operatorname{span}(\operatorname{range}(A),b)\leq d+1 , while for randomized low-rank approximation with target rank r , one applies it with s=r+1 to the augmented subspaces that arise in the analysis. See Sarlós [ 17 ] , Drineas–Mahoney–Muthukrishnan–Sarlós [ 8 ] , Rokhlin–Tygert [ 16 ] , Clarkson–Woodruff [ 6 ] , and Woodruff [ 23 ] for least squares, and Rokhlin–Szlam–Tygert [ 15 ] , Halko–Martinsson–Tropp [ 9 ] , Martinsson–Tropp [ 11 ] , and Wang–Townsend [ 21 ] for randomized low-rank approximation. The resulting estimates take the form: \left\lVert A\widetilde{x}-b\right\rVert_{2}\leq\sqrt{\frac{\beta}{\alpha}}\left\lVert Ax_{\star}-b\right\rVert_{2},\qquad\|A-\widetilde{A}\|_{F}\leq\sqrt{\frac{\beta}{\alpha}}\left\lVert A-A_{r}\right\rVert_{F}, where A_{r} is the best rank- r approximation to A , and \alpha and \beta are the OSE parameters. In this paper, when we refer to OSE-style relative error, we mean a guarantee in which, when the sketch has near-isometric OSE parameters \alpha=1-O(\varepsilon) , \beta=1+O(\varepsilon) , and failure probability \rho=O(\varepsilon) , the resulting approximation factor is 1+O(\varepsilon) and the overall failure probability is O(\varepsilon) , with both depending only on the sketch parameters. Camaño, Epperly, Meyer, and Tropp recently introduced a much weaker sketching property, called the oblivious subspace injection (OSI) property, and showed that it is sufficient for constant-factor guarantees in sketch-and-solve least squares and low-rank approximation via randomized SVD [ 4 , Theorems 2.2 and 2.7] . In other words, they proved that the sketched solutions were within a constant factor of optimal, but their results do not identify a parameter regime in which that constant approaches 1 . Definition 1 . Fix integers 1\leq s\leq n and k\geq 1 , an injectivity parameter \alpha\in(0,1] , and a failure parameter \rho\in[0,1) . A random matrix \Omega\in\mathbb{R}^{n\times k} is an (s,\alpha,\rho) -OSI if: (i) Isotropy: \mathbb{E}[\Omega\Omega^{\top}]=I_{n} . (ii) Injectivity: for every fixed s -dimensional subspace V\subseteq\mathbb{R}^{n} , \mathbb{P}\!\left\{\left\lVert\Omega^{\top}x\right\rVert_{2}^{2}\geq\alpha\,\left\lVert x\right\rVert_{2}^{2}\text{ for all }x\in V\right\}\geq 1-\rho. Definition 1 is very close to the one in [ 4 ] . The only substantive difference is that we parameterize the failure probability by \rho , whereas their definition fixes the injectivity event to hold with probability at least 19/20 . Thus their (s,\alpha) -OSI is the special case of our (s,\alpha,1/20) -OSI. For historical context, the open-problems note [ 2 , §5.1] points to related one-sided conditions in earlier regression work, notably Drineas–Mahoney–Muthukrishnan–Sarlós [ 8 ] . The OSI property is especially useful for structured random matrices, where the OSE property is difficult to guarantee. The Camaño, Epperly, Meyer, and Tropp paper guarantees the OSI property for several fast sketches, including sparse maps, subsampled randomized trigonometric transforms, and tensor-product constructions [ 4 ] , whereas the previous literature had mostly focused on proving the OSE property with various degrees of success; see Nelson–Nguy \tilde{\hat{\mathrm{e}}} n [ 13 ] , Ailon–Chazelle [ 1 ] , Tropp [ 20 ] , and Pham–Pagh [ 14 ] . More recently, tensor-train sketching has also been analyzed through the OSI lens [ 5 ] . In this paper, we show that OSI is not strong enough to imply OSE-style relative-error guarantees. It turns out that the OSI property is significantly weaker than OSE (see section 2 ), and that weakness is precisely what makes it possible to verify OSI for structured sketches in settings where proving a full OSE may be difficult or out of reach. At the same time, our results show that this added flexibility comes at a price: OSI alone cannot guarantee relative error in the same way that OSE can when the failure probability is required to be controlled only by the OSI parameter. Indeed, we find that relative-error bounds require upper control on the optimal residual in least squares or on the tail component in randomized SVD, whereas OSI provides only lower control on the range of A together with isotropy in expectation. Thus, Camaño, Epperly, Meyer, and Tropp showed that constant-factor guarantees remain available far beyond the classical OSE setting [ 4 ] , while our counterexamples show why there is still a genuine need for OSE-type upper

Read the complete text