\sqrt{\gamma}X+N)=\frac{1}{2}\int_{0}^{\gamma}\mathrm{mmse}(X,t)\,dt.$ (249)

The I-MMSE relation directly yields the following formula for differential
entropy: for a square-integrable continuous RV $Y$ we have that [3]

$h(Y)=\frac{1}{2}\log\left(2\pi
e\sigma_{Y}^{2}\right)-\frac{1}{2}\int_{0}^{\infty}\frac{\sigma_{Y}^{2}}{1+\sigma_{Y}^{2}t}-\mathrm{mmse}(Y,t)\,dt.$
(250)

Noting that for $a,b>0$

$\int_{0}^{\infty}\frac{a}{1+at}-\frac{b}{1+bt}\,dt=\lim_{\gamma\to\infty}\log\frac{1+a\gamma}{1+b\gamma}=\log\frac{a}{b},$
(251)

we obtain

$h(Y)=\frac{1}{2}\int_{0}^{\infty}\mathrm{mmse}(Y,t)-\frac{1}{2\pi e+t}\,dt.$
(252)

The MMSE term in the above expression can be approximated by the PMMSE,
resulting in an expression for differential entropy as a function of moments
of $Y$. We explore this connection next.

###  8.2 A New Formula for Differential Entropy

From (250) and (252), and since $\mathrm{mmse}(Y,t)\leq\mathrm{lmmse}(Y,t),$
replacing the MMSE with the LMMSE gives the upper bound on differential
entropy $h(Y)$

$h(Y)\leq
h_{1}(Y):=\frac{1}{2}\int_{0}^{\infty}\mathrm{lmmse}(Y,t)-\frac{1}{2\pi
e+t}\,dt=\frac{1}{2}\log\left(2\pi
e\sigma_{Y}^{2}\right)=h(\mathcal{N}(0,\sigma_{Y}^{2})),$ (253)

which is the maximum possible differential entropy for a continuous RV with a
prescribed variance of $\sigma_{Y}^{2}.$ We take this a step further and
introduce for each $n\in\mathbb{N}$ (assuming $\mathbb{E}[Y^{2n}]<\infty$)

$h_{n}(Y):=\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(Y,t)-\frac{1}{2\pi
e+t}\,dt.$ (254)

From the definition of the PMMSE, we have the monotonicity

$\mathrm{pmmse}_{1}(Y,t)\geq\mathrm{pmmse}_{2}(Y,t)\geq\cdots\geq\mathrm{mmse}(Y,t).$
(255)

Hence, we obtain the monotonicity

$h_{1}(Y)\geq h_{2}(Y)\geq\cdots\geq h(Y)$ (256)

for a RV $Y$ having moments of all orders. In fact, if $Y$ has a MGF, then
$h_{n}(Y)\to h(Y)$ by the monotone convergence theorem in view of the limit
$\mathrm{pmmse}_{n}(Y,t)\to\mathrm{mmse}(Y,t)$ shown in Theorem 17. Hence, we
have the following formula for differential entropy in terms of the moments.

######  Theorem 32.

Let $Y$ be a continuous RV whose MGF exists. Then, we have a decreasing
sequence

$\frac{1}{2}\log\left(2\pi e\sigma_{Y}^{2}\right)=h_{1}(Y)\geq
h_{2}(Y)\geq\cdots\geq h(Y)$ (257)

converging to the differential entropy

$\lim_{n\to\infty}h_{n}(Y)=h(Y).$ (258)

###### Proof.

The functions $g_{n}(t):=\mathrm{lmmse}(Y,t)-\mathrm{pmmse}_{n}(Y,t)$ are
nonnegative and nondecreasing. By Theorem 17, $g_{n}\to g$ pointwise, where
$g(t):=\mathrm{lmmse}(Y,t)-\mathrm{mmse}(t).$ Therefore, by the monotone
convergence theorem,
$\int_{\mathbb{R}}g_{n}(t)\,dt\to\int_{\mathbb{R}}g(t)\,dt.$ Adding and
subtracting $1/(2\pi e+t)$ to each integrand, and noting that
$t\mapsto\mathrm{lmmse}(Y,t)-1/(2\pi e+t)$ is absolutely integrable, we
conclude that $h_{n}(Y)\to h(Y).$ ∎

###  8.3 Behavior of $h_{n}$ Under Affine Transformations

Each approximation $h_{n}$ behaves under (injective) affine transformations
exactly as differential entropy does. Specifically, by the behavior of the
PMMSE under affine transformations shown in Proposition 9, we have that

$\mathrm{pmmse}_{n}(\alpha
Y+\beta,t)=\alpha^{2}\mathrm{pmmse}_{n}(Y,\alpha^{2}t).$ (259)

From (259), and after a change of variables in

$h_{n}(Y):=\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(Y,t)-\frac{1}{2\pi
e+t}\,dt,$ (260)

one can show that $h_{n}(\alpha Y+\beta)=h_{n}(Y)+\log|\alpha|.$

######  Proposition 33.

For $Y\in L^{2n}(\mathcal{F})$ and $(\alpha,\beta)\in\mathbb{R}^{2}$ with
$\alpha\neq 0,$ we have that

$h_{n}(\alpha Y+\beta)=h_{n}(Y)+\log|\alpha|.$ (261)

###### Proof.

See Appendix G. ∎

##  9 A New Formula for Mutual Information

From the formula we developed for differential entropy in Proposition 32, we
immediately obtain a new formula for mutual information between a discrete RV
$X$ and a continuous RV $Y.$ We use the shorthand $Y^{(x)}$ for the RV $Y$
conditioned on $\\{X=x\\}$ (as opposed to the subscript notation used in
Section 6), as we will later consider i.i.d. samples which we will indicate
with subscripts.

First, note that for each $x$ such that $P_{X}(x)>0,$ the RV $Y^{(x)}$ is
continuous. Indeed, if $B\in\mathcal{B}$ has Lebesgue measure zero, we have
that

$0=P_{Y}(B)=\sum_{a\in\mathrm{supp}(X)}P_{X,Y}(\\{a\\}\times
B)=\sum_{a\in\mathrm{supp}(X)}P_{Y^{(a)}}(B)P_{X}(a)\geq
P_{Y^{(x)}}(B)P_{X}(x).$ (262)

Since $P_{X}(x)>0,$ we infer from (262) that $P_{Y^{(x)}}(B)=0.$ Further, the
joint measure $P_{X,Y}$ is absolutely continuous with respect to the product
measure $P_{X}\otimes P_{Y}.$ Indeed, if $B$ is a Borel subset of
$\mathbb{R}^{2},$ and $B_{x}:=\\{y\in\mathbb{R}\leavevmode\nobreak\
;\leavevmode\nobreak\ (x,y)\in B\\},$ then $(P_{X}\otimes
P_{Y})(B)=\sum_{x\in\mathrm{supp}(X)}P_{Y}(B_{x})P_{X}(x).$ Suppose that
$(P_{X}\otimes P_{Y})(B)=0,$ so for each $x\in\mathrm{supp}(X),$ either
$P_{X}(x)=0$ or $P_{Y}(B_{x})=0.$ In addition, we have that
$P_{X,Y}(B)=\sum_{x\in\mathrm{supp}(X)}P_{Y^{(x)}}(B_{x})P_{X}(x).$ For every
$x\in\mathrm{supp}(X)$ such that $P_{X}(x)\neq 0,$ we have that

$0=P_{Y}(B_{x})=\sum_{a\in\mathrm{supp}(X)}P_{X,Y}(\\{a\\}\times
B_{x})=\sum_{a\in\mathrm{supp}(X)}P_{Y^{(x)}}(B_{x})P_{X}(a)\geq
P_{Y^{(x)}}(B_{x})P_{X}(x),$ (263)

hence $P_{Y^{(x)}}(B_{x})=0.$ Therefore, $P_{X,Y}(B)=0,$ and we conclude that
$P_{X,Y}$ is absolutely continuous with respect to $P_{X}\otimes P_{Y}.$ We
have the Radon-Nikodym derivative

$\frac{dP_{X,Y}}{dP_{X}\times P_{Y}}(x,y)=\frac{p_{Y^{(x)}}(y)}{p_{Y}(y)}.$
(264)

Now, by the disintegration theorem, we have that

$I(X;Y)=\sum_{x\in\mathrm{supp}(X)}P_{X}(x)\int_{\mathbb{R}}p_{Y^{(x)}}(y)\log\frac{p_{Y^{(x)}}(y)}{p_{Y}(y)}\leavevmode\nobreak\
dy.$ (265)

Suppose that $\sigma_{Y}^{2}<\infty,$ so we also have that
$\sigma_{Y^{(x)}}^{2}<\infty$ for each $x\in\mathrm{supp}(X).$ If we also have
that $h(Y)>-\infty,$ then we may split the integral in (265) to obtain

$I(X;Y)=-\sum_{x\in\mathrm{supp}(X)}P_{X}(x)\int_{\mathbb{R}}p_{Y^{(x)}}(y)\log
p_{Y}(y)\leavevmode\nobreak\
dy+\sum_{x\in\mathrm{supp}(X)}P_{X}(x)\int_{\mathbb{R}}p_{Y^{(x)}}(y)\log
p_{Y^{(x)}}(y)\leavevmode\nobreak\ dy.$ (266)

In other words,

$I(X;Y)=h(Y)-\mathbb{E}_{X}\left[h\left(Y^{(X)}\right)\right],$ (267)

where the subscript in $\mathbb{E}_{X}$ is to emphasize that the expectation
is taken with respect to $X$ only.

Next, we discuss implications of equation (267) in view of the formula for
differential entropy proved in Proposition 32 and the behavior of the PMMSE
under affine transformations proved in Proposition 9. In particular, we show
that the ensuing approximants of mutual information are affine-transformation
invariant, which is in agreement with how mutual information behaves. In
Section 10, we obtain another formula for the mutual information $I(X;Y)$ when
both RVs $X$ and $Y$ are continuous.

###  9.1 Mutual Information in Terms of Moments

Under the assumptions used in Theorem 32, and utilizing equation (267), we
obtain a formula for mutual information primarily in terms of moments.

######  Theorem 34.

For a discrete RV $X$ with finite support and a continuous RV $Y$ with a MGF
such that $h(Y)>-\infty,$ the mutual information is given by

$I(X;Y)=\frac{1}{2}\lim_{n\to\infty}\int_{0}^{\infty}\mathrm{pmmse}_{n}(Y,t)-\mathbb{E}_{X}\left[\mathrm{pmmse}_{n}(Y^{(X)},t)\right]\,dt.$
(268)

###### Proof.

By assumption on the MGF of $Y,$ we have that $\mathbb{E}[e^{Yt}]<\infty$
whenever $|t|<\delta$ for some fixed $\delta>0.$ Then, whenever $|t|<\delta,$
we also have that for each $x\in\mathrm{supp}(X)$

$P_{X}(x)\mathbb{E}[e^{Y^{(x)}t}]\leq\sum_{a\in\mathrm{supp}(X)}P_{X}(a)\mathbb{E}[e^{Y^{(a)}t}]=\mathbb{E}[e^{Yt}]<\infty.$
(269)

Therefore, the MGF of $Y^{(x)}$ for each $x\in\mathrm{supp}(X)$ is finite over
the nonempty neighborhood $(-\delta,\delta)$ of $0.$ Therefore, Theorem 32 and
equation (267) yield the desired equation for $I(X;Y).$ ∎

Equipped with the relationship between the moments and $I(X;Y)$ given in
Theorem 34, we will introduce a moments-based estimator of mutual information
in Section 11. Specifically, we approximate the mutual information by fixing
$n,$ then further approximate the ensuing expression by replacing moments with
sample moments. Therefore, the estimator makes use of the approximants

$I_{n}(X;Y):=\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(Y,t)-\mathbb{E}_{X}\left[\mathrm{pmmse}_{n}(Y^{(X)},t)\right]\,dt$
(270)

for every $n\in\mathbb{N},$ where $X$ is a discrete RV with finite support and
$Y$ is a continuous RV that is $2n$-times integrable. Under the premises of
Theorem 34, we have the limit

$I(X;Y)=\lim_{n\to\infty}I_{n}(X;Y).$ (271)

Also, in view of the definition of $h_{n}$ in equation (254),

$I_{n}(X;Y)=h_{n}(Y)-\mathbb{E}_{X}\left[h_{n}(Y^{(X)})\right].$ (272)

###  9.2 Properties of $I_{n}$: Affine Transformations and Independence

We prove properties of the approximants $I_{n}$ that resemble those for the
mutual information. First, the behavior of the PMMSE under affine
transformations exhibited in Proposition 9 implies that $I_{n}(X;Y)$ is
invariant under injective affine transformations of $Y.$ Indeed, this can be
seen immediately from the behavior of $h_{n}$ in Proposition 33 in view of
equation (272).

######  Corollary 35.

Suppose $X$ and $Y$ are RVs satisfying the premises of Theorem 34. For any
constants $(\alpha,\beta)\in\mathbb{R}^{2}$ with $\alpha\neq 0,$ and for any
$n\in\mathbb{N}$

$I_{n}(X;\alpha Y+\beta)=I_{n}(X;Y).$ (273)

Also, the approximations $I_{n}(X;Y)$ detect independence exactly.

######  Proposition 36.

Suppose $X$ and $Y$ are RVs satisfying the premises of Theorem 34. If $X$ and
$Y$ are independent, then for any $n\in\mathbb{N}$

$I_{n}(X;Y)=0.$ (274)

###### Proof.

By independence, each $Y^{(x)}$ is identically distributed to $Y.$ Therefore,
$h_{n}(Y^{(x)})=h_{n}(Y)$ for each $x\in\mathrm{supp}(X).$ The desired result
then follows from equation (272). ∎

We give full expressions for the first two approximants of mutual information
that are generated by the LMMSE and quadratic MMSE.

######  Example 6.

When $n=1,$ we obtain

$I_{1}(X;Y)=\log\sigma_{Y}-\mathbb{E}_{X}\left[\log\sigma_{Y^{(X)}}\right],$
(275)

which is the exact formula for $I(X;Y)$ when both $Y$ is Gaussian and each
$Y^{(x)}$ (for $x\in\mathrm{supp}(X)$) is Gaussian; indeed, in such a case,
the MMSE is just the LMMSE. ∎

######  Example 7.

For $n=2,$ we obtain the formula

$\displaystyle
I_{2}(X;Y)=\frac{1}{6}\log\frac{b_{Y}^{2,3}}{\prod_{x\in\mathrm{supp}(X)}\left(b_{Y^{(x)}}^{2,3}\right)^{P_{X}(x)}}+\frac{1}{2}\int_{0}^{\infty}$
$\displaystyle\frac{a_{Y}^{2,1}t}{2+b_{Y}^{2,1}t+b_{Y}^{2,2}t^{2}+b_{Y}^{2,3}t^{3}}$
$\displaystyle\quad-\mathbb{E}_{X}\leavevmode\nobreak\
\frac{a_{Y^{(X)}}^{2,1}t}{2+b_{Y^{(X)}}^{2,1}t+b_{Y^{(X)}}^{2,2}t^{2}+b_{Y^{(X)}}^{2,3}t^{3}}\,dt$

where we may compute for any $R\in L^{4}(\mathcal{F})$

$b_{R}^{2,3}:=\left|\begin{array}[]{ccc}1&\mathbb{E}R&\mathbb{E}R^{2}\\\
\mathbb{E}R&\mathbb{E}R^{2}&\mathbb{E}R^{3}\\\
\mathbb{E}R^{2}&\mathbb{E}R^{3}&\mathbb{E}R^{4}\end{array}\right|=\sigma_{R}^{2}\mathbb{E}R^{4}+2(\mathbb{E}R)(\mathbb{E}R^{2})\mathbb{E}R^{3}-(\mathbb{E}R^{2})^{3}-(\mathbb{E}R^{3})^{2},$
(276)

which is strictly positive when $|\mathrm{supp}(R)|>2,$ and

$\displaystyle b_{R}^{2,2}$
$\displaystyle=-4(\mathbb{E}R)\mathbb{E}R^{3}+3(\mathbb{E}R^{2})^{2}+\mathbb{E}R^{4}$
(277) $\displaystyle b_{R}^{2,1}$ $\displaystyle=6\sigma_{R}^{2}$ (278)
$\displaystyle a_{R}^{2,1}$
$\displaystyle=4(\mathbb{E}R)^{4}-8(\mathbb{E}R)^{2}\mathbb{E}R^{2}+\frac{8}{3}(\mathbb{E}R)\mathbb{E}R^{3}+2(\mathbb{E}R^{2})^{2}-\frac{2}{3}\mathbb{E}R^{4}.$
(279)

∎

##  10 Generalizations to Arbitrary Bases and Multiple Dimensions

We extend our approximation results for the conditional expectation from the
polynomial-basis setting to arbitrary bases, and from conditioning on random
variables to conditioning on arbitrary $\sigma$-algebras. An extension to the
multidimensional case is also presented, which straightforwardly yields an
approximation theorem for differential entropy of random vectors. Another
byproducts of the multidimensional generalization is an expression for mutual
information between two continuous random variables completely in terms of
moments, which is presented at the end of this section.

###  10.1 Arbitrary Bases and $\sigma$-Algebras

Up to here, our exposition dealt with the polynomial basis of
$L^{2}(\sigma(Y)).$ However, our results can be extended to a more general
setup. Recall that we have defined

$\bm{M}_{Y,n}=\mathbb{E}\left[\bm{Y}^{(n)}\left(\bm{Y}^{(n)}\right)^{T}\right],$
(280)

and derived

$\mathbb{E}[X\mid
Y]=\lim_{n\to\infty}\mathbb{E}\left[X\bm{Y}^{(n)}\right]\bm{M}_{Y,n}^{-1}\bm{Y}^{(n)}$
(281)

in Theorem 5 under two requirements: $Y$ satisfies Carleman’s condition, and
$|\mathrm{supp}(Y)|=\infty.$ Along similar lines, we derive a generalization
where the set of polynomials of $Y$ is replaced with any linearly-independent
subset of $L^{2}(\Sigma)$ having a dense span, where
$\Sigma\subset\mathcal{F}$ is any $\sigma$-algebra. Denseness replaces
Carleman’s condition, while linear independence replaces the infinite-support
requirement.

######  Theorem 37.

Fix a $\sigma$-algebra $\Sigma\subset\mathcal{F}$ and a set
$\\{\psi_{k}\\}_{k\in\mathbb{N}}=\mathcal{S}\subset L^{2}(\Sigma).$ For each
$n\in\mathbb{N},$ define the random vector
$\boldsymbol{\psi}^{(n)}=(\psi_{0},\cdots,\psi_{n})^{T}$ and the matrix of
inner products

$\bm{M}_{\mathcal{S},n}:=\mathbb{E}\left[\boldsymbol{\psi}^{(n)}\left(\boldsymbol{\psi}^{(n)}\right)^{T}\right].$
(282)

If $\mathcal{S}$ is linearly independent and $\mathrm{span}(\mathcal{S})$ is
dense in $L^{2}(\Sigma),$ then

$\mathbb{E}[X\mid\Sigma]=\lim_{n\to\infty}\mathbb{E}\left[X\boldsymbol{\psi}^{(n)}\right]^{T}\bm{M}_{\mathcal{S},n}^{-1}\leavevmode\nobreak\
\boldsymbol{\psi}^{(n)}$ (283)

in $L^{2}(\Sigma)$ for any RV $X\in L^{2}(\mathcal{F}).$

For the proof of Theorem 37, we will need the following formula for the
closest element in a finite-dimensional subspace of $L^{2}(\mathcal{F})$ to a
RV $X\in L^{2}(\mathcal{F}),$ which will also be used for the extension of our
results to random vectors later in this section.

######  Lemma 38.

For any fixed finite-dimensional subspace $\mathcal{V}\subset
L^{2}(\mathcal{F})$ having a basis $\\{V_{0},V_{1},\cdots,V_{n}\\},$ we have
that for every $X\in L^{2}(\mathcal{F})$

$\mathbb{E}\left[X\bm{V}\right]^{T}\mathbb{E}\left[\bm{V}\bm{V}^{T}\right]^{-1}\bm{V}=\underset{V\in\mathcal{V}}{\mathrm{argmin}}\left\|X-V\right\|_{2},$
(284)

where $\bm{V}=(V_{0},V_{1},\cdots,V_{n})^{T}.$

###### Proof.

See Appendix H.1. ∎

In view of Lemma 38, we introduce the following notation.

######  Definition 7.

Fix a RV $X\in L^{2}(\mathcal{F}),$ a $\sigma$-algebra
$\Sigma\subset\mathcal{F},$ and a linearly-independent set
$\\{\theta_{j}\\}_{j\in\mathbb{N}}=\Theta\subset L^{2}(\Sigma).$ Write
$\boldsymbol{\theta}^{(n)}=(\theta_{0},\cdots,\theta_{n})^{T}$ for each
$n\in\mathbb{N}.$ We define the $n$-th approximation of
$\mathbb{E}[X\mid\Sigma]$ with respect to $\Theta$ by

$E_{n,\Theta}\left[X\mid\Sigma\right]:=\mathbb{E}\left[X\boldsymbol{\theta}^{(n)}\right]\mathbb{E}\left[\boldsymbol{\theta}^{(n)}\left(\boldsymbol{\theta}^{(n)}\right)^{T}\right]^{-1}\boldsymbol{\theta}^{(n)}.$
(285)

Note that $E_{n,\Theta}[X\mid\Sigma]$ belongs to
$\mathrm{span}(\\{\theta_{j}\\}_{j\in[n]}).$ Further, according to Lemma 38,
$E_{n,\Theta}[X\mid\Sigma]$ is the unique closest element in
$\mathrm{span}(\\{\theta_{j}\\}_{j\in[n]})$ to $X$

$E_{n,\Theta}[X\mid\Sigma]=\underset{V\,\in\leavevmode\nobreak\
\mathrm{span}(\\{\theta_{j}\\}_{j\in[n]})}{\mathrm{argmin}}\left\|X-V\right\|_{2}.$
(286)

If $Y\in L^{2n}(\mathcal{F}),$ $\Theta=\\{Y^{j}\\}_{j\in\mathbb{N}},$ and
$\Sigma=\sigma(Y),$ then

$E_{n,\Theta}[X\mid\Sigma]=E_{n}[X\mid Y].$ (287)

The central claim in Theorem 37 is that if $\mathrm{span}(\Theta)$ is dense in
$L^{2}(\Sigma)$ then

$\mathbb{E}[X\mid\Sigma]=\lim_{n\to\infty}E_{n,\Theta}[X\mid\Sigma].$ (288)

###### Proof of Theorem 37.

For each $n\in\mathbb{N},$ define the subspace

$\mathcal{V}^{(n)}=\mathrm{span}(\\{\psi_{j}\\}_{j\in[n]}).$ (289)

As in the proof of Lemma 38, the entries of the vector

$\boldsymbol{\xi}^{(n)}=\bm{M}_{\mathcal{S},n}^{-1/2}\boldsymbol{\psi}^{(n)}$
(290)

form an orthonormal basis for $\mathcal{V}^{(n)}.$ Note that
$\boldsymbol{\xi}^{(n)}$ is the Gram-Schmidt orthonormalization of
$\boldsymbol{\psi}^{(n)}.$ Hence, $\boldsymbol{\xi}^{(n)}$ is a prefix of
$\boldsymbol{\xi}^{(n+1)}.$ Let $\Theta=\\{\xi_{j}\\}_{j\in\mathbb{N}}$ be the
ensuing orthonormal basis for $L^{2}(\Sigma),$ i.e.,
$\boldsymbol{\xi}^{(n)}=(\xi_{0},\cdots,\xi_{n})^{T}.$ Then,
$\mathrm{span}(\Theta)$ is dense in $L^{2}(\Sigma).$ Therefore,

$\mathbb{E}[X\mid\Sigma]=\sum_{j\in\mathbb{N}}\mathbb{E}[X\xi_{j}]\xi_{j}=\lim_{n\to\infty}\mathbb{E}[X\boldsymbol{\xi}^{(n)}]^{T}\boldsymbol{\xi}^{(n)}=\lim_{n\to\infty}E_{n,\Theta}[X\mid\Sigma],$
(291)

as desired. ∎

###  10.2 The Multidimensional Case

We extend our results on the PMMSE of random variables to random vectors. We
will modify our notation for this subsection only.

Denote the Borel $\sigma$-algebra of $\mathbb{R}^{m}$ by $\mathcal{B}_{m}.$ We
are still working with the probability space $(\Omega,\mathcal{F},P).$ By an
$m$-dimensional random vector ($m$-RV) we mean a measurable function from
$\left(\Omega,\mathcal{F}\right)$ to $(\mathbb{R}^{m},\mathcal{B}_{m}).$ For a
sub-$\sigma$-algebra $\Sigma\subset\mathcal{F},$ we denote the set of
$(\Sigma,\mathcal{B}_{m})$-measurable functions by $\mathcal{M}_{m}(\Sigma)$;
so, the set of $m$-RVs is denoted by $\mathcal{M}_{m}(\mathcal{F}).$
Additionally, for each $q\geq 1,$ we define

$L^{q}(\mathbb{R}^{m},\Sigma):=\left\\{\bm{f}\in\mathcal{M}_{m}\left(\Sigma\right)\leavevmode\nobreak\
;\leavevmode\nobreak\
\int_{\Omega}\|\bm{f}(\omega)\|_{q}^{q}\,dP(\omega)<\infty\right\\}.$ (292)

In (292), $\|\bm{f}(\omega)\|_{q}$ refers to the $q$-norm of the vector
$\bm{f}(\omega)\in\mathbb{R}^{m}.$ In other words, if
$\bm{f}=(f_{1},\cdots,f_{m})^{T},$ then
$\|\bm{f}(\omega)\|_{q}^{q}=\sum_{i=1}^{m}|f_{i}(\omega)|^{q}.$ We will also
use $\|\mathrel{\;\cdot\;}\|_{q}$ for the norm of
$L^{q}(\mathbb{R}^{m},\Sigma),$ i.e., for $\bm{f}\in
L^{q}(\mathbb{R}^{m},\Sigma)$ we have

$\|\bm{f}\|_{q}^{q}=\int_{\Omega}\|\bm{f}(\omega)\|_{q}^{q}\,dP(\omega).$
(293)

The distinction is that we consider the $q$-norm of $\mathbb{R}^{m}$ when we
specify the input of $\bm{f}$ (i.e., $\bm{f}(\omega)$), and when no input is
given to $\bm{f}$ then $\|\bm{f}\|_{q}$ refers to the norm of
$L^{q}(\mathbb{R}^{m},\Sigma).$ We keep the notation
$L^{q}(\mathbb{R},\Sigma)=L^{q}(\Sigma).$

A function $\bm{f}:\mathbb{R}^{m}\to\mathbb{R}^{k}$ is called Borel if it is
$(\mathcal{B}_{m},\mathcal{B}_{k})$-measurable. For any
$\bm{Y}\in\mathcal{M}_{m}(\mathcal{F})$ and integer $k\geq 1$

$\mathcal{M}_{k}(\sigma(\bm{Y}))=\\{\bm{f}(\bm{Y})\leavevmode\nobreak\
;\leavevmode\nobreak\ \bm{f}:\mathbb{R}^{m}\to\mathbb{R}^{k}\text{ Borel
}\\}.$ (294)

By a generalization of Hölder’s inequality, for any $m$-RV
$\bm{Y}=(Y_{1},\cdots,Y_{m})^{T}\in L^{\beta}(\mathbb{R}^{m},\mathcal{F}),$ we
also have that $Y_{1}^{\alpha_{1}}\cdots Y_{m}^{\alpha_{m}}\in
L^{1}(\mathcal{F})$ for any constants $\alpha_{1},\cdots,\alpha_{m}\geq 0$
such that $\alpha_{1}+\cdots+\alpha_{m}\leq\beta.$

We extend the notation $\bm{Y}^{(n)}$ in (45) to random vectors as follows.
For an $m$-RV $\bm{Y}=(Y_{1},\cdots,Y_{m})^{T},$ we let $\bm{Y}^{(n,m)}$
denote the random vector whose entries are monomials in the $Y_{j}$ of total
degree at most $n,$ ordered first by total degree then reverse-
lexicographically in the exponents. For example, if $m=3$ so
$\bm{Y}=(Y_{1},Y_{2},Y_{3})^{T},$ then for $n=2$

$\bm{Y}^{(2,3)}=(1,Y_{1},Y_{2},Y_{3},Y_{1}^{2},Y_{1}Y_{2},Y_{1}Y_{3},Y_{2}^{2},Y_{2}Y_{3},Y_{3}^{2})^{T}$
(295)

because the totally ordered set of exponents $(\leavevmode\nobreak\
\\{\bm{v}\in\mathbb{N}^{3}\mid\mathbf{1}^{T}\bm{v}\leq
2\\}\leavevmode\nobreak\ ,\leavevmode\nobreak\ <\leavevmode\nobreak\ )$ has
the order111111Note that this ordering is not the same as the degree reverse
lexicographical order nor its reverse.

$\displaystyle(0,0,0)<(1,0,0)<(0,1,0)<(0,0,1)<(2,0,0)<(1,1,0)<(1,0,1)<(0,2,0)<(0,1,1)<(0,0,2).$

A straightforward stars-and-bars counting argument reveals that the length of
$\bm{Y}^{(n,m)}$ is $\binom{n+m}{m}.$

Let $\mathscr{P}_{n,m}$ denote the set of polynomials in $m$ variables with
real coefficients of total degree at most $n.$ For an $m$-RV $\bm{Y},$ denote

$\mathscr{P}_{n,m}(\bm{Y}):=\left\\{p(\bm{Y})\leavevmode\nobreak\
;\leavevmode\nobreak\ p\in\mathscr{P}_{n,m}\right\\}.$ (296)

Note that $\mathscr{P}_{n,1}=\mathscr{P}_{n}.$ Also, the notation
$\bm{Y}^{(n,1)},$ while avoided, is disambiguated by interpreting it as
$\bm{Y}^{(n)},$ i.e., $\bm{Y}^{(n,1)}=(1,Y,\cdots,Y^{n})^{T}$ where the
subscript on $Y_{1}$ is dropped. We denote the product sets of
$\mathscr{P}_{n,m}(\bm{Y})$ by $\mathscr{P}_{n,m}^{\ell}(\bm{Y}),$ and
consider their elements as vectors rather than tuples. In other words, we
denote the set of length-$\ell$ vectors whose coordinates are multivariate
polynomial expressions of an $m$-RV $\bm{Y}$ with total degree at most $n$ by

$\mathscr{P}_{n,m}^{\ell}(\bm{Y})=\left\\{(p_{1}(\bm{Y}),\cdots,p_{\ell}(\bm{Y}))^{T}\leavevmode\nobreak\
;\leavevmode\nobreak\ p_{1},\cdots,p_{\ell}\in\mathscr{P}_{n,m}\right\\}.$
(297)

The multivariate generalization of the PMMSE is defined as follows.

######  Definition 8 (Multivariate Polynomial MMSE).

Fix positive integer $\ell,m,$ and $n$. Fix an $\ell$-RV $\bm{X}\in
L^{2}(\mathbb{R}^{\ell},\mathcal{F})$ and an $m$-RV $\bm{Y}\in
L^{2n}(\mathbb{R}^{m},\mathcal{F}),$ and set $k=\binom{n+m}{m}.$ We define the
$n$-th order PMMSE for estimating $\bm{X}$ given $\bm{Y}$ by

$\text{pmmse}_{n}(\bm{X}\mid\bm{Y}):=\underset{\bm{C}\in\mathbb{R}^{\ell\times
k}}{\min}\;\left\|\bm{X}-\bm{C}\bm{Y}^{(n,m)}\right\|_{2},$ (298)

and the $n$-th order PMMSE estimate of $\bm{X}$ given $\bm{Y}$ by

$E_{n}[\bm{X}\mid\bm{Y}]:=\bm{C}\bm{Y}^{(n,m)}\in\mathscr{P}_{n,m}^{\ell}(\bm{Y})$
(299)

for any minimizing matrix $\bm{C}\in\mathbb{R}^{\ell\times k}$ in (298).

######  Remark 20.

For any minimizer $\bm{C}$ in (298), the $\ell$-RV $\bm{C}\bm{Y}^{(n,m)}$ is
the unique orthogonal projection of $\bm{X}$ onto
$\mathscr{P}_{n,m}^{\ell}(\bm{Y})$; in particular, $E_{n}[\bm{X}\mid\bm{Y}]$
is well-defined by (299).

Denote, for $\bm{Y}\in L^{2n}(\mathbb{R}^{m},\mathcal{F}),$

$\bm{M}_{\bm{Y},n}:=\mathbb{E}\left[\bm{Y}^{(n,m)}\left(\bm{Y}^{(n,m)}\right)^{T}\right].$
(300)

For $n\in\mathbb{N}$ and an $\ell$-RV $(X_{1},\cdots,X_{\ell})^{T}=\bm{X}\in
L^{2}(\mathbb{R}^{\ell},\mathcal{F}),$ if $\bm{M}_{\bm{Y},n}$ is invertible,
Lemma 38 yields that

$E_{n}[\bm{X}\mid\bm{Y}]=\left(\begin{array}[]{c}E_{n}[X_{1}\mid\bm{Y}]\\\
\vdots\\\
E_{n}[X_{\ell}\mid\bm{Y}]\end{array}\right)=\left(\begin{array}[]{c}\vspace{2mm}\mathbb{E}\left[X_{1}\bm{Y}^{(n,m)}\right]^{T}\bm{M}_{\bm{Y},n}^{-1}\bm{Y}^{(n,m)}\\\
\vspace{2mm}\vdots\\\
\mathbb{E}\left[X_{\ell}\bm{Y}^{(n,m)}\right]^{T}\bm{M}_{\bm{Y},n}^{-1}\bm{Y}^{(n,m)}\end{array}\right).$
(301)

We say that the $Y_{j}$ do not satisfy a polynomial relation if the monomials
$\prod_{j=1}^{m}Y_{j}^{\alpha_{j}},$ for
$\alpha_{1},\cdots,\alpha_{m}\in\mathbb{N},$ are linearly independent, i.e.,
if the mapping

$\varphi:\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n,m}\to\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n,m}(\bm{Y}),\quad\quad\varphi(p)=p(\bm{Y})$
(302)

is an isomorphism of vector spaces.

Generalizing our results on RVs to $m$-RVs can be done in view of the
following polynomial denseness result.

######  Theorem 39 ([48]).

For any $m$-RV $\bm{Y}=(Y_{1},\cdots,Y_{m})^{T}$ and $q>1,$ if

$\overline{\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n}(Y_{j})}=L^{q}(\sigma(Y_{j}))$
(303)

for each $j\in\\{1,\cdots,m\\},$ then

$\overline{\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n,m}(\bm{Y})}=L^{r}(\sigma(\bm{Y}))$
(304)

for every $r\in[1,q).$

An immediate corollary that we use in this section is as follows.

######  Corollary 40.

Fix an integer $m\geq 1$ and an $m$-RV $\bm{Y}=(Y_{1},\cdots,Y_{m})^{T}.$ If
each of the RVs $Y_{1},\cdots,Y_{m}$ satisfies Carleman’s condition, then the
set of vectors of polynomials
$\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n,m}^{m}(\bm{Y})$ is dense in
$L^{q}(\mathbb{R}^{m},\sigma(\bm{Y}))$ for any $q\geq 1.$

###### Proof.

See Appendix H.2. ∎

We deduce the following result on the convergence of the multivariate PMMSE to
the MMSE.

######  Theorem 41.

Fix an $m$-RV $\bm{Y}=(Y_{1},\cdots,Y_{m})^{T}$ and an $\ell$-RV $\bm{X}\in
L^{2}(\mathbb{R}^{\ell},\mathcal{F}).$ If each $Y_{j}$ satisfies Carleman’s
condition, and if the $Y_{j}$ do not satisfy a polynomial relation, then we
have the $L^{2}(\mathbb{R}^{\ell},\sigma(\bm{Y}))$-limit

$\mathbb{E}[\bm{X}\mid\bm{Y}]=\lim_{n\to\infty}E_{n}[\bm{X}\mid\bm{Y}].$ (305)

###### Proof.

See Appendix H.3. ∎

With the definition of the multivariate PMMSE at hand, we show that the PMMSE
estimate satisfies a tower property similar to the conditional expectation.

######  Proposition 42 (Tower Property).

Fix $n\in\mathbb{N}$ and three RVs $X\in L^{2}(\mathcal{F})$ and
$Y_{1},Y_{2}\in L^{2n}(\mathcal{F}).$ Suppose that
$|\mathrm{supp}(Y_{1})|,|\mathrm{supp}(Y_{2})|>n.$ Then

$E_{n}\left[E_{n}[X\mid Y_{1}]\mid Y_{1},Y_{2}\right]=E_{n}[X\mid Y_{1}],$
(306)

and

$E_{n}\left[E_{n}[X\mid Y_{1},Y_{2}]\mid Y_{2}\right]=E_{n}[X\mid Y_{2}].$
(307)

###### Proof.

See Appendix H.4. ∎

Now, to generalize our results on estimation in Gaussian channels, we first
note a straightforward generalization of the MMSE dimension to the
multidimensional case.

######  Theorem 43.

Fix two square-integrable continuous $m$-RVs $\bm{X}$ and $\bm{N}$ that are
independent. Suppose that $p_{\bm{N}}$ is bounded and that121212The exponent
$m+2$ in (308) may be replaced with $m+1+\varepsilon$ for any $\varepsilon>0,$
see [45, Section 3.2]

$p_{\bm{N}}(\bm{z})=O\left(\|\bm{z}\|^{-(m+2)}\right)$ (308)

as $\|\bm{z}\|\to\infty.$ Then, we have that

$\lim_{t\to\infty}t\cdot\mathrm{mmse}\left(\bm{X}\mid\sqrt{t}\bm{X}+\bm{N}\right)=\mathrm{tr}\leavevmode\nobreak\
\Sigma_{\bm{N}}.$ (309)

###### Proof.

See Appendix I. ∎

The approach for showing the rationality of $t\mapsto\mathrm{pmmse}_{n}(X,t)$
for a RV $X\in L^{2n}(\mathcal{F})$ in Section 5 may be generalized to deduce
rationality of $t\mapsto\mathrm{pmmse}_{n}(\bm{X},t)$ for an $m$-RV $\bm{X}\in
L^{2n}(\mathbb{R}^{m},\mathcal{F}).$ Here, we are denoting
$\mathrm{pmmse}_{n}(\bm{X},t):=\mathrm{pmmse}_{n}(\bm{X}\mid\sqrt{t}\bm{X}+\bm{N}),$
where $\bm{N}\sim\mathcal{N}(\bm{0},\bm{I}_{m})$ is independent of $\bm{X}.$
For brevity, we give a blueprint of how this generalization of rationality can
be obtained.

First, Lemma 20 may be generalized to yield that
$\det\bm{M}_{\sqrt{t}\bm{X}+\bm{N}}$ is a polynomial in $t$ of degree at most
$d_{n,m}$ which is given by

$\displaystyle d_{n,m}$
$\displaystyle:=\sum_{k\in[n]}k\cdot|\\{(\lambda_{1},\cdots,\lambda_{m})\in\mathbb{N}^{m}\leavevmode\nobreak\
;\leavevmode\nobreak\ \lambda_{1}+\cdots+\lambda_{m}=k\\}|$ (310)
$\displaystyle=\sum_{k\in[n]}k\binom{k+m-1}{m-1}=\sum_{k\in[n]}m\binom{k+m-1}{m}=m\binom{n+m}{m+1}.$
(311)

Further, the coefficient of $t^{d_{n,m}}$ in
$\det\bm{M}_{\sqrt{t}\bm{X}+\bm{N}}$ is $\det\bm{M}_{\bm{X}}.$ Note that
$d_{n,1}=d_{n}.$ Then, generalizing Lemma 21 we obtain an analogous expression
to the scalar case given in Theorem 14, namely,

$\mathrm{pmmse}_{n}(\bm{X},t)=\frac{\left(\mathrm{tr}\leavevmode\nobreak\
\Sigma_{\bm{X}}\right)\det\bm{M}_{\bm{N},n}+\cdots+\left(\mathrm{tr}\leavevmode\nobreak\
\Sigma_{\bm{N}}\right)\left(\det\bm{M}_{\bm{X},n}\right)\leavevmode\nobreak\
t^{d_{n,m}-1}}{\det\bm{M}_{\bm{N},n}+\cdots+\left(\det\bm{M}_{\bm{X},n}\right)\leavevmode\nobreak\
t^{d_{n,m}}}.$ (312)

To deduce (312), the multidimensional MMSE dimension result in Theorem 43 is
used, as follows. Note that $\mathrm{tr}\leavevmode\nobreak\
\Sigma_{\bm{N}}=m$ for $\bm{N}\sim\mathcal{N}(\mathbf{0},\bm{I}_{m}).$ By
Theorem 43, we have that $\mathrm{mmse}(\bm{X},t)\sim m/t.$ It is also true
that $\mathrm{lmmse}(\bm{X},t)\sim m/t.$ Therefore,
$\mathrm{pmmse}_{n}(\bm{X},t)\sim m/t$ for every integer $n\geq 1.$ Note that
$\mathrm{pmmse}_{n}(\bm{X},0)=\mathrm{tr}\leavevmode\nobreak\
\Sigma_{\bm{X}}.$ Expression (312) follows.

###  10.3 Mutual Information for Continuous Random Variables

We prove an analogous approximation result to that in Theorem 34 for the
mutual information between continuous RVs.

######  Theorem 44.

For two continuous RVs $X$ and $Y$ whose MGFs exist, if
$\min(h(X),h(Y))>-\infty,$ then the mutual information is given by

$I(X;Y)=\frac{1}{2}\lim_{n\to\infty}\int_{0}^{\infty}\mathrm{pmmse}_{n}(X,t)+\mathrm{pmmse}_{n}(Y,t)-\mathrm{pmmse}_{n}(\bm{W},t)\leavevmode\nobreak\
dt,$ (313)

where $\bm{W}:=(X,Y)^{T}.$

######  Remark 21.

This formula expresses the mutual information between two continuous RVs
entirely in terms of moments, because
$\mathrm{pmmse}_{n}(\mathrel{\;\cdot\;},t)$ is determined completely by the
moments. This is in contrast to the formula in Theorem 34, which expresses the
mutual information between a discrete RV and a continuous RV in terms of
moments along with the expectation operator of the discrete RV.

To prove Theorem 44, we use the following generalization of Theorem 32 to
higher dimensions. For an $m$-RV $\bm{V}\in
L^{2n}(\mathbb{R}^{m},\mathcal{F}),$ we define

$h_{n}(\bm{V}):=\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(\bm{V},t)-\frac{m}{2\pi
e+t}\,dt.$ (314)

######  Theorem 45.

Let $\bm{V}$ be a continuous $m$-RV whose MGF exists. Then, we have a
decreasing sequence

$\frac{1}{2}\log\left((2\pi
e)^{m}\det\bm{\Sigma}_{\bm{V}}\right)=h_{1}(\bm{V})\geq
h_{2}(\bm{V})\geq\cdots\geq h(\bm{V})$ (315)

converging to the differential entropy

$\lim_{n\to\infty}h_{n}(\bm{V})=h(\bm{V}).$ (316)

###### Proof.

In view of monotonicity of $\mathrm{pmmse}_{n}(\bm{V},t)$ in $n,$ and since
$h_{1}(\bm{V})$ is finite, it suffices by the monotone convergence theorem and
the equation

$h(\bm{V})=\frac{1}{2}\int_{0}^{\infty}\mathrm{mmse}(\bm{V},t)-\frac{m}{2\pi
e+t}\,dt$ (317)

to show that $\mathrm{pmmse}_{n}(\bm{V},t)\to\mathrm{mmse}(\bm{V},t)$ as
$n\to\infty.$ Let $\bm{N}\sim\mathcal{N}(0,\bm{I}_{m})$ be independent of
$\bm{V}.$ A simple application of the triangle inequality yields that it
suffices to prove the convergence

$E_{n}\left[\bm{V}\mid\sqrt{t}\bm{V}+\bm{N}\right]\to\mathbb{E}\left[\bm{V}\mid\sqrt{t}\bm{V}+\bm{N}\right].$
(318)

We deduce (318) from Theorem 41, as follows.

Denote $\bm{Z}^{(t)}:=\sqrt{t}\bm{V}+\bm{N},$ and let $Z_{j}^{(t)}$ be the
$j$-th entry of $\bm{Z}^{(t)}.$ Fix $t\geq 0.$ To apply Theorem 41, we only
need to show that the $Z_{j}^{(t)}$ do not satisfy a nontrivial polynomial
relation. We show this by induction on $m.$ The case $m=1$ follows since
$Z_{1}^{(t)}$ is continuous. Assume that we have shown that
$Z_{1}^{(t)},\cdots,Z_{m-1}^{(t)}$ do not satisfy a nontrivial polynomial
relation, and that $m\geq 2.$ Suppose, for the sake of contradiction, that $q$
is a polynomial in $m$ variables such that $q(\bm{Z}^{(t)})=0.$ Write
$q(u_{1},\cdots,u_{m})=\sum_{k\in[d]}q_{k}(u_{1},\cdots,u_{m-1})u_{m}^{k}$ for
some polynomials $q_{k}$ in $m-1$ variables such that $q_{d}\neq 0.$ Squaring
$q(\bm{Z}^{(t)})=0$ and taking the conditional expectation with respect to
$N_{m}$ we obtain

$0=\mathbb{E}\left[q\left(\bm{Z}^{(t)}\right)\right]=\sum_{k\in[2d]}\beta_{k}N_{m}^{k}$
(319)

for some constants $\beta_{k}\in\mathbb{R}$ with
$\beta_{2d}:=\|q_{d}(Z_{1}^{(t)},\cdots,Z_{m-1}^{(t)})\|_{2}^{2}.$ Since
$N_{m}$ is continuous, equation (319) cannot be a nontrivial polynomial
relation for $N_{m}.$ Thus, we must have $\beta_{2d}=0,$ i.e.,
$q_{d}(Z_{1}^{(t)},\cdots,Z_{m-1}^{(t)})=0.$ By the induction hypothesis,
$q_{d}=0$ identically, a contradiction. Therefore, no nontrivial polynomial
relation $q(\bm{Z}^{(t)})=0$ can hold, and the inductive proof is complete.
Finally, applying Theorem 41, we deduce the limit in (318), thereby completing
the proof of the theorem. ∎

Now, we deduce Theorem 44 from Theorem 45.

###### Proof of Theorem 44..

Since $X$ and $Y$ have finite variance, the mutual information $I(X;Y)$ is
shown in [10] to satisfy

$I(X;Y)=\frac{1}{2}\int_{0}^{\infty}\mathbb{E}\left[\left(\mathbb{E}\left[X\mid
Z_{1}^{(t)}\right]-\mathbb{E}\left[X\mid
Z_{1}^{(t)},Z_{2}^{(t)}\right]\right)^{2}\right]dt+\frac{1}{2}\int_{0}^{\infty}\mathbb{E}\left[\left(\mathbb{E}\left[Y\mid
Z_{2}^{(t)}\right]-\mathbb{E}\left[Y\mid
Z_{1}^{(t)},Z_{2}^{(t)}\right]\right)^{2}\right]dt$ (320)

where $Z_{1}^{(t)}:=\sqrt{t}X+N_{1}$ and $Z_{2}^{(t)}:=\sqrt{t}Y+N_{2}.$ We
may rewrite (320) as

$I(X;Y)=\frac{1}{2}\int_{0}^{\infty}\mathrm{mmse}(X,t)+\mathrm{mmse}(Y,t)-\mathrm{mmse}(\bm{W},t)\leavevmode\nobreak\
dt,$ (321)

where $\bm{W}:=(X,Y)^{T}.$ Adding and subtracting $2/(2\pi e+t)$ to the
integrand in (321), and noting that the assumption $\min(h(X),h(Y))>-\infty$
allows us to split the integral, we obtain

$\displaystyle I(X;Y)$
$\displaystyle=\frac{1}{2}\int_{0}^{\infty}\mathrm{mmse}(X,t)-\frac{1}{2\pi
e+t}\,dt+\frac{1}{2}\int_{0}^{\infty}\mathrm{mmse}(Y,t)-\frac{1}{2\pi
e+t}\,dt-\frac{1}{2}\int_{0}^{\infty}\mathrm{mmse}(\bm{W},t)-\frac{2}{2\pi
e+t}\,dt$ (322) $\displaystyle=h(X)+h(Y)-h(\bm{W}).$ (323)

Finally, note that the MGF of $\bm{W}$ exists by the assumption that the MGFs
of $X$ and $Y$ exist. Thus, by Theorem 45, we have that $h_{n}(A)\to h(A)$ for
$A\in\\{X,Y,\bm{W}\\}.$ Hence, we obtain the desired formula

$I(X;Y)=\lim_{n\to\infty}I_{n}(X;Y)$ (324)

where we define

$\displaystyle I_{n}(X;Y)$ $\displaystyle:=h_{n}(X)+h_{n}(Y)-h_{n}(\bm{W})$
(325)
$\displaystyle=\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(X,t)-\frac{1}{2\pi
e+t}\,dt+\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(Y,t)-\frac{1}{2\pi
e+t}\,dt$ $\displaystyle\hskip
159.3356pt-\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(\bm{W},t)-\frac{2}{2\pi
e+t}\,dt$ (326)
$\displaystyle=\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(X,t)+\mathrm{pmmse}_{n}(Y,t)-\mathrm{pmmse}_{n}(\bm{W},t)\leavevmode\nobreak\
dt,$ (327)

and the proof is complete. ∎

##  11 Application: Estimation of Information Measures from Data

The approximations introduced in the previous sections naturally motivate
estimators for information measures. These estimators are based on (i)
approximating moments with sample moments, then (ii) plugging the sample
moments into the formulas we have developed for information measures. Since
the formulas for information measures depend continuously on the underlying
moments, the resulting estimators are asymptotically consistent. Moreover, the
estimators also behave as the target information measure under affine
transformations, being inherently robust to, for example, rescaling of the
samples.

We estimate $h(X)$ from i.i.d. samples $X_{1},\cdots,X_{m}$ as $h_{n}(U)$ for
$U\sim\mathrm{Unif}(\\{X_{1},\cdots,X_{m}\\}).$ More precisely, we introduce
the following estimator of differential entropy.

######  Definition 9.

Let $X,X_{1},\cdots,X_{m}$ be i.i.d. continuous RVs, denote
$\mathcal{S}=\\{X_{j}\\}_{j=1}^{m},$ and consider the uniform RV
$U\sim\mathrm{Unif}(\mathcal{S}).$ We define the $n$-th estimate
$\widehat{h}_{n}(\mathcal{S})$ of the differential entropy $h(X)$ by
$\widehat{h}_{n}(\mathcal{S}):=h_{n}(U).$

The estimator of mutual information $I(X;Y)$ between a discrete $X$ and a
continuous $Y$ is defined next. We utilize Theorem 34. We will need to invert
the Hankel matrices of moments $(\mathbb{E}[V^{i+j}\mid U=u])_{i,j\in[n]}$ for
each $u\in\mathrm{supp}(U),$ where $(U,V)$ is uniformly distributed over the
samples $\mathcal{S}=\\{(X_{j},Y_{j})\\}_{j=1}^{m}.$ These Hankel matrices are
invertible if and only if for each $u\in\\{X_{j}\\}_{j=1}^{m}$ there are more
than $n$ distinct samples $(X_{j},Y_{j})$ for which $X_{j}=u$; equivalently,
the size of the support set of the RV $V$ conditioned on $U=u$ exceeds $n.$
Thus, we remove all values $u$ that appear at most $n$ times in the samples
$\mathcal{S}.$ In other words, we replace $\mathcal{S}$ with the subset

$\mathcal{S}^{(n)}:=\left\\{(X^{\prime},Y^{\prime})\in\mathcal{S}\;;\;|\\{1\leq
i\leq m\;;\;X_{i}=X^{\prime}\\}|>n\right\\}.$ (328)

######  Definition 10.

Let $(X,Y),(X_{1},Y_{1}),\cdots,(X_{m},Y_{m})$ be i.i.d. $2$-RVs such that $X$
is discrete with finite support and $Y$ is continuous, and denote
$\mathcal{S}=\\{(X_{j},Y_{j})\\}_{j=1}^{m}.$ Define
$\mathcal{S}^{(1)}\supseteq\mathcal{S}^{(2)}\supseteq\cdots$ by

$\mathcal{S}^{(n)}:=\left\\{(X^{\prime},Y^{\prime})\in\mathcal{S}\;;\;|\\{1\leq
i\leq m\;;\;X_{i}=X^{\prime}\\}|>n\right\\}.$ (329)

For each $n\geq 1$ such that $\mathcal{S}^{(n)}$ is nonempty, let
$(U^{(n)},V^{(n)})\sim\mathrm{Unif}(\mathcal{S}^{(n)}).$ We define the $n$-th
estimate $\widehat{I}_{n}(\mathcal{S})$ of the mutual information $I(X;Y)$ by
$\widehat{I}_{n}(\mathcal{S}):=I_{n}(U^{(n)};V^{(n)}).$

We show in this section how to implement these estimators numerically, prove
that they are consistent, and discuss their sample complexity. We end the
section by empirically comparing their performance with other estimators from
the literature. For convenience, define the function
$\delta_{X,n}:(0,\infty)\to[0,\infty)$ by

$\delta_{X,n}(t):=\det\bm{M}_{\sqrt{t}X+N,n}$ (330)

for a $2n$-times integrable RV $X.$ Recall that $\delta_{X,n}$ is the
denominator of $\mathrm{pmmse}_{n}(X,\mathrel{\;\cdot\;}).$

###  11.1 Simplification of the Differential Entropy Formula from Moments for
Numerical Stability

We develop the expressions of our approximations of differential entropy
further to avoid possible issues that could arise from numerically computing
the improper integral over $[0,\infty).$ To illustrate this issue, consider
the expression for $h_{2}(X).$ Recall from (21) that a zero-mean unit-variance
RV $X$ satisfies

$\mathrm{pmmse}_{2}(X,t)=\frac{2+4t+(\mathcal{X}_{4}-\mathcal{X}_{3}^{2}-1)t^{2}}{2+6t+(\mathcal{X}_{4}+3)t^{2}+(\mathcal{X}_{4}-\mathcal{X}_{3}^{2}-1)t^{3}}.$
(331)

For example, when $X\sim\mathrm{Unif}([-\sqrt{3},\sqrt{3}]),$ so

$(\mathcal{X}_{1},\mathcal{X}_{2},\mathcal{X}_{3},\mathcal{X}_{4})=\left(0,1,0,\frac{9}{5}\right),$
(332)

we obtain

$\mathrm{pmmse}_{2}(X,t)=\frac{5+10t+2t^{2}}{5+15t+12t^{2}+2t^{3}}.$ (333)

Now, consider the expression for $h_{2}(X)$ in (254), namely,

$h_{2}(X)=\frac{1}{2}\int_{0}^{\infty}\frac{5+10t+2t^{2}}{5+15t+12t^{2}+2t^{3}}-\frac{1}{2\pi
e+t}\,dt.$ (334)

The integral in (334) converges, but a numerical computation might not be able
to capture this convergence as the expression for the integrand is a
difference of non-integrable functions that both decay as $1/t.$ To avoid this
possible issue, we subtract a $1/t$ term from both of these non-integrable
functions. More precisely, denoting differentiation with respect to $t$ by a
prime, we write

$\displaystyle\mathrm{pmmse}_{2}(X,t)$
$\displaystyle=\frac{5+10t+2t^{2}-\frac{1}{3}\delta_{X,2}^{\prime}(t)+\frac{1}{3}\delta_{X,2}^{\prime}(t)}{\delta_{X,2}(t)}$
(335)
$\displaystyle=\frac{2t}{5+15t+12t^{2}+2t^{3}}+\frac{1}{3}\frac{d}{dt}\log\delta_{X,2}(t)$
(336)

and

$\frac{1}{2\pi e+t}=\frac{d}{dt}\log(2\pi e+t).$ (337)

The integrand $\mathrm{pmmse}_{2}(X,t)-1/(2\pi e+t)$ now becomes

$\frac{2t}{5+15t+12t^{2}+2t^{3}}+\frac{d}{dt}\log\frac{\delta_{X,2}(t)^{1/3}}{2\pi
e+t}.$ (338)

The advantage in having the integrand in this form is that the first term is
well-behaved (it decays as $1/t^{2}$), and the second term’s integral can be
given in closed form

$\int_{0}^{\infty}\left(\log\frac{\delta_{X,2}(t)^{1/3}}{2\pi
e+t}\right)^{\prime}\,dt=\log\left(2\pi
e\left(\frac{2}{5}\right)^{1/3}\right).$ (339)

Therefore, equation (334) becomes

$h_{2}(X)=\frac{1}{2}\log\frac{2\pi
e}{(5/2)^{1/3}}+\int_{0}^{\infty}\frac{t}{5+15t+12t^{2}+2t^{3}}\,dt.$ (340)

We use equation (340) instead of (334) for numerical computation. Note that
this resolves the same numerical instability issue when estimating from data:
if $\mathcal{S}=\\{X_{j}\\}_{j=1}^{m}$ is a multiset of i.i.d. samples
distributed according to $P_{X},$ and if $U\sim\mathrm{Unif}(\mathcal{S}),$ we
compute the estimate $\widehat{h}_{2}(\mathcal{S})=h_{2}(U)$ of $h_{2}(X)$ via
an expression analogous to that in (340) where $X$ is replaced with $U.$

The procedure of obtaining expression (340) from (334) can be carried out for
a general $X$ and $n$ such that $\mathbb{E}[X^{2n}]<\infty$ and
$|\mathrm{supp}(X)|>n,$ as follows. Let $\theta_{X,n}:[0,\infty)\to[0,\infty)$
be the polynomial that is the numerator of $\mathrm{pmmse}_{n}(X,t),$ i.e.,
$\theta_{X,n}(t):=\delta_{X,n}(t)\cdot\mathrm{pmmse}_{n}(X,t).$ Thus, we have
that

$\mathrm{pmmse}_{n}(X,t)=\frac{\theta_{X,n}(t)}{\delta_{X,n}(t)}.$ (341)

We define the function $\rho_{X,n}:[0,\infty)\to\mathbb{R}$ by

$\rho_{X,n}(t):=\frac{\theta_{X,n}(t)-d_{n}^{-1}\delta_{X,n}^{\prime}(t)}{2\delta_{X,n}(t)},$
(342)

where $d_{n}=\binom{n+1}{2}.$ By the analysis of the coefficients in
$\mathrm{pmmse}_{n}(X,t)$ proved in Theorem 18, we have that $\rho_{X,n}(0)=0$
and

$\rho_{X,n}(t)=O\left(t^{-2}\right)$ (343)

as $t\to\infty.$ In particular, $\rho_{X,n}$ is integrable over $[0,\infty).$
The following formula for differential entropy directly follows from the
definition of $h_{n}$ in (254).

######  Lemma 46.

For any RV $X$ satisfying $\mathbb{E}[X^{2n}]<\infty$ and
$|\mathrm{supp}(X)|>n,$ we have the formula

$h_{n}(X)=\frac{1}{2}\log\left(2\pi
e\left(\frac{\det\bm{M}_{X,n}}{\det\bm{M}_{N,n}}\right)^{1/d_{n}}\right)+\int_{0}^{\infty}\rho_{X,n}(t)\,dt,$
(344)

where $d_{n}=\binom{n+1}{2},$ $N\sim\mathcal{N}(0,1),$ and $\rho_{X,n}$ is as
defined in (342).

A similar conclusion holds for mutual information in view of equation (272)
that expresses $I_{n}$ in terms of $h_{n}.$

######  Lemma 47.

Fix a discrete RV $X$ with finite support, and a $2n$-times integrable
continuous RV $Y.$ We have that

$\displaystyle
I_{n}(X;Y)=\frac{1}{n(n+1)}\log\frac{\det\bm{M}_{Y,n}}{\prod_{x\in\mathrm{supp}(X)}\left(\det\bm{M}_{Y^{(x)},n}\right)^{P_{X}(x)}}+\int_{0}^{\infty}\rho_{Y,n}(t)-\mathbb{E}_{X}\left[\rho_{Y^{(X)},n}(t)\right]\,dt,$
(345)

where for each $x\in\mathrm{supp}(X)$ we denote by $Y^{(x)}$ the RV $Y$
conditioned on $\\{X=x\\}.$

Note that in Lemmas 46 and 47, the determinants $\det\bm{M}_{A,n}$ and the
rational functions $\rho_{n}(A;t),$ for $A\in\\{X,Y\\}$ or
$A\in\\{Y^{(x)}\leavevmode\nobreak\ ;\leavevmode\nobreak\
x\in\mathrm{supp}(X)\\},$ are completely determined by the first $2n$ moments
of $A.$ To obtain the estimates $\widehat{h}_{n}$ and $\widehat{I}_{n}$ given
samples, the moments of $A$ are replaced with their respective sample moments
in formulas (344) and (345).

###  11.2 Consistency

As sample moments converge almost surely to the moments, and as our
expressions for differential entropy and mutual information depend
continuously on the moments, the continuous mapping theorem yields that the
estimators of differential entropy and mutual information introduced in the
beginning of this section are consistent.

######  Theorem 48.

Let $X$ be a continuous RV that has a MGF. Let $\\{X_{j}\\}_{j=1}^{\infty}$ be
i.i.d. samples drawn according to $P_{X}.$ Then, for every $n\in\mathbb{N},$
we have the almost-sure convergence

$\lim_{m\to\infty}\widehat{h}_{n}\left(\\{X_{j}\\}_{j=1}^{m}\right)=h_{n}(X).$
(346)

Furthermore, we have that

$h(X)=\lim_{n\to\infty}\lim_{m\to\infty}\widehat{h}_{n}\left(\\{X_{j}\\}_{j=1}^{m}\right)$
(347)

where the convergence in $m$ is almost-sure convergence.

###### Proof.

See Appendix J.1. ∎

######  Corollary 49.

Let $X$ be discrete RV with finite support, and $Y$ be a continuous RV with a
MGF. Let $\\{(X_{j},Y_{j})\\}_{j=1}^{\infty}$ be i.i.d. samples drawn
according to $P_{X,Y}.$ For every $n\in\mathbb{N},$ we have the almost-sure
convergence

$\lim_{m\to\infty}\widehat{I}_{n}\left(\\{(X_{j},Y_{j})\\}_{j=1}^{m}\right)=I_{n}(X;Y).$
(348)

Furthermore,

$I(X;Y)=\lim_{n\rightarrow\infty}\lim_{m\rightarrow\infty}\widehat{I}_{n}\left(\\{(X_{j},Y_{j})\\}_{j=1}^{m}\right)$
(349)

where the convergence in $m$ is almost-sure convergence.

###### Proof.

See Appendix J.2. ∎

###  11.3 Sample Complexity

When $X$ is a continuous RV of bounded support, we may derive the following
sample complexity of the estimator of differential entropy in Definition 9
from Hoeffding’s inequality.

######  Proposition 50.

Fix a bounded-support continuous RV $X\in L^{2n}(\mathcal{F}).$ There is a
constant $C=C(X,n)$ such that, for all small enough $\varepsilon,\delta>0,$
any collection $\mathcal{S}$ of i.i.d. samples drawn according to $P_{X}$ of
size

$|\mathcal{S}|>\frac{C}{\varepsilon^{2}}\log\frac{1}{\delta}$ (350)

must satisfy

$\mathrm{Pr}\left\\{\left|\widehat{h}_{n}(\mathcal{S})-h_{n}(X)\right|<\varepsilon\right\\}\geq
1-\delta.$ (351)

###### Proof.

See Appendix K. ∎

From Proposition 50, we may also obtain a sample complexity result for the
estimate $\widehat{I}_{n}$ in Definition 10.

######  Proposition 51.

Fix a finitely-supported discrete RV $X$ and a bounded-support continuous RV
$Y\in L^{2n}(\mathcal{F}).$ There is a constant $C=C(X,Y,n)$ such that, for
all small enough $\varepsilon,\delta>0,$ any collection $\mathcal{S}$ of
i.i.d. samples drawn according to $P_{X,Y}$ of size

$|\mathcal{S}|>\frac{C}{\varepsilon^{2}}\log\frac{1}{\delta}$ (352)

must satisfy

$\mathrm{Pr}\left\\{\left|\widehat{I}_{n}(\mathcal{S})-I_{n}(X;Y)\right|<\varepsilon\right\\}\geq
1-\delta.$ (353)

###### Proof.

See Appendix K.4. ∎

###  11.4 Numerical Results

We compare via synthetic experiments the performance of our estimators131313A
Python code can be found at [49]. against some of the estimators in the
literature.

Our proposed estimator for differential entropy is $\widehat{h}_{10},$ i.e.,
given samples $\mathcal{S}$ of $X$ we estimate $h(X)$ by
$\widehat{h}_{10}(\mathcal{S})$ as given by Definition 9. We compare this
estimator with two estimation methods: $k$-Nearest-Neighbors ($k$-NN), and
Kernel Density Estimation (KDE). The $k$-NN-based method we compare against is
as provided by the Python package ‘entropy_estimators’ [50], which we will
refer to in this section as KSG. The kernel used for the KDE method is
Gaussian, and it is obtained by computing from a set of samples
$\\{X_{j}\\}_{j=1}^{m}$ a kernel $\Phi$ via the Python function
‘scipy.stats.gaussian_kde’ [51]; then, the estimate for differential entropy
will be $\frac{-1}{m}\sum_{j=1}^{m}\log\Phi(X_{j}).$ The parameters for the
KSG and the KDE estimators are the default parameters, namely, $k=3$ for the
KSG estimator, and the bandwidth for the KDE estimator is chosen according to
Scott’s rule (i.e., $m^{-1/(d+4)}$ for a set of $m$ samples of a $d$-RV).

The mutual information is estimated using $\widehat{I_{5}},$ i.e., given
samples $\mathcal{S}$ of $(X,Y)$ our estimate for $I(X;Y)$ will be
$\widehat{I}_{5}(\mathcal{S})$ as given by Definition 10. This estimator is
compared against the partitioning estimator and the Mixed KSG estimator [40]
(which is a $k$-NN-based estimator); we utilize the implementation in [40] for
both estimators. In particular, the parameters are fixed throughout, namely,
we utilize the parameters used in [40] ($k=5$ for the Mixed KSG, and $8$ bins
per dimension for the partitioning estimator).

We perform $250$ independent trials for each experiment and each fixed sample
size, then plot the absolute error as a percentage of the true value (except
for the last experiment, where the ground truth is $0,$ so we plot the
absolute error) against the sample size.

We note that we also performed the mutual information experiments for the
Noisy KSG estimator based on the estimator in [36] (with noise strength
$\sigma=0.01$ as in [40]), but its performance was much worse than the other
estimators, so we do not include it in the plots.

######  Experiment 1.

We estimate the differential entropy of a RV $X$ distributed according to
Wigner’s semicircle distribution, i.e.,

$p_{X}(x):=\frac{2}{\pi}\sqrt{1-x^{2}}\cdot 1_{[-1,1]}(x).$ (354)

The ground truth is $h(X)\approx 0.64473$ nats. We generate a set
$\mathcal{S}$ of i.i.d. samples distributed according to $P_{X}.$ The size of
$\mathcal{S}$ ranges from $800$ to $4000$ in increments of $800,$ and for each
fixed sample size we independently generate $250$ such sets $\mathcal{S}$ (so
we generate a total of $1250$ sets of samples). The differential entropy
$h(X)$ is estimated by three methods: the moments-based estimator that we
propose $\widehat{h}_{10},$ the $k$-NN-based estimator implemented in [50]
(which we refer to as the KSG estimator), and the Gaussian KDE estimator. For
the proposed estimator, we use $\widehat{h}_{10}(\mathcal{S})$ as an estimate
for $h(X).$ For the KSG estimator, we use the default setting, for which
$k=3.$ We also use the default setting for the Gaussian KDE estimator; in
particular, the bandwidth is chosen according to Scott’s Rule as
$m^{-1/(d+4)}$ where $m=|\mathcal{S}|$ and $d=1$ is the dimensionality of $X.$
The percentage relative absolute error in the estimation (e.g.,
$100\cdot|\widehat{h}_{10}(\mathcal{S})/h(X)-1|$) is plotted against the
sample size for the three estimators in Figure 3. The solid lines in Figure 3
are the means of the errors, i.e., the mean in the $250$ independent trials of
the percentage relative absolute error for each fixed sample size in
$\\{800,1600,2400,3200,4000\\}.$ Via bootstrapping, we infer confidence
intervals, which are indicated by the shaded areas around the solid lines in
Figure 3. We see that the proposed estimator outperforms the KSG estimator and
the KDE estimator for this experiment.

Figure 3: Estimation of differential entropy for a semicircle distribution as
in Experiment 1. The vertical axis shows the percentage relative absolute
error in the estimation, e.g., for the proposed estimator it is
$100\cdot|\widehat{h}_{10}(\mathcal{S})/h(X)-1|$ where $\mathcal{S}$ is the
set of samples and $h(X)\approx 0.64473$ nats is the ground truth. The
horizontal axis shows $|\mathcal{S}|,$ the sample size. The proposed estimator
$\widehat{h}_{10}$ outperforms the $k$-NN-based estimator (denoted KSG) and
the Gaussian KDE estimator for this experiment.

######  Experiment 2.

We estimate the differential entropy $h(\bm{X})$ of a random vector
$\bm{X}=(X_{1},X_{2})^{T}$ where $X_{1}$ and $X_{2}$ are i.i.d. distributed
according to Wigner’s semicircle distribution, namely, $\bm{X}$ has the PDF

$p_{\bm{X}}(x,y)=\frac{4}{\pi^{2}}\sqrt{(1-x^{2})(1-y^{2})}\cdot
1_{[-1,1]\times[-1,1]}(x,y).$ (355)

The ground truth is $h(\bm{X})\approx 1.28946$ nats. The same numerical setup
as in Experiment 1 is performed here. The results are plotted in Figure 4,
where we see a similar behavior to the comparison in the 1-dimensional case;
in particular, the proposed estimator outperforms the KSG estimator and the
KDE estimator for this experiment.

Figure 4: Estimation of differential entropy for a 2-dimensional semicircle
distribution as in Experiment 2. The proposed estimator $\widehat{h}_{10}$
outperforms both the KSG and the KDE estimators for this experiment.

######  Experiment 3.

We estimate the differential entropy $h(X)$ of a Gaussian mixture $X$ whose
PDF is given by

$p_{X}(x)=\sum_{i=1}^{4}\frac{p_{i}}{\sqrt{2\pi\sigma_{i}^{2}}}e^{-(x-\mu_{i})^{2}/(2\sigma_{i}^{2})},$
(356)

where

$\displaystyle\bm{p}$ $\displaystyle=(0.1,0.2,0.3,0.4)$ (357)
$\displaystyle\boldsymbol{\mu}$ $\displaystyle=(-2,0,1,5)$ (358)
$\displaystyle\boldsymbol{\sigma}$ $\displaystyle=(1.5,1,2,1).$ (359)

The ground truth is $h(X)\approx 2.34249$ nats. The same numerical setup in
Experiments 1 and 2 is used here. The results are plotted in Figure 5. For
this experiment, the proposed estimator outperforms the KSG estimator, and it
is essentially indistinguishable from the KDE estimator. Note that it is
expected that the KDE estimator performs well in this Gaussian mixture
experiment, since it is designed specifically to approximate densities by
Gaussian mixtures.

Figure 5: Estimation of differential entropy for a Gaussian mixture as in
Experiment 3. The proposed estimator $\widehat{h}_{10}$ outperforms both the
KSG and KDE estimators for this experiment. The plot of the KDE estimator’s
performance is omitted to avoid cluttering, as it lies just above the line for
the proposed estimator but overlaps significantly with its uncertainty region.

######  Experiment 4.

We estimate the differential entropy $h(\bm{X})$ of a random vector $\bm{X}$
that is a mixture of two Gaussians, namely, $\bm{X}$ has the PDF

$p_{\bm{X}}(\bm{x})=\frac{1}{4\pi\sqrt{\det(\bm{A})}}e^{-(\bm{x}-\boldsymbol{\mu})^{T}\bm{A}^{-1}(\bm{x}-\boldsymbol{\mu})/2}+\frac{1}{4\pi\sqrt{\det(\bm{B})}}e^{-(\bm{x}-\boldsymbol{\nu})^{T}\bm{B}^{-1}(\bm{x}-\boldsymbol{\nu})/2},$
(360)

where we have the means $\boldsymbol{\mu}=(-1,-1)^{T}$ and
$\boldsymbol{\nu}=(1,1)^{T},$ and the covariance matrices

$\bm{A}=\left(\begin{array}[]{cc}1&1/2\\\ 1/2&1\end{array}\right)$ (361)

and $\bm{B}=\bm{I}_{2}.$ The ground truth is $h(\bm{X})\approx 3.22406$ nats.
The same numerical setup as in Experiments 1-3 is performed here. The results
are plotted in Figure 6. As in the 1-dimensional case in Experiment 3, the
proposed estimator outperforms the KSG estimator for this experiment. Further,
the proposed estimator also outperforms the KDE estimator in this
2-dimensional setting.

Figure 6: Estimation of differential entropy for a vector Gaussian mixture as
in Experiment 4. The proposed estimator $\widehat{h}_{10}$ outperforms both
the KSG and KDE estimators for this experiment.

######  Experiment 5.

We replicate the mixture-distribution part of the zero-inflated Poissonization
experiment of [40]. In detail, we let $Y\sim\mathrm{Exp}(1),$ and let $X=0$
with probability $0.15$ and $X\sim\mathrm{Pois}(y)$ given that $Y=y$ with
probability $0.85.$ The quantity to be estimated is the mutual information
$I(X;Y),$ and the ground truth is $I(X;Y)\approx 0.25606$ nats. We generate a
set of i.i.d. samples $\mathcal{S}$ according to the distribution $P_{X,Y},$
where $\mathcal{S}$ has size in $\\{800,1600,2400,3200\\}.$ We estimate
$I(X;Y)$ via the proposed estimator by $\widehat{I}_{5}(\mathcal{S}),$ and we
also consider the estimates given by the Mixed KSG estimator and the
partitioning estimator, both as implemented in [40] (including the parameters
used therein). This estimation process is repeated independently $250$ times.
The comparison of estimators’ performance is plotted in Figure 7. The solid
lines indicate the mean percentage relative absolute error, and the shaded
areas indicate confidence intervals obtained via bootstrapping. We see in
Figure 7 that the proposed estimator outperforms the other considered
estimators for this experiment. We also test the affine-transformation
invariance property of the proposed estimator. In particular, we consider
estimating the mutual information from the scaled samples
$\mathcal{S}^{\prime}$ obtained from $\mathcal{S}$ via scaling the $Y$ samples
by $10^{4},$ i.e.,

$\mathcal{S}^{\prime}:=\\{(A,10^{4}B)\leavevmode\nobreak\
;\leavevmode\nobreak\ (A,B)\in\mathcal{S}\\}.$ (362)

Plotted in Figure 8 is a comparison of the same estimators using the same
samples as those used to generate Figure 7, but where $Y$ is processed through
this affine transformation. The ground truth stays unchanged, and so do our
estimator and the partitioning estimator, but the Mixed KSG estimates change.
This experiment illustrates the resiliency of the proposed estimator to affine
transformations. In fact, the computed numerical values in the modified
setting by the proposed estimator differ by no more than $10^{-15}$ nats from
those numerically computed in the original setting for each of the $1000$
different sets of samples $\mathcal{S}$; in theory, these pairs of values are
identical, and the less than $10^{-15}$ discrepancy is an artifact of the
computer implementation. Finally, we note that although the setup is more
general than the assumptions we prove our results under in this paper (as $X$
here is not finitely supported), the proposed estimator outperformed the other
estimators.

Figure 7: Percentage relative absolute error vs. sample size for unscaled
zero-inflated poissonization in Experiment 5. The proposed estimator
$\widehat{I}_{5}$ outperforms both the $k$-NN-based estimator (denoted Mixed
KSG) and the partitioning estimator. Figure 8: Percentage relative absolute
error vs. sample size for the scaled zero-inflated poissonization in
Experiment 5. To generate these plots, we use the same samples that yield the
plots in Figure 7, but we process them through an affine transformation.
Specifically, each sample $(A,B)$ is replaced with $(A,10^{4}B).$ Then the
samples are passed to the three estimators. We see that the proposed estimator
$\widehat{I}_{5}$ is resilient to scaling, i.e., the same performance line in
Figure 7 is observed here too. This is in contrast to the performance of the
Mixed KSG estimator. The partitioning estimator is resilient to scaling, but
its performance is not favorable in this experiment (with above $\%25$
relative absolute error).

######  Experiment 6.

We test for independence under the following settings. We consider independent
$X\sim\mathrm{Bernoulli}(0.5)$ and $Y\sim\mathrm{Unif}([0,2]).$ We estimate
$I(X;Y),$ whose true value is $I(X;Y)=0.$ We employ the same estimation
procedure as in Experiment 5. The results are plotted in Figure 9, which shows
that the proposed estimator predicted independence more accurately than the
other estimators for the same sample size. Note that in this case the plot
shows the absolute error (in nats) rather than the relative absolute error, as
the ground truth is zero.

Figure 9: Absolute error (in nats) vs. sample size for the independence
testing in Experiment 6. The proposed estimator $\widehat{I}_{5}$ outperforms
the Mixed KSG and the partitioning estimators in this experiment.

## Acknowledgements

The authors would like to thank Dr. Shahab Asoodeh (Harvard University) for
pointing out that our approach for expressing the mutual information in terms
of moments is applicable also to differential entropy. The authors are also
grateful to Prof. Alex Dytso (NJIT) for noting that the higher-order
derivatives of the conditional expectation in Gaussian channels are
expressible in terms of the conditional cumulants.

##  Appendix A A Derivation of Equation (58)

Using the notation of [52], we have that

$C_{r}=\sum_{k=1}^{r}(k-1)!\genfrac{\\{}{\\}}{0.0pt}{}{r}{k}_{\geq 2}$ (363)

where $\genfrac{\\{}{\\}}{0.0pt}{}{r}{k}_{\geq 2}$ denotes the number of
partitions of an $r$-element set into $k$ subsets each of which contains at
least $2$ elements (note that there are $(k-1)!$ cyclically-invariant
arrangements of $k$ parts). The exponential generating function of the
sequence $r\mapsto\genfrac{\\{}{\\}}{0.0pt}{}{r}{k}_{\geq 2}$ is
$(e^{x}-1-x)^{k}/k!.$ Now, we may write

$(e^{x}-1-x)^{k}=\sum_{a+b\leq
k}\binom{k}{a,b}(-1)^{k-a}x^{b}\sum_{t\in\mathbb{N}}\frac{(ax)^{t}}{t!}.$
(364)

Therefore, the coefficient of $x^{r}$ in $(e^{x}-1-x)^{k}/k!$ is

$\displaystyle\frac{1}{r!}\genfrac{\\{}{\\}}{0.0pt}{}{r}{k}_{\geq 2}$
$\displaystyle=\sum_{a+b\leq k}\frac{(-1)^{k-a}a^{r-b}}{a!b!(k-a-b)!(r-b)!}$
(365)
$\displaystyle=\frac{1}{r!}\sum_{b=0}^{k}\binom{r}{b}\sum_{a=0}^{k-b}(-1)^{k-a}\frac{a^{r-b}}{a!(k-a-b)!}$
(366)
$\displaystyle=\frac{1}{r!}\sum_{b=0}^{k}\binom{r}{b}\genfrac{\\{}{\\}}{0.0pt}{}{r-b}{k-b}(-1)^{b},$
(367)

which when combined with (363) gives (58).

##  Appendix B Proof of Lemma 2

Assume that $\mathbb{E}\left[|X|^{\deg(p)}\right]=\infty$ (so $\deg(p)\geq
1$), and we will show that $\mathbb{E}\left[|p(X)|\right]=\infty$ too. Let
$k\in[\deg(p)-1]$ be the largest integer for which
$\mathbb{E}\left[|X|^{k}\right]<\infty,$ and write $p(u)=u^{k+1}q(u)+r(u)$ for
a nonzero polynomial $q$ and a remainder $r\in\mathscr{P}_{k}.$ By
monotonicity of norms, $\mathbb{E}\left[|X|^{j}\right]<\infty$ for every
$j\in[k].$ Hence, $r(X)$ is integrable. Therefore, it suffices to prove that
$X^{k+1}q(X)$ is non-integrable, which we show next.

Consider the set $\mathcal{D}=\left\\{u\in\mathbb{R}\leavevmode\nobreak\
;\leavevmode\nobreak\ \left|q(u)\right|<|a|\right\\}$ where $a\neq 0$ is the
leading coefficient of $q.$ If $q$ is constant, then $\mathcal{D}$ is empty,
whereas if $\deg q\geq 1$ then $|q(u)|\to\infty$ as $|u|\to\infty$ implies
that $\mathcal{D}$ is bounded; in either case, there is an $M\in\mathbb{R}$
such that $\mathcal{D}\subset[-M,M].$ Now, writing
$1=1_{\mathcal{D}}+1_{\mathcal{D}^{c}},$ we obtain

$\mathbb{E}\left[|X|^{k+1}|q(X)|\right]\geq|a|\leavevmode\nobreak\
\mathbb{E}\left[|X|^{k+1}1_{\mathcal{D}^{c}}(X)\right].$ (368)

But we also have that

$\infty=\mathbb{E}\left[|X|^{k+1}\right]\leq
M^{k+1}+\mathbb{E}\left[|X|^{k+1}1_{\mathcal{D}^{c}}(X)\right],$ (369)

so $\mathbb{E}\left[|X|^{k+1}1_{\mathcal{D}^{c}}(X)\right]=\infty.$ Therefore,
inequality (368) yields that
$\mathbb{E}\left[\left|X^{k+1}q(X)\right|\right]=\infty,$ concluding the
proof.

##  Appendix C Proofs of Section 3: PMMSE Preliminaries

###  C.1 Proof of Proposition 4: Equivalence of PMMSE Definitions

In this proof, we drop the subscript on the norm, so $\|\mathrel{\;\cdot\;}\|$
is the norm of $L^{2}(\mathcal{F}).$ Let $\\{p_{i}(Y)\\}_{i\in[d]}$ be an
orthonormal basis for $\mathscr{P}_{n}(Y).$ Then, the orthogonal projection,
$E_{n}^{A}[X\mid Y],$ of $X$ onto $\mathscr{P}_{n}(Y)$ is given by

$E_{n}^{A}[X\mid Y]=\sum_{i\in[d]}\langle X,p_{i}(Y)\rangle p_{i}(Y),$ (370)

with $d=\dim\mathscr{P}_{n}(Y)-1.$

We next show that $E_{n}^{A}[X\mid Y]$ is the unique closest element in
$\mathscr{P}_{n}(Y)$ to $X.$ Note that $L^{2}(\mathcal{F})$ is separable.
Extend the orthonormal basis $\\{p_{i}(Y)\\}_{i\in[d]}$ to an orthonormal
basis $\\{p_{i}(Y)\\}_{i\in[d]}\cup\\{f_{j}\\}_{j\in\mathbb{N}}$ for
$L^{2}(\mathcal{F}).$

Fix an arbitrary $q(Y)\in\mathscr{P}_{n}(Y)$ and let
$\bm{a}\in\mathbb{R}^{d+1}$ be such that $q(Y)=\sum_{i\in[d]}a_{i}p_{i}(Y).$
We may expand $X$ as

$X=\sum_{i\in[d]}\langle X,p_{i}(Y)\rangle
p_{i}(Y)+\sum_{j\in\mathbb{N}}\langle X,f_{j}\rangle f_{j}.$ (371)

Then, the projection $E_{n}^{A}[X\mid Y]$ is at least as close to $X$ as
$q(Y)$ is, because

$\displaystyle\left\|X-E_{n}^{A}[X\mid Y]\right\|^{2}$
$\displaystyle=\left\|X-\sum_{i\in[d]}\langle X,p_{i}(Y)\rangle
p_{i}(Y)\right\|^{2}=\left\|\sum_{j\in\mathbb{N}}\langle X,f_{j}\rangle
f_{j}\right\|^{2}=\sum_{j\in\mathbb{N}}|\langle X,f_{j}\rangle|^{2}$ (372)
$\displaystyle\leq\sum_{i\in[d]}|\langle X,p_{i}(Y)\rangle-
a_{i}|^{2}+\sum_{j\in\mathbb{N}}|\langle X,f_{j}\rangle|^{2}$ (373)
$\displaystyle=\left\|\sum_{i\in[d]}(\langle X,p_{i}(Y)\rangle-
a_{i})p_{i}(Y)+\sum_{j\in\mathbb{N}}\langle X,f_{j}\rangle
f_{j}\right\|^{2}=\|X-q(Y)\|^{2}.$ (374)

Finally, we show uniqueness. So, assume that $r\in\mathscr{P}_{n}$ is such
that

$\|X-E_{n}^{A}[X\mid Y]\|=\|X-r(Y)\|,$ (375)

so this value lower bounds $\|X-p(Y)\|$ for any $p(Y)\in\mathscr{P}_{n}(Y).$
Note that $(E_{n}^{A}[X\mid Y]+r(Y))/2\in\mathscr{P}_{n}(Y).$ Hence,
$\|X-(E_{n}^{A}[X\mid Y]+r(Y))/2\|$ is lower bounded by both
$\|X-E_{n}^{A}[X\mid Y]\|$ and $\|X-r(Y)\|.$ We utilize the parallelogram law,
$\|a+b\|^{2}+\|a-b\|^{2}=2\|a\|^{2}+2\|b\|^{2}$ for $a,b\in
L^{2}(\mathcal{F}).$ Setting $a=X-E_{n}^{A}[X\mid Y]$ and $b=X-r(Y)$ in the
parallelogram law, we have that

$\displaystyle 0$ $\displaystyle\leq\|E_{n}^{A}[X\mid
Y]-r(Y)\|^{2}=\|(X-r(Y))-(X-E_{n}^{A}[X\mid Y])\|^{2}$ (376)
$\displaystyle=2\|X-r(Y)\|^{2}+2\|X-E_{n}^{A}[X\mid
Y]\|^{2}-4\|X-(E_{n}^{A}[X\mid Y]+r(Y))/2\|^{2}\leq 0.$ (377)

Therefore, $\|E_{n}^{A}[X\mid Y]-r(Y)\|=0,$ i.e., $E_{n}^{A}[X\mid Y]=r(Y).$
Hence, $E_{n}^{A}[X\mid Y]$ uniquely minimizes $\|X-p(Y)\|$ over
$p(Y)\in\mathscr{P}_{n}(Y).$ Therefore, by definition of $E_{n}^{B}[X\mid Y],$
we get that $E_{n}^{B}[X\mid Y]$ is well defined and that

$E_{n}^{A}[X\mid Y]=E_{n}^{B}[X\mid Y],$ (378)

and the proof is complete.

###  C.2 Proof of Theorem 5: PMMSE Converges to MMSE

First, we show that the limits hold if $Y$ has finite support. Suppose
$\mathrm{supp}(Y)=\\{y_{j}\\}_{j\in[m]}.$ Let $q\in\mathscr{P}_{m}$ be the
polynomial interpolant of $\\{\left(y_{j},\mathbb{E}[X\mid
Y=y_{j}]\right)\\}_{j\in[m]},$ so $q(Y)=\mathbb{E}[X\mid Y].$ Then, for every
$n\geq m,$ we have that $E_{n}[X\mid Y]=q(Y)=\mathbb{E}[X\mid Y].$ Hence, the
limits (102) and (103) hold in this case. Thus, we may assume that
$|\mathrm{supp}(Y)|=\infty.$

By Carleman’s condition, polynomials are dense in $L^{2}(\sigma(Y))$ [5],
i.e.,

$\overline{\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n}(Y)}=L^{2}(\sigma(Y)).$
(379)

In particular, the collection of monomials $\\{Y^{k}\\}_{k\in\mathbb{N}}$ is a
complete set, i.e., if $Z\in L^{2}(\sigma(Y))$ satisfies $\langle
Z,Y^{k}\rangle=0$ for every $k\in\mathbb{N}$ then it must be that $Z=0.$
Further, since $|\mathrm{supp}(Y)|=\infty,$ the monomials are linearly
independent. Hence, applying Gram-Schmidt, one obtains an orthonormal basis
for the Hilbert space $L^{2}(\sigma(Y))$ consisting of polynomials
$\\{q_{k}(Y)\\}_{k\in\mathbb{N}}$ such that $q_{k}\in\mathscr{P}_{k}$ for each
$k\in\mathbb{N}.$

Therefore, we may write

$\mathbb{E}[X\mid Y]=\sum_{k\in\mathbb{N}}\langle\mathbb{E}[X\mid
Y],q_{k}(Y)\rangle q_{k}(Y)$ (380)

where the series converges in the $L^{2}(\sigma(Y))$-norm sense. Further, by
the orthogonality principle for $\mathbb{E}[X\mid Y]$

$\langle\mathbb{E}[X\mid Y],q_{k}(Y)\rangle=\langle X,q_{k}(Y)\rangle$ (381)

for every $k\in\mathbb{N}.$ Now, by the characterization in (86) that
$E_{n}[X\mid Y]$ is the orthogonal projection of $X$ onto
$\mathscr{P}_{n}(Y),$ we know that

$E_{n}[X\mid Y]=\sum_{k=0}^{n}\langle X,q_{k}(Y)\rangle q_{k}(Y)$ (382)

for each $n\in\mathbb{N}$ (note that $\\{q_{k}(Y)\\}_{k\in[n]}$ is an
orthonormal basis for $\mathscr{P}_{n}(Y)$). Therefore,

$\mathbb{E}[X\mid Y]=\lim_{n\to\infty}\sum_{k=0}^{n}\langle X,q_{k}(Y)\rangle
q_{k}(Y)=\lim_{n\to\infty}E_{n}[X\mid Y],$ (383)

i.e., (102) holds.

Finally, for (103), note that

$\displaystyle\mathrm{pmmse}_{n}(X\mid Y)$ $\displaystyle=\|X-E_{n}[X\mid
Y]\|_{2}^{2}$ (384) $\displaystyle\mathrm{mmse}(X\mid Y)$
$\displaystyle=\|X-\mathbb{E}[X\mid Y]\|_{2}^{2}.$ (385)

Since both RVs $E_{n}[X\mid Y]$ and $\mathbb{E}[X\mid Y]$ are elements in
$L^{2}(\sigma(Y)),$ the orthogonality principle of $\mathbb{E}[X\mid Y]$
implies that $X-\mathbb{E}[X\mid Y]$ and $E_{n}[X\mid Y]-\mathbb{E}[X\mid Y]$
are orthogonal. Then, the Pythagorean theorem implies that

$\mathrm{pmmse}_{n}(X\mid Y)-\mathrm{mmse}(X\mid Y)=\|\mathbb{E}[X\mid
Y]-E_{n}[X\mid Y]\|_{2}^{2},$ (386)

and the limit (103) follows from the limit (102).

###  C.3 Proof of Lemma 7: Invertibility of $\bm{M}_{Y,n}$

The matrix $\bm{M}_{Y,n}$ is symmetric. We show that it is positive-
semidefinite, and that it is positive-definite if and only if
$|\mathrm{supp}(Y)|>n.$ For any $\bm{d}\in\mathbb{R}^{n+1},$ we have the
inequality

$\displaystyle\bm{d}^{T}\bm{M}_{Y,n}\bm{d}$
$\displaystyle=\bm{d}^{T}\mathbb{E}\left[\bm{Y}^{(n)}\left(\bm{Y}^{(n)}\right)^{T}\right]\bm{d}=\mathbb{E}\left[\bm{d}^{T}\bm{Y}^{(n)}\left(\bm{Y}^{(n)}\right)^{T}\bm{d}\right]=\mathbb{E}\left[\left|\bm{d}^{T}\bm{Y}^{(n)}\right|^{2}\right]\geq
0,$ (387)

so $\bm{M}_{Y,n}$ is positive-semidefinite. Furthermore, the equality case

$\mathbb{E}\left[\left|\bm{d}^{T}\bm{Y}^{(n)}\right|^{2}\right]=0$ (388)

holds if and only if $\left|\bm{d}^{T}\bm{Y}^{(n)}\right|^{2}=0,$ and this
latter relation holds if and only if $\bm{d}^{T}\bm{Y}^{(n)}=0.$ Therefore,
$\bm{M}_{Y,n}$ is positive-definite if and only if $\bm{d}^{T}\bm{Y}^{(n)}=0$
implies $\bm{d}=\mathbf{0},$ i.e., $\bm{Y}^{(n)}$ does not lie almost surely
in a hyperplane in $\mathbb{R}^{n+1}.$ Finally, $\bm{Y}^{(n)}$ lies almost
surely in a hyperplane in $\mathbb{R}^{n+1}$ if and only if
$|\mathrm{supp}(Y)|\leq n.$ Therefore, the desired result that $\bm{M}_{Y,n}$
is invertible if and only if $|\mathrm{supp}(Y)|>n$ follows.

###  C.4 Proof of Lemma 8: An Orthonormal Basis for $\mathscr{P}_{n}(Y)$

First, note that Lemma 7 implies that $\bm{M}_{Y,n}$ is invertible. To show
orthonormality, we show that the expectation of the outer product of the
random vector

$\bm{V}=\bm{M}_{Y,n}^{-1/2}\bm{Y}^{(n)}$ (389)

is the identity matrix. We have that

$\displaystyle\mathbb{E}\left[\bm{V}\bm{V}^{T}\right]$
$\displaystyle=\mathbb{E}\left[\bm{M}_{Y,n}^{-1/2}\bm{Y}^{(n)}\left(\bm{Y}^{(n)}\right)^{T}\left(\bm{M}_{Y,n}^{-1/2}\right)^{T}\right]=\bm{M}_{Y,n}^{-1/2}\bm{M}_{Y,n}\left(\bm{M}_{Y,n}^{-1/2}\right)^{T}=\bm{I}_{n+1},$
(390)

where we have used that (see (49))

$\bm{M}_{Y,n}^{1/2}\left(\bm{M}_{Y,n}^{1/2}\right)^{T}=\bm{M}_{Y,n}$ (391)

and (see (50))

$\bm{M}_{Y,n}^{-1/2}=\left(\bm{M}_{Y,n}^{1/2}\right)^{-1}.$ (392)

Hence, the entries of the vector $\bm{M}_{Y,n}^{-1/2}\bm{Y}^{(n)}$ form an
orthonormal subset of $\mathscr{P}_{n}(Y).$ Since we have that
$\mathrm{span}(\\{1,\cdots,Y^{n}\\})=\mathscr{P}_{n}(Y),$ and
$\bm{M}_{Y,n}^{-1/2}$ is invertible, we conclude that the entries of
$\bm{M}_{Y,n}^{-1/2}\bm{Y}^{(n)}$ also span $\mathscr{P}_{n}(Y),$ which
completes the proof.

###  C.5 A Second Proof for Theorem 6

By assumption on $Y,$ Lemma 8 yields invertibility of $\bm{M}_{Y,n}.$ Denote

$\bm{c}_{X,Y,n}:=\bm{M}_{Y,n}^{-1}\mathbb{E}\left[X\bm{Y}^{(n)}\right],$ (393)

and we will show that strict convexity of the function
$g:\mathbb{R}^{n+1}\to[0,\infty)$ defined by

$g(\bm{d})=\mathbb{E}\left[\left(X-\bm{d}^{T}\bm{Y}^{(n)}\right)^{2}\right]$

implies that $\bm{c}_{X,Y,n}$ is its unique minimizer. For any
$\bm{d}\in\mathbb{R}^{n+1},$ linearity of expectation implies that the
gradient of $g$ is

$\nabla
g(\bm{d})=\left(\mathbb{E}\left[2Y^{k}\left(\bm{d}^{T}\bm{Y}^{(n)}-X\right)\right]\right)_{0\leq
k\leq n},$

so the Hessian of $g$ is the constant $2\bm{M}_{Y,n}.$ As $\bm{M}_{Y,n}$ is
positive-definite, $g$ is strictly convex. As $\nabla g(\bm{d})={\bf 0}$ is
equivalent to $\bm{M}_{Y,n}\bm{d}=\mathbb{E}\left[X\bm{Y}^{(n)}\right],$ i.e.,
to $\bm{d}=\bm{c}_{X,Y,n},$ the desired result follows.

##  Appendix D Proofs of Section 4: Basic PMMSE Properties

###  D.1 Proof of Proposition 9: PMMSE and Affine Transformations

Set $U=Y+\beta.$ For any $\bm{c}\in\mathbb{R}^{n+1},$

$X+\alpha-\bm{c}^{T}\bm{U}^{(n)}=X-(\bm{M}\bm{c}-\alpha\bm{e}_{1})^{T}\bm{Y}^{(n)},$
(394)

where we define the matrix

$\bm{M}:=\left(\beta^{i-j}\binom{i}{j}\right)_{(i,j)\in[n]^{2}},$ (395)

and we set $\beta^{i-j}\binom{i}{j}=0$ when $j>i$ and
$\beta^{0}\binom{i}{i}=1$ when $\beta=0.$ Then $\bm{M}$ is lower-triangular
with an all-$1$ diagonal, so the inverse $\bm{M}^{-1}$ exists. Thus, the
mapping $\mathbb{R}^{n+1}\to\mathbb{R}^{n+1}$ defined by
$\bm{c}\mapsto\bm{M}\bm{c}-\alpha\bm{e}_{1}$ is invertible (where
$\bm{d}\mapsto\bm{M}^{-1}(\bm{d}+\alpha\bm{e}_{1})$ is the inverse mapping).
Therefore, the following two subsets of $L^{2}(\mathcal{F})$ are equal

$\left\\{X+\alpha-\bm{c}^{T}\bm{U}^{(n)}\leavevmode\nobreak\
;\leavevmode\nobreak\
\bm{c}\in\mathbb{R}^{n+1}\right\\}=\left\\{X-\bm{d}^{T}\bm{Y}^{(n)}\leavevmode\nobreak\
;\leavevmode\nobreak\ \bm{d}\in\mathbb{R}^{n+1}\right\\}.$ (396)

Then, by the definition of the PMMSE, equality (128) holds.

Equation (129) may be treated similarly. First, note that the case $\alpha=0$
is immediate, because then $\alpha X=0\in\mathscr{P}_{n}(\beta Y)$ implies
$\mathrm{pmmse}_{n}(\alpha X\mid\beta Y)=0.$ Assume $\alpha\neq 0.$ Setting
$V=\beta Y,$ one has that for any $\bm{c}\in\mathbb{R}^{n+1}$

$\alpha
X-\bm{c}^{T}\bm{V}^{(n)}=\alpha\left(X-(\bm{L}\bm{c})^{T}\bm{Y}^{(n)}\right)$
(397)

where we define the invertible matrix

$\bm{L}:=\mathrm{diag}\left(\left(\beta^{k}/\alpha\right)_{k\in[n]}\right).$
(398)

As $\bm{c}\mapsto\bm{L}\bm{c}$ is a bijection of $\mathbb{R}^{n+1},$ the
definition of the PMMSE yields equation (129).

###  D.2 Proof of Lemma 11: PMMSE Operator Properties

Let $\bm{e}_{0},\bm{e}_{1},\cdots,\bm{e}_{n}$ denote the standard basis
vectors for $\mathbb{R}^{n+1}.$ For (i), we first note that

$\bm{M}_{Z,n}^{-1}\mathbb{E}\left[\bm{Z}^{(n)}\right]=\bm{e}_{0},$ (399)

because $\mathbb{E}[\bm{Z}^{(n)}]=\bm{M}_{Z,n}\bm{e}_{0}.$ By the formula for
$E_{n}[X\mid Z]$ in Theorem 6

$E_{n}[X\mid
Z]=\mathbb{E}\left[X\bm{Z}^{(n)}\right]^{T}\bm{M}_{Z,n}^{-1}\,\bm{Z}^{(n)}.$
(400)

Taking the expectation and using (399),

$\mathbb{E}\left[E_{n}[X\mid Z]\right]=\mathbb{E}[X].$ (401)

For (ii), we generalize this approach and note that

$\bm{M}_{Z,n}^{-1}\mathbb{E}\left[Z^{j}\bm{Z}^{(n)}\right]=\bm{e}_{j}.$ (402)

for each $j\in[n].$ Then, for any monomial $Z^{j}$ with $j\in[n]$ we have from
(400) and (402) that

$\mathbb{E}\left[E_{n}[X\mid
Z]Z^{j}\right]=\mathbb{E}\left[X\bm{Z}^{(n)}\right]^{T}\bm{e}_{j}=\mathbb{E}[XZ^{j}].$
(403)

In other words, for all $j\in[n],$

$\mathbb{E}\left[(X-E_{n}[X\mid Z])Z^{j}\right]=0.$ (404)

By linearity of expectation, we conclude that for any polynomial
$p\in\mathscr{P}_{n}$

$\mathbb{E}[(X-E_{n}[X\mid Z])p(Z)]=0.$ (405)

Properties (iii)-(vi) follow immediately by Proposition 10. Alternatively, the
linearity in (iii) follows from linearity of expectation in view of the
formula for $E_{n}[\mathrel{\;\cdot\;}\mid Z]$ in (400), the contractivity in
(iv) follows since $0\leq\mathrm{pmmse}_{n}(X\mid
Y)=\|X\|_{2}^{2}-\|E_{n}[X\mid Y]\|_{2}^{2},$ the idempotence in (v) follows
directly from the fact that $E_{n}[X\mid Z]\in\mathscr{P}_{n}(Z),$ and the
self-adjointness in (vi) can be verified via formula (400).

If $X$ and $Z$ are independent, then

$\mathbb{E}\left[X\bm{Z}^{(n)}\right]=\mathbb{E}[X]\leavevmode\nobreak\
\mathbb{E}\left[\bm{Z}^{(n)}\right].$ (406)

Therefore, from
$\bm{M}_{Z,n}^{-1}\mathbb{E}\left[\bm{Z}^{(n)}\right]=\bm{e}_{0}$ in (399),
and in view of formula (400) for $E_{n}[X\mid Z],$ we have that

$E_{n}[X\mid Z]=\mathbb{E}[X]\bm{e}_{0}^{T}\bm{Z}^{(n)}=\mathbb{E}[X],$ (407)

so (vii) follows.

Finally, for (viii), assume that $X$—$Y$—$Z$ is a Markov chain. Then, for
every $j\in[n]$

$\mathbb{E}\left[XZ^{j}\right]=\mathbb{E}\left[\mathbb{E}\left[XZ^{j}\mid
Y\right]\right]=\mathbb{E}\left[\mathbb{E}\left[X\mid
Y\right]\mathbb{E}\left[Z^{j}\mid Y\right]\right].$ (408)

Further, we have that

$\mathbb{E}\left[\mathbb{E}\left[X\mid Y\right]\mathbb{E}\left[Z^{j}\mid
Y\right]\right]=\mathbb{E}\left[\mathbb{E}\left[X\mid Y\right]Z^{j}\right]$
(409)

by the orthogonality property for $\mathbb{E}[\mathrel{\;\cdot\;}\mid Y]$:

$\mathbb{E}\left[\mathbb{E}\left[X\mid
Y\right]\left(Z^{j}-\mathbb{E}\left[Z^{j}\mid Y\right]\right)\right]=0.$ (410)

Combining (408) and (409), we obtain that for every $j\in[n]$

$\mathbb{E}\left[XZ^{j}\right]=\mathbb{E}\left[\mathbb{E}\left[X\mid
Y\right]Z^{j}\right].$ (411)

Multiplying (411) on the right by $\bm{M}_{Z,n}^{-1}\bm{Z}^{(n)},$ the formula
for $E_{n}[\mathrel{\;\cdot\;}\mid Z]$ (see (400)) implies that

$E_{n}\left[X\mid Z\right]=E_{n}\left[\mathbb{E}[X\mid Y]\mid Z\right],$ (412)

as desired.

###  D.3 Proof of Proposition 12: PMMSE for Symmetric RVs

We may assume that $X$ and $Z$ are symmetric around $0,$ since $E_{m}[X+a\mid
X+Z+b]=a+E_{m}[X\mid X+Z]$ for every $m\in\mathbb{N}$ and $a,b\in\mathbb{R}.$
Then, $\mathbb{E}[X^{j}]=\mathbb{E}[Z^{j}]=0$ for every odd $j\in\mathbb{N}.$
Set $Y=X+Z$ and $n=2k.$ Then, $\mathbb{E}[Y^{j}]=0$ for every odd
$j\in\mathbb{N},$ and $\mathbb{E}[XY^{\ell}]=0$ for every even
$\ell\in\mathbb{N}.$ Then, the coefficient of $Y^{n}$ in $E_{n}[X\mid Y]$ is

$\frac{1}{\det\bm{M}_{Y,n}}\sum_{\begin{subarray}{c}\ell\in[n]\\\
\ell\leavevmode\nobreak\
\text{odd}\end{subarray}}\mathbb{E}\left[XY^{\ell}\right]\left[\bm{M}_{Y,n}^{-1}\right]_{\ell,n},$
(413)

where $\left[\bm{M}_{Y,n}^{-1}\right]_{\ell,n}$ denotes the $(\ell,n)$-th
entry of $\bm{M}_{Y,n}^{-1}.$ Fix an odd $\ell\in[n].$ Let $T_{n}^{(\ell,n)}$
denote the set of permutations of $[n]$ that send $\ell$ to $n.$ We have that

$\left[\bm{M}_{Y,n}^{-1}\right]_{\ell,n}=-\sum_{\pi\in
T_{n}^{(\ell,n)}}\mathrm{sgn}(\pi)\prod_{r\in[n]\setminus\\{\ell\\}}\mathbb{E}\left[Y^{r+\pi(r)}\right].$
(414)

We have that, for every $\pi\in T_{n}^{(\ell,n)},$
$\sum_{r\in[n]\setminus\\{\ell\\}}r+\pi(r)=n(n+1)-\ell-n,$ which is odd.
Therefore, for at least one $r\in[n]\setminus\\{\ell\\},$ the integer
$r+\pi(r)$ is odd. Hence, $\mathbb{E}[Y^{r+\pi(r)}]=0,$ implying that
$\left[\bm{M}_{Y,n}^{-1}\right]_{\ell,n}=0.$ As this is true for every odd
$\ell\in[n],$ we conclude that the coefficient of $Y^{n}$ in $E_{n}[X\mid Y]$
is $0,$ i.e., (143) holds. Equation (144) follows from (143) as
$\mathrm{pmmse}_{m}(X\mid Y)=\|X-E_{m}[X\mid Y]\|_{2}^{2}$ for every
$m\in\mathbb{N}.$

##  Appendix E Proofs of Section 5

###  E.1 Proof of Theorem 17: Uniform Convergence of the PMMSE

We start the proof by obtaining from Proposition 5 pointwise convergence. Let
$N\sim\mathcal{N}(0,1)$ be independent of $X.$ We shall verify the assumptions
in Proposition 5 on $\sqrt{t}X+N$ for fixed $t\geq 0$: i) As $N$ is continuous
and $X$ is independent of $N$ we must have
$|\mathrm{supp}(\sqrt{t}X+N)|=\infty,$ and ii) The MGF of $\sqrt{t}X+N$ exists
(it is the product of the MGFs of $\sqrt{t}X$ and $N$) and this implies that
$\sqrt{t}X+N$ satisfies Carleman’s condition [5]. Hence, by Proposition 5, we
get that for every $t\geq 0$

$\lim_{n\to\infty}\mathrm{pmmse}_{n}(X,t)=\mathrm{mmse}(X,t).$ (415)

Now, we show that the convergence is uniform.

Set, for each $n\in\mathbb{N}$ and $t\in[0,\infty),$

$g_{n}(t):=\mathrm{pmmse}_{n}(X,t)-\mathrm{mmse}(X,t)$ (416)

for short. We will show that

$\lim_{n\rightarrow\infty}\sup_{t\in[0,\infty)}g_{n}(t)=0,$ (417)

which is the uniform convergence in (160).

The limit (415) says that

$\lim_{n\to\infty}g_{n}(t)=0$ (418)

for every fixed $t\geq 0.$ In addition, the asymptotics given in Corollary 15
imply that for each fixed $n\in\mathbb{N}$

$\lim_{t\to\infty}g_{n}(t)=0.$ (419)

By definition of the PMMSE as the minimum over sets of increasing size (in
$n$), for each fixed $t\geq 0$ the sequence
$\\{\mathrm{pmmse}_{n}(X,t)\\}_{n\in\mathbb{N}}$ is decreasing. So
$\\{g_{n}\\}_{n\in\mathbb{N}}$ is a pointwise decreasing sequence of functions
(i.e., $g_{1}(t)\geq g_{2}(t)\geq\cdots$ for each fixed $t\geq 0$). Note that
the $g_{n}$ are nonnegative. We finish the proof via Cantor’s intersection
theorem.

Fix $\varepsilon>0.$ For each $n\in\mathbb{N},$ let
$C_{\varepsilon,n}=g^{-1}_{n}([\varepsilon,\infty)),$ where $g^{-1}$ denotes
the set-theoretic inverse. As $\\{g_{n}\\}_{n\in\mathbb{N}}$ is decreasing,
$C_{\varepsilon,1}\supseteq C_{\varepsilon,2}\supseteq\cdots$ is decreasing
too. As each $g_{n}$ is continuous, each $C_{\varepsilon,n}$ is closed.
Further, $\lim_{t\to\infty}g_{1}(t)=0$ implies that $C_{\varepsilon,1}$ is
bounded, hence each $C_{\varepsilon,n}$ is bounded. Thus, each
$C_{\varepsilon,n}$ is compact. But, the intersection
$\bigcap_{n\in\mathbb{N}}C_{\varepsilon,n}$ is empty, for if $t_{0}$ were in
the intersection then $\liminf_{n\to\infty}g_{n}(t_{0})\geq\varepsilon$
violating that $\lim_{n\to\infty}g_{n}(t_{0})=0.$ Hence, by Cantor’s
intersection theorem, it must be that the $C_{\varepsilon,n}$ are eventually
empty, i.e., there is an $m\in\mathbb{N}$ such that
$\sup_{t\in[0,\infty)}g_{n}(t)\leq\varepsilon$ for every $n>m.$ This is
precisely the uniform convergence in (417), and the proof is complete.

###  E.2 Proof of Lemma 19

The integer $i+\pi(i)$ is odd if and only if $i$ and $\pi(i)$ have opposite
parities. Thus, the desired result follows from the following more general
characterization. For any partition $[n]=A\cup B,$ the cardinality of the set

$I:=\left\\{i\in\\{1,\cdots,n\\}\;;\;(i,\pi(i))\in(A\times B)\cup(B\times
A)\right\\}$ (420)

is even. The desired result follows by letting $A$ and $B$ be even and odd
integers, respectively, in $[n].$ Now, we show that the general
characterization holds.

Let $A_{\pi}\subset A$ denote the subset of elements of $A$ that get mapped by
$\pi$ into $B,$ i.e.,

$A_{\pi}:=\\{i\in A\;;\;\pi(i)\in B\\},$ (421)

and define $B_{\pi}$ similarly. Then, $I=A_{\pi}\cup B_{\pi}$ is a partition.
As $|A_{\pi}|=|B_{\pi}|,$ the desired result follows.

###  E.3 Proof of Lemma 21

For each $(i,j)\in[n]^{2}$ let the subset
$T_{n}^{(i,j)}\subset\mathcal{S}_{[n]}$ denote the collection of permutations
sending $i$ to $j,$ i.e.,

$T_{n}^{(i,j)}:=\left\\{\pi\in\mathcal{S}_{[n]}\leavevmode\nobreak\
;\leavevmode\nobreak\ \pi(i)=j\right\\}.$ (422)

We define, for each $(i,j)\in[n]^{2},$ the cofactor functions
$c_{X,n}^{(i,j)}:[0,\infty)\to\mathbb{R}$ and the products
$d_{X,n}^{(i,j)}:[0,\infty)\to\mathbb{R}$ by

$\displaystyle c_{X,n}^{(i,j)}(t)$ $\displaystyle:=\sum_{\pi\in
T_{n}^{(i,j)}}\mathrm{sgn}(\pi)\prod_{k\neq
i}\left(\bm{M}_{\sqrt{t}X+N,n}\right)_{k,\pi(k)},$ (423) $\displaystyle
d_{X,n}^{(i,j)}(t)$ $\displaystyle:=v_{X,i}(t)\leavevmode\nobreak\
c_{X,n}^{(i,j)}(t)\leavevmode\nobreak\ v_{X,j}(t).$ (424)

Here, $\left(\bm{M}_{\sqrt{t}X+N,n}\right)_{a,b}$ is the $(a,b)$-th entry of
$\bm{M}_{\sqrt{t}X+N,n},$ i.e.,

$\left(\bm{M}_{\sqrt{t}X+N,n}\right)_{a,b}=\mathbb{E}\left[\left(\sqrt{t}X+N\right)^{a+b}\right].$
(425)

Note that $c_{X,n}^{(i,j)}(t)$ is the $(i,j)$-th cofactor of
$\bm{M}_{\sqrt{t}X+N,n}.$ The cofactor matrix
$\bm{C}_{X,n}:[0,\infty)\to\mathbb{R}^{(n+1)\times(n+1)}$ of
$t\mapsto\bm{M}_{\sqrt{t}X+N,n}$ is given by

$\displaystyle\bm{C}_{X,n}$
$\displaystyle:=\left(c_{X,n}^{(i,j)}\right)_{(i,j)\in[n]^{2}}.$ (426)

We define the function $D_{X,t}:[0,\infty)\to\mathbb{R}$ by

$D_{X,n}:=\bm{v}_{X,n}^{T}\bm{C}_{X,n}\bm{v}_{X,n}.$ (427)

We have the following two relations. First, $D_{X,n}$ is the sum of the
$d_{X,n}^{(i,j)}$

$D_{X,n}(t)=\sum_{(i,j)\in[n]^{2}}d_{X,n}^{(i,j)}(t).$ (428)

Second, by Cramer’s rule, and because symmetry of the matrix
$\bm{M}_{\sqrt{t}X+N,n}$ implies that its cofactor is equal to its adjugate,
we have the formula

$\bm{M}_{\sqrt{t}X+N,n}^{-1}=\frac{1}{\det\bm{M}_{\sqrt{t}X+N,n}}\leavevmode\nobreak\
\bm{C}_{X,n}.$ (429)

Therefore, we obtain

$F_{X,n}(t)=\frac{D_{X,n}(t)}{\det\bm{M}_{\sqrt{t}X+N,n}}=\frac{\sum_{(i,j)\in[n]^{2}}d_{X,n}^{(i,j)}(t)}{\det\bm{M}_{\sqrt{t}X+N,n}}.$
(430)

Hence, it suffices to study the $d_{X,n}^{(i,j)}.$

We start with a characterization of the cofactors $c_{X,n}^{(i,j)}.$ Namely,
we show that if $i+j$ is even then $c_{X,n}^{(i,j)}(t)$ is a polynomial in
$t,$ and if $i+j$ is odd then $\sqrt{t}c_{X,n}^{(i,j)}(t)$ is a polynomial in
$t.$ If $i+j$ is even, then

$c_{X,n}^{(i,j)}(t)=\sum_{\pi\in
T_{n}^{(i,j)}}\mathrm{sgn}(\pi)\leavevmode\nobreak\
t^{\delta(\pi)/2}\quad\quad\prod_{\mathclap{\begin{subarray}{c}k\in[n]\\\
k+\pi(k)\;\text{odd}\end{subarray}}}\quad
o_{1,X,k+\pi(k)}(t)\quad\quad\prod_{\mathclap{\begin{subarray}{c}r\in[n],\leavevmode\nobreak\
r\neq i\\\ r+\pi(r)\;\text{even}\;\end{subarray}}}\quad e_{1,X,r+\pi(r)}(t),$
(431)

whereas if $i+j$ is odd then

$c_{X,n}^{(i,j)}(t)=\sum_{\pi\in
T_{n}^{(i,j)}}\mathrm{sgn}(\pi)\leavevmode\nobreak\
t^{\frac{\delta(\pi)-1}{2}}\quad\quad\prod_{\mathclap{\begin{subarray}{c}k\in[n],\leavevmode\nobreak\
k\neq i\\\ k+\pi(k)\;\text{odd}\end{subarray}}}\quad
o_{1,X,k+\pi(k)}(t)\quad\quad\prod_{\mathclap{\begin{subarray}{c}r\in[n]\\\
r+\pi(r)\;\text{even}\end{subarray}}}\quad e_{1,X,r+\pi(r)}(t).$ (432)

Thus, evenness of $\delta(\pi)$ for each $\pi\in\mathcal{S}_{[n]}$ implies
that each $c_{X,n}^{(i,j)}(t)$ is a polynomial when $i+j$ is even and that
each $\sqrt{t}c_{X,n}^{(i,j)}(t)$ is a polynomial when $i+j$ is odd. Further,
the degree of $c_{X,n}^{(i,j)}$ for even $i+j$ is upper bounded by

$\frac{\delta(\pi)}{2}+\sum_{k+\pi(k)\;\text{odd}}\frac{k+\pi(k)-1}{2}+\sum_{r+\pi(r)\;\text{even}\,;\,r\neq
i}\frac{r+\pi(r)}{2}=\frac{n(n+1)}{2}-\frac{i+j}{2},$ (433)

whereas the degree of $\sqrt{t}c_{X,n}^{(i,j)}$ and for odd $i+j$ is upper
bounded by

$\frac{\delta(\pi)}{2}+\sum_{k+\pi(k)\;\text{odd}\,;\,k\neq
i}\frac{k+\pi(k)-1}{2}+\sum_{r+\pi(r)\;\text{even}}\frac{r+\pi(r)}{2}=\frac{n(n+1)}{2}-\frac{i+j-1}{2}.$
(434)

We note that both upper bounds are equal to

$\frac{n(n+1)}{2}-\left\lfloor\frac{i+j}{2}\right\rfloor.$ (435)

Finally, considering the terms of highest order, we see that the term

$\sum_{\pi\in
T_{n}^{(i,j)}}\mathrm{sgn}(\pi)\prod_{k\in[n]\setminus\\{i\\}}\mathcal{X}_{k+\pi(k)}$
(436)

is the coefficient of
$t^{\frac{n(n+1)}{2}-\left\lfloor\frac{i+j}{2}\right\rfloor}$ in
$c_{X,n}^{(i,j)}$ when $i+j$ is even and in $\sqrt{t}c_{X,n}^{(i,j)}$ when
$i+j$ is odd.

Now, to show that $D_{X,n}$ is a polynomial, it suffices to check that each
$d_{X,n}^{(i,j)}$ is. We consider separately the parity of $i+j$ and build
upon the characterization of $c_{X,n}^{(i,j)}.$ If $i+j$ is even, so $i$ and
$j$ have the same parity, then

$\mathbb{E}\left[X\left(\sqrt{t}X+N\right)^{i}\right]\mathbb{E}\left[X\left(\sqrt{t}X+N\right)^{j}\right]$

is a polynomial in $t$ of degree at most $(i+j)/2$ with the coefficient of
$t^{(i+j)/2}$ being $\mathcal{X}_{i+1}\mathcal{X}_{j+1}.$ If $i+j$ is odd, so
$i$ and $j$ have different parities, then

$t^{-1/2}\mathbb{E}\left[X\left(\sqrt{t}X+N\right)^{i}\right]\mathbb{E}\left[X\left(\sqrt{t}X+N\right)^{j}\right]$

is a polynomial in $t$ of degree at most $(i+j-1)/2$ with the coefficient of
$t^{(i+j-1)/2}$ being $\mathcal{X}_{i+1}\mathcal{X}_{j+1}.$

Thus, from the characterization of $c_{X,n}^{(i,j)},$ regardless of the parity
of $i+j$ we obtain that $d_{X,n}^{(i,j)}(t)$ is a polynomial in $t$ of degree
at most $n(n+1)/2$ with the coefficient of $t^{n(n+1)/2}$ being

$\mathcal{X}_{i+1}\mathcal{X}_{j+1}\sum_{\pi\in
T_{n}^{(i,j)}}\mathrm{sgn}(\pi)\prod_{k\in[n]\setminus\\{i\\}}\mathcal{X}_{k+\pi(k)}.$
(437)

Summing over all $(i,j)\in[n]^{2},$ we obtain that the coefficient of
$t^{n(n+1)/2}$ in $D_{X,n}(t)$ is

$\sum_{(i,j)\in[n]^{2}}\sum_{\pi\in
T_{n}^{(i,j)}}\mathrm{sgn}(\pi)\mathcal{X}_{i+1}\mathcal{X}_{j+1}\prod_{k\in[n]\setminus\\{i\\}}\mathcal{X}_{k+\pi(k)}.$
(438)

The proof is completed by noting that, for each $i\in[n],$ we have a partition

$\mathcal{S}_{[n]}=\bigcup_{j\in[n]}T_{n}^{(i,j)}.$ (439)

###  E.4 Proof of Lemma 22

The formulas for $a_{X}^{n,0}$ and $b_{X}^{n,0}$ follow by setting $t=0$ in
(213) and (214). Indeed, if $N\sim\mathcal{N}(0,1)$ is independent of $X,$
then

$F_{X,n}(0)=\mathcal{X}_{1}^{2}\leavevmode\nobreak\
\mathbb{E}\left[\bm{N}^{(n)}\right]^{T}\bm{M}_{N,n}^{-1}\leavevmode\nobreak\
\mathbb{E}\left[\bm{N}^{(n)}\right]=\mathcal{X}_{1}^{2}$ (440)

because $\mathbb{E}\left[\bm{N}^{(n)}\right]$ is the leftmost column of
$\bm{M}_{N,n}.$ Therefore,

$a_{X}^{n,0}=\sigma_{X}^{2}\det\bm{M}_{N,n}=\sigma_{X}^{2}b_{X}^{n,0}.$ (441)

Further, by direct computation or using the connection between Hankel matrices
and orthogonal polynomials [53, Appendix A] along with the fact that the
probabilist’s Hermite polynomials $q_{k}$ satisfy the recurrence
$xq_{k}(x)=q_{k+1}(x)+kq_{k-1}(x),$ it follows that
$\det\bm{M}_{N,n}=\prod_{k=1}^{n}k!=G(n+2)$ where $G$ is the Barnes
$G$-function. Equation (219) for $b_{X}^{n,d_{n}}$ is proved in Lemma 20. To
simplify the proof of formula (218) for $b_{X}^{n,1},$ we first show the
shift-invariance stated in (221).

Fix $s\in\mathbb{R}.$ For any i.i.d. RVs $Z,Z_{0},\cdots,Z_{n},$ we have that
(see, e.g., [53, Appendix A])

$\det\bm{M}_{Z,n}=\frac{1}{(n+1)!}\leavevmode\nobreak\
\mathbb{E}\left[\prod_{0\leq i<j\leq n}(Z_{i}-Z_{j})^{2}\right].$ (442)

From equation (442), since $(Z_{i}+s)-(Z_{j}+s)=Z_{i}-Z_{j},$ we obtain that

$\det\bm{M}_{Z+s,n}=\det\bm{M}_{Z,n}.$ (443)

Let $N\sim\mathcal{N}(0,1)$ be independent of $X.$ Then, for every
$t\in[0,\infty),$ considering $Z=\sqrt{t}X+N$ in (443), we obtain

$\det\bm{M}_{\sqrt{t}(X+s)+N,n}=\det\bm{M}_{\sqrt{t}X+N,n}.$ (444)

As both sides of (444) are polynomials in $t,$ we obtain that
$b_{X+s}^{n,j}=b_{X}^{n,j}$ for every $j\in[d_{n}].$ Since we also have
$\mathrm{pmmse}_{n}(X+s,t)=\mathrm{pmmse}_{n}(X,t),$ it follows that

$t\mapsto\sum_{j\in[d_{n}]}a_{X}^{n,j}t^{j}=\mathrm{pmmse}_{n}(X,t)\sum_{j\in[d_{n}]}b_{X}^{n,j}t^{j}$
(445)

is also invariant under shifting $X,$ so we also obtain
$a_{X+s}^{n,j}=a_{X}^{n,j}.$

By the shift-invariance of $b_{X}^{n,1},$ we may assume that
$\mathcal{X}_{1}=0$ (so $\mathcal{X}_{2}=\sigma_{X}^{2}$). Now, as each entry
in $\bm{M}_{\sqrt{t}X+N,n}$ is a polynomial in $\sqrt{t},$ we see that we may
drop any term of order $(\sqrt{t})^{3}$ or above for the sake of finding
$b_{X}^{n,1}$ (which is the coefficient of $t$ in
$\det\bm{M}_{\sqrt{t}X+N,n}$). In other words,

$b_{X}^{n,1}=\det\left(\binom{i+j}{2}\sigma_{X}^{2}\mathbb{E}\left[N^{i+j-2}\right]t+\mathbb{E}\left[N^{i+j}\right]\right)_{(i,j)\in[n]^{2}}.$
(446)

By Leibniz’s formula, we conclude

$b_{X}^{n,1}=\sigma_{X}^{2}\sum_{\begin{subarray}{c}\pi\in\mathcal{S}_{[n]}\\\
k\in[n]\end{subarray}}\mathrm{sgn}(\pi)\binom{k+\pi(k)}{2}\mathbb{E}\left[N^{k+\pi(k)-2}\right]\prod_{i\in[n]\setminus\\{k\\}}\mathbb{E}\left[N^{i+\pi(i)}\right].$
(447)

But, for any non-negative integer $m$

$\binom{m}{2}\mathbb{E}\left[N^{m-2}\right]=\frac{m}{2}\mathbb{E}\left[N^{m}\right].$
(448)

Therefore, (447) simplifies to

$b_{X}^{n,1}=\frac{\sigma_{X}^{2}}{2}\sum_{\begin{subarray}{c}\pi\in\mathcal{S}_{[n]}\\\
k\in[n]\end{subarray}}\mathrm{sgn}(\pi)(k+\pi(k))\prod_{i\in[n]}\mathbb{E}\left[N^{i+\pi(i)}\right].$
(449)

Evaluating the summation over $k$ for each fixed $\pi,$ we obtain that

$b_{X}^{n,1}=\binom{n+1}{2}\sigma_{X}^{2}\sum_{\pi\in\mathcal{S}_{[n]}}\mathrm{sgn}(\pi)\prod_{i\in[n]}\mathbb{E}\left[N^{i+\pi(i)}\right].$
(450)

Finally, by Leibniz’s formula for $\det\bm{M}_{N,n},$ we obtain that

$b_{X}^{n,1}=\binom{n+1}{2}\sigma_{X}^{2}\det\bm{M}_{N,n},$ (451)

as desired.

###  E.5 Formulas for $a_{X}^{n,j}$

We have (see (211)) the polynomial in $t$

$\left(\mathcal{X}_{2}-F_{X,n}(t)\right)\det\bm{M}_{\sqrt{t}X+N,n}=\sum_{j\in[d_{n}]}a_{X}^{n,j}t^{j}.$
(452)

We obtain from (229)

$\mathcal{X}_{2}\det\bm{M}_{\sqrt{t}X+N,n}=\sum_{j\in[d_{n}]}\mathcal{X}_{2}b_{X}^{n,j}t^{j}.$
(453)

The function $t\mapsto F_{X,n}(t)\det\bm{M}_{\sqrt{t}X+N,n}$ was also shown in
Lemma 21 to be a polynomial of degree at most $d_{n}.$ By definition of
$F_{X,n}$ in (175), we obtain that

$F_{X,n}(t)\det\bm{M}_{\sqrt{t}X+N,n}=\bm{v}_{X,n}(t)^{T}\bm{C}_{\sqrt{t}X+N,n}\bm{v}_{X,n}(t),$
(454)

where $\bm{C}_{\sqrt{t}X+N,n}$ is the cofactor matrix of
$\bm{M}_{\sqrt{t}X+N,n}$ and $\bm{v}_{X,n}$ is the vector-valued function
defined in (172) and (173). As the entries in the cofactor matrix are $\pm 1$
times determinants of minors of $\bm{M}_{\sqrt{t}X+N,n},$ we may use Leibniz’s
formula here too. Explicitly, if
$\bm{u}=(u_{0},\cdots,u_{n})^{T}\in\mathbb{R}^{n+1}$ is any vector and
$\bm{H}=(h_{i+j})_{(i,j)\in[n]^{2}}\in\mathbb{R}^{(n+1)\times(n+1)}$ is any
Hankel matrix, and if $\bm{R}$ is the cofactor matrix of $\bm{H},$ then

$\bm{u}^{T}\bm{R}\bm{u}\hskip
5.69054pt=\sum_{(i,\pi)\in[n]\times\mathcal{S}_{[n]}}(-1)^{i+\pi(i)}\hskip
2.84526pt\mathrm{sgn}(\pi)u_{i}u_{\pi(i)}\prod_{r\in[n]\setminus\\{i\\}}h_{r+\pi(r)}.$
(455)

Applying (455) to the triplet

$(\bm{u},\bm{H},\bm{R})=(\bm{v}_{X,n}(t),\bm{M}_{\sqrt{t}X+N,n},\bm{C}_{\sqrt{t}X+N,n}),$
(456)

we obtain a formula for $F_{X,n}(t)\det\bm{M}_{\sqrt{t}X+N,n}$ similar to
(455). Then, analogously to how we obtained (226) from (225), expanding the
powers and expectations we obtain from (454) and (455) that

$\displaystyle F_{X,n}(t)\det\bm{M}_{\sqrt{t}X+N,n}\hskip 8.53581pt=\hskip
28.45274pt\sum_{\mathclap{\begin{subarray}{c}(i,\pi)\in[n]\times\mathcal{S}_{[n]}\\\
(w,z)\in[i]\times[\pi(i)]\\\ k_{r}\in[r+\pi(r)],\leavevmode\nobreak\ \forall
r\in[n]\setminus\\{i\\}\end{subarray}}}\hskip
14.22636ptt^{(w+z+s_{i}(\bm{k}))/2}\gamma_{i,\pi,\bm{k},w,z}\mathcal{X}_{w+1}\mathcal{X}_{z+1}\prod_{r\in[n]\setminus\\{i\\}}\mathcal{X}_{k_{r}},$
(457)

where $\gamma_{i,\pi,\bm{k},w,z}$ are the integers141414An alternative proof
of Lemma 21 is derivable via analysing when these coefficients are nonzero.

$\displaystyle\gamma_{i,\pi,\bm{k},w,z}=(-1)^{i+\pi(i)}\mathrm{sgn}(\pi)\binom{i}{w}\binom{\pi(i)}{z}\mathbb{E}[N^{i-w}]\mathbb{E}[N^{\pi(i)-z}]\prod_{r\in[n]\setminus\\{i\\}}\binom{r+\pi(r)}{k_{r}}\mathbb{E}[N^{r+\pi(r)-k_{r}}],$
(458)

and where we define the restricted sums

$s_{i}(\bm{k})=\sum_{r\in[n]\setminus\\{i\\}}k_{r}.$ (459)

Since $F_{X,n}(t)\det\bm{M}_{\sqrt{t}X+N,n}$ is shown in Lemma 21 to be a
polynomial in $t,$ the summation in (457) may be restricted to run through
only those parameters for which $w+z+s_{i}(\bm{k})$ is even. Therefore,

$\displaystyle F_{X,n}(t)\det\bm{M}_{\sqrt{t}X+N,n}\hskip 8.53581pt=\hskip
5.69054pt\sum_{j\in[d_{n}]}\hskip 2.84526ptt^{j}\hskip
36.98857pt\sum_{\mathclap{\begin{subarray}{c}(i,\pi)\in[n]\times\mathcal{S}_{[n]}\\\
(w,z)\in[i]\times[\pi(i)]\\\ k_{r}\in[r+\pi(r)],\leavevmode\nobreak\ \forall
r\in[n]\setminus\\{i\\}\\\ w+z+s_{i}(\bm{k})=2j\end{subarray}}}\hskip
22.76219pt\gamma_{i,\pi,\bm{k},w,z}\mathcal{X}_{w+1}\mathcal{X}_{z+1}\prod_{r\in[n]\setminus\\{i\\}}\mathcal{X}_{k_{r}}.$
(460)

Now, returning to the definition of the $a_{X}^{n,j}$ in (213)

$\left(\mathcal{X}_{2}-F_{X,n}(t)\right)\det\bm{M}_{\sqrt{t}X+N,n}=\sum_{j\in[d_{n}]}a_{X}^{n,j}t^{j},$
(461)

we obtain that

$\displaystyle a_{X}^{n,j}\hskip 8.53581pt=\hskip
28.45274pt\sum_{\mathclap{\begin{subarray}{c}\pi\in\mathcal{S}_{[n]}\\\
k_{r}\in[r+\pi(r)],\leavevmode\nobreak\ \forall r\in[n]\\\
k_{0}+\cdots+k_{n}=2j\end{subarray}}}\hskip
22.76219pt\beta_{\pi;k_{0},\cdots,k_{n}}\mathcal{X}_{2}\mathcal{X}_{k_{0}}\cdots\mathcal{X}_{k_{n}}\hskip
8.53581pt-\hskip
28.45274pt\sum_{\mathclap{\begin{subarray}{c}(i,\pi)\in[n]\times\mathcal{S}_{[n]}\\\
(w,z)\in[i]\times[\pi(i)]\\\ k_{r}\in[r+\pi(r)],\leavevmode\nobreak\ \forall
r\in[n]\setminus\\{i\\}\\\ w+z+s_{i}(\bm{k})=2j\end{subarray}}}\hskip
28.45274pt\gamma_{i,\pi,\bm{k},w,z}\mathcal{X}_{w+1}\mathcal{X}_{z+1}\prod_{r\in[n]\setminus\\{i\\}}\mathcal{X}_{k_{r}}.$
(462)

From (462), we obtain

$a_{X}^{n,j}\in H_{2j+2,\min(n,2j)+2,\tau_{n}(j)}(X)$ (463)

where

$\tau_{n}(j)=\left\\{\begin{array}[]{cl}2&\text{if }j=0,\\\ 2j+1&\text{if
}1\leq j\leq\frac{n}{2},\\\ 2j&\text{if }\frac{n+1}{2}\leq j\leq n,\\\
2n&\text{if }j>n.\end{array}\right.$ (464)

###  E.6 Proof of Lemma 23

Fix $\varepsilon>0.$ Let $W$ be a discrete RV with finite support such that
$\mathbb{E}\left[W^{k}\right]=\mu_{k}$ for each $k\in[m],$ which exists by the
solution to the truncated Hamburger moment problem [47, Theorem 3.1]. Set
$A=\mathrm{supp}(W),$ and let $\\{q_{a}\\}_{a\in A}\subset[0,1]$ be such that
$p_{W}=\sum_{a\in A}q_{a}\delta_{a}$ is the PMF of $W.$ Then, for each
$k\in[m],$ we have that

$\sum_{a\in A}q_{a}a^{k}=\mu_{k}.$ (465)

For each $s>0,$ $a\in A,$ and $k\in[m],$ we have that

$\int_{a-s}^{a+s}\frac{z^{k}}{2s}\,dz=\frac{(a+s)^{k+1}-(a-s)^{k+1}}{2s(k+1)}.$
(466)

Further, we have the limit

$\lim_{s\to 0^{+}}\frac{(a+s)^{k+1}-(a-s)^{k+1}}{2s(k+1)}=a^{k}.$ (467)

Therefore, there exist constants $\eta_{a,k}>0,$ for $(a,k)\in A\times[m],$
such that $0<s\leq\eta_{a,k}$ implies

$\left|\frac{(a+s)^{k+1}-(a-s)^{k+1}}{2s(k+1)}-a^{k}\right|<\varepsilon.$
(468)

Let $\eta=\min_{(a,k)\in A\times[m]}\eta_{a,k}$ and consider the continuous RV
$Z$ whose PDF is given by

$p_{Z}(z)=\sum_{a\in A}\frac{q_{a}}{2\eta}1_{[a-\eta,a+\eta]}(z).$ (469)

Thus, for each $k\in[m],$

$\mathbb{E}\left[Z^{k}\right]=\sum_{a\in
A}q_{a}\cdot\frac{(a+\eta)^{k+1}-(a-\eta)^{k+1}}{2\eta(k+1)}\in\left(\sum_{a\in
A}q_{a}(a^{k}-\varepsilon),\sum_{a\in
A}q_{a}(a^{k}+\varepsilon)\right)=\left(\mu_{k}-\varepsilon,\mu_{k}+\varepsilon\right),$
(470)

which follow by (466), (468), and (465), respectively.

###  E.7 Proof of Proposition 24

We proceed by induction on $m.$ The case $m=1$ follows because then by
assumption on $p$ we have that $p(k)=0$ for every positive integer $k$ as can
be seen by taking $X\sim\mathcal{N}(k,1),$ but the only polynomial with
infinitely many zeros is the zero polynomial. Now, assume that the statement
of the proposition holds for every polynomial in $m-1$ variables, where $m\geq
2.$

Fix a polynomial $p$ in $m$ variables, and assume that
$p|_{\mathcal{C}^{m}}=0.$ Regarding $p$ as a polynomial in one of the
variables with coefficients being polynomials in the remaining $m-1$
variables, we may write

$p(u_{1},\cdots,u_{m})=\sum_{j\in[d]}p_{j}(u_{1},\cdots,u_{m-1})u_{m}^{j},$
(471)

for some polynomials $p_{0},\cdots,p_{d}$ in $m-1$ variables, where $d$ is the
total degree of $p.$ We show that $p=0$ identically by showing that each
$p_{j}$ vanishes on $\mathcal{C}_{m-1}$ and using the induction hypothesis to
obtain $p_{j}=0$ identically.

Fix $\boldsymbol{\mu}=(\mu_{1},\cdots,\mu_{m-1})\in\mathcal{C}_{m-1}.$ Let
$\mu_{m}$ be a variable, and set $\ell=\lfloor m/2\rfloor.$ We have that
$\ell=(m-1)/2$ if $m$ is odd, and $\ell=m/2$ if $m$ is even. Set
$\bm{H}=(\mu_{i+j})_{(i,j)\in[\ell]^{2}}.$ If $m$ is even, then
$\det\bm{H}=\alpha\mu_{m}+\beta$ for some constants
$\alpha,\beta\in\mathbb{R}$ determined by $\boldsymbol{\mu},$ with
$\alpha=\det(\mu_{i+j})_{(i,j)\in[\ell-1]^{2}}>0.$ In the case $m$ is even, we
set $t=-\beta/\alpha,$ and in the case $m$ is odd, we set $t=0.$ Then,
$\bm{H}$ is positive definite whenever $\mu_{m}>t.$

For each integer $k\geq 1$ and real $\varepsilon>0,$ Lemma 23 yields a RV
$X_{k,\varepsilon}\in\mathcal{R}_{m}$ satisfying

$\delta_{k,j}(\varepsilon):=\mathbb{E}[X_{k,\varepsilon}^{j}]-\mu_{j}\in(-\varepsilon,\varepsilon)$
(472)

for each $j\in\\{1,\cdots,m-1\\}$ and

$\delta_{k,m}(\varepsilon):=\mathbb{E}[X_{k,\varepsilon}^{m}]-(t+k)\in(-\varepsilon,\varepsilon).$
(473)

Then, by assumption on $p,$ for every $\varepsilon>0$ and
$k\in\mathbb{N}_{\geq 1},$

$\sum_{j\in[d]}p_{j}(\mu_{1}+\delta_{k,1}(\varepsilon),\cdots,\mu_{m-1}+\delta_{k,m-1}(\varepsilon))(t+k+\delta_{k,m}(\varepsilon))^{j}=0.$
(474)

Taking the limit $\varepsilon\to 0^{+},$ we deduce that

$\sum_{j\in[d]}p_{j}(\mu_{1},\cdots,\mu_{m-1})(t+k)^{j}=0.$ (475)

Considering (475) as a univariate polynomial in $k,$ we see that its vanishing
at infinitely many values of $k$ implies that

$p_{j}(\mu_{1},\cdots,\mu_{m-1})=0$ (476)

for every $j\in[d].$ This holds for every
$(\mu_{1},\cdots,\mu_{m-1})\in\mathcal{C}_{m-1},$ i.e., the premise of the
proposition applies to each $p_{j}$ (namely, for every $X\in\mathcal{R}_{m-1}$
we have $p_{j}(\mathbb{E}[X],\cdots,\mathbb{E}[X^{m-1}])=0$). By the induction
hypothesis, we obtain $p_{j}=0,$ as polynomials, for every $j\in[d].$
Therefore, $p=0,$ and the proof is complete.

##  Appendix F Proofs of Section 6

###  F.1 Proof of Proposition 27: Conditional Expectation Derivatives

Recall that the conditional expectation can be expressed as

$\mathbb{E}[Z\mid
Y=y]=\frac{\mathbb{E}\left[Ze^{-(X-y)^{2}/2}\right]}{\mathbb{E}\left[e^{-(X-y)^{2}/2}\right]}$
(477)

for any RV $Z$ for which $Ze^{-(X-y)^{2}/2}$ is integrable. This formula
applies for both $Z=X$ and $Z=(X-\mathbb{E}[X\mid Y=y])^{k},$ where
$(y,k)\in\mathbb{R}\times\mathbb{N},$ because they are polynomials in $X$ and
the map $x\mapsto q(x)e^{-(x-y)^{2}/2}$ is bounded for any polynomial $q.$

Differentiating (477) for $Z=X$ and rearranging terms, we obtain

$\frac{d}{dy}\leavevmode\nobreak\ \mathbb{E}[X\mid
Y=y]=\frac{\mathbb{E}\left[(X-\mathbb{E}[X\mid
Y=y])^{2}e^{-(X-y)^{2}/2}\right]}{\mathbb{E}\left[e^{-(X-y)^{2}/2}\right]},$
(478)

i.e., $f^{\prime}=g_{2}.$ Note that $g_{0}\equiv 1$ and $g_{1}\equiv 0.$
Differentiating $g_{r}$ for $r\geq 1,$ we obtain that

$g_{r}^{\prime}=g_{r+1}-rg_{2}g_{r-1}.$ (479)

We apply successive differentiation to $f^{\prime}=g_{2}$ and recover patterns
by utilizing (479) at each step.

From $f^{\prime}=g_{2}$ and (479), we infer the first few derivatives

$f^{(2)}=g_{3},\leavevmode\nobreak\
f^{(3)}=g_{4}-3g_{2}^{2},\leavevmode\nobreak\ f^{(4)}=g_{5}-10g_{2}g_{3}.$
(480)

We see a homogeneity in (480), namely, $f^{(r-1)}$ is an integer linear
combination of terms of the form $g_{i_{1}}^{\alpha_{1}}\cdots
g_{i_{\ell}}^{\alpha_{\ell}}$ with
$i_{1}\alpha_{1}+\cdots+i_{\ell}\alpha_{\ell}=r.$ This homogeneity can be
shown to hold for a general $r$ by induction, which we show next. For most of
the remainder of the proof, we forget the numerical values of the $f^{(k)}$
and the $g_{r}^{(k)}$ and only treat them as symbols satisfying
$f^{\prime}=g_{2}$ and $g_{r}^{\prime}=g_{r+1}-rg_{2}g_{r-1}$ that respect
rules of differentiation and which commute.

We call $\sum_{j=1}^{\ell}i_{j}\alpha_{j}$ the weighted degree of any nonzero
integer multiple of $g_{i_{1}}^{\alpha_{1}}\cdots
g_{i_{\ell}}^{\alpha_{\ell}}.$ This is a well-defined degree because it is
invariant to the way the product is arranged. We also say that a sum is of
weighted degree $r$ if each summand is of weighted degree $r.$ To prove the
claim of homogeneity, i.e., that $f^{(r-1)}$ is of weighted degree $r,$ we
differentiate and apply the relation in (479) to a generic term
$g_{i_{1}}^{\alpha_{1}}\cdots g_{i_{\ell}}^{\alpha_{\ell}}$ whose weighted
degree is $r.$ We have the derivative

$\left(g_{i_{1}}^{\alpha_{1}}\cdots
g_{i_{\ell}}^{\alpha_{\ell}}\right)^{\prime}=\left(g_{i_{1}}^{\alpha_{1}}\right)^{\prime}\cdots
g_{i_{\ell}}^{\alpha_{\ell}}+\cdots+g_{i_{1}}^{\alpha_{1}}\cdots\left(g_{i_{\ell}}^{\alpha_{\ell}}\right)^{\prime}.$
(481)

From (479), for integers $i,\alpha\geq 1,$

$\left(g_{i}^{\alpha}\right)^{\prime}=\alpha g_{i}^{\alpha-1}g_{i+1}-\alpha
ig_{2}g_{i-1}g_{i}^{\alpha-1}.$ (482)

Therefore, the derivative of $g_{i}^{\alpha}$ has weighted degree $i\alpha+1.$
In other words, differentiation increased the weighted degree of
$g_{i}^{\alpha}$ by $1.$ From (481), then, we see that the weighted degree of
$\left(g_{i_{1}}^{\alpha_{1}}\cdots
g_{i_{\ell}}^{\alpha_{\ell}}\right)^{\prime}$ is $r+1.$ Since
$f^{\prime}=g_{2}$ is of weighted degree $2,$ induction and linearity of
differentiation yield that $f^{(r-1)}$ is of weighted degree $r$ for each
$r\geq 2.$

Now, we fix the way we are writing products of the $g_{i}.$ We ignore
explicitly writing $g_{0}$ and $g_{1},$ collect identical terms into an
exponent, and write lower indices first. One way to keep this notation is via
integer partitions. Consider the “homogeneous” sets

$G_{r}:=\left\\{\sum_{\boldsymbol{\lambda}\in\Pi_{r}}\beta_{\boldsymbol{\lambda}}\bm{g}^{\boldsymbol{\lambda}}\leavevmode\nobreak\
;\leavevmode\nobreak\
\beta_{\boldsymbol{\lambda}}\in\mathbb{Z}\leavevmode\nobreak\ \text{for
each}\leavevmode\nobreak\ \boldsymbol{\lambda}\in\Pi_{r}\right\\}.$ (483)

The homogeneity property for the derivatives of $f$ can be written as
$f^{(r-1)}\in G_{r}$ for each $r\geq 2.$

Next, we investigate the exact integer coefficients $h_{\boldsymbol{\lambda}}$
in the expression of the derivatives of $f$ in terms of the
$\bm{g}^{\boldsymbol{\lambda}}.$ Homogeneity of the derivatives of $f$ says
that we may write each $f^{(r-1)},$ $r\geq 2,$ as an integer linear
combination of
$\\{\bm{g}^{\boldsymbol{\lambda}}\\}_{\boldsymbol{\lambda}\in\Pi_{r}}.$ One
way to obtain such a representation is via repeated differentiation of
$f^{\prime}=g_{2},$ applying the relation (482), and discarding any term that
is a multiple of $g_{1}.$ Applying these steps, we arrive at representations

$f^{(r-1)}=\sum_{\boldsymbol{\lambda}\in\Pi_{r}}h_{\boldsymbol{\lambda}}\bm{g}^{\boldsymbol{\lambda}},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
c_{\boldsymbol{\lambda}}\in\mathbb{Z}.$ (484)

The terms $\bm{g}^{\boldsymbol{\nu}}$ that appear upon differentiating a term
$\bm{g}^{\boldsymbol{\lambda}}$ can be described as follows. For
$(\lambda_{2},\cdots,\lambda_{\ell})=\boldsymbol{\lambda}\in\Pi_{r},$ we call
$\lambda_{2}$ the leading term of $\boldsymbol{\lambda}.$ Consider for a tuple
$\boldsymbol{\lambda}\in\Pi_{r}$ the following two sets of tuples
$\tau_{+}(\boldsymbol{\lambda}),\tau_{-}(\boldsymbol{\lambda})\subset\Pi_{r+1}$:

  * •

The set $\tau_{+}(\boldsymbol{\lambda})$ consists of all tuples obtainable
from $\boldsymbol{\lambda}$ via replacing a pair $(\lambda_{i},\lambda_{i+1})$
with $(\lambda_{i}-1,\lambda_{i+1}+1)$ (so, necessarily $\lambda_{i}\geq 1$)
while keeping all other entries unchanged;

  * •

The set $\tau_{-}(\boldsymbol{\lambda})$ consists of all tuples obtainable
from $\boldsymbol{\lambda}$ via replacing a pair
$(\lambda_{i-1},\lambda_{i}),$ for which $i\geq 3,$ with the pair
$(\lambda_{i-1}+1,\lambda_{i}-1)$ (so, necessarily $\lambda_{i}\geq 1$) and
additionally increasing the leading term by $1$ while keeping all other terms
unchanged.

For example, if $\boldsymbol{\lambda}=(0,5,0,1)\in\Pi_{20}$ then

$\tau_{+}(\boldsymbol{\lambda})=\\{(0,4,1,1),(0,5,0,0,1)\\}\subset\Pi_{21}$
(485)

and

$\tau_{-}(\boldsymbol{\lambda})=\\{(2,4,0,1),(1,5,1)\\}\subset\Pi_{21}.$ (486)

The relation (482) yields, in view of

$\left(g_{2}^{\lambda_{2}}\cdots
g_{\ell}^{\lambda_{\ell}}\right)^{\prime}=\left(g_{2}^{\lambda_{2}}\right)^{\prime}\cdots
g_{\ell}^{\lambda_{\ell}}+\cdots+g_{2}^{\lambda_{2}}\cdots\left(g_{\ell}^{\lambda_{\ell}}\right)^{\prime},$
(487)

that

$\left(\bm{g}^{\boldsymbol{\lambda}}\right)^{\prime}=\sum_{\boldsymbol{\nu}\in\tau_{+}(\boldsymbol{\lambda})}a_{\boldsymbol{\lambda},\boldsymbol{\nu}}\bm{g}^{\boldsymbol{\nu}}-\sum_{\boldsymbol{\nu}\in\tau_{-}(\boldsymbol{\lambda})}b_{\boldsymbol{\lambda},\boldsymbol{\nu}}\bm{g}^{\boldsymbol{\nu}}$
(488)

for some positive integers $a_{\boldsymbol{\lambda},\boldsymbol{\nu}}$ and
$b_{\boldsymbol{\lambda},\boldsymbol{\nu}},$ which we describe next. Finding
$a_{\boldsymbol{\lambda},\boldsymbol{\nu}}$ and
$b_{\boldsymbol{\lambda},\boldsymbol{\nu}}$ can be straightforwardly done from
(482) in view of (487). If
$\boldsymbol{\nu}\in\tau_{+}(\boldsymbol{\lambda}),$ say

$(\nu_{i},\nu_{i+1})=(\lambda_{i}-1,\lambda_{i+1}+1),$ (489)

then $a_{\boldsymbol{\lambda},\boldsymbol{\nu}}=\lambda_{i}.$ If
$\boldsymbol{\nu}\in\tau_{-}(\boldsymbol{\lambda}),$ say

$(\nu_{i-1},\nu_{i})=(\lambda_{i-1}+1,\lambda_{i}-1),$ (490)

then $b_{\boldsymbol{\lambda},\boldsymbol{\nu}}=i\lambda_{i}.$ In our example
of $\boldsymbol{\lambda}=(0,5,0,1),$ we get

$\displaystyle a_{(0,5,0,1),(0,4,1,1)}$ $\displaystyle=5$ (491) $\displaystyle
a_{(0,5,0,1),(0,5,0,0,1)}$ $\displaystyle=1,$ (492)

whereas

$\displaystyle b_{(0,5,0,1),(2,4,0,1)}$ $\displaystyle=15$ (493)
$\displaystyle b_{(0,5,0,1),(1,5,1)}$ $\displaystyle=5.$ (494)

Note that the two sets $\tau_{+}(\boldsymbol{\lambda})$ and
$\tau_{-}(\boldsymbol{\lambda})$ are disjoint because, e.g., the sum of
entries of a tuple in $\tau_{+}(\boldsymbol{\lambda})$ is the same as that for
$\boldsymbol{\lambda},$ whereas the sum of entries of a tuple in
$\tau_{-}(\boldsymbol{\lambda})$ is one more than that for
$\boldsymbol{\lambda}.$

We next describe how to use what we have shown thus far to deduce a recurrence
relation for the $h_{\boldsymbol{\lambda}}.$ Let $\theta$ be a process
inverting $\tau,$ i.e., define for $\boldsymbol{\nu}\in\Pi_{r+1}$ the two sets

$\theta_{+}(\boldsymbol{\nu}):=\left\\{\boldsymbol{\lambda}\in\Pi_{r}\leavevmode\nobreak\
;\leavevmode\nobreak\
\boldsymbol{\nu}\in\tau_{+}(\boldsymbol{\lambda})\right\\}$ (495)

and

$\theta_{-}(\boldsymbol{\nu}):=\left\\{\boldsymbol{\lambda}\in\Pi_{r}\leavevmode\nobreak\
;\leavevmode\nobreak\
\boldsymbol{\nu}\in\tau_{-}(\boldsymbol{\lambda})\right\\}$ (496)

The two sets $\theta_{+}(\boldsymbol{\nu})$ and $\theta_{-}(\boldsymbol{\nu})$
are disjoint because the two sets $\tau_{+}(\boldsymbol{\lambda})$ and
$\tau_{-}(\boldsymbol{\lambda})$ are disjoint for each fixed
$\boldsymbol{\lambda}.$ Recall our process for defining
$h_{\boldsymbol{\lambda}}$: we start with $f^{\prime}=g_{2},$ so $h_{(1)}=1$;
we successively differentiate $f^{\prime}=g_{2}$; after each differentiation,
we use (482) and (487) (recall that we have the understanding $g_{i}^{0}=1$);
we discard any ensuing multiple of $g_{1}$; after $r-2$ differentiations, we
get an equation
$f^{(r-1)}=\sum_{\boldsymbol{\lambda}\in\Pi_{r}}h_{\boldsymbol{\lambda}}\bm{g}^{\boldsymbol{\lambda}},$
which we take to be the definition of the $h_{\boldsymbol{\lambda}}.$ The
point here is that it could be that $f^{(r-1)}$ is representable as an integer
linear combination of the $\bm{g}^{\boldsymbol{\lambda}}$ in more than one
way, which can only be verified after the numerical values for the $g_{i}$ are
taken into account, but we are not doing that: our approach treats the $g_{i}$
as symbols following the laid out rules. Now, we look at one of the steps of
this procedure, starting at differentiating
$f^{(r-1)}=\sum_{\boldsymbol{\lambda}\in\Pi_{r}}h_{\boldsymbol{\lambda}}\bm{g}^{\boldsymbol{\lambda}},$
so
$f^{(r)}=\sum_{\boldsymbol{\lambda}\in\Pi_{r}}h_{\boldsymbol{\lambda}}\left(\bm{g}^{\boldsymbol{\lambda}}\right)^{\prime}.$
Replacing $(\bm{g}^{\boldsymbol{\lambda}})^{\prime}$ via (488),

$f^{(r)}=\sum_{\boldsymbol{\lambda}\in\Pi_{r}}\left(\sum_{\boldsymbol{\nu}\in\tau_{+}(\boldsymbol{\lambda})}a_{\boldsymbol{\lambda},\boldsymbol{\nu}}\bm{g}^{\boldsymbol{\nu}}-\sum_{\boldsymbol{\nu}\in\tau_{-}(\boldsymbol{\lambda})}b_{\boldsymbol{\lambda},\boldsymbol{\nu}}\bm{g}^{\boldsymbol{\nu}}\right).$
(497)

Exchanging the order of summations (for which we use $\theta$),

$f^{(r)}=\sum_{\boldsymbol{\nu}\in\Pi_{r+1}}\left(\sum_{\boldsymbol{\lambda}\in\theta_{+}(\boldsymbol{\nu})}h_{\boldsymbol{\lambda}}a_{\boldsymbol{\lambda},\boldsymbol{\nu}}-\sum_{\boldsymbol{\lambda}\in\theta_{-}(\boldsymbol{\nu})}h_{\boldsymbol{\lambda}}b_{\boldsymbol{\lambda},\boldsymbol{\nu}}\right)\bm{g}^{\boldsymbol{\nu}}.$
(498)

Therefore, by definition of the $h_{\boldsymbol{\lambda}},$ we have the
recurrence: for each $\boldsymbol{\nu}\in\Pi_{r+1}$

$h_{\boldsymbol{\nu}}=\sum_{\boldsymbol{\lambda}\in\theta_{+}(\boldsymbol{\nu})}h_{\boldsymbol{\lambda}}a_{\boldsymbol{\lambda},\boldsymbol{\nu}}-\sum_{\boldsymbol{\lambda}\in\theta_{-}(\boldsymbol{\nu})}h_{\boldsymbol{\lambda}}b_{\boldsymbol{\lambda},\boldsymbol{\nu}},\quad
h_{(1)}=1.$ (499)

One instance of this recurrence is, e.g.,

$h_{(2,1)}=3h_{(3)}-4h_{(1,0,1)}-6h_{(0,2)}.$ (500)

Now, we show that the recurrence in (499) also generates
$e_{\boldsymbol{\lambda}}$ as defined in (57). For
$(\lambda_{2},\cdots,\lambda_{\ell})=\boldsymbol{\lambda}\in\Pi_{r},$ denote
$\sigma(\boldsymbol{\lambda})=\lambda_{2}+\cdots+\lambda_{\ell}.$ If
$\boldsymbol{\nu}\in\tau_{+}(\boldsymbol{\lambda})$ then
$\sigma(\boldsymbol{\nu})=\sigma(\boldsymbol{\lambda}),$ and if
$\boldsymbol{\nu}\in\tau_{-}(\boldsymbol{\lambda})$ then
$\sigma(\boldsymbol{\nu})=\sigma(\boldsymbol{\lambda})+1.$ Therefore,
$\boldsymbol{\lambda}\in\theta_{+}(\boldsymbol{\nu})$ implies
$\sigma(\boldsymbol{\nu})=\sigma(\boldsymbol{\lambda}),$ and
$\boldsymbol{\lambda}\in\theta_{-}(\boldsymbol{\nu})$ implies
$\sigma(\boldsymbol{\nu})=\sigma(\boldsymbol{\lambda})+1.$ Multiplying (499)
by $(-1)^{\sigma(\boldsymbol{\nu})-1}$ yields the equivalent recurrence

$t_{\boldsymbol{\nu}}=\sum_{\boldsymbol{\lambda}\in\theta_{+}(\boldsymbol{\nu})}t_{\boldsymbol{\lambda}}a_{\boldsymbol{\lambda},\boldsymbol{\nu}}+\sum_{\boldsymbol{\lambda}\in\theta_{-}(\boldsymbol{\nu})}t_{\boldsymbol{\lambda}}b_{\boldsymbol{\lambda},\boldsymbol{\nu}},\quad
t_{(1)}=1,$ (501)

where
$t_{\boldsymbol{\lambda}}:=(-1)^{\sigma(\boldsymbol{\lambda})-1}h_{\boldsymbol{\lambda}}.$
We show that
$c_{\boldsymbol{\lambda}}=(-1)^{\sigma(\boldsymbol{\lambda})-1}e_{\boldsymbol{\lambda}}$
(see (57)) satisfies this recurrence, which is equivalent to
$e_{\boldsymbol{\lambda}}$ satisfying the recurrence (499). Clearly,
$c_{(1)}=1,$ so consider $c_{\boldsymbol{\nu}}$ for
$\boldsymbol{\nu}\in\Pi_{r}$ with $r\geq 3.$

Consider labelled elements $s_{1},s_{2},\cdots,$ and let
$S_{k}=\\{s_{1},\cdots,s_{k}\\}$ for each $k\geq 2.$ For any
$\boldsymbol{\lambda}\in\Pi_{k},$ let $\mathcal{C}_{\boldsymbol{\lambda}}$ be
the set of arrangements of cyclically-invariant set-partitions of $S_{k}$
according to $\boldsymbol{\lambda},$ so
$|\mathcal{C}_{\boldsymbol{\lambda}}|=c_{\boldsymbol{\lambda}}.$ Now, fix
$\boldsymbol{\nu}\in\Pi_{r+1},$ and we will build
$\mathcal{C}_{\boldsymbol{\nu}}$ from the $\mathcal{C}_{\boldsymbol{\lambda}}$
where $\boldsymbol{\lambda}$ ranges over
$\theta_{+}(\boldsymbol{\nu})\cup\theta_{-}(\boldsymbol{\nu}).$ Consider first
$\boldsymbol{\lambda}\in\theta_{+}(\boldsymbol{\nu}),$ where a partition in
$\mathcal{C}_{\boldsymbol{\nu}}$ is constructed from a partition in
$\mathcal{C}_{\boldsymbol{\lambda}}$ by appending $s_{r+1}$ to one of the
parts of the latter partition. Note that adding $s_{r+1}$ to two distinct
partitions of $S_{r}$ cannot produce the same partition of $S_{r+1}$; indeed,
just removing $s_{r+1}$ shows that that is impossible. Now, let $i$ be the
unique index such that $(\nu_{i},\nu_{i+1})=(\lambda_{i}-1,\lambda_{i+1}+1).$
Then, a partition $\mathcal{P}\in\mathcal{C}_{\boldsymbol{\nu}}$ of $S_{r+1}$
is induced by a partition
$\mathcal{P}^{\prime}\in\mathcal{C}_{\boldsymbol{\lambda}}$ of $S_{r}$ if and
only if $s_{r+1}$ is added to a part in $\mathcal{P}^{\prime}$ of size $i,$ of
which there are exactly
$\lambda_{i}=a_{\boldsymbol{\lambda},\boldsymbol{\nu}}.$ Therefore, we get a
contribution of
$\sum_{\boldsymbol{\lambda}\in\theta_{+}(\boldsymbol{\nu})}c_{\boldsymbol{\lambda}}a_{\boldsymbol{\lambda},\boldsymbol{\nu}}$
towards $c_{\boldsymbol{\nu}},$ which is the first part in (501).

For the second part,
$\sum_{\boldsymbol{\lambda}\in\theta_{-}(\boldsymbol{\nu})}c_{\boldsymbol{\lambda}}b_{\boldsymbol{\lambda},\boldsymbol{\nu}},$
we consider the remaining ways of generating a partition in
$\mathcal{C}_{\boldsymbol{\nu}}$ from a partition according to some
$\boldsymbol{\lambda}\in\theta_{-}(\boldsymbol{\nu}).$ In this case, $s_{r+1}$
is not appended to an existing part, but it is used to create a new part of
size $2.$ Thus, we need to also move an element $s_{j},$ $1\leq j\leq r,$ from
a part of size at least $3$ to be combined with $s_{r+1}$ to create a new part
of size $2.$ It is also clear in this case that such a procedure applied to
two distinct partitions in $\mathcal{C}_{\boldsymbol{\lambda}}$ cannot produce
the same partition in $\mathcal{C}_{\boldsymbol{\nu}}.$ Let $i$ be the unique
index for which $(\nu_{i-1},\nu_{i})=(\lambda_{i-1}+1,\lambda_{i}-1).$ There
are $\lambda_{i}$ parts to choose from, and $i$ elements to choose from once a
part is chosen, so there are a total of
$i\lambda_{i}=b_{\boldsymbol{\lambda},\boldsymbol{\nu}}$ ways to generate a
partition in $\mathcal{C}_{\boldsymbol{\nu}}$ from a partition in
$\mathcal{C}_{\boldsymbol{\lambda}}.$ This gives the second sum in (501), and
we conclude that

$c_{\boldsymbol{\nu}}=\sum_{\boldsymbol{\lambda}\in\theta_{+}(\boldsymbol{\nu})}c_{\boldsymbol{\lambda}}a_{\boldsymbol{\lambda},\boldsymbol{\nu}}+\sum_{\boldsymbol{\lambda}\in\theta_{-}(\boldsymbol{\nu})}c_{\boldsymbol{\lambda}}b_{\boldsymbol{\lambda},\boldsymbol{\nu}}.$
(502)

Therefore, the $c_{\boldsymbol{\lambda}}$ and the $t_{\boldsymbol{\lambda}}$
satisfy the same recurrence, which takes the form: for
$\boldsymbol{\nu}\in\Pi_{r+1}$ there are integers
$\\{d_{\boldsymbol{\lambda},\boldsymbol{\nu}}\\}_{\boldsymbol{\lambda}\in\Pi_{r}}$
such that

$u_{\boldsymbol{\nu}}=\sum_{\boldsymbol{\lambda}\in\Pi_{r}}d_{\boldsymbol{\lambda},\boldsymbol{\nu}}u_{\boldsymbol{\lambda}}$
(503)

with the initial condition $u_{(1)}=1.$ Then, we can induct on $r$ to conclude
that the $c_{\boldsymbol{\lambda}}$ and the $t_{\boldsymbol{\lambda}}$ are the
same sequence. Since $\Pi_{2}=\\{(1)\\},$ we see that
$c_{\boldsymbol{\lambda}}=t_{\boldsymbol{\lambda}}$ for every
$\boldsymbol{\lambda}\in\Pi_{2}.$ Suppose $r\geq 2$ is such that
$c_{\boldsymbol{\lambda}}=t_{\boldsymbol{\lambda}}$ for every
$\boldsymbol{\lambda}\in\Pi_{r}.$ Hence, for every
$\boldsymbol{\nu}\in\Pi_{r+1},$ we have that

$\sum_{\boldsymbol{\lambda}\in\Pi_{r}}d_{\boldsymbol{\lambda},\boldsymbol{\nu}}c_{\boldsymbol{\lambda}}=\sum_{\boldsymbol{\lambda}\in\Pi_{r}}d_{\boldsymbol{\lambda},\boldsymbol{\nu}}t_{\boldsymbol{\lambda}}.$
(504)

Since both sequences $c_{\boldsymbol{\lambda}}$ and $t_{\boldsymbol{\lambda}}$
satisfy the recurrence (503), we obtain from (504) that
$c_{\boldsymbol{\nu}}=t_{\boldsymbol{\nu}}$ for every
$\boldsymbol{\nu}\in\Pi_{r+1}.$ Therefore, we obtain by induction that
$c_{\boldsymbol{\lambda}}=t_{\boldsymbol{\lambda}}$ for every
$\boldsymbol{\lambda}\in\Pi_{r}$ for every $r,$ as desired.

###  F.2 Proof of Theorem 29

Fix $p\in\mathscr{D},$ suppose $X\sim p,$ and write $Y=X+N$ and
$p_{Y}=e^{-Q}.$ First, we note that $Q^{\prime}(y)$ is equal to
$\mathbb{E}[N\mid Y=y].$

######  Lemma 52.

Fix a random variable $X$ and let $Y=X+N$ where $N\sim\mathcal{N}(0,1)$ is
independent of $X.$ Writing $p_{Y}=e^{-Q},$ we have that
$Q^{\prime}(y)=\mathbb{E}[N\mid Y=y].$

###### Proof.

We have that $p_{Y}(y)=\mathbb{E}[e^{-(y-X)^{2}/2}]/\sqrt{2\pi}.$
Differentiating this equation, we obtain that
$p_{Y}^{\prime}(y)=\mathbb{E}[(X-y)e^{-(y-X)^{2}/2}]/\sqrt{2\pi},$ where the
exchange of differentiation and integration is warranted since $t\mapsto
te^{-t^{2}/2}$ is bounded. Now, $Q=-\log p_{Y},$ so
$Q^{\prime}=-p_{Y}^{\prime}/p_{Y},$ i.e.,

$Q^{\prime}(y)=y-\frac{\mathbb{E}[Xe^{-(y-X)^{2}/2}]}{\mathbb{E}[e^{-(y-X)^{2}/2}]}=y-\mathbb{E}\left[X\mid
Y=y\right].$ (505)

The proof is completed by substituting $X=Y-N.$ ∎

In view of Lemma 52, that $p$ is even and non-increasing over
$[0,\infty)\cap\mathrm{supp}(p)$ imply that $Q$ satisfies conditions (1)–(4)
of Definition 5. It remains to show that property (5) holds. To this end, we
show that if $\mathrm{supp}(p)\subset[-M,M]$ and $\lambda=M+2,$ then for every
$y>M+4$ we have that

$1<\frac{M^{2}+5M+8}{2(M+2)}\leq\frac{Q^{\prime}(\lambda
y)}{Q^{\prime}(y)}\leq\frac{M^{2}+7M+8}{4}.$ (506)

First, since $Q^{\prime}(y)=y-\mathbb{E}[X\mid Y=y]$ (see (505)), we have the
bounds $y-M\leq Q^{\prime}(y)\leq y+M$ for every $y\in\mathbb{R}.$ Therefore,
$y>M$ and $\lambda>1$ imply that

$\frac{\lambda y-M}{y+M}\leq\frac{Q^{\prime}(\lambda
y)}{Q^{\prime}(y)}\leq\frac{\lambda y+M}{y-M}.$ (507)

Further, since $y>M+4$ and $\lambda=M+2,$ we have

$\frac{M^{2}+5M+8}{2(M+2)}<\lambda-\frac{M(M+3)}{y+M}=\frac{\lambda y-M}{y+M}$
(508)

and

$\frac{\lambda y+M}{y-M}=\lambda+\frac{M(M+3)}{y-M}\leq\frac{M^{2}+7M+8}{4}.$
(509)

The fact that $1<\frac{M^{2}+5M+8}{2(M+2)}$ follows since the discriminant of
$M^{2}+3M+4$ is $-7<0.$ Therefore, $p_{Y}$ is a Freud weight.

###  F.3 Proof of Inequality (245)

By Lemma 52,

$Q^{\prime}(y)=\mathbb{E}[N\mid Y=y]=y-\mathbb{E}[X\mid Y=y].$ (510)

Therefore $X\leq M$ implies that, for any constant $z\geq 0,$ we have

$\displaystyle\int_{0}^{1}\frac{ztQ^{\prime}(zt)}{\sqrt{1-t^{2}}}\,dt$
$\displaystyle=\frac{\pi}{4}z^{2}-z\int_{0}^{1}\frac{t}{\sqrt{1-t^{2}}}\frac{\mathbb{E}\left[Xe^{-(X-zt)^{2}/2}\right]}{\mathbb{E}\left[e^{-(X-zt)^{2}/2}\right]}dt$
(511) $\displaystyle\geq\frac{\pi}{4}z^{2}-Mz.$ (512)

We have $\pi z^{2}/4-Mz>n$ for $z=(2M+\sqrt{2})\sqrt{n}.$ Since $y\mapsto
yQ^{\prime}(y)$ is strictly increasing over $(0,\infty)$ (condition (3) of
Definition 5), we conclude that $a_{n}(Q)\leq(2M+\sqrt{2})\sqrt{n}.$

##  Appendix G Proof of Proposition 33: $h_{n}$ Under Affine Transformations

Fix $n\in\mathbb{N}_{\geq 1}$ and let $N\sim\mathcal{N}(0,1)$ be independent
of $Y.$ From equation (128) in Proposition 9, for any fixed $t\geq 0$

$\displaystyle\mathrm{pmmse}_{n}(\alpha Y+\beta,t)$
$\displaystyle=\mathrm{pmmse}_{n}(\alpha Y+\beta\mid\sqrt{t}(\alpha
Y+\beta)+N)$ (513) $\displaystyle=\mathrm{pmmse}_{n}(\alpha
Y+\beta\mid\sqrt{\alpha^{2}t}Y+\beta\sqrt{t}+N)$ (514)
$\displaystyle=\mathrm{pmmse}_{n}(\alpha Y\mid\sqrt{\alpha^{2}t}Y+N).$ (515)

Also, from equation (129) in Proposition 9,

$\mathrm{pmmse}_{n}(\alpha
Y\mid\sqrt{\alpha^{2}t}Y+N)=\alpha^{2}\mathrm{pmmse}_{n}(Y\mid\sqrt{\alpha^{2}t}Y+N)=\alpha^{2}\mathrm{pmmse}_{n}(Y,\alpha^{2}t).$
(516)

Combining these two relations, we obtain

$\mathrm{pmmse}_{n}(\alpha
Y+\beta,t)=\alpha^{2}\mathrm{pmmse}_{n}(Y,\alpha^{2}t).$ (517)

Therefore, by definition of $h_{n}$ (see equation (254))

$\displaystyle h_{n}(\alpha Y+\beta)$
$\displaystyle=\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(\alpha
Y+\beta,t)-\frac{1}{2\pi e+t}\,dt$ (518)
$\displaystyle=\frac{1}{2}\int_{0}^{\infty}\alpha^{2}\mathrm{pmmse}_{n}(Y,\alpha^{2}t)-\frac{1}{2\pi
e+t}\,dt$ (519)
$\displaystyle=\frac{1}{2}\int_{0}^{\infty}\left(\mathrm{pmmse}_{n}(Y,\alpha^{2}t)-\frac{1}{2\pi
e\alpha^{2}+\alpha^{2}t}\right)\alpha^{2}dt.$ (520)

Performing the substitution $u=\alpha^{2}t,$

$h_{n}(\alpha
Y+\beta)=\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(Y,u)-\frac{1}{2\pi
e\alpha^{2}+u}\,du.$ (521)

Finally, from (251) (with $a=1/(2\pi e\alpha^{2})$ and $b=1/(2\pi e)$), we
obtain

$\frac{1}{2}\int_{0}^{\infty}\frac{1}{2\pi e\alpha^{2}+u}-\frac{1}{2\pi
e+u}\,du=\frac{1}{2}\log\frac{1}{\alpha^{2}}=-\log|\alpha|.$ (522)

Note that the integrand in the right hand side of (521) and the integrand in
the left hand side of (522) are both absolutely integrable over $(0,\infty).$
Therefore, adding (521) and (522), and utilizing the definition of $h_{n}$ in
(254) again, we obtain

$h_{n}(\alpha
Y+\beta)-\log|\alpha|=\frac{1}{2}\int_{0}^{\infty}\mathrm{pmmse}_{n}(Y,u)-\frac{1}{2\pi
e+u}\,du=h_{n}(Y),$ (523)

and the proof is complete.

##  Appendix H Proofs of Section 10

###  H.1 Proof of Lemma 38

Fix $X,$ and let $W$ be its orthogonal projection onto the closed subspace
$\mathcal{V}.$ Consider the symmetric matrix
$\bm{M}=\mathbb{E}[\bm{V}\bm{V}^{T}].$ Since
$\bm{c}^{T}\bm{M}\bm{c}=\mathbb{E}[|\bm{c}^{T}\bm{V}|^{2}]$ for each
$\bm{c}\in\mathbb{R}^{n+1},$ linear independence of the $V_{j}$ implies that
$\bm{M}$ is positive-definite. Let $\bm{M}^{1/2}$ be the unique lower-
triangular matrix with positive diagonal such that
$\bm{M}^{1/2}\left(\bm{M}^{1/2}\right)^{T}=\bm{M},$ and denote its inverse by
$\bm{M}^{-1/2}.$ Let $(U_{0},\cdots,U_{n})^{T}=\bm{U}=\bm{M}^{-1/2}\bm{V}.$
Then, $\\{U_{j}\\}_{j\in[n]}\subset\mathcal{V}$ and
$\mathbb{E}[\bm{U}\bm{U}^{T}]=\bm{I}_{n+1}.$ Therefore,
$\\{U_{j}\\}_{j\in[n]}$ is an orthonormal basis of $\mathcal{V}$; indeed, it
is the output of Gram-Schmidt orthonormalization on $\\{V_{j}\\}_{j\in[n]}.$
Then, because $W$ is the orthogonal projection of $X$ onto $\mathcal{V},$ we
can express $W$ as

$W=\sum_{j\in[n]}\mathbb{E}[XU_{j}]\leavevmode\nobreak\
U_{j}=\mathbb{E}[X\bm{U}^{T}]\bm{U}.$ (524)

Plugging the defining formulas of $\bm{U}$ and $\bm{M}$ into (524),

$W=\mathbb{E}\left[X\bm{V}\right]^{T}\mathbb{E}\left[\bm{V}\bm{V}^{T}\right]^{-1}\bm{V}.$
(525)

Finally, being the orthogonal projection of $X$ onto $\mathcal{V},$ $W$ is the
unique closest element in $\mathcal{V}$ to $X$; hence, equation (284) follows.

###  H.2 Proof of Corollary 40

Fix $q\geq 1.$ For each $j,$ Carleman’s condition on $Y_{j}$ yields that the
set of polynomials in $Y_{j},$ i.e.,
$\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n}(Y_{j}),$ is dense in
$L^{2q}(\sigma(Y_{j})).$ Therefore, by Theorem 39,

$\overline{\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n,m}(\bm{Y})}=L^{q}(\sigma(\bm{Y})).$
(526)

Now, fix $(f_{1},\cdots,f_{m})^{T}=\bm{f}\in
L^{q}(\mathbb{R}^{m},\sigma(\bm{Y})).$ For each $j,$ $f_{j}\in
L^{q}(\sigma(\bm{Y})).$ Hence, there is a sequence
$\\{g_{j,n}\\}_{n\in\mathbb{N}}\subset\mathscr{P}_{n,m}(\bm{Y})$ such that
$f_{j}=\lim_{n\to\infty}g_{j,n}$ in $L^{q}(\sigma(\bm{Y}))$-norm. Set
$\bm{g}_{n}=(g_{1,n},\cdots,g_{m,n})^{T},$ and note that
$\bm{g}_{n}\in\mathscr{P}_{n,m}^{m}(\bm{Y}).$ By definition of the norm in
$L^{q}(\mathbb{R}^{m},\sigma(\bm{Y})),$ we deduce

$\lim_{n\to\infty}\|\bm{f}-\bm{g}_{n}\|_{q}^{q}=\lim_{n\to\infty}\sum_{j=1}^{m}\|f_{j}-g_{j,n}\|_{q}^{q}=0,$
(527)

and the desired denseness result follows.

###  H.3 Proof of Theorem 41

Since the $Y_{j}$ do not satisfy a polynomial relation, the matrix
$\bm{M}_{\bm{Y},n}$ is invertible for each $n\in\mathbb{N}.$ Further, the
entries of $\bm{Y}^{(n,m)}$ are linearly independent for each $n.$ Then, by
Lemma 38, equation (301) follows, i.e., $E_{n}[\bm{X}\mid\bm{Y}]$ is the
$\ell$-RV whose $k$-th entry is
$\mathbb{E}\left[X_{k}\bm{Y}^{(n,m)}\right]^{T}\bm{M}_{\bm{Y},n}^{-1}\bm{Y}^{(n,m)}.$
By Corollary 40, since each $Y_{j}$ satisfies Carleman’s condition, the set of
vectors of polynomials $\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n,m}^{m}(\bm{Y})$
is dense in $L^{2}(\mathbb{R}^{m},\sigma(\bm{Y})).$ In particular,
$\bigcup_{n\in\mathbb{N}}\mathscr{P}_{n,m}(\bm{Y})$ is dense in
$L^{2}(\sigma(\bm{Y})).$ By Theorem 37, we have the $L^{2}(\sigma(\bm{Y}))$
limits

$\mathbb{E}[X_{k}\mid\bm{Y}]=\lim_{n\to\infty}\mathbb{E}\left[X_{k}\bm{Y}^{(n,m)}\right]^{T}\bm{M}_{\bm{Y},n}^{-1}\bm{Y}^{(n,m)}$
(528)

for each $k\in\\{1,\cdots,\ell\\}.$ We conclude that
$E_{n}[\bm{X}\mid\bm{Y}]\to\mathbb{E}[\bm{X}\mid\bm{Y}]$ in
$L^{2}(\mathbb{R}^{\ell},\sigma(\bm{Y})),$ as desired.

###  H.4 Proof of Proposition 42

Set $\bm{Y}=(Y_{1},Y_{2})^{T}.$ Equation (306) is straightforward: since
$E_{n}[X\mid Y_{1}]\in\mathscr{P}_{n}(Y_{1})\subset\mathscr{P}_{n,2}(\bm{Y}),$
the projection of $E_{n}[X\mid Y_{1}]$ onto $\mathscr{P}_{n,2}(\bm{Y})$ is
$E_{n}[X\mid Y_{1}]$ again. Equation (307) also follows by an orthogonal
projection argument. There is a unique representation
$X=p_{1,2}+p_{1,2}^{\perp}$ for
$(p_{1,2},p_{1,2}^{\perp})\in\mathscr{P}_{n,2}(\bm{Y})\times\mathscr{P}_{n,2}(\bm{Y})^{\perp}.$
There is also a unique representation $p_{1,2}=q_{2}+q_{2}^{\perp}$ for
$(q_{2},q_{2}^{\perp})\in\mathscr{P}_{n}(Y_{2})\times\mathscr{P}_{n}(Y_{2})^{\perp}.$
The projection of $X$ onto $\mathscr{P}_{n,2}(\bm{Y})$ is $p_{1,2},$ whose
projection onto $\mathscr{P}_{n}(Y_{2})$ is $q_{2},$ i.e.,

$E_{n}\left[E_{n}[X\mid Y_{1},Y_{2}]\mid Y_{2}\right]=q_{2}.$ (529)

Furthermore, we have the representation
$X=q_{2}+(q_{2}^{\perp}+p_{1,2}^{\perp}),$ for which
$(q_{2},q_{2}^{\perp}+p_{1,2}^{\perp})\in\mathscr{P}_{n}(Y_{2})\times\mathscr{P}_{n}(Y_{2})^{\perp}.$
Hence, the projection of $X$ onto $\mathscr{P}_{n}(Y_{2})$ is $q_{2}$ too,
i.e.,

$E_{n}[X\mid Y_{2}]=q_{2}.$ (530)

From (529) and (530) we get (307). Equation (307) can also be deduced from the
formula of $W:=\mathbb{E}[X\mid\bm{Y}].$ Denote
$\bm{Y}_{2}^{(n)}=(1,Y_{2},\cdots,Y_{2}^{n})^{T}.$ We have that

$W=\mathbb{E}\left[X\bm{Y}^{(n,2)}\right]^{T}\bm{M}_{\bm{Y},n}^{-1}\bm{Y}^{(n,2)}$
(531)

and

$E_{n}[W\mid
Y_{2}]=\mathbb{E}\left[W\bm{Y}_{2}^{(n)}\right]^{T}\bm{M}_{Y_{2},n}^{-1}\bm{Y}_{2}^{(n)}.$
(532)

For $k\in[n],$ let $\delta(k)\in\left[\binom{n+2}{2}-1\right]$ be the index of
the entry in $\bm{Y}^{(n,2)}$ that equals $Y_{2}^{k}.$ Then,

$\mathbb{E}\left[Y_{2}^{k}\bm{Y}^{(n,2)}\right]=\bm{M}_{\bm{Y},n}\bm{e}_{\delta(k)},$
(533)

where $\bm{e}_{0},\cdots,\bm{e}_{\binom{n+2}{2}-1}$ are the standard basis
vectors of $\mathbb{R}^{\binom{n+2}{2}}.$ Therefore, plugging (531) into
(532), we obtain

$E_{n}[W\mid
Y_{2}]=\mathbb{E}\left[X\bm{Y}_{2}^{(n)}\right]^{T}\bm{M}_{Y_{2},n}^{-1}\bm{Y}_{2}^{(n)},$
(534)

which is just $E_{n}[X\mid Y_{2}],$ as desired.

##  Appendix I Multidimensional MMSE Dimension (Theorem 43)

In this proof, we will denote the Euclidean norm in $\mathbb{R}^{m}$ by the
unsubscripted $\|\mathrel{\;\cdot\;}\|,$ so if
$\bm{N}=(N_{1},\cdots,N_{m})^{T}$ then
$\|\bm{N}\|=\sqrt{N_{1}^{2}+\cdots+N_{m}^{m}}$ is a RV.

Our proof is a straightforward extension of the proof for the one-dimensional
case given in [32]. In particular, we use the concept of approximations to the
identity.

######  Definition 11.

The set of functions $\\{K_{\delta}:\mathbb{R}^{m}\to\mathbb{R}\\}_{\delta>0}$
is called _an approximation to the identity_ if

  1. (i)

$\int_{\mathbb{R}^{m}}K_{\delta}(\bm{y})\,d\bm{y}=A$ for each $\delta>0,$

  2. (ii)

$|K_{\delta}(\bm{y})|\leq B\delta^{-m}$ for each $\delta>0,$ and
$\bm{y}\in\mathbb{R}^{m},$

  3. (iii)