A lower-tail proof for pure relative structured matrix learning

We give a self-contained proof that a known $q$-dimensional linear matrix
family can be fitted to an unknown matrix with pure relative Frobenius error
using nonadaptive, two-sided matrix–vector queries. The algorithm measures a
high-leverage left subspace exactly and uses a Gaussian right sketch on its
orthogonal complement. Only a lower bound on the sketched Gram matrix is
required. A second-moment argument and an elementary matrix lower-tail
estimate give a constant-success query bound of order
$\sqrt{q(\log q+1/\varepsilon)}+\log q$, with no additive error and no
dependence on the ratio of the target norm to the optimal residual. A
median-radius selector amplifies confidence for affine families. The
constant-success argument also extends to closed convex subsets of a known
affine family, subject to solving the sketched convex optimization problem.