Linear Systems and Eigenvalue Problems — Problem 33 (Sketch-and-solve)

Definitions and mathematical statement

Let $A\in{\mathbb{R}}^{n\times d}$ be full rank, let $B\in{\mathbb{R}}^{n\times p}$, and let $\Omega\in{\mathbb{R}}^{n\times k}$. The source requires $\Omega$ to be an "oblivious subspace injection with dimension $d$ and injectivity $1-\varepsilon$." This condition is retained verbatim because the supplied record does not define it. In particular, the sketching map acting on the data is $\Omega^\top:{\mathbb{R}}^n\to{\mathbb{R}}^k$.

For a real matrix $M=(M_{ij})$, define its Frobenius norm by $\|M\|_{\mathrm F}=(\sum_{i,j}|M_{ij}|^2)^{1/2}$, and write $M^+$ for its Moore--Penrose pseudoinverse. Set \[ X=A^+B\in{\mathbb{R}}^{d\times p},\qquad \widetilde X=(\Omega^\top A)^+(\Omega^\top B)\in{\mathbb{R}}^{d\times p}. \] Thus $X$ is an ordinary least-squares solution, and $\widetilde X$ is the sketch-and-solve approximation specified by the source.

Question (source Problem 33). Prove or disprove that, for every choice of matrices satisfying the stated hypotheses, one necessarily has \[ \|A\widetilde X-B\|_{\mathrm F} \leq \left(1+\mathcal O(\varepsilon)\right) \min_{Y\in{\mathbb{R}}^{d\times p}}\|AY-B\|_{\mathrm F}. \] The admissible range of $\varepsilon$, the asymptotic regime and permitted dependencies of the implicit constant, and any probability qualification are unspecified in the supplied record. It also supplies no relation between $n$ and $d$. Consequently, this is a faithful statement of the source question with unresolved qualifications, rather than a fully specified quantified conjecture.

Short English statement

Does sketch-and-solve achieve a Frobenius residual within a factor $1+\mathcal O(\varepsilon)$ of the optimal least-squares residual under the source's stated oblivious subspace injection hypothesis? The meaning of that hypothesis, the probabilistic guarantee, and the uniformity of the error factor require clarification.

Sources

• Local UnsolvedMath registry, permanent ID $800524$, source code catalogue entry, title "Linear Systems and Eigenvalue Problems --- Problem 33 (Sketch-and-solve)." The supplied registry labels the problem open; this label is not an independently verified mathematical or literature assessment.
• Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 33. Supplied source URL: https://arxiv.org/abs/2602.05394. The registry attributes the problem to Amsel, Baumann et al., with proposed year 2026 and attribution/context "Sketch-and-solve."
• Supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. This access date is source metadata; no independent source visit or verification is claimed. The supplied upstream revision is d371ee917ac9647fbb06cd6fc529deec6f3dda82.