64c3814
==== TABLE OF CONTENTS ====
Replacing-Gaussian-observations-in-memory-constrained-inference//main.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//preamble.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//references.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/00-introduction.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/01-information-and-densities.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/02-mixed-moments.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/03-critical-radius.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/04-density-levels.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/05-hybrids.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/06-fiber.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07-streaming-applications.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07a-density-endpoints.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07b-hybrid-endpoint.tex
Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07c-fiber-endpoint.tex
===========================
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//main.tex ====
\documentclass[11pt]{article}
\input{preamble}
\hypersetup{
pdftitle={Replacing Gaussian observations in memory-constrained inference},
pdfauthor={OpenAI},
pdfsubject={Information comparisons for actual and fresh Gaussian observations}
}
\title{Replacing Gaussian observations in memory-constrained inference}
\author{OpenAI}
\date{September 27, 2026}
\begin{document}
\maketitle
\begin{abstract}
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(d\log(1/\epsilon))\) exact observations to attain
uniform-sphere angular success at least \(3/5\), for
\(0<\epsilon\le1/10\) and a deterministic finite horizon.
\end{abstract}
\setcounter{tocdepth}{1}
\tableofcontents
\clearpage
\input{sections/00-introduction}
\input{sections/01-information-and-densities}
\input{sections/02-mixed-moments}
\input{sections/03-critical-radius}
\input{sections/04-density-levels}
\input{sections/05-hybrids}
\input{sections/06-fiber}
\input{sections/07-streaming-applications}
\input{references}
\end{document}
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//main.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//preamble.tex ====
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\pdfgentounicode=1
\pdfglyphtounicode{tfm:lmsy10/mapsto}{007C}
\pdfglyphtounicode{tfm:lmex10/parenleftbig}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightbig}{0029}
\pdfglyphtounicode{tfm:lmex10/bracketleftbig}{005B}
\pdfglyphtounicode{tfm:lmex10/bracketrightbig}{005D}
\pdfglyphtounicode{tfm:lmex10/vextendsingle}{23D0}
\pdfglyphtounicode{tfm:lmex10/parenleftbigg}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightbigg}{0029}
\pdfglyphtounicode{tfm:lmex10/bracketleftbigg}{005B}
\pdfglyphtounicode{tfm:lmex10/bracketrightbigg}{005D}
\pdfglyphtounicode{tfm:lmex10/ceilingleftbigg}{2308}
\pdfglyphtounicode{tfm:lmex10/ceilingrightbigg}{2309}
\pdfglyphtounicode{tfm:lmex10/parenleftBigg}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightBigg}{0029}
\pdfglyphtounicode{tfm:lmex10/bracelefttp}{23A7}
\pdfglyphtounicode{tfm:lmex10/braceleftbt}{23A9}
\pdfglyphtounicode{tfm:lmex10/braceleftmid}{23A8}
\pdfglyphtounicode{tfm:lmex10/braceex}{23AA}
\pdfglyphtounicode{tfm:lmex10/summationtext}{2211}
\pdfglyphtounicode{tfm:lmex10/producttext}{220F}
\pdfglyphtounicode{tfm:lmex10/integraltext}{222B}
\pdfglyphtounicode{tfm:lmex10/summationdisplay}{2211}
\pdfglyphtounicode{tfm:lmex10/productdisplay}{220F}
\pdfglyphtounicode{tfm:lmex10/integraldisplay}{222B}
\pdfglyphtounicode{tfm:lmex10/hatwide}{02C6}
\pdfglyphtounicode{tfm:lmex10/tildewide}{02DC}
\pdfglyphtounicode{tfm:lmex10/bracketleftBig}{005B}
\pdfglyphtounicode{tfm:lmex10/bracketrightBig}{005D}
\pdfglyphtounicode{tfm:lmex10/radicalBig}{221A}
\pdfglyphtounicode{tfm:msbm10/hatwide}{02C6}
\pdfglyphtounicode{tfm:msbm7/hatwide}{02C6}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{needspace}
\usepackage{enumitem,booktabs}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage[nameinlink,noabbrev]{cleveref}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\R}{\mathbb R}
\newcommand{\E}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\newcommand{\ind}{\mathbf 1}
\newcommand{\norm}[1]{\left\lVert #1\right\rVert}
\newcommand{\ip}[2]{\langle #1,#2\rangle}
\newcommand{\dist}{\operatorname{dist}}
\newcommand{\supp}{\operatorname{supp}}
\newcommand{\aff}{\operatorname{aff}}
\newcommand{\op}{\mathrm{op}}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\Gram}{Gram}
\DeclareMathOperator{\Ent}{Ent}
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//preamble.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//references.tex ====
\begin{thebibliography}{99}
\bibitem{Austin2020}
Tim Austin.
\newblock Multi-variate correlation and mixtures of product measures.
\newblock \emph{Kybernetika}, 56(3):459--499, 2020.
\newblock \href{https://doi.org/10.14736/kyb-2020-3-0459}{doi:10.14736/kyb-2020-3-0459}.
\bibitem{DKS2019}
Yuval Dagan, Gil Kur, and Ohad Shamir.
\newblock Space lower bounds for linear prediction in the streaming model.
\newblock In \emph{Proceedings of the Thirty-Second Conference on Learning Theory},
Proceedings of Machine Learning Research 99, pages 929--954, 2019.
\newblock \url{https://proceedings.mlr.press/v99/dagan19b.html}.
Theorem 3 and Theorem 10 locators refer to this published PMLR version.
\bibitem{DupuisMao2022}
Paul Dupuis and Yixiang Mao.
\newblock Formulation and properties of a divergence used to compare
probability measures without absolute continuity.
\newblock \emph{ESAIM: Control, Optimisation and Calculus of Variations},
28, Article 10, 2022.
\newblock \href{https://doi.org/10.1051/cocv/2022002}{doi:10.1051/cocv/2022002}.
\bibitem{Mattila1975}
Pertti Mattila.
\newblock Hausdorff dimension, orthogonal projections and intersections with planes.
\newblock \emph{Annales Academiae Scientiarum Fennicae, Series A I, Mathematica},
1(2):227--244, 1975.
\newblock \href{https://doi.org/10.5186/aasfm.1975.0110}{doi:10.5186/aasfm.1975.0110}.
\bibitem{OpenAILocalization2026}
OpenAI.
\newblock Localization costs and information growth for exact Gaussian observations.
\newblock OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Localization-costs-and-information-growth-for-exact-Gaussian-observations-September-27-2026/paper.pdf}{OAI:Localization-costs-and-information-growth-for-exact-Gaussian-observations-September-27-2026}, 2026.
\bibitem{Raz2016}
Ran Raz.
\newblock Fast learning requires good memory: A time-space lower bound for parity learning.
\newblock arXiv:1602.05161v1, 16 February 2016.
\newblock \url{https://arxiv.org/abs/1602.05161v1}.
\bibitem{Raz2017}
Ran Raz.
\newblock A time-space lower bound for a large class of learning problems.
\newblock In \emph{Proceedings of the 58th Annual IEEE Symposium on Foundations
of Computer Science}, pages 732--742, 2017.
\newblock \href{https://doi.org/10.1109/FOCS.2017.73}{doi:10.1109/FOCS.2017.73}.
Theorem and section locators refer to ECCC Report TR17-020, 12 February 2017:
\url{https://eccc.weizmann.ac.il/report/2017/020/}.
\bibitem{RussoZou2016}
Daniel Russo and James Zou.
\newblock Controlling bias in adaptive data analysis using information theory.
\newblock In \emph{Proceedings of the 19th International Conference on Artificial
Intelligence and Statistics}, Proceedings of Machine Learning Research 51,
pages 1232--1240, 2016.
\newblock \url{https://proceedings.mlr.press/v51/russo16.html}.
\bibitem{SSV2019}
Vatsal Sharan, Aaron Sidford, and Gregory Valiant.
\newblock Memory-sample tradeoffs for linear regression with small error.
\newblock In \emph{Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing}, pages 890--901, 2019.
\newblock \href{https://doi.org/10.1145/3313276.3316403}{doi:10.1145/3313276.3316403}.
Theorem and section locators refer to the full version
arXiv:1904.08544v2, 10 October 2020:
\url{https://arxiv.org/abs/1904.08544v2}.
\bibitem{SteinhardtDuchi2015}
Jacob Steinhardt and John Duchi.
\newblock Minimax rates for memory-bounded sparse linear regression.
\newblock In \emph{Proceedings of the 28th Conference on Learning Theory},
Proceedings of Machine Learning Research 40, pages 1564--1587, 2015.
\newblock \url{https://proceedings.mlr.press/v40/Steinhardt15.html}.
\bibitem{vanErvenHarremoes2014}
Tim van Erven and Peter Harremo\"es.
\newblock R\'enyi divergence and Kullback--Leibler divergence.
\newblock arXiv:1206.2459v2, 24 April 2014.
\newblock \url{https://arxiv.org/abs/1206.2459v2}.
Theorem and equation locators refer to this version.
\bibitem{XuRaginsky2017}
Aolin Xu and Maxim Raginsky.
\newblock Information-theoretic analysis of generalization capability of learning algorithms.
\newblock In \emph{Advances in Neural Information Processing Systems} 30,
pages 2524--2533, 2017.
\newblock \url{https://papers.nips.cc/paper_files/paper/2017/hash/ad71c82b22f4f65b9398f76d8be4c615-Abstract.html}.
\end{thebibliography}
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//references.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/00-introduction.tex ====
\section{Introduction}\label{sec:r-introduction}
A finite message chosen from data changes the conditional distribution
of those data. This elementary fact becomes a central issue in
memory-constrained inference. Suppose a signal \(S\) is observed
through exact Gaussian equations and a learner retains a finite state
\(W\). After conditioning on \(W\), the rows used to select that
state are generally biased. An independent Gaussian matrix has the
same unconditional row law, but it need not leave the same information
about \(S\) once its labels are revealed.
This paper quantifies that change. We compare information beyond a
wholly independent auxiliary projection with information beyond a
projection containing the actual rows used by the learner. The two
experiments keep the signal--message marginal and the signal--matrix
marginal fixed. Their full joint laws differ. At suitable row
dimensions proportional to \(d\), the comparison cost is \(O(d)\)
when the message entropy is at most \(d^2\). We also prove the
projection moment that makes this possible and develop two further
comparisons based on replacing one row at a time and on a
two-signal fiber measure.
Here is one precise comparison. Write \(H\) for discrete entropy
in nats, \(h\) for differential entropy, and
\(I(\cdot;\cdot\mid\cdot)\) for conditional mutual
information. Let \(S\) be uniform on \(S^{d-1}\), put
\(m=\lfloor d/10\rfloor\) and \(\ell=\lfloor d/2\rfloor\), and
let \(A\) be an \(m\)-row standard Gaussian matrix independent of
\(S\). A countable message \(W\) may have arbitrary joint
dependence on \((S,A)\), subject to \(H(W)\le d^2\).
Draw an \((\ell-m)\)-row Gaussian matrix \(C\) independently of
\((S,A,W)\), and an \(\ell\)-row Gaussian matrix \(G\) independently of
\((S,W)\). Theorem~\ref{thm:r-critical-comparison} proves
\[
I(S;W\mid G,GS)
\le I(S;W\mid A,C,AS,CS)+Kd
\]
for all sufficiently large \(d\), with an absolute threshold and
an absolute constant \(K\). Thus replacing rows that helped select
the message by fresh rows costs only \(O(d)\) additional conditional
information, despite the possible bias of \(A\) given \(W\).
\subsection*{Memory, exact equations, and prior methods}
Memory restrictions affect statistical estimation even when
computation is unrestricted. Steinhardt and Duchi established
memory-dependent minimax bounds for sparse noisy regression
\cite{SteinhardtDuchi2015}. Raz's branching-program lower bounds
for parity learning and broader discrete learning tasks showed how
finite width can force a large sample cost \cite{Raz2016,Raz2017}.
Sharan, Sidford, and Valiant developed a closely related finite-state
framework for continuous regression \cite{SSV2019}.
Their precision theorem uses isotropic Gaussian covariates with
independent uniform additive noise of half-width \(2^{-d/5}\).
For Euclidean accuracy \(d^{-r}\), with \(r\le O(d/\log d)\),
at most \(d^2/4\) bits of memory, and success probability at least
\(2/3\), it gives an \(\Omega(d\log r)\) sample lower bound
\cite[Theorem~1]{SSV2019}. The present observation law has exact
labels, which contain more information than noisy labels.
Accordingly, our proof needs an estimate for exact projection
densities. Sharan, Sidford, and Valiant's expansion of a projection
moment into independent signal copies is a direct method precedent
\cite[Section~7, Lemma~12]{SSV2019}; their one-row interval estimate
uses a positive noise scale and global \(L^2\) control, while the
mixed multirow estimate below is proved from local mass bounds.
Dagan, Kur, and Shamir give related space lower bounds for an
approximate-nullvector task with independent Gaussian rows and for
empirical regression on a randomly ordered finite data set with
exactly consistent labels \cite[Theorems~3 and~10]{DKS2019}.
The latter result bounds the empirical residual under a hard joint
data distribution; our recovery problem uses independent Gaussian
rows and a fixed signal.
Information-theoretic analyses of adaptive selection also compare a
selected statistic with an independent reference. Russo and Zou
bound the divergence between a selected statistic on the observed
data and its evaluation on an independent copy by the information
used for selection \cite[Section~2.4, Proposition~4]{RussoZou2016}.
Xu and Raginsky bound an expectation difference between a joint law
and the product of its marginals for a test that is sub-Gaussian
under the product law
\cite[Section~3.1, Lemma~1]{XuRaginsky2017}. These comparisons
explain the role of an information charge for selection. Here the
test is an exact projection density, and a locally proved \(q\)th
moment makes the row-information charge appear with coefficient
\(1/q\).
The geometric calculation also belongs to the tradition of
controlling projection energies by inverse distances. Mattila's
two-point averaging estimate gives a classical instance of that
principle \cite[proof of Lemma~5.1, p.~236]{Mattila1975}. Our mixed moment
contains both inverse lengths and inverse distances to the span of
earlier signal differences. The specific Gaussian factors,
dimension conditions, and finite fiber normalization are proved in
this paper.
\subsection*{The streaming model and the application}
The comparison theorems concern finite messages with arbitrary
dependence on a signal and some Gaussian rows. Their streaming
application uses the following model.
\begin{definition}[Finite persistent-state learner]
\label{def:r-streaming-model}
Fix \(d\ge2\), an integer memory bound \(M\ge0\), an angular
accuracy \(0<\epsilon\le1/10\), and a deterministic finite integer
horizon \(T\ge0\). The signal is a unit vector. It may be fixed
before sampling, or sampled from a specified prior; the
average-case statements in this paper use uniform probability on
\(S^{d-1}\). Pre-generate independent
\[
X_t\sim N(0,I_d),\qquad Y_t=\langle X_t,S\rangle,\qquad t\ge1.
\]
The row sequence is independent of \(S\).
Let \(\Xi\) be a shared rule seed, constant if no shared seed is
used, and let \(U_0\) be the initial finite state. The pair
\((\Xi,U_0)\) is jointly independent of
\((S,(X_t)_{t\ge1})\); \(\Xi\) and \(U_0\) may depend on one
another. The original randomized experiment is jointly measurable
in the signal, the complete row sequence, the shared seed,
initialization, and all transition and output randomness. All
variables and kernels are taken on standard Borel spaces, with the
completed-measurability convention below for sample arguments.
At every index, including index zero, the persistent state has at most \(2^M\)
possible values. Conditional on \(\Xi\), the rule at time \(t\)
uses only the current state, the index \(t\), and the entire current
pair \((X_t,Y_t)\), together with fresh randomness that has no
additional signal or sample information. The rule may perform
unrestricted computation on that pair, but everything retained for
later samples must be encoded in the new finite state. The learner
receives the rows once in their prescribed order and cannot choose a
row or revisit an earlier one.
The learner stops at an index \(\tau\in\{0,\ldots,T\}\). Conditional
on the fixed seed, its unit-vector output \(\widehat S\) is drawn
from a kernel depending only on the terminal state and \(\tau\),
using fresh output randomness. In particular the last observed pair
can affect the output only through that terminal state. The seed
may select nonuniform rules depending on \(d,\epsilon,t\), but it
has no data-dependent content.
Before the first sample, a stopping choice may use only the seed,
the initial state, and fresh randomness.
For each fixed seed, state, and index, the transition and stopping
probabilities may be Borel functions of the sample pair, or
measurable in the completion of Gaussian row measure times Lebesgue
label measure. This per-seed convention supplements the required
joint measurability of the original mixed experiment; it does not
replace it. Success means
\(\arccos\langle\widehat S,S\rangle\le\epsilon\).
\end{definition}
The joint condition on \((\Xi,U_0)\) ensures that fixing the rule
seed leaves initialization data-independent. We record this
reduction because the information potentials start from the
conditional initial-state law.
\Needspace{6\baselineskip}
\begin{lemma}[Fixing the shared rule seed]\label{lem:r-seed-reduction}
In the model above, for almost every seed value \(\xi\),
\begin{equation}\label{eq:r-seed-factorization}
\mathcal L\bigl(S,(X_t)_{t\ge1},U_0\mid\Xi=\xi\bigr)
=\mathcal L\bigl(S,(X_t)_{t\ge1}\bigr)
\otimes\mathcal L(U_0\mid\Xi=\xi).
\end{equation}
If the original uniform-prior success probability is at least
\(p_0\), one may choose such a seed value whose conditional
uniform-prior success is at least \(p_0\), with the same state
bound and horizon. This assertion is about the uniform-prior
experiment.
\end{lemma}
\begin{proof}
Disintegrate the joint independence of
\((\Xi,U_0)\) and \((S,(X_t)_{t\ge1})\) over \(\Xi\).
It gives \eqref{eq:r-seed-factorization} for almost every seed.
Joint measurability of the original experiment makes its conditional
success probability a measurable function of \(\xi\), whose mean
is the original success probability. Averaging therefore supplies
a seed with the stated success and factorization. The conditional
initial-state law is retained. A later Borel replacement is
performed separately in this fixed-seed experiment; no jointly
measurable selection of replacement versions is required.
\end{proof}
The critical-radius comparison gives the following streaming
consequence: for \(M(d)=o(d^2)\), every accuracy sequence
\(0<\epsilon(d)\le1/10\), and uniform-sphere average success at
least \(3/5\), the deterministic horizon must satisfy
\[
T(d)=\Omega\!\left(d\log\frac1{\epsilon(d)}\right).
\]
The lower-bound constant is absolute; the eventual dimension
threshold may depend on the memory sequence. Section~\ref{sec:r-streaming}
proves this statement and records the distinct constants and
thresholds arising from the other comparisons. A learner that
succeeds with probability at least \(2/3\) for every fixed signal
also has that success under the uniform prior, so the worst-signal
consequence follows separately. The auxiliary projections used in
the proof are analysis variables; the learner receives only the
exact stream in Definition~\ref{def:r-streaming-model}.
\subsection*{How the comparisons work}
Section~\ref{sec:r-experiments} defines the aligned and independent
experiments explicitly. Their information difference contains a
negative conditional row-information term. Data processing
compares that term with the divergence between the actual
conditional label law and the projection of the posterior
\(P_{S\mid W}\). What remains is the entropy of the independent
projection plus an aligned log density.
Section~\ref{sec:r-mixed-moments} proves the analytic estimate for
that density. In a \(q\)th moment, the actual rows are shared by
all \(q\) factors while independent auxiliary rows are averaged
separately in each factor. Gaussian integration produces inverse
lengths and the inverse Gram determinant of the signal differences.
A local mass bound controls thin tubes around their successive
spans, and a second bound controls the sum over small radial scales.
The section treats exact density versions and the order of the
change of row law and limiting operation.
Sections~\ref{sec:r-critical-radius} and
\ref{sec:r-density-levels} use this estimate after refining a
posterior by its local mass. The critical-radius refinement records
both a radius and its logarithmic mass level. Two further
comparisons use a single maximal level or a pair of density labels.
Their entropy costs are explicit, and the density-level terms
cancel with opposite signs. The two-label argument also retains
its own Gaussian-mollifier and first-density passage.
These comparisons have different scopes. The critical-radius result
allows countable messages and \(\lfloor d/10\rfloor\) actual rows.
The two-label result treats finite messages with the larger actual
block \(\lfloor d/8\rfloor\); its Gaussian-mollifier density version
supports an estimate at every fixed target. The one-level result
uses only one refinement label, a net-weight entropy estimate, and
\(\lfloor d/32\rfloor\) actual rows. It keeps the entropy-dependent
comparison cost explicit rather than imposing \(H(W)\le d^2\)
in its statement.
The last two comparisons use different geometric objects.
Section~\ref{sec:r-hybrids} keeps the actual ending state fixed
while replacing an actual prefix of rows by an independent suffix,
one row at a time. Independent random kernels and a normalized
reciprocal-distance selection control the successive changes.
Section~\ref{sec:r-fiber} constructs a finite measure on pairs
having the same Gaussian label. It proves that measure's exact
kernel and normalizes the reference before applying probability
data processing. Local-mass ratios then bound the resulting
information difference.
The hybrid argument averages over the number of auxiliary observations,
whereas the fiber comparison concerns a state transition through an
actual block, rather than an arbitrary message jointly distributed
with its rows. These scopes explain the separate applications below.
Finally, Section~\ref{sec:r-streaming} applies these comparisons
to successive fresh blocks. It includes a local Borel-version
reduction for the fixed-seed uniform-prior experiment, the state
and stopping-index costs, and the residual-sphere information
required by an accurate output. A separate memory-unrestricted
sample bound absorbs the final-block rounding cost. This separates the
analytic comparisons from the bookkeeping needed to apply them
to a learner.
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/00-introduction.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/01-information-and-densities.tex ====
\section{The two experiments and their information difference}
\label{sec:r-experiments}
The comparison begins with two experiments that give the signal and
the finite message the same joint distribution. They differ in the
rows revealed alongside that message. Before defining them, we fix
the measure and entropy conventions needed to interpret their exact
labels.
Write \(\sigma\) for uniform probability on \(S^{d-1}\), put \(n=d-1\),
and let \(B(z,t)\) be the closed Euclidean ball with center \(z\) and
radius \(t\). The notation \(\gamma_a\) denotes the law of an
\(a\times d\) matrix with independent \(N(0,1)\) entries. All
logarithms are natural. Constants denoted by \(C\) are positive and
absolute and may increase between occurrences.
\begin{lemma}[Spherical caps and ambient balls]\label{lem:r-caps}
On the unit sphere in \(\R^a\), \(a\ge2\), a cap of angular radius
\(0\le\theta\le\pi\) has uniform probability at most
\(\theta^{a-1}\). On \(S^{d-1}\),
\[
\sigma(B(s,t))\le t^n\quad(s\in S^{d-1}),\qquad
\sigma(B(z,t))\le(2t)^n\quad(z\in\R^d),\qquad t>0.
\]
Consequently a fixed unit-vector output, or a random unit-vector
output independent of the signal, succeeds to angular error
\(\epsilon\) on a set of \(\sigma\)-mass at most \(\epsilon^n\).
\end{lemma}
\begin{proof}
The cap probability is the ratio of the integrals of
\(\sin^{a-2}u\) over \([0,\theta]\) and \([0,\pi]\). The numerator
is at most \(\theta^{a-1}/(a-1)\). Symmetry and
\(\sin u\ge2u/\pi\) on \([0,\pi/2]\) bound the denominator below by
\(\pi/(a-1)\), proving the angular estimate.
For the centered Euclidean estimate it suffices to consider \(t\le1\).
Rotate \(s\) to the north pole. Points in \(B(s,t)\) have last
coordinate at least \(1-t^2/2\ge1/2\). As a graph above the first
\(n\) coordinates, this part of the sphere has area element at most
twice Lebesgue measure and projects into the \(n\)-ball of radius
\(t\). The entire sphere has area at least twice the volume of the
unit \(n\)-ball, by projecting the two hemispheres. Their ratio is
at most \(t^n\). For \(t>1\), total mass one suffices. An ambient
ball meeting the sphere is contained, on the sphere, in the ball of
radius \(2t\) about any one point of that intersection. This gives
the second bound. Finally, angular error at most \(\epsilon\)
implies Euclidean error at most \(\epsilon\), since
\(2\sin(\theta/2)\le\theta\). Integrating the centered bound over
an independent output law proves the last assertion.
\end{proof}
For probability measures \(P,Q\), relative entropy means
\[
D(P\Vert Q)=
\begin{cases}
\displaystyle\int\log\frac{dP}{dQ}\,dP,&P\ll Q,\\
+\infty,&\text{otherwise}.
\end{cases}
\]
For a countable discrete variable \(W\), \(H(W)\) is its Shannon
entropy in nats. Mutual information and conditional mutual
information are the corresponding relative entropies of a joint law
from the product of its marginals, conditionally when appropriate.
We use regular conditional laws on standard Borel spaces. The
conditional chain rule and average conditional relative-entropy
formulas used here are given by Austin
\cite[Lemma~3.6 and Equations~(13)--(18)]{Austin2020}.
For probability data processing under a measurable map or a common
Markov kernel, see van Erven and Harremo\"es
\cite[Theorems~5 and~9; Example~2]{vanErvenHarremoes2014}.
Our finite-reference comparisons use the following precise
normalization.
\begin{lemma}[A finite reference measure]\label{lem:r-finite-reference}
Let \(P\) be a probability measure and let \(Q\) be a finite
nonzero measure on the same measurable space. Put \(c=Q(\Omega)\)
and \(\overline Q=Q/c\). When \(P\ll Q\), define
\[
D_{\mathrm{fin}}(P\Vert Q)=\int\log\frac{dP}{dQ}\,dP.
\]
This extended quantity is bounded below by \(-\log c\) and satisfies
\[
D_{\mathrm{fin}}(P\Vert Q)
=D(P\Vert\overline Q)-\log c.
\]
If \(T\) is measurable, then
\[
D_{\mathrm{fin}}(T_\#P\Vert T_\#Q)
\le D_{\mathrm{fin}}(P\Vert Q).
\]
\end{lemma}
\begin{proof}
The density identity \(dP/dQ=c^{-1}dP/d\overline Q\) gives the
displayed equality and lower bound. Both \(Q\) and \(T_\#Q\) have
mass \(c\), and \(\overline{T_\#Q}=T_\#\overline Q\).
Probability data processing applied to \((P,\overline Q)\), followed
by subtracting the same \(\log c\) from both sides, proves the claim.
For completeness, probability data processing follows from the
identity
\[
\frac{dT_\#P}{dT_\#\overline Q}(T)
=\E_{\overline Q}\left[\frac{dP}{d\overline Q}\,\middle|\,T\right]
\]
and conditional Jensen for \(x\log x\). Thus the finite comparison
uses a normalized probability reference before the inequality is
applied.
\end{proof}
We will also use the entropy variational inequality. If \(P\ll Q\)
are probabilities and \(f\) is bounded and measurable, then
\begin{equation}\label{eq:r-entropy-variational}
\E_P f\le D(P\Vert Q)+\log\E_Q e^f.
\end{equation}
Indeed, normalize \(e^fQ\) to a probability measure and expand the
nonnegative relative entropy from \(P\) to that measure. Truncation
gives the same statement for nonnegative \(f\) whenever
\(\E_Qe^f<\infty\), and for integrable \(f\) with a finite
exponential moment. This is the standard variational relation
between entropy and exponential moments; see
Dupuis and Mao \cite[Equations~(1.1)--(1.2), pp.~1--2]{DupuisMao2022}.
\subsection{Density versions for exact labels}
\label{subsec:r-densities}
A Gaussian block maps a spherical signal into Euclidean label space.
The next lemma specifies a common measurable density version and the
integrability that permits subsequent entropy subtractions. Its
first-moment argument is also a separate route from cube averages to
the exact density.
\begin{lemma}[Projection densities and logarithmic integrability]
\label{lem:r-projection-density}
Let \(1\le\ell<n\). If \(\rho\) is a finite measure with
\(\rho\ll\sigma\), then the image \(g_\#\rho\) of \(\rho\) under
every full-row-rank \(g\in\R^{\ell\times d}\) has a Lebesgue density.
For \(\delta>0\), put
\[
p_{\rho,\delta}(g,y)
=(2\delta)^{-\ell}\int
\ind_{\{\norm{gu-y}_\infty\le\delta\}}\,d\rho(u).
\]
A jointly Borel density version is
\begin{equation}\label{eq:r-density-version}
p_\rho(g,y)=\lim_{j\to\infty}p_{\rho,1/j}(g,y)
\end{equation}
where the limit exists and is finite, and zero otherwise.
Suppose now that \(\nu\) is a probability measure with
\(\nu\le H\sigma\), \(H<\infty\), and \(G\sim\gamma_\ell\) is
independent of \(S\sim\nu\). Then \(\log p_\nu(G,GS)\) is
integrable. In addition,
\begin{equation}\label{eq:r-first-density-moment}
\sup_{\delta>0}\E p_{\nu,\delta}(G,GS)
\le(2\pi)^{-\ell/2}
\iint\norm{u-s}^{-\ell}\,d\nu(u)d\nu(s)<\infty,
\end{equation}
and the same upper bound holds for \(\E p_\nu(G,GS)\).
Finally, let a countable \(W\) with \(H(W)<\infty\) have any joint
law with \((S,G)\) that leaves the latter's product marginal
unchanged. For each positive-probability \(w\), put
\(\nu_w=P_{S\mid W=w}\). The actual conditional law of \(GS\)
given \((G,W)\) has a Lebesgue density. The logarithm of that
density and \(\log p_{\nu_W}(G,GS)\) are both integrable under the
actual law.
\end{lemma}
\begin{proof}
The first \(\ell\) coordinates of a uniform spherical point have
density
\[
\frac{\Gamma(d/2)}
{\pi^{\ell/2}\Gamma((d-\ell)/2)}
(1-\norm{y}^2)^{(d-\ell-2)/2}
\ind_{\{\norm{y}<1\}}.
\]
To see the normalization, write the point as a standard Gaussian
vector divided by its length. Its projected squared length has the
\(\operatorname{Beta}(\ell/2,(d-\ell)/2)\) law and its projected
direction is uniform. Polar coordinates give the displayed
density. An orthogonal change of coordinates followed by the
invertible map \((gg^{\mathsf T})^{1/2}\) gives the density for
\(g_\#\sigma\), with Jacobian
\(\det(gg^{\mathsf T})^{-1/2}\). Absolute continuity gives a
density for \(g_\#\rho\). Each cube average is Borel in \((g,y)\)
by integration of a Borel indicator. Lebesgue differentiation
shows that \eqref{eq:r-density-version} is a density version for
each full-rank \(g\); the specified limit is jointly Borel.
We first verify logarithmic integrability from this explicit
spherical density. Under the product law \(\gamma_\ell\otimes\sigma\),
the logarithm of the residual squared radius is integrable by the
beta law. Gram--Schmidt expresses \(\det(GG^{\mathsf T})\) as a
product of chi-square variables with positive degrees of freedom,
whose logarithms have finite absolute means. Hence
\(\log p_\sigma(G,GS)\) is integrable. Domination by \(H\)
preserves this integrability under \(\gamma_\ell\otimes\nu\).
For every full-rank \(g\), data processing gives
\[
D(g_\#\nu\Vert g_\#\sigma)\le D(\nu\Vert\sigma)\le\log H.
\]
The negative logarithmic part of any probability density ratio
\(a/b\), integrated under \(a\), is at most \(1/e\), because
\(t\log^-(t)\le1/e\). Its positive part is therefore finite when
the relative entropy is finite. Apply this to \(p_\nu/p_\sigma\)
and add the integrable baseline logarithm.
Here is a direct proof that retains the first density moment in
\eqref{eq:r-first-density-moment}. For distinct \(u,s\), the
\(\ell\) coordinates of \(G(u-s)\) are independent centered
normals with variance \(\norm{u-s}^2\). Their joint density is
at most \((2\pi)^{-\ell/2}\norm{u-s}^{-\ell}\). The cube volume
is \((2\delta)^\ell\). Multiplying these quantities and applying
Tonelli proves the first inequality in
\eqref{eq:r-first-density-moment}; the diagonal is null since
\(\nu\le H\sigma\) is nonatomic. For each \(s\in S^{d-1}\),
Lemma~\ref{lem:r-caps} and dyadic shells give
\[
\int\norm{u-s}^{-\ell}\,d\nu(u)
\le 1+H2^\ell\sum_{j\ge0}2^{-j(n-\ell)}<\infty.
\]
The term \(1\) covers distances greater than one, and \(n-\ell>0\)
makes the series converge. This is uniform in \(s\).
For each full-rank \(G\), Lebesgue differentiation holds at \(GS\)
for \(\nu\)-almost every \(S\), since \(G_\#\nu\) has a density.
Fubini and Fatou pass the first-moment bound to \(p_\nu(G,GS)\).
It follows that \(\E\log^+p_\nu(G,GS)<\infty\). To control the
other part, let \(\phi_\ell\) be the standard Gaussian density on
\(\R^\ell\). For each \(G\),
\[
\int p_\nu(G,y)
\left(\log\frac{p_\nu(G,y)}{\phi_\ell(y)}\right)_-dy
\le\frac1e.
\]
Also \(\E\norm{GS}^2=\ell\), so
\(\E[-\log\phi_\ell(GS)]=\frac{\ell}{2}\log(2\pi)+\frac{\ell}{2}\).
The inequality
\[
(-\log p_\nu)_+
\le\left(\log(p_\nu/\phi_\ell)\right)_-
+(-\log\phi_\ell)_+
\]
proves the negative logarithmic bound directly. The densities in
these conclusions describe the exact labels; the cube averages only
prove their estimates.
For the last assertion, conditioning on \(W=w\) dominates the joint
law of \((G,S)\) by \(P(W=w)^{-1}\) times
\(\gamma_\ell\otimes\nu\). This gives an actual conditional image
density for every full-rank \(G\), up to the usual null set in \(G\).
The product marginal is unchanged after averaging over \(w\), so the
actual expectation of \(\lvert\log p_\nu(G,GS)\rvert\) is finite.
The relative entropy of the actual conditional image density from
\(p_\nu(G,\cdot)\), averaged over \((G,W)\), equals
\(I(W;GS\mid G)\le H(W)\). The density-ratio negative part is at
most \(1/e\), hence its logarithm is integrable and so is the actual
log density.
Similarly, conditional data processing gives
\[
\E D\bigl(P_{GS\mid G,W}\Vert G_\#\nu_W\bigr)
\le \E D\bigl(P_{S\mid G,W}\Vert\nu_W\bigr)
=I(S;G\mid W)\le H(W).
\]
The last inequality follows from \(I(S;G)=0\) and the chain rule.
The log ratio in this display is integrable by the same negative-part
bound. Subtracting it from the actual log density proves integrability
of \(\log p_{\nu_W}(G,GS)\). The argument also applies to a
deterministic refinement \(W'=(W,E(S,W))\) whenever \(H(W')<\infty\).
\end{proof}
\subsection{A message selected using actual rows}
\label{subsec:r-two-experiments}
Let \(m,r\ge1\), \(\ell=m+r<n\), and let \(S\sim\sigma\).
Let \(A\sim\gamma_m\) be independent of \(S\), and let \(W\) be a
countable message with \(H(W)<\infty\), coupled arbitrarily to
\((S,A)\). We define two laws:
\begin{itemize}
\item In the \emph{aligned experiment} \(P_1\), retain the joint law
of \((S,A,W)\), take \(C\sim\gamma_r\) independently, and set
\(G=(A;C)\) and \(Y=GS\).
\item In the \emph{independent experiment} \(P_0\), retain the
marginal law of \((S,W)\), draw \(G\sim\gamma_\ell\) independently
of that pair, and again set \(Y=GS\).
\end{itemize}
Both laws have the same \((S,W)\) marginal and the same product
\((S,G)\) marginal. In the aligned law, \(W\) may be dependent on
the rows \(G\); in the independent law, \(G\) is independent of
\((S,W)\). Define
\[
J_i(W)=I_i(S;W\mid G,Y),\qquad i=0,1,
\]
and, for positive-probability \(w\), let
\(\nu_w=P_{S\mid W=w}\), which is common to both experiments.
\begin{proposition}[The information identity and its density bound]
\label{prop:r-information-comparison}
In the two experiments just defined, all quantities below are finite,
and
\begin{align}
J_0(W)-J_1(W)
&=h_0(Y\mid G,W)-h_1(Y\mid G,W)-I_1(S;G\mid W)
\label{eq:r-information-identity}\\
&\le h_0(Y\mid G,W)+\E_1\log p_{\nu_W}(G,Y).
\label{eq:r-information-density-bound}
\end{align}
If \(E=E(S,W)\) is countable and \(H(E\mid W)<\infty\), and the
same deterministic refinement \(W'=(W,E)\) is used in both laws,
then
\begin{equation}\label{eq:r-refinement-charge}
J_0(W)-J_1(W)
\le J_0(W')-J_1(W')+H(E\mid W).
\end{equation}
\end{proposition}
\begin{proof}
Because \(Y\) is determined by \((S,G)\), the conditional chain
rule gives
\[
J_i(W)=I_i(S;W\mid G)-I_i(W;Y\mid G).
\]
Since \(S\) and \(G\) are independent in both laws,
\[
I_i(S;W\mid G)=I(S;W)+I_i(S;G\mid W),
\]
and \(I_0(S;G\mid W)=0\). The \((S,W)\) and \((S,G)\)
marginals agree, so subtraction gives
\[
J_0(W)-J_1(W)
=I_1(W;Y\mid G)-I_0(W;Y\mid G)-I_1(S;G\mid W).
\]
All mutual information terms are finite: those involving the
countable message are at most \(H(W)\), and the last is at most
\(H(W)\) by this same chain rule. Lemma~\ref{lem:r-projection-density}
makes the conditional differential entropies finite. Expressing
the two \(I(W;Y\mid G)\) terms as entropy differences, whose
\(h(Y\mid G)\) terms agree, proves
\eqref{eq:r-information-identity}. In particular the conditional
row-information term has a negative sign.
Apply conditional data processing to \(s\mapsto Gs\):
\begin{align*}
-h_1(Y\mid G,W)-\E_1\log p_{\nu_W}(G,Y)
&=\E_1 D(P_1(Y\in\cdot\mid G,W)\Vert G_\#\nu_W)\\
&\le\E_1 D(P_1(S\in\cdot\mid G,W)\Vert\nu_W)\\
&=I_1(S;G\mid W).
\end{align*}
The integrability assertion of the same lemma justifies these
subtractions. Substituting this inequality into
\eqref{eq:r-information-identity} proves
\eqref{eq:r-information-density-bound}.
Finally
\[
J_i(W')=J_i(W)+I_i(S;E\mid W,G,Y).
\]
The difference for \(W\) therefore equals the difference for \(W'\)
minus the \(i=0\) term and plus the \(i=1\) term. The former is
nonnegative and the latter is at most \(H(E\mid W)\). This proves
\eqref{eq:r-refinement-charge}.
\end{proof}
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/01-information-and-densities.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/02-mixed-moments.tex ====
\section{A projection moment with shared and fresh rows}
\label{sec:r-mixed-moments}
The information bound in
Proposition~\ref{prop:r-information-comparison} contains a projection
density evaluated at the true label. The rows used to select the
message can be biased after conditioning on that message. We first
bound a high moment under the original Gaussian row law. Some rows
are shared across all factors in this moment; the other rows are
averaged independently in each factor. The high moment will then
pay for the change from Gaussian rows to selected rows.
Expanding a projection moment into independent signal copies is part
of the projection method of Sharan, Sidford, and Valiant
\cite[Section~7, Lemma~12]{SSV2019}. The estimate below treats exact
multirow projections. Its geometric hypothesis has two local mass
bounds: one controls distance to a span, and the other controls the
small radial scales.
For \(x>0\), write \(\log^+x=\max\{\log x,0\}\).
\Needspace{6\baselineskip}
\begin{theorem}[Mixed projection moment and exact density version]
\label{thm:r-mixed-moment}
Let \(n=d-1\), let \(m,r,q\ge1\) be integers, and put
\(\ell=m+r\). Suppose
\begin{equation}\label{eq:r-mixed-dimensions}
\ell<n,\qquad \ell-m-(q-1)\ge1.
\end{equation}
Let \(\rho\) be a finite nonnegative Borel measure on \(S^{d-1}\).
Suppose that \(B,D>0\) and, for every \(z\in\R^d\) and \(t>0\),
\begin{equation}\label{eq:r-mixed-growth}
\rho(B(z,t))\le Bt^\ell,\qquad
\rho(B(z,t))\le Dt^n.
\end{equation}
Let \(X\sim\gamma_m\) and \(Z\sim\gamma_r\) be independent, and set
\(G=(X;Z)\). For \(\delta>0\), define the cube average
\[
p_{\rho,\delta}(g,y)
=(2\delta)^{-\ell}\int
\ind_{\{\norm{gu-y}_\infty\le\delta\}}\,d\rho(u).
\]
There is an absolute \(C\) such that, for every fixed
\(s\in S^{d-1}\) and every \(\delta>0\),
\begin{equation}\label{eq:r-mixed-smoothed}
\left[\E_X
\left(\E_Z p_{\rho,\delta}((X;Z),(X;Z)s)\right)^q
\right]^{1/q}
\le e^{Cd}B\bigl(1+\log^+(D/B)\bigr).
\end{equation}
If in addition \(\rho\ll\sigma\), use the jointly Borel density
\(p_\rho\) in \eqref{eq:r-density-version}. There is a measurable
set \(E_\rho\subset S^{d-1}\), with \(\rho(E_\rho)=0\), such that
for every \(s\notin E_\rho\) the cube averages converge to
\(p_\rho(G,Gs)\) for \(\gamma_\ell\)-almost every \(G\), and
\begin{equation}\label{eq:r-mixed-exact}
\left[\E_X
\left(\E_Zp_\rho((X;Z),(X;Z)s)\right)^q
\right]^{1/q}
\le e^{Cd}B\bigl(1+\log^+(D/B)\bigr).
\end{equation}
When \(\rho\ne0\), \(E_\rho\) may also be chosen so that
\(0<p_\rho(G,Gs)<\infty\) for \(\gamma_\ell\)-almost every \(G\)
and every \(s\notin E_\rho\).
\end{theorem}
\begin{proof}
We begin with the inverse-distance integral that appears after
expanding the moment. Fix \(s\in S^{d-1}\) and a linear subspace
\(V\subset\R^d\) of dimension \(h\le q-1\). On a radial shell
\[
R/2<\norm{u-s}\le R,\qquad R=2^{1-i},\quad i\ge0,
\]
consider the points satisfying
\(\dist(u-s,V)\le\eta R\), where \(0<\eta\le1\). Project them
onto the radius-\(R\) ball in \(s+V\). An \(\eta R\)-net of this
ball has at most \((3/\eta)^h\) points: a maximal separated set
has disjoint \(h\)-balls of radius \(\eta R/2\), all lying in the
ball of radius \(R+\eta R/2\). For \(h=0\), take the single
point of the zero-dimensional ball. Every point under consideration
is within \(2\eta R\) of one of the net points. The ambient-center
bounds in \eqref{eq:r-mixed-growth} therefore give
\begin{equation}\label{eq:r-mixed-tube}
\rho\{R/2<\norm{u-s}\le R,\ \dist(u-s,V)\le\eta R\}
\le e^{Cd}\min\{BR^\ell\eta^{\ell-h},
DR^n\eta^{n-h}\}.
\end{equation}
Both powers of \(\eta\) are positive, so the part of the shell at
zero distance from \(V\) has zero \(\rho\)-mass. The ball bounds
also give \(\rho(\{s\})=0\), by sending their radius to zero.
On the band
\(2^{-a-1}R<\dist(u-s,V)\le2^{-a}R\), \(a\ge0\), we have
\[
\norm{u-s}^{-r}\dist(u-s,V)^{-m}
\le 2^{r+m}R^{-\ell}2^{am}.
\]
Summing \eqref{eq:r-mixed-tube} over these bands with either of its
two terms gives a geometric series. The relevant exponents satisfy
\[
\ell-h-m\ge\ell-(q-1)-m\ge1,\qquad
n-h-m\ge1.
\]
Thus the integral on one radial shell is at most
\[
e^{Cd}\min\{B,DR^{\,n-\ell}\}.
\]
The shells \(R=2^{1-i}\) cover all nonzero distances on the unit
sphere. Put \(b=n-\ell\ge1\). Their sum obeys
\[
\sum_{i\ge0}\min\{B,D2^{b(1-i)}\}
\le C B\bigl(1+\log^+(D/B)\bigr).
\]
For example, after the \(i=0\) term, if \(D/B\le1\) the terms form
a geometric tail of ratio at most \(1/2\). If \(D/B>1\), at most
\(1+\log_2(D/B)/b\) further terms equal \(B\), followed by such a
tail. We have proved the uniform estimate
\begin{equation}\label{eq:r-mixed-inverse}
\int\norm{u-s}^{-r}\dist(u-s,V)^{-m}\,d\rho(u)
\le e^{Cd}B\bigl(1+\log^+(D/B)\bigr).
\end{equation}
We now expand the projection moment. For fixed \(u\ne s\), the
\(r\) coordinates of \(Z(u-s)\) are independent centered normals
of variance \(\norm{u-s}^2\). Bounding each cube probability by
its volume times the peak density shows that the fresh-row average,
after division by \((2\delta)^r\), is at most
\((2\pi)^{-r/2}\norm{u-s}^{-r}\).
Expand the \(q\)th power of the remaining integral over
\(u_1,\ldots,u_q\). Write \(v_i=u_i-s\). For one shared row of
\(X\), the vector of its \(q\) evaluations on the \(v_i\) is
Gaussian with covariance \(\Gram(v_1,\ldots,v_q)\). On the set
where this matrix is nonsingular, its peak density bounds its cube
probability by
\[
(2\delta)^q(2\pi)^{-q/2}
\det\Gram(v_1,\ldots,v_q)^{-1/2}.
\]
The singular tuples have zero \(\rho^{\otimes q}\)-mass:
successively, \eqref{eq:r-mixed-tube} gives zero mass to
\(s+\operatorname{span}(v_1,\ldots,v_{i-1})\). Independence of
the \(m\) shared rows and the \(r\) fresh rows cancels all cube
volumes and bounds the expanded moment by
\begin{equation}\label{eq:r-mixed-collision}
(2\pi)^{-\ell q/2}
\int\prod_{i=1}^q\norm{v_i}^{-r}\,
\det\Gram(v_1,\ldots,v_q)^{-m/2}\,d\rho^{\otimes q}.
\end{equation}
Gram--Schmidt gives
\[
\det\Gram(v_1,\ldots,v_q)
=\prod_{i=1}^q
\dist\bigl(v_i,\operatorname{span}(v_1,\ldots,v_{i-1})\bigr)^2,
\]
with the empty span equal to \(\{0\}\). Integrate in the reverse
order \(u_q,\ldots,u_1\). Every inner integral is bounded by
\eqref{eq:r-mixed-inverse}, uniformly in the previous vectors.
This proves \eqref{eq:r-mixed-smoothed}. All integrands used in
the expansion are nonnegative, so Tonelli justifies each
interchange.
Suppose now that \(\rho\ll\sigma\). For every full-rank \(g\),
Lemma~\ref{lem:r-projection-density} and Lebesgue differentiation
give cube convergence outside a Lebesgue-null subset of label
space. Its inverse image is \(\rho\)-null because \(g_\#\rho\)
has a density. The same argument shows that the exact density is
finite and, when \(\rho\ne0\), positive at \(gs\) for
\(\rho\)-almost every \(s\). Since \(\gamma_\ell\) gives full
row rank almost surely, Fubini supplies a single
\(\rho\)-null set \(E_\rho\) with these properties for every
\(s\notin E_\rho\) and almost every independent \(G\).
Fix such an \(s\). Fatou in the fresh rows gives
\[
\E_Zp_\rho((X;Z),(X;Z)s)
\le\liminf_{j\to\infty}
\E_Zp_{\rho,1/j}((X;Z),(X;Z)s)
\]
for almost every \(X\). Raise to the \(q\)th power and use Fatou
again in \(X\). The uniform bound
\eqref{eq:r-mixed-smoothed} then proves
\eqref{eq:r-mixed-exact}. This last assertion has the stated
\(\rho\)-almost-everywhere qualification.
\end{proof}
\subsection{Changing the actual row law before taking the density limit}
\label{subsec:r-actual-row-limit}
The exceptional set in the exact moment theorem is measured using
\(\rho\). A selected message produces a different conditional law
of the true signal and the actual rows. The following form uses the
uniform cube estimate for every signal, pays for that row selection,
and then takes the density limit under the actual label law. The
localization application uses this order in its own specialized proof.
\begin{proposition}[Actual-row tilt and exact-label limit]
\label{prop:r-actual-row-limit}
Keep the dimensions of Theorem~\ref{thm:r-mixed-moment}. Let
\(\nu\le H\sigma\), \(H<\infty\), be a probability measure.
Let \(S\sim\nu\) and \(X\sim\gamma_m\) be independent, let \(W\)
be countable with \(H(W)<\infty\) and any joint law with
\((S,X)\), and let \(Z\sim\gamma_r\) be independent of
\((S,X,W)\). Put \(G=(X;Z)\) and \(Y=GS\).
For every positive-probability \(w\), let \(\rho_w\ll\sigma\)
be a finite nonnegative measure satisfying
\eqref{eq:r-mixed-growth} with constants \(B_w,D_w>0\), and set
\[
C_w=e^{Cd}B_w\bigl(1+\log^+(D_w/B_w)\bigr),
\]
where \(C\) is the constant in the theorem. Assume
\(\E\log(1+C_W)<\infty\).
The actual conditional law of \(Y\) given \((G,W)\) has a
Lebesgue density. With the versions
\eqref{eq:r-density-version},
\[
p_{\rho_W,1/j}(G,Y)\longrightarrow p_{\rho_W}(G,Y)
\quad\text{almost surely under the actual law}.
\]
For every \(\delta>0\), and also for the exact density,
\begin{align}
\E\log\bigl(1+p_{\rho_W,\delta}(G,Y)\bigr)
&\le \frac{I(X;W\mid S)}q+\E\log(1+C_W),
\label{eq:r-actual-smoothed}\\
\E\log\bigl(1+p_{\rho_W}(G,Y)\bigr)
&\le \frac{I(X;W\mid S)}q+\E\log(1+C_W)
\le \frac{H(W)}q+\E\log(1+C_W).
\label{eq:r-actual-exact}
\end{align}
In particular \(\log^+p_{\rho_W}(G,Y)\) is integrable, and the
extended expectation of \(\log p_{\rho_W}(G,Y)\), with
\(\log0=-\infty\), is defined and bounded above by the same
right-hand side. For a deterministic countable refinement
\(W'=(W,E(S,W))\) of finite entropy, the row charge is unchanged:
\[
I(X;W'\mid S)=I(X;W\mid S).
\]
\end{proposition}
\begin{proof}
For almost every \((s,w)\), let \(K_{s,w}\) be the conditional law
of \(X\). Since \(X\) and \(S\) are initially independent, the
conditional chain rule gives
\begin{equation}\label{eq:r-conditional-row-kl}
\E_{S,W}D(K_{S,W}\Vert\gamma_m)
=I(X;W\mid S)\le H(W)<\infty.
\end{equation}
Thus \(K_{s,w}\ll\gamma_m\) for almost every \((s,w)\).
For fixed \(s,w,\delta\), define
\[
F_{w,\delta}(s,x)=
\E_Zp_{\rho_w,\delta}((x;Z),(x;Z)s).
\]
The every-signal estimate \eqref{eq:r-mixed-smoothed} says that
\(\|F_{w,\delta}(s,\cdot)\|_{L^q(\gamma_m)}\le C_w\), uniformly
in \(\delta\). Conditional on \((S,X,W)\), \(Z\) still has its
independent Gaussian law. Jensen in \(Z\), followed by
\eqref{eq:r-entropy-variational} with the nonnegative test
\(q\log(1+F_{w,\delta})\), gives
\begin{align*}
\E\!\left[\log(1+p_{\rho_w,\delta}(G,Y))
\,\middle|\,S=s,W=w\right]
&\le \E_{K_{s,w}}\log(1+F_{w,\delta}(s,X))\\
&\le \frac{D(K_{s,w}\Vert\gamma_m)}q
+\frac1q\log\E_{\gamma_m}(1+F_{w,\delta}(s,X))^q\\
&\le \frac{D(K_{s,w}\Vert\gamma_m)}q+\log(1+C_w).
\end{align*}
The last step is the \(L^q\) triangle inequality, valid since
\(q\ge1\). Average over \((S,W)\) and use
\eqref{eq:r-conditional-row-kl} to obtain
\eqref{eq:r-actual-smoothed}.
It remains to specify the null set for the limit in the actual
experiment. The marginal law of \((G,S)\) is
\(\gamma_\ell\otimes\nu\). Lemma~\ref{lem:r-projection-density}
therefore gives a Lebesgue density for the actual conditional law
of \(Y\) given \((G,W)\). For each \(w\) and every full-rank \(g\),
Lebesgue differentiation for \(g_\#\rho_w\) says that
\(p_{\rho_w,1/j}(g,y)\to p_{\rho_w}(g,y)\) outside a
Lebesgue-null set of \(y\). The actual conditional density gives
that set zero probability. Gaussian \(G\) has full rank almost
surely, and there are only countably many \(w\), proving the
asserted almost-sure convergence under the actual law.
The functions \(\log(1+p_{\rho_W,1/j}(G,Y))\) are nonnegative.
Fatou applied now, after the row-law change, passes
\eqref{eq:r-actual-smoothed} to \eqref{eq:r-actual-exact}.
Since \(\log^+x\le\log(1+x)\), the positive logarithmic part is
integrable; the negative part may have infinite mean, in which
case the extended expectation of \(\log p_{\rho_W}\) is
\(-\infty\) and the upper bound remains valid. Applications
that subtract this logarithm verify its full integrability
separately. Finally, \(E\) is determined by \((S,W)\), so
\(I(X;E\mid S,W)=0\); the chain rule proves the refinement identity.
\end{proof}
\begin{remark}[The parameters used by the localization potential]
\label{rem:r-localization-substitution}
The inverse-distance potential in the localization companion
\cite[Section~12, Lemma~12.5]{OpenAILocalization2026} takes
\[
m=r=q=k=\lfloor d/16\rfloor,\qquad \ell=p=2k,\qquad n=d-1.
\]
For its bounded-density probability \(\nu\le H\sigma\), it
defines \(J_\nu(s)=\int\norm{u-s}^{-p}\,d\nu(u)\) and
\(d\rho=d\nu/J_\nu\). The application proves locally that
\[
\rho(B(z,t))\le 2^p t^p,\qquad
\rho(B(z,t))\le 2^{p+n}H t^n.
\]
Thus the precise constants in Theorem~\ref{thm:r-mixed-moment}
are \(B=2^p\) and \(D=2^{p+n}H\), the angular margin is
\(p-k-(k-1)=1\), and the radial margin is \(n-p>0\).
The theorem supplies the uniform cube estimate and its exact-density
scope. The localization application imports the positive-scale
estimate and proves its reweighting, specialized row-law change,
and actual-law Fatou passage locally, together with its potential
calculations.
Proposition~\ref{prop:r-actual-row-limit} gives a general comparison
of the same type within the present paper.
\end{remark}
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/02-mixed-moments.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/03-critical-radius.tex ====
\section{A critical radius makes the density terms cancel}
\label{sec:r-critical-radius}
The two terms in \eqref{eq:r-information-density-bound} can each
be large when the message concentrates the signal on a small region.
We will compare them at the same region and scale. A discrete
refinement records a radius where the posterior mass is largest
relative to the projection dimension, together with its logarithmic
mass level. Confinement at that radius lowers the entropy in the
independent experiment. The same level raises the aligned projection
density by the opposite amount.
Throughout this section \(d\) is sufficiently large and
\begin{equation}\label{eq:r-critical-parameters}
m=k=\lfloor d/10\rfloor,\qquad
\ell=\lfloor d/2\rfloor,\qquad r=\ell-m,\qquad n=d-1.
\end{equation}
The integer \(k\) is a moment order. We reserve \(q\) in this
section for a logarithmic mass level. In particular
\(\ell<n\), \(\ell-k-m\ge1\), and \(n-k-m\ge1\).
\begin{theorem}[Critical-radius comparison]\label{thm:r-critical-comparison}
In the two experiments of Subsection~\ref{subsec:r-two-experiments},
use the dimensions \eqref{eq:r-critical-parameters}. Thus
\(S\sim\sigma\), \(A\sim\gamma_m\) is independent of \(S\), and
\(W\) is countable with an arbitrary joint dependence on \((S,A)\).
The aligned law retains \((S,A,W)\) and appends independent
\(r\)-row \(C\), whereas the independent law retains \((S,W)\)
and draws an independent \(\ell\)-row matrix \(G\).
If \(H(W)\le d^2\), then, for an absolute constant \(K\),
\begin{equation}\label{eq:r-critical-comparison}
I_0(S;W\mid G,GS)\le I_1(S;W\mid G,GS)+Kd.
\end{equation}
\end{theorem}
\begin{proof}
For a positive-probability message \(w\), write
\[
p_w=\Prob(W=w),\qquad D_w=p_w^{-1},\qquad
F_w=P_{S\mid W=w}.
\]
Then \(F_w\le D_w\sigma\). The common density lemma and
Proposition~\ref{prop:r-information-comparison} apply to every
finite-entropy refinement used below.
\subsection*{Selecting a radius and a mass level}
Let \(R_j=2^{1-j}\) for \(j\ge0\), and define
\begin{equation}\label{eq:r-critical-selector}
b_w(s)=\max_{j\ge0} R_j^{-\ell}F_w(B(s,R_j)).
\end{equation}
The \(j=0\) term is \(2^{-\ell}\). On the other hand,
Lemma~\ref{lem:r-caps} gives
\[
R_j^{-\ell}F_w(B(s,R_j))
\le 2^nD_wR_j^{\,n-\ell}\longrightarrow0.
\]
Hence the maximum is attained. Let \(j_w(s)\) be the least
maximizing index, and put \(q_w(s)=\lceil\log b_w(s)\rceil\).
Ball masses are measurable functions of their centers, and a
countable comparison selects the least maximizing index, so these
choices are measurable.
The preceding upper bound and \(b_w\ge2^{-\ell}\) give
\[
0\le j_w(s)\le C(d+1+\log D_w).
\]
For \(R_j\le1\), the same upper bound is at most \(2^nD_w\);
for \(R_j>1\), total mass one suffices. Therefore
\[
-Cd\le q_w(s)\le C(d+1+\log D_w).
\]
Define the discrete refinement
\[
E=(j_W(S),q_W(S)),\qquad W'=(W,E).
\]
For a positive-probability value \(w'\), write
\(F_{w'}=P_{S\mid W'=w'}\).
There are at most \(C(d+1+\log D_w)^2\) possible pairs conditional
on \(W=w\). Since \(\E\log D_W=H(W)\), counting those pairs
and then using Jensen gives
\begin{equation}\label{eq:r-critical-refinement-entropy}
H(E\mid W)\le C\log(d+1+H(W)).
\end{equation}
In particular \(H(W')=H(W)+H(E\mid W)<\infty\).
The same deterministic function of \((S,W)\) is used in both
experiments, so \eqref{eq:r-refinement-charge} gives
\begin{equation}\label{eq:r-critical-refinement-charge}
J_0(W)-J_1(W)
\le J_0(W')-J_1(W')+H(E\mid W).
\end{equation}
Fix a positive-probability \(w'=(w,j,q)\) and put
\[
\eta=\Prob(E=(j,q)\mid W=w),\qquad F=P_{S\mid W'=w'}.
\]
The measure \(F\) is the restriction of \(F_w\) to the selected
class, divided by \(\eta\). It satisfies
\begin{equation}\label{eq:r-critical-growth}
F\le D'\sigma,\qquad F(B(z,t))\le B't^\ell
\quad(z\in\R^d,\ t>0),\qquad
D'=\frac{D_w}{\eta},\quad B'=\frac{4^\ell e^q}{\eta}\ge1.
\end{equation}
For the local mass bound, if \(t\le1\) and \(B(z,t)\) has positive
\(F\)-mass, choose a selected-class point \(s_0\) in that ball.
Choose a dyadic radius \(R_h\le2\) satisfying
\(2t\le R_h\le4t\); its ball about \(s_0\) covers \(B(z,t)\).
Its \(F_w\)-mass is at
most \(e^q(4t)^\ell\) by \eqref{eq:r-critical-selector}.
Divide by \(\eta\). For \(t>1\), use total mass one and
\(B'\ge1\). The latter bound follows from
\(e^q\ge b_w\ge2^{-\ell}\) and \(\eta\le1\).
\subsection*{The independent projection loses the mass level}
The selected class can be covered by at most
\begin{equation}\label{eq:r-critical-cover}
N\le e^{1-q}R_j^{-\ell}
\end{equation}
balls of radius \(2R_j\). Indeed, choose successive class points
at mutual distances greater than \(2R_j\). Their radius-\(R_j\)
balls are disjoint. Each such ball has \(F_w\)-mass at least
\(e^{q-1}R_j^\ell\), since \(j\) maximizes the ratio and
\(q=\lceil\log b_w\rceil\). Total mass one bounds the number
of points and forces the selection to terminate with the asserted
cover. For each of the countably many labels \(w'\), fix one such
finite cover and assign a point to the first ball containing it.
The resulting center label \(c\) is measurable and has conditional
entropy at most \(\log N\).
In the independent experiment, conditional on \(W'=w'\), the
matrix \(G\) is independent of \((S,c)\) and
\(\norm{S-c}\le2R_j\). Consequently
\[
\E_0[\norm{G(S-c)}^2\mid W'=w']\le4\ell R_j^2.
\]
Compare the conditional density of \(Y-Gc\), given \((G,c,w')\),
with the centered Gaussian density of covariance \(4R_j^2I_\ell\).
Nonnegative relative entropy and the displayed second moment give
\[
h_0(Y\mid G,c,W'=w')\le\ell\log R_j+C\ell.
\]
The conditional densities and their logarithms are integrable by
Lemma~\ref{lem:r-projection-density}, also after the finite center
refinement. Removing \(c\) costs at most \(\log N\). Using
\eqref{eq:r-critical-cover} cancels the radius and gives
\begin{equation}\label{eq:r-critical-independent-entropy}
h_0(Y\mid G,W'=w')\le-q+Cd.
\end{equation}
\subsection*{The aligned density gains the same level}
For the same \(F\), the exact moment bound needed here is
\begin{equation}\label{eq:r-critical-moment}
\E_A\left(\E_Cp_F((A;C),(A;C)s)\right)^k
\le [C^dB'(1+\log D')]^k
\quad\text{for \(F\)-almost every \(s\)}.
\end{equation}
To check the exact substitution in
Theorem~\ref{thm:r-mixed-moment}, use \(m\) shared rows, \(r\)
fresh rows, moment order \(k\), and \(\ell=m+r\).
The angular gap is
\(\ell-m-(k-1)=\ell-m-k+1\ge2\), and \(\ell<n\).
The first growth coefficient is \(B=B'\). The second is
\(D=2^nD'\), by \(F\le D'\sigma\) and
Lemma~\ref{lem:r-caps}. Since \(B',D'\ge1\),
\[
e^{Cd}B'[1+\log^+(2^nD'/B')]
\le C^dB'(1+\log D').
\]
The exact conclusion of the theorem yields
\eqref{eq:r-critical-moment}.
In the aligned law, conditioning on \((S,W')\) can bias the
actual rows \(A\). Its precise average cost is
\begin{equation}\label{eq:r-critical-row-charge}
\E_1D(P_1(A\in\cdot\mid S,W')\Vert\gamma_m)
=I_1(A;W'\mid S)=I_1(A;W\mid S)\le H(W).
\end{equation}
Here \(A\) is initially independent of \(S\), and \(E\) is
determined by \((S,W)\). The finite average divergence also
gives absolute continuity of the conditional actual row law for
almost every \((S,W')\).
For \(w'\) fixed, the actual marginal \(S\mid W'=w'\) is exactly
\(F\). Hence the \(F\)-null exceptional set in
\eqref{eq:r-critical-moment} has zero actual probability.
For such an \(s\), set
\[
K_F(A,s)=\E_C\log p_F((A;C),(A;C)s).
\]
The reference and actual logarithmic integrability follow from
Lemma~\ref{lem:r-projection-density}; null sets in \(A\) transfer
to its conditional actual law by the preceding absolute
continuity. Jensen and \eqref{eq:r-critical-moment} imply
\[
\E_A e^{kK_F(A,s)}
\le [C^dB'(1+\log D')]^k.
\]
Apply \eqref{eq:r-entropy-variational} to \(kK_F\) under the
conditional actual row law relative to \(\gamma_m\).
The rows \(C\) remain independent after conditioning on
\((S,W',A)\). Averaging and using \eqref{eq:r-critical-row-charge}
therefore gives
\begin{align}
\E_1\log p_{F_{W'}}(G,Y)
\le{}&\frac{H(W)}k+Cd+\E q+H(E\mid W)
+\log(1+H(W')).
\label{eq:r-critical-aligned-density}
\end{align}
Indeed,
\[
\log B'=\ell\log4+q+\log(1/\eta),\quad
\E\log(1/\eta)=H(E\mid W),\quad
\E\log D'=H(W'),
\]
and Jensen bounds
\(\E\log(1+\log D')\) by \(\log(1+H(W'))\).
These expectations are finite by the preceding entropy bounds.
We now have the two estimates at the same selected radius and
mass level. Apply \eqref{eq:r-information-density-bound} to
\(W'\), average \eqref{eq:r-critical-independent-entropy}, and
use \eqref{eq:r-critical-aligned-density}. The terms
\(-\E q\) and \(+\E q\) cancel. Including the refinement charge
\eqref{eq:r-critical-refinement-charge} yields the more precise
inequality
\begin{equation}\label{eq:r-critical-quantitative-gap}
J_0(W)-J_1(W)
\le\frac{H(W)}k+Cd+2H(E\mid W)+\log(1+H(W')).
\end{equation}
Now \(k=\lfloor d/10\rfloor\), \(H(W)\le d^2\), and
\eqref{eq:r-critical-refinement-entropy} make the right-hand side
at most \(Kd\) for an absolute \(K\). This proves
\eqref{eq:r-critical-comparison}.
\end{proof}
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/03-critical-radius.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/04-density-levels.tex ====
\section{Posterior density levels and auxiliary projections}
\label{rlevels:section}\label{sec:r-density-levels}
A state can be informative because its posterior concentrates on a small
part of the sphere. The two comparisons in this section measure that
concentration at dyadic radii. In each comparison, a state is tested
after independent Gaussian observations have been supplied to the
analysis. Replacing some of those rows by the current block makes the
state update a conditional Markov channel. The task is to bound the
information cost of returning from the current rows to independent ones.
The two arguments use different refinements. The first retains only
the level of the largest normalized ball mass and uses a net to estimate
the independent projection entropy. The second retains both the first
maximizing radius and the density level; its covering estimate cancels
the radius directly. These choices lead to different row counts and
to complementary exact-density estimates.
We use the measure, Gaussian law \(\gamma_t\), and entropy conventions
of Section~\ref{sec:r-experiments}. Locally, write \(N=d-1\) for
the sphere dimension; this avoids confusing it with the actual-row
count \(n\) in the second comparison. The row symbols have the
following roles, with their numerical values specified in each
subsection:
\begin{center}
\begin{tabular}{lcccc}
\toprule
Comparison & Total rows & Actual rows & Fresh rows & Moment \\
\midrule
One level & \(m\) & \(k\) & \(j=m-k\) & \(q\) \\
Two labels & \(k\) & \(n\) & \(l=k-n\) & \(q\) \\
\bottomrule
\end{tabular}
\end{center}
Constants \(C,C_0\) are positive and absolute and may increase.
All claims are for sufficiently large \(d\), with an absolute
threshold unless otherwise stated.
We use the local spherical-ball and projection-density results,
Lemmas~\ref{lem:r-caps} and \ref{lem:r-projection-density}. In
particular, for every \(z\in\mathbb R^d\) and \(\rho>0\),
\begin{equation}\label{rlevels:ambient-cap}
\sigma(B(z,\rho))\le (2\rho)^N.
\end{equation}
For \(\nu\le K\sigma\) and a full-row-rank matrix \(g\) with fewer
than \(N\) rows, write \(p_\nu(g,\cdot)\) for the jointly measurable
cube-average version of the density of \(gS\), \(S\sim\nu\).
For independent Gaussian \(G\) and \(S\sim\nu\), the logarithm
\(\log p_\nu(G,GS)\) is integrable.
The same lemma supplies the actual conditional image densities and
the integrable log ratios used below when a finite state is correlated
with the rows. These density statements concern the exact
observations.
We use \eqref{eq:r-entropy-variational} with \(f=q\log F\) in the form
\begin{equation}\label{rlevels:tilt}
\mathbb E_P\log F
\le \frac{D(P\Vert Q)+\log\mathbb E_Q F^q}{q},
\qquad P\ll Q,\quad q>0,\quad F\ge0.
\end{equation}
Truncation gives the integrable form and the upper bound when the
left side is negative infinite.
\subsection{A comparison using one density level}
\label{rlevels:one-level}
Set, locally in this subsection,
\begin{equation}\label{rlevels:one-parameters}
m=\lfloor d/4\rfloor,\qquad k=\lfloor d/32\rfloor,\qquad
j=m-k,\qquad q=\lfloor d/16\rfloor.
\end{equation}
The auxiliary projection has \(m\) rows, of which \(k\) can be actual
rows and \(j\) remain independent. The integer \(q\) is the moment
order. For large \(d\),
\[
m<N,\qquad m-k-(q-1)\ge1.
\]
For a probability measure \(\nu\le K\sigma\), \(K<\infty\), put
\(r_i=2^{1-i}\), \(i\ge0\), and define
\begin{equation}\label{rlevels:one-maximal}
L_\nu(s)=\max_{i\ge0} r_i^{-m}\nu(B(s,r_i)).
\end{equation}
The \(i=0\) term is \(2^{-m}\). On the other hand,
\[
r_i^{-m}\nu(B(s,r_i))\le K2^N r_i^{N-m},
\]
which tends to zero uniformly in \(s\). Hence the maximum is
attained among at most \(C(1+d+\log K)\) initial scales, and
\[
2^{-m}\le L_\nu(s)\le Ke^{Cd}.
\]
The ball-mass functions are Borel, by integration of the Borel
indicator \(\ind_{\{\|s-u\|\le r_i\}}\). Thus \(L_\nu\) and the
first maximizing scale are Borel. For \(a=2^b\), \(b\in\mathbb Z\),
let
\[
F_a=\{s:a\le L_\nu(s)<2a\},\qquad w_a=\nu(F_a).
\]
Only \(C(1+d+\log K)\) levels can be nonempty, and a nonempty level
has \(a\ge2^{-m}\).
\begin{lemma}[Independent projection entropy from a net]
\label{rlevels:one-net}
If \(G\sim\gamma_m\) and \(S\sim\nu\le K\sigma\) are
independent, then
\begin{equation}\label{rlevels:one-net-bound}
\mathbb E\log p_\nu(G,GS)
\ge \mathbb E\log L_\nu(S)-Cd
-\log\!\bigl(C(1+d+\log K)\bigr).
\end{equation}
\end{lemma}
\begin{proof}
At each relevant scale \(i\), take a maximal \(r_i\)-separated set
of centers on the sphere, and assign each point to a nearest center,
breaking ties in a fixed order. Denote the cells and centers by
\(C_{ih}\) and \(c_{ih}\). Each cell is contained in
\(B(c_{ih},r_i)\). At most \(7^d\) centers lie within \(3r_i\)
of a fixed center: the ambient balls of radius \(r_i/2\) about
those centers have disjoint interiors and lie in a ball of radius
\(7r_i/2\).
Let \(b_{ih}\) be the sum of the \(\nu\)-masses of cells with centers
within \(3r_i\) of \(c_{ih}\). For \(s\in C_{ih}\),
\(\nu(B(s,r_i))\le b_{ih}\), and
\(\sum_h b_{ih}\le7^d\). Partition the sphere by its first
maximizing scale \(i(s)\) and its cell at that scale. Write \(w_{ih}\)
for the masses of these classes, omitting zero-mass classes. If
\(N_0\le C(1+d+\log K)\) is the number of relevant scales, Jensen
gives
\begin{equation}\label{rlevels:one-net-weight}
\mathbb E\log\frac{\nu(B(S,r_{i(S)}))}
{w_{i(S),h(S)}}
\le \log\sum_{i,h:w_{ih}>0}b_{ih}
\le d\log7+\log N_0.
\end{equation}
In a class \((i,h)\), let \(\nu_{ih}\) be the conditional law of
\(S\). Its points are within \(r_i\) of \(c_{ih}\). Comparing
the density of \(GS\) with the Gaussian density of mean \(Gc_{ih}\)
and covariance \(r_i^2I_m\), nonnegative relative entropy yields
\[
\mathbb E_{G,S\sim\nu_{ih}}\log p_{\nu_{ih}}(G,GS)
\ge m\log(1/r_i)-Cm,
\]
because independence gives
\(\mathbb E\|G(S-c_{ih})\|^2\le mr_i^2\).
Also \(p_\nu\ge w_{ih}p_{\nu_{ih}}\) almost everywhere.
Average its logarithm under each class. The identity
\(L_\nu(S)=r_{i(S)}^{-m}\nu(B(S,r_{i(S)}))\) then gives
\[
\mathbb E\log p_\nu(G,GS)
\ge \mathbb E\log L_\nu(S)
-\mathbb E\log\frac{\nu(B(S,r_{i(S)}))}
{w_{i(S),h(S)}}-Cm.
\]
Apply \eqref{rlevels:one-net-weight}. The refinement is finite,
and every class is dominated by a finite multiple of \(\sigma\);
Lemma~\ref{lem:r-projection-density} justifies all logarithmic
expectations.
\end{proof}
The next bound uses the same density level to control the projection
when the \(k\) rows will later be allowed to depend on the state.
The order of averaging is essential: the \(j\) independent rows are
averaged before taking a \(q\)-th moment in the other rows.
\begin{lemma}[A moment on one level]\label{rlevels:one-moment}
Let \(w_a>0\) and \(\mu=\nu(\,\cdot\,\mid F_a)\). For independent
\(X\sim\gamma_k\), \(B\sim\gamma_j\), and \(G=(X;B)\),
\begin{equation}\label{rlevels:one-moment-bound}
\left[\mathbb E_X
\bigl(\mathbb E_B p_\mu(G,Gs)\bigr)^q\right]^{1/q}
\le e^{Cd}\frac{a}{w_a}(1+d+\log K)
\end{equation}
for \(\mu\)-almost every \(s\).
\end{lemma}
\begin{proof}
For every ambient ball and \(t>0\),
\begin{equation}\label{rlevels:one-two-powers}
\mu(B(z,t))\le C_0^d\frac{a}{w_a}t^m,
\qquad
\mu(B(z,t))\le C_0^d\frac{K}{w_a}t^N
\end{equation}
with one absolute \(C_0\). For the first estimate, if the ball has
positive \(\mu\)-mass, choose \(s_0\in F_a\cap B(z,t)\). For
\(t\le1\), a dyadic radius between \(2t\) and \(4t\) contains
\(B(z,t)\cap F_a\), and its \(\nu\)-mass is at most
\(2a(4t)^m\). For \(t>1\), use total mass one and
\(a\ge2^{-m}\). The second estimate follows from
\(\mu\le(K/w_a)\sigma\) and \eqref{rlevels:ambient-cap}.
Apply the shared/fresh moment theorem, Theorem~\ref{thm:r-mixed-moment},
with \(k\) shared rows, \(j\) fresh rows, total row count \(m\),
moment order \(q\), and
\[
B_0=C_0^d a/w_a,\qquad D_0=C_0^d K/w_a.
\]
Its angular gap is \(m-k-(q-1)\ge1\), and its radial gap is
\(N-m>0\). The inverse factor in its one-point integration is
exactly
\[
\|u-s\|^{-j}\operatorname{dist}(u-s,V)^{-k},
\qquad \dim V\le q-1.
\]
The ratio \(D_0/B_0=K/a\) does not contain \(w_a\), and
\(\log^+(K/a)\le\log K+m\log2\). The theorem therefore gives the
right side of \eqref{rlevels:one-moment-bound} uniformly in the
cube-average scale, for every fixed \(s\).
For completeness, the passage to the exact density has the
almost-everywhere scope asserted here. At \(Gs\) the cube averages
converge for almost every \((G,s)\) under
\(\gamma_m\otimes\mu\): condition on \(G\), use absolute
continuity of its image law and Lebesgue differentiation, and then
apply Fubini. For \(\mu\)-almost every fixed \(s\), Fatou first
in \(B\) and then in \(X\) after taking the \(q\)-th power gives
\eqref{rlevels:one-moment-bound}. This passage estimates the exact
label; it does not change the learner's observation. The expansion
into independent points underlying the moment theorem is related to
the projection-moment method of Sharan, Sidford, and Valiant
\cite[Section~7, Lemma~12]{SSV2019}; the multirow estimate used here
is the local theorem with the displayed parameters.
\end{proof}
We now specify both experiments. For a finite variable \(V\)
jointly distributed with \(S\sim\sigma\), define
\[
\mathcal D(V)=I_{\mathrm{ind}}(S;V\mid G,GS),
\qquad G\sim\gamma_m
\text{ independent of }(S,V).
\]
In the actual experiment, \(X\sim\gamma_k\) is independent of
\(S\sim\sigma\), \(U\) is any finite variable jointly distributed
with \((S,X)\), and \(B\sim\gamma_j\) is independent of
\((S,X,U)\). Put \(G=(X;B)\) and
\[
\widetilde{\mathcal D}(U)=I_{\mathrm{act}}(S;U\mid G,GS).
\]
The same definition applies to a finite refinement \(V\) determined
by \((S,U)\).
Thus \(G\) and \(S\) are marginally independent in both experiments,
but \(G\) can depend on \(U\) in the actual one. The independent
experiment uses the same \((S,U)\) marginal as the actual one.
\Needspace{6\baselineskip}
\begin{proposition}[One-level auxiliary-row comparison]
\label{rlevels:one-comparison}
For the preceding experiments and parameters,
\begin{equation}\label{rlevels:one-comparison-bound}
\mathcal D(U)\le\widetilde{\mathcal D}(U)
+C\left(d+\log(1+d+H(U))+\frac{H(U)}d\right).
\end{equation}
The proposition applies to every finite \(U\) with the specified
joint law.
\end{proposition}
\begin{proof}
First take \(V=U\), or a finite refinement of \(U\) determined by
\((S,U)\). Let \(P\) be the actual law and \(Q\) the law with the
same \((S,V)\) marginal and an independent \(G\sim\gamma_m\).
Their \((G,S)\) marginals also agree. Write
\(\nu_v=P_{S\mid V=v}=Q_{S\mid V=v}\).
Proposition~\ref{prop:r-information-comparison} gives the exact identity
\begin{equation}\label{rlevels:one-information-identity}
\mathcal D(V)-\widetilde{\mathcal D}(V)
=I_P(V;GS\mid G)-I_Q(V;GS\mid G)-I_P(S;G\mid V).
\end{equation}
Its density bound specializes to
\begin{equation}\label{rlevels:one-density-comparison}
\mathcal D(V)-\widetilde{\mathcal D}(V)
\le \mathbb E_P\log p_{\nu_V}(G,GS)
-\mathbb E_Q\log p_{\nu_V}(G,GS).
\end{equation}
The negative term in \eqref{rlevels:one-information-identity} is
what pays for the changed conditional image density. All quantities
are finite by Lemma~\ref{lem:r-projection-density} and
\(I_P(S;G\mid V)\le H(V)\).
For \(u\) of positive probability let \(K_u=P(U=u)^{-1}\), so
\(\nu_u\le K_u\sigma\). Let \(J\) be the integer with
\(S\in F_{2^J}\) for the levels of \(L_{\nu_U}\), and put
\(V=(U,J)\). The level count and Jensen give
\begin{equation}\label{rlevels:one-label-entropy}
H(J\mid U)
\le \mathbb E\log\!\bigl(C(1+d+\log K_U)\bigr)
\le \log\!\bigl(C(1+d+H(U))\bigr).
\end{equation}
Under \(Q\), refinement increases the mean log projection density
by \(I_Q(J;GS\mid G,U)\ge0\). Applying
Lemma~\ref{rlevels:one-net} to each \(\nu_u\) therefore yields
\begin{equation}\label{rlevels:one-independent-lower}
\mathbb E_Q\log p_{\nu_V}(G,GS)
\ge \mathbb E\log L_{\nu_U}(S)-Cd
-\log\!\bigl(C(1+d+H(U))\bigr).
\end{equation}
For the actual upper bound, condition on \(S=s,V=v=(u,b)\) and
write \(a=2^b\). Conditional on \((s,v,X)\), \(B\) is still
independent with law \(\gamma_j\). Jensen in \(B\) bounds the
conditional mean of \(\log p_{\nu_v}(G,Gs)\) by the mean, under
\(P_{X\mid s,v}\), of
\(\log\mathbb E_Bp_{\nu_v}((X;B),(X;B)s)\).
Apply \eqref{rlevels:tilt} with reference \(\gamma_k\), order
\(q\), and Lemma~\ref{rlevels:one-moment}. The conditional
divergences average to
\begin{equation}\label{rlevels:one-row-kl}
\mathbb E D(P_{X\mid S,V}\Vert\gamma_k)
=I_P(X;V\mid S)=I_P(X;U\mid S)\le H(U).
\end{equation}
The first equality uses marginal independence of \(X,S\); the
second uses that \(J\) is determined by \((S,U)\). Thus the
refinement creates no additional conditional row information.
Finite average divergence also gives \(P_{X\mid S,V}\ll\gamma_k\)
almost everywhere. The exact moment is needed only for
\(\nu_v\)-almost every \(s\), which is precisely the conditional
signal law at \(V=v\).
If \(w_a=\nu_u(F_a)\), the logarithm of the moment bound is
\[
Cd+\log a+\log(1/w_a)+\log(1+d+\log K_u).
\]
Averaging, using
\(\mathbb E\log(1/w_a)=H(J\mid U)\), and applying Jensen once more,
we obtain
\begin{equation}\label{rlevels:one-actual-upper}
\mathbb E_P\log p_{\nu_V}(G,GS)
\le Cd+\mathbb E\log a+H(J\mid U)
+\log(1+d+H(U))+\frac{H(U)}q.
\end{equation}
The log expectations and the truncated use of
\eqref{rlevels:tilt} are justified by the integrability already
established.
Finally, \(\log a\le\log L_{\nu_U}(S)\), so the local-density terms
in \eqref{rlevels:one-independent-lower} and
\eqref{rlevels:one-actual-upper} cancel. Refinement gives
\[
\mathcal D(U)\le\mathcal D(V),\qquad
\widetilde{\mathcal D}(V)
\le\widetilde{\mathcal D}(U)+H(J\mid U).
\]
Combine these inequalities with \eqref{rlevels:one-density-comparison}
and \eqref{rlevels:one-label-entropy}. Since \(q\) is a fixed
positive fraction of \(d\) for large \(d\), the result is
\eqref{rlevels:one-comparison-bound}.
\end{proof}
\subsection{A comparison retaining the radius and the level}
\label{rlevels:two-level}
We now use more auxiliary rows and retain the first maximizing radius
as a second label. This lets a covering argument estimate the
independent entropy without the net-weight average above. In this
subsection the local parameters are
\begin{equation}\label{rlevels:two-parameters}
k=\lfloor d/2\rfloor,\qquad n=\lfloor d/8\rfloor,\qquad
l=k-n,\qquad q=n.
\end{equation}
Here \(n\) is the number of actual rows; the surface exponent remains
\(N=d-1\). In particular
\[
N-k\ge d/3,\qquad k-q-n\ge1,\qquad N-q-n\ge1
\]
for large \(d\).
For a finite variable \(V\) with \(S\sim\sigma\), let
\[
\mathcal J(V)=I_{\mathrm{ind}}(S;V\mid G,GS),
\qquad G\sim\gamma_k
\text{ independent of }(S,V).
\]
In the actual experiment \(A\sim\gamma_n\) is independent of
\(S\sim\sigma\), \(V\) has any joint law with \((S,A)\), and
\(B\sim\gamma_l\) is independent of \((S,A,V)\). Put
\(D=(A;B)\). Thus \(D\) is marginally independent of \(S\)
with law \(\gamma_k\), although its conditional law given
\((S,V)\) need not be Gaussian. The independent experiment defining
\(\mathcal J(V)\) preserves the actual \((S,V)\) marginal.
\begin{proposition}[Two-label auxiliary-row comparison]
\label{rlevels:two-comparison}
If \(V\) is finite and \(H(V)\le d^2\) in the preceding actual
experiment, then
\begin{equation}\label{rlevels:two-comparison-bound}
\mathcal J(V)\le I_{\mathrm{act}}(S;V\mid D,DS)+Cd.
\end{equation}
\end{proposition}
\begin{proof}
Let \(P\) denote the actual law. We first construct the refinement and obtain the two geometric
estimates it supplies. For \(\pi_v=P(V=v)>0\), write
\(\nu_v=P_{S\mid V=v}\le\pi_v^{-1}\sigma\), and define
\[
\lambda_v(s)=\max_{i\ge0} r_i^{-k}\nu_v(B(s,r_i)),
\qquad r_i=2^{1-i}.
\]
Let \(j\) be the first maximizing index and let
\(b=\lfloor\log_2\lambda_v(s)\rfloor\). The maximum is attained:
its \(i=0\) term is \(2^{-k}\), while
\(\pi_v^{-1}2^N r_i^{N-k}\) bounds the \(i\)-th term and tends
to zero. The ball-mass functions are Borel, so both labels are
measurable. The same bounds give
\[
b\ge-k,\qquad 2^b\le\pi_v^{-1}C^d,\qquad
2^{-k}\le\pi_v^{-1}C^d r_j^{N-k}.
\]
Because \(N-k\ge d/3\), the last inequality implies
\(j\le C(1+\log(1/\pi_v)/d)\). At fixed \(v\), the number of
pairs \((j,b)\) is at most \(C(d+1+\log(1/\pi_v))^2\).
For \(W=(V,j,b)\) evaluated at \(s=S\), this proves finiteness and
\begin{equation}\label{rlevels:two-label-entropy}
H(W\mid V)\le C+2\log(d+1+H(V)).
\end{equation}
For \(w=(v,j,b)\) with \(\pi_w=P(W=w)>0\), set \(R=r_j\).
Let \(E_w\) be the corresponding subset of the sphere, and write
\[
\nu_w=P_{S\mid W=w}
=\alpha_w\,\nu_v|_{E_w},\qquad
\alpha_w=\frac{\pi_v}{\pi_w}.
\]
Every \(s_0\in E_w\) satisfies
\[
\nu_v(B(s_0,R))\ge2^bR^k,\qquad
\nu_v(B(s_0,r_i))\le2^{b+1}r_i^k\quad(i\ge0).
\]
Choose centers in \(E_w\) successively at distances greater than
\(2R\) from those already chosen, until their \(2R\)-balls cover
\(E_w\). Their \(R\)-balls are disjoint and each has
\(\nu_v\)-mass at least \(2^bR^k\); hence the process stops with
at most \((2^bR^k)^{-1}\) centers. Assign each point to one of
its covering balls. Under the independent matrix \(G\), conditioning
also on this finite index adds at most
\(-b\log2-k\log R\) to the entropy. Within a ball, comparison with
a Gaussian of covariance \((2R)^2I_k\) adds at most
\(k\log R+Ck\), since
\(\mathbb E\|G(S-z)\|^2\le4kR^2\) for its center \(z\).
Consequently
\begin{equation}\label{rlevels:two-independent-entropy}
h_{\mathrm{ind}}(GS\mid G,W=w)\le-b\log2+Ck.
\end{equation}
The entropies are finite by Lemma~\ref{lem:r-projection-density}.
The same labels give, for all \(z\in\mathbb R^d\) and \(\rho>0\),
\begin{equation}\label{rlevels:two-two-powers}
\nu_w(B(z,\rho))
\le C_0^d\min\{U_w\rho^k,\ \Gamma_w\rho^N\},
\qquad U_w=\alpha_w2^b,\quad \Gamma_w=\pi_w^{-1}.
\end{equation}
For the first bound, choose a point of \(E_w\) in the ball when
there is one, double the radius, and use a dyadic radius in
\([2\rho,4\rho]\) if \(\rho\le1\). The upper ball bound at that
point and restriction by \(\alpha_w\) prove the assertion. For
larger \(\rho\), use total mass one and \(U_w\ge2^{-k}\).
The second bound follows from \(\nu_w\le\Gamma_w\sigma\) and
\eqref{rlevels:ambient-cap}. Notice that \(\alpha_w\ge1\),
\(\Gamma_w\ge1\), and \(U_w\ge2^{-k}\).
We next express the information difference in terms of exact projection
densities. Let \(Q\) denote the independent
law preserving \((S,W)\). Their \((D,S)\) and \((G,S)\)
marginals agree after identifying the matrices. Hence
\(h_Q(GS\mid G)=h_P(DS\mid D)\).
Proposition~\ref{prop:r-information-comparison} gives
\begin{equation}\label{rlevels:two-information-identity}
\mathcal J(W)-I_P(S;W\mid D,DS)
=h_Q(GS\mid G,W)-h_P(DS\mid D,W)-I_P(S;A\mid W).
\end{equation}
Here independence of \(B\) from \((S,A,W)\) reduces
\(I_P(S;D\mid W)\) to \(I_P(S;A\mid W)\).
Lemma~\ref{lem:r-projection-density} makes the baseline
and conditional entropies finite; it also gives the actual conditional
image density. Thus \eqref{rlevels:two-information-identity} is an
identity of finite quantities, with the displayed negative sign.
For a matrix \(D\), let \(p_{w,D}\) be a density of the image of
\(\nu_w\) under \(s\mapsto Ds\). This denominator uses
\(\nu_w=P_{S\mid W=w}\) before conditioning on the actual rows.
Contraction of
\[
\mathbb E D(P_{S\mid A,W}\Vert\nu_W)=I_P(S;A\mid W)
\]
under \(s\mapsto Ds\), with \(B\) still independent, gives
\begin{equation}\label{rlevels:two-cross-entropy}
-h_P(DS\mid D,W)-I_P(S;A\mid W)
\le \mathbb E_P\log p_{W,D}(DS).
\end{equation}
The numerator after contraction is the true conditional image density
given \((D,W)\). Its log ratio to \(p_{W,D}\) is integrable:
the relative entropy is finite, and the negative part of a log
likelihood ratio has expectation at most \(1/e\). Subtracting this
ratio from the integrable actual log density also proves integrability
of the right side.
Here we choose a density version that retains a bound at every fixed
target \(s\). For each positive integer \(a\), let
\(\varphi_\delta^a\) be the centered Gaussian density of covariance
\(\delta^2I_a\), and fix a sequence \(\delta_t\downarrow0\).
For any probability measure \(\nu\le K\sigma\), define
\[
F_\delta^\nu(g,s)
=\int\varphi_\delta^k(g(u-s))\,\nu(du),\qquad
p^\flat_\nu(g,y)
=\liminf_{t\to\infty}
\int\varphi_{\delta_t}^k(gu-y)\,\nu(du).
\]
These functions are measurable. For each full-rank \(g\), the
Gaussian approximate identity converges to the image density at its
Lebesgue points, so \(p^\flat_\nu(g,\cdot)\) is a density version.
It may be defined by a liminf on the exceptional set; this choice is
useful at a fixed target. It is valid in
\eqref{rlevels:two-cross-entropy}, since the actual conditional image
law is absolutely continuous.
There is a quantitative first-density passage under the independent
law, before taking logarithms. For independent \(G\sim\gamma_k\)
and \(S\sim\nu\), Gaussian integration and Tonelli give
\begin{align}
\mathbb E_{G,S}F_\delta^\nu(G,S)
&= (2\pi)^{-k/2}\iint
(\|u-s\|^2+\delta^2)^{-k/2}\,\nu(du)\nu(ds) \notag\\
&\le (2\pi)^{-k/2}\iint
\|u-s\|^{-k}\,\nu(du)\nu(ds)<\infty.
\label{rlevels:two-first-density}
\end{align}
The last integral is finite uniformly in \(s\): the diagonal has
zero mass, and the centered cap bound on dyadic shells gives
\[
\sup_{s\in S^{d-1}}\int\|u-s\|^{-k}\,\nu(du)
\le 1+K2^k\sum_{i\ge0}2^{-i(N-k)}<\infty.
\]
At \(GS\) the approximate identity converges almost surely under
the independent law, by absolute continuity of the image, Lebesgue
differentiation, and Fubini. Fatou in
\eqref{rlevels:two-first-density} therefore gives
\[
\mathbb E_{G,S}p^\flat_\nu(G,GS)
\le (2\pi)^{-k/2}\iint\|u-s\|^{-k}\,\nu(du)\nu(ds)<\infty.
\]
This proves the positive logarithmic part directly. For the negative
part compare with the standard Gaussian density \(\phi\) on
\(\mathbb R^k\): \(t(\log t)_-\le1/e\) bounds the negative part
of \(\log(p^\flat_\nu/\phi)\), and
\(\mathbb E\|GS\|^2=k\) bounds the cross entropy with \(\phi\).
This recovers independent log integrability for this density version.
Actual log integrability is supplied by the contraction preceding
\eqref{rlevels:two-cross-entropy}. In what follows take
\(p_{w,D}=p^\flat_{\nu_w}(D,\cdot)\). The mollifiers here only
specify and estimate densities at exact labels.
It remains to bound those densities under independent rows before
changing the law of \(A\). We claim that for every fixed
\(w\) of positive probability and every \(s\in S^{d-1}\),
\begin{equation}\label{rlevels:two-moment}
\left[\mathbb E_A
\bigl(\mathbb E_B p^\flat_{\nu_w}((A;B),(A;B)s)\bigr)^q
\right]^{1/q}
\le e^{Cd}U_w(1+\log\Gamma_w),
\end{equation}
where \(A\sim\gamma_n\) and \(B\sim\gamma_l\) are
independent in this displayed expectation. We prove the
uniform-in-\(\delta\) version first, with
\[
F_\delta(A,B,s)
=\int\varphi_\delta^k((A;B)(u-s))\,\nu_w(du).
\]
For \(h=u-s\),
\[
\mathbb E_B\varphi_\delta^l(Bh)
=(2\pi)^{-l/2}(\|h\|^2+\delta^2)^{-l/2}.
\]
Expanding the \(q\)-th power introduces \(u_1,\ldots,u_q\) and
\(h_i=u_i-s\). For their Gram matrix
\(K=(\langle h_i,h_j\rangle)_{i,j}\), Gaussian integration in the
\(n\) shared rows gives exactly
\[
\mathbb E_A\prod_{i=1}^q\varphi_\delta^n(Ah_i)
=(2\pi)^{-nq/2}\det(K+\delta^2I_q)^{-n/2}.
\]
Using \(\det(K+\delta^2I_q)\ge\det K\) and Gram--Schmidt,
we conclude
\begin{equation}\label{rlevels:two-gram}
\mathbb E_A\bigl(\mathbb E_B F_\delta(A,B,s)\bigr)^q
\le (2\pi)^{-kq/2}
\int\prod_{i=1}^q
\|u_i-s\|^{-l}\operatorname{dist}(u_i-s,L_{i-1})^{-n}
\,\nu_w^{\otimes q}(d\mathbf u),
\end{equation}
where \(L_{i-1}\) is the span of \(u_1-s,\ldots,u_{i-1}-s\),
starting with \(\{0\}\). An infinite upper bound is allowed at
singular Gram matrices. All integrations so far are nonnegative.
We bound the corresponding one-point integral uniformly over \(s\)
and every linear subspace \(L\) of dimension at most \(q\).
On a radial shell \(R/2<\|u-s\|\le R\), \(R=2^{1-i}\),
the part at distance at most \(2^{-a}R\) from \(L\) is covered
by at most \((3\cdot2^a)^q\) balls of radius \(2^{1-a}R\).
This follows by covering the radius-\(R\) projection ball in \(L\)
with a \(2^{-a}R\)-net. By \eqref{rlevels:two-two-powers} its
\(\nu_w\)-mass is at most
\[
C^d\min\{
U_w2^{-a(k-q)}R^k,\,
\Gamma_w2^{-a(N-q)}R^N\}.
\]
In particular the set at distance zero has zero mass. On the band
\(2^{-a-1}R<\operatorname{dist}(u-s,L)\le2^{-a}R\), the
integrand \(\|u-s\|^{-l}\operatorname{dist}(u-s,L)^{-n}\)
is at most \(2^k2^{an}R^{-k}\). Sum the transverse bands first.
The positive gaps \(k-q-n\) and \(N-q-n\) make both sums geometric,
so the integral on the radial shell is at most
\[
C^d\min\{U_w,\Gamma_wR^{N-k}\}.
\]
For the radial sum put \(a_0=N-k\ge d/3\). The sum of
\(\min\{1,(\Gamma_w/U_w)2^{a_0(1-i)}\}\) has at most
\(2+(\log_2(\Gamma_w/U_w))_+/a_0\) saturated terms followed by
a geometric tail. Since \(U_w\ge2^{-k}\) and
\(\Gamma_w\ge1\), this proves
\begin{equation}\label{rlevels:two-inverse}
\int\|u-s\|^{-l}\operatorname{dist}(u-s,L)^{-n}\,\nu_w(du)
\le e^{Cd}U_w(1+\log\Gamma_w).
\end{equation}
Integrate \eqref{rlevels:two-gram} from its last point to its first,
applying \eqref{rlevels:two-inverse} each time. This proves the
claimed bound uniformly in \(\delta\).
The liminf version now gives the exact fixed-target conclusion:
for every fixed \(s\),
\[
\mathbb E_Bp^\flat_{\nu_w}((A;B),(A;B)s)
\le\liminf_{t\to\infty}\mathbb E_BF_{\delta_t}(A,B,s)
\]
by Fatou in \(B\). Raise to the \(q\)-th power and apply Fatou
in \(A\). The uniform moment bound proves
\eqref{rlevels:two-moment}, including at targets where a density
version specified only almost everywhere would not have sufficed.
This is the distinct fixed-target passage used in this comparison.
We finally pay for dependence of the actual rows. Their conditional
relative entropies satisfy
\begin{equation}\label{rlevels:two-row-kl}
\mathbb E D(P_{A\mid S,W}\Vert\gamma_n)
=I_P(A;W\mid S)=I_P(A;V\mid S)\le H(V).
\end{equation}
Here \(A,S\) are marginally independent, and \(W\) adds only
a function of \((S,V)\). Given \((S,W,A)\), \(B\) is still
independent. Jensen in \(B\), followed by
\eqref{rlevels:tilt} for the true \(P_{A\mid S,W}\) relative to
\(\gamma_n\), uses \eqref{rlevels:two-moment} to give
\begin{equation}\label{rlevels:two-actual-upper}
\mathbb E_P\log p^\flat_{\nu_W}(D,DS)
\le \frac{H(V)}q+Cd+
\mathbb E\bigl[\log\alpha_W+b\log2+
\log(1+\log\Gamma_W)\bigr].
\end{equation}
Finite average divergence ensures the required absolute continuity.
Truncation permits the conditional inequality wherever a log
expectation is negative infinite; the integrated cross entropy is
finite by \eqref{rlevels:two-cross-entropy}.
The \(b\log2\) term cancels
\eqref{rlevels:two-independent-entropy} when substituted with
\eqref{rlevels:two-actual-upper} into
\eqref{rlevels:two-information-identity}--\eqref{rlevels:two-cross-entropy}.
Moreover
\[
\mathbb E\log\alpha_W=H(W\mid V),\qquad
\mathbb E\log(1+\log\Gamma_W)\le\log(1+H(W)).
\]
Removing the refinement costs another \(H(W\mid V)\), since
\[
\mathcal J(V)\le\mathcal J(W),\qquad
I_P(S;W\mid D,DS)\le I_P(S;V\mid D,DS)+H(W\mid V).
\]
Thus the full quantitative budget is
\begin{equation}\label{rlevels:two-budget}
\mathcal J(V)-I_P(S;V\mid D,DS)
\le Cd+\frac{H(V)}q+2H(W\mid V)+\log(1+H(W)).
\end{equation}
Only now use \(H(V)\le d^2\), \(q=\lfloor d/8\rfloor\), and
\eqref{rlevels:two-label-entropy}. They bound the right side by
\(Cd\), proving \eqref{rlevels:two-comparison-bound}.
\end{proof}
The applications of both comparisons, including their distinct residual-sphere constants, are proved in Subsection~\ref{rlevels:endpoints}.
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/04-density-levels.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/05-hybrids.tex ====
\section{Actual and fresh projections through independent kernels}
\label{rhyb:section}\label{sec:r-hybrids}
We compare the information in a block's incoming and ending states after
revealing independent auxiliary measurements of the same signal. The
comparison averages over the number of auxiliary rows.
We use the uniform-sphere experiment in
Definition~\ref{def:r-streaming-model} and the entropy conventions of
Section~\ref{sec:r-experiments}. Write \(\gamma=N(0,I_d)\) for
the law of a single row. All intermediate lemmas concern the
fixed-seed experiment supplied by Lemma~\ref{lem:r-seed-reduction}
and the Borel reduction in Lemma~\ref{lem:r-borel-kernels}; in
particular initialization remains jointly independent of the signal
and all rows. Transitions may use fresh randomness, and the terminal
output uses only its state and index. Auxiliary rows are analysis
variables, independent of the joint signal and learner variables as
specified below. Constants \(c,C>0\) are absolute and may increase.
The estimates are for sufficiently large integer \(d\).
For a nonnegative integer \(j\), write \(D'_j=(Z,ZS)\) for \(j\) fresh
measurements. The matrix \(Z\) is independent of the joint vector consisting of the
signal and all learner variables already generated; \(D'_0\) is empty. Set
\begin{equation}\label{rhyb:parameters}
k_0=\lceil d/4\rceil,\qquad k_1=\lfloor d/2\rfloor,\qquad
N_k=k_1-k_0+1,\qquad h_0=\lfloor d/8\rfloor,\qquad
q=\lfloor d/32\rfloor.
\end{equation}
For a finite state \(V\), with fresh rows independent of \((S,V)\), define
\begin{equation}\label{rhyb:potential}
J_k(V)=I(S;V\mid D'_k),\qquad
\overline J(V)=\frac1{N_k}\sum_{k=k_0}^{k_1}J_k(V).
\end{equation}
These quantities are finite and nonnegative because they are at most
\(H(V)\).
Consider a block of \(1\le m\le h_0\) actual observations, with incoming
state \(U\) and ending state \(V\). Assume \(H(V)\le B<\infty\).
The block rows \(X_1,\ldots,X_m\) are independent of \((S,U)\). The
block transition produces \(V\) from \(U\) and the block data by a
measurable kernel, conditionally independently of \(S\).
\begin{proposition}[Averaged information increase per block]
\label{rhyb:block}
For the block above, with \(1\le m\le h_0\) and \(H(V)\le B\),
\begin{equation}\label{rhyb:block-cost}
\overline J(V)-\overline J(U)
\le Cm+\frac{m}{N_k}\left(C+\frac{B}{h_0}\right)+\frac{B}{q}.
\end{equation}
When \(B\le d^2\), the right side is at most \(C'd\) for an absolute
constant \(C'\).
\end{proposition}
Keeping \(V\) as produced by the actual block, replace fresh auxiliary
rows one at a time by rows the learner actually saw. Conditioning on the
ending state can bias an actual row; the total row-information cost is at
most \(H(V)\).
Independent random kernels control the accompanying entropy cost, and
averaging over the auxiliary count reduces the difference of successive
conditional entropies to two endpoint terms.
\subsection{Residual geometry and finite label entropies}
The following residual-sphere estimates justify the entropy subtractions
and will also normalize the row comparison.
\begin{lemma}[Residual-sphere estimates]\label{rhyb:residual}
Let \(D_j=(X,XS)\) consist of \(j\) independent Gaussian measurements,
where \(0\le j<d\), and put \(n=d-j\). Conditional on \(D_j\), the signal
is uniform on a sphere of radius \(R\) in the affine solution space.
Marginally,
\begin{equation}\label{rhyb:radius}
R^2\stackrel{\mathrm{law}}=
\frac{G_n}{G_n+G_j},
\qquad
\mathbb E R^{-2}=1+\frac{j}{n-2}\quad(n>2),
\end{equation}
where \(G_n,G_j\) are independent chi-squared variables and \(G_0=0\).
If \(j\le 3d/4\), the entropy of one further label given its row and
\(D_j\) lies between two absolute constants, and its conditional log
density is absolutely integrable. Joint label entropies, and the
conditional label entropies obtained by also conditioning on a finite
state \(V\), are finite whenever the total number of rows is at most
\(3d/4\). The associated conditional log densities are absolutely
integrable. Removing \(V\) can increase any such joint entropy by at
most \(H(V)\).
Let \(\sigma_R\) be uniform probability on a sphere of radius \(R>0\) in an
\(n\)-dimensional affine space. A Euclidean ball of radius \(a\) with
arbitrary center has \(\sigma_R\)-mass at most
\((2a/R)^{n-1}\) when \(2a/R\le 1/2\). For \(n\ge3\),
\begin{equation}\label{rhyb:reciprocal-sphere}
\sup_{s\in\operatorname{supp}\sigma_R}
\int\frac{\sigma_R(dt)}{\|t-s\|}
\le \frac{C}{R}.
\end{equation}
\end{lemma}
\begin{proof}
The rows have full rank almost surely. Their labels determine the
row-space component of \(S\). Rotational invariance makes the remaining
direction uniform in the kernel, conditionally on its length and the
data. Representing a uniform sphere point as a standard Gaussian vector
divided by its norm proves the ratio law in \eqref{rhyb:radius}.
For \(n>2\), independence and the chi-squared density give
\(\mathbb E G_n^{-1}=1/(n-2)\) and \(\mathbb E G_j=j\), proving the inverse
moment.
Let \(P\) be projection onto the kernel and let \(x\) be a new row.
Conditional on \(D_j,x\), the new label is a fixed shift plus
\[
R\|Px\|U_1,
\]
where \(U\) is uniform on \(S^{n-1}\). The density of \(U_1\) is
proportional to \((1-u^2)^{(n-3)/2}\) on \((-1,1)\). Its normalizing
integral is at least \(c/\sqrt n\), by integrating over
\(|u|\le1/\sqrt n\). For the dimensions in use this density is at most
\(C\sqrt n\), and hence
\[
h(U_1)\ge-\log(C\sqrt n).
\]
Its log density is integrable: near an endpoint this is the
integrability of \(t^\alpha|\log t|\) for \(\alpha>-1\).
Also \(\|Px\|^2\) is chi-squared with \(n\) degrees of freedom.
For \(j\le3d/4\), the inverse moments of \(R\) and \(\|Px\|/\sqrt n\)
are bounded by absolute constants. Jensen's inequality gives, for
example,
\[
\mathbb E\log R\ge-\tfrac12\log\mathbb E R^{-2}\ge-C,
\qquad
\mathbb E\log(\|Px\|/\sqrt n)\ge-C.
\]
Ordinary positive moments control the positive logarithmic parts.
The entropy formula under scaling now gives an absolute lower bound for
the conditional entropy of the next label. The upper bound is
\(\tfrac12\log(2\pi e)\), the entropy of its marginal standard normal
law. These calculations also give absolute integrability of the
conditional log density. Applying the chain rule in any order gives
the same conclusion for all ordered subsets of labels with the stated
row budget. Extra independent rows may be conditioned on before \(V\)
is added, since they do not change these baseline distributions.
Adding the finite state reduces a joint label entropy by a conditional
mutual information at most \(H(V)\). To check absolute integrability as
well, let \(r=dQ/dP\) be the density ratio of the conditional joint law
to its product-of-conditionals reference law. The negative part of
\(\int\log r\,dQ\) is at most \(1/e\), because
\(-r\log r\le1/e\) for \(0<r\le1\). Finite relative entropy therefore
also makes the positive part integrable. The log density after
conditioning on \(V\) is the baseline log density plus this integrable
log ratio. All label-entropy chain rules just used are consequently
between finite quantities.
For \(n=1\) the cap bound is the trivial bound one. For \(n\ge2\), first
scale to \(R=1\) and center the ball at a
sphere point. If its radius is \(a\le1/2\), its projection onto the
tangent coordinate plane lies in an \((n-1)\)-ball of radius \(a\).
The graph area factor there is at most \(2\), while the whole sphere
has area at least twice the volume of the unit \((n-1)\)-ball.
The cap has mass at most \(a^{n-1}\). For an arbitrary center, choose a
sphere point in the intersection, if one exists, and double the radius.
This proves the displayed arbitrary-center bound.
Finally, for a sphere point \(s\), integrate the centered cap estimate
against \(t^{-2}\,dt\) for \(0<t\le R/2\); the integral is bounded by
\[
R^{-(n-1)}\int_0^{R/2}t^{n-3}\,dt\le C/R
\]
when \(n\ge3\). The part with \(t>R/2\) is at most \(C/R\) using total
mass one. The layer-cake formula for \(\|t-s\|^{-1}\) proves
\eqref{rhyb:reciprocal-sphere}.
\end{proof}
\subsection{A block reduction and its row-information cost}
For this block, write
\[
X_{\le i}=(X_1,\ldots,X_i),\qquad
Y_{\le i}=X_{\le i}S,\qquad
D_i=(X_{\le i},Y_{\le i}),\qquad L_i=(V,D_i)
\]
for \(0\le i\le m\), with the evident empty tuples at \(i=0\).
The rows are Gaussian before conditioning on \(V\); their conditional
laws after \(V\) is known need not be Gaussian.
For an independent sequence of fresh rows \(z_1,z_2,\ldots\), define the
successive conditional entropies
\begin{equation}\label{rhyb:slopes}
a_j^{(i)}
=h(z_jS\mid z_j,D'_{j-1},L_i),
\qquad j\ge1,\quad i+j\le3d/4.
\end{equation}
All the entropies used below have a total row count at most \(3d/4\), so
Lemma~\ref{rhyb:residual} applies.
\begin{lemma}[One-row hybrid identity]\label{rhyb:hybrid}
For \(k_0\le k\le k_1\) and \(0\le i\le m\), let \(Z^{(i,k)}\) be a fresh
matrix of \(k-i\) rows and define
\[
G_i(k)=
h\bigl((Y_{\le i},Z^{(i,k)}S)\mid X_{\le i},Z^{(i,k)},V\bigr)
+I(S;X_{\le i}\mid V).
\]
For \(i<m\), put \(x=X_{i+1}\), \(Y=xS\), \(L=L_i\), and \(r=k-i-1\).
With \(F_r=(Z,ZS)\) denoting common fresh data of size \(r\),
\begin{equation}\label{rhyb:hybrid-step}
G_i(k)-G_{i+1}(k)
=a_{r+1}^{(i)}
-\bigl[h(Y\mid x,F_r,L)+I(S;x\mid F_r,L)\bigr].
\end{equation}
The actual-row divergence costs are
\begin{align}
K_i&:=\mathbb E D_{\rm KL}
\bigl(\mathcal L(X_{i+1}\mid S,L_i)\,\|\,\gamma\bigr)
=I(X_{i+1};V\mid S,X_{\le i}),\label{rhyb:row-cost}\\
\sum_{i=0}^{m-1}K_i
&=I(X_1,\ldots,X_m;V\mid S)\le H(V)\le B.\label{rhyb:row-budget}
\end{align}
Finally,
\begin{equation}\label{rhyb:block-reduction}
J_k(V)\le J_k(U)+G_0(k)-G_m(k).
\end{equation}
\end{lemma}
\begin{proof}
We first relate \(G_i(k)\) to conditional information without
subtracting differential entropies of the singular signal. Suppose
\(D=(A,AS)\) has the marginal law of \(k\) independent Gaussian
measurements, although its rows may have helped produce \(V\). The
conditional relative-entropy chain rule gives
\[
I(S;V\mid D)-I(S;V)=I(D;V\mid S)-I(D;V).
\]
Every term here is finite, being bounded by \(H(V)\). The labels are
determined by \(A,S\), and \(A\) is marginally independent of \(S\).
Expanding the finite terms involving \(V\) therefore yields
\begin{equation}\label{rhyb:information-identity}
I(S;V\mid D)=I(S;V)-h(AS\mid A)+h(AS\mid A,V)+I(S;A\mid V).
\end{equation}
The label entropies are finite by Lemma~\ref{rhyb:residual}.
In a hybrid, the fresh rows contribute zero to the last mutual
information. All hybrids have the same baseline entropy \(h(AS\mid A)\).
Thus
\[
J_k(V)-I(S;V\mid D_m,D'_{k-m})=G_0(k)-G_m(k).
\]
Given \(D_m,D'_{k-m}\), the block transition is a Markov kernel from
\(U\) to \(V\), conditionally independently of \(S\). Conditional
data processing gives
\[
I(S;V\mid D_m,D'_{k-m})
\le I(S;U\mid D_m,D'_{k-m})=J_k(U).
\]
The equality holds because these \(k\) rows are fresh relative to
\((S,U)\). This proves \eqref{rhyb:block-reduction}.
For the one-row identity, realize the two adjacent hybrids using the
same \(r\) fresh rows \(Z\), one further fresh row for \(G_i(k)\), and
the actual row \(x\) for \(G_{i+1}(k)\). Expand the labels in the order
\(Y_{\le i},ZS,\text{last label}\). Before the last row is added the
common part is
\[
h(Y_{\le i}\mid X_{\le i},V)
+I(S;X_{\le i}\mid V)+h(ZS\mid Z,L).
\]
The remaining term for \(G_i(k)\) is \(a_{r+1}^{(i)}\).
For \(G_{i+1}(k)\), conditioning the first two label groups on the
actual row subtracts, respectively,
\[
I(Y_{\le i};x\mid X_{\le i},V)
\quad\hbox{and}\quad I(ZS;x\mid Z,L).
\]
Its new row-information term is initially
\(I(S;x\mid X_{\le i},V)\). The first subtraction leaves \(I(S;x\mid L)\),
because the old labels are determined by \(S,X_{\le i}\).
The second leaves \(I(S;x\mid F_r,L)\): the fresh matrix \(Z\) is
independent, and \(ZS\) is determined by \(S,Z\). The last label then
contributes \(h(Y\mid x,F_r,L)\). This proves \eqref{rhyb:hybrid-step}
and retains both earlier-label subtractions.
Conditional on \(S,X_{\le i}\), the unconditioned law of \(X_{i+1}\)
is \(\gamma\), and the labels in \(L_i\) are redundant. The definition
of conditional mutual information proves \eqref{rhyb:row-cost}.
Summing it is the conditional chain rule for \(X_1,\ldots,X_m\).
The resulting information is at most \(H(V)\), proving
\eqref{rhyb:row-budget}. In particular the conditional actual-row
laws have finite divergence from \(\gamma\) almost surely.
\end{proof}
The identity has isolated the issue caused by conditioning on \(V\).
We next lower-bound the bracket in \eqref{rhyb:hybrid-step}. Its reference
posterior will exclude the actual row, and the change from a Gaussian
row to the actual row will be charged through \(K_i\).
\subsection{Independent kernels and the biased-row comparison}
Two signals giving the same fresh labels differ by a vector in the
fresh matrix's kernel. The posterior will select such directions
nonuniformly, so we need an inverse-volume estimate that holds for every
selection rule allowed below.
\begin{lemma}[Inverse volumes for independent kernels]
\label{rhyb:inverse-volume}
Let \(r,q\) be integers satisfying
\[
d/8\le r<d,\qquad 1\le q\le r/2,\qquad r-q\ge2.
\]
Generate independent standard Gaussian \(r\)-by-\(d\) matrices
\(Z_1,\ldots,Z_q\). After generating \(Z_j\), select a unit vector
\(u_j\in\ker Z_j\) by a probability kernel that may depend on \(Z_j\)
and all preceding matrices and selections, but not on future matrices.
Then
\begin{equation}\label{rhyb:volume-moment}
\mathbb E\,\operatorname{vol}(u_1,\ldots,u_q)^{-1}\le C^q,
\end{equation}
uniformly over all such selection kernels. In particular the volume
is positive almost surely.
\end{lemma}
\begin{proof}
Fix a previous span \(P\) of dimension \(p<q\), and let \(E\) be the row
space of the next matrix. When \(p>0\), set
\[
\xi(P,E)=\inf_{\substack{v\in P\\\|v\|=1}}\|P_Ev\|,
\]
and set \(\xi=1\) for \(p=0\). An operator and its adjoint have the same
norm, so
\(\|P_P|_{E^\perp}\|=\|P_{E^\perp}|_P\|\). For \(p>0\), taking
complements of their squared norms shows, for every unit \(u\in E^\perp\),
that
\begin{equation}\label{rhyb:adjoint}
\operatorname{dist}(u,P)^2
\ge1-\|P_P|_{E^\perp}\|^2
=\inf_{\substack{v\in P\\\|v\|=1}}\|P_Ev\|^2
=\xi(P,E)^2.
\end{equation}
For \(p=0\), both the distance and \(\xi\) equal one, so all the bounds
below are immediate. We may therefore assume \(p>0\) in the small-ball
calculation.
The new \(E\) is a uniform \(r\)-dimensional subspace independent of
the preceding selections. For a fixed unit \(v\) and \(0<t\le1/4\),
\begin{equation}\label{rhyb:fixed-vector-small-ball}
\mathbb P\{\|P_Ev\|\le2t\}\le(Ct)^r.
\end{equation}
Indeed \(\|P_Ev\|\) has the distribution of
\(\|g\|/(\|g\|^2+\|g'\|^2)^{1/2}\), with independent standard Gaussian
vectors of dimensions \(r\) and \(d-r\). The event forces
\(\|g\|\le Ct\|g'\|\). The Gaussian integral, restricted to the ball
of radius \(\sqrt r\), gives
\((2\pi)^{r/2}\ge e^{-r/2}v_r r^{r/2}\), hence
\(v_r\le(C/\sqrt r)^r\). Conditional on \(g'\), this volume estimate
and the Gaussian density bound make its probability at most
\((Ct\|g'\|/\sqrt r)^r\).
For \(z\ge0\),
\[
z^{r/2}\le(2r/e)^{r/2}e^{z/4},
\qquad
\mathbb E e^{\|g'\|^2/4}=2^{(d-r)/2}.
\]
Since \(r\ge d/8\), these estimates give
\(\mathbb E\|g'\|^r\le(C\sqrt d)^r\). Averaging proves
\eqref{rhyb:fixed-vector-small-ball}.
A maximal \(t\)-separated subset of the unit sphere in \(P\) is a
\(t\)-net with at most \((1+2/t)^p\le(3/t)^p\) points, by packing
disjoint balls of radius \(t/2\) in the ball of radius \(1+t/2\).
Projection is a contraction, so \(\xi\le t\) puts some net point at
projection distance at most \(2t\). By \eqref{rhyb:fixed-vector-small-ball},
\begin{equation}\label{rhyb:subspace-small-ball}
\mathbb P\{\xi\le t\}\le(3/t)^p(Ct)^r
\le(C_0t)^{r-p},\qquad 0<t\le1/4.
\end{equation}
Here \(C_0\) is absolute because \(p<q\le r/2\).
Choose a fixed \(t_0\le1/4\) such that \(C_0t_0\le1/2\).
Since \(r-p>1\), integration of \eqref{rhyb:subspace-small-ball} gives
\[
\mathbb E\xi^{-1}
=1+\int_0^1\mathbb P\{\xi<t\}\,\frac{dt}{t^2}
\le C.
\]
For \(t\ge t_0\), the trivial probability bound suffices.
The estimate is uniform in the preceding span \(P\).
Gram--Schmidt expresses the volume as the product of distances from
successive preceding spans. Conditional on all previous selections,
the \(p=0\) observation and \eqref{rhyb:adjoint} bound the reciprocal of
the next distance by
\(\xi^{-1}\), whatever vector the new kernel selects. The new row space
is still independent of that history. Iterated conditional expectation
therefore bounds the inverse-volume product by \(C^q\), and also shows
that none of the distances vanishes with positive probability.
\end{proof}
Return to a fixed \(i,k\) in Lemma~\ref{rhyb:hybrid}. Thus
\(x=X_{i+1}\), \(L=(V,D_i)\), \(r=k-i-1\), and \(F_r=(Z,ZS)\) is fresh.
Define the reference posterior and its reciprocal-distance scale by
\begin{equation}\label{rhyb:reciprocal-scale}
\mu=\mathcal L(S\mid L,F_r),
\qquad
A(s,L,F_r)=\int\frac{\mu(ds')}{\|s'-s\|}.
\end{equation}
The posterior \(\mu\) includes the ending state but does not condition on
the actual row \(x\). This distinction is essential: we will compare the
actual conditional law of \(x\) with a Gaussian row.
\Needspace{6\baselineskip}
\begin{lemma}[A row biased by the ending state]\label{rhyb:row-comparison}
In the preceding experiment, \(A(S,L,F_r)\ge1/2\) almost surely and
\(\mathbb E A(S,L,F_r)<\infty\) for each fixed \(d\). For almost every
Gaussian row \(x\), the projection of \(\mu\) by \(s\mapsto xs\) has a
Lebesgue density \(p_{\mu,x}\). With \(q=\lfloor d/32\rfloor\),
\begin{align}
h(xS\mid x,L,F_r)+I(S;x\mid L,F_r)
&\ge-\mathbb E\log p_{\mu,x}(xS),\label{rhyb:cross-entropy}\\
\mathbb E\log\frac{p_{\mu,x}(xS)}{A(S,L,F_r)}
&\le C+\frac{K_i}{q}.\label{rhyb:row-log-bound}
\end{align}
Both expectations use the actual row law. The logarithms in these
displays are absolutely integrable.
\end{lemma}
\begin{proof}
Conditional on \(D_i,F_r\), before \(V\) is imposed, the signal is uniform
on a residual sphere of affine dimension
\[
n=d-i-r=d-k+1>2.
\]
For a state \(v\) with
\(\pi_v=\mathbb P\{V=v\mid D_i,F_r\}>0\), its posterior density relative
to the uniform residual law is at most \(1/\pi_v\). This follows directly
from Bayes' formula, since the conditional probability of \(V=v\) given
the signal and these data is at most one. Lemma~\ref{rhyb:residual}
therefore gives
\[
A(s,L,F_r)\le\frac{C}{R\pi_v}
\]
for every point \(s\) on the residual sphere. Average first over \(s\)
and \(v\). The factor \(\pi_v\) cancels, and the sum has at most \(W\)
terms if \(V\) has at most \(W\) values. Consequently
\begin{equation}\label{rhyb:scale-integrability}
\mathbb E A(S,L,F_r)\le CW\,\mathbb E R^{-1}<\infty.
\end{equation}
The inverse moment in \eqref{rhyb:radius} proves the last inequality.
Every pairwise distance on the unit sphere is at most two, giving
\(A\ge1/2\). In particular \(\log A\) is absolutely integrable.
The posterior is nonatomic and is absolutely continuous relative to the
uniform residual law. For every row whose projection into the residual
kernel is nonzero, the projection of that uniform law has a Lebesgue
density, by the one-coordinate formula in Lemma~\ref{rhyb:residual}.
The exceptional rows have Gaussian measure zero. Absolute continuity
passes to the projected posterior, proving the assertion about
\(p_{\mu,x}\).
The information cost of conditioning this posterior on \(x\) is finite.
Indeed \(x\) and \(F_r\) are conditionally
independent given \(S,L\), so the conditional chain rule yields
\[
I(S;x\mid L)-I(S;x\mid L,F_r)=I(x;F_r\mid L)\ge0.
\]
Also the chain rule for the relative entropy in \(K_i\) gives
\[
K_i=I(S;x\mid L)+
\mathbb E D_{\rm KL}\bigl(\mathcal L(x\mid L)\,\|\,\gamma\bigr).
\]
Thus
\begin{equation}\label{rhyb:information-charge}
I(S;x\mid L,F_r)\le I(S;x\mid L)\le K_i.
\end{equation}
The conditional actual law of \(S\) given \(x,L,F_r\) is therefore dominated
by \(\mu\) almost surely. Projecting by \(s\mapsto xs\) contracts its
relative entropy, so the actual projected law is dominated by the
reference projected law with expected divergence at most
\(I(S;x\mid L,F_r)\). Lemma~\ref{rhyb:residual} supplies an integrable
log density for the actual conditional label. Applying the
log-density-ratio argument from that lemma to the finite projected
divergence shows that \(\log p_{\mu,x}(xS)\) is absolutely integrable
as well. We may now expand the projected divergence:
\[
-\mathbb E\log p_{\mu,x}(xS)-h(xS\mid x,L,F_r)
\le I(S;x\mid L,F_r).
\]
This is \eqref{rhyb:cross-entropy}.
It remains to prove \eqref{rhyb:row-log-bound}. Fix a typical pair
\((s,L)\) under the joint law of \((S,L)\). Generate \(q\) independent
copies \(Z_1,\ldots,Z_q\) of the \(r\) fresh rows, and put
\(F^{(j)}=(Z_j,Z_js)\). Let \(\mu_j,A_j\) be the corresponding
posterior and scale from \eqref{rhyb:reciprocal-scale}. Initially let
\(x\sim\gamma\) be independent of all these matrices. We claim
\begin{equation}\label{rhyb:product-moment}
\mathbb E_{Z_1,\ldots,Z_q,x}
\prod_{j=1}^q\frac{p_{\mu_j,x}(xs)}{A_j}\le C^q.
\end{equation}
For \(\delta>0\), replace the density in the \(j\)-th factor by its
symmetric slab average
\[
p^\delta_{\mu_j,x}(xs)
=\frac{1}{2\delta}
\mu_j\{s':|x(s'-s)|\le\delta\}.
\]
Draw \(s'_j\) separately from \(\mu_j\), and write
\(\Delta_j=s'_j-s\), \(u_j=\Delta_j/\|\Delta_j\|\). The posteriors are
nonatomic, so the differences are nonzero almost surely. Conditional on
these differences, the vector
\((x\Delta_1,\ldots,x\Delta_q)\) is Gaussian. Its density is bounded by
\begin{equation}\label{rhyb:gaussian-density}
(2\pi)^{-q/2}
\prod_{j=1}^q\|\Delta_j\|^{-1}
\operatorname{vol}(u_1,\ldots,u_q)^{-1};
\end{equation}
we may use \(+\infty\) for a singular tuple. This is the usual Gaussian
density bound with covariance matrix
\((\langle\Delta_j,\Delta_\ell\rangle)_{j,\ell}\).
Its probability in \([-\delta,\delta]^q\) is at most
\eqref{rhyb:gaussian-density} times \((2\delta)^q\).
After division by \(\prod_j A_j\), nonnegative integration converts the
resulting bound into \((2\pi)^{-q/2}\) times an inverse-volume expectation.
Conditional on each \(Z_j\), the selected point in that expectation has
the probability law
\begin{equation}\label{rhyb:normalized-kernel}
\nu_j(ds')=\frac{\mu_j(ds')}{\|s'-s\|A_j}.
\end{equation}
Each law is normalized by its own \(A_j\). Its total mass is one for
every typical \(Z_j\), so the marginal law of the matrices remains the
product of their original Gaussian laws. In particular the matrices
have not been tilted. Both \(s\) and \(s'_j\) satisfy the labels \(Z_js\);
therefore \(u_j\in\ker Z_j\). These selections, made separately
conditional on their matrices and \((s,L)\), satisfy the hypotheses of
Lemma~\ref{rhyb:inverse-volume}. Indeed
\[
r=k-i-1\ge k_0-h_0\ge d/8,\qquad q\le r/2,\qquad r-q\ge2
\]
for sufficiently large \(d\). The lemma bounds the smoothed product
expectation by \(C^q\), uniformly in \(\delta\).
Here is a density version that makes passage to exact evaluations
legitimate. In the unbiased one-copy experiment, \(x\) is independent
of \((S,L,F_r)\), so conditional on \(L,F_r,x\), the signal has law
\(\mu\). The one-dimensional Lebesgue differentiation theorem applied
to the integrable density \(p_{\mu,x}\) shows that \(xS\) is almost surely
a Lebesgue point and that the symmetric slab averages converge to
\(p_{\mu,x}(xS)\). Each slab average is jointly measurable in its
kernel parameters and evaluation point. Taking its limit along
\(\delta=2^{-n}\), and assigning zero when no finite limit exists,
therefore gives a jointly measurable density version that agrees at
these evaluations. Fubini's theorem gives the same assertion for
almost every fixed \((s,L)\). For such a pair it holds simultaneously
for all \(q\) copies, since \(q\) is finite. Fatou's lemma now proves
\eqref{rhyb:product-moment}.
Change only \(x\) from its unbiased law to its actual conditional law
given \(S=s,L\). The \(Z_j\) remain independent of it and of one
another. The divergence from the unbiased product experiment is
exactly
\(D_{\rm KL}(\mathcal L(x\mid s,L)\,\|\,\gamma)\).
For probability laws \(Q\ll P\) and a nonnegative function \(g\), the
entropy variational inequality gives
\begin{equation}\label{rhyb:entropy-inequality}
\mathbb E_Q\log g
\le D_{\rm KL}(Q\|P)+\log\mathbb E_P g.
\end{equation}
For positive bounded \(g\) this follows from Jensen's inequality applied
to \(g/(dQ/dP)\); truncation gives the extended form. This is the
standard variational identity recorded in
\cite[Equations~(1.1)--(1.2)]{DupuisMao2022}.
Apply it to the product in \eqref{rhyb:product-moment}.
Finite row divergence transfers the unbiased almost-sure density
statements to the actual law. The logarithms are integrable by
\eqref{rhyb:cross-entropy} and \eqref{rhyb:scale-integrability}.
The expectation of the log product is \(q\) times the one-copy
expectation, since the \(q\) fresh copies have the same marginal law.
Divide by \(q\) and average over \((S,L)\). Equation
\eqref{rhyb:row-cost} then gives \eqref{rhyb:row-log-bound}.
\end{proof}
The independent-kernel estimate bounds the actual projected density at
the scale \(A\). To compare this scale to a fresh conditional entropy,
we use two fresh rows after the \(r\) common rows. The second of the two
is the next slope beyond the one already present in the hybrid identity.
\subsection{A reciprocal-distance tilt and two fresh rows}
\begin{lemma}[The next fresh entropy slope]\label{rhyb:tilted-coupling}
For the posterior and scale in \eqref{rhyb:reciprocal-scale},
\begin{equation}\label{rhyb:next-slope}
a_{r+2}^{(i)}\le-\mathbb E\log A(S,L,F_r)+C.
\end{equation}
\end{lemma}
\begin{proof}
Write \(C_*=(L,F_r)\). Conditional on \(C_*\), the signal has law
\(\mu\). For an integer \(N\ge1\), define
\[
w_N(s,t)=\min\{N,\|t-s\|^{-1}\},\qquad
A_N(s,C_*)=\int w_N(s,t)\,\mu(dt),
\]
where \(w_N(s,s)=N\). Given \(S=s,C_*\), draw an auxiliary point \(S^*\)
from the probability kernel
\[
\nu_s^N(dt)=\frac{w_N(s,t)}{A_N(s,C_*)}\,\mu(dt).
\]
Distances on the unit sphere are at most two, so
\(1/2\le A_N\le N\) and \(d\nu_s^N/d\mu\le2N\).
The marginal law of \(S^*\) need not equal \(\mu\).
Compare the joint conditional law of \((S,S^*)\) with
\(\mu\otimes\mu\). Its divergence is
\[
\mathbb E\log\frac{w_N(S,S^*)}{A_N(S,C_*)}.
\]
The relative-entropy chain rule splits this into
\(I(S;S^*\mid C_*)\) plus the divergence of the
actual \(S^*\) marginal from the comparator \(\mu\). Hence
\begin{align}
I(S;S^*\mid C_*)
&\le\mathbb E\log\frac{w_N(S,S^*)}{A_N(S,C_*)}\notag\\
&\le-\mathbb E\log\|S-S^*\|
-\mathbb E\log A_N(S,C_*).\label{rhyb:tilt-information}
\end{align}
The comparator divergence is finite, at most \(\log(2N)\).
The points differ almost surely because \(\mu\) is nonatomic.
Their log distance is absolutely integrable: its positive part is at
most \(\log2\); under \(\mu\otimes\mu\) its negative part is bounded by
an integrable multiple of \(\|S-S^*\|^{-1}\) by
\eqref{rhyb:scale-integrability}, and the tilted density is at most \(2N\).
Thus both inequalities in \eqref{rhyb:tilt-information} are between
well-defined finite quantities.
After drawing \(S^*\), generate independent fresh Gaussian rows
\(x_1,x_2\) and labels \(b_1=x_1S\), \(b_2=x_2S\).
Before \(S^*\) is added to the conditioning,
Lemma~\ref{rhyb:residual} gives a joint conditional density with an
integrable logarithm for these labels, since
\(i+r+2=k+1\le3d/4\). Fresh-row independence and data processing give
\begin{align}
I(b_2;S^*\mid b_1,x_1,x_2,C_*)
&\le I((b_1,b_2);S^*\mid x_1,x_2,C_*)\notag\\
&\le I(S;S^*\mid C_*).\label{rhyb:remove-coupling}
\end{align}
This is finite. The log-density-ratio argument from
Lemma~\ref{rhyb:residual} consequently gives integrable conditional log
densities after \(S^*\) is added, both for the joint labels and for the
first label. Their entropy chain rule justifies the conditional entropy
of the second label used next.
Given \(b_1,x_1,x_2,C_*,S^*\), compare the density of \(b_2\) with the Cauchy
density centered at \(x_2S^*\) and with scale
\(|b_1-x_1S^*|\). The scale is positive almost surely. With
\(\Delta=S-S^*\), the expected negative log of this reference density
at \(b_2\) is
\begin{align}
&\log\pi+\mathbb E\log|x_1\Delta|
+\mathbb E\log\left(1+\frac{(x_2\Delta)^2}{(x_1\Delta)^2}\right)
\notag\\
&\hspace{35mm}=\mathbb E\log\|\Delta\|+C_1,\label{rhyb:cauchy}
\end{align}
where \(C_1\) is absolute. Conditional on nonzero \(\Delta\), the two
projections divided by \(\|\Delta\|\) are independent standard normals
\(G_1,G_2\). The first logarithm is integrable because
\(\mathbb E|\log|G_1||<\infty\). For the ratio term,
\[
\log\bigl(1+(G_2/G_1)^2\bigr)
=\log(G_1^2+G_2^2)-\log G_1^2,
\]
and both logarithms on the right are integrable by the one- and
two-dimensional chi-squared densities. The cross-entropy inequality
therefore gives
\[
h(b_2\mid b_1,x_1,x_2,C_*,S^*)
\le\mathbb E\log\|\Delta\|+C_1.
\]
Removing \(S^*\) from the conditioning in this entropy bound and using
\eqref{rhyb:tilt-information}--\eqref{rhyb:remove-coupling} cancels
\(\mathbb E\log\|\Delta\|\). We obtain
\[
h(b_2\mid b_1,x_1,x_2,C_*)\le-\mathbb E\log A_N(S,C_*)+C_1.
\]
The left side is exactly \(a_{r+2}^{(i)}\) and is independent of \(N\).
Finally \(A_N\uparrow A\) and \(\log A_N\ge-\log2\).
Monotone convergence, with the integrability of \(\log A\) already
proved, yields \eqref{rhyb:next-slope}.
\end{proof}
\subsection{Averaging over the number of side measurements}
The row comparison and the two-row coupling now leave only a difference
of consecutive fresh entropy slopes. Averaging over consecutive values
of \(k\) makes this difference telescope.
\begin{proof}[Proof of Proposition~\ref{rhyb:block}]
Equations~\eqref{rhyb:cross-entropy} and \eqref{rhyb:row-log-bound}
lower-bound the bracket in \eqref{rhyb:hybrid-step} by
\(-\mathbb E\log A-C-K_i/q\). Equation~\eqref{rhyb:next-slope} then
gives
\[
h(xS\mid x,L,F_r)+I(S;x\mid L,F_r)
\ge a_{r+2}^{(i)}-C-K_i/q.
\]
Since \(r=k-i-1\), the hybrid identity becomes
\begin{equation}\label{rhyb:slope-difference}
G_i(k)-G_{i+1}(k)
\le a_{k-i}^{(i)}-a_{k-i+1}^{(i)}+C+K_i/q.
\end{equation}
For fixed \(i\), the fresh observations are exchangeable conditional on
\(L_i\). Relabel two consecutive fresh observations and then condition
on the additional earlier one. Conditional entropy can only decrease,
so the successive slopes \(a_j^{(i)}\) are nonincreasing in their
finite range. Also
\[
a_j^{(i)}\le\tfrac12\log(2\pi e)
\]
by comparison with the marginal standard normal label.
For \(i+j\le k_1+1\), a useful lower bound is
\begin{equation}\label{rhyb:slope-lower}
a_j^{(i)}\ge-C-B/h_0.
\end{equation}
To prove it, use monotonicity to bound \(a_j^{(i)}\) below by the
average of the next \(h_0\) slopes. Their sum is the joint entropy of
the next \(h_0\) fresh labels given their rows, \(D'_j\), and \(L_i\).
Removing \(V\) from that conditioning increases the entropy by at most
\(H(V)\le B\). Without \(V\), the actual prefix and all fresh rows have
the ordinary independent-row law. Each successive baseline label
entropy is at least \(-C\) by Lemma~\ref{rhyb:residual}, since the total
number of rows is at most
\[
i+j+h_0\le k_1+1+h_0\le3d/4
\]
for sufficiently large \(d\). The sum is therefore at least
\(-Ch_0-B\), proving \eqref{rhyb:slope-lower}.
Average \eqref{rhyb:slope-difference} over \(k_0\le k\le k_1\).
For each \(i\), its slope term is exactly
\[
\frac1{N_k}\sum_{k=k_0}^{k_1}
\bigl(a_{k-i}^{(i)}-a_{k-i+1}^{(i)}\bigr)
=\frac{a_{k_0-i}^{(i)}-a_{k_1-i+1}^{(i)}}{N_k}
\le\frac{C+B/h_0}{N_k}.
\]
Now sum over \(i=0,\ldots,m-1\), use
\(\sum_iK_i\le B\) from \eqref{rhyb:row-budget}, and apply
\eqref{rhyb:block-reduction}. This gives \eqref{rhyb:block-cost}.
Finally \(N_k,h_0,q\ge cd\) and \(m\le d/8\), so \(B\le d^2\) makes
the displayed block cost at most \(C'd\).
\end{proof}
Subsection~\ref{subsec:r-hybrid-application} combines this block estimate with the stopping clock and the terminal residual-sphere bound.
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/05-hybrids.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/06-fiber.tex ====
\section{A finite Gaussian-fiber comparison}\label{sec:r-fiber}
We now bound the information retained after a block of exact Gaussian
measurements by comparing two ways to average the state likelihood along
a measurement fiber. The comparison measure is finite but need not have
mass one. Its marginal is an inverse-distance kernel involving the rows
actually used by the transition. A common local-mass quantity then
connects that marginal to a projection independent of the new state.
We retain the measure and entropy conventions of
Section~\ref{sec:r-experiments}. Constants denoted by \(K\) are
positive and absolute and may increase. The local row counts are
\begin{equation}\label{rfib:parameters}
n=\lfloor d/10\rfloor,\qquad
k=\lfloor d/3\rfloor,\qquad
\ell=\lfloor d/10\rfloor.
\end{equation}
Here \(n\) is the number of rows read in one block, \(k\) is the number
of rows in an auxiliary projection, and \(\ell\) is an integer moment
order. We take \(d\) sufficiently large that \(\ell\ge2\) and
\(k-\ell-n\ge d/10\).
\subsection{Projection fibers and conditional information}
We first record the geometric facts used both in the block estimate and
at the terminal state. If \(\sigma_m\) is uniform probability on
\(S^{m-1}\), then for \(m\ge2\), \(z\in S^{m-1}\), and \(0<r\le1/2\),
\begin{equation}\label{rfib:cap}
\sigma_m(B(z,r))\le r^{m-1}.
\end{equation}
This is the centered-ball estimate of Lemma~\ref{lem:r-caps} in
dimension \(m\).
For a full-row-rank \(b\times d\) matrix \(C\), where \(1\le b\le d-2\),
put
\[
P_C=C^{\mathsf T}(CC^{\mathsf T})^{-1}C,\qquad
x_C(z)=C^{\mathsf T}(CC^{\mathsf T})^{-1}z .
\]
Write \(S(H)=\{u\in H:\|u\|=1\}\) for the unit sphere of a subspace
\(H\). The conditional law of \(S\sim\sigma\) given \(CS=z\), denoted by
\(\sigma_{C,z}\), fixes \(P_CS=x_C(z)\) and is uniform on the remaining
sphere
\[
x_C(z)+\sqrt{1-\|x_C(z)\|^2}\,
S(\ker C),\qquad \|x_C(z)\|<1.
\]
This formula specifies a Borel probability kernel on the indicated
set. For example, the uniform direction in \(\ker C\) can be realized
as \((I-P_C)Z/\|(I-P_C)Z\|\) with \(Z\) a standard Gaussian vector;
the map is Borel away from a null set. Set the kernel to a fixed point mass off
the full-rank interior set. To verify the formula, write a uniform
sphere point as a standard Gaussian vector divided by its length.
The squared lengths in the row space and its orthogonal complement are
independent chi-squared variables with \(b\) and \(d-b\) degrees of
freedom before division. The first divided by their sum has the beta distribution with
parameters \(b/2\) and \((d-b)/2\), and the two directions are
independent and uniform. Consequently the row-space projection, in
orthonormal coordinates, has density
\begin{equation}\label{rfib:projection-density}
c_{d,b}(1-\|x\|^2)^{(d-b-2)/2}\quad(\|x\|<1),
\qquad
c_{d,b}=\frac{\Gamma(d/2)}
{\pi^{b/2}\Gamma((d-b)/2)} .
\end{equation}
The density is zero outside the unit ball. In particular, the conditional statement holds for almost every
observation. Since
\(\|x_C(z)\|^2=z^{\mathsf T}(CC^{\mathsf T})^{-1}z\), the
Lebesgue density \(p_C\) of \(CS\) is
\begin{equation}\label{rfib:label-density}
p_C(z)=
\begin{cases}
\displaystyle
\frac{c_{d,b}}{\det(CC^{\mathsf T})^{1/2}}
\bigl(1-\|x_C(z)\|^2\bigr)^{(d-b-2)/2},
&\|x_C(z)\|<1,\\
0, &\text{otherwise}.
\end{cases}
\end{equation}
Boundary values do not affect any of the integrals below.
For \(b=k\), the exponent in \eqref{rfib:projection-density} is
nonnegative. Integrating its normalization over the ball of radius
\(1/2\) shows that its supremum times the volume of the unit \(k\)-ball
is at most \(2^k(4/3)^{d/2}\). Thus, for every ball \(D\) of radius
\(r\) in the row space,
\begin{equation}\label{rfib:projection-ball}
\Pr\{P_CS\in D\}\le 2^k(4/3)^{d/2}r^k\le e^{Kd}r^k.
\end{equation}
The estimate is for the unweighted uniform measure \(\sigma\).
Let \(V\) take values in a finite set \(\mathcal V\) and be jointly
distributed with \(S\). Choose Borel versions of the state likelihoods
\[
f_v(s)=\Pr\{V=v\mid S=s\},\qquad
\bar f_v(C,z)=\int f_v(t)\,d\sigma_{C,z}(t).
\]
Modify the first family on a Borel \(\sigma\)-null set, if needed, so
that \(f_v\ge0\) and \(\sum_v f_v=1\) everywhere.
These are likelihoods, not probability densities normalized separately
for each state. When \(C\) has \(k\) independent standard Gaussian rows
and is independent of \((S,V)\), disintegration identifies
\(\bar f_v(C,z)\) with \(\Pr\{V=v\mid C,CS=z\}\). The conditional
relative-entropy chain rule therefore gives
\begin{equation}\label{rfib:potential}
\begin{aligned}
\Phi(V)&:=I(S;V\mid C,CS)
=\mathbb E\log\frac{f_V(S)}{\bar f_V(C,CS)}\\
&=H(V\mid C,CS)-H(V\mid S).
\end{aligned}
\end{equation}
Here \(H\) denotes Shannon entropy in nats. For the standard-Borel form of this chain rule, see
\cite[Section~3.3]{Austin2020}. Nonnegativity of conditional relative
entropy and the displayed difference give
\(0\le\Phi(V)\le\log|\mathcal V|\). Terms on
zero-probability state or fiber events are omitted.
\begin{proposition}[Information through a Gaussian block]\label{rfib:block}
Let \(S\sim\sigma\), let \(V\) be finite-valued, and let \(A\) have
\(n\) independent standard Gaussian rows, independently of \((S,V)\).
Suppose \(W\) takes at most \(N\) values, where \(N\ge1\) is an integer, and is obtained from
\((V,A,AS)\) by a Borel transition kernel. If \(\log N\le d^2\), then
for the dimensions in \eqref{rfib:parameters} and all sufficiently
large \(d\),
\begin{equation}\label{rfib:drift}
\Phi(W)\le\Phi(V)+Kd .
\end{equation}
The auxiliary matrix in each occurrence of \(\Phi\) is independent of
the pair consisting of the signal and the state in that occurrence.
\end{proposition}
The proof first compares the real law to a finite measure. We next
identify the latter's signal/state marginal by a two-point Borel measure
identity. Finally, two estimates with different geometric proofs compare
that marginal and the fresh-projection likelihood to one local mass.
\subsection{The finite measure and its exact marginal}
Write the transition probabilities as \(h_{vw}(A,AS)\). Define
\begin{equation}\label{rfib:routing}
g_w(A,t)=\sum_v f_v(t)h_{vw}(A,At),\qquad
f_w(t)=\mathbb E_A g_w(A,t).
\end{equation}
Thus \(0\le g_w\le1\), \(0\le f_w\le1\), and the sums over \(w\) of
each of these functions are one. The function \(f_w\) is precisely
the new state's likelihood given \(S=t\). In particular neither
\(g_w\) nor \(f_w\) is divided by the marginal probability of state
\(w\).
Augment \(A\) by \(k-n\) independent Gaussian rows and call the
result \(C\), with \(A\) as its first \(n\) rows. Relative to the
product measure \(\mathfrak m\) of the Gaussian law of \(C\),
\(\sigma(ds)\), and counting measure on the two state sets, the real law \(P\) and the comparison
measure \(Q\) on \((C,S,V,W)\) have densities
\begin{align}
\frac{dP}{d\mathfrak m}(C,s,v,w)
&=f_v(s)h_{vw}(A,As),\notag\\
\frac{dQ}{d\mathfrak m}(C,s,v,w)
&=p_C(Cs)\bar f_v(C,Cs)h_{vw}(A,As).
\label{rfib:PQ}
\end{align}
The factor \(p_C(Cs)\) turns the conditional fiber average
\(\bar f_v(C,Cs)\) into the density at \(Cs\) of the projection of
\(f_v\,d\sigma\). This unnormalized equal-label measure will yield the
inverse-distance kernel in Lemma~\ref{rfib:two-point}.
The routing weights in \(Q\) remain the actual weights
\(h_{vw}(A,As)\). We have \(P\ll Q\): \(p_C(Cs)>0\) almost surely,
and a fiber on which \(\bar f_v(C,Cs)=0\) has \(f_v=0\) almost
everywhere on that fiber.
The comparison measure has strictly positive finite mass. Indeed,
summing the routing probabilities and then the old-state likelihoods
gives
\[
m_Q:=Q(\Omega)
=\mathbb E_C\int p_C(Cs)\,d\sigma(s)
=\mathbb E_C\int p_C(z)^2\,dz
\le\mathbb E_C\sup_z p_C(z)<\infty.
\]
The last expectation is finite by \eqref{rfib:label-density}.
Gram--Schmidt on the Gaussian rows expresses
\(\det(CC^{\mathsf T})^{1/2}\) as a product of successive
perpendicular lengths with conditional chi laws of degrees
\(d,d-1,\ldots,d-k+1\). A chi variable of degree \(\nu>1\) has
finite inverse first moment
\(2^{-1/2}\Gamma((\nu-1)/2)/\Gamma(\nu/2)\), and all these degrees
are greater than one. Strict positivity follows from the positivity
of \(p_C\) on the interior of its support.
Use the signed finite-reference entropy
\(D_{\mathrm{fin}}(P\|Q)=\mathbb E_P\log(dP/dQ)\) from
Lemma~\ref{lem:r-finite-reference}. Cancellation in
\eqref{rfib:PQ}, together with the independence of \(C\) from
\((S,V)\), yields
\begin{equation}\label{rfib:finite-entropy}
D_{\mathrm{fin}}(P\|Q)=\Phi(V)+\mathbb E[-\log p_C(CS)]
\le\Phi(V)+\frac{k}{2}\log(2\pi e).
\end{equation}
Here \(\log p_C(CS)\) is integrable: the logarithm of the determinant
has finite log moments by the same chi factorization, and the residual
factor in \eqref{rfib:label-density} has finite log moments by the beta
law. For the inequality, let \(\varphi_k\) be the standard Gaussian
density. Nonnegativity of \(D(p_C\,dz\|\varphi_k\,dz)\), integrated
over \(C\), gives
\(\mathbb E[-\log p_C(CS)]\le\mathbb E[-\log\varphi_k(CS)]\).
Unconditionally \(CS\) is standard Gaussian, because \(S\) has unit
length and is independent of the Gaussian rows. This assertion is
not a conditional Gaussian assertion given \(C\) or the state.
It is necessary to normalize \(Q\) before invoking probability data
processing. Set \(Q_0=Q/m_Q\), and let \(\pi\) be any measurable
map. Both \(Q\) and its pushforward have mass \(m_Q\), so
\begin{align}
D_{\mathrm{fin}}(P\|Q)&=D(P\|Q_0)-\log m_Q, \notag\\
D_{\mathrm{fin}}(\pi_\#P\|\pi_\#Q)
&=D(\pi_\#P\|\pi_\#Q_0)-\log m_Q \notag\\
&\le D(P\|Q_0)-\log m_Q
=D_{\mathrm{fin}}(P\|Q). \label{rfib:finite-dp}
\end{align}
No nonnegativity of \(D_{\mathrm{fin}}(P\|Q)\) is used.
Let \(q_w(s)\) be the density of the \((S,W)\) marginal of \(Q\)
relative to \(\sigma\) and counting measure. The corresponding real
density is \(f_w(s)\). Equations \eqref{rfib:finite-entropy} and
\eqref{rfib:finite-dp} imply
\begin{equation}\label{rfib:marginal-entropy}
\mathbb E\log\frac{f_W(S)}{q_W(S)}
\le\Phi(V)+Kd ,
\end{equation}
where this expectation, and all state expectations below, are under
the real law. The densities \(q_w\) need not sum to a probability
density.
We next calculate this marginal in a form suitable for geometric
estimates. Let \(\gamma_b\) denote the law of \(b\) unrestricted
standard Gaussian rows. For a unit vector \(u\), let
\(\gamma_{b,\perp u}\) be the law of \(b\) independent rows with
Gaussian covariance \(I-uu^{\mathsf T}\), supported on \(u^\perp\).
\begin{lemma}[Two-point Gaussian fiber measure]\label{rfib:two-point}
Assume \(1\le k<d-1\). For every bounded Borel function
\(H(C,s,t)\) on
\(\mathbb R^{k\times d}\times S^{d-1}\times S^{d-1}\),
\begin{align}
&\int \gamma_k(dC)\int\sigma(ds)\,p_C(Cs)
\int\sigma_{C,Cs}(dt)\,H(C,s,t) \notag\\
&\quad=(2\pi)^{-k/2}\int\sigma(ds)\int\sigma(dt)\,
\|s-t\|^{-k}
\int\gamma_{k,\perp\widehat{s-t}}(dC)\,H(C,s,t),
\label{rfib:two-point-id}
\end{align}
where \(\widehat{s-t}=(s-t)/\|s-t\|\) off the diagonal. The diagonal
has product measure zero, and its assigned value is immaterial.
Both sides define finite Borel measures.
\end{lemma}
\begin{proof}
For \(\delta>0\), let
\(\kappa_\delta(z)=(2\pi\delta^2)^{-k/2}
e^{-\|z\|^2/(2\delta^2)}\). First let \(H\) be bounded and
continuous, and integrate
\[
H(C,s,t)\kappa_\delta(C(t-s))
\quad\text{against}\quad
\gamma_k(dC)\sigma(ds)\sigma(dt).
\]
Fix full-rank \(C\) and \(s\) with \(\|P_Cs\|<1\). Disintegration
in \(z=Ct\) makes the integral in \(t\)
\[
\int\kappa_\delta(z-Cs)\,p_C(z)
\left(\int H(C,s,t)\,d\sigma_{C,z}(t)\right)dz.
\]
The function multiplied by \(\kappa_\delta\) is continuous at \(Cs\).
Indeed the displayed fiber parametrization is continuous at interior
observations, and the test is bounded and continuous. It is bounded
in absolute value by \(\|H\|_\infty\sup_zp_C(z)\). The Gaussian
approximate identity therefore converges to the left integrand in
\eqref{rfib:two-point-id}; the preceding inverse determinant estimate
makes this bound integrable in \(C\).
Alternatively fix \(s\ne t\), and integrate first in \(C\).
Writing \(v=t-s\), each row integral has total weight
\[
(2\pi)^{-1/2}(\|v\|^2+\delta^2)^{-1/2}.
\]
After division by that weight, the row is a centered Gaussian with
covariance \(I-vv^{\mathsf T}/(\|v\|^2+\delta^2)\). As
\(\delta\downarrow0\) this law converges to the Gaussian law on
\(v^\perp\). The \(k\) rows remain independent, so the limit is the
right integrand in \eqref{rfib:two-point-id}. Its absolute value is
dominated by
\((2\pi)^{-k/2}\|H\|_\infty\|s-t\|^{-k}\).
This is integrable under \(\sigma\otimes\sigma\): dyadic annuli about
\(s\), with \eqref{rfib:cap} for the small radii, give a convergent
geometric series because \(k<d-1\).
The two orders compute the same limit. They prove equality on bounded
continuous tests of two finite Borel measures on the indicated Polish
space. Uniqueness of finite Borel measures then proves the equality
for bounded Borel tests as well. This last step is what permits
measurable routing functions in the application.
\end{proof}
On the fiber \(Ct=Cs\), the first \(n\) rows give \(At=As\).
Consequently, using \eqref{rfib:routing} without normalizing its
weights,
\[
q_w(s)=\mathbb E_C\left[
p_C(Cs)\int g_w(A,t)\,d\sigma_{C,Cs}(t)\right].
\]
Apply Lemma~\ref{rfib:two-point} to
\(H(C,s,t)=\psi(s)g_w(A,t)\) for bounded Borel \(\psi\).
The extra \(k-n\) rows do not enter \(g_w\), so integrating them out
leaves precisely the marginal law of the \(n\) actual rows. We obtain,
for \(\sigma\)-almost every \(s\),
\begin{equation}\label{rfib:kernel}
q_w(s)=(2\pi)^{-k/2}\int
\|s-t\|^{-k}
\mathbb E_{A\sim\gamma_{n,\perp\widehat{s-t}}}g_w(A,t)
\,d\sigma(t).
\end{equation}
This is an equality of marginal densities of the finite measure \(Q\);
there is no additional normalization on its right-hand side.
\subsection{Two estimates for a common local mass}
Put \(a_w=\int f_w\,d\sigma=\Pr\{W=w\}\), and omit states with
\(a_w=0\). Define
\begin{equation}\label{rfib:local-mass}
L_{w,r}(s)=r^{-k}\int_{B(s,r)}f_w(t)\,d\sigma(t),
\qquad L_w(s)=\sup_{r>0}L_{w,r}(s).
\end{equation}
For each \(r\) the integral is Borel in \(s\). Rational radii suffice
in the supremum: approximate any radius from above and use continuity
from above of the finite measure \(f_w\sigma\). Thus \(L_w\) is
Borel. The diameter-two ball gives its lower bound, while
\eqref{rfib:cap} for \(r\le1/2\) and total mass at most one for larger
radii give the upper bound
\begin{equation}\label{rfib:local-bounds}
2^{-k}a_w\le L_w(s)\le2^k .
\end{equation}
Choose the state-count-dependent cutoff
\begin{equation}\label{rfib:cutoff}
J=1+\left\lceil\frac{\log_2N}{d-1-k}\right\rceil,\qquad
r_*=2^{-J}.
\end{equation}
Then \(r_*\le1/2\), \(Nr_*^{d-1-k}\le1\), and \(J=O(d)\), since
\(d-1-k\ge d/2\) for large \(d\) and \(\log N\le d^2\).
\begin{lemma}[Comparison with an independent projection]\label{rfib:first-ratio}
Let \(C'\) have \(k\) independent standard Gaussian rows and be
independent of \((S,W)\). Then
\begin{equation}\label{rfib:ratio-fresh}
\mathbb E\frac{L_W(S)}{\bar f_W(C',C'S)}\le e^{Kd}.
\end{equation}
\end{lemma}
\begin{proof}
Fix a full-rank \(C'\) and a radius \(r\le2\). Choose a finite
maximal \(r\)-separated set \(\{z_i\}\) on the sphere, and partition
the sphere into Borel cells \(E_i\subseteq B(z_i,r)\), breaking ties
by their indices. The enlarged balls \(B(z_i,2r)\) overlap at most
\(5^d\) times: balls of radius \(r/2\) about their separated centers
have disjoint interiors, and all those meeting a given point in an
enlarged ball lie inside the ambient ball of radius \(5r/2\) about
that point.
On \(E_i\),
\[
L_{w,r}(s)\le r^{-k}\int_{B(z_i,2r)}f_w\,d\sigma.
\]
Write \(R\) for the row space of \(C'\), \(p_R\) for the density in
\eqref{rfib:projection-density}, and \(\sigma_x\) for the corresponding
uniform fiber law. Conditioning on \(P_{C'}S=x\) gives
\begin{align*}
\int_{E_i}\frac{f_w(s)}{\bar f_w(C',C's)}\,d\sigma(s)
&=\int_R p_R(x)
\frac{\int_{E_i}f_w(s)\,d\sigma_x(s)}
{\bar f_w(C',C'x)}\,dx\\
&\le\Pr\{P_{C'}S\in B(P_{C'}z_i,r)\}
\le e^{Kd}r^k .
\end{align*}
The quotient is defined to be zero on zero-denominator fibers; on all
other fibers its numerator is at most its denominator. The numerator
vanishes on fibers outside the displayed projected ball. The last
probability is under the unweighted prior and is bounded by
\eqref{rfib:projection-ball}. Multiplying the last two estimates and
summing the cells, with their \(5^d\) overlap, yields
\begin{equation}\label{rfib:fixed-radius}
\int\frac{f_w(s)L_{w,r}(s)}
{\bar f_w(C',C's)}\,d\sigma(s)
\le e^{Kd}a_w .
\end{equation}
For \(r\ge r_*\), one of the grid radii
\(2,1,1/2,\ldots,r_*\) gives
\(L_{w,r}\le2^k L_{w,\mathrm{grid}}\); radii greater than two are
already bounded by the radius-two expression. For \(r<r_*\),
\eqref{rfib:cap} gives
\(L_{w,r}\le r^{d-1-k}\le r_*^{d-1-k}\).
A second conditioning on the projection gives
\(\int f_w/\bar f_w(C',C'\cdot)\,d\sigma\le1\).
We may therefore sum \eqref{rfib:fixed-radius} over the grid and over
states, obtaining
\[
\sum_w\int\frac{f_wL_w}{\bar f_w(C',C'\cdot)}\,d\sigma
\le 2^k(J+2)e^{Kd}\sum_w a_w+Nr_*^{d-1-k}
\le e^{Kd}.
\]
The bound is uniform in full-rank \(C'\), and averaging proves the
claim.
\end{proof}
The other comparison is with the actual finite-measure marginal:
\begin{equation}\label{rfib:ratio-kernel}
\mathbb E\frac{q_W(S)}{L_W(S)}\le e^{Kd}.
\end{equation}
We prove it now. For each positive-mass state introduce the finite
measure
\[
d\nu_w(s)=\frac{f_w(s)}{L_w(s)}\,d\sigma(s).
\]
Equation \eqref{rfib:local-bounds} gives
\(\nu_w(S^{d-1})\le2^k\). More locally, for every ambient center
\(z\) and \(r>0\),
\begin{equation}\label{rfib:nu-ball}
\nu_w(B(z,r))\le(2r)^k .
\end{equation}
Indeed, if \(m=\int_{B(z,r)}f_w\,d\sigma>0\), every \(s\) in that
ball on the sphere has \(L_w(s)\ge(2r)^{-k}m\); integration of
\(f_w/L_w\) over the ball gives the bound. The case \(m=0\) is
immediate.
Inserting \eqref{rfib:kernel} shows that the left side of
\eqref{rfib:ratio-kernel} is \(\sum_w\int q_w\,d\nu_w\). First take
the portion with \(\|s-t\|\le r_*\). Uniformly in \(s\), dyadic
annuli and \eqref{rfib:cap} give
\begin{equation}\label{rfib:near}
\int_{\{\|s-t\|\le r_*\}}\|s-t\|^{-k}\,d\sigma(t)
\le\frac{2^k r_*^{d-1-k}}
{1-2^{-(d-1-k)}}.
\end{equation}
Using \(g_w\le1\), summing the at most \(N\) masses
\(\nu_w(S^{d-1})\le2^k\), and retaining the prefactor in
\eqref{rfib:kernel}, this portion is at most
\[
(2\pi)^{-k/2}\,
\frac{N\,2^{2k} r_*^{d-1-k}}
{1-2^{-(d-1-k)}}\le e^{Kd}.
\]
Thus the state count in the near singular part is paid by the cutoff
chosen in \eqref{rfib:cutoff}.
For the remaining distances use the annuli
\(r/2<\|s-t\|\le r\) with outer radii
\(r=2,1,\ldots,2r_*\). Fix \(w,t,r\), and push
\(r^{-k}\nu_w\) restricted to that annulus to the unit direction
\(u=(s-t)/\|s-t\|\); call the resulting measure \(\mu\).
It has total mass at most \(2^k\) by \eqref{rfib:nu-ball}.
For a linear subspace \(E\) of dimension \(0\le j\le\ell-1\) and
\(0<\eta\le1\), its directions satisfy
\begin{equation}\label{rfib:tube}
\mu\{u:\operatorname{dist}(u,E)\le\eta\}
\le3^j4^k\eta^{k-j}.
\end{equation}
In fact the corresponding \(s\)'s lie within distance \(\eta r\) of
the affine subspace \(t+E\), with their projections there in the
radius-\(r\) ball about \(t\). That \(j\)-ball has an
\(\eta r\)-net of at most \((3/\eta)^j\) points by ambient packing.
Balls of radius \(2\eta r\) about these points cover the \(s\)'s.
Applying \eqref{rfib:nu-ball} and multiplying by \(r^{-k}\) proves
\eqref{rfib:tube}.
\Needspace{6\baselineskip}
\begin{lemma}[Averaging perpendicular Gaussian laws]\label{rfib:mixture}
Let \(\mu\) be a finite measure on \(S^{d-1}\) of mass at most \(2^k\)
satisfying \eqref{rfib:tube} for every linear subspace of dimension
\(j\le\ell-1\). Define the finite measure on \(n\times d\) matrices
\[
\lambda=\int\gamma_{n,\perp u}\,d\mu(u).
\]
This is a Borel measure: a perpendicular matrix can be realized as
\(Z(I-uu^{\mathsf T})\) with \(Z\sim\gamma_n\).
Then every bounded Borel function \(H\) on this matrix space satisfies
\begin{equation}\label{rfib:mixture-dual}
\left|\int H\,d\lambda\right|
\le e^{Kd}\|H\|_{L^{\ell/(\ell-1)}(\gamma_n)} .
\end{equation}
\end{lemma}
\begin{proof}
For \(E\) of dimension \(j\le\ell-1\), layer-cake integration of
\eqref{rfib:tube} gives the inverse moment
\begin{equation}\label{rfib:inverse-distance}
\int\operatorname{dist}(u,E)^{-n}\,d\mu(u)
\le2^k+\frac{n\,3^j4^k}{k-j-n}\le e^{Kd}.
\end{equation}
Here \(\operatorname{dist}(u,E)\le1\); its layer-cake integral below
one is \(n\int_0^1\eta^{-n-1}
\mu\{\operatorname{dist}(u,E)\le\eta\}\,d\eta\).
The denominator is positive because
\(k-j-n\ge k-\ell+1-n\ge d/10\).
For \(u_1,\ldots,u_\ell\), let
\(G=(\langle u_i,u_j\rangle)_{i,j\le\ell}\).
The tube estimate, sent to \(\eta\downarrow0\), shows that each
proper span of at most \(\ell-1\) preceding directions has
\(\mu\)-mass zero. Thus \(G\) is invertible for
\(\mu^{\otimes\ell}\)-almost every tuple. Gram--Schmidt gives
\[
\det G=\prod_{i=1}^{\ell}
\operatorname{dist}\bigl(u_i,\operatorname{span}(u_1,\ldots,u_{i-1})
\bigr)^2 .
\]
Integrate \(u_\ell,u_{\ell-1},\ldots,u_1\) in that order and apply
\eqref{rfib:inverse-distance} at each step. This proves
\begin{equation}\label{rfib:inverse-gram}
\int(\det G)^{-n/2}\prod_{i=1}^{\ell}d\mu(u_i)
\le e^{Kd\ell}.
\end{equation}
It remains to pass from this determinant moment to singular row laws.
For \(0<\delta\le1\), set
\[
\begin{aligned}
\alpha_\delta&=\Pr\{|Z|\le\delta\},\qquad Z\sim N(0,1),\\
D_\delta(A)&=\int
\frac{\mathbf 1_{\{\|Au\|_\infty\le\delta\}}}{\alpha_\delta^n}
\,d\mu(u).
\end{aligned}
\]
There is an absolute \(c>0\) such that \(\alpha_\delta\ge c\delta\).
Expanding the integer \(\ell\)-th moment under \(\gamma_n\) produces
one tuple \(u_1,\ldots,u_\ell\). For an invertible Gram matrix \(G\),
the projections of each unrestricted Gaussian row onto those directions
have density at most
\((2\pi)^{-\ell/2}(\det G)^{-1/2}\). The box of allowed projections
has volume \((2\delta)^\ell\). Row independence and
\eqref{rfib:inverse-gram} therefore give
\[
\mathbb E_{\gamma_n}D_\delta^\ell
\le
\left(\frac{(2\delta)^\ell(2\pi)^{-\ell/2}}
{\alpha_\delta^\ell}\right)^n e^{Kd\ell}
\le e^{Kd\ell}.
\]
The null set of dependent tuples was removed above. Thus
\(\|D_\delta\|_{L^\ell(\gamma_n)}\le e^{Kd}\) uniformly in
\(\delta\).
The measure \(D_\delta\,d\gamma_n\) is the mixture, with mixing
measure \(\mu\), of the laws conditioned on
\(\|Au\|_\infty\le\delta\). For each \(u\), this conditioning
preserves the independent perpendicular components and makes all
components along \(u\) tend to zero. For every bounded continuous
test \(H\), bounded convergence in \(u\) consequently gives
\(\int H D_\delta\,d\gamma_n\longrightarrow\int H\,d\lambda\).
Hölder's inequality proves \eqref{rfib:mixture-dual} for those tests.
Both \(\gamma_n\) and \(\lambda\) are finite Euclidean Borel
measures. Bounded continuous functions are dense in
\(L^{\ell/(\ell-1)}(\gamma_n+\lambda)\); approximation in this
space passes the inequality to every bounded Borel \(H\).
In particular no absolute continuity of the singular mixture
\(\lambda\) was assumed before the dual estimate.
\end{proof}
For the far-annulus contribution to \(\sum_w\int q_w\,d\nu_w\),
apply Lemma~\ref{rfib:mixture} to the annular measure above and
\(H(A)=g_w(A,t)\). Since \(0\le g_w\le1\),
\[
\int\mathbb E_{\gamma_{n,\perp u}}g_w(A,t)\,d\mu(u)
\le e^{Kd}\bigl(\mathbb E_{\gamma_n}g_w(A,t)\bigr)^{1-1/\ell}
=e^{Kd}f_w(t)^{1-1/\ell}.
\]
On its annulus, \(\|s-t\|^{-k}\le2^kr^{-k}\).
The definition of \(\mu\) thus bounds the annular integration in
\(s\) in \eqref{rfib:kernel} by \(2^ke^{Kd}f_w(t)^{1-1/\ell}\),
apart from the displayed kernel prefactor. Concavity gives, pointwise
in \(t\),
\[
\sum_w f_w(t)^{1-1/\ell}
\le N^{1/\ell}\left(\sum_wf_w(t)\right)^{1-1/\ell}
\le N^{1/\ell}\le e^{Kd}.
\]
There are \(J+1=O(d)\) far annuli. Summing them and integrating in
\(t\), then adding the near contribution, proves
\eqref{rfib:ratio-kernel}.
\subsection{Logarithmic combination}
We can now finish Proposition~\ref{rfib:block}. All logarithms in the
following split are integrable under the real \((S,W)\) law and the
independent \(C'\). Indeed
\[
\mathbb E[-\log f_W(S)]=H(W\mid S)\le\log N,\qquad
\mathbb E[-\log\bar f_W(C',C'S)]=H(W\mid C',C'S)\le\log N.
\]
Also \eqref{rfib:local-bounds} and
\(\mathbb E[-\log a_W]=H(W)\le\log N\) make \(\log L_W(S)\)
integrable. Finally \(P_{S,W}\ll Q_{S,W}\). For any finite
measure \(Q'\) and probability \(P'\ll Q'\), the negative part of
its log density ratio has bound
\[
\int_{\{r<1\}}r\log(1/r)\,dQ'\le Q'(\Omega)/e,
\qquad r=\frac{dP'}{dQ'}.
\]
Applied to the marginal comparison, this and the finite upper bound
\eqref{rfib:marginal-entropy} make
\(\log(f_W(S)/q_W(S))\) integrable. Hence \(\log q_W(S)\) is
integrable as well, and \(q_W(S)>0\) almost surely under the real law.
Using the fresh \(C'\) in the new-state potential, we may therefore
write
\begin{align*}
\Phi(W)
&=\mathbb E\log\frac{f_W(S)}{q_W(S)}
+\mathbb E\log\frac{q_W(S)}{L_W(S)}\\
&\quad+\mathbb E\log\frac{L_W(S)}{\bar f_W(C',C'S)}\\
&\le \Phi(V)+Kd
+\log\mathbb E\frac{q_W(S)}{L_W(S)}\\
&\quad+\log\mathbb E\frac{L_W(S)}{\bar f_W(C',C'S)}
\le\Phi(V)+Kd .
\end{align*}
The first inequality uses \eqref{rfib:marginal-entropy} and Jensen;
the last uses \eqref{rfib:ratio-kernel} and
Lemma~\ref{rfib:first-ratio}. This proves the proposition. The
extra \(k-n\) rows allowed both local comparisons to use exponent
\(k\), whereas only the \(n\) actual rows entered the perpendicular
mixture moment.
Subsection~\ref{subsec:r-fiber-application} applies the estimate to a
learner and combines it with stopping and terminal accuracy to obtain a
sample lower bound.
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/06-fiber.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07-streaming-applications.tex ====
\section{From row comparisons to streaming lower bounds}
\label{sec:r-streaming}
To apply the row comparisons to the learner in
Definition~\ref{def:r-streaming-model}, we first replace
completed-measurable rules by Borel versions in the selected
uniform-prior experiment. We then account for the stopping index
and quantify the information that an accurate output must retain
after independent auxiliary rows are revealed. These common
reductions leave each comparison its own block estimate, row
dimensions, and terminal residual-radius bound.
\subsection{Borel rules after the shared seed is fixed}
\label{subsec:r-borel-reduction}
Lemma~\ref{lem:r-seed-reduction} is applied to the original jointly
measurable experiment. It supplies a fixed seed for which
\eqref{eq:r-seed-factorization} holds and the required uniform-prior
success is retained. The following reduction is performed only
after that choice. It does not assert preservation of behavior at
every individual signal.
\begin{lemma}[Borel versions of the finite-state rules]
\label{lem:r-borel-kernels}
Fix a seed satisfying \eqref{eq:r-seed-factorization}, a dimension
\(d\ge2\), and a deterministic finite horizon \(T\). Retain the
conditional law of \(U_0\) at that seed. Suppose each transition
and stopping probability at a positive sample index is measurable
in the completion of the Borel sigma field on
\(\R^d\times\R\) under
\[
\lambda(dx,dy)=\gamma_1(dx)\,dy .
\]
There are everywhere defined Borel transition and stopping kernels
with the same state sets and terminal output kernels whose
fixed-seed uniform-prior joint law of the signal, state path,
stopping index, and output is the same as before. Their block
routing probabilities are Borel functions of the entering state
and the entire block data, including at states and data that have
zero probability in the original run.
\end{lemma}
\begin{proof}
For each state and positive index, combine the next-state and
stopping choices into one finite destination set, tagging a
destination as continuing or terminal. The kernel is a finite
vector of completed-measurable nonnegative functions of \((x,y)\)
whose sum is one. Every completed-measurable real function has a
Borel version: approximate it by simple functions and replace their
level sets by Borel sets modulo null sets. Choose such a version
for every coordinate. The union of the exceptional sets is
contained in a Borel \(\lambda\)-null set. On the Borel set where
the chosen vector is not a probability vector, replace it by a
fixed point mass. That set is also null. Since the horizon and all
state sets are finite, a single Borel \(\lambda\)-null set \(Z\)
contains every sample-pair modification. A stopping choice at
index zero depends only on the initial state and the fixed seed,
with fresh randomness, and has no sample argument to replace.
In the fixed-seed law, \eqref{eq:r-seed-factorization} leaves
\(S\sim\sigma\) independent of the pre-generated Gaussian rows.
For a nonzero row \(x\), the image of \(\sigma\) under
\(s\mapsto\langle x,s\rangle\) has a Lebesgue density when \(d\ge2\).
This follows from the one-coordinate sphere formula after rotation
and multiplication by \(\|x\|\). The zero row has Gaussian
probability zero. Hence every marginal sample pair
\((X_t,\langle X_t,S\rangle)\) is absolutely continuous with
respect to \(\lambda\). In particular,
\[
\Prob\{(X_t,\langle X_t,S\rangle)\in Z\}=0.
\]
For any state \(u\), even one selected using previous observations,
the probability that the state before time \(t\) is \(u\) and the
current pair lies in \(Z\) is bounded by this same zero probability.
A finite union over the pre-generated indices therefore shows that
no modified input is visited almost surely.
Couple the original and Borel finite kernels with the same fresh
uniform random variable at each step. Induction makes their state
paths and stopping choices identical almost surely. At identical
terminal state-index pairs their output kernels agree, so the
outputs may also be coupled identically. This proves the claimed
joint-law equality. For any specified entering state, finite
composition of the everywhere Borel kernels gives Borel block
routing probabilities on every block-data vector. Such a routing
function is a continuation from the specified state; it need not
be a conditional law given that the state was reached.
\end{proof}
The order of these reductions matters. Original joint measurability
makes the conditional success function of the shared seed
measurable, so it can be averaged in Lemma~\ref{lem:r-seed-reduction}.
Lemma~\ref{lem:r-borel-kernels} then chooses versions separately for
the selected seed. No jointly measurable selection of replacement
versions across seed values is needed. In particular the global
Borel extensions used in the finite fiber comparison are fixed
before its singular comparison measure is constructed; no
real-law null set is transferred to a perpendicular Gaussian law.
In each fixed-seed experiment below, unused future rows are still
independent of the joint vector consisting of the signal and the
current state. This follows from the pre-generated product row law,
\eqref{eq:r-seed-factorization}, and the fresh transition
randomness in the model. If stopping is allowed at index zero,
let \(\overline U_0\) denote the initial padded state, including
that status. It is generated from \(U_0\) and fresh time-zero
randomness, so
\[
\overline U_0\ \perp\!\!\!\perp\
(S,(X_t)_{t\ge1})
\]
in the fixed-seed law. Whenever an auxiliary matrix is introduced,
it is sampled independently of the pair consisting of \(S\) and
the state in question. These joint independence statements justify
the zero initial potentials and the fresh-block comparisons.
\subsection{Common stopping and terminal estimates}
\label{subsec:r-stopping-reduction}
The five comparisons use different information potentials. Their
application to a learner shares two estimates. First we account for
the stopping index before any analytic comparison is invoked. We then
bound the information that success requires after auxiliary rows have
been revealed.
\begin{lemma}[Padding, output capacity, and unrestricted data]
\label{lem:r-stopping-reduction}
Consider a fixed-seed Borel learner from
Lemmas~\ref{lem:r-seed-reduction} and \ref{lem:r-borel-kernels}.
Suppose its accuracy satisfies \(0<\epsilon\le1/10\), its
persistent states have at most \(2^M\) values, and its deterministic
finite horizon is \(T\). Write
\(L=\log(1/\epsilon)\). It admits an absorbing extension,
including to the end of a longer final block, with at most
\[
N=(T+2)2^M
\]
values at each layer. The terminal output is a kernel of the extended
state alone. The initial extended state is independent of the joint
signal and row sequence. At every deterministic block boundary,
unused future rows are independent of the pair consisting of the
signal and the entering extended state. The block transition is a
Borel kernel of that state and the exact block data.
If its uniform-prior angular success probability is \(p\), then
\begin{equation}\label{eq:r-common-output-capacity}
p\le (T+1)2^M\epsilon^{d-1}.
\end{equation}
For a sequence of such learners with \(p\ge3/5\) and
\(M(d)=o(d^2)\), on the branch \(T\le dL\),
\begin{equation}\label{eq:r-common-clock}
dL=O(M+1),\qquad L=o(d),\qquad
\log N=M\log2+\log(T+2)=o(d^2).
\end{equation}
All these estimates are uniform over the allowed accuracies.
For all sufficiently large \(d\), even a learner given all its exact
observations must have \(T>d/4\) to achieve success at least \(3/5\).
\end{lemma}
\begin{proof}
After stopping, retain the terminal state together with its stopping
index in an absorbing state. Defer the output until the end of the
extension and apply its original state-index kernel. Active states
and all stopped pairs number at most \((T+2)2^M\). At index zero the
stopping status is generated from the data-independent initialization
and fresh randomness. The independence statements then follow from
the pre-generated product row law. Finite composition of the Borel
rules gives the asserted block kernel, including on inputs never
visited in the original run.
There are at most \((T+1)2^M\) terminal state-index labels.
For each label, its output kernel has no further dependence on the
signal. In the success integral for that label, bound the conditional
probability of reaching it by one. Lemma~\ref{lem:r-caps}, averaged
over the output kernel, bounds the remaining integral by
\(\epsilon^{d-1}\). Summing proves
\eqref{eq:r-common-output-capacity}, including for randomized output.
When \(p\ge3/5\), taking logarithms gives
\[
(d-1)L\le M\log2+\log(T+1)+\log(5/3).
\]
For sufficiently large \(d\), uniformly for \(L\ge\log10\),
\((d-1)L\ge3dL/4\) and \(\log(dL+1)\le dL/4\).
On \(T\le dL\), subtraction gives \(dL=O(M+1)\).
Consequently \(L=o(d)\), \(T=o(d^2)\), and
\(\log N=o(d^2)\). This is a conclusion only on the stated
branch; no restriction on the accuracy sequence has been imposed.
For the unrestricted-data bound, suppose \(T\le d/4\) and grant
the output all \(T\) pre-generated rows and labels, including unused
pairs after a stop. Given those data, the remaining signal is uniform
on a sphere of radius \(R\) in a \((d-T)\)-dimensional affine space.
Indeed the row-space component is determined, while rotational
invariance leaves a uniform direction in the kernel. More generally,
if \(U\) is the span of \(t<d\) independent Gaussian rows, isotropy
and independence give
\begin{equation}\label{rlevels:residual-mean}
\mathbb E\|P_US\|^2=t/d.
\end{equation}
Taking \(t=T\) gives \(\mathbb E(1-R^2)=T/d\), so
\[
\Pr\{R<1/2\}\le\frac{4T}{3d}\le\frac13.
\]
On the complementary event, an output ball of radius \(\epsilon\)
intersecting that residual sphere is contained in a ball of radius
\(2\epsilon\) centered at a residual-sphere point. Rescaling by
\(R\ge1/2\) and applying Lemma~\ref{lem:r-caps} bounds conditional
success by \((4\epsilon)^{d-T-1}\). The learner's remaining
randomness has no further signal information after all data are given,
so the same estimate holds after averaging its output. Thus success
is at most
\[
\frac13+(2/5)^{3d/4-1}<\frac35
\]
for large \(d\), a contradiction. This argument includes \(T=0\),
when the residual sphere is the original unit sphere.
\end{proof}
\begin{lemma}[Residual information in a successful state]
\label{lem:r-residual-terminal}
Let \(S\sim\sigma\), let \(V\) be a finite state jointly
distributed with \(S\), and let \(G\) have \(0\le k<d-1\)
independent standard Gaussian rows, independently of \((S,V)\).
Suppose a unit-vector output is drawn from a kernel of \(V\) alone
and has angular success probability at least \(p\) at accuracy
\(\epsilon>0\). Let \(R\) be the radius of the conditional
sphere of \(S\) given \((G,GS)\). If
\[
0<\rho\le1,\qquad 2\epsilon<\rho,\qquad
\Pr\{R<\rho\}\le\eta<p,
\]
then
\begin{equation}\label{eq:r-residual-terminal}
I(S;V\mid G,GS)
\ge(p-\eta)(d-k-1)\log\frac{\rho}{2\epsilon}-\log2.
\end{equation}
For \(\rho<1\), one available bad-radius bound is
\begin{equation}\label{eq:r-residual-markov}
\Pr\{R<\rho\}\le\frac{k}{d(1-\rho^2)}.
\end{equation}
\end{lemma}
\begin{proof}
Let \(Q\) preserve the side-data marginal \((G,GS)\) and the
conditional marginals of \(S,V\) given those data, while making
\(S\) and \(V\) conditionally independent. Apply the same
state-output kernel under both laws. Their relative entropy,
including the output, is \(I(S;V\mid G,GS)\).
The event of angular success and \(R\ge\rho\) has actual
probability at least \(p-\eta\). Under \(Q\), condition also
on the output. The residual signal remains uniform on its sphere
in the kernel of \(G\), independently of the output. Angular
success implies Euclidean error at most \(\epsilon\). If the
corresponding output ball intersects the residual sphere, centering
it at one point of the intersection enlarges its radius to at most
\(2\epsilon\). Rescaling the residual sphere to unit radius
and applying Lemma~\ref{lem:r-caps} bounds the conditional success
probability by \((2\epsilon/\rho)^{d-k-1}\).
For any event with actual probability \(a\) and reference
probability at most \(b\), where \(0<b\le1\), binary relative
entropy and data processing give
\begin{equation}\label{rlevels:binary-kl}
D(P\Vert Q)\ge a\log(1/b)-\log2.
\end{equation}
Indeed the binary entropy of \(a\) is at most \(\log2\).
Applying this inequality to the preceding event proves
\eqref{eq:r-residual-terminal}. Finally
\eqref{rlevels:residual-mean} gives
\(\mathbb E(1-R^2)=k/d\); Markov's inequality proves
\eqref{eq:r-residual-markov}.
\end{proof}
We now apply the comparisons to these extended states. The
critical-radius, density-level, and hybrid comparisons use an entropy
bound for the outgoing state; the fiber comparison uses its number of values. The
same width bound supplies both hypotheses. Each route retains its own
auxiliary dimension and terminal residual-sphere estimate.
\subsection{The critical-radius comparison}
\label{subsec:r-critical-application}
\begin{theorem}[Streaming consequence of the critical radius]
\label{thm:r-critical-streaming}
Let \(M(d)\) be a nonnegative integer sequence with \(M(d)=o(d^2)\),
and let \(0<\epsilon(d)\le1/10\). For each \(d\), consider a learner
in Definition~\ref{def:r-streaming-model} with deterministic finite
horizon \(T(d)\). If its uniform-sphere angular success probability,
including all learner randomness, is at least \(3/5\), then
\[
T(d)\ge c\,d\log\frac1{\epsilon(d)}
\]
for an absolute \(c>0\) and all sufficiently large \(d\). The
eventual dimension threshold may depend on the memory sequence.
\end{theorem}
\begin{proof}
Use Lemma~\ref{lem:r-seed-reduction} with \(p_0=3/5\), and then
Lemma~\ref{lem:r-borel-kernels}. The resulting fixed-seed
uniform-prior experiment retains success at least \(3/5\), the
conditional initial-state law, the same state bound, and the same
horizon. Transition and terminal output randomness remain fresh.
Put \(L=\log(1/\epsilon)\ge\log10\). The branch
\(T\ge dL\) already has the desired order. On \(T<dL\),
Lemma~\ref{lem:r-stopping-reduction} gives padded states of entropy
at most \(H_*=M\log2+\log(T+2)\le d^2\) eventually. In
particular its output-capacity estimate specializes to
\begin{equation}\label{eq:r-critical-output-capacity}
\frac35\le(T+1)2^M\epsilon^{d-1}.
\end{equation}
Use \(B=\lceil T/m\rceil\) full padded blocks, where
\(m=\lfloor d/10\rfloor\) as in
\eqref{eq:r-critical-parameters}.
For a boundary state \(U\), define
\[
J(U)=I(S;U\mid G,GS)
\]
with an independent \(\ell\)-row matrix \(G\),
\(\ell=\lfloor d/2\rfloor\), sampled independently of the pair
\((S,U)\). In a block, write \(U,W\) for the entering and exiting
states and \(A\) for its \(m\) rows. The matrix \(A\) is independent
of \((S,U)\). Append an independent \(r=\ell-m\) row matrix \(C\)
and set \(G=(A;C)\). In the aligned experiment \((G,GS)\) reveals
the entire exact block data \((A,AS)\). Conditional on these data
and \(U\), the block transition has no further dependence on \(S\).
Conditional data processing therefore gives
\[
I_1(S;W\mid G,GS)
\le I_1(S;U\mid G,GS)=J(U).
\]
The equality uses independence of \(G\) from the pair \((S,U)\).
Theorem~\ref{thm:r-critical-comparison}, applied to the outgoing
state with \(H(W)\le H_*\le d^2\), yields
\[
J(W)\le J(U)+Kd.
\]
The initial padded state \(\overline U_0\) is independent of \(S\),
and its auxiliary matrix is independent of
\((S,\overline U_0)\), so \(J(\overline U_0)=0\). Iteration gives
for the final padded state \(W_f\)
\begin{equation}\label{eq:r-critical-iteration}
J(W_f)\le Kd\left\lceil\frac{T}{m}\right\rceil .
\end{equation}
We next lower-bound that final information. Conditional on
\((G,GS)\), the row-space projection of \(S\) is determined and
the residual direction is uniform in \(\ker G\). If
\(a=d-\ell\), its radius \(R\) has the marginal representation
\[
R^2\stackrel{\mathrm{law}}=\frac{X}{X+Y},
\qquad X\sim\chi_a^2,\quad Y\sim\chi_\ell^2
\]
with independent \(X,Y\). This follows by normalizing a standard
Gaussian vector. Since \(a\ge d/2\), the events
\(X\ge0.75a\) and \(X+Y\le1.4d\) imply \(R\ge1/2\).
Chebyshev's inequality, using variances \(2a\) and \(2d\), gives
\begin{equation}\label{eq:r-critical-radius-tail}
\Prob\{R<1/2\}
\le\frac{32}{a}+\frac{25}{2d}=O(1/d).
\end{equation}
For sufficiently large \(d\), the radius tail in
\eqref{eq:r-critical-radius-tail} leaves success probability at
least \(1/2\) on \(R\ge1/2\). Apply
Lemma~\ref{lem:r-residual-terminal} with \(\rho=1/2\) and
that tail bound. It gives
\begin{equation}\label{eq:r-critical-required-information}
J(W_f)\ge\frac{a-1}{2}\bigl(L-\log4\bigr)-\log2
\ge c_0dL
\end{equation}
for an absolute \(c_0>0\) and all sufficiently large \(d\).
This is uniform over \(L\ge\log10\), because
\[
L-\log4\ge
\left(1-\frac{\log4}{\log10}\right)L>0 .
\]
The common stopping reduction gives \(T>d/4\ge m\), so
\(\lceil T/m\rceil\le2T/m\). Equation
\eqref{eq:r-critical-iteration} is therefore an \(O(T)\) upper
bound. Comparing it with
\eqref{eq:r-critical-required-information} proves \(T\ge cdL\)
uniformly over the stated accuracies.
\end{proof}
\input{sections/07a-density-endpoints}
\input{sections/07b-hybrid-endpoint}
\input{sections/07c-fiber-endpoint}
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07-streaming-applications.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07a-density-endpoints.tex ====
\subsection{The density-level comparisons}
\label{rlevels:endpoints}
We apply both comparisons to Definition~\ref{def:r-streaming-model}.
Assume that the original uniform-prior experiment has angular success
probability at least \(2/3\), that \(0<\epsilon\le1/10\), and that
\(M=M(d)=o(d^2)\); \(T\) is its deterministic finite horizon. Put
\(L=\log(1/\epsilon)\ge\log10\). A worst-signal success premise of
\(2/3\) first implies this uniform-prior premise by integration.
Apply Lemma~\ref{lem:r-seed-reduction} to the original jointly
measurable experiment with \(p_0=2/3\). Fix a seed \(\xi\) for which
\eqref{eq:r-seed-factorization} holds and conditional success is at
least \(2/3\), retain \(\mathcal L(U_0\mid\Xi=\xi)\), and then apply
Lemma~\ref{lem:r-borel-kernels}. These reductions preserve the fixed-seed
uniform-prior joint law, the state bound, and the horizon. All learner
statements in this subsection concern that experiment. We prove
\(T\ge c dL\) for an absolute \(c>0\) in all sufficiently large
dimensions; the eventual threshold may depend on the memory sequence.
For completeness, \eqref{rlevels:binary-kl} applied to success
under the product signal/output law and Lemma~\ref{lem:r-caps}
give the unconditional bound
\begin{equation}\label{rlevels:output-information}
I(S;\widehat S)\ge\tfrac23(d-1)L-\log2.
\end{equation}
Restrict to \(T<dL\). Lemma~\ref{lem:r-stopping-reduction}
provides absorbing padded states, a state-only terminal output,
data-independent initial state \(\overline U_0\), and fresh future
blocks. Its clock bound implies, in particular,
\begin{equation}\label{rlevels:clock}
L\le C\frac{M+1+\log d}{d},\qquad T=O(M+d),\qquad
H_*:=M\log2+\log(T+2)=o(d^2).
\end{equation}
The lemma also gives
\begin{equation}\label{rlevels:linear}
T>d/4.
\end{equation}
Both comparisons below use this padded learner. Their auxiliary
matrices and block lengths remain distinct.
For the one-level comparison, return to
\eqref{rlevels:one-parameters} and use
\(B_{\mathrm{one}}=\lceil T/k\rceil\) padded blocks. In a block let \(Z\)
and \(U\) be the entering and exiting states. The next matrix
\(X\) is independent of the pair \((S,Z)\). Draw \(B\) independently
of \((S,Z,X,U)\), and put \(G=(X;B)\) as in Proposition~\ref{rlevels:one-comparison}.
Conditional on \((G,GS)\), the entire block data \((X,XS)\)
are known. The transition kernel from \(Z\) to \(U\) then has no
additional dependence on \(S\). Conditional data processing gives
\[
\widetilde{\mathcal D}(U)
\le I_{\mathrm{act}}(S;Z\mid G,GS)=\mathcal D(Z),
\]
where the equality uses independence of \(G\) from \((S,Z)\).
By \eqref{rlevels:clock}, \(H(U)\le H_*\le d^2\) eventually,
so Proposition~\ref{rlevels:one-comparison} costs at most \(Cd\)
per block. The initial boundary \(\overline U_0\) is independent of
\(S\), and its auxiliary \(G\) is independent of the pair
\((S,\overline U_0)\); hence \(\mathcal D(\overline U_0)=0\), and
\begin{equation}\label{rlevels:one-recurrence}
\mathcal D(U_f)\le CdB_{\mathrm{one}}
\end{equation}
for the final padded state.
Take the independent \(m\)-row matrix in the definition of
\(\mathcal D\). Its residual radius \(R\) satisfies
\[
\Pr\{R<1/2\}\le \frac{m/d}{3/4}\le\frac13.
\]
Lemma~\ref{lem:r-residual-terminal}, with
\(p=2/3\), \(\rho=1/2\), and \(\eta=1/3\), now gives
\begin{equation}\label{rlevels:one-endpoint}
\mathcal D(U_f)
\ge\frac{d-m-1}{3}(L-\log4)-\log2
\ge c_0dL
\end{equation}
for an absolute \(c_0>0\) in sufficiently large dimension.
The final inequality is uniform for \(L\ge\log10>\log4\).
Since \(T>d/4\ge k\), the common raw-data bound makes
\(\lceil T/k\rceil\le2T/k\). Hence
\eqref{rlevels:one-recurrence} is \(O(T)\), and comparison with
\eqref{rlevels:one-endpoint} proves \(T\ge cdL\).
For the two-label comparison, use
\eqref{rlevels:two-parameters} and
\(B_{\mathrm{two}}=\lceil T/n\rceil\) padded batches. Let \(V_i\) be the
state after \(i\) batches. At a batch the incoming \(A\) is
independent of \((S,V_i)\), and \(B\) is independent of the
whole actual experiment. Apply Proposition~\ref{rlevels:two-comparison}
to the outgoing state \(V_{i+1}\); the required entropy bound follows
from \eqref{rlevels:clock} on the branch \(T<dL\).
Given \((D,DS)\), the exact batch \((A,AS)\) is known, so
the update is conditionally a channel from \(V_i\) without further
access to \(S\). Therefore
\[
\mathcal J(V_{i+1})
\le I_{\mathrm{act}}(S;V_{i+1}\mid D,DS)+Cd
\le I_{\mathrm{act}}(S;V_i\mid D,DS)+Cd
=\mathcal J(V_i)+Cd.
\]
The last equality uses independence of \(D\) from \((S,V_i)\).
Set \(V_0=\overline U_0\). It is independent of \(S\), and its
auxiliary \(G\) is independent of the pair \((S,V_0)\); hence
\(\mathcal J(V_0)=0\). Iteration gives
\begin{equation}\label{rlevels:two-recurrence}
\mathcal J(V_{B_{\mathrm{two}}})\le CdB_{\mathrm{two}}\le C'(T+d).
\end{equation}
For the independent \(k\)-row matrix defining \(\mathcal J\),
\eqref{eq:r-residual-markov} at \(\rho=1/4\) gives
\[
\Pr\{R<1/4\}\le\frac{16}{15}\frac{k}{d}\le\frac8{15}.
\]
Apply Lemma~\ref{lem:r-residual-terminal} with \(p=2/3\) and
\(\eta=8/15\). It gives
\begin{equation}\label{rlevels:two-endpoint}
\mathcal J(V_{B_{\mathrm{two}}})
\ge\frac2{15}(d-k-1)(L-\log8)-\log2.
\end{equation}
This is at least \(cdL\) uniformly for \(L\ge\log10\), since
\(L-\log8\ge(1-\log8/\log10)L>0\) and
\(d-k-1\ge d/3\).
The upper bound
\eqref{rlevels:two-recurrence} is \(O(T)\) by
\(T>d/4\). This proves \(T\ge cdL\); the discarded branch
\(T\ge dL\) already has the same order.
In both arguments the auxiliary rows are analysis variables. The
learner receives only its prescribed fresh Gaussian stream with exact
labels, and the comparisons permit arbitrary computation within a
transition subject to the persistent finite-state restriction.
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07a-density-endpoints.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07b-hybrid-endpoint.tex ====
\subsection{The hybrid comparison: stopping and terminal information}
\label{subsec:r-hybrid-application}
The averaged block estimate combines with the common stopping
reduction. We need a terminal information bound uniform over the
auxiliary row counts in that average.
\Needspace{6\baselineskip}
\begin{lemma}[Information in a successful terminal state]
\label{rhyb:terminal}
Let \(V\) be a padded final state whose unit-vector output has
uniform-prior angular success at least \(2/3\) at
\(0<\epsilon\le1/10\). For every \(k_0\le k\le k_1\),
\begin{equation}\label{rhyb:terminal-information}
J_k(V)\ge\frac{d-k-1}{14}\log\frac1{5\epsilon}-\log2.
\end{equation}
\end{lemma}
\begin{proof}
For every \(k_0\le k\le k_1\), the auxiliary matrix has
\(k\le d/2\) rows. At \(\rho=2/5\),
\eqref{eq:r-residual-markov} therefore gives
\[
\Pr\{R<2/5\}\le\frac{k/d}{1-4/25}\le\frac{25}{42}.
\]
The success probability is at least \(2/3\), and
\(2/3-25/42=1/14\). Lemma~\ref{lem:r-residual-terminal}
now gives \eqref{rhyb:terminal-information}, because
\(\rho/(2\epsilon)=1/(5\epsilon)\). Its radius condition
holds for \(\epsilon\le1/10\).
\end{proof}
\begin{theorem}[Precision lower bound from hybrid projections]
\label{rhyb:conclusion}
Let \(M(d)\) be a nonnegative integer sequence with \(M(d)=o(d^2)\), and
let \(0<\epsilon(d)\le1/10\). For each \(d\), consider a learner in
Definition~\ref{def:r-streaming-model} with memory bound \(M(d)\),
accuracy \(\epsilon(d)\), deterministic horizon \(T(d)\ge0\), and
uniform prior on \(S^{d-1}\). If
\[
\mathbb P\{\angle(\widehat S,S)\le\epsilon(d)\}\ge\frac23,
\]
then
\[
T(d)\ge c\,d\log\frac1{\epsilon(d)}
\]
for all sufficiently large \(d\). The constant \(c>0\) is absolute;
the dimension threshold may depend on the memory sequence.
\end{theorem}
\begin{proof}
Apply Lemma~\ref{lem:r-seed-reduction} with \(p_0=2/3\) to the
original jointly measurable experiment. Fix a seed satisfying
\eqref{eq:r-seed-factorization} with conditional uniform-prior success
at least \(2/3\), retain its conditional initial-state law, and then
apply Lemma~\ref{lem:r-borel-kernels}. The fixed-seed joint experiment,
state bound, and horizon are preserved.
Put \(b=\log(1/\epsilon)\). In dimensions with \(T>db\), the conclusion
already holds. In the remaining dimensions, Lemma~\ref{lem:r-stopping-reduction}
permits padding with \(W=(T+2)2^M\) states and
\(B=\log W=o(d^2)\), so eventually \(B\le d^2\).
Break the padded computation into blocks of \(h_0\) observations, with
a shorter final block if necessary. The initial padded state
\(\overline U_0\) is independent of \(S\), and the side matrix is
independent of the pair \((S,\overline U_0)\). Thus
\(J_k(\overline U_0)=0\) for every \(k\), and its averaged potential is zero.
Proposition~\ref{rhyb:block} gives
\[
\overline J(V_{\rm final})
\le Cd\left\lceil\frac{T}{h_0}\right\rceil
\le C'(T+d)\le C''T.
\]
The last inequality uses the independent bound \(T>d/4\) from
Lemma~\ref{lem:r-stopping-reduction}; thus it also covers a shorter
last block.
Lemma~\ref{rhyb:terminal} gives the opposite bound for every \(k\) in
the average. Since \(k\le d/2\) and \(b\ge\log10\),
\[
\log\frac1{5\epsilon}=b-\log5
\ge\frac{\log2}{\log10}\,b.
\]
The right side of \eqref{rhyb:terminal-information} is consequently at
least \(c'db\) for all sufficiently large \(d\), uniformly over the
allowed accuracies. Comparing the two bounds proves \(T\ge cdb\).
The dimensions with \(T>db\) were already covered.
\end{proof}
If a learner succeeds for every unit signal with probability at least
\(2/3\), it also satisfies the uniform-prior hypothesis, so the theorem
applies to that worst-signal guarantee. The shared-seed case is covered
by the joint-independence reduction at the start of the proof, which
retains fresh randomized transition and output kernels. The proof uses
exact labels and imposes no linearity or within-transition precision
restriction.
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07b-hybrid-endpoint.tex ====
==== BEGIN Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07c-fiber-endpoint.tex ====
\subsection{The finite Gaussian-fiber comparison}
\label{subsec:r-fiber-application}
We apply Proposition~\ref{rfib:block} to
Definition~\ref{def:r-streaming-model}, including its common notation
\(\Xi,U_0,(X_t)_{t\ge1}\). This route also fixes the remaining
randomness after choosing the seed, so its terminal count uses a
deterministic decoder.
\begin{corollary}[Uniform-sphere sample lower bound]\label{rfib:streaming}
Let \(M(d)\ge0\) be integer-valued with \(M(d)=o(d^2)\), and let
\(0<\epsilon(d)\le1/10\). Suppose learners in Definition~\ref{def:r-streaming-model},
with \(S\sim\sigma\), satisfy
\[
\Pr\{\arccos\langle\widehat S,S\rangle\le\epsilon(d)\}\ge2/3,
\]
where the probability includes the signal, rows, and learner randomness.
Then
\[
T(d)\ge c\,d\log(1/\epsilon(d))
\]
for an absolute \(c>0\) and all sufficiently large \(d\). The
eventual dimension threshold may depend on the memory sequence.
\end{corollary}
\begin{proof}
Apply Lemma~\ref{lem:r-seed-reduction} with \(p_0=2/3\) to the
original jointly measurable uniform-prior experiment. Fix a seed
\(\xi\) satisfying \eqref{eq:r-seed-factorization} whose conditional
success is at least \(2/3\), and retain the conditional initial-state
law. Then apply Lemma~\ref{lem:r-borel-kernels} in that fixed-seed
experiment. In particular all global Borel routing extensions are fixed
before \eqref{rfib:routing} and the finite measure \(Q\) are formed.
The two-point identity applies to those Borel functions without transferring
a null set from the real observation law to a perpendicular row law.
On a product extension of this fixed-seed experiment, choose an array
\(\mathcal R\) of independent uniform random variables consisting of
\(R_t\), \(0\le t\le T\), and
\(R^{\mathrm{out}}_{t,j}\), \(0\le t\le T\),
\(1\le j\le2^M\). Choose the whole array independently of
\((U_0,S,(X_t)_{t\ge1})\). The factorization
\eqref{eq:r-seed-factorization} then implies that the complete
conditional choice vector \((U_0,\mathcal R)\) is independent of
\((S,(X_t)_{t\ge1})\).
Enumerate each finite state alphabet by slots \(j\le2^M\). Use
\(R_0\) for a stopping choice before the first sample and, at time
\(t\ge1\), use \(R_t\) to realize the joint next-state and stopping
outcome by the inverse distribution function of its finite probability
row. Use \(R^{\mathrm{out}}_{t,j}\) to realize the unit-vector output
kernel at terminal pair \((t,j)\). Such a realization can be chosen
Borel for a probability kernel on the standard Borel sphere, by mapping
the sphere into a Borel subset of \([0,1]\) and using an inverse
distribution function. The resulting fixed-seed experiment is jointly
measurable and has the same conditional law as the Borel learner.
Its success probability averaged over \((U_0,\mathcal R)\) is at
least \(2/3\). Fubini and averaging give a complete realization with
uniform-prior success at least \(3/5\). Fix it. The initial state,
all transition and stopping rules, and all terminal outputs are now
deterministic. Independence of the complete choice vector leaves the
joint law of the signal and all rows unchanged. Thus the complete vector
\((\xi,U_0,\mathcal R)\), including the seed and initialization, is
fixed before any state comparison. Its unused entries add no persistent
learner state.
Put \(X_*=d\log(1/\epsilon)\), and restrict to \(T<X_*\).
Apply Lemma~\ref{lem:r-stopping-reduction} to the fixed decoder with
success at least \(3/5\). Its output count gives
\begin{equation}\label{rfib:output-count}
(d-1)\log(1/\epsilon)
\le M\log2+\log(T+1)+\log(5/3).
\end{equation}
The common short-run estimate yields \(X_*=O(M+1)\), and the
absorbing padded state has width at most
\begin{equation}\label{rfib:width}
\begin{aligned}
N&=(T+2)2^M,\\
\log N&\le M\log2+\log(X_*+2)=O(M+1)\le d^2
\end{aligned}
\end{equation}
for all sufficiently large \(d\). The padded decoder is a function
of this state, and rows generated after stopping remain fresh.
Pad also to \(\lceil T/n\rceil\) full \(n\)-row blocks. Each block's
row matrix is independent of the pair consisting of the signal and old
state, while its labels remain exact. After the complete fixation, the
initial padded state is deterministic, so its potential is zero. Iterating
Proposition~\ref{rfib:block} for the padded final state \(F\) gives
\begin{equation}\label{rfib:iteration}
\Phi(F)\le Kd\lceil T/n\rceil.
\end{equation}
For a lower bound use the independent \(k\)-row matrix in
\(\Phi(F)\). Equation~\eqref{eq:r-residual-markov} gives
\[
\Pr\{R<1/2\}\le\frac{4k}{3d}\le\frac49.
\]
The fixed decoder has success at least \(3/5\). Apply
Lemma~\ref{lem:r-residual-terminal} with \(p=3/5\),
\(\rho=1/2\), and \(\eta=4/9\), and write
\(p_0=3/5-4/9>0\). It gives
\begin{align}
\Phi(F)
&\ge p_0(d-k-1)\log(1/(4\epsilon))-\log2 \notag\\
&\ge c\,d\log(1/\epsilon) \label{rfib:terminal}
\end{align}
for sufficiently large \(d\). The constant is absolute because
\(d-k-1\ge d/2\) and
\(\log(1/(4\epsilon))\ge
(1-\log4/\log10)\log(1/\epsilon)\) on the stated accuracy range.
Finally, Lemma~\ref{lem:r-stopping-reduction} gives
\(T>d/4\ge n\), including the exclusion of \(T=0\).
Hence \(\lceil T/n\rceil\le2T/n\), and \(d/n\) is
absolutely bounded for large \(d\). The upper bound
\eqref{rfib:iteration} is therefore \(O(T)\). Combining it with
\eqref{rfib:terminal} proves the corollary.
\end{proof}
If a learner has angular success at least \(2/3\) for every fixed
signal, averaging that guarantee over the uniform sphere supplies the
hypothesis of Corollary~\ref{rfib:streaming}. It therefore gives the
same lower bound with the stated worst-signal premise.
==== END Replacing-Gaussian-observations-in-memory-constrained-inference//sections/07c-fiber-endpoint.tex ====