The maximal gain of nonadaptive randomization

We determine the supremum of the improvement in polynomial convergence rate due to randomization for approximation of bounded linear operators between real Banach spaces using nonadaptive continuous linear measurements. The supremum is one. We construct fixed infinite-dimensional operators whose gains tend to one, with worst-case expected-norm error and at most \(n\) measurements for every random seed. The construction combines a finite-dimensional deterministic lower bound with a known nonadaptive CountSketch estimate and a weighted \(\ell_1\) sum of blocks.