Oblivious Subspace Injection Is Not Enough for Relative Error

This paper demonstrates that Oblivious Subspace Injection (OSI), while sufficient for constant-factor guarantees in randomized low-rank approximation and least-squares regression, is theoretically insufficient to ensure relative error bounds without additional control over the optimal residual or tail component.

The Gist

Imagine you are a chef trying to taste a massive pot of soup (a huge dataset) to see if it needs more salt. The pot is so big that tasting the whole thing takes forever. So, you decide to take a small spoonful (a "sketch") to get a quick idea of the flavor.

In the world of math and computers, this is called Randomized Sketching. You want that spoonful to be a perfect representative of the whole pot.

The Old Rule: The "Perfect Mirror" (OSE)

For a long time, mathematicians believed that for your spoonful to be reliable, the spoon itself had to be a perfect mirror. This is called an Oblivious Subspace Embedding (OSE).

• What it means: No matter what direction the soup flows, the spoon preserves the shape and size of the flavor perfectly. If the soup is salty, the spoonful is salty. If it's bland, the spoonful is bland.
• The Catch: Making a "perfect mirror" spoon is very hard and slow, especially if the soup has a weird, complex structure.

The New Idea: The "One-Way Gate" (OSI)

Recently, researchers found a shortcut. They realized you don't need a perfect mirror. You just need a One-Way Gate (called Oblivious Subspace Injection or OSI).

• What it means: The spoon guarantees that the flavor won't disappear. If the soup is salty, the spoonful will definitely taste salty (or stronger). It prevents the flavor from vanishing.
• The Promise: This is much easier to build. It's like using a sieve instead of a mirror. It's fast, cheap, and works great for many tasks. The creators of this idea thought, "Hey, if the flavor doesn't vanish, we can probably get a very accurate result, right?"

The Big Discovery: "Good Enough" isn't "Perfect"

This paper, written by Alex Townsend and Christopher Wang, answers a question asked at a famous math workshop: "Does this 'One-Way Gate' (OSI) guarantee a perfectly accurate result, or just a 'good enough' one?"

Their answer is a definitive: It guarantees "good enough," but not "perfect."

Here is the analogy of why it fails for high-precision tasks:

1. The "Hidden Residue" Problem (Least Squares)

Imagine you are trying to balance a scale. You have a heavy weight (the data) and you want to find the exact counterweight to make it level.

• The OSI Spoon: It guarantees that the heavy weight on the scale won't suddenly turn into a feather. It preserves the existence of the weight.
• The Flaw: The OSI spoon doesn't care if the empty space around the weight gets distorted.
  • Imagine the scale is slightly tilted. The OSI spoon says, "Don't worry, the weight is still there!" But it doesn't notice that the tilt (the error) has been magnified by 100x.
  • Result: You get a solution that is "okay" (within a constant factor), but if you need relative error (meaning "I need the answer to be within 1% of the truth"), the OSI spoon might give you an answer that is 50% off. It fails to control the "tail" or the "leftover" part of the problem.

2. The "Missed Note" Problem (Randomized SVD)

Imagine you are trying to identify the main melody in a symphony orchestra (finding the most important patterns in data).

• The OSI Spoon: It guarantees that if the orchestra plays a loud note, your spoon will hear it.
• The Flaw: The spoon might accidentally ignore the quiet, high-pitched notes that are actually the difference between the melody and the noise.
  • In math terms, the OSI property controls the "main" part of the data but lets the "tail" (the quiet, trailing notes) get distorted wildly.
  • Result: You might identify the main melody, but your reconstruction of the song will sound terrible because the background noise got amplified. You get a "constant factor" approximation (it sounds like music), but not a "relative error" approximation (it doesn't sound like this specific song).

The Solution: Adding One Extra Rule

The paper doesn't say OSI is useless. In fact, the authors show that in real life, OSI often works amazingly well (see the graphs in the paper). It's just that theoretically, it's not strong enough to promise perfection.

However, they found a fix. If you add just one tiny extra rule to the OSI spoon:

"Make sure the spoon also preserves the size of the leftover residue (the part of the soup that didn't fit in the main bowl)."

If you add this one rule, the "One-Way Gate" suddenly becomes powerful enough to give you the perfect, high-precision results you wanted.

Summary for the Everyday Person

• The Goal: Solve huge math problems quickly by taking a small sample.
• The Old Way: Take a sample that is a perfect mirror of the whole. (Hard to do).
• The New Way (OSI): Take a sample that guarantees nothing disappears. (Easy to do, usually works well).
• The Paper's Verdict: The "Easy Way" (OSI) is great for getting a rough answer, but it cannot guarantee a precise answer on its own. It's like a map that shows you the general direction but might be off by a few miles.
• The Fix: If you tweak the map to also show the "leftover details," it becomes precise enough for anything.

In short: Oblivious Subspace Injection is a fantastic, fast tool, but if you need a guarantee that your answer is exactly right (within a tiny margin of error), you need to add a little bit more control to the process.

Technical Summary

1. Problem Statement

The paper addresses a fundamental question in Randomized Numerical Linear Algebra (RandNLA) regarding the strength of Oblivious Subspace Injection (OSI) compared to the classical Oblivious Subspace Embedding (OSE).

• Context: Randomized sketching compresses high-dimensional data ($A \in \mathbb{R}^{n \times d}$) using a random matrix $\Omega$ to solve problems like least-squares regression and low-rank approximation (SVD).
• The Gap: OSE guarantees that the sketch preserves the geometry of all vectors in a subspace (both lower and upper bounds), enabling relative error guarantees (e.g., error $\leq (1+\epsilon) \times$ optimal). Recently, Camaño et al. (2025) introduced OSI, a weaker property requiring only lower bounds (injectivity) and isotropy (expected norm preservation), which suffices for constant-factor guarantees.
• The Open Question: Does OSI alone imply OSE-style relative error bounds (where the approximation factor approaches 1 as parameters improve), or is it strictly limited to constant-factor guarantees? The authors investigate whether the lack of an explicit upper bound in OSI prevents achieving relative error with failure probabilities controlled solely by the OSI parameters.

2. Methodology

The authors employ a combination of theoretical analysis, counterexample construction, and probabilistic bounding:

1. Theoretical Comparison (Section 2): They analyze the relationship between OSI and OSE. They prove that while OSI implies a weak form of OSE, the upper distortion parameter ($\beta$) derived from isotropy is too coarse to yield relative error. They show that in the zero-failure regime, the upper distortion grows linearly with the subspace dimension $s$, making it impossible to achieve near-isometry solely from OSI.
2. Counterexample Construction (Sections 3 & 4):
   • Least Squares: They construct specific matrices $A$ and vectors $b$ where the sketch preserves the range of $A$ (satisfying OSI) but catastrophically distorts the residual direction ($b - Ax^*$). This leads to a constant-factor error even when the injectivity parameter is perfect.
   • Randomized SVD: They construct diagonal matrices where the sketch preserves the dominant singular space but misaligns with the tail singular vectors, causing the approximation error to be separated from the optimum by a fixed constant factor.
3. Positive Results via Augmented Subspaces: They demonstrate that if the injectivity condition is strengthened to hold on augmented subspaces (e.g., $\text{span}(\text{range}(A), b)$ for regression or $\text{span}(\text{dominant space}, \text{tail vector})$ for SVD), relative error bounds can be recovered.
4. $\ell_p$ Extension (Section 5): They generalize the concept to $\ell_p$ regression, defining an OSI$_p$ property (preserving $p$-norms in expectation and lower-bounding them with high probability) and proving it yields constant-factor guarantees.

3. Key Contributions

A. Negative Results: OSI is Insufficient for Relative Error

The paper proves that OSI is theoretically too weak to guarantee relative error for standard sketch-and-solve algorithms:

• Least Squares (Theorem 3.1 & 3.2): Even with an $(1, 1, \rho)$-OSI (perfect injectivity on 1D subspaces), the sketch-and-solve estimator can incur a constant-factor error (e.g., $\sqrt{2}$ times the optimal) with probability $\rho$. Even with zero failure probability ($\rho=0$), a constant-factor loss can occur with probability $\Omega(\epsilon)$.
• Randomized SVD (Theorem 4.1): For a target rank $r=1$, an $(1, 1, 1/2)$-OSI can produce an approximation where the Frobenius error is $\sqrt{2}$ times the optimal error almost surely.
• Mechanism of Failure: The failure arises because OSI controls the lower singular values of the range of $A$ but provides no control over the upper bound of the optimal residual (in regression) or the interaction between dominant and tail singular vectors (in SVD). Isotropy only controls the average behavior, allowing the sketch to concentrate "excess" energy in the critical residual direction.

B. Positive Results: The Missing Ingredient

The authors identify exactly what is needed to recover relative error:

• Augmented Injectivity: Relative error is recovered if the sketch is injective on the augmented subspace $\text{span}(\text{range}(A), b)$ for regression, or on subspaces $\text{span}(V_1, v_j)$ (dominant space + individual tail vectors) for SVD.
• Proposition 3.3 & 4.2: Under these augmented injectivity conditions, combined with isotropy, the authors derive near-relative error bounds of the form:
  $$\text{Error} \leq \left(1 + O\left(\frac{1-\alpha}{\eta}\right)\right) \times \text{Optimal Error}$$
  with probability $1 - \delta - \eta$. This shows that the "missing ingredient" is upper control on the residual/tail, which isotropy provides in expectation once the lower bound is secured on the augmented space.

C. $\ell_p$ Regression Analogue

• Definition 5.1: Introduced OSI$_p$, requiring $p$-isotropy ($E[\|\Omega^T z\|_p^p] = \|z\|_p^p$) and lower-bounded injectivity.
• Theorem 5.2 & Corollary 5.3: Proved that OSI$_p$ guarantees a constant-factor approximation for $\ell_p$ regression. This extends the scope of OSI results beyond Euclidean ($\ell_2$) settings.

4. Results Summary

Setting	Property	Guarantee Type	Failure Probability Control
Least Squares	Standard OSI	Constant Factor	Controlled by $\rho$
Least Squares	Augmented OSI	Relative Error	Controlled by $\rho$ and $\eta$
Randomized SVD	Standard OSI	Constant Factor	Controlled by $\rho$
Randomized SVD	Augmented OSI	Relative Error	Controlled by $\rho$ and $\eta$
$\ell_p$ Regression	OSI$_p$	Constant Factor	Controlled by $\rho$

Note: "Augmented OSI" requires injectivity on a subspace of dimension $d+1$ (for regression) rather than just $d$.

5. Significance and Implications

• Theoretical Clarification: The paper resolves an open problem (Problem 5.1 in [2]) by definitively showing that OSI is strictly weaker than OSE regarding relative error guarantees. It clarifies that the "one-sided" nature of OSI is the bottleneck for relative error.
• Practical vs. Theoretical: The authors note that in practice (Figure 1), OSI-based sketches often perform as well as OSE sketches. The theoretical gap exists because worst-case constructions exploit the lack of upper control, which rarely happens in typical data distributions. However, for rigorous worst-case guarantees, OSE (or augmented OSI) is necessary.
• Guidance for Algorithm Design: The work suggests that for applications requiring strict relative error bounds, one should either:
  1. Use standard OSE sketches (e.g., Gaussian, Subsampled Randomized Hadamard).
  2. If using structured/OSI-friendly sketches, ensure the sketching dimension or construction guarantees injectivity on the augmented subspaces (e.g., including the residual vector in the analysis).
• Foundation for Future Work: By isolating the "upper control on the residual" as the critical missing piece, the paper provides a clear roadmap for analyzing other sketching properties in non-Euclidean norms or structured settings.

In conclusion, while OSI is a powerful tool for obtaining constant-factor approximations efficiently, it is not sufficient to guarantee the high-precision relative error bounds associated with OSE unless additional structural assumptions (injectivity on augmented spaces) are imposed.