Linear Systems and Eigenvalue Problems — Problem 34 (Randomized SVD)

Definitions and mathematical statement

For a real matrix $X=(x_{ij})$, its Frobenius norm is $\|X\|_{\mathrm F}=(\sum_{i,j}x_{ij}^{2})^{1/2}$, and $X^{+}$ denotes its Moore--Penrose pseudoinverse.

The supplied formulation takes $A\in{\mathbb{R}}^{n\times d}$, fixes $r>0$, and takes $\Omega\in{\mathbb{R}}^{n\times k}$ described as an "oblivious subspace injection with dimension $r$ and injectivity $1-\varepsilon$." It denotes by $A_r$ a best rank-$r$ approximation to $A$ in Frobenius norm and writes \[ \widetilde A=(A\Omega)(A\Omega)^{+}A. \] The proposed assertion is that every admissible choice necessarily satisfies \[ \|A-\widetilde A\|_{\mathrm F} \leq \left(1+\mathcal O(\varepsilon)\right)\|A-A_r\|_{\mathrm F}. \] The task is to prove or disprove this assertion in the randomized SVD setting.

Unresolved formulation qualifications. With the supplied matrix sizes, $A\Omega$ is undefined unless $d=n$. The source does not impose that equality or specify a correction to either matrix size or the product. The formulas above therefore reproduce the intended question but do not define a mathematical assertion for all supplied dimensions. No definition of "oblivious subspace injection," its dimension parameter, or its injectivity parameter is supplied. In particular, the relevant subspaces, quantifiers, and any randomness or probability of success are unspecified. The condition $r>0$ does not specify an integer rank parameter, its relation to the matrix dimensions, or whether "rank-$r$" means rank exactly $r$ or at most $r$. The range of $\varepsilon$, the asymptotic regime for $\mathcal O(\varepsilon)$, and the permitted dependence and uniformity of its implicit constant are also unspecified. These issues require clarification before a precise quantified conjecture can be stated.

Short English statement

The source asks whether an oblivious subspace injection guarantees that the randomized SVD approximation has Frobenius error within a factor $1+\mathcal O(\varepsilon)$ of the best rank-$r$ error. The supplied dimensions make the matrix product undefined in general, and the injection hypothesis and several quantifiers are missing. This draft preserves the question and records the unresolved qualifications.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $800525$, exact source problem code catalogue entry; title: Linear Systems and Eigenvalue Problems --- Problem 34 (Randomized SVD). The registry attributes the problem to Amsel, Baumann et al., with proposed year 2026, and labels it open. This is a supplied registry status, 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 34. Supplied source URL: https://arxiv.org/abs/2602.05394. The record gives access date 2026-10-16 and extraction method arxiv_latex. These are supplied provenance details; the source and access claim have not been independently verified here. Supplied attribution/context: randomized SVD.