Linear Systems and Eigenvalue Problems — Problem 38 (Rerandomized subsampled trigonometric transforms)

Definitions and mathematical statement

The supplied assertion is: assuming $n=\Omega(\log r)$, prove or disprove that the rerandomized SRHT with output dimension $k=\mathcal O(r/\varepsilon^2)$ is an oblivious subspace embedding with distortion parameters $\alpha=1-\varepsilon$ and $\beta=1+\varepsilon$.

The source record does not define the rerandomized SRHT, the parameter $n$, or the probability required for an oblivious subspace embedding. Consequently, this assertion is not yet a fully specified mathematical proposition.

For clarity, a conditional formulation of the embedding property is as follows. Let $\mathbb K$ be a specified scalar field, either ${\mathbb{R}}$ or ${\mathbb{C}}$, let $d,k,r$ be positive integers with $r\le d$, and let $0<\varepsilon<1$ and $0<\delta<1$. Let $\mathcal D_{d,k,n}$ be a distribution of linear maps $S:\mathbb K^d\to\mathbb K^k$, chosen independently of the subspace to be embedded. With the Euclidean norm and a specified exponent $p\in\{1,2\}$, the relevant property would be \[ \text{for every fixed subspace }V\subseteq\mathbb K^d\text{ with }\dim V=r,\qquad \Pr_{S\sim\mathcal D_{d,k,n}}\!\left[ (1-\varepsilon)\|v\|_2^p\le \|Sv\|_2^p\le(1+\varepsilon)\|v\|_2^p \text{ for every }v\in V \right]\ge 1-\delta. \] Here $p=1$ expresses norm distortion, whereas $p=2$ expresses squared-norm distortion. The supplied record does not select between these conventions. The field, ambient dimension, parameter ranges, and failure probability in this template are explicit placeholders for missing specifications, not additional source hypotheses.

Under the intended specifications, the question asks whether a rerandomized SRHT distribution can satisfy the required embedding property with $k\le C r/\varepsilon^2$ whenever $n\ge c\log r$, in the intended asymptotic regime. The record does not specify that regime, the admissible dependence of the positive constants $c,C$, or any dependence on failure probability. It also does not identify whether $n$ denotes an ambient dimension, a number of randomization steps, or another parameter. These qualifications must be resolved before the conditional formulation can be identified with the intended problem.

Short English statement

Determine whether the rerandomized SRHT achieves an oblivious subspace embedding of dimension $\mathcal O(r/\varepsilon^2)$, with distortion parameters $1-\varepsilon$ and $1+\varepsilon$, assuming $n=\Omega(\log r)$. The transform, the meaning of $n$, the probability guarantee, and the distortion convention require clarification. The registry supplies an open label; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry: permanent ID $800529$, exact source problem code catalogue entry, in the AMR Open Problem Lists collection. Supplied title: Linear Systems and Eigenvalue Problems --- Problem 38 (Rerandomized subsampled trigonometric transforms). The record attributes the problem to Amsel, Baumann et al., with proposed year 2026, and labels it open.
• Supplied source attribution: Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 38. Supplied URL: https://arxiv.org/abs/2602.05394. The recorded access date is 2026-10-16, and the extraction method is arxiv_latex. These are supplied provenance details; the source has not been independently visited or verified for this draft.
• Supplied context: rerandomized subsampled trigonometric transforms. Registry upstream ID: $800529$; supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82. The registry creation and update date is 2026-10-16. No separate literature assessment or definition of the transform is included in the supplied record.