#  $L^{1}$ Estimation: On the Optimality of Linear Estimators

Leighton P. Barnes, Alex Dytso, Jingbo Liu, and H. Vincent Poor  Leighton P.
Barnes is with the Center for Communications Research, Princeton, NJ 08540,
USA (e-mail: l.barnes@idaccr.org). Alex Dytso is with Qualcomm Flarion
Technology, Inc., Bridgewater, NJ 08807, USA (e-mail: odytso2@gmail.com).
Jingbo Liu is with the Department of Statistics and the Department of
Electrical and Computer Engineering, University of Illinois, Urbana-Champaign,
IL 61820, USA (e-mail: jingbol@illinois.edu). H. Vincent Poor is with the
Department of Electrical and Computer Engineering, Princeton University,
Princeton, NJ 08544, USA (e-mail: poor@princeton.edu). Part of this work was
presented at the 2023 IEEE International Symposium on Information Theory
(ISIT) [1].

###### Abstract

Consider the problem of estimating a random variable $X$ from noisy
observations $Y=X+Z$, where $Z$ is standard normal, under the $L^{1}$ fidelity
criterion. It is well known that the optimal Bayesian estimator in this
setting is the conditional median. This work shows that the only prior
distribution on $X$ that induces linearity in the conditional median is
Gaussian.

Along the way, several other results are presented. In particular, it is
demonstrated that if the conditional distribution $P_{X|Y=y}$ is symmetric for
all $y$, then $X$ must follow a Gaussian distribution. Additionally, we
consider other $L^{p}$ losses and observe the following phenomenon: for
$p\in[1,2]$, Gaussian is the only prior distribution that induces a linear
optimal Bayesian estimator, and for $p\in(2,\infty)$, infinitely many prior
distributions on $X$ can induce linearity. Finally, extensions are provided to
encompass noise models leading to conditional distributions from certain
exponential families.

##  1 Introduction

The theory of linear estimation plays a central role in Bayesian estimation.
Linear estimators are easy to deploy and are thus attractive from a practical
point of view. From a theoretical point of view, linear estimators often serve
as useful benchmarks for understanding the performance of other more complex
estimators. Furthermore, they appear as key objects in the study of Bayesian
topics such as exponential families and conjugate priors. Thus characterizing
the optimality of linear estimators is important from both practical and
theoretical points of view.

In the Bayesian setting, whether a given estimator is optimal or not depends
highly on the chosen fidelity criterion. To make things concrete, suppose we
seek to estimate a scalar random variable $X\in\mathbb{R}$ from a noisy
observation $Y\in\mathbb{R}$. For the time being, we will focus on the simple
but already rich noise model

$Y=X+Z,$ (1)

where $Z$ is _standard normal_ independent of $X$. Later on, we will also
consider more general noise models. The fidelity criterion determines the
nature of the optimal estimator. In particular, for $L^{2}$ and $L^{1}$ error
measures, it is well-known that the optimal estimators are given by the
_conditional mean_ and the _conditional median_ , respectively, that is

$\displaystyle\mathbb{E}[X|Y]$
$\displaystyle=\arg\min_{f:\,\mathbb{E}[|f(Y)|^{2}]<\infty}\mathbb{E}\left[\left|X-f(Y)\right|^{2}\right],$
(2) $\displaystyle\mathsf{m}(X|Y)$
$\displaystyle=\arg\min_{f:\,\mathbb{E}[|f(Y)|]<\infty}\mathbb{E}\left[\left|X-f(Y)\right|\right].$
(3)

The conditional mean and median of $X$ given $Y=y$ are defined as

$\displaystyle\mathbb{E}[X|Y=y]$ $\displaystyle=\int
x\,F_{X|Y=y}(\mathrm{d}x),\,y\in\mathbb{R},$ (4)
$\displaystyle\mathsf{m}(X|Y=y)$
$\displaystyle=F^{-1}_{X|Y=y}\left(\frac{1}{2}\right),\,y\in\mathbb{R},$ (5)

where $F_{X|Y=y}$ is the conditional cumulative distribution function (cdf)
and $F^{-1}_{X|Y=y}$ is the conditional quantile function111 Recall that for a
random variable $U$ the _quantile function_ or the _inverse cumulative
distribution function_ (cdf) is defined as
$F_{U}^{-1}(p)=\inf\\{x\in\mathbb{R}:p\leq F_{U}(x)\\},\,p\in(0,1).$ of $X$
given $Y=y$. Therefore, under the $L^{2}$ criterion, the optimality of linear
estimators reduces to characterizing whether or not there exists a constant
$a$ and a prior distribution for $X$ such that for (almost) all
$y\in\mathbb{R}$,

$\mathbb{E}[X|Y=y]=ay.$ (6)

Similarly, for the $L^{1}$ criterion, the optimality of linear estimators
reduces to characterizing whether there exists a constant $a$ and a prior
distribution for $X$ such that for (almost) all $y\in\mathbb{R}$,

$\mathsf{m}(X|Y=y)=ay.$ (7)

For the case of $L^{2}$ error, the problem of identifying the set of
distribution on $X$ that would induce a linear conditional mean has been well
understood for several decades. In fact, for the Gaussian noise setting, in
Appendix B we provide four different ways of showing that the only prior that
induces linearity is the Gaussian with zero mean and variance $\frac{a}{1-a}$,
i.e., $X\sim\mathcal{N}(0,\frac{a}{1-a})$, and that the only admissible $a$
values lie in the interval $[0,1]$. The problem is also well understood beyond
the Gaussian noise case. For example, when $P_{Y|X}$ belongs to an
_exponential family_ , it is known that the conditional mean is linear if and
only if $X$ is distributed according to a _conjugate prior_ [2, 3] in which
case $a=\frac{{\rm Cov}(X,Y)}{{\rm Var}(Y)}$. Conjugate priors are used to
model a variety of phenomena in statistical and machine-learning applications
[4].

For additive noise channels, i.e., $Y=X+N$, where $N$ is not necessarily
Gaussian, the authors of [5] characterized necessary and sufficient conditions
for the linearity of the optimal Bayesian estimators for the case of $L^{p}$
Bayesian risks (i.e., $\mathbb{E}[|X-f(Y)|^{p}]$) with $p$ taking only _even_
values. More specifically, the authors of [5] found the characteristic
function of $X$ as a function of the characteristic function of $N$. These
results, however, do not generalize to our case of $p=1$.

Finally, for the $L^{2}$ case, in addition to uniqueness results, we also have
_stability_ results. In particular, for the Gaussian and Poisson noise models,
if the conditional expectation is close to a linear function in the $L^{2}$
distance, then the distribution of $X$ needs to be close to a matching prior
(Gaussian for Gaussian noise and gamma for Poisson noise) in the _Lévy
distance_ [6, 7].

Interestingly, for the $L^{1}$ case, there appears to be no full answer in the
existing literature. While $X\sim\mathcal{N}(0,\frac{a}{1-a})$ clearly induces
a linear conditional median, to the best of our knowledge, there are no
previous results that guarantee that this is the only prior that induces
linearity. The aim of this work is to close this gap and show that the
Gaussian distribution is the only one inducing linearity of the conditional
median. Moreover, we will provide several equivalent perspectives on this
problem related to integral operator theory and convolution equations. Near
the end, we will also examine other $L^{p}$ losses and will show that for
$p\in[1,2]$, Gaussian is the only distribution that induces linearity of the
optimal Bayesian estimator, and for $p\in(2,\infty)$, multiple prior
distributions on $X$ can induce linearity. The point $p=2$ is an interesting
phase transition point which appears to not have been noted in prior
literature. In handling $L^{p}$ losses for all $p\in[1,\infty)$, instead of
just even values, we work in a more general setting than [5]. In that work,
they show that for even $p$, there are no priors _with the same variance as
the noise_ , other than the Gaussian, that induce linearity of the optimal
Bayesian estimator. Since we do not make the equal variance assumption, our
results are not contradictory and give a more complete understanding of the
scenario.

The conditional median plays an important role in our analysis, and for a
detailed study of the properties of the conditional median in the most
abstract $\sigma$-algebra setting, the interested reader is referred to [8,
9]. For recent applications of the conditional median, the interested reader
is referred to [10] and references therein.

###  1.1 Outline and Contributions

The paper outline and contributions are as follows. In Section 2, we start by
making some preliminary observations about characterizing which prior
distributions lead to linear conditional medians. In Section 2.3, Proposition
2, we show that a Gaussian prior distribution does indeed yield a linear
conditional median. Section 2.4, Proposition 5 provides an equivalent
condition to linearity in terms of a convolution; and Section 2.5 discusses
finding the nullspace of the corresponding linear operator. In Section 3, we
present our main results and show that the Gaussian distribution is the only
prior distribution that induces a linear conditional median. Finally, in
Section 4 we conclude by discussing the Poisson noise case, exponential
families, other $L^{p}$ losses, and possible multidimensional extensions.

##  2 The Problem Setup and Some Preliminary Observations

In this section, we begin by providing preliminary observations about the
problem, derive a necessary and sufficient condition for linearity of the
conditional median to hold, and try to point out the reasons why solving the
problem is a challenging task. Along the way, we also derive some results that
might be of independent interest.

###  2.1 The Problem Setup

Despite considerable research into linear estimators, to the best of our
knowledge, the question of identifying the set of prior distributions on $X$
that ensure that $\mathsf{m}(X|Y)$ is a linear function of $Y$ has not been
characterized. In this work, we seek to close this gap. Formally, we seek to
answer the following question: _For a given $a\in\mathbb{R}$, what is the set
of distributions on the input $X$ that ensure that for all $y\in\mathbb{R}$_

$\mathsf{m}(X|Y=y)=ay?$ (8)

Unless otherwise noted, we will focus on the Gaussian in (1). However,
interestingly, we will also be able to bootstrap Gaussian results to a subset
of the exponential family.

It is well known that for the conditional expectation, under the model in (1),

$\mathbb{E}[X|Y=y]=ay,\,\forall y\in\mathbb{R},$ (9)

if and only if $a\in[0,1)$ and $X\sim\mathcal{N}(0,\frac{a}{1-a})$. The
authors of this paper are aware of five district ways of showing this fact;
four of these methods, some of which are new, are provided in Appendix B.
However, none of these techniques appear to be generalizable to the
conditional median setting. Indeed, this work develops a new technique to
establish the linearity of the conditional median.

###  2.2 On the Admissible Values of $a$

We next show that the admissible values of $a$ that satisfy (8) must be in
$[0,1)$. This is done for all $L^{p}$ losses with $p\geq 1$.

######  Theorem 1.

Let $p\geq 1$. Then,

$\min_{a\in\mathbb{R}}\mathbb{E}[|X-aY|^{p}]=\min_{a\in[0,1)}\mathbb{E}[|X-aY|^{p}].$
(10)

In other words, the _admissible_ values of $a$ lie in $[0,1)$.

###### Proof.

We will assume, without loss of generality, that $\mathbb{E}[X]=0$. This can
be done by constructing a version of the measure $P_{X}$ that is symmetric
about the origin by averaging it with its time-reverse. This measure will have
mean-zero, and will give the same values for $\mathbb{E}[|X-aY|^{p}]$.

Let

$f(a)=\mathbb{E}[|X-aY|^{p}],$ (11)

which is differentiable for $a>0$ in view of the fact that $X-aY=(a-1)X+aZ$ is
continuous random variable for $a>0$. Then, by letting

$g(t)=p\,\mathsf{sign}(t)|t|^{p-1},\,p\geq 1,\,t\in\mathbb{R},$ (12)

we have

$\displaystyle f^{\prime}(a)$ $\displaystyle=-\mathbb{E}[g(X-aY)Y]$ (13)
$\displaystyle=\mathbb{E}[g(aY-X)Y]$ (14)
$\displaystyle=\mathbb{E}\left[g\left((a-1)X+aZ\right)(X+Z)\right].$ (15)

We will show that the function $f(a)$ is _non-decreasing_ for $a\geq 1$ and
_non-increasing_ for $a<0$. Thus, we will reduce our search space to
$a\in[0,1]$. To aid our proof, recall the FKG inequality (see for example
[11]): for two non-decreasing functions $f$ and $g$, we have that

$\mathbb{E}[f(X)g(X)]\geq\mathbb{E}[f(X)]\mathbb{E}[g(X)],$ (16)

or equivalently, if $f$ is non-decreasing and $g$ is non-increasing, then

$\mathbb{E}[f(X)g(X)]\leq\mathbb{E}[f(X)]\mathbb{E}[g(X)].$ (17)

Now, assume that $a\geq 1$; then

$\displaystyle f^{\prime}(a)$
$\displaystyle=\mathbb{E}\left[g\left((a-1)X+aZ\right)(X+Z)\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)(X+Z)|Z\right]\right]$
(18)
$\displaystyle\geq\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)|Z\right]\mathbb{E}\left[X+Z|Z\right]\right]$
(19)
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)|Z\right]Z\right]$
(20) $\displaystyle=\mathbb{E}\left[g\left((a-1)X+aZ\right)Z\right]$ (21)
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)Z|X\right]\right]$
(22)
$\displaystyle\geq\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)|X\right]\mathbb{E}\left[Z|X\right]\right]$
(23) $\displaystyle=0,$ (24)

where (19) we have used that given $Z$ the functions $X\mapsto g((a-1)X+aZ)$
and $h(X)=X+Z$ are non-decreasing and applying the FKG inequality; (20)
follows by using that $X$ and $Z$ are independent and the assumption that
$\mathbb{E}[X]=0$ which implies that
$\mathbb{E}\left[X+Z|Z\right]=Z+\mathbb{E}[X]=Z$; (23) follows by using the
fact that given $X$ the functions $Z\mapsto g\left((a-1)X+aZ\right)$ and
$h(Z)=Z$ are non-decreasing and applying the FKG inequality.

Now, assume that $a\leq 0$; then

$\displaystyle f^{\prime}(a)$
$\displaystyle=\mathbb{E}\left[g\left((a-1)X+aZ\right)(X+Z)\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)(X+Z)|Z\right]\right]$
(25)
$\displaystyle\leq\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)|Z\right]\mathbb{E}\left[X+Z|Z\right]\right]$
(26)
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)|Z\right]Z\right]$
(27) $\displaystyle=\mathbb{E}\left[g\left((a-1)X+aZ\right)Z\right]$ (28)
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)Z|X\right]\right]$
(29)
$\displaystyle\leq\mathbb{E}\left[\mathbb{E}\left[g\left((a-1)X+aZ\right)|X\right]\mathbb{E}\left[Z|X\right]\right]$
(30) $\displaystyle=0,$ (31)

where in (26) we have used that, given $Z$, $X\mapsto g\left((a-1)X+aZ\right)$
is non-increasing and $h(X)=X+Z$ are non-decreasing; and (30) we have used
that, given $X$, $Z\mapsto g\left((a-1)X+aZ\right)$ is non-increasing and
$h(Z)=Z$ are non-decreasing and applying the FKG inequality.

Thus, we can assume that $a\in[0,1]$. To conclude the proof note that by
independence, we have that

$f^{\prime}(1)=\mathbb{E}\left[g\left(Z\right)(X+Z)\right]=\mathbb{E}[|Z|^{p}]>0,$
(32)

which implies that we can eliminate the value of $a=1$. ∎

###  2.3 Gaussian $X$ is a Solution

We begin by showing that the set of distributions that satisfies (8) is not
empty.

######  Proposition 2.

If $0\leq a<1$, a Gaussian random variable
$X\sim\mathcal{N}(0,\sigma_{X}^{2})$ satisfies (8) if
$\sigma_{X}^{2}=\frac{a}{1-a}$.

###### Proof.

Suppose that $X\sim\mathcal{N}(0,\sigma_{X}^{2})$; then the conditional
distribution
$X|Y=y\sim\mathcal{N}(\frac{\sigma^{2}_{X}}{1+\sigma_{X}^{2}}y,\frac{\sigma^{2}_{X}}{1+\sigma_{X}^{2}})$.
Since Gaussian distributions are symmetric, the conditional median and
conditional mean coincide, and we have that

$\mathsf{m}(X|Y=y)=\mathbb{E}[X|Y=y]=\frac{\sigma^{2}_{X}}{1+\sigma_{X}^{2}}y.$
(33)

Solving for $\sigma_{X}^{2}$ concludes the proof. ∎

In Proposition 2, for the case of $a=0$, and for the rest of the paper, we do
not distinguish between point measures and Gaussian measures with zero
variance and treat them as the same objects.

The proof of Proposition 2 relied on the fact that if $X$ is Gaussian, then
$X|Y=y$ is a symmetric distribution222The random variable $U$ is said to have
symmetric distribution if there exists a constant $c$ such that
$U+c\stackrel{{\scriptstyle d}}{{=}}-(U+c)$ where $\stackrel{{\scriptstyle
d}}{{=}}$ denotes equality in distribution.  for all $y$ and, hence, the mean
and the median coincide. The next result, which might be of independent
interest, shows that this construction works only in the Gaussian case.

######  Theorem 3.

If $X$ is Gaussian, then $X|Y=y$ is symmetric for all $y$. Conversely, if
$X|Y=y$ is symmetric for all $y\in S$ where $S$ is a subset of $\mathbb{R}$
that has an accumulation, then $X$ is Gaussian.

###### Proof.

See Appendix C. ∎

###  2.4 An Equivalent Condition via Convolution

In this subsection, we derive a condition that is equivalent to (8). Our
starting place is the following condition akin to the orthogonality principle
[12, 5]: a function $f$ minimizes (3) if and only if

$\mathbb{E}\left[\mathsf{sign}\left(X-f(Y)\right)g(Y)\right]=0,$ (34)

for all $g$ such that $\mathbb{E}[|g(Y)|]<\infty$.

######  Proposition 4.

$X$ satisfies (8) if and only if for a.e. $y\in\mathbb{R}$

$\mathbb{E}\left[\mathsf{sign}\left(X-ay\right)\phi(y-X)\right]=0,$ (35)

where $\phi$ denotes the probability density function (pdf) of a standard
Gaussian random variable.

###### Proof.

We seek to show that for $f(Y)=aY$, the condition in (34) is equivalent to
(35). Note that (35) can be equivalently re-written as: for all $g$ such that
$\mathbb{E}[|g(Y)|]<\infty$

$\displaystyle 0$
$\displaystyle=\mathbb{E}\left[\mathsf{sign}\left(X-aY\right)g(Y)\right]$ (36)
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\mathsf{sign}\left(X-aY\right)|Y\right]g(Y)\right]$
(37) $\displaystyle=\mathbb{E}\left[h(Y)g(Y)\right],$ (38)

where we have defined
$h(y)=\mathbb{E}\left[\mathsf{sign}\left(X-aY\right)|Y=y\right]$. The fact
that (38) is equivalent to

$0=h(y)\text{ a.e. }y\in\mathbb{R},$ (39)

is a standard fact (see, for example, [13, Lem. 10.1.1]). This concludes the
proof. ∎

We now show that (8) can be restated as a convolution problem.

######  Proposition 5.

$X\sim P_{X}$ satisfies (8) if and only if for all $y\in\mathbb{R}$

$0=\int_{-\infty}^{\infty}\mathsf{sign}(x-y)\phi(y-x)\,\mu(\mathrm{d}x)=\int_{-\infty}^{\infty}g^{\prime}(x-y)\,\mu(\mathrm{d}x)$
(40)

where we let
$\mu(\mathrm{d}x)=\exp\left((1-a)\frac{x^{2}}{2}\right)P_{X}(\sqrt{a}\,\mathrm{d}x)$,
$g(x)=\max(\Phi(x),1-\Phi(x))$, and where $\Phi$ is the cdf of a standard
Gaussian random variable.

###### Proof.

Observe the following sequence of implications. Starting with (35)

$\displaystyle
0=\int\mathsf{sign}\left(x-ay\right)\phi(y-x)\,P_{X}(\mathrm{d}x)$ (41)
$\displaystyle\Leftrightarrow
0=\int\mathsf{sign}\left(\frac{x}{\sqrt{a}}-\sqrt{a}y\right)\phi(y-x)\,P_{X}(\mathrm{d}x)$
(42) $\displaystyle\Leftrightarrow
0=\int\mathsf{sign}\left(x-\sqrt{a}y\right)\phi(y-\sqrt{a}x)\,P_{X}(\sqrt{a}\mathrm{d}x)$
(43) $\displaystyle\Leftrightarrow
0=\int\mathsf{sign}\left(x-y\right)\phi\left(\frac{y}{\sqrt{a}}-\sqrt{a}x\right)\,P_{X}(\sqrt{a}\mathrm{d}x)$
(44) $\displaystyle\Leftrightarrow
0=\int\mathsf{sign}\left(x-y\right)\exp\left(xy-\frac{x^{2}}{2}\right)\exp\left((1-a)\frac{x^{2}}{2}\right)\,P_{X}(\sqrt{a}\mathrm{d}x)$
(45) $\displaystyle\Leftrightarrow
0=\int\mathsf{sign}(x-y)\phi(y-x)\,\mu(\mathrm{d}x).$ (46)

To show the second representation let

$g(x)=\max(\Phi(x),1-\Phi(x)),$ (47)

and note that

$g^{\prime}(x)=\mathsf{sign}(x)\phi(x).$ (48)

This concludes the proof. ∎

At this point, it may appear that we can simply adopt the Fourier approach to
solve the convolution problem. However, caution must be exercised regarding
the validity of such an approach. It needs to be ensured that $\mathrm{d}\mu$
does not increase too rapidly at infinity before properly applying Fourier
techniques.

To conclude this section, we will present the Fourier transform of
$g^{\prime}$, which will be useful in our main proof.

######  Lemma 6.

Let $g^{\prime\wedge}$ denote the Fourier transform333We use the following
convention for the Fourier transform:
$\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(x)e^{-j\omega x}\mathrm{d}x$.
of $g^{\prime}$. We have that

$g^{\prime\wedge}(\omega)=\frac{2j}{\sqrt{\pi}}D\left(\frac{\omega}{\sqrt{2}}\right)$
(49)

where $j=\sqrt{-1}$ and $D(\omega)$ is the _Dawson function_ define as

$D(\omega)=\mathrm{e}^{-\omega^{2}}\int_{0}^{\omega}\mathrm{e}^{t^{2}}\mathrm{d}t.$
(50)

###### Proof.

This is a standard result that can, for example, be found in [14]. ∎

###  2.5 Operator Theory Perspective and Why the Positivity Assumption Is
Important

In this section, we take an operator theory perspective. Consider the
following integral operator on the set of $L^{1}$ functions:

$T_{a}[f](y)=\int_{-\infty}^{\infty}K_{a}(x,y)f(x)\mathrm{d}x$ (51)

where the _kernel_ $K_{a}(x,y)$ is given by

$K_{a}(x,y)=\mathsf{sign}(x-ay)\phi(y-x).$ (52)

If we restrict our attention only to random variables $X$ having a pdf,
finding the set of solutions to (35) is equivalent to characterizing the null
space of $T_{a}[f]$ over the space $L_{+}^{1}=\\{f:f\geq 0,\int f<\infty\\}$
(i.e., non-negative $L_{1}$ functions); that is

$\mathcal{N}(T_{a})=\left\\{f\in L_{+}^{1}:T_{a}[f]=0\right\\}.$ (53)

In this work, we show that

$\mathcal{N}(T_{a})=\\{c\phi_{\frac{a}{1-a}}:c\geq 0\\},$ (54)

where $\phi_{\frac{a}{1-a}}$ is Gaussian density with variance
$\frac{a}{1-a}$. Although we are only interested in $L_{+}^{1}$ functions (for
$f$ to be a pdf), the operator $T_{a}$ can also be thought of as a bounded
linear operator from $L^{p}(\mathbb{R})$ to itself for any $1\leq
p\leq\infty$.

One sensible approach to showing that the Gaussian function
$\phi_{\frac{a}{1-a}}$ is the only non-trivial solution is to relax the non-
negativity constraint on $f$ and consider a null-space over
$L^{1}(\mathbb{R})$, that is

$\mathcal{N}_{L^{1}}(T_{a})=\left\\{f\in
L^{1}(\mathbb{R}):T_{a}[f]=0\right\\}.$ (55)

Somewhat surprisingly, we show that this $\mathcal{N}_{L^{1}}(T_{a})$ is
infinite-dimensional.

To aid this discussion, we require to understand how the _Gabor wavelet_ [15]
is transformed by the operator $T_{a}$. Recall that the Gabor wavelet is
defined as

$f_{\mu,\sigma^{2},\omega}(x)=\exp\left(-\frac{(x-\mu)^{2}}{2\sigma^{2}}\right)\mathrm{e}^{jxw},\,x,\
\in\mathbb{R}.$ (56)

######  Theorem 7.

Assume that $-1<\sigma^{2}<\infty$. Then,

$T_{a}[f_{\mu,\sigma^{2},\omega}](y)=2\phi(y)\exp\left(-\frac{\mu^{2}}{2\sigma^{2}}\right)\sqrt{\frac{\pi/2}{b}}\exp\left(\frac{(y+\frac{\mu}{\sigma^{2}}+jw)^{2}}{2b}\right)\mathrm{erf}\left(\frac{(1-ba)y+\frac{\mu}{\sigma^{2}}+jw}{\sqrt{2b}}\right),$
(57)

where $b=1+\frac{1}{\sigma^{2}}$. Moreover, if $\sigma^{2}=\frac{a}{1-a}$,
then

$T_{a}[f_{\mu,\sigma^{2},\omega}](y)=c(b,\omega,\mu)\mathrm{e}^{-\left(1-a\right)\frac{(y-\mu)^{2}}{2}}\mathrm{e}^{jway},$
(58)

where
$c(b,\omega,\mu)=\sqrt{a}\exp(-\frac{a\omega^{2}}{2})\mathrm{erf}\left(\frac{\frac{\mu}{\sigma^{2}}+jw}{\sqrt{2\frac{1}{a}}}\right)\exp\left(\frac{jw\frac{\mu}{\sigma^{2}}}{\frac{1}{a}}\right)$.

###### Proof.

See Appendix A. ∎

At this point, we recall that $z\mapsto\mathrm{erf}(z)$ has infinitely many
zeros [16]. For example, the first three zeros are given by

$\displaystyle z_{1}$ $\displaystyle=1.4506161632+j1.8809430002,$ (59)
$\displaystyle z_{2}$ $\displaystyle=2.2446592738+j2.6165751407,$ (60)
$\displaystyle z_{3}$ $\displaystyle=2.8397410469+j3.1756280996.$ (61)

We also note that due to conjugate symmetry, if $z_{n}$ is a zero, so are
$-z_{n},\bar{z}_{n}$ and $-\bar{z}_{n}$. Therefore, in Theorem 7, by choosing
$b=\frac{1}{a}$ and $\frac{\mu}{\sigma^{2}}+j\omega$ to be a zero of the
$\mathrm{erf}(z)$ function we arrive at the following result.

######  Theorem 8.

$\mathcal{N}_{L^{1}}(T_{a})$ is infinite-dimensional. Moreover,

$\displaystyle{\rm
span}\left(\bigcup_{(\mu_{n},\omega_{n}):z_{n}=\frac{\frac{1-a}{\sqrt{a}}\mu_{n}+j\sqrt{a}\omega_{n}}{\sqrt{2}}}f_{\mu_{n},\frac{a}{1-a},\omega_{n}}\right)\subseteq\mathcal{N}_{L^{1}}(T_{a}),$
(62)

where the $z_{n}$’s are the zeros of the $\mathrm{erf}$ function.

###### Proof.

Chose $\omega_{n}$ and $\mu_{n}$ such that

$\displaystyle
z_{n}=\frac{\frac{\mu}{\sigma^{2}}+jw}{\sqrt{2b}}=\frac{\frac{\mu}{\frac{a}{1-a}}+jw}{\sqrt{2\frac{1}{a}}}=\frac{1}{\sqrt{2}}\left(\frac{1-a}{\sqrt{a}}\mu_{n}+j\sqrt{a}\omega_{n}\right)$
(63)

where $z_{n}$ is a zero of the $\mathrm{erf}$ function. Then, by using (58),
we have that

$T_{a}[f_{\mu_{n},\frac{a}{1-a},\omega_{n}}](y)=0,$ (64)

since $c(b,\omega_{n},\mu_{n})=0$. Thus, the collection of
$f_{\mu_{n},\frac{a}{1-a},\omega_{n}}$’s are in the null space of $T_{a}$.
Furthermore, since there are infinitely many such functions, which follows
from the fact that $\mathrm{erf}(z)$ function has infinitely many zeros, and
since Gabor wavelets are linearly independent (provided that the set does not
form too dense of a set of points in the $(\mu,\omega)$-plane)[17], we arrive
at a conclusion that $\mathcal{N}_{L^{1}}(T_{a})$ is infinite-dimensional. ∎

The above theorem says that the null space of $T_{a}$ over $L^{1}(\mathbb{R})$
contains infinitely many Gabor wavelets. These Gabor wavelets are special in
the sense that the location and frequency components correspond to the real
and imaginary parts of zeros of the $\mathrm{erf}$ function, respectively.
Note that the above also implies that the following real-valued functions are
also solutions:

$\displaystyle\frac{f_{\mu_{n},\frac{a}{1-a},\omega_{n}}(x)+f_{\mu_{n},\frac{a}{1-a},\omega_{n}}(x)}{2}=\exp\left(-\frac{\left(x-\mu_{n}\right)^{2}}{2\frac{a}{1-a}}\right)\cos(x\omega_{n}),$
(65)
$\displaystyle\frac{f_{\mu_{n},\frac{a}{1-a},\omega_{n}}(x)-f_{\mu_{n},\frac{a}{1-a},\omega_{n}}(x)}{2j}=\exp\left(-\frac{\left(x-\mu_{n}\right)^{2}}{2\frac{a}{1-a}}\right)\sin(x\omega_{n}).$
(66)

The above discussion shows that the non-negativity of probability measures
plays a crucial role; otherwise, we get infinitely many solutions. Indeed, the
non-negativity of the probability measures will also play a key role in our
proof. An interesting implication of our results is that infinite linear
combinations of the functions defined on the left-hand side of (62) can only
result in a single non-negative function, which is the Gaussian pdf. Finally,
in Section 4.3, we will revisit functions similar to Gabor wavelets, where
such functions will be used to demonstrate that infinitely many distributions
can induce linearity in Bayesian estimators under other $L^{p}$ loss.

##  3 Main Results

In this section, we present our main result. Our main technique uses the
theory of _distributions_ and _tempered distributions_ from functional
analysis, the background of which can be found in [18]. In a nutshell, this is
a rigorous framework for extending the concept of functions to include
important examples such as the Heaviside delta function that arise naturally
from Fourier analysis.

The main result of this work is the following theorem.

######  Theorem 9.

Fix some $a\in[0,1)$. Then, $\mathsf{m}(X|Y=y)=ay,\,\forall y\in\mathbb{R}$ if
and only if $X\sim\mathcal{N}\left(0,\frac{a}{1-a}\right)$.

###### Proof.

Starting with (40) we have that

$\int_{-\infty}^{\infty}g^{\prime}(t-x)\mu(\mathrm{d}x)=0,\quad\forall
t\in\mathbb{R}.$ (67)

Lemma 10 below shows that $\mu$ is a tempered distribution, so that we can
take its Fourier transform, denoted as $\mu^{\wedge}$. Next, observe that
$\mu^{\wedge}$ is a (tempered) distribution supported at the origin, as is
shown in Lemma 11 below. Equivalently, we have that $\mu$ can be represented
as a polynomial function

$\mu(x)=\sum_{i=0}^{k}a_{i}x^{i}.$ (68)

We next show that all coefficients but $a_{0}$ are zero and that $\mu$ is a
constant. Suppose that $\mu(t-x)=\sum_{i,j\colon i+j\leq k}b_{ij}t^{i}x^{j}$
for some coefficients $(b_{ij})$. Evidently, $b_{ij}=0$ if and only if
$a_{i+j}=0$. Next, define

$\epsilon_{j}:=\int
g^{\prime}(x)x^{j}=\mathbb{E}[\mathsf{sign}(Z)Z^{j}]=\left\\{\begin{array}[]{cc}0&j\text{
even}\\\ \mathbb{E}[|Z|^{j}]&j\text{ odd}.\end{array}\right.$ (69)

Therefore, the condition for the linearity in (67) can be written as: for all
$t\in\mathbb{R}$

$0=\int_{\infty}^{\infty}g^{\prime}(t-x)\mu(\mathrm{d}x)=\sum_{i+j\leq
k,\,2\nmid j}b_{ij}t^{i}\epsilon_{j},$ (70)

Clearly, the only way a polynomial of degree $k$ can be zero on the real line
is if and only if all coefficients are zero. Thus, we have that $b_{ij}=0$ for
all $i\leq k$ and all odd $j\leq k$. This implies that all $a_{i}=0$ for
$i\geq 1$. This shows that $\mathrm{d}\mu(x)=a_{0}$. Consequently, using the
definition of $\mu$, we have that

$a_{0}=\exp\left((1-a)\frac{x^{2}}{2}\right)P_{X}(\sqrt{a}\mathrm{d}x)$ (71)

which implies that
$P(\mathrm{d}x)\propto\exp\left(\frac{(1-a)}{a}\frac{x^{2}}{2}\right)$. This
concludes the proof. ∎

######  Remark 1.

A key component in the proof of Theorem 9 was to show that $\mu$ is a tempered
distribution (Lemma 10), which relies crucially on the positivity of the
measure $\mu$ in establishing the growth estimate (73). Indeed, in the
counterexamples from Section 2.5 above, we do not have positivity and $\mu$
does not end up being a tempered distribution. Once $\mu$ is shown to be a
tempered distribution, Fourier transform techniques can be applied. We remark
that Fourier and complex analysis techniques have been successful in proving a
number of Gaussian-characterizing properties, such as the Bernstein theorem
[19] and the Lévy-Cramer theorem [20], which, in turn, show that Gaussian
distributions arise in a number of optimization problems in information theory
[21, 22, 23, 24, 25, 26, 27].

######  Lemma 10.

If a non-negative measure $\mu$ satisfies (67), then $\mu$ is a tempered
distribution.

###### Proof.

Since $\max\\{|g^{\prime}(x)|,g(x)\\}\lesssim e^{-\frac{x^{2}}{2}}$, it is
easy to check that

$G(t):=\int_{-\infty}^{\infty}g(t-x)\mu(\mathrm{d}x)$ (72)

is convergent for any $t$, and by dominated convergence and (67) we have that
$G^{\prime}(t)=0$. This shows that $G(t)=C$ is a constant. Since $g(\cdot)\geq
c1_{[-1,1]}$ for some $c>0$, and $\mu$ is a non-negative measure, it follows
that $\mu([t-1,t+1])\leq\frac{C}{c}$ for all $t$. In particular, there exists
a constant $C_{1}$ such that $\mu([-R,R])\leq C_{1}R$ for all $R>1$. Then for
any $\psi$ supported on $\\{|x|\leq R\\}$, we obtain

$\int\psi(x)\mu(\mathrm{d}x)\leq C_{1}R\sup_{|x|\leq R}|\psi(x)|.$ (73)

This growth estimate implies that $\mu$ is a tempered distribution [18, p.
147, Exercise 7]. This concludes the proof. ∎

######  Lemma 11.

$\mu^{\wedge}=\sum_{i=0}^{k}a_{i}\partial_{x}^{i}\delta$ is a finite sum.

###### Proof.

Let $\mathcal{D}$ be the set of smooth (indefinitely differentiable) functions
with compact support, equipped with the topology of convergence of all the
(any order of) derivatives and containment of the support. A distribution is a
continuous linear functional on $\mathcal{D}$. Let $\psi\in\mathcal{D}$ be an
arbitrary function supported on $\mathbb{R}\setminus\\{0\\}$. Using Lemma 6,
we know that $g^{\prime\wedge}$ is the Dawson function, which is a smooth
function vanishing only at zero, therefore, there exists $\xi\in\mathcal{D}$
such that $\psi=g^{\prime\wedge}\cdot\xi$ (where $\cdot$ indicates pointwise
product of two functions). Then

$\displaystyle\mu^{\wedge}(\psi)$ $\displaystyle=\mu(\psi^{\wedge})$ (74)
$\displaystyle=\mu(g^{\prime\sim}*\psi^{\wedge})$ (75)
$\displaystyle=\int\left(\int
g^{\prime}(t-x)\xi^{\wedge}(t)dt\right)\mu(\mathrm{d}x)$ (76)
$\displaystyle=\int\left(\int
g^{\prime}(t-x)\mathrm{d}\mu(x)\right)\xi^{\wedge}(t)\mathrm{d}t$ (77)
$\displaystyle=0$ (78)

where (74) uses the definition of Fourier transform of a distribution [18, p.
108], and $\sim$ indicates the reflection of a function, i.e.,
$f^{\sim}(x)=f(-x)$ for any $f$; (77) uses Fubini’s theorem; and (78) uses
(67). This implies that $\mu^{\wedge}$ is supported at 0. Using [18, p. 110]
we conclude that $\mu^{\wedge}=\sum_{i=0}^{k}a_{i}\partial_{x}^{i}\delta$ is a
finite sum. ∎

##  4 Discussion, Extensions and Future Directions

This work has focused on characterizing which prior distributions give an
optimal estimator (with respect to $L^{1}$ loss) that is linear, which is
equivalent to the answering the question of when conditional medians are a
linear function of the observation. We have focused on a Gaussian noise model
and $L^{1}$ loss, but the question can be considered more generally. In this
section, we will discuss several interesting future directions and show
several extensions.

###  4.1  A Near Miss for Poisson Noise

One interesting direction is to consider the case of Poisson noise, where the
input-output relationship is given by

$P_{Y|X}(y|x)=\frac{1}{y!}x^{y}\mathrm{e}^{-x},\,x\in\mathbb{R}_{+},y\in\mathbb{N}_{0}$
(79)

with the convention that $0^{0}=1$.

It is well-known that a linear conditional expectation is induced by gamma
distribution prior, that is, when $X\sim{\rm Gam}(\alpha,\beta)$ where the pdf
of a gamma distribution is given by

$f_{X}(x)=\frac{\beta^{\alpha}}{\Gamma(\alpha)}x^{\alpha-1}\mathrm{e}^{-\beta
x},\,x\geq 0,$ (80)

where $\alpha>0$ is the shape parameter and $\beta>0$ is the rate parameter.
The gamma is a unique such distribution [28, 3, 7]. Moreover, the conditional
expectation is given by

$\mathbb{E}[X|Y=y]=\frac{1}{\beta+1}y+\frac{\alpha}{\beta+1},y\in\mathbb{N}_{0}.$
(81)

and the posterior distribution is also gamma with

$X\mid Y=y\sim{\rm Gam}(\alpha+y,\beta+1),\,y\in\mathbb{R}.$ (82)

Now, the median of the gamma distribution does not have a closed-form and is
given by

$m(X|Y=y)=\frac{1}{\beta}\gamma^{-1}\left(\frac{1}{2},\alpha+y\right),$ (83)

where $\gamma^{-1}$ is the inverse of the lower incomplete gamma function and
needs to be computed numerically. Clearly, the conditional median, unlike the
conditional mean, is _not_ linear. Approximations of the median of the gamma
distribution have received some attention in the literature, and the
interested reader is referred to [29, 30, 31].

Although the median in (83) is not linear, it is nearly linear. In fact, the
deviation from linearity is rather small and decreases as
$O\left(\frac{1}{y}\right)$ [31]. Fig. 1 compares the conditional mean in (82)
and the conditional median in (83) for $(\alpha,\beta)=(1,1)$.

$0$$5$$10$$15$$20$$0$$2$$4$$6$$8$$10$$12$$y$MedianMean (a) Conditional mean in
(82) vs. conditional median in (83).

$0$$5$$10$$15$$20$$-0.17$$-0.16$$-0.16$$y$ (b) Difference between (82) vs.
(83).

Figure 1: Poisson Noise Case: Conditional mean vs. conditional median under a
gamma prior with $(\alpha,\beta)=(1,1)$.

An interesting future direction will be to see if there exists another prior
on $X$ that induces linearity of the conditional median. It is not difficult
to see, following the same proof as in Proposition 4, that $f_{X}$ induced
linearity for give a pair $(a,b)$444Note that since $X$ is only supported on
non-negative values, in order not to lose generality, we need to consider
affine estimators $ay+b$ instead of just a linear estimator $ay$. if and only
if

$0=\int_{0}^{\infty}\mathsf{sign}\left(x-ay-b\right)x^{y}\mathrm{e}^{-x}f_{X}(x)\mathrm{d}x,\,y\in\mathbb{N}_{0}.$
(84)

There are a few key distinctions in the equation (84) from the Gaussian case
that could potentially complicate its solution. First, the integration over
non-negative values: In contrast to the Gaussian case, the integration in this
equation is limited to non-negative values. Second, the integral in (84) is
required to equal to zero for non-negative integers rather than the entire
real line. These restrictions potentially introduce additional constraints and
can affect the solution methodology.

###  4.2 Extension to the Natural Exponential Family

In this section, we extend our results to members of certain exponential
families of distributions. Recall that a _natural exponential family_ ,
parameterized by $x\in\mathbb{R}$, is characterized by the pdf of the form

$f_{Y|X}(y|x)=h(y)\mathrm{e}^{xy-\psi(x)},\,y\in\mathbb{R},\,x\in\mathbb{R},$
(85)

where $h(y):\mathbb{R}\to[0,\infty)$ is known as the _base measure_ and
$\psi:\mathbb{R}\mapsto\mathbb{R}$ is known as the _log-partition function_.
We now seek to characterize the prior that induces linearity of the
conditional median when the noise distribution induces a conditional
distribution for $Y$ given $X=x$ whose pdf is a member of a natural
exponential family in (85). For the natural exponential family, the condition
for linearity in (35) is derived verbatim and is given by: for $a\in[0,1)$

$\mathbb{E}\left[{\rm sign}(X-ay)h(y)e^{Xy-\psi(X)}\right]=0,\,\forall
y\in\mathbb{R}.$ (86)

While we do not have an answer for every such exponential family prior, we
show that our result can be bootstrapped to find the solution to (86) for some
special cases of the exponential families. Answering this in full generality
is outside of the scope of this work and constitutes an interesting and
ambitious future direction.

######  Theorem 12.

Suppose that

$\sup_{x\in\mathbb{R}}\,\frac{x^{2}}{2}-\psi(x)<\infty.$ (87)

Then, the only solution to (86) is given by

$f_{X}(x)\propto\mathrm{e}^{-\frac{x^{2}}{2a}+\psi(x)},$ (88)

provided that it is integrable.

###### Proof.

Suppose that a probability measure $P_{X}$ satisfies (86) and induces
linearity. Now, starting with (86), note the following transformations:

$\displaystyle\int{\rm
sign}(x-ay)h(y)\mathrm{e}^{xy-\psi(x)}\,P_{X}(\mathrm{d}x)=0,\forall y$
$\displaystyle\Longleftrightarrow\int{\rm
sign}(x-ay)\mathrm{e}^{-\frac{x^{2}}{2}+xy}\mathrm{e}^{\frac{x^{2}}{2}-\psi(x)}\,P_{X}(\mathrm{d}x)=0,\forall
y$ (89) $\displaystyle\Longleftrightarrow\int{\rm
sign}(x-ay)\mathrm{e}^{-\frac{(y-x)^{2}}{2}}\mathrm{e}^{\frac{x^{2}}{2}-\psi(x)}\,P_{X}(\mathrm{d}x)=0,\forall
y$ (90) $\displaystyle\Longleftrightarrow\int{\rm
sign}(x-ay)\mathrm{e}^{-\frac{(y-x)^{2}}{2}}\,G_{X}(\mathrm{d}x)=0,\forall y$
(91)

where we have defined

$G_{X}(\mathrm{d}x)=\mathrm{e}^{\frac{x^{2}}{2}-\psi(x)}P_{X}(\mathrm{d}x).$
(92)

Now, if $G_{X}(\mathbb{R})<\infty$, then using Theorem 9, we have that the
only solution is the measure $G_{X}$ absolutely continuous with respect to
Lebesgue measure with the density given by

$g(x)\propto\mathrm{e}^{-\frac{x^{2}}{2\frac{a}{1-a}}}.$ (93)

Note that a sufficient condition for $G_{X}(\mathbb{R})<\infty$ is
$\sup_{x\in\mathbb{R}}\frac{x^{2}}{2}-\psi(x)\leq c<\infty$.

Next, letting $f_{X}$ be the pdf of $P_{X}$, using (92) and (93), we have that

$f_{X}(x)\propto\mathrm{e}^{-\frac{x^{2}}{2\frac{a}{1-a}}-\frac{x^{2}}{2}+\psi(x)}=\mathrm{e}^{-\frac{x^{2}}{2a}+\psi(x)},$
(94)

is the unique solution to (86) provided that it is integrable. This concludes
the proof. ∎

Note that a necessary condition for $f_{X}$ in (88) to be integrable is

$\sup_{x\in\mathbb{R}}\psi(x)-\frac{x^{2}}{2a}<\infty.$ (95)

This, together with the condition in (87), implies that such priors for which
we for which we could find a unique solution need to be nearly Gaussian. An
example of $\psi(x)$ that satisfies the above condition is given by

$\psi(x)=\frac{x^{2}}{2}-\frac{1}{1+x^{2}},$ (96)

Note that $\psi(x)$ is also convex and leads to Gaussian-like noise and
Gaussian-like prior.

It is not surprising that the Gaussian result in Theorem 9 only applies to a
limited range of distributions. Consider that the distributions that yield
linearity of the conditional mean, within the exponential family, known as
conjugate priors [2, 3], can be quite distinct from Gaussian distributions.
Consequently, when considering the conditional median, we should not
anticipate that an approximately Gaussian distribution would consistently
establish linearity.

###  4.3 On Other $L^{p}$ Losses

In this section, we consider similar questions to that of when the median is
linear for other $L_{p}$ losses. More precisely, we consider a Bayesian risk
of the form: $p\geq 1$

$\inf_{g}\mathbb{E}[|X-g(Y)|^{p}]$ (97)

We again are interested in finding the distributions that would lead to the
optimality of linear estimators. The condition for linearity akin to the one
in (35) for the $L^{p}$ losses with even $p$ is given by

$\displaystyle\int_{-\infty}^{\infty}\mathsf{sign}(x-ay)|x-ay|^{p-1}\phi(y-x)P_{X}(\mathrm{d}x)=0,\,y\in\mathbb{R}$
(98)

which, by following the steps in Proposition 5, can be re-written as a
convolution

$\displaystyle\int_{-\infty}^{\infty}\mathsf{sign}(x-y)|x-ay|^{p-1}\phi(y-x)\mu(\mathrm{d}x)=0,\,y\in\mathbb{R}$
(99)

where as before
$\mu(\mathrm{d}x)=\exp\left((1-a)\frac{x^{2}}{2}\right)P_{X}(\sqrt{a}\,\mathrm{d}x)$.

Next, somewhat surprisingly, we show that for $p>2$ there are infinitely many
priors that induce linearity.

######  Theorem 13.

Fix a $p\in(2,\infty)$. Then for every $|\rho|\leq 1$ and
$\theta\in\mathbb{R}$, there exists an $\omega$ such that the density

$f_{X}(x)\propto\mathrm{e}^{-\frac{1-a}{a}\frac{x^{2}}{2}}\left(1+\rho\cos\left(\frac{\omega
x}{\sqrt{a}}+\theta\right)\right)$ (100)

induces a linear minimum $L^{p}$ estimator. Moreover, for even $p$, $\omega$’s
are given by the zeros of the probabilist’s Hermite polynomial $H_{e_{p-1}}$.

###### Proof.

We show that there is an appropriate choice of $\omega$ such that the density
in (100) satisfies (99) , which would imply that the above density induces
linearity of the conditional $L^{p}$ estimator. We have that

$\displaystyle\int_{-\infty}^{\infty}\mathsf{sign}(x-y)|x-y|^{p-1}\phi(y-x)\exp\left((1-a)\frac{x^{2}}{2}\right)f_{X}(\sqrt{a}x)\mathrm{d}x$
$\displaystyle=\int_{-\infty}^{\infty}\mathsf{sign}(x-y)|x-y|^{p-1}\phi(y-x)\left(1+\rho\cos\left(\omega
x+\theta\right)\right)\mathrm{d}x$ (101)
$\displaystyle=\rho\int_{-\infty}^{\infty}\mathsf{sign}(x-y)|x-y|^{p-1}\phi(y-x)\cos\left(\omega
x+\theta\right)\mathrm{d}x$ (102)
$\displaystyle=\rho\mathsf{Re}\left\\{\mathrm{e}^{-j\omega
y+j\theta}\mathcal{F}\left(\mathsf{sign}(\cdot)|\cdot|^{p-1}\phi(\cdot)\right)(\omega)\right\\}$
(103)

where (102) follows from the fact that the function is odd.

For even $p$, the proof is simple and

$\displaystyle\mathsf{Re}\left\\{\mathrm{e}^{-j\omega
y+j\theta}\mathcal{F}\left((\cdot)^{p-1}\phi(\cdot)\right)(\omega)\right\\}$
$\displaystyle=\mathsf{Re}\left\\{\mathrm{e}^{-j\omega
y+j\theta}\frac{\mathrm{d}^{p-1}}{\mathrm{d}\omega^{p-1}}\phi(\omega)\right\\}$
(104) $\displaystyle=\mathsf{Re}\left\\{\mathrm{e}^{-j\omega
y+j\theta}(-1)^{p-1}H_{e_{p-1}}(\omega)\phi(\omega)\right\\},$ (105)

where (105) follows by using the identity between derivative of the Gaussian
density and the probabilist’s Hermite polynomials $H_{e_{k}}$. Note that
$H_{e_{p-1}}$ has exactly $p-1$ zeros, thus placing $\omega$ at any of these
locations will result in (105) being equal to zero.

For the general $p$, we require to show that

$\mathcal{F}\left(\mathsf{sign}(\cdot)|\cdot|^{p-1}\phi(\cdot)\right)(\omega)$
(106)

has nonzero roots. The proof of this fact is shown in Appendix D. This
concludes the proof. ∎

Fig. 2 shows a few examples of the distributions in (100) for $p=4$ where we
note that $H_{e_{3}}$ has zeros at $\\{\pm\sqrt{3},0\\}$. An interesting
observation to note is that a non-symmetric distribution induces linearity of
the estimator.

$-10$$-8$$-6$$-4$$-2$$0$$2$$4$$6$$8$$10$$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$x$Gaussian
(i.e.,
$\omega=0,\theta=0$)$\omega=\sqrt{3},\theta=0$$\omega=\sqrt{3},\theta=\frac{\pi}{2}$
Figure 2: Example of probability densities in (100) for $p=4$ and $\rho=1$.

We note that the authors of [5] have shown that under the assumption that $Z$
and $X$ have the same variance, the estimator is linear if and only if $X$ is
Gaussian.555In fact the result of [5] holds for arbitrary distributions on the
noise $Z$, and that that if $X$ and $Z$ have the same variance then the
estimator is linear if and only if $X$ and $Z$ have the same distribution. Our
results do not contradict those of [5] since it is not difficult to
demonstrate that the variance of the distribution in (100) for $\theta=0$ is
given by

$\mathsf{Var}(X)=\frac{a}{1-a}\frac{1+\left(1-\frac{\omega^{2}}{1-a}\right)\rho\mathrm{e}^{-\frac{\omega^{2}}{2(1-a)}}}{1+\rho\mathrm{e}^{-\frac{\omega^{2}}{2(1-a)}}},$
(107)

which is only equal to one if $(a,\omega)=(\frac{1}{2},0)$ and/or
$(a,\rho)=(\frac{1}{2},0)$.

We complement the result in Theorem 13 by showing that for $p\in[1,2]$, the
Gaussian density is only solution.

######  Theorem 14.

For any $p\in[1,2]$, Gaussian priors are the only ones inducing linear optimal
estimators.

###### Proof.

The proof is given in Appendix D. ∎

###  4.4 Extension to Higher Dimensions

Interestingly, the techniques of characterizing prior distribution that induce
linearity of the conditional expectation are largely independent of the
dimension of the random parameter $X$ to be estimated. For example, the
results for the continuous exponential family in the previous section hold
verbatim for the case when $X$ is an $n$-dimensional vector. Similar results
also hold for the discrete vector cases, such the vector Poisson case [32].

The situation with extending the results from the present paper to the
multivariate case is more complex. First of all, unlike for the conditional
expectation, there is no unique way of defining the median in the multivariate
setting, and several competing definitions exist; the interested reader is
referred to [33] and references therein. Second of all, the median that
minimizes the $L^{1}$ loss, also known as the _spatial median_ [34], that is

$\mathsf{m}_{\text{S}}(X|Y)=\arg\min_{f}\mathbb{E}\left[\|X-f(Y)\|\right],$
(108)

does not have a closed-form characterization, unlike the conditional mean,
which does have an integral representation. Along these lines, an interesting
future direction is to consider a scenario where

$Y=X+Z$

where $Z$ multivariate normal with zero mean and covariance matrix
$\mathsf{K}$ and independent of the vector $X$, and consider the following
multivariate estimation problem with $L_{p,k}$ loss:

$\mathsf{m}_{p,k}(X|Y)=\arg\min_{f}\mathbb{E}\left[\|X-f(Y)\|_{\ell_{k}}^{p}\right],\,k\geq
1,\,p\geq 1$ (109)

where
$\|u\|_{\ell_{k}}=\left(\sum_{i=1}^{n}|u_{i}|^{k}\right)^{\frac{1}{k}},u\in\mathbb{R}^{n}$
is the usual $\ell_{k}$ norm. Under this setup, one could seek to understand
under what conditions on $X$ do we have that

$\mathsf{m}_{p,k}(X|Y)=\mathsf{A}Y$ (110)

where $\mathsf{A}$ is a matrix. In particular, with the tools developed in
Section 3 and Section 4.3, it seems to be possible to characterize the region
of $(p,k)$ values such that Gaussian is the only prior that induces linearity.

## Acknowledgements

The authors would like to thank Dr. Tang Liu for a helpful discussion on the
near-miss example in the Poisson case and for pointing out reference [29].

## References

  * [1] L. P. Barnes, A. Dytso, and H. V. Poor, “${L}^{1}$ estimation in Gaussian noise: On the optimality of linear estimators,” in _Proceedings of the 2023 IEEE International Symposium on Information Theory (ISIT)_ , June 2023, pp. 1872–1877.
  * [2] P. Diaconis and D. Ylvisaker, “Conjugate priors for exponential families,” _The Annals of Statistics_ , vol. 7, no. 2, pp. 269–281, 1979.
  * [3] J.-P. Chou, “Characterization of conjugate priors for discrete exponential families,” _Statistica Sinica_ , vol. 11, pp. 409–418, 2001.
  * [4] C. M. Bishop and N. M. Nasrabadi, _Pattern Recognition and Machine Learning_. Springer, 2006.
  * [5] E. Akyol, K. Viswanatha, and K. Rose, “On conditions for linearity of optimal estimation,” _IEEE Transactions on Information Theory_ , vol. 58, no. 6, pp. 3497–3508, 2012.
  * [6] F. du Pin Calmon, Y. Polyanskiy, and Y. Wu, “Strong data processing inequalities for input constrained additive noise channels,” _IEEE Transactions on Information Theory_ , vol. 64, no. 3, pp. 1879–1892, 2018.
  * [7] A. Dytso and H. V. Poor, “Estimation in Poisson noise: Properties of the conditional mean estimator,” _IEEE Transactions on Information Theory_ , vol. 66, no. 7, pp. 4304–4323, 2020.
  * [8] R. J. Tomkins, “On conditional medians,” _The Annals of Probability_ , vol. 3, no. 2, pp. 375–379, 1975.
  * [9] Y. N. Ghosh and B. Mukherjee, “On probabilistic properties of conditional medians and quantiles,” _Statistics & Probability Letters_, vol. 76, no. 16, pp. 1775–1780, 2006.
  * [10] D. Medarametla and E. Candès, “Distribution-free conditional median inference,” _Electronic Journal of Statistics_ , vol. 15, no. 2, pp. 4625–4658, 2021.
  * [11] J. H. Kemperman, “On the FKG-inequality for measures on a partially ordered space,” in _Indagationes Mathematicae (Proceedings)_ , vol. 80, no. 4. North-Holland, 1977, pp. 313–331.
  * [12] A. Dytso, R. Bustin, D. Tuninetti, N. Devroye, H. V. Poor, and S. S. Shitz, “On the minimum mean $p$ th error in Gaussian noise channels and its applications,” _IEEE Transactions on Information Theory_ , vol. 64, no. 3, pp. 2012–2037, 2017.
  * [13] S. Resnick, _A Probability Path_. Springer, 2019.
  * [14] M. Abramowitz and I. A. Stegun, _Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables_. US Government Printing Office, 1964, vol. 55.
  * [15] L. Shen and L. Bai, “A review on Gabor wavelets for face recognition,” _Pattern Analysis and Applications_ , vol. 9, pp. 273–292, 2006.
  * [16] H. E. Fettis, J. C. Caslin, and K. R. Cramer, “Complex zeros of the error function and of the complementary error function,” _Mathematics of Computation_ , vol. 27, no. 122, pp. 401–407, 1973.
  * [17] G. E. Pfander and P. Rashkov, “Remarks on multivariate Gaussian Gabor frames,” 2010. [Online]. Available: https://arxiv.org/pdf/1008.3517v2.pdf
  * [18] E. M. Stein and R. Shakarchi, _Functional Analysis: Introduction to Further Topics in Analysis_. Princeton University Press, 2011, vol. 4.
  * [19] S. N. Bernshtein, “On a property characterizing Gauss’ law,” _Trudy Leningr. Bolitekhn._ , vol. 217, no. 3, pp. 21–22, 1941.
  * [20] H. Cramér, “Über eine Eigenschaft der normalen Verteilungsfunktion,” _Mathematische Zeitschrift_ , vol. 41, no. 1, pp. 405–414, 1936.
  * [21] Y. Geng and C. Nair, “The capacity region of the two-receiver Gaussian vector broadcast channel with private and common messages,” _IEEE Transactions on Information Theory_ , vol. 60, no. 4, pp. 2087–2104, 2014.
  * [22] T. A. Courtade and J. Jiao, “An extremal inequality for long Markov chains,” in _Proceedings of the 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2014, pp. 763–770.
  * [23] J. Liu, T. A. Courtade, P. Cuff, and S. Verdu, “Information-theoretic perspectives on Brascamp-Lieb inequality and its reverse,” 2017. [Online]. Available: https://arxiv.org/pdf/1702.06260.pdf
  * [24] J. Liu, T. A. Courtade, P. W. Cuff, and S. Verdú, “A forward-reverse Brascamp-Lieb inequality: Entropic duality and Gaussian optimality,” _Entropy_ , vol. 20, no. 6, p. 418, 2018.
  * [25] V. Anantharam, V. Jog, and C. Nair, “Unifying the Brascamp-Lieb inequality and the entropy power inequality,” _IEEE Transactions on Information Theory_ , vol. 68, no. 12, pp. 7665–7684, 2022.
  * [26] J. Liu, “Stability of the Gaussian stationary point in the Han-Kobayashi region for Z-interference channels,” _IEEE Transactions on Information Theory_ , 2023, to appear.
  * [27] M. M. Mahvari and G. Kramer, “Stability of Bernstein’s theorem and soft doubling for vector Gaussian channels,” 2023. [Online]. Available: https://arxiv.org/pdf/2212.04484.pdf
  * [28] N. Johnson, “Uniqueness of a result in the theory of accident proneness,” _Biometrika_ , vol. 44, no. 3-4, pp. 530–531, 1957.
  * [29] J. Chen and H. Rubin, “Bounds for the difference between median and mean of gamma and Poisson distributions,” _Statistics & Probability letters_, vol. 4, no. 6, pp. 281–283, 1986.
  * [30] K. P. Choi, “On the medians of gamma distributions and an equation of Ramanujan,” _Proceedings of the American Mathematical Society_ , vol. 121, no. 1, pp. 245–251, 1994.
  * [31] C. Berg and H. L. Pedersen, “The Chen-Rubin conjecture in a continuous setting,” _Methods and Applications of Analysis_ , vol. 13, no. 1, pp. 63–88, 2006.
  * [32] A. Dytso, M. Fauß, and H. V. Poor, “The vector Poisson channel: On the linearity of the conditional mean estimator,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 5894–5903, 2020.
  * [33] C. G. Small, “A survey of multidimensional medians,” _International Statistical Review/Revue Internationale de Statistique_ , vol. 58, no. 3, pp. 263–277, 1990.
  * [34] P. Milasevic and G. Ducharme, “Uniqueness of the spatial median,” _The Annals of Statistics_ , vol. 15, no. 1, pp. 1332–1333, 1987.
  * [35] A. Dytso, H. Poor, and S. Shamai (Shitz), “Conditional mean estimation in Gaussian noise: A meta derivative identity with applications,” _IEEE Transactions on Information Theory_ , 2022, to appear.
  * [36] E. Lukacs, _Characteristic Functions_. Griffin, London, 1970.
  * [37] C. Stein, “A bound for the error in the normal approximation to the distribution of a sum of dependent random variables,” in _Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2: Probability Theory_. University of California Press, 1972, pp. 583–603.
  * [38] D. Guo, Y. Wu, S. S. Shitz, and S. Verdú, “Estimation in Gaussian noise: Properties of the minimum mean-square error,” _IEEE Transactions on Information Theory_ , vol. 57, no. 4, pp. 2371–2385, 2011.
  * [39] S. G. Krantz and H. R. Parks, _A Primer of Real Analytic Functions_. Springer Science & Business Media, 2002.
  * [40] E. H. Lieb and M. Loss, _Analysis_. American Mathematical Society, 2001, vol. 14.

##  Appendix A Proof of Theorem 7

We first note that

$\displaystyle\int_{-\infty}^{\infty}\mathsf{sign}(x-ay)\phi(y-x)f(x)\mathrm{d}x=\int_{-\infty}^{ay}\phi(y-x)f(x)\mathrm{d}x-\int_{ay}^{\infty}\phi(y-x)f(x)\mathrm{d}x.$
(111)

Next, we will need the following indefinite integral: for any $d$ and $b$

$\displaystyle\int\exp\left(dx-\frac{bx^{2}}{2}\right)\mathrm{d}x=\sqrt{\frac{\pi/2}{b}}\exp\left(\frac{d^{2}}{2b}\right){\rm
erf}\left(\frac{bx-d}{\sqrt{2b}}\right).$ (112)

Next, let $b=1+\frac{1}{\sigma^{2}}$ and $d=y+\frac{\mu}{\sigma^{2}}+jw$ and
note that

$\displaystyle\int_{ay}^{\infty}\phi(y-x)\exp\left(-\frac{(x-\mu)^{2}}{2\sigma^{2}}\right)\mathrm{e}^{jxw}\mathrm{d}x$
$\displaystyle=\phi(y)\mathrm{e}^{-\frac{\mu^{2}}{2\sigma^{2}}}\int_{ay}^{\infty}\mathrm{e}^{(y+\frac{\mu}{\sigma^{2}}+jw)x-\frac{bx^{2}}{2}}\mathrm{d}x$
(113)
$\displaystyle=\phi(y)\mathrm{e}^{-\frac{\mu^{2}}{2\sigma^{2}}}\sqrt{\frac{\pi/2}{b}}\exp\left(\frac{(y+\frac{\mu}{\sigma^{2}}+jw)^{2}}{2b}\right)\left(1-\mathrm{erf}\left(\frac{bay-(y+\frac{\mu}{\sigma^{2}}+jw)}{\sqrt{2b}}\right)\right).$
(114)

Also,

$\displaystyle\int_{-\infty}^{ay}\phi(y-x)\exp\left(-\frac{(x-\mu)^{2}}{2\sigma^{2}}\right)\mathrm{e}^{jxw}\mathrm{d}x$
(115)
$\displaystyle=\phi(y)\mathrm{e}^{-\frac{\mu^{2}}{2\sigma^{2}}}\int_{-\infty}^{ay}\mathrm{e}^{(y+\frac{\mu}{\sigma^{2}}+jw)x-\frac{bx^{2}}{2}}\mathrm{d}x$
(116)
$\displaystyle=\phi(y)\mathrm{e}^{-\frac{\mu^{2}}{2\sigma^{2}}}\sqrt{\frac{\pi/2}{b}}\exp\left(\frac{(y+\frac{\mu}{\sigma^{2}}+jw)^{2}}{2b}\right)\left(\mathrm{erf}\left(\frac{bay-(y+\frac{\mu}{\sigma^{2}}+jw)}{\sqrt{2b}}\right)+1\right)$
(117)

Combining everything we have that

$\displaystyle\int_{-\infty}^{\infty}\mathsf{sign}(x-ay)\phi(y-x)\exp\left(-\frac{(x-\mu)^{2}}{2\sigma^{2}}\right)\mathrm{e}^{jxw}\mathrm{d}x$
$\displaystyle=2\phi(y)\mathrm{e}^{-\frac{\mu^{2}}{2\sigma^{2}}}\sqrt{\frac{\pi/2}{b}}\exp\left(\frac{(y+\frac{\mu}{\sigma^{2}}+jw)^{2}}{2b}\right)\mathrm{erf}\left(\frac{(y+\frac{\mu}{\sigma^{2}}+jw)-bay}{\sqrt{2b}}\right).$
(118)

Now, for $a=\frac{1}{b}$

$\displaystyle T_{a}[f_{\mu,\sigma^{2},\omega}](y)$
$\displaystyle=2\phi(y)\mathrm{e}^{-\frac{\mu^{2}}{2\sigma^{2}}}\sqrt{\frac{\pi/2}{b}}\exp\left(\frac{(y+\frac{\mu}{\sigma^{2}}+jw)^{2}}{2b}\right)\mathrm{erf}\left(\frac{\frac{\mu}{\sigma^{2}}+jw}{\sqrt{2b}}\right)$
(119)
$\displaystyle=2\frac{1}{\sqrt{2\pi}}\sqrt{\frac{\pi/2}{b}}\exp\left(\frac{(y+\frac{\mu}{\sigma^{2}}+jw)^{2}}{2b}-\frac{\mu^{2}}{2\sigma^{2}}-\frac{y^{2}}{2}\right)\mathrm{erf}\left(\frac{\frac{\mu}{\sigma^{2}}+jw}{\sqrt{2b}}\right)$
(120)
$\displaystyle=\sqrt{\frac{1}{b}}\exp\left(\frac{(y+\frac{\mu}{\sigma^{2}}+jw)^{2}}{2b}-\frac{\mu^{2}}{2\sigma^{2}}-\frac{y^{2}}{2}\right)\mathrm{erf}\left(\frac{\frac{\mu}{\sigma^{2}}+jw}{\sqrt{2b}}\right)$
(121)
$\displaystyle=\sqrt{\frac{1}{b}}\exp\left(-\left(1-\frac{1}{b}\right)\frac{(y-\mu)^{2}}{2}\right)\exp\left(\frac{jw(y+\frac{\mu}{\sigma^{2}})}{b}\right)\exp\left(-\frac{\omega^{2}}{2b}\right)\mathrm{erf}\left(\frac{\frac{\mu}{\sigma^{2}}+jw}{\sqrt{2b}}\right)$
(122)

where we have have used that $b=1+\frac{1}{\sigma^{2}}$. This concludes the
proof.

##  Appendix B Proof of Linearity of the Conditional Expectation

We presented here four different proofs that the only prior distribution that
induces linearity of the conditional expectation, under the model in (1), is
Gaussian $X$. To the best of our knowledge, the proofs based on Stein’s method
and on the cumulant method are new.

###  B.1 Tweedie Formula Approach

Using Tweedie’s formula, the conditional expectation can be written as

$\displaystyle\mathbb{E}[X|Y=y]=y+\frac{\mathrm{d}}{\mathrm{d}y}\log
f_{Y}(y),\,y\in\mathbb{R}$ (123)

where $f_{Y}$ is the pdf of $Y$. Now, by the linearity assumption, we have
that

$\displaystyle(a-1)y=\frac{\mathrm{d}}{\mathrm{d}y}\log
f_{Y}(y),\,y\in\mathbb{R}.$ (124)

The solution to this differential equation has a unique form and is given by

$\displaystyle f_{Y}(y)=\mathrm{e}^{(a-1)\frac{y^{2}}{2}+by+c}$ (125)

for some $b$ and $c$. Therefore, $f_{Y}$ is Gaussian. Now using the standard
characteristic function argument, the only distribution on $X$ that induces
$Y$ to be Gaussian is Gaussian.

###  B.2 Cumulant Approach

Our starting place for this proof is the following expression shown in [35]:
for $k\geq 1$

$\frac{\mathrm{d}^{k}}{\mathrm{d}x^{k}}\mathbb{E}[X|Y=y]=\kappa_{X|Y=y}(k+1),$
(126)

where $\kappa_{X|Y=y}(k)$ is the $k$-th order conditional cumulant.

Now using the linearity assumption, we have that for $y\in\mathbb{R}$

$\displaystyle\kappa_{X|Y=y}(1)$ $\displaystyle=ay,$ (127)
$\displaystyle\kappa_{X|Y=y}(2)$ $\displaystyle=a,$ (128)
$\displaystyle\kappa_{X|Y=y}(k)$ $\displaystyle=0,\,k\geq 3$ (129)

Note that the only distribution that satisfies the above property is Gaussian
[36].

###  B.3 Stein Method Approach

Recall the following two facts. First, by the orthogonality principle,

$\mathbb{E}[(X-\mathbb{E}[X|Y])g(Y)]=0,$ (130)

for all $g$. Second,

$\mathbb{E}[f^{\prime}(U)]=\sigma^{2}\mathbb{E}[Uf(U)]$ (131)

for all differential functions $f$, if and only if $U$ is zero mean Gaussian
with variance $\sigma^{2}$ [37]. The result in (131) is known as Stein’s
equation.

Now using the linearity assumption and the orthogonality principle, observe
the following sequence of steps:

$\displaystyle\mathbb{E}[Xg(Y)]$ $\displaystyle=a\mathbb{E}[Yg(Y)]$ (132)
$\displaystyle=a\mathbb{E}[\mathbb{E}[Yg(Y)|X]]$ (133)
$\displaystyle=a\mathbb{E}[\mathbb{E}[(X+Zg(X+Z)|X]]$ (134)
$\displaystyle=a\mathbb{E}[X\mathbb{E}[g(X+Z)|X]+\mathbb{E}[(Zg(X+Z)|X]]$
(135)
$\displaystyle=a\mathbb{E}[X\mathbb{E}[g(X+Z)|X]+\mathbb{E}[g^{\prime}(X+Z)|X]]$
(136)
$\displaystyle=a\mathbb{E}[X\mathbb{E}[g(Y)|X]+\mathbb{E}[g^{\prime}(Y)|X]]$
(137) $\displaystyle=a\mathbb{E}[Xg(Y)+g^{\prime}(Y)],$ (138)

where (136) follows by using Stein’s equation.

Now re-writting (138) we have that, for all $g$

$\displaystyle(1-a)\mathbb{E}[Xg(Y)]=a\mathbb{E}[g^{\prime}(Y)].$ (139)

Next, note that by the orthogonality principle
$\mathbb{E}[Xg(Y)]=a\mathbb{E}[Yg(Y)]$; therefore (139) can finally be re-
written as: for all $g$

$(1-a)\mathbb{E}[Yg(Y)]=\mathbb{E}[g^{\prime}(Y)],$ (140)

which corresponds to Stein’s equation and therefore, $Y$ must be Gaussian with
variance $\frac{1}{1-a}$. This further implies that $X$ needs to be Gaussian
with variance $\frac{a}{1-a}$.

###  B.4 Fourier Approach

This proof will rely on the orthogonality principle in (130). By the linearity
assumption and choose $g(Y)=\mathrm{e}^{j\omega Y}$, we have that

$\displaystyle\mathbb{E}[X\mathrm{e}^{j\omega Y}]$
$\displaystyle=a\mathbb{E}[Y\mathrm{e}^{j\omega Y}]$ (141)
$\displaystyle=-ja\phi_{Y}^{\prime}(\omega),$ (142)

where $\phi_{Y}(\omega)$ is the characteristic function of $Y$. Next, note
that

$\displaystyle\mathbb{E}[X\mathrm{e}^{j\omega Y}]$
$\displaystyle=\mathbb{E}[X\mathbb{E}[\mathrm{e}^{j\omega Y}|X]]$ (143)
$\displaystyle=\mathbb{E}[X\mathrm{e}^{j\omega
X}\mathbb{E}[\mathrm{e}^{j\omega Z}|X]]$ (144)
$\displaystyle=\mathbb{E}[X\mathrm{e}^{j\omega
X}]\mathrm{e}^{-\frac{\omega^{2}}{2}}$ (145)
$\displaystyle=-j\phi_{X}^{\prime}(\omega)\mathrm{e}^{-\frac{\omega^{2}}{2}}$
(146)
$\displaystyle=-j\left(\frac{\mathrm{d}}{\mathrm{d}\omega}\phi_{X}(\omega)\mathrm{e}^{-\frac{\omega^{2}}{2}}+\omega\phi_{X}(\omega)\mathrm{e}^{-\frac{\omega^{2}}{2}}\right)$
(147)
$\displaystyle=-j\left(\phi_{Y}^{\prime}(\omega)+\omega\phi_{Y}(\omega)\right),$
(148)

where in (145) we have used the fact that $Z$ is standard normal independent
of $X$ and, hence, $\mathbb{E}[\mathrm{e}^{j\omega
Z}|X]=\mathrm{e}^{-\frac{\omega^{2}}{2}}$; and in (148) we have used that
$\phi_{Y}(\omega)=\phi_{X}(\omega)\mathrm{e}^{-\frac{\omega^{2}}{2}}$

Now combining (142) and (148) we arrive at

$\displaystyle(1-a)\phi_{Y}^{\prime}(\omega)+\omega\phi_{Y}(\omega)=0,\forall\omega$
(149)

Clearly, the only solution to the above differential equation is Gaussian with
variance $\frac{1}{1-a}$. This concludes the proof.

##  Appendix C Proof of Theorem 3

The direct part of the theorem follows since the conditions that
$X|Y=y\sim\mathcal{N}(\frac{\sigma^{2}_{X}}{1+\sigma_{X}^{2}}y,\frac{\sigma^{2}_{X}}{1+\sigma_{X}^{2}})$
and is symmetric around the mean $\frac{\sigma^{2}_{X}}{1+\sigma_{X}^{2}}y$.

For the converse part, note that if $X|Y=y$ for all $y\in S$, then for all
$y\in S$, we have that the third conditional moment666 It can be shown that
$X|Y=y$ is always sub-Gaussian [38]. Therefore, all moments exist.  is given
by

$\displaystyle 0$ $\displaystyle=\mathbb{E}[(X-\mathbb{E}[X|Y])^{3}|Y=y]$
(150) $\displaystyle=\kappa_{X|Y=y}(3),$ (151)

where $\kappa_{X|Y=y}(3)$ denotes the third conditional cumulant. Now, since
$y\mapsto\kappa_{X|Y=y}(3)$ is a real-analytic function [35, Lem. 2] and the
set $S$ has an accumulation point by the identity theorem [39], we have that

$0=\kappa_{X|Y=y}(3),\forall y\in S\Longrightarrow 0=\kappa_{X|Y=y}(3),\forall
y\in\mathbb{R}.$ (152)

Using the result in [35, eq. (55)], the conditional cumulant can be expressed
as

$\kappa_{X|Y=y}(3)=\frac{\mathrm{d}^{3}}{\mathrm{d}y^{3}}\log f_{Y}(y),\forall
y\in\mathbb{R}$ (153)

where $f_{Y}$ is the pdf of $Y$. Therefore, combining (152) and (153), we have
that

$\frac{\mathrm{d}^{3}}{\mathrm{d}y^{3}}\log f_{Y}(y)=0,\forall
y\in\mathbb{R},$ (154)

which has a unique form of a solution given by

$f_{Y}(y)=\mathrm{e}^{ay^{2}+by+c},y\in\mathbb{R},$ (155)

for some constants $a,b,c$. Now using the standard characteristic function
argument, the only distribution on $X$ that induces an output pdf of the form
in (155) is Gaussian. This concludes the proof.

##  Appendix D Proof of Theorem 14

Now consider the case of general $p\in[1,\infty)$. Since this is an odd
function, the Fourier transform can be calculated by integrating against
$i\sin(wx)$ on $(0,\infty)$, so we are led to the definition:

$\displaystyle
f_{p}(w):=\int_{0}^{\infty}x^{p-1}\mathrm{e}^{-x^{2}}\sin(wx)\mathrm{d}x.$
(156)

From the previous analysis, we see that the existence of non-Gaussian prior is
equivalent to the existence of nonzero roots of $f_{p}$. We first observe that
$f_{p}$ is characterized by an ordinary differential equation:

######  Lemma 15.

For any $p\in(0,\infty)$, $f_{p}$ is a smooth function, and

$\displaystyle 2f_{p}^{\prime\prime}(w)+(p-1)f_{p}(w)+(wf_{p}(w))^{\prime}=0$
(157)

for all $w\in\mathbb{R}$.

###### Proof.

We have

$\displaystyle(wf_{p}(w))^{\prime}$
$\displaystyle=\int_{0}^{\infty}x^{p-1}\mathrm{e}^{-x^{2}}(w\sin(wx))^{\prime}\mathrm{d}x$
(158)
$\displaystyle=\int_{0}^{\infty}x^{p-1}\mathrm{e}^{-x^{2}}(\sin(wx)+xw\cos(wx))\mathrm{d}x,$
(159)

and using integration by parts,

$\displaystyle\int_{0}^{\infty}x^{p}\mathrm{e}^{-x^{2}}w\cos(wx)\mathrm{d}x$
$\displaystyle=-\int_{0}^{\infty}d(x^{p}\mathrm{e}^{-x^{2}})\sin(wx).$ (160)

Then (157) easily follows. ∎

######  Lemma 16.

For $p\in(2k,2k+2]$, where $k\in\\{0,1,2,\dots\\}$, $f_{p}(w)$ has $k$ roots
on $(0,\infty)$.

###### Proof.

Note that $f_{p}(w)$ is a smooth, odd function that vanishes at infinity. Now
suppose $p\in(0,2]$, and note that for $m\in\\{0,2,4,\dots,\\}$ the $m$-th
derivative $f^{(m)}_{p}(w)=f_{p+m}(w)$. We argue by induction, with the
following induction hypotheses for $m=1,2,\dots$:

  * •

$f_{p}^{(m)}$ has $m+1$ roots on $(-\infty,\infty)$;

  * •

at these $m+1$ roots, $f_{p}^{(m+1)}$ are nonzero and their signs are
alternating.

The second hypothesis actually follows from the first: Using (157) we obtain

$\displaystyle 2f_{p}^{(m+2)}(w)+(m+p)f^{(m)}(w)+wf_{p}^{(m+1)}(w)=0.$ (161)

So if $f_{p}^{(m)}(w_{0})=f_{p}^{(m+1)}(w_{0})$ at some $w_{0}$, we obtain
$f_{p}^{(m+2)}(w_{0})=0$ as well, and the ODE gives the trivial solution
$f_{p}^{(m)}=0$, a contradiction. Therefore $f_{p}^{(m+1)}$ must be nonzero at
the roots of $f_{p}^{(m)}$, and by continuity their signs must be alternating
(i.e., signs of $f_{p}^{(m+1)}$ must be different at consecutive roots of
$f_{p}^{(m)}$).

If the induction hypothesis is true for $M$, then the $M+1$ roots partition
$\mathbb{R}$ into $M+2$ intervals, so that by Rolle’s theorem, there is at
least root for $f_{p}^{(M+1)}$ on the interior of each of these intervals.
There cannot be more roots: Suppose otherwise, that $a_{1}$ and $a_{2}$ are
two consecutive roots of $f_{p}^{(M)}$, and $b_{1},b_{2}\in(a_{1},a_{2})$
($b_{1}<b_{2}$) are two roots of $f_{p}^{(M+1)}$. Then $f_{p}^{(M)}$ does not
change sign on $(a_{1},a_{2})$, and we can assume without loss of generality
that the sign is positive on that interval. From (161) we see that
$f_{p}^{(M+2)}(b_{1}),f_{p}^{(M+2)}(b_{2})<0$. So for sufficiently small
$\epsilon>0$ we have $f_{p}^{(M+1)}(b_{1}+\epsilon)<0$ and
$f_{p}^{(M+1)}(b_{2}-\epsilon)>0$, and by continuity there exists
$b_{3}\in(b_{1},b_{2})$ such that $f_{p}^{(M+1)}(b_{3})=0$ and
$f_{p}^{(M+2)}(b_{3})\geq 0$. Then (161) does not hold at $b_{3}$, a
contradiction. Similar arguments can be applied when $a_{1}=-\infty$ or
$a_{2}=\infty$. Therefore the induction hypotheses are true for all
$m\in\\{0,1,2,\\}$, and in particular the case of even $m$ implies the lemma,
noting that $f_{p+m}$ is an odd function vanishing at 0. ∎

This implies that for $p\in(2,\infty)$, the existence of nonzero roots of
$f_{p}$, which yield the desired non-Gaussian priors.

######  Lemma 17.

Suppose that $p\in(0,2)$. There exists a constant $c_{p}\neq 0$ such that

$\displaystyle f_{p}(w)=c_{p}\,{\rm
p.v.}\int_{\mathbb{R}}t^{-p}\mathrm{e}^{-(w-t)^{2}/4}\mathrm{d}t.$ (162)

Note that since $\mathrm{e}^{-(w-t)^{2}/4}$ is smooth at $t=0$ for every $w$,
the integral is well-defined in the sense of Cauchy’s principal value. As a
consequence, whenever $p\in(0,2]$, $f_{p}(w)=0$ only for $w=0$.

###### Proof.

If $p\in(1,2)$, we can prove (162) using the fact that the Fourier transform
of $|x|^{p-2}$ is $|w|^{1-p}$ for $p\in(1,2)$ [40, Section 5.9], which implies
that the Fourier transform of $|x|^{p-1}\mathsf{sign}(x)$ is
$|w|^{-p}\mathsf{sign}(w)$ (all up to multiplicative constants). However, this
argument does not directly extend to the case of $p\in(0,1]$, since
$|x|^{p-2}$ will then no longer be a tempered distribution (the singularity at
0 leads to divergent integral).

Instead, here we prove (162) by showing that $g(w)$, defined as the integral
on the right side of (162), must satisfy (157), and so $f_{p}$ and $g$ are two
solutions to the same second-order ODE with $f_{p}(0)=g(0)$ and
$f_{p}^{\prime}(0),g^{\prime}(0)\neq 0$. Indeed, we have

$\displaystyle g^{\prime\prime}(w)={\rm p.v.}\int
t^{-p}\left[-\frac{1}{2}+\left(\frac{w-t}{2}\right)^{2}\right]\mathrm{e}^{-(w-t)^{2}/4}\mathrm{d}t,$
(163)

and

$\displaystyle(wg(w))^{\prime}={\rm p.v.}\int
t^{-p}\left[1-\frac{w(w-t)}{2}\right]\mathrm{e}^{-(w-t)^{2}/4}\mathrm{d}t.$
(164)

With some arrangements, we see the ODE is equivalent to

$\displaystyle{\rm p.v.}\int
t^{-p}\left[a-\frac{t(w-t)}{2}\right]\mathrm{e}^{-(w-t)^{2}/4}\mathrm{d}t=0.$
(165)

This is true since using integration by parts,

$\displaystyle\int t^{-p+1}\mathrm{d}\mathrm{e}^{-(w-t)^{2}/4}$
$\displaystyle=\lim_{\epsilon\downarrow
0}\left(\left.t^{-p+1}\mathrm{e}^{-(w-t)^{2}/4}\right|_{\epsilon}^{\infty}+\left.t^{-p+1}\mathrm{e}^{-(w-t)^{2}/4}\right|_{-\infty}^{-\epsilon}\right)+(p-1){\rm
p.v.}\int t^{-p}\mathrm{e}^{-(w-t)^{2}/4}$ (166) $\displaystyle=(p-1){\rm
p.v.}\int t^{-p}\mathrm{e}^{-(w-t)^{2}/4}.$ (167)

Now that (162) is verified, it is easy to see from this representation that
$w=0$ is the only root of $f_{p}$, assuming $p\in(0,2)$. On the other hand,
$f_{2}(w)$ can be directly calculated as a linear function times a Gaussian
function, so $w=0$ is still the only root. ∎

#### Proof of Theorem 14:

For $p\in[1,2]$, the claim follows since by Lemma 16, $f_{p}$ only has a root
at 0, and the same proof for the median estimator applies (once reduced to the
case of point-supported distributions, we only used $f_{p}^{\prime}(0)\neq 0$
to conclude that the distribution is a Dirac delta).