Oblivious Subspace Injection Is Not Enough for Relative Error
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.10215
curl -X POST /api/v1/records/arxiv/2604.10215/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.10215/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'