Let $\mathcal L\subseteq\mathbb R^{n\times m}$ be any known $q$-dimensional linear matrix family, and let an unknown $A$ be accessible only through products $Ax$ and $A^\top y$. A recent result obtains a nearly optimal approximation from $\mathcal L$ in about $\sqrt q$ queries, but incurs factor three and additive error proportional to $\|A\|_F$. Whether sublinear query complexity can give pure $(1+\epsilon)$ relative error was left open. We resolve this problem with a polynomial-time, nonadaptive algorithm. For a Frobenius-orthonormal basis $B_1,\ldots,B_q$, form the basis-invariant partial trace $S_L=\sum_iB_iB_i^\top$. The algorithm queries the leading eigenspace of $S_L$ exactly from the left, then fits the remaining directions from a Gaussian right sketch. If $\lambda_j$ are the eigenvalues of $S_L$, its constant-success query complexity is $\min_s\left\{s+C\left[ \max\{1,\lambda_{s+1}\}\log^2(2q) +\lambda_{s+1}/\epsilon \right]\right\}.$ The transposed profile is also available. Since $\lambda_{s+1}\le q/(s+1)$, every family admits pure relative error with $\widetilde O(\sqrt{q/\epsilon})$ queries, independent of ambient dimensions and $\|A\|_F/OPT$. The key proof is a partial-trace covariance lemma for a Gaussian matrix-valued design. Exact high-leverage queries make its expected Hessian the identity, while the centered regression offset has variance only $O(\lambda_{s+1}OPT^2/k)$. A median construction amplifies success without estimating residual norms. Finally, a symmetric Wishart lower bound for fixed-sparsity approximation yields $\Omega(\sqrt{q/\epsilon})$ adaptive two-sided queries when $q\epsilon$ is bounded below. Thus the universal rate is optimal up to logarithmic factors in this joint regime. We also show that the transformed profile gives pure relative reducible prediction risk under known input and output covariances. For structured positive-definite precisions, it further controls Gaussian KL error and preconditioned condition number.
Keywords: matrix-vector queries, relative error approximation, structured matrices, query complexity, randomized linear algebra, spectral estimation