\section{Introduction} \label{sec1}

In this paper, we consider the Schr\"odinger operator $e^{i \Delta}$
which is naturally arose from the Cauchy problem for the free Schr\"odinger equation
\begin{equation*}
\left\{
\begin{array}{ll}
i\partial_t u + \Delta u = 0, & t \in \mathbb{R},\ x \in \mathbb{R}^n, \\
u( 0, x )=u_0 (x),  &  x \in  \mathbb{R}^n.
\end{array}
\right.
\end{equation*}
Here, the differential operator $\Delta$ is the usual Laplacian.
The Schr\"odinger operator is a special case of Fourier multipliers
and denoted by
\begin{equation} \label{sch op}
e^{i \Delta} f (x) = (2\pi)^{-n} \int_{ \mathbb{R}^n } e^{ i x \cdot \xi } e^{ - i | \xi |^2 } \widehat f (\xi) d \xi.
\end{equation}

Wiener amalgam spaces $W_{p,q}^s$ are variation of modulation spaces $M_{p,q}^s$
which were introduced  from the view point of time-frequency analysis
(see Feichtinger \cite{feichtinger 1983} and Gr\"ochenig \cite{grochenig 2001}).
The essence of modulation and Wiener amalgam spaces is
to measure integrability (or decay property) of functions
with respect to their space variable and frequency variable simultaneously.
On the other hand, in $L^p$-Sobolev spaces $L^p_s$ and Besov spaces $B^s_{p,q}$,
the space and frequency variables of functions must be considered separately.
This idea is a major difference among these spaces.
The exact definitions and basic properties of modulation and Wiener amalgam spaces
will be given in Section \ref{sec2.2}.
In the following, if $s = 0$ we simply write $ M_{p,q} $ and $ W_{p,q} $
instead of $ M_{p,q}^s $ and $ W_{p,q}^s $, respectively.

The boundedness problems of Fourier multipliers have been studied by many researchers.
In particular, we here focus on the unimodular Fourier multiplier
$e^{- i |D|^\alpha}$ for $\alpha \geq 0$,
which is denoted by the expression (\ref{sch op})
whose phase function $| \xi |^2$ is replaced by $| \xi |^\alpha$.
In \cite{hormander 1960}, H\"ormander studied
that $e^{- i |D|^2}$ (i.e., $e^{i\Delta}$) is bounded on $L^p$ if and only if $p = 2$.
After that, it was proved that
for $1 < p <\infty$, $e^{- i |D|^\alpha}$ is bounded from $ L^p_s $ to $L^p$
if and only if $s \geq \alpha n | 1/p - 1/2 | $ (see, e.g., Miyachi \cite{miyachi 1980}).
Next, we shall consider the boundedness results on modulation spaces.
On modulation spaces, Gr\"ochenig and Heil \cite{grochenig heil 1999} invented
that $e^{- i |D|^2}$ is bounded on $M_{p,q}$ for all $1 \leq p,q \leq \infty$
(see also Toft \cite{toft 2004} and Wang, Zhao and Guo \cite{wang zhao guo 2006}).
Then, the boundedness of $e^{-i |D|^\alpha}$ on modulation spaces
was studied for $0 \leq \alpha \leq 2$
by B\'enyi, Gr\"ochenig, Okoudjou and Rogers \cite{benyi grochenig okoudjou rogers 2007},
and for $\alpha > 2$
by Miyachi, Nicola, Rivetti, Tabacco and Tomita \cite{miyachi nicola rivetti tabacco tomita 2009}.
Optimality of these results can be found in, e.g.,
\cite[Theorem 1.2]{miyachi nicola rivetti tabacco tomita 2009}
and \cite[Remark 3.4]{tomita 2010}.
Extracting the Schr\"odinger operator case, namely, $\alpha=2$, we have the following:

\begin{theoremA}
Let $s \in \mathbb{R}$ and $1 \leq p,q \leq \infty$. Then, $e^{ i \Delta}$ is bounded from $M^s_{p,q}$ to $ M_{p,q} $ if and only if $s \geq 0$.
\end{theoremA}

Comparing the results on $L^p$-Sobolev and modulation spaces,
we see that the Schr\"odinger operator is bounded on modulation spaces without loss of regularity,
while on $L^p$-Sobolev spaces loss of the order up to $2n | 1/p - 1/2 | $ occurs.
This is one of advantages in using modulation spaces.

The objective of this paper is to study the boundedness problem of the Schr\"odinger operator $e^{ i \Delta}$
on variation of modulation spaces, Wiener amalgam spaces.
In \cite[Theorem 1.1]{cunanan sugimoto 2014}, Cunanan and Sugimoto proved that
for $1 \leq p,q \leq \infty$, $e^{ i \Delta}$ is bounded from $W^s_{p,q}$ to $W_{p,q} $ if $s > n | 1/p - 1/q |$.
Conversely, in Cordero and Nicola \cite[Proposition 6.1]{cordero nicola 2010},
it was shown that
$e^{ i \Delta}$ is bounded from $W^s_{p,q}$ to $W_{p,q} $ only if $s \geq n | 1/p - 1/q |$.
Moreover, in \cite[Proposition 6.1]{cordero nicola 2010},
it was also stated that if $p = \infty$ and $q < \infty$,
the necessary condition for the boundedness holds with the strict inequality,
namely, $e^{ i \Delta}$ is bounded from $W^s_{\infty,q}$ to $W_{\infty,q} $ only if $s > n/q $.
Therefore, except for the case $p = \infty$ and $q < \infty$, there is a gap
between the sufficient and necessary conditions for this boundedness problem.
That is, the critical case $s = n | 1/p - 1/q | $ is not included in the sufficient condition,
although it is included in the necessary condition.
The goal of this paper is to determine whether this critical case is needed or not.
The exact answer is provided by the following.

\begin{theorem} \label{main thm}
Let $s \in \mathbb{R}$ and $1 \leq p,q \leq \infty$.
\begin{enumerate}
\item For $p = q$, $e^{i\Delta}$ is bounded from $W^s_{p,q}$ to $W_{p,q} $ if and only if $s \geq 0$.
\item For $p \neq q$, $e^{i\Delta}$ is bounded from $W^s_{p,q}$ to $W_{p,q} $  if and only if $s > n | 1/p - 1/q |$.
\end{enumerate}
\end{theorem}

Theorem \ref{main thm} mentions that unlike modulation spaces,
$e^{i \Delta}$ is not bounded on $W_{p,q} $ if $p \neq q$
(Wiener amalgam spaces coincide with modulation spaces in the case $p = q$).
However, the boundedness of unimodular Fourier multiplier $e^{-i |D|^\alpha}$ on $W_{p,q}$
for $0 \leq \alpha \leq 1$ was given
by Cunanan and Sugimoto \cite[Corollary 2.1]{cunanan sugimoto 2014}.
Since $e^{-i |D|^\alpha} = e^{i \Delta}$ if $\alpha = 2$,
we have yet to determine an upper bound of $\alpha$
to obtain the boundedness of $e^{- i |D|^\alpha}$ on $W_{p,q} $.

We end this section with mentioning the plan of this paper.
In Section \ref{sec2}, we will state basic notations which will be used throughout this paper,
and then introduce the definitions and some basic properties of modulation and Wiener amalgam spaces.
After stating and proving some lemmas needed to show our main theorem in Section \ref{sec3},
we will actually prove it in Section \ref{sec4}.

\section{Preliminaries}\label{sec2}

\subsection{Basic notations} \label{sec2.1}
We collect notations which will be used throughout this paper.
We denote by $\mathbb{R}$ and $\mathbb{Z}$
the sets of reals and integers, respectively.
The notation $a \lesssim b$ means $a \leq C b$ with a constant $C > 0$ which may be different in each occasion, and $a \sim b $ means $a \lesssim b$ and $b \lesssim a$. We write $\langle x \rangle = (1 + | x |^2)^{1/2}$.

We denote the Schwartz space of rapidly decreasing smooth functions
on $\mathbb{R}^n$ by $\mathcal{S} = \mathcal{S} (\mathbb{R}^n)$ and its dual,
the space of tempered distributions, by $\mathcal{S}^\prime = \mathcal{S}^\prime(\mathbb{R}^n)$.
The Fourier transform and the inverse Fourier transform of $f \in \mathcal{S}(\mathbb{R}^n)$ are given by
\begin{equation*}
\mathcal{F} f  (\xi) = \widehat {f} (\xi) = \int_{\mathbb{R}^n}  e^{-i \xi \cdot x } f(x) d x
\quad\textrm{and}\quad
\mathcal{F}^{-1} f (x) = (2\pi)^{-n} \int_{\mathbb{R}^n}  e^{i x \cdot \xi } f( \xi ) d\xi,
\end{equation*}
respectively.
For $g \in \mathcal{S}^\prime (\mathbb{R}^n)$,
the Fourier multiplier is denoted by
$g(D) f = \mathcal{F}^{-1} \left[g \cdot \mathcal{F} f \right]$,
and for $s \in \mathbb{R}$, the Bessel potential by
$(I - \Delta )^{s/2} f = \mathcal{F}^{-1} [ \langle \cdot \rangle^s \cdot \mathcal{F}f ]$
for $f \in \mathcal{S}(\mathbb{R}^n)$.

We will use some function spaces.
The Lebesgue space $L^p = L^p(\mathbb{R}^n) $ is equipped with the norm
\begin{equation*}
\| f \|_{L^p} = \left( \int_{\mathbb{R}^n} \big| f(x) \big|^p dx \right)^{1/p}
\end{equation*}
for $1 \leq p < \infty$. If $p = \infty$, $\| f \|_{\infty} = \textrm{ess.}\sup_{x\in\mathbb{R}^n} |f(x)|$.
Moreover, we denote the $L^p$-Sobolev space (or the Bessel potential space) $L^p_s$
by $L^p_s (\mathbb{R}^n) = \{ f \in \mathcal{S}^\prime (\mathbb{R}^n) : \| (I-\Delta)^{s/2} f \|_{L^p} < \infty \}$
for $1 < p < \infty$ and $s\in\mathbb{R}$.
For $1 \leq q \leq \infty$, we denote by $\ell^q$ the set of all complex number sequences
$\{ a_k \}_{ k \in \mathbb{Z}^n }$ such that
\begin{equation*}
 \| a_k \|_{ \ell^q } = \left( \sum_{ k \in \mathbb{Z}^n }  | a_k  |^q \right)^{ 1 / q } < \infty,
\end{equation*}
with the usual modification for $ q = \infty$.
For the sake of simplicity, we write $ \| a_k  \|_{ \ell^q } $
instead of the more correct notation $ \| \{ a_k \}_{ k\in\mathbb{Z}^n } \|_{ \ell^q } $.

\subsection{Modulation and Wiener amalgam spaces} \label{sec2.2}
We give the definitions of modulation and Wiener amalgam spaces.
They are based on Feichtinger \cite{feichtinger 1983} and Gr\"ochenig \cite{grochenig 2001}.
We fix a function (called a window function) $g \in \mathcal{S} (\mathbb{R}^n) \setminus \{0\}$
and denote the short-time Fourier transform of $f \in \mathcal{S}^\prime (\mathbb{R}^n) $ with respect to $g$ by
\begin{equation*}
V_g f (x,\xi) = \int_{\mathbb{R}^n} e^{ - i \xi \cdot t } \ \overline {g (t-x)} f(t) d t.
\end{equation*}
We will sometimes write $V_g [ f ] $ when the function $f$ is complicated.
Now, for $s \in \mathbb{R}$ and $1 \leq p,q \leq \infty$, the modulation space $M_{ p , q }^s$ is denoted by
\begin{equation*}
M_{p,q}^s (\mathbb{R}^n)
=
\left\{ f\in\mathcal{S}^\prime(\mathbb{R}^n) : \left\| f \right\|_{M_{p,q}^s} = \left\| \left\| \langle \xi \rangle^s V_g f (x,\xi) \right\|_{L^p(\mathbb{R}^n_x)} \right\|_{L^q(\mathbb{R}^n_\xi)} < +\infty \right\},
\end{equation*}
and the Wiener amalgam space $W_{ p , q }^s$ is denoted by
\begin{equation*}
W_{p,q}^s (\mathbb{R}^n)
=
\left\{ f\in\mathcal{S}^\prime(\mathbb{R}^n) : \left\| f \right\|_{W_{p,q}^s} = \left\| \left\| \langle \xi \rangle^s V_g f (x,\xi) \right\|_{L^q(\mathbb{R}^n_\xi)} \right\|_{L^p(\mathbb{R}^n_x)} < +\infty \right\}.
\end{equation*}
These definitions are independent of the choices of the window function $g$.
From the definitions, we see that $M_{p,p}^s = W_{p,p}^s $.
We also remark that $M_{2,2}^s = W_{2,2}^s = L^2_s $.
In the following, if $s = 0$ we will simply write $ M_{p,q} $ and $ W_{p,q} $
instead of $ M_{p,q}^s $ and $ W_{p,q}^s $, respectively.

We write $ X_{p,q}^s $ instead of $ M_{p,q}^s $ or $ W_{p,q}^s $.
We note that $X_{p,q}^s$ are Banach spaces
and $\mathcal{S} \subset X_{p,q}^s \subset \mathcal{S}^\prime$.
In particular, $\mathcal{S}$ is dense in $X_{p,q}^s $ if $1 \leq p,q < \infty$.
For $1 \leq p,q < \infty$,
the dual space of $ X_{p,q}^s $ can be seen as $\big( X_{p,q}^s \big)^\prime =  X_{p^\prime , q^\prime  }^{-s} $.
Moreover, we have the following complex interpolation theorem.
If $0 < \theta < 1$, $s = (1-\theta)s_1 + \theta s_2$, $ 1/p= (1-\theta)/p_1 + \theta/p_2 $ and $ 1/q= (1-\theta)/q_1 + \theta/q_2$,
we have $\big( X_{p_1,q_1}^{s_1},X_{p_2,q_2}^{s_2} \big)_\theta = X_{p,q}^{s}$.

We finally present the basic inclusion relations and the lifting property.

\begin{proposition} \label{basic emb}
Let $s_1, s_2 \in \mathbb{R}$ and $1 \leq p, p_1, p_2, q_1, q_2 \leq \infty$.
\begin{enumerate}
\item $X_{p_1,q_1}^{s_1} \hookrightarrow X_{p_2,q_2}^{s_2}$ if $p_1 \leq p_2$, $q_1 \leq q_2$ and $s_1 \geq s_2$.
\item $X_{p,q_1}^{s_1} \hookrightarrow X_{p,q_2}^{s_2} $ if $q_1 > q_2$ and $s_1 - s_2 > n ( 1 / q_2 - 1/q_1 )$.
\end{enumerate}
\end{proposition}

\begin{proposition} \label{lift op}
Let $s,t\in\mathbb{R}$ and $1 \leq p,q \leq \infty$.
Then, $(I-\Delta)^{t/2}$ maps $ X_{p,q}^s $ isomorphically onto $X_{p,q}^{s-t}$,
and $\left\| (I-\Delta)^{t/2} f \right\|_{ X_{p,q}^{s-t} } \sim \left\| f \right\|_{ X_{p,q}^s }$.
\end{proposition}

\section{Lemma}\label{sec3}

In this section, we state a key lemma and its proof,
which will be used for the proof of the ``ONLY IF'' part of Theorem \ref{main thm} (2).

\begin{lemma} \label{sequence}
Let $s \in \mathbb{R}$ and $1 \leq p,q < \infty$.
If $e^{ i \Delta}$ or $e^{ - i \Delta}$ is bounded from $W^s_{p,q}$ to $W_{p,q}$, then
\begin{equation} \label{seq ck}
\left( \sum_{k\in\mathbb{Z}^n}  | c_k |^p \right)^{1/p}
\lesssim \left( \sum_{k\in\mathbb{Z}^n} \langle k \rangle^{sq} | c_k |^q \right)^{1/q}
\end{equation}
holds for all finitely supported sequences $\{ c_k \}_{k\in\mathbb{Z}^n}$
(that is, $c_k = 0$ except for a finite number of k's).
\end{lemma}

\begin{proof} [\bf Proof of Lemma \ref{sequence}]
Before beginning with the proof, we give the following notations which will be used here:
\begin{align*}
\| f \|_{ M_{p,q}^{(s_1, s_2)} }
&=
\left\|
	\left\| \langle x \rangle^{s_1} \langle \xi \rangle^{s_2} V_g f (x,\xi)
	\right\|_{L^p (\mathbb{R}^n_x)}
\right\|_{L^q (\mathbb{R}^n_\xi)} ;
\\
\| f \|_{ W_{p,q}^{(s_1, s_2)} }
&=
\left\|
	\left\| \langle x \rangle^{s_1} \langle \xi \rangle^{s_2} V_g f (x,\xi)
	\right\|_{L^q (\mathbb{R}^n_\xi)}
\right\|_{L^p (\mathbb{R}^n_x)}.
\end{align*}
Note that $\| f \|_{ M_{p,q}^s } = \| f \|_{ M_{p,q}^{(0, s)} } $
and $\| f \|_{ W_{p,q}^s } = \| f \|_{ W_{p,q}^{(0, s)} }$.
From the fact $| V_g f (x,\xi) | = (2\pi)^{-n} | V_{\widehat g} \widehat f (\xi,-x) |$
(see \cite[Section 2.2]{grochenig heil 1999} for the detail calculation),
$ \| f \|_{ W_{p,q}^{(s_1, s_2)} } \sim \| \widehat f \|_{ M_{q,p}^{(s_2, s_1)} } $ for $1 \leq p,q \leq \infty$.
Hence, the assumption $\| e^{ \pm i \Delta} f \|_{ W_{p,q} } \lesssim \| f \|_{ W_{p,q}^{s} } $
is equivalent to the inequality
\begin{equation} \label{equiv ass}
\left\| e^{ \mp i | \cdot |^2 } \widehat f \right\|_{ M_{q,p}^{(0, 0)} }
\lesssim \left\| \widehat f \right\|_{ M_{q,p}^{(s, 0)} } .
\end{equation}
In the following statements, we will consider (\ref{equiv ass}) and write $f$ instead of $\widehat f$ for the sake of simplicity.

\noindent{\bf Step 1:}
We first consider the left hand side of (\ref{equiv ass}).
We compute the short-time Fourier transform of $e^{ \pm i | \cdot |^2 } f$.
\begin{align*}
\left| V_g [e^{ \pm i | \cdot |^2 } f] (x,\xi) \right|
&=
\left|
	\int_{ \mathbb{R}^n } e^{-i \xi \cdot t }
	\
	\overline {g ( t - x )} \cdot e^{ \pm i | t |^2 } f ( t ) dt
\right|
\\
&=
\left|
	\int_{ \mathbb{R}^n } e^{-i (\xi \mp 2x ) \cdot t }
	\
	\overline {g ( t - x )} \cdot e^{ \pm i | t - x |^2 } f ( t ) dt
\right|
\\
&=
\left| V_{g \cdot e^{ \mp i | \cdot |^2 }} f (x, \xi \mp 2x ) \right| ,
\end{align*}
where it should be remarked that
$g \cdot e^{ \mp i | \cdot |^2 } \in \mathcal{S}(\mathbb{R}^n) \setminus \{ 0 \}$
since $e^{ \mp i | \cdot |^2 } $ and all their derivatives are $C^\infty$ slowly increasing functions.
Since the norm of modulation spaces is independent of the choice of window functions,
\begin{align}
\label{equiv scho mod}
\begin{split}
\left\| e^{ \pm i | \cdot |^2 } f \right\|_{ M_{q,p}^{(0, 0)} }
&\sim
\left\|
	\left\| V_{\psi \cdot e^{ \pm i | \cdot |^2 }}
		\left[ e^{ \pm i | \cdot |^2 } f
		\right]( x, \xi )
	\right\|_{L^q (\mathbb{R}^n_x)}
\right\|_{L^p (\mathbb{R}^n_\xi)}
\\
&=
\left\| \left\| V_\psi f ( x, \xi \mp 2x ) \right\|_{L^q (\mathbb{R}^n_x)} \right\|_{L^p (\mathbb{R}^n_\xi)}
\end{split}
\end{align}
for any $\psi \in \mathcal{S}(\mathbb{R}^n) \setminus \{ 0 \}$.

We choose $\varphi  \in \mathcal{S} (\mathbb{R}^n)$ satisfying that
\begin{equation*}
\supp \varphi \subset [ - 1/8, 1/8 ]^n
\quad\textrm{and}\quad
| \widehat \varphi | \geq c >0 \textrm{ on } [ - 3/8, 3/8 ]^n
\end{equation*}
for some positive constant $c$, and $\psi \in \mathcal{S} (\mathbb{R}^n)$ satisfying that
\begin{equation*}
\supp \psi \subset [ - 3/8, 3/8 ]^n
\quad\textrm{and}\quad
\psi \equiv 1 \textrm{ on } [ -1/4, 1/4 ]^n
\end{equation*}
(see \cite[Lemma 4.3]{kobayashi miyachi tomita 2009} for existence of such functions $\varphi$ and $\psi$). We put
\begin{equation*}
f(t) = \sum_{\ell\in\mathbb{Z}^n}  c_\ell \cdot \varphi \left( t - \ell \right)
\end{equation*}
for a finitely supported sequence $\{c_\ell\}_{\ell\in\mathbb{Z}^n}$.

Under the conditions above,
we first consider the inner $L^q$ norm in the last quantity in (\ref{equiv scho mod}) and have
\begin{equation} \label{integ qk}
\left\| V_\psi f ( x, \xi \mp 2x ) \right\|_{L^q (\mathbb{R}^n_x)}
\geq
\left( \sum_{ k \in \mathbb{Z}^n } \int_{ Q_k }
	\left| \int_{ \mathbb{R}^n } e^{-i (\xi \mp 2x) \cdot t}
	\
	\overline{\psi (t-x)} \sum_{ \ell \in\mathbb{Z}^n } c_\ell
		\cdot \varphi (t - \ell) dt
	\right|^q dx
\right)^{1/q},
\end{equation}
where we set $ Q_k = k + [-1/8, 1/8]^n $. Considering the supports of the functions in the integral of (\ref{integ qk}), we have for all $x \in Q_k$
\begin{align*}
\supp \psi (\cdot-x) &\subset x + [ - 3/8, 3/8 ]^n \subset k + [ - 1/2, 1/2 ]^n ; \\
\supp \varphi (\cdot - \ell) &\subset \ell + [ - 1/8, 1/8 ]^n,
\end{align*}
so that we see that $\supp \psi (\cdot-x) \cap \supp \varphi (\cdot - \ell) = \varnothing$ if $k \neq \ell$ for all $x \in Q_k$. Hence, the right hand side of (\ref{integ qk}) is equal to
\begin{equation}
\label{integ qk 2}
\left( \sum_{ k \in \mathbb{Z}^n } |c_k |^q \int_{ Q_k }
	\left| \int_{ \mathbb{R}^n } e^{-i (\xi \mp 2x) \cdot t} \ \overline{\psi (t-x)} \cdot \varphi (t - k) dt
	\right|^q dx
\right)^{1/q}.
\end{equation}
Moreover, we realize that $\psi (\cdot-x) \equiv 1 $ on $\supp \varphi (\cdot - k )$,
since we have the fact that $\supp \varphi (\cdot - k ) \subset k + [-1/8,1/8]^n \subset x + [-1/4,1/4]^n$
which is given from the equivalence $x \in Q_k \Leftrightarrow k \in Q_x$.
Then, we have
\begin{align*}
(\ref{integ qk 2})
&=
\left( \sum_{ k \in \mathbb{Z}^n } |c_k |^q \int_{ Q_k }
	\left| \int_{ \mathbb{R}^n } e^{-i (\xi \mp 2x) \cdot t } \varphi (t - k) dt
	\right|^q dx
\right)^{1/q} \\
&=
\left( \sum_{ k \in \mathbb{Z}^n } |c_k |^q \int_{ Q_k }
	\left| \widehat \varphi (\xi \mp 2x)
	\right|^q dx
\right)^{1/q}.
\end{align*}
Substituting this conclusion into the last quantity of (\ref{equiv scho mod}), we have
\begin{align}
\label{integ qk 3}
\begin{split}
\left\|
	\left\|
		V_\psi f ( x, \xi \mp 2x )
	\right\|_{L^q (\mathbb{R}^n_x)}
\right\|_{L^p (\mathbb{R}^n_\xi)}
&\geq
\left\|
	\left( \sum_{ k \in \mathbb{Z}^n } |c_k |^q \int_{ Q_k }
		\left|
		\widehat \varphi (\xi \mp 2x)
		\right|^q dx
	\right)^{1/q}
\right\|_{L^p (\mathbb{R}^n_\xi)}
\\
&\geq
\left( \sum_{ m \in \mathbb{Z}^n} \int_{ Q_{\pm 2m } }
	\left( \sum_{ k \in \mathbb{Z}^n } |c_k |^q \int_{ Q_k }
		\left|
		\widehat \varphi (\xi \mp 2x)
		\right|^q dx
	\right)^{p/q} d\xi
\right)^{1/p}
\\
&\geq
\left( \sum_{ m \in \mathbb{Z}^n} |c_m |^p \int_{ Q_{\pm 2m } }
	\left( \int_{ Q_m }
		\left| \widehat \varphi (\xi \mp 2x)
		\right|^q dx
	\right)^{p/q} d\xi
\right)^{1/p},
\end{split}
\end{align}
where we set $Q_{\pm 2m } = \pm 2m + [-1/8,1/8]^n $.
The assumption $| \widehat \varphi | \geq c >0 \textrm{ on } [ - 3/8, 3/8 ]^n$
and the fact $\xi \mp 2x \in ( \pm 2m + [-1/8,1/8]^n ) \mp 2 (m + [-1/8,1/8]^n) \subset [ - 3/8, 3/8 ]^n$
yield that the last expression in (\ref{integ qk 3}) is estimated from below by
\begin{align*}
\left( \sum_{ m \in \mathbb{Z}^n} |c_m |^p \int_{ Q_{\pm 2m } } \left( \int_{ Q_m } c^q dx \right)^{p/q} d\xi \right)^{1/p},
\end{align*}
which gives
\begin{align*}
\left\| \left\| V_\psi f ( x, \xi \mp 2x ) \right\|_{L^q (\mathbb{R}^n_x)} \right\|_{L^p (\mathbb{R}^n_\xi)}
\gtrsim
\left( \sum_{ m \in \mathbb{Z}^n} |c_m |^p \right)^{1/p} .
\end{align*}
Combining this result with (\ref{equiv scho mod}), we obtain
\begin{equation} \label{conc prop 1}
\left\| e^{ \pm i | \cdot |^2 } f \right\|_{ M_{q,p}^{(0, 0)} }
\gtrsim
\left( \sum_{ m \in \mathbb{Z}^n} |c_m |^p \right)^{1/p} .
\end{equation}

\noindent{\bf Step 2:} Next, we estimate the right hand side of (\ref{equiv ass}).
The statement of this step is essentially the same as that of \cite[Theorem 12.2.4]{grochenig 2001}.
Recall that we put
\begin{equation*}
f(t) = \sum_{\ell\in\mathbb{Z}^n}  c_\ell \cdot \varphi \left( t - \ell \right)
\end{equation*}
for a finitely supported sequence $\{c_\ell\}_{\ell\in\mathbb{Z}^n}$.
We calculate the short-time Fourier transform of this function $f$ with the $x$-weight.
Using the $N$-times integration by parts with respect to the $t$-variable, we have for any $N\geq 0$
\begin{align*}
\langle x \rangle^{s}
\left| V_g f (x,\xi) \right|
&=
\langle x \rangle^{s}
\left|
	\sum_{\ell\in\mathbb{Z}^n} c_\ell \int_{ \mathbb{R}^n } e^{ - i \xi \cdot t }
	\
	\overline{g (t-x)}\cdot \varphi \left( t - \ell \right) dt
\right|
\\
&\lesssim
\langle x \rangle^{s} \langle \xi \rangle^{-N}
\sum_{\ell\in\mathbb{Z}^n} | c_\ell |
	\sum_{\substack{ \beta \leq \alpha \\ | \alpha | \leq N } }
	\int_{ \mathbb{R}^n } \left| ( \partial^{ \alpha - \beta } g ) (t-x) \right|
	\cdot
	\left| ( \partial^{ \beta } \varphi )\left( t - \ell \right) \right| dt.
\end{align*}
From the inequality
$\langle x - \ell \rangle \lesssim \langle t - x \rangle \cdot \langle t - \ell \rangle$
and the Schwarz inequality,
it follows that for any $M \geq 0$
\begin{align*}
&
\int_{ \mathbb{R}^n } \left| ( \partial^{ \alpha - \beta } g ) (t-x) \right|  \cdot  \left| ( \partial^{ \beta } \varphi )\left( t - \ell \right) \right| dt
\\
&\lesssim
\langle x - \ell \rangle^{-M}
\int_{ \mathbb{R}^n }
\langle t - x \rangle^M \left| ( \partial^{ \alpha - \beta } g ) (t-x) \right|
\cdot \langle t - \ell \rangle^{M}  \left| ( \partial^{ \beta } \varphi ) ( t - \ell ) \right| dt
\\
&\leq
\langle x - \ell \rangle^{-M}
\left\| \langle \cdot \rangle^M ( \partial^{ \alpha - \beta } g ) \right\|_{L^2}
\cdot
\left\| \langle \cdot \rangle^M ( \partial^{ \beta } \varphi ) \right\|_{L^2}
\\
&\sim
\langle x - \ell \rangle^{-M},
\end{align*}
since $g ,\varphi \in \mathcal{S}(\mathbb{R}^n)$.
Thus, by the Peetre inequality
$\langle x \rangle^s \lesssim \langle \ell \rangle^s \cdot \langle x - \ell \rangle^{ | s | } $,
we have for any $M\geq0$
\begin{align*}
\langle x \rangle^{s} \left| V_g f (x,\xi) \right|
&\lesssim
\langle x \rangle^{s} \langle \xi \rangle^{-N} \sum_{\ell\in\mathbb{Z}^n} | c_\ell | \langle x - \ell \rangle^{-M}
\\
&\lesssim
\langle \xi \rangle^{-N}\sum_{\ell\in\mathbb{Z}^n} \langle \ell \rangle^s | c_\ell | \langle x - \ell \rangle^{-M + |s|}.
\end{align*}
Substitute this estimate into the right hand side of (\ref{equiv ass}) and choose $N\geq0$ such that $N >n/p$.
Then, we have
\begin{align}
\label{seq right}
\begin{split}
\left\| f \right\|_{ M_{q,p}^{(s, 0)} }
&=
\left\|
	\left\|
		\langle x \rangle^{s} V_g f (x,\xi)
	\right\|_{L^q (\mathbb{R}^n_x)}
\right\|_{L^p (\mathbb{R}^n_\xi)}
\\
&\lesssim
\left\|
	\left\|
		\langle \xi \rangle^{-N} \sum_{\ell\in\mathbb{Z}^n}
		\langle \ell \rangle^s | c_\ell | \langle x - \ell \rangle^{-M + |s|}
	\right\|_{L^q (\mathbb{R}^n_x)}
\right\|_{L^p (\mathbb{R}^n_\xi)}
\\
&\sim
\left\|
	\sum_{\ell\in\mathbb{Z}^n} \langle \ell \rangle^s | c_\ell | \langle x - \ell \rangle^{-M + |s|}
\right\|_{L^q (\mathbb{R}^n_x)}.
\end{split}
\end{align}
Moreover, since $\mathbb{R}^n$ is decomposed by $\mathbb{R}^n = \bigcup_{m \in \mathbb{Z}^n} \widetilde Q_m $ with $ \widetilde Q_m = m + [-1/2,1/2)^n$, the last quantity in (\ref{seq right}) is expressed as
\begin{align*}
\left\{
	\sum_{m\in\mathbb{Z}^n}
	\int_{\widetilde Q_m}
	\left(
		\sum_{\ell\in\mathbb{Z}^n} \langle \ell \rangle^s | c_\ell | \langle x - \ell \rangle^{-M + |s|}
	\right)^q dx
\right\}^{1/q} .
\end{align*}
Hence, by the fact that $\langle x - \ell \rangle \sim \langle m - \ell \rangle$ for all $x \in \widetilde Q_m$,
we have
\begin{align*}
\left\| f \right\|_{ M_{q,p}^{(s, 0)} }
\lesssim
\left\{
	\sum_{m\in\mathbb{Z}^n}
	\left(
		\sum_{\ell\in\mathbb{Z}^n} \langle \ell \rangle^s | c_\ell | \langle m - \ell \rangle^{-M + |s|}
	\right)^q
\right\}^{1/q} .
\end{align*}
Choosing $M\geq0$ such that $M > n + |s|$
and using the convolution relation $\ell^q \ast \ell^1 \hookrightarrow \ell^q$ for $1 \leq q \leq \infty$,
we obtain
\begin{equation}
 \label{conc prop 2}
\left\| f \right\|_{ M_{q,p}^{(s, 0)} }
\lesssim
\left(
	\sum_{\ell\in\mathbb{Z}^n} \langle \ell \rangle^{sq} | c_\ell |^q
\right)^{1/q} .
\end{equation}

\noindent{\bf Step 3:} Combing (\ref{conc prop 1}) and (\ref{conc prop 2}) with the assumption, we have
\begin{align*}
\left( \sum_{ m \in \mathbb{Z}^n} |c_m |^p \right)^{1/p}
&\lesssim
\left\| e^{ \mp i | \cdot |^2 } \widehat f \right\|_{ M_{q,p}^{(0, 0)} }
\sim
\left\| e^{ \pm i \Delta} f \right\|_{ W_{p,q} }
\\
&\lesssim
\left\| f \right\|_{ W_{p,q}^{s} }
\sim
\left\| \widehat f \right\|_{ M_{q,p}^{(s, 0)} }
\lesssim
\left( \sum_{\ell\in\mathbb{Z}^n} \langle \ell \rangle^{sq} | c_\ell |^q \right)^{1/q} ,
\end{align*}
which is the desired result.
\end{proof}

\section{Proof of the main theorem} \label{sec4}

In this section, we prove Theorem \ref{main thm}.
As mentioned in Section \ref{sec1}, the ``IF'' part in Theorem \ref{main thm} was already proved
by Cunanan and Sugimoto \cite{cunanan sugimoto 2014}
and also the ``ONLY IF'' part for $p = \infty$ and $1 \leq q < \infty$
in Theorem \ref{main thm} was proved by Cordero and Nicola \cite{cordero nicola 2010},
so that the main contribution of this paper is
to show the ``ONLY IF'' part for the remaining cases of $p$ and $q$.
However, for the reader's convenience,
we will prove the ``IF'' and ``ONLY IF'' parts for the whole range $1\leq p,q \leq \infty$.

\begin{proof}[\bf Proof of the ``IF'' part of Theorem \ref{main thm}]
We divide the proof into the following three cases:
  \begin{center}
    \begin{tabular}{lll}
    (a) $1\leq p = q \leq \infty$; & (b) $1 \leq p < q \leq \infty $; & (c) $1 \leq q < p \leq \infty $.
    \end{tabular}
  \end{center}

\noindent{\bf Case (a):}
Since $M_{p,p} = W_{p,p} $, Theorem A gives the conclusion in this case.

\noindent{\bf Case (b):}
Recall from Proposition \ref{basic emb} (1)
that $W_{p,p} \hookrightarrow W_{p,q}$ for $p < q$,
and from Proposition \ref{basic emb} (2)
that $W_{p,q}^s \hookrightarrow W_{p,p}$ for $p < q$ and $s > n (1/p - 1/q)$.
Then, Theorem A combined with $ M_{p,p} = W_{p,p} $ gives
\begin{equation*}
\left\| e^{i\Delta} f \right\|_{ W_{p,q} }
\lesssim
\left\| e^{i\Delta} f \right\|_{ W_{p,p} }
\lesssim
\left\| f \right\|_{ W_{p,p} }
\lesssim
\left\| f \right\|_{ W_{p,q}^s }.
\end{equation*}

\noindent{\bf Case (c):}
As above, using Proposition \ref{basic emb} and Theorem A, we have the desired conclusion.
\end{proof}

\begin{proof}[\bf Proof of the ``ONLY IF'' part of Theorem \ref{main thm}]
We prove the ``ONLY IF'' part of Theorem \ref{main thm} by considering the following four cases:
\begin{center}
	\begin{tabular}{llll}
	(a) $1 \leq p = q \leq \infty$; & (b) $1 \leq p < q < \infty $; & (c) $1 < q < p \leq \infty $; &(d) otherwise.
	\end{tabular}
\end{center}

\noindent{\bf Case (a):}
The relation $W_{p,p}^s = M_{p,p}^s$ and Theorem A complete the proof for this case.

\noindent{\bf Case (b):}
Note that the condition $1 \leq p < q < \infty$ implies that $1 < q/p < \infty$.
Using (\ref{seq ck}) with $c_k = \langle k \rangle^{-s} |d_k|^{1/p}$
for a given finitely supported sequence $\{ d_k \}_{k\in\mathbb{Z}^n}$, we have
\begin{equation} \label{seq dk}
\sum_{k\in\mathbb{Z}^n} \langle k \rangle^{-sp} |d_k|
\lesssim
\left( \sum_{k\in\mathbb{Z}^n} | d_k |^{q/p} \right)^{p/q}.
\end{equation}
We take the supremum over $\{ d_k \}_{k\in\mathbb{Z}^n}$ such that $\| d_k \|_{\ell^{q/p}} = 1$.
Then, we have by (\ref{seq dk})
\begin{equation*}
\left\| \langle k \rangle^{- s p } \right\|_{\ell^{(q/p)^\prime}}
=
\sup_{\| d_k \|_{\ell^{q/p}} = 1} \left| \sum_{k\in\mathbb{Z}^n} \langle k \rangle^{-sp} d_k \right|
\lesssim
1,
\end{equation*}
which yields that $(q/p)^\prime s p > n$, namely, $s > n(1/p-1/q) = n | 1/p - 1/q | $.

\noindent{\bf Case (c):}
By duality, our assumption implies $e^{ - i \Delta} : W_{p^\prime,q^\prime} \to W^{-s}_{p^\prime,q^\prime} $,
which is equivalent from Proposition \ref{lift op} that $e^{ - i \Delta} : W^s_{p^\prime,q^\prime} \to W_{p^\prime,q^\prime} $.
Note that $1 < q < p \leq \infty $ implies that $1 \leq p^\prime < q^\prime < \infty $
and thus $1 < q^\prime / p^\prime < \infty $.
Then, repeating the proof above, we obtain $(q^\prime / p^\prime )^\prime s p^\prime > n$,
that is, $s > - n(1/p-1/q) = n | 1/p - 1/q | $.

\noindent{\bf Case (d):} We note that the remaining parts are, in detail,
\begin{center}
	\begin{tabular}{ll}
	(d-1) $1 \leq p < \infty$ and $q = \infty$;
	& (d-2) $1 < p \leq \infty $ and $ q = 1$.
	\end{tabular}
\end{center}
We first consider the case (d-1).
We assume towards a contradiction that $s \leq n | 1/p - 1/q | = n/p$.
Note that we have $e^{ i \Delta}: W^s_{p,\infty} \to W_{p,\infty} $ by the assumption,
which implies that $e^{ i \Delta}: W^{ n/p }_{p,\infty} \to W_{p,\infty}$,
and $e^{ i \Delta}: W_{p,p} \to W_{p,p} $ by Theorem \ref{main thm} (1).
Interpolation yields
for arbitrary $0 < \theta < 1$
that $e^{ i \Delta}: W^{\widetilde s}_{ p ,\widetilde q } \to W_{ p ,\widetilde q} $,
where $1/ \widetilde q = \theta/p$ and $\widetilde s = (1-\theta)n/p$.
Now, we remark that $\widetilde s = n(1/p-1/\widetilde q)$ and $1 \leq p < \widetilde q  < \infty$.
However, this is a contradiction,
since we already proved in Case (b) that, for $1 \leq p < \widetilde q  < \infty$,
$e^{ i \Delta}: W^{\widetilde s}_{ p ,\widetilde q } \to W_{ p ,\widetilde q} $ holds
only if $\widetilde s > n(1/p-1/\widetilde q)$.
Thus, we obtain for $1 \leq p < \infty$,
$e^{ i \Delta}: W^{s}_{p,\infty} \to W_{p,\infty}$ holds only if $s > n / p$.
The case (d-2) can be also given by a similar argument, so that we omit the detail.
\end{proof}

\section*{Acknowledgments}
The authors appreciate Professor Mitsuru Sugimoto,
who listened our talk and gave them valuable advice and comments.
The first author is supported by Grant-in-Aid for JSPS Research Fellow (No. 17J00359).
The second author is partially supported by Grant-in-aid for Scientific Research from JSPS (No. 16K05201).


\section{Introduction}

\IEEEPARstart{G}{ender} recognition can be implemented using different types of data, such as facial images, hand skin images, body signals, and etc. However, as it is the easiest way for human to recognize gender by looking at face, facial images are the most informative data for gender recognition. Since previous decades, various methods and algorithms have been proposed for facial gender recognition. A survey on methods in gender recognition using facial images can be found in \cite{1}.

According to \cite{2,3}, facial information for gender recognition can be categorized into two main categories: (I) geometrical information and (II) texture (or appearance) information. Geometrical information contains the shape and geometry of face and skull, and texture information takes into account the intensity and pattern of facial pixels. Note that in literature of facial gender recognition, usually geometrical information is used in fusion with texture information and not alone; although, texture information is used alone in lots of cases. Moreover, texture and intensity are usually considered the same, referred to as holistic features; however, in \cite{4} intensity, texture, and shape pieces of information are considered differently and are fused in a gender recognition system.

Ref. \cite{5} is one of the first works in facial gender recognition which uses neural network for classification. Neural networks are widely used for feature extraction and classification in gender recognition. For example, back propagation neural networks are used in \cite{3,6,7,8,9,10}. In addition, it is recently shown that convolutional neural networks are useful to obtain discriminative features and classifying genders \cite{11,12,13}.

Other classification methods are also widely used in facial gender recognition, such as Support Vector Machine (SVM), Linear Discriminant Analysis (LDA), and Adaboost. For instance, Independent Component Analysis (ICA) is used in \cite{14} and three different classifiers, i.e., Cosine, LDA, and SVM, are tested. They show that SVM works better with ICA in facial gender recognition. SVM is thoroughly analyzed in \cite{15} for facial gender recognition. In \cite{16}, SVM is used for classifying features extracted by Local Binary Pattern (LBP) and selected by Adaboost. Likewise, SVM is used with LBP in \cite{17}. They also propose a new method in SVM, namely SVM-dropout for avoiding overfitting. Similar to \cite{16}, Adaboost is used with SVM in \cite{18}. Ref. \cite{19,20} are other examples of using SVM in facial gender recognition.

\begin{figure}[!t]
\centering
\includegraphics[width=3.45in]{./images/overall_structure}
\caption{Overall structure of the proposed method.}
\label{figure_overall_structure}
\end{figure}

On the other hand, dimension of facial images is usually high, and methods such as Principal Component Analysis (PCA), ICA, or LDA can be used in order to decrease the dimension of data.
In ref. \cite{10,21,22}, ref. \cite{14}, and ref. \cite{23}, PCA, ICA, and LDA are respectively used for feature extraction and dimension reduction.
LDA prepares a proper subspace for projection which results in better discrimination and also dimension reduction. A novel approach is proposed in \cite{24} which randomly crops a set of image patches out of central face and represents each image set as a projection subspace.

This paper proposes a fusion-based gender recognition method which uses the important ideas of previous work in facial gender recognition area. The overall structure of the proposed method is shown in Fig \ref{figure_overall_structure}.
As can be seen in this figure, the facial images are firstly pre-processed, i.e., become gray-scaled and histogram equalized. Thereafter, landmarks of faces are detected using one of the landmark detection methods in literature. The center of faces are cropped out of images afterwards. Four frameworks are proposed in this method, inspired by the previous works. The two first use texture information of faces for recognition. The third one uses both geometrical and texture information, and the last one uses merely the geometrical information. The inspiration and reasons are explained for each of these frameworks in the next sections. Finally, decisions of four frameworks are voted with appropriate weights and using a threshold, the final decision on the gender of each test face is obtained.
The remainder of this paper is as follows. Section \ref{section_methodology} introduces the method with details on pre-processing, the four frameworks, and the final fusion. Experimental result is reported in \ref{section_experiment}. The article is finally concluded in Section \ref{section_conclusion}.

\section{Methodology}\label{section_methodology}

The proposed fusion-based facial gender recognition method consists of a pre-processing step, and four frameworks whose decisions are finally fused by weighted voting. In the following, all steps are explained in detail, and their inspiration by previous work are also mentioned.

\subsection{Pre-processing}

As shown in Fig. \ref{figure_overall_structure}, pre-processing phase includes making images gray-scaled, equalizing image histogram, detecting landmarks of faces, cropping center of faces out of images, and finally resampling faces to a $30 \times 30$ uniform grid.

\subsubsection{Gray-scale and Histogram Equalization}
After gray-scaling RGB facial images, they should be histogram equalized for better contrast \cite{25}. This is important in gender recognition because facial details carry discriminative and important information for gender classification. Many other gender recognition methods, such as \cite{23}, also use histogram equalization.

\subsubsection{Landmark Detection}\label{section_landmark}
Afterwards, landmarks of faces are detected using a landmark detection method, e.g., Active Shape Model (ASM) \cite{26} or Constrained Local Neural Fields (CLNF) \cite{27}. In this work, CLNF method \cite{27} is used.\footnote{The code of CLNF method can be found in https://github.com/TadasBaltrusaitis/OpenFace.}
In this work, there are 17 landmarks for side outline, 14 landmarks for lips, three landmarks for each upper and lower teeth, six landmarks for each eye, nine landmarks for the whole nose and five landmarks for each eyebrow, resulting in 68 total landmarks.
These landmarks are required for both geometrical information and cropping issues.
The detected landmarks on several sample faces are shown in Fig. \ref{figure_landmarks}.

\begin{figure}[!t]
\centering
\includegraphics[width=3.45in]{./images/landmarks}
\caption{Detected landmarks for several face samples.}
\label{figure_landmarks}
\end{figure}

\subsubsection{Cropping Center of Face and Resampling}
In facial gender recognition, solely central part of face should be considered in order to prevent taking advantage of side information such as long hair. Hence, center-of-faces are cropped out of facial images. Different methods are used for face detection and segmentation in literature. For example, Viola-Jones face detector \cite{28} is used in \cite{6,7,10,17}. Some papers have used skin color detection for segmenting central face, such as \cite{3,18,21}. In this work, however, central face is cropped using the side outline landmarks of face.

As the final step of pre-processing, the cropped central faces are resampled to a $30 \times 30$ uniform grid because of two facts: (I) The cropped central faces do not necessarily have the same size in different images, and (II) high number of pixels results in very high dimensional feature vector which is not suitable.
Moreover, note that not only is not resampling to small size and low resolution images a bad idea, but also as it is declared in \cite{8,15}, information of gender does exist in low resolution of facial images because of skull shape and shadow. In fact, gender can be identified using merely shape and characteristics of skull and face structure.

\subsection{First Framework}

As is shown in Fig. \ref{figure_overall_structure}, the first framework includes uniform LBP, PCA, and back-propagation neural network which are explained in the following.

\subsubsection{Uniform Local Binary Pattern}
It is shown in methods \cite{16,17} that LBP can extract proper features in facial gender recognition. Therefore, in the first framework, inspired by \cite{16,17}, uniform LBP is used for feature extraction out of the $30 \times 30$ face images (see Fig. \ref{figure_overall_structure}). According to \cite{29,30}, LBP for a pixel with intensity $g_c$ and $P$ neighbor pixels with intensities $g_p$ $(p=\{0,\dots,P-1\})$ is calculated as
\begin{equation}
\text{LBP}^u = \sum_{p=0}^{P-1} s(g_p - g_c)2^p,
\end{equation}
where,
\begin{equation}
s(x) =
  \left\{
      \begin{array}{l}
        1 \quad \text{if } x \geq 0,\\
        0 \quad \text{if } x < 0.\\
      \end{array}
    \right.
\end{equation}
If $U(\text{LBP})$ returns the number of transitions from 0 to 1 and vice versa, uniform LBP is calculated as
\begin{equation}
\text{LBP}^u =
  \left\{
      \begin{array}{l}
        \sum_{p=0}^{P-1} s(g_p - g_c) \quad \text{if } U(\text{LBP}) \leq 2,\\
        P+1 \quad \quad \quad \quad \quad \quad \text{otherwise}.\\
      \end{array}
    \right.
\end{equation}
It is shown in \cite{29,30} that uniform LBP works better than LBP; therefore, uniform LBP is used in this framework with eight neighbors having one pixel radius and sliding step of one pixel.

\subsubsection{Principal Component Analysis}\label{section_PCA}

As previously mentioned, because of high dimensionality of image data, PCA can be used to reduce the dimensions. For instance, PCA is used in \cite{10,21,22,23} for feature extraction and reduction. Inspired by them, PCA is used for the sake of dimension reduction. If there are $n$ training samples, the $\text{LBP}^u$ for every training sample $i$ is reshaped to a vector $x_i$, and the covariance matrix of
\begin{equation}
C = \sum_{i=1}^n (x_i - \overline{x}) (x_i - \overline{x})^{T},
\end{equation}
where $\overline{x}$ is the average of training samples. Afterwards, the eigenvectors ($P_k$) of the covariance matrix are found as
\begin{equation}
C P_k = \lambda_k P_k,
\end{equation}
where $\lambda_k$ denote the eigenvalues of $C$. The eigenvectors whose corresponding eigenvalues are bigger than 0.999 times summation of eigenvalues are kept and the others are left over. In test phase, the reshaped $\text{LBP}^u$ is projected onto the purified eigenvectors and its dimension becomes much lower.

\subsubsection{Neural Network}

As previously mentioned, back-propagation \cite{3,6,7,8,9,10} and convolutional neural networks \cite{11,12,13} are widely used in facial gender recognition, and they are shown to be effective for this application. In this framework, a back-propagation neural network with 149 input neurons, one hidden layer with 10 neurons, and one output neuron is utilized. Labels $1$ and $-1$ are used respectively for females and males, as well as for classifiers of other three frameworks.

\subsection{Second Framework}

As is shown in Fig. \ref{figure_overall_structure}, the second framework consists of Gabor filtering, PCA, and kernel SVM which are detailed in the following.

\subsubsection{Gabor Filtering}

It is shown in \cite{6,18} that Gabor filtering prepares suitable features for gender classification. Inspired by them, Gabor filtering is performed in this framework with three scales (wavelengths 2, 5, and 8) and four orientations (angles 0, 45, 90, and 135 degrees). According to \cite{31}, Gabor filter bank is formulated as
\begin{equation}
g(x,y;\lambda,\theta,\phi,\sigma) = \frac{1}{2\pi \sigma^2} e^{\frac{-(x^2+y^2)}{2\sigma^2}} \text{sin}(\frac{2\pi x'}{\lambda} + \phi),
\end{equation}
where
\begin{equation}
x' = x \text{ cos}\theta + y \text{ sin}\theta,
\end{equation}
and $\lambda$, $theta$, $\phi$, and $\sigma$ are respectively wavelength (scale), orientation angle, phase offset, and Gaussian standard deviation. In this framework, magnitudes of Gabor filter results are used. Figure \ref{figure_gabor} shows the 12 filter bank results for one of the faces.

\begin{figure}[!t]
\centering
\includegraphics[width=3.45in]{./images/gabor}
\caption{Magnitude domain of 12 Gabor filter bank results for a sample face.}
\label{figure_gabor}
\end{figure}

\subsubsection{Principal Component Analysis}

There are 12 Gabor filters and each of them have $30 \times 30$ size because of image size. Therefore, after concatenating filter results and reshaping them to a vector, dimension of data becomes 10800 which is very high. PCA is again used for dimension reduction the same as explained in Section \ref{section_PCA}.

\subsubsection{Kernel SVM}\label{section_kernel_svm}

Various gender recognition methods, such as \cite{14,15,16,17,18,19,20}, use SVM as classifier. This fact shows the effectiveness of this powerful classifier in facial gender recognition.
That is why kernel SVM is used as classifier in the second framework.
According to \cite{32}, the decision function in kernel SVM can be expressed as,
\begin{equation}
y_t = \text{sign} (\sum_{i=1}^N \alpha_i y_i K(x_i,x_t) + b),
\end{equation}
where $x_i$ and $x_t$ are respectively training and testing data, $b$ is bias, $\alpha_i$ is positive Lagrange multiplier, $N$ is the number of all training samples, $y_i \in \{+1,-1\}$ is the label of training data, and $K(.,.)$ is the kernel function. In this work, radial basis function is used for kernel, which is
\begin{equation}
K(x_i,x_t) = \text{exp}(-||x_i-x_t||^2).
\end{equation}

\subsection{Third Framework}

As is shown in Fig. \ref{figure_overall_structure}, the third framework includes extracting lower part of face, resampling the cropped image, and kernel SVM which are explained in the following.

\subsubsection{Extracting lower part of face}

According to \cite{19}, lower part of face, i.e., from nose tip to chin, includes crucial information about gender. In other words, gender can be recognized by merely considering the lower part of face because of differences in smoothness or roughness of texture pattern. Inspired by \cite{19}, lower part of face is used in this framework. To extract the lower face, nose tip, chin, and two of the side outline landmarks are used in this work. Several examples of extraction of lower part of face are shown in Fig. \ref{figure_lower_face}. The differences in smoothness of texture in males and females are obvious in this figure.

\begin{figure}[!t]
\centering
\includegraphics[width=3.45in]{./images/lower_face}
\caption{Lower part of faces extracted from sample faces. The first and second rows contain male and female samples respectively.}
\label{figure_lower_face}
\end{figure}

\subsubsection{Resampling}

In order to decrease dimension of data and also equalize the dimension of data samples, the extracted lower parts of faces are resampled to a uniform $30 \times 30$ grid. Thereafter, the $30 \times 30$ images are reshaped to $900 \times 1$ column vectors.

\subsubsection{Kernel SVM}

Finally, the same as explanations in Section \ref{section_kernel_svm}, kernel SVM is used in order to classify the $900 \times 1$ data samples.

\subsection{Fourth Framework}

As is depicted in Fig. \ref{figure_overall_structure}, the fourth framework includes using LDA to classify the side outline landmarks. It is explained in the following.

\subsubsection{Side Outline Landmarks}
In this framework, the side outline landmarks, which were detected previously (see Section \ref{section_landmark}), are taken into account. The inspirations of this framework are \cite{8,9} in gender recognition and \cite{33,34,35,36} in human biology science, which claim that physical and geometrical characteristics of human face and skull have significant differences in males and females. Side outline of face, eyes, eyebrows, chin, supraorbital ridges, cheekbones, mandible, palate, vertical distance between eyes and nose tip, vertical distance between eyes and lips center, nose width, lips width, height of face, and shadow on face because of facial structure are mentioned in literature as geometrical differences in faces of males and females.
Some of these characteristics might be imperfect because they can be affected by the fatness and slimness of face. According to \cite{8}, side outline shape of faces are the most discriminative feature among geometrical information for goal of gender identification. The above part of side outline, however, is covered by hair and is useless. Hence, the bottom side outline of face from left to right ear is considered in this work. The $x$ and $y$ coordinates of landmarks are all concatenated as a column vector in order to feed the classifier which is explained in the following.

\subsubsection{Linear Discriminant Analysis}

Fisher LDA is used for classification in the fourth framework. LDA is a powerful classifier which projects data onto a discriminative subspace \cite{37}.
Suppose $S_b$ and $S_w$ denote the between-class and within-class scattering matrices, respectively, formulated as
\begin{equation}
S_b = \sum_{i=1}^C N_i (\mu_i - \mu) (\mu_i - \mu)^T,
\end{equation}
\begin{equation}
S_w = \sum_{i=1}^C \sum_{x_k \in X_i} (x_k - \mu_i) (x_k - \mu_i)^T,
\end{equation}
where $\mu_i$, $\mu$, $N_i$, $x_k$, and $C$ are respectively average of $i^{th}$ class, average of averages of classes, the number of samples of $i^{th}$ class, the $k^{th}$ sample of $i^{th}$ class ($X_i$), and the number of classes which is two here. In this work, $x_k$ is the column vector containing $x$ and $y$ coordinates of side outline landmarks.
The projection discriminative subspace of LDA is constructed by eigenvectors of $S_w^{-1}S_b$.

\subsection{Fusion}

Output labels (decisions) of the four frameworks ($v_i$) are $+1$ for females and $-1$ for males. In order to fuse the four decisions and make the final decision, majority voting can be useful; however, even number of frameworks might result in a draw. Therefore, a better fusion is required, such as weighted voting. The voting weight of every framework can be considered as its recognition rate on a training subset. In other words, weights are better to show the power of their corresponding frameworks. If $w_i$ denotes the voting weight of $i^{th}$ framework, the final decision can be obtained using a simple threshold as
\begin{equation}
\text{Gender} =
  \left\{
      \begin{array}{l}
        \text{Female} \quad \quad \text{if} \quad \sum_{i=1}^4 w_i v_i \geq 0,\\
        \text{Male} \quad \quad \quad \text{if} \quad \sum_{i=1}^4 w_i v_i < 0.\\
      \end{array}
    \right.
\end{equation}
Fusion step is illustrated in Fig. \ref{figure_overall_structure}.

\section{Experimental Result}\label{section_experiment}

\subsection{Utilized dataset}

For verification of the proposed method, experiments were performed on FEI face dataset \cite{38,39}. In this work, solely 200 neutral faces of FEI dataset was used because gender recognition methods, as well as lots of papers in literature, usually deal with neutral faces without pose and expression difference. 100 of faces are pictures of females and 100 faces are males. 75\% of the samples were used as training samples and the rest of samples were considered for test. The number of female and male samples were fairly equal in training and testing phases.

\subsection{Results}

Table \ref{table_rates} reports the gender recognition rates in the four proposed frameworks and for males, females, and overall. It also reports the rates of final fusion. As can be seen in this table, the best and weakest ones among frameworks are the third and first frameworks respectively.
Moreover, as can be seen in this table, some frameworks work better for males and some are more accurate for females. This, itself, shows that fusion of different frameworks can result in an overall framework which works precisely for both males and females (see last column in Table \ref{table_rates} in which male and female rates are both good and close to each other).
The overall rate in fusion-based method is obtained as 94\% for neutral faces of FEI dataset.

\begin{table}[!t]
\renewcommand{\arraystretch}{1.3}
\caption{Gender recognition rates. F1, F2, F3, and F4 denotes first, second, third, and fourth frameworks respectively. The last row determines the weights associated to frameworks in final fusion.}
\label{table_rates}
\centering
\begin{tabular}{l | c | c | c | c || c}
\hline
\hline
 & F1 & F2 & F3 & F4 & Fusion  \\
\hline
Males   & 84\% & 80\% & 100\% & 80\% & 96\%  \\
\hline
Females & 72\% & 92\% & 80\% & 92\% & 92\%  \\
\hline
Overall & 78\% & 86\% & 90\% & 86\% & \textbf{94\%}  \\
\hline
Weight & 0.78 & 0.86 & 0.9 & 0.86 & --  \\
\hline
\hline
\end{tabular}%
\end{table}

\subsection{Comparison With State-of-the-art}

The recognition rates of state-of-the-art methods in neutral faces of FEI dataset are reported in Table \ref{table_comparison} for the sake of comparison. As can be seen in this table, the paper obtains excellent recognition rate (94\%) equal to the state-of-the-art rate \cite{10} reported in literature. According to this table, it is also observed that the recognition rates of males and females are more close to each other in this work in comparison to \cite{3}, as well as being high enough. This fact is obtained because of the advantage of fusing different frameworks and having their benefits together. Every framework extracts specific and different features necessary for gender recognition, and fusing the results brings various types of features and information together for better performance.

\begin{table}[!t]
\renewcommand{\arraystretch}{1.3}
\caption{Comparison of the proposed method with state-of-the-art facial gender recognition methods in FEI dataset. Question marks mean that the paper has not reported the corresponding rates.}
\label{table_comparison}
\centering
\begin{tabular}{l || c | c | c}
\hline
\hline
 & Males & Females & Total \\
\hline
\cite{3} & 80\% & \textbf{100\%} & 90\%  \\
\hline
\cite{10} & ? & ? & \textbf{94\%}  \\
\hline
Ours & \textbf{96\%} & 92\% & \textbf{94\%}  \\
\hline
\hline
\end{tabular}%
\end{table}

\section{Conclusion and Discussion}\label{section_conclusion}

In this paper, a fusion-based facial gender recognition method is proposed in which four different frameworks, inspired by the state-of-the-art gender recognition methods, exist.
The first framework is composed of LBP, PCA, and back propagation neural network, while the second framework included Gabor filtering, PCA, and kernel SVM. The third and fourth frameworks respectively deal with lower part of faces and side outline landmarks, and use kernel SVM and LDA for classification.

As is obvious, different classification methods, which are neural network, kernel SVM, and LDA, are used in this method making it powerful and effective for different aspects and types of features. In addition, different feature extraction methods, which are LBP, Gabor, PCA, lower face, and landmarks, use almost all the most important features required for gender recognition.
In this paper, both texture and geometrical information are used for recognizing facial gender.
The first and second frameworks are using texture information and the third and fourth ones use the geometrical information.
Taking advantage of both types of information and also different frameworks makes the proposed method powerful, as the experiments verify it.

\appendices

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi


\section{Introduction and Background}

Power diagrams play an important role in many disciplines within operations research, ranging from balanced least-squares clustering~\cite{bbg-14, bbg-17,bbd-00} to multiclass classification~\cite{bm-92, b-14,bb-99,cs-01,v-98,ww-98}. They have recently surfaced in the domain of information elicitation, where one wishes to design contracts or mechanisms to incentivize a self-minded agent to reveal their private information truthfully~\cite{lambert2009eliciting,lambert2011elicitation,frongillo2014general,agarwal2015consistent,frongillo2017geometric}.
In the latter, power diagrams are shown in various settings to characterize the possible sets of information that can be treated identically under the mechanism, an important step in understanding which mechanisms can and cannot be \emph{truthful}, i.e.,\ elicit this information effectively.
Motivated by this application in particular, where one wishes to know whether a given mechanism or contract could be truthful, we study the problem of power diagram detection: deciding whether a given cell decomposition is in fact a power diagram.

We begin with a formal definition of a power diagram~\cite{aurenhammer1987power}.

\begin{definition}[Power Diagram, Original]
  \label{def:pd}
  Given a set of sites $s_1,\ldots,s_k\in\mathbb{R}^d$ and weights $w_1,\ldots,w_k\in\mathbb{R}$, we define the cell corresponding to site $s_i$ as
\begin{equation}
  \label{eq:cell}
  \mathrm{cell}(s_i) = \left\{\, x\in\mathbb{R}^d : i \in \mathop{\mathrm{argmin}}\nolimits_j \|x-s_j\|^2-w_j^2\, \right\}~.
\end{equation}
A cell decomposition $P=(P_1,\ldots,P_k)$ of $\mathbb{R}^d$ is a \emph{power diagram} if there exist $\{s_i\}_{i=1}^k \subseteq \mathbb{R}^d$ and $\{w_i\}_{i=1}^k \subseteq \mathbb{R}$ so that for all $i\in\{1,\ldots,k\}$ we have $P_i = \mathrm{cell}(s_i)$, as in Eq.~\eqref{eq:cell}.
\end{definition}
Informally, the cell of a power diagram is the set of all points which are closest to the corresponding site in squared Euclidean distance, discounting each site by its weight squared. For the sake of simplicity, we assume that cell decompositions in $\mathbb{R}^d$ have full-dimensional cells.

Several basic observations follow from this definition. First, note that $\mathrm{cell}(s_i)$ depends on \emph{all} sites $s_1,\ldots,s_k$ and weights $w_1,\ldots,w_k$. Second, setting $w_1 = \cdots = w_k$ recovers the definition of a Voronoi diagram, where points are assigned to a partition according to which site is closest in Euclidean distance. Third, any power diagram is a polyhedral cell complex, in the sense that all of its cells, and the interesections of these cells, are polyhedra. In particular, the shared boundary of any pair of cells is either empty or is contained in a hyperplane, and thus can be described via linear constraints. Power diagrams exhibit many useful properties beyond the basic observations above, see e.g.~\cite{aurenhammer1987criterion,aurenhammer1987power,b-10,b-14,bg-12}.

The problem we consider is the following: given some polyhedral cell complex $P$, where the cells are described by linear inequalities, determine whether or not $P$ is a power diagram. In Section~\ref{sec:lp}, we devise a novel linear program to solve this problem with a running time complexity that is (at most) weakly polynomial. We treat two variants of the problem, where $P$ decomposes $\mathbb{R}^d$ and where it decomposes a restricted convex domain $D\subseteq \mathbb{R}^d$. We then present and discuss several applications to information elicitation in Section~\ref{sec:applications}. We conclude in Section~\ref{sec:conclusion} with a brief review of our contribution and additional challenges in practice.

\section{Power Diagram Detection by Linear Programming}\label{sec:lp}

We devise a linear program to check whether a given polyhedral cell complex can be represented as a power diagram. For this, recall that polyhedra can be described as the intersection of finitely many halfspaces. Let us begin with a formal problem statement.

\begin{problem}[Power Diagram Detection]\label{problem}
Let $P=(P_1,\dots,P_k)$ be a polyhedral cell complex defined by a set of separating hyperplanes between the cells. Let the index sets $J_i = \{j : \dim(P_i \cap P_j)=d-1\}$ give the adjacency structure in the complex. Finally, let $a_{ij}\in\mathbb{R}^d$ and $\gamma_{ij}\in \mathbb{R}$ with \begin{equation}
    \label{eq:polyhedral-def}
    P_i = \{x\in\mathbb{R}^d : a_{ij}^T x \leq \gamma_{ij} \; \forall j \in J_i\}.
  \end{equation}
\emph{Decide:} Is there a set of sites $\{s_i\}_{i=1}^k \subset \mathbb{R}^d$ and $\{w_i\}_{i=1}^k \subset \mathbb{R}$ such that $P_i = \mathrm{cell}(s_i)$ for all $i\in\{1,\ldots,k\}$?
\end{problem}
Related questions have been studied (for stronger input) in the literature: Based on the information in an incidence lattice of a cell complex, it is possible to determine whether the cell complex is the Voronoi diagram of a set of sites in time linear in the number of facets of the cell complex~\cite{aurenhammer1987recognising}. A similar result, with time linear in the number of vertices of the cell complex, holds in the dual setting of Dirichlet tesselations~\cite{ab-85}. Rybnikov presented an algorithm to decide whether a cell complex given through an incidence graph with information on facets and $(d{-}2)$--faces is a power diagram~\cite{rybnikov1999stresses}. The algorithm is based on finding a feasible point in a set of equalities and strict inequalities.
Its running time is weakly polynomial provided one can address its numerical instability and the challenging implementation of a tailored interior point method.

In this paper, we devise a simple solution to Problem~\ref{problem} that will give a straightforward resolution for applications such as those outlined in Section~\ref{sec:applications}.
The advantages lie in a simple implementation, solvability by any linear programming algorithm, numerical stability, and a practical running time that matches its (favorable) theoretical bound; see Theorems~\ref{thm:detect} and~\ref{thm:detect-restricted}.

Our first tool is the use of an alternative definition of power diagrams, which has been devised in different ways, ranging from pairwise linear separation in a multiclass setting ~\cite{bm-92,b-10,b-14} to duality theory~\cite{bg-12}.

\begin{definition}[Power Diagram, Alternative]\label{def:pd2}
Given a set of sites $s_1,\ldots,s_k\in\mathbb{R}^d$ and $\gamma_1,\dots,\gamma_k \in \mathbb{R}$, we define the cell corresponding to site $s_i$ as
\begin{equation}
  \label{eq:gammacells}
  \mathrm{cell}(s_i) = \{\, x\in\mathbb{R}^d : (s_j-s_i)^Tx\leq \gamma_j-\gamma_i \; \forall j \neq i  \}~.
\end{equation}
A cell decomposition $P=(P_1,\ldots,P_k)$ of $\mathbb{R}^d$ is a \emph{power diagram} if there exist $\{s_i\}_{i=1}^k \subseteq \mathbb{R}^d$ and $\gamma_1,\dots,\gamma_k \in \mathbb{R}$ so that for all $i\in\{1,\ldots,k\}$ we have $P_i = \mathrm{cell}(s_i)$, as in Eq.~\eqref{eq:gammacells}.
\end{definition}

It is easy to match this definition with the original notion of a power diagram through a small transformation~\cite{b-14}: The cells $P_i$ and $P_j$ are separated by the hyperplane \begin{eqnarray*}
H_{ij}& := &\{x \in \mathbb{R}^d: \|s_i-x\|^2 -w_i = \|s_j-x\|^2-w_j\} \\
& = & \{x \in \mathbb{R}^d: 2(s_j-s_i)^Tx = (s_j^Ts_j-w_j)-(s_i^Ts_i-w_i)\}
\end{eqnarray*}
Choosing $\gamma_i=\frac{1}{2}(s_i^Ts_i-w_i)$ for $i \leq k$ yields this new representation, which fits with the definition of piecewise-linear separability~\cite{bm-92} with the small exception that we use weak instead of strict inequalities.
The right-hand sides in the above take the form $\gamma_j-\gamma_i$. This means that the ability to devise a set of sites $\{s_i\}_{i=1}^k \subseteq \mathbb{R}^d$ and $\gamma_1,\dots,\gamma_k$ would be a positive resolution to Problem~\ref{problem}.

Our second tool is the invariance of power diagrams under scaling~\cite{aha-98,b-10}. More precisely, the above representation of power diagrams is invariant under scaling of all $s_i$ and $\gamma_i$, for all $i\leq k$, with the same parameter. For our purposes, it is important to note that in the representation of $H_{ij}$, all parameters can be scaled with a $\lambda_{ij}>0$ without changing $H_{ij}$:
$$2(\lambda_{ij} s_j- \lambda_{ij}s_i)^Tx = \lambda_{ij} \gamma_j-\lambda_{ij}\gamma_i \Leftrightarrow \lambda_{ij}\cdot 2( s_j- s_i)^Tx = \lambda_{ij} \cdot (\gamma_j-\gamma_i) \Leftrightarrow  2(s_j-s_i)^Tx = \gamma_j-\gamma_i.  $$
Of course, the hyperplane specified by $a_{ij}^Tx \leq \gamma_{ij}$ in Eq.~\eqref{eq:polyhedral-def} is similarly invariant under joint scaling of the left-hand and right-hand sides.

These tools allow us to construct a linear program to check whether the cells specified by the given input can be represented as the cells of a power diagram. Recall Eq.~\eqref{eq:polyhedral-def}, which states the cells of the input as $P_i = \{x\in\mathbb{R}^d : a_{ij}^T x \leq \gamma_{ij} \; \forall j \in J_i\}$. We have to match these with the description of the cells as specified in Eq.~\eqref{eq:gammacells}, $\mathrm{cell}(s_i)= \{\, x\in\mathbb{R}^d : (s_j-s_i)^Tx\leq \gamma_j-\gamma_i \; \forall j \neq i  \}$. By the above, we may use any joint scaling of $a_{ij}$ and $\gamma_{ij}$ by a factor $\lambda_{ij}$ in this match.

Consider the following linear program for power diagram detection (PDD)
$$
\begin{array}{lrclcl}
  & \lambda_{ij} \cdot a_{ij}  & = & s_i-s_j &  & \,\,\,\, \forall i \leq k, \forall j \in J_i\\
(PDD) \;\;\;\;& \lambda_{ij}\cdot \gamma_{ij} & = & \gamma_j- \gamma_i & &   \,\,\,\, \forall i \leq k, \forall j \in J_i\\
& \lambda_{ij} & \geq & 1 & &  \,\,\,\, \forall i \leq k, \forall j \in J_i
\end{array}
$$
First, note that the $a_{ij}$ and $\gamma_{ij}$ are given. The $\{s_i\}_{i=1}^k \subseteq \mathbb{R}^d$, the $\gamma_1,\dots,\gamma_k \in \mathbb{R}$, and the $\lambda_{ij}$ $\,\,\,\,\forall i \leq k, \forall j \in J_i$ are variables. Further, note that we do not specify an objective function. We are only interested in finding a feasible solution, so a dummy objective function or a Phase-$0$ formulation of this program will be sufficient.

For all hyperplanes in the form $a_{ij}^Tx \leq \gamma_{ij}$ specified by the original input, this linear program checks whether $a_{ij}$ and $\gamma_{ij}$ can be jointly scaled to match Definition~\ref{def:pd2} of a power diagram. These are the first two lines of the program.

Due to the invariance of power diagrams under joint scaling of all their parameters, the constraints $\lambda_{ij} \geq  1$ $\,\,\,\,\forall i \leq k, \forall j \in J_i$ may be imposed without losing the ability to construct a power diagram (in the cases where this is possible). These additional constraints guarantee that no trivial scaling $\lambda_{ij}=0$ and $s_j=s_i$ is feasible, as well as that no negative scaling $\lambda_{ij}<0$ is feasible, so that the direction of the separation of cells $P_i$ and $P_j$ cannot change.

We now use (PDD) to show the weakly polynomial solvability of Problem~\ref{problem}.

\begin{theorem}
  \label{thm:detect}
  For all rational input, Problem~\ref{problem} can be solved in weakly polynomial time by finding a feasible solution to (PDD). For a yes-instance, a representation of a power diagram is returned.
\end{theorem}

\begin{proof}
Recall that linear programs can be solved in weakly polynomial time through some variants of interior point methods, or the Ellipsoid method. As all the parameters in (PDD) are from the original input, it suffices to show that the number of variables and constraints is strongly polynomial in the size of the input.

Let $p=\sum_{i=1}^k |J_i|$.  There are exactly $3p$ constraints and $k$ variable vectors of type $s_i\in \mathbb{R}^d$, $k$ variables of type $\gamma_i$, and $p$ variables of type $\lambda_{ij}$, giving a total of $kd + k + p$ variables.

The variables $\{s_i\}_{i=1}^k \subseteq \mathbb{R}^d$ and $\gamma_1,\dots,\gamma_k \in \mathbb{R}$ of a feasible solution represent a power diagram for a yes-instance, as in Definition~\ref{def:pd2}. Further, appropriate values for weights $w_i$ (as in Defintion~\ref{def:pd}) can be derived from the $\gamma_i$ through the equality $\gamma_i=\frac{1}{2}(s_i^Ts_i-w_i)$ for $i \leq k$. \qed
\end{proof}

In the next section, we exhibit a collection of applications in which power diagram detection arises. The practical problems essentially fit with the statement  of Problem~\ref{problem}, with the exception that often the domain is restricted, in the sense that the cells $P_i$ given are actually $P_i\cap D$ for some (full-dimensional) domain $D$. We therefore must address the problem of power diagram detection in restricted domains, where one asks whether the given cells can be expressed as a power diagram \emph{restricted to $D$}. We formally capture this problem in the following.

\begin{problem}[Power Diagram Detection for Restricted Domains]\label{problem-restricted}
  Let $D \subseteq \mathbb{R}^d$ be a convex domain, and let $P=(P_1,\dots,P_k)$, $P_i\subseteq D$, be a polyhedral cell complex restricted to $D$ defined by a set of separating hyperplanes between the cells.
  Let the index sets $J^D_i = \{j : \dim (P_i \cap P_j) = d-1\}$ give the adjacency structure in the complex.
  Finally, let $a_{ij}\in\mathbb{R}^d$ and $\gamma_{ij}\in \mathbb{R}$ with
  \begin{equation}
    \label{eq:polyhedral-def-restricted}
    P_i = \{x\in D : a_{ij}^T x \leq \gamma_{ij} \; \forall j \in J_i^D\}.
  \end{equation}
\emph{Decide:} Is there a set of sites $\{s_i\}_{i=1}^k \subseteq \mathbb{R}^d$ and $\{w_i\}_{i=1}^k \subseteq \mathbb{R}$ such that $P_i = \mathrm{cell}(s_i) \cap D$ for all $i\in\{1,\ldots,k\}$?
\end{problem}

This problem variant can be resolved through a small tweak to (PDD): the index sets $J_i$ are replaced with the index sets $J_i^D$. We obtain the following linear program for restricted power diagram detection (r-PDD) for the detection of a power diagram in a restricted domain:
$$
\begin{array}{lrclcl}
  & \lambda_{ij} \cdot a_{ij}  & = & s_i-s_j &  & \,\,\,\, \forall i \leq k, \forall j \in J^D_i\\
(r{-}PDD) \;\;\;\;& \lambda_{ij}\cdot \gamma_{ij} & = & \gamma_j- \gamma_i & &   \,\,\,\, \forall i \leq k, \forall j \in J^D_i\\
& \lambda_{ij} & \geq & 1 & &  \,\,\,\, \forall i \leq k, \forall j \in J^D_i
\end{array}
$$

We now show that Problem~\ref{problem-restricted} is also weakly polynomially solvable. On one hand, we do not find this result surprising, as the structure of the associated linear program essentially remains the same as for Problem~\ref{problem}. However, one has to take special care to understand the impact of the restricted domain, and why the program does not give false-positive answers.

\begin{theorem}
  \label{thm:detect-restricted}
  For all rational input, Problem~\ref{problem-restricted} can be solved in weakly polynomial time by finding a feasible solution to (r-PDD).  For a yes-instance, a representation of a power diagram is returned.
\end{theorem}
\begin{proof}
The running time claim, and the return of a representation of a power diagram for yes-instances, follows analgously to the proof of Theorem~\ref{thm:detect}. The single, yet important difference lies in the restricted domain $D$. We have to consider how the index set $J^D_i$ in Problem~\ref{problem-restricted} relates to the cells $P_i$ in the restricted problem. More precisely, we have to make sure that a yes-answer to the problem corresponds precisely to those inputs, where the polyhedral cells in the domain $D$ come from the intersection of a power diagram in $\mathbb{R}^d$ with the domain $D$.

To this end, let $P'$ be a cell complex in $\mathbb{R}^d$ as defined in Problem~\ref{problem}, and let $J_i$ be the corresponding index sets. Further, let $J^D_i$ be the index sets as defined in Problem~\ref{problem-restricted}. Note $J^D_i\subseteq J_i$. Thus any feasible solution $(s,\gamma)$ to (PDD) (for index sets $J_i$) is also a feasible solution to (r-PDD) (for index sets $J^D_i$). Recall that, by Definition~\ref{def:pd2}, a feasible solution  $(s,\gamma)$ for (PDD) provides the parameters to represent a power diagram $P'$   in $\mathbb{R}^d$. This implies that if there exists a power diagram $P'$ in $\mathbb{R}^d$ with $P=P'\cap D$, the corresponding $(s,\gamma)$ is a feasible solution to both (PDD) and (r-PDD) and we correctly identify a yes-instance for Problem~\ref{problem-restricted}.

It remains that show that all no-instances are identified correctly, as well. Assume there is a feasible solution $(s,\gamma)$ to (r-PDD), and let $P'$ be the corresponding power diagram in $\mathbb{R}^d$. Let index sets $J_i$ and $J^D_i$ represent the adjacency of cells of $P'$ in $\mathbb{R}^d$, respectively in $D$, as defined in Problems~\ref{problem} and~\ref{problem-restricted}. We have to show that $P=P'\cap D$.

By construction, $P_i = \{x\in D : (s_j-s_i)^T x \leq \gamma_j-\gamma_i \; \forall j \in J_i^D\}$ and $P_i'\cap D=\{x\in D : (s_j-s_i)^T x \leq \gamma_j-\gamma_i \; \forall j \in J_i\}$ for all $i=1,\dots,k$. This gives $(P_i'\cap D)\subseteq P_i$ for all $i=1,\dots,k$.

Now, recall that the cells $P_i$ decompose the convex domain $D$, i.e. $\bigcup_{i=1}^k P_i =D$ with $\text{int}(P_i)\cap\text{int}(P_j)=\emptyset$ for $i\neq j$. But as $P'$ is a power diagram of $\mathbb{R}^d$,  the $(P_i'\cap D)$ also decompose $D$, i.e. we have $\bigcup_{i=1}^k (P_i'\cap D) =D$ and $\text{int}(P'_i)\cap\text{int}(P'_j)=\emptyset$  for $i\neq j$. Together with $(P_i'\cap D)\subseteq P_i$, we obtain $P_i=(P_i'\cap D)$ for all $i=1,\dots,k$. This proves the claim.
\qed
\end{proof}

\section{Applications to Information Elicitation}\label{sec:applications}

In the domain of information elicitation, one wishes to design contracts or mechanisms to incentivize a self-minded agent to reveal their private information truthfully.
Often this private information comes in one of two varieties: a \emph{belief} about some future event, or a \emph{utility} or valuation about a particular commodity or outcome.
Power diagrams play a central role in the design of such mechanisms, as characterization theorems show that contracts or mechanisms are truthful (have the correct incentives) if and only if they partition the information space (or ``type space'') into cells that form a power diagram.
As the information space is typically not all of $\mathbb{R}^d$, we will work with the restricted version, Problem~\ref{problem-restricted}.
In what follows, we show how to apply Theorem~\ref{thm:detect-restricted} to three such information elicitation scenarios where power diagrams arise.

\subsubsection*{Property Elicitation.}

One of the most basic information elicitation tasks is to design a contract to elicit some function, or \emph{property}, of an agent's belief.
The literature dates back to Savage~\cite{savage1971elicitation} and Osband~\cite{osband1985providing}, with its modern incarnation beginning with Lambert et al.~\cite{lambert2008eliciting,lambert2009eliciting}.
Concretely, consider a finite set of outcomes $\O$, the set of probability distributions $\Delta(\O)$, a finite set of possible \emph{reports} $\mathcal{R}$, and a property $\Gamma:\Delta(\O)\to 2^\mathcal{R}$ which designates a set of reports considered ``correct'' or ``desired'' for an agent with a particular belief.
For example, the map $\Gamma(p) = \mathop{\mathrm{argmax}}_{\o\in\O} p(\o)$ is the mode functional, which one notes is set-valued whenever there are multiple outcomes with the highest probability.

\begin{figure}[t]
  \begin{tikzpicture} [scale=2.9, thick, tdplot_main_coords]

    \coordinate (orig) at (0,0,0);

    \pgfmathsetmacro{\ph}{4/12}
    \pgfmathsetmacro{\pm}{4/12}
    \pgfmathsetmacro{\pl}{4/12}
    \coordinate (p) at (\ph,\pm,\pl);
    \coordinate[label=below:sun\vphantom{i}] (h) at (1,0,0);
    \coordinate[label=below:rain] (m) at (0,1,0);
    \coordinate[label=above:snow\vphantom{i}] (l) at (0,0,1);

    \coordinate (hm) at (\ph+\pl/2,\pm+\pl/2,0);
    \coordinate (hl) at (\ph+\pm/2,0,\pl+\pm/2);
    \coordinate (ml) at (0,\pm+\ph/2,\pl+\ph/2);

    \draw[simplex] (h) -- (m) -- (l) -- (h);
    \draw[cell] (p) -- (hm);
    \draw[cell] (p) -- (hl);
    \draw[cell] (p) -- (ml);
    \fill (hm) circle [radius=0.5pt];
    \fill (hl) circle [radius=0.5pt];
    \fill (ml) circle [radius=0.5pt];
    \fill (p) circle [radius=0.5pt];

    \node at ($0.38*(m)+0.85*(l)$) {$D$};

    \node at ($0.4*(h)$) {$P_\text{sun}$};
    \node at ($0.4*(m)$) {$P_\text{rain}$};
    \node at ($0.4*(l)$) {$P_\text{snow}$};

    \placefiglabel{(L)}
  \end{tikzpicture}
  ~
  \begin{tikzpicture} [scale=2.9, thick, tdplot_main_coords]

    \coordinate (orig) at (0,0,0);

    \pgfmathsetmacro{\ph}{5/12}
    \pgfmathsetmacro{\pl}{7/12}
    \pgfmathsetmacro{\pm}{0}
    \coordinate (p) at (\ph,\pm,\pl);
    \coordinate[label=below:sun\vphantom{i}] (h) at (1,0,0);
    \coordinate[label=below:rain] (m) at (0,1,0);
    \coordinate[label=above:snow\vphantom{i}] (l) at (0,0,1);

    \coordinate (hm) at (0.6,0.4,0);
    \coordinate (hl) at (\ph+\pm/2,0,\pl+\pm/2);
    \coordinate (ml) at (0,0.5,0.5);

    \draw[simplex] (h) -- (m) -- (l) -- (h);
    \draw[cell] (p) -- (hm);
    \draw[cell] (p) -- (hl);
    \draw[cell] (p) -- (ml);
    \fill (hm) circle [radius=0.5pt];
    \fill (hl) circle [radius=0.5pt];
    \fill (ml) circle [radius=0.5pt];
    \fill (p) circle [radius=0.5pt];

    \node at ($0.38*(m)+0.85*(l)$) {$D$};

    \node at ($0.55*(h)$) {$P_\text{sun}$};
    \node at ($0.25*(m)$) {$P_\text{rain}$};
    \node at ($0.6*(l)$) {$P_\text{snow}$};

    \placefiglabel{(M)}
  \end{tikzpicture}
  ~
  \begin{tikzpicture} [scale=2.9, thick, tdplot_main_coords]

    \coordinate (orig) at (0,0,0);

    \pgfmathsetmacro{\ph}{3/12}
    \pgfmathsetmacro{\pl}{4/12}
    \pgfmathsetmacro{\pm}{5/12}
    \coordinate (p) at (\ph,\pm,\pl);
    \coordinate[label=below:sun\vphantom{i}] (h) at (1,0,0);
    \coordinate[label=below:rain] (m) at (0,1,0);
    \coordinate[label=above:snow\vphantom{i}] (l) at (0,0,1);

    \coordinate (hm) at (0.7,0.3,0);
    \coordinate (hl) at (\ph+\pm/2,0,\pl+\pm/2);
    \coordinate (ml) at (0,0.48,0.52);

    \draw[simplex] (h) -- (m) -- (l) -- (h);
    \draw[cell] (p) -- (hm);
    \draw[cell] (p) -- (hl);
    \draw[cell] (p) -- (ml);
    \fill (hm) circle [radius=0.5pt];
    \fill (hl) circle [radius=0.5pt];
    \fill (ml) circle [radius=0.5pt];
    \fill (p) circle [radius=0.5pt];

    \node at ($0.38*(m)+0.85*(l)$) {$D$};

    \node at ($0.55*(h)$) {$P_\text{sun}$};
    \node at ($0.5*(m)$) {$P_\text{rain}$};
    \node at ($0.6*(l)$) {$P_\text{snow}$};

    \placefiglabel{(R)}
  \end{tikzpicture}
  \caption{\textbf{(L)} The cell decomposition corresponding to the mode functional, which is a power diagram (indeed, a Voronoi diagram) intersected with $D$, the probability simplex over outcomes $\{$sun, rain, snow$\}$ projected onto $\mathbb{R}^2$.  (Take e.g. sites at the corners of the simplex, with equal weights.)
    \textbf{(M)} Another cell decomposition which is a power diagram intersected with $D$, and therefore corresponds to an elicitable property.  Note that the index set would be $J_{\text{sun}} = \{$rain, snow$\}$ in Problem~\ref{problem}, whereas $J_{\text{sun}}^D = \{$rain$\}$ in Problem~\ref{problem-restricted}.
    \textbf{(R)} A cell decomposition which is not a power diagram intersected with $D$, and therefore not an elicitable property.}
  \label{fig:example-simplex}
\end{figure}

To elicit the property $\Gamma$ from an agent, we wish to design a contract $S:\mathcal{R}\times\O\to\mathbb{R}$ which determines the payment to the agent once the outcome materializes.
The protocol is thus: the score $S$ is announced, the agent reports some $r\in\mathcal{R}$, the outcome $\o\in\O$ is revealed, and the agent is paid $S(r,\o)$.
We say that the score $S$ \emph{elicits} the property $\Gamma$ if for all beliefs $p\in\Delta(\O)$, we have
\begin{equation}
  \label{eq:prop-elic}
  \Gamma(p) = \mathop{\mathrm{argmax}}_{r\in\mathcal{R}} \mathbb{E}_{\o\sim p}[S(r,\o)]~,
\end{equation}
that is, the agent maximizes their expected score according to their belief $p$ by reporting $r\in\Gamma(p)$.
For example, if one would like to know which of sun, rain, or snow, is most likely for the weather tomorrow, one would set $\mathcal{R}=\O=\{$sun, rain, snow$\}$ and offer to pay the agent $S(r,\o) = \mathbbm{1}\{r=\o\}$, for the simple reason that this score elicits the mode: $\mathop{\mathrm{argmax}}_r \mathbb{E}_{\o\sim p}[\mathbbm{1}\{r=\o\}] = \mathop{\mathrm{argmax}}_r p(r)$.

A natural question is thus the following: for which properties $\Gamma$ can one devise a score which elicits it?
Perhaps surprisingly, the answer is simple: the elicitable properties $\Gamma$ are precisely those for which the partition $P=(P_r)_{r\in\mathcal{R}}$ given by $P_r = \{p : r \in \Gamma(p)\}$ forms a power diagram~\cite{lambert2009eliciting,frongillo2014general}.
More precisely, after projecting to $\mathbb{R}^{|\O|-1}$, e.g. by dropping the last coordinate, the partition forms a power diagram intersected with the (projected) probability simplex.
See Figure~\ref{fig:example-simplex}(L) for an illustration of this projection for the mode.
The rough intuition for this result is as follows: Eq.~\eqref{eq:cell} can be expressed via an $\mathop{\mathrm{argmin}}$ over $k$ affine functions of $x$ by dropping the irrelevant $\|x\|^2$ term, and then as the negation of an $\mathop{\mathrm{argmax}}$ of affine functions.
As the expected score is linear (and therefore affine) in the agent's belief $p$, the distributions $p$ which share the same optimal report (i.e.,\ the same $\mathop{\mathrm{argmax}}$) must form a cell of a power diagram.

With this characterization at hand, as a practical matter, it becomes relevant to test whether a given polyhedral cell complex, dividing the probability simplex into regions with the same report, forms a power diagram.
This test can be done via Theorem~\ref{thm:detect-restricted}, where the restricted domain $D$ is the probability simplex, $D = \{x\in\mathbb{R}^d : \sum_{i=1}^d x_i = 1, x_i \geq 0 \;\;\; \forall i\leq d \}$.
Note that the restricted domain can indeed change the index sets from (PDD) to (r-PDD), and even when $P_i \cap P_j \neq \emptyset$, one could still have $j \notin J^D_i$, as we illustrate in Figure~\ref{fig:example-simplex}(M).

Essentially the same formalism as described above arises in machine learning as well, in the context of designing loss functions for classification or ranking tasks~\cite{bartlett2006convexity,ramaswamy2013convex,agarwal2015consistent}.
Here one may wish to assign certain distributions over the labels (or classes) to different reports, and one may ask, for which such assignments does there exist a loss function which, when minimized, would yield these reports.
This is again the same question as whether the property corresponding to this assignment is elicitable, where we simply negate the score to obtain a loss.

\subsubsection*{Peer Prediction.}

A problem closely related to property elicitation is peer prediction, where one has access to several agents rather than one, but no direct access to the ground truth.
Instead of designing a contract which scores an agent's report based on some observed outcome, one will never see the outcome, and therefore must score the agents based on each other's reports~\cite{miller2005eliciting,witkowski2012robust}.

To make headway, one typically assumes some structure about the underlying Bayesian (or pseudo-Bayesian) process through which agents form their beliefs.
In particular, one typically assumes that agents receive some \emph{signal} $S\in\O$ about the true outcome (like the quality of a hotel, or the correct label for an image classification task), and from this signal form a posterior belief $p(\cdot|S)$ about the true outcome, or about what another agent's signal was.
By making assumptions about the possible values of this posterior, one can design mechanisms which have a truthful equilibrium, in which each agent simply reports their signal $S$.

Constraints on the possible posteriors in the literature often take the form $p(\cdot|S=\o)\in P_\o$ for some sets $\{P_\o : \o\in\O\}$, dubbed a \emph{belief model constraint} in Frongillo and Witkowski~\cite{frongillo2017geometric}.
Their work shows that there exists a mechanism with a truthful equilibrium if and only if the sets $\{P_\o\}$ form a power diagram~\cite[Corollary 3.5]{frongillo2017geometric}.
(More precisely, there must exist a power diagram with sites $s_\o$ such that $P_\o\subseteq\mathrm{cell}(s_\o)$ for all $\o\in\O$, but we restrict attention to \emph{maximal} constraints, where every distribution is allowed to be the posterior following some signal.)
The problem of detecting whether a belief model constraint supports a mechanism, and constructing said mechanism if so, thus reduces to detecting and constructing a power diagram in a restricted domain (again the probability simplex), to which Theorem~\ref{thm:detect-restricted} applies.

\begin{figure}
  \centering
  \begin{tikzpicture}[thick,scale=0.8]
    \path[->] (0,0) edge node[left]{$t(\o_2)$} (0,4) edge node[below]{$t(\o_1)$} (4,0);
    \draw[dashed] (2,0) -- (2,4) (2,2) -- (4,2);
    \node[anchor=center] at (1,2) {$p_1$};
    \node[anchor=center] at (3,1) {$p_3$};
    \node[anchor=center] at (3,3) {$p_2$};
  \end{tikzpicture}
  \qquad
  \begin{tikzpicture}[thick,scale=0.8]
    \path[->] (0,0) edge node[left]{$t(\o_2)$} (0,4) edge node[below]{$t(\o_1)$} (4,0);
    \draw[dashed] (2,0) -- (2,4) (0,2) -- (4,2);
    \node[anchor=center] at (1,1) {$p_1$};
    \node[anchor=center] at (1,3) {$p_0$};
    \node[anchor=center] at (3,1) {$p_3$};
    \node[anchor=center] at (3,3) {$p_2$};
  \end{tikzpicture}
  \caption{An allocation rule ``skeleton'' which cannot be completed to an implementable allocation rule for any distinct choices of $p_i$ (left), and one which could be so completed for appropriate choices of $p_i$ (right).  Here $t$ denotes the type of an agent, and $t$ being the cell corresponding to $p_i$ implies the allocation $f(t) = p_i$.}
  \label{fig:example-mechanism}
\end{figure}

\subsubsection*{Mechanism Design.}

In mechanism design, one wishes to design an algorithm to choose an outcome based on the reports of the participants, but in a way which is robust to strategic misreports.
From the well-known \emph{revelation principle}, we may assume without loss of generality that the reports or ``bids'' submitted to a mechanism take the form of utility functions: each participant reports their utility for each possible outcome.
From the reported utilities (called \emph{types}) of the agents, the mechanism then chooses a distribution over outcomes (called the \emph{allocation}) as well as a payment owed the mechanism by each participant.
For simplicity, we will consider the case of a single agent.

Given the agent's type $t\in\mathbb{R}^\O$ which encodes their utility $t(\o)$ following each outcome $\o$, the mechanism wishes to choose a random allocation from some set $\O$ of outcomes, as well as the amount the agent should pay.
Formally, given a finite outcome space $\O$ and a convex \emph{type space} $\mathcal{T} \subseteq \mathbb{R}^\O$, a (direct, randomized) \emph{mechanism} is a pair $(f,p)$ where $f:\mathcal{T}\to\Delta_\O$ is the \emph{allocation rule} and $p:\mathcal{T}\to\mathbb{R}$ is the \emph{payment} function.
We typically assume that the agent's utility is \emph{quasi-linear} in the sense that their net utility upon allocation $\o$ and payment $c$ is the difference $t(\o) - c$.
Note that the expected utility can be written $U(t',t) = f(t')\cdot t - p(t')$, where the inner product is between elements of $\mathbb{R}^\O$, where we consider $f(t') \in \Delta_\O \subset \mathbb{R}^\O$ to be the vector form of the allocation distribution.
We say the mechanism $(f,p)$ is \emph{truthful} if $U(t',t) \leq U(t,t)$ for all $t,t' \in \mathcal{T}$.

A fundamental question in mechanism design is \emph{implementability}: given a desired allocation rule $f$, can one find a payment function $p$ such that the pair $(f,p)$ is a truthful mechanism?
In other words, can one design payments to implement the desired allocation rule while being robust to the incentives of the agents?
(If given the allocations themselves, one can use the fact that weak monotonicity (WMON) is sufficient and perform checks in $O(n^2)$ time~\cite{saks2005weak}.)
We consider the following variant of this classic question: given the ``skeleton'' of an allocation rule, that decides upon ``cells'' of types to assign the same allocation but not what that allocation should be, could there be any assignment of allocations to cells such that the resulting allocation rule is implementable?
See Figure~\ref{fig:example-mechanism} for an illustration.
More formally, given the skeleton $g:\mathcal{T}\to\{1,\ldots,m\}$, could there be any implementable allocation rule of the form $f = h \circ g$ for some $h:\{1,\ldots,m\}\to\Delta(\O)$?
From~\cite{saks2005weak,frongillo2014general}, such skeletons must form a power diagram, and thus, given $g$ in the form~\eqref{eq:polyhedral-def-restricted} where $D=\mathcal{T}$ is the type space, this problem can also be solved as stated in Theorem~\ref{thm:detect-restricted}.

\section{Conclusion}
\label{sec:conclusion}

We have presented a simple linear program for power diagram detection, the problem of deciding whether a polyhedral cell decomposition given by linear equalities can be represented as a power diagram. The problem of power diagram detection arises in information elicitation applications, and we have detailed three such applications, to property elicitation, peer prediction, and mechanism design. In each of these problems, the domain is typically restricted to a subset $D$ of $\mathbb{R}^d$, and thus we have also addressed the restricted power diagram detection problem (Problem~\ref{problem-restricted} and Theorem~\ref{thm:detect-restricted}), to determine whether the given complex can be represented as a power diagram restricted to $D$. Combined, our results give a (weakly) polynomial time algorithm to determine whether a given property is elicitable, whether a given belief model constraint corresponds to a truthful peer prediction mechanism, or whether a given allocation ``skeleton'' could extended to an implementable allocation rule.

As a practical concern, we note that information elicitation problems do not necessarily exhibit polyhedral representations of their cells. More precisely, it is possible that the cells of a proposed property, belief model constraint, or allocation rule, are not convex polyhedra, and thus could not possibly be represented as those of a power diagram. Even when they allow a polyhedral representation, the input may be given in a form such that this is not obvious. For example, given a representation of a polyhedron as the convex hull of its vertices, it typically is not efficient to devise a representation as the intersection of halfspaces. In many applications, expert knowledge will allow a viable resolution of these issues, before the methods presented in this paper will be applied. In general however, they pose significant challenges before obtaining a broader detection algorithm in practice.

\bibliographystyle{plain}