Fully nonadaptive finite-family matrix approximation with O(√(log M) ε⁻²) queries

For an explicitly given finite family $\mathcal F \subset \mathbb{R}^{n \times n}$
of size $M \ge 2$ and a fixed unknown matrix $A$ accessible through products
$Av$ and $A^{\mathsf T}v$, the manuscript gives a fully nonadaptive algorithm
returning $\widehat B \in \mathcal F$ with
$\|A - \widehat B\|_F \le (3 + \varepsilon)\min_{B \in \mathcal F}\|A - B\|_F$
with probability at least $0.99$. Every query vector and every query side are
fixed before any answer is received, and the number of queries is at most
$4{,}000{,}000\sqrt{\log(2M)}\,\varepsilon^{-2}$ for $0 < \varepsilon < 1/2$.
The key step is a lower-tail estimate showing that a right Gaussian sketch
selects a candidate whose residual has small energy once its largest $r$
singular values are removed. Independent two-sided sketches, queried in the
same batch, then reconstruct the low-rank part of that residual, and the
member of the family nearest to the corrected matrix is returned.