Memory–sample lower bounds for noiseless Gaussian regression

For a signal with density bounded by L relative to uniform probability on S^{d-1}, we bound the information in a finite message W formed from exact Gaussian measurements, conditional on an independent projection revealed only to the analyst. For explicit row counts proportional to d, the bound is O(H(W)/d+d+log(2+log L)). Consequently, a finite-state learner with o(d^2) persistent bits and a deterministic sample horizon needs \Omega(dlog(1/ε)) fresh noiseless Gaussian measurements for constant-probability angular accuracy 0< ε\le1/10 under the uniform spherical prior.

For the image of a uniform cube under a spherical coordinate map, we prove that finite messages from t blocks of Θ(d) exact Gaussian measurements reveal only O_A(dt) information when each message has at most exp(Ad^2) values, for fixed A. The same bound holds when each message is supplemented with a nested cell that restores the required geometric spread.

We prove moment estimates for exact random projections of finite measures whose mass is controlled on Euclidean balls, and derive positive domination by countable sums of spherical cap measures. For learners with M=o(d^2) bits of memory, these estimates give three proofs that uniform-sphere average success at least 2/3 at angular accuracy 0< ε\le1/10 requires \Omega(dlog(1/ε)) noiseless Gaussian observations. The three proofs keep their different stopping and accuracy costs explicit.

Replacing the Gaussian rows used to select a finite message by independent rows increases the remaining conditional information by at most Cd, for a uniform spherical signal, message entropy at most d^(2), and the specified row dimensions proportional to d. As an application, we prove that learners with M=o(d^2) persistent bits need T=\Omega(dlog(1/ε)) exact observations to attain uniform-sphere angular success at least 3/5, for 0< ε\le1/10 and a deterministic finite horizon.

Let a finite-state streaming learner estimate a uniformly random unit vector from independent exact Gaussian linear measurements. We prove that o(d^2) bits of persistent memory and angular success probability at least 2/3 require at least 2^{-16}d\log_2(1/ε) samples for all sufficiently large d, uniformly for 0< ε\le1/10. The proof conditions each batch on its observed projection and controls the resulting random residual subsphere.