# On Simplices with a Given Barycenter That Are Enclosed by the Standard
Simplex

Brent Austgen<EMAIL_ADDRESS>John J. Hasenbein  Erhan Kutanoglu
Operations Research & Industrial Engineering Program, The University of Texas
at Austin, Austin, TX, USA

###### Abstract

We present an optimization model defined on the manifold of the set of
stochastic matrices. Geometrically, the model is akin to identifying a
maximum-volume $n$-dimensional simplex that has a given barycenter and is
enclosed by the $n$-dimensional standard simplex. Maximizing the volume of a
simplex is equivalent to maximizing the determinant of its corresponding
matrix. In our model, we employ trace maximization as a linear alternative to
determinant maximization. We identify the analytical form of a solution to
this model. We prove the solution is optimal and present necessary and
sufficient conditions for it to be the unique optimal solution. Additionally,
we show the identified optimal solution is an inverse $M$-matrix, and that its
eigenvalues are the same as its diagonal entries. We demonstrate how the model
and its solutions apply to the task of synthesizing conditional cumulative
distribution functions (CDFs) that, in tandem with a given discrete marginal
distribution, coherently preserve a given CDF.

###### keywords:

barycenter, eigenvalue, optimization, simplex

††journal: Operations Research Letters

We present an optimization model that is akin to identifying a maximum-volume
simplex that has a given barycenter and is enclosed by the standard simplex.

We provide the analytical form of a particular solution to the model, a matrix
$\overline{U}$, and prove that it is optimal. Additionally, we prove necessary
and sufficient conditions for $\overline{U}$ to be the unique optimal
solution.

We provide the analytical form of $\overline{V}=\overline{U}^{-1}$. We prove
that $\overline{V}$ is an $M$-matrix and that $\overline{U}$ is thus an
inverse $M$-matrix. We also prove that the eigenvalues of $\overline{U}$ and
$\overline{V}$ are the same as their diagonal entries.

We demonstrate how the optimization model and its solutions apply to the task
of synthesizing conditional cumulative distribution functions (CDFs) that, in
tandem with a given discrete marginal distribution, coherently preserve a
given CDF.

##  Introduction

###  1.1 Overview

We present an optimization model defined on the manifold of the set of
stochastic matrices. Geometrically, the model is akin to identifying a
maximum-volume $n$-dimensional simplex. The identification of maximum- and
minimum-volume simplices under various conditions has many applications
including but not limited to hyperspectral unmixing [1, 2, 3], system control
[4, 5], computer-aided design [6], and signal processing [7]. In our model,
the conditions we consider are that the simplex has a given barycenter and
that the simplex is enclosed by the $n$-dimensional standard simplex.
Maximizing the volume of a simplex is equivalent to maximizing the determinant
of its corresponding matrix. In our model, we employ the trace (the sum of
eigenvalues) as a linear alternative to the determinant (the product of
eigenvalues).

We introduce the model and its dual in Section 2. In Section 3, we identify
the analytical form of primal and dual solutions and prove that the solutions
are optimal using the Karush-Kuhn-Tucker (KKT) conditions. We additionally
prove a necessary and sufficient condition for the identified optimal primal
solution, a matrix, to be uniquely optimal. In Section 4, we present the
analytical inverse of that and then classify the two matrices. We additionally
identify and discuss the eigenvalues of these matrices. In Section 5, we
present the application that motivates the optimization model and its
solutions. The application involves synthesizing conditional cumulative
distribution functions (CDFs) that, in tandem with a given discrete marginal
distribution, coherently preserve a given CDF. We present our conclusions in
Section 6.

###  1.2 Notation, Conventions, & Definitions

In this paper, all matrices and vectors are indexed using 1-based indexing.
All vectors are column vectors unless transposed, and all transposed vectors
are row vectors. We let $\bm{0}$ and $\bm{1}$ be vectors of all zeros or ones,
respectively, and we let $\bm{e}_{i}$ be the vector with a 1 in the
$i\textsuperscript{th}$ position and zeros elsewhere. We define
$[c]^{+}=\max\\{c,0\\}$ and $[c]^{-}=\min\\{c,0\\}$. We additionally define
$\mathbb{I}_{[\,\cdot\,]}$ as the indicator function that takes a value of one
if the subscripted condition is true and zero otherwise.

Our analysis revolves around stochastic matrices and vectors, terms we now
define.

######  Definition 1.

A square matrix $A\in\mathbb{R}^{n\times n}$ is a (right) stochastic matrix if
$A\bm{1}=\bm{1}$ and $A\geq 0$ elementwise.

######  Definition 2.

A vector $\bm{a}\in\mathbb{R}^{n}$ is a stochastic vector if
$\bm{a}^{\top}\bm{1}=1$ and $\bm{a}\geq\bm{0}$ elementwise.

In Section 5, we discuss the 1-Wasserstein distance, also known as the Earth-
Mover’s distance. We now define that distance as it appears in Rachev and
Rüschendorf [8].

######  Definition 3.

The _1-Wasserstein distance_ between probability measure $\mu_{1}$ with
associated CDF $F_{1}(x)$ and probability measure $\mu_{2}$ with associated
CDF $F_{2}(x)$ is

$W_{1}(\mu_{1},\mu_{2})=\int_{\mathbb{R}}|F_{1}(x)-F_{2}(x)|\mathop{}\\!\mathrm{d}x.$

##  Optimization Model

Let $U\in\mathbb{R}^{n\times n}$ be a stochastic matrix and
$\bm{q}\in\mathbb{R}^{n}$ a stochastic vector. Note that $U\geq 0$ and
$\bm{q}\geq\bm{0}$ together imply that $U^{\top}\bm{q}\geq\bm{0}$, and that
$\bm{1}^{\top}U^{\top}\bm{q}=\bm{1}^{\top}\bm{q}=1$. That is, $U^{\top}$ maps
one stochastic vector to another.

Given two $n$-dimensional stochastic vectors ${\bm{q}>\bm{0}}$ and
${\bm{p}>\bm{0}}$, we consider as a candidate any stochastic matrix $U$ whose
transpose maps $\bm{q}$ to $\bm{p}$. That is, our candidate set is

$\mathcal{U}=\\{U\in\mathbb{R}^{n\times
n}:U^{\top}\bm{q}=\bm{p},U\bm{1}=\bm{1},U\geq 0\\}.$ (1)

Among these matrices, we seek a matrix whose trace is maximized. The problem
we describe may be formulated as a linear program (LP):

$\max\\{\operatorname{tr}(U):U\in\mathcal{U}\\}.$ (P)

Recall that the trace of a matrix is the sum of its diagonal entries, which is
also equal to the sum of its eigenvalues. As such, (P) is an eigenvalue
optimization problem.

The geometry of (P) may be interpreted as follows. Take the rows of $U$ to be
vertices of an $(n-1)$-simplex and the entries of $\bm{q}$ to be weights at
those vertices. The feasible space is the set of $(n-1)$-simplices that have a
$\bm{q}$-weighted barycenter of $\bm{p}$ and are enclosed by the standard
${(n-1)}$-simplex. The goal is to identify a simplex for which the sum of
$L^{1}$ distances between the $i\textsuperscript{th}$ vertex and $\bm{e}_{i}$
is minimized.

To obtain the dual of (P), consider its Lagrangian:

$\mathcal{L}(U,\bm{\alpha},\bm{\beta},\Gamma)=\mathrm{tr}(U)-\bm{\alpha}^{\top}(U^{\top}\bm{q}-\bm{p})-\bm{\beta}^{\top}(U\bm{1}-\bm{1})+\mathrm{tr}(\Gamma
U^{\top}).$

From this, we see that

$\nabla_{U}\mathcal{L}(U,\bm{\alpha},\bm{\beta},\Gamma)=I-\bm{q}\bm{\alpha}^{\top}-\bm{\beta}\bm{1}^{\top}+\Gamma.$

Hence, the dual function is

$g(\bm{\alpha},\bm{\beta},\Gamma)=\begin{cases}\bm{\alpha}^{\top}\bm{p}+\bm{\beta}^{\top}\bm{1}~{}&\text{if}~{}\bm{q}\bm{\alpha}^{\top}+\bm{\beta}\bm{1}^{\top}-\Gamma=I,\Gamma\geq
0,\\\ \infty~{}&\text{otherwise}.\end{cases}$ (2)

The dual LP, derived from (2), is α^⊤p\+ β^⊤1 qα^⊤+ β1 ^⊤- Γ= I, Γ≥0.

We summarize the KKT conditions [9, 10] for (P) and (2) in Table 1. Since (P)
and (2) are LPs, the KKT conditions are necessary and sufficient for
optimality.

Table 1: KKT Conditions for (P) and (2). Stationarity | $\bm{q}\bm{\alpha}^{\top}+\bm{\beta}\bm{1}^{\top}-\Gamma=I$
---|---
Primal Feasibility | $\bm{p}^{\top}=\bm{q}^{\top}U$
$U\bm{1}=\bm{1}$
$U\geq 0$
Dual Feasibility | $\Gamma\geq 0$
Complementary Slackness | $\operatorname{tr}(U\Gamma^{\top})=0$

##  Optimal Primal & Dual Solutions

For stochastic vectors $\bm{p}>\bm{0}$ and $\bm{q}>\bm{0}$, let $\overline{U}$
be the corresponding matrix with entries

$\overline{u}_{ij}\triangleq\begin{cases}1-[1-p_{i}/q_{i}]^{+},&i=j,\\\\[2.5pt]
0,&i\neq j~{}\text{and}~{}\bm{p}=\bm{q},\\\\[2.5pt]
\displaystyle\frac{[1-p_{i}/q_{i}]^{+}[p_{j}-q_{j}]^{+}}{\sum_{k=1}^{n}[p_{k}-q_{k}]^{+}},&i\neq
j~{}\text{and}~{}\bm{p}\neq\bm{q}.\end{cases}$ (2)

Additionally, let $\overline{\bm{\alpha}}$ and $\overline{\bm{\beta}}$ be
$n$-dimensional vectors and $\overline{\Gamma}$ an $n\times n$ matrix with
entries

$\displaystyle\overline{\alpha}_{j}$
$\displaystyle\triangleq\mathbb{I}_{[p_{j}<q_{j}]}/q_{j},$
$\displaystyle\overline{\beta}_{i}$
$\displaystyle\triangleq\mathbb{I}_{[p_{i}\geq q_{i}]},$
$\displaystyle\overline{\gamma}_{ij}$
$\displaystyle\triangleq\mathbb{I}_{[p_{i}\geq
q_{i}]}+\mathbb{I}_{[p_{j}<q_{j}]}\cdot q_{i}/q_{j}-\mathbb{I}_{[i=j]}.$

We present these values on a case-by-case basis in Table 2.

Table 2: Values of $\overline{\bm{\alpha}}$, $\overline{\bm{\beta}}$, $\overline{\Gamma}$, and related quantities on a case-by-case basis. Conditions | $\overline{\alpha}_{j}$ | $\overline{\beta}_{i}$ | $\overline{\gamma}_{ij}$ | $\left[\bm{q}\overline{\bm{\alpha}}^{\top}\right]_{ij}$ | $\left[\overline{\bm{\beta}}\bm{1}^{\top}\right]_{ij}$
---|---|---|---|---|---
$i=j$ | $p_{i}<q_{i}$ | $p_{j}<q_{j}$ | $1/q_{j}$ | $0$ | $0$ | $1$ | $0$
$i=j$ | $p_{i}\geq q_{i}$ | $p_{j}\geq q_{j}$ | $0$ | $1$ | $0$ | $0$ | $1$
$i\neq j$ | $p_{i}<q_{i}$ | $p_{j}<q_{j}$ | $1/q_{j}$ | $0$ | $q_{j}/q_{i}$ | $q_{j}/q_{i}$ | $0$
$i\neq j$ | $p_{i}<q_{i}$ | $p_{j}\geq q_{j}$ | $0$ | $0$ | $0$ | $0$ | $0$
$i\neq j$ | $p_{i}\geq q_{i}$ | $p_{j}<q_{j}$ | $1/q_{j}$ | $1$ | $q_{j}/q_{i}+1$ | $q_{j}/q_{i}$ | $1$
$i\neq j$ | $p_{i}\geq q_{i}$ | $p_{j}\geq q_{j}$ | $0$ | $1$ | $1$ | $0$ | $1$

We now work toward proving that $\overline{U}$ and
$(\overline{\bm{\alpha}},\overline{\bm{\beta}},\overline{\Gamma})$ are an
optimal primal-dual pair.

######  Lemma 1.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the corresponding matrix $\overline{U}$ is feasible in (P).

###### Proof.

For $\overline{U}$ to be feasible in (P), it must exist in $\mathcal{U}$. If
$\bm{p}=\bm{q}$, then $\overline{U}=I\in\mathcal{U}$, trivially. Otherwise,
consider as preliminaries that

$[1-p_{i}/q_{i}]^{+}=[q_{i}-p_{i}]^{+}/q_{i},$

and

$q_{j}\overline{u}_{jj}=q_{j}-q_{j}[1-p_{j}/q_{j}]^{+}=q_{j}-[q_{j}-p_{j}]^{+}=p_{j}-[p_{j}-q_{j}]^{+}.$

Now first,

$\displaystyle\sum_{j=1}^{n}\overline{u}_{ij}$
$\displaystyle=\overline{u}_{ii}+\sum_{j\neq i}\overline{u}_{ij}$
$\displaystyle=1-[1-p_{i}/q_{i}]^{+}+\sum_{j\neq
i}\frac{[1-p_{i}/q_{i}]^{+}[p_{j}-q_{j}]^{+}}{\sum_{k=1}^{n}[p_{k}-q_{k}]^{+}}$
$\displaystyle=1-\frac{[q_{i}-p_{i}]^{+}[p_{j}-q_{j}]^{+}}{q_{i}\sum_{k=1}^{n}[p_{k}-q_{k}]^{+}}$
$\displaystyle=1.$

And second,

$\displaystyle\sum_{i=1}^{n}q_{i}\overline{u}_{ij}$
$\displaystyle=q_{j}\overline{u}_{jj}+\sum_{i\neq j}q_{i}\overline{u}_{ij}$
$\displaystyle=p_{j}-[p_{j}-q_{j}]^{+}+\sum_{i\neq
j}\frac{q_{i}[1-p_{i}/q_{i}]^{+}[p_{j}-q_{j}]^{+}}{\sum_{k=1}^{n}[p_{k}-q_{k}]^{+}}$
$\displaystyle=p_{j}-\frac{[p_{j}-q_{j}]^{+}[q_{j}-p_{j}]^{+}}{\sum_{k=1}^{n}[p_{k}-q_{k}]^{+}}$
$\displaystyle=p_{j}.$

Thus, $\overline{U}\bm{1}=\bm{1}$ and $\overline{U}^{\top}\bm{q}=\bm{p}$.
Finally, $\overline{U}\geq 0$ is evident from the definition of
$\overline{u}_{ij}$. Hence, $\overline{U}\in\mathcal{U}$. ∎

######  Lemma 2.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the corresponding vectors $\overline{\bm{\alpha}}$ and
$\overline{\bm{\beta}}$ and matrix $\overline{\Gamma}$ are feasible in (2).

###### Proof.

One may verify that $\overline{\bm{\alpha}},\overline{\bm{\beta}}$, and
$\overline{\Gamma}$ comprise a feasible solution to (2) from Table 2. ∎

######  Lemma 3.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the corresponding matrices $\overline{U}$ and
$\overline{\Gamma}$ satisfy the complementary slackness condition
$\operatorname{tr}(U\Gamma^{\top})=0$.

###### Proof.

Observe that $\overline{\gamma}_{ij}=0$ only when $i=j$ or when $i\neq
j,p_{i}<q_{i}$, and $p_{j}\geq q_{j}$. In any other case,
$\overline{u}_{ij}=0$. As such $\overline{\gamma}_{ij}\overline{u}_{ij}=0$ for
all $i,j=1,\ldots,n$. ∎

######  Theorem 4.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the corresponding $\overline{U}$ is optimal in (P) and the
corresponding $\overline{\bm{\alpha}}$, $\overline{\bm{\beta}}$, and
$\overline{\Gamma}$ are optimal in (2).

###### Proof.

The KKT conditions in Table 1 are necessary and sufficient for LP optimality.
For $\overline{U}$, $\overline{\bm{\alpha}}$, $\overline{\bm{\beta}}$, and
$\overline{\Gamma}$, Lemma 1 proves primal feasibility, Lemma 2 proves dual
feasibility and stationarity, and Lemma 3 proves complementary slackness. ∎

It follows, of course, that
$\operatorname{tr}(\overline{U})=\overline{\bm{\alpha}}^{\top}\bm{p}+\overline{\bm{\beta}}^{\top}\bm{1}$.
No matter, showing how this equality holds shines light on the relationship
between $[\,\cdot\,]^{+}$ in the construction of the primal optimal solution
and $\mathbb{I}_{[\,\cdot\,]}$ in the construction of the dual optimal
solution:

$\displaystyle\overline{\bm{\alpha}}^{\top}\bm{p}+\overline{\bm{\beta}}^{\top}\bm{1}$
$\displaystyle=\sum_{i=1}^{n}\left(p_{i}/q_{i}\cdot\mathbb{I}_{[p_{i}<q_{i}]}+\mathbb{I}_{[p_{i}\geq
q_{i}]}\right)$
$\displaystyle=\sum_{i=1}^{n}\left(p_{i}/q_{i}\cdot(1-\mathbb{I}_{[p_{i}\geq
q_{i}]})+\mathbb{I}_{[p_{i}\geq q_{i}]}\right)$
$\displaystyle=\sum_{i=1}^{n}\left((1-p_{i}/q_{i})\mathbb{I}_{[p_{i}\geq
q_{i}]}+p_{i}/q_{i}\right)$
$\displaystyle=\sum_{i=1}^{n}\left(1-[1-p_{i}/q_{i}]^{+}\right)$
$\displaystyle=\sum_{i=1}^{n}\overline{u}_{ii}$
$\displaystyle=\operatorname{tr}(\overline{U}).$

To conclude this section, we discuss conditions under which $\overline{U}$ is
uniquely optimal in (P).

######  Lemma 5.

Every optimal solution to (P) possesses

$u_{ii}=\min\\{p_{i}/q_{i},1\\}=1-[1-p_{i}/q_{i}]^{+},\quad\forall
i=1,\ldots,n.$

Moreover, if an optimal solution possesses $u_{ii}=1$ then its
$i\textsuperscript{th}$ row is $\bm{e}_{i}^{\top}$, and if it possesses
$u_{ii}=\frac{p_{i}}{q_{i}}$ then its $i\textsuperscript{th}$ column is
$\frac{p_{i}}{q_{i}}\bm{e}_{i}$.

###### Proof.

For each $i=1,\ldots,n$,

$\displaystyle U\bm{1}=\bm{1},U\geq 0$ $\displaystyle\implies u_{ii}\leq 1,$
$\displaystyle U^{\top}\bm{q}=\bm{p},U\geq 0$ $\displaystyle\implies
u_{ii}\leq p_{i}/q_{i}.$

As such, the constraints of (P) imply for each $i=1,\ldots,n$ that
${u_{ii}\leq\min\\{p_{i}/q_{i},1\\}=1-[1-p_{i}/q_{i}]^{+}}$ independently. The
objective of (P) is to maximize $\sum_{i=1}^{n}u_{ii}$, and $\overline{U}$
does so by satisfying all of these constraints at equality. Hence, every
optimal solution to (P) must satisfy these constraints at equality.

If $u_{ii}=1$, then $U\bm{1}=\bm{1},U\geq 0$ imply that $u_{ij}=0$ for all
$j\neq i$. Similarly, if $u_{ii}=p_{i}/q_{i}$, then
$U^{\top}\bm{q}=\bm{p},U\geq 0$ imply that $u_{ji}=0$ for all $j\neq i$. ∎

The following lemma, which provides a necessary and sufficient condition for
the uniqueness of an optimal LP solution, comes from Mangasarian [11].

######  Lemma 6.

Let $\overline{\bm{x}}$ be an optimal solution to the linear program

$\min\\{\bm{p}^{\top}\bm{x}:A\bm{x}=\bm{b},C\bm{x}\geq d\\}.$

Let $\bm{c}_{i}^{\top}$ be the $i\textsuperscript{th}$ row of $C$, and let
$C_{\mathcal{E}}$ be the matrix whose rows are all the $\bm{c}_{i}$ satisfying
$\bm{c}_{i}^{\top}\overline{\bm{x}}=d_{i}$. Then $\overline{\bm{x}}$ is
uniquely optimal if and only if

$\widetilde{\mathcal{X}}=\\{\tilde{\bm{x}}:\bm{p}^{\top}\tilde{\bm{x}}\leq
0,\tilde{\bm{x}}\neq\bm{0},A\tilde{\bm{x}}=\bm{0},C_{\mathcal{E}}\tilde{\bm{x}}\geq\bm{0}\\}=\varnothing.$

Lemma 6 essentially states that for any $\tilde{\bm{x}}\in\widetilde{X}$ and
sufficiently small $\epsilon>0$, $\overline{\bm{x}}$ and
$\overline{\bm{x}}+\epsilon\tilde{\bm{x}}$ are both feasible and optimal
solutions. With this in mind, we consider the conditions under which

$\displaystyle\widetilde{\mathcal{U}}\triangleq\\{\widetilde{U}\in\mathbb{R}^{n\times
n}:\operatorname{tr}(\widetilde{U})\geq 0,\widetilde{U}\neq
0,\widetilde{U}^{\top}\bm{q}=\bm{0},\widetilde{U}\bm{1}=\bm{0},$
$\displaystyle\tilde{u}{ij}\geq 0,\forall
i,j=1,\ldots,n~{}\text{s.t.}~{}\overline{u}_{ij}=0$
$\displaystyle\\}=\varnothing.$

######  Theorem 7.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, define

$\displaystyle\mathcal{G}$ $\displaystyle=\\{i:p_{i}>q_{i}\\},$
$\displaystyle\mathcal{E}$ $\displaystyle=\\{i:p_{i}=q_{i}\\},$
$\displaystyle\mathcal{L}$ $\displaystyle=\\{i:p_{i}<q_{i}\\}.$

The corresponding matrix $\overline{U}\in\mathbb{R}^{n\times n}$ is uniquely
optimal in (P) if and only if $|\mathcal{G}|\leq 1$ or $|\mathcal{L}|\leq 1$.

###### Proof.

We first consider the case of $|\mathcal{G}|\leq 1$. Note that
$|\mathcal{G}|=0$ if and only if $\bm{p}=\bm{q}$, and it follows from Lemma 5
that $\overline{U}=I$ is uniquely optimal. If $|\mathcal{G}|=1$, then
$|\mathcal{E}\cup\mathcal{L}|=n-1$. In this case, $n-1$ columns of an optimal
to solution to (P) are determined by Lemma 5, and the remaining column is
determined by $U\bm{1}=\bm{1}$. Hence, $\overline{U}$ is uniquely optimal. For
$|\mathcal{L}|\leq 1$, a similar argument applies to the rows of an optimal
solution.

Now if neither $|\mathcal{G}|\leq 1$ nor $|\mathcal{L}|\leq 1$, then
${|\mathcal{G}|\geq 2}$ and ${|\mathcal{L}|\geq 2}$. Let
$i,i^{\prime}\in\mathcal{L},i\neq i^{\prime}$, let
$j,j^{\prime}\in\mathcal{G},j\neq j^{\prime}$, and let $\widetilde{U}$ be a
matrix with ${\tilde{u}_{ij}=q_{i^{\prime}}}$,
${\tilde{u}_{ij^{\prime}}=-q_{i^{\prime}}}$,
${\tilde{u}_{i^{\prime}j}=-q_{i}}$,
${\tilde{u}_{i^{\prime}j^{\prime}}=q_{i}}$, and all other entries zero. Note
that $\mathcal{G}\cap\mathcal{L}=\varnothing$, so
$\operatorname{tr}(\widetilde{U})=0$. The matrix $\widetilde{U}$ trivially
satisfies $\widetilde{U}\neq 0$, $\widetilde{U}^{\top}\bm{q}=\bm{0}$, and
$\widetilde{U}\bm{1}=\bm{0}$. Finally, owing to the fact that $p_{i}<q_{i}$,
$p_{i^{\prime}}<q_{i^{\prime}}$, $p_{j}>q_{j}$, and
$p_{j^{\prime}}>q_{j^{\prime}}$, all of $\overline{u}_{ij}$,
$\overline{u}_{ij^{\prime}}$, $\overline{u}_{i^{\prime}j}$, and
$\overline{u}_{i^{\prime}j^{\prime}}$ are strictly positive. Accordingly, the
corresponding entries of $\widetilde{U}$ are not subject to the only other
constraint of $\widetilde{\mathcal{U}}$. Hence,
$\widetilde{U}\in\widetilde{\mathcal{U}}\neq\varnothing$. Following Lemma 6,
$\overline{U}$ is not uniquely optimal in (P). ∎

######  Corollary 8.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the corresponding $\overline{U}$ is uniquely optimal in (P)
if $n=1,2,3$.

######  Example 1.

Let
$\bm{p}^{\top}=[\nicefrac{{1}}{{2}},\nicefrac{{1}}{{4}},\nicefrac{{1}}{{8}},\nicefrac{{1}}{{8}}]$
and
$\bm{q}^{\top}=[\nicefrac{{1}}{{20}},\nicefrac{{1}}{{5}},\nicefrac{{7}}{{20}},\nicefrac{{2}}{{5}}]$.
Then $\mathcal{G}=\\{1,2\\}$, $\mathcal{E}=\varnothing$,
$\mathcal{L}=\\{3,4\\}$, and

$\overline{U}=\left[\begin{array}[]{cccc}1&0&0&0\\\ 0&1&0&0\\\
\nicefrac{{3}}{{8}}&\nicefrac{{1}}{{8}}&\nicefrac{{1}}{{2}}&0\\\
\nicefrac{{9}}{{16}}&\nicefrac{{3}}{{16}}&0&\nicefrac{{1}}{{4}}\end{array}\right].$

Using the construction in the proof for Theorem 7, we obtain

$\widetilde{U}=\left[\begin{array}[]{cccc}0&0&0&0\\\ 0&0&0&0\\\
\nicefrac{{-1}}{{2}}&\nicefrac{{1}}{{2}}&0&0\\\
\nicefrac{{1}}{{4}}&\nicefrac{{-1}}{{4}}&0&0\end{array}\right]\in\widetilde{\mathcal{U}}.$

From this, we see that

$\overline{U}+\min\\{\nicefrac{{\overline{u}_{31}}}{{q_{4}}},\nicefrac{{\overline{u}_{42}}}{{q_{3}}}\\}\widetilde{U}=\left[\begin{array}[]{cccc}1&0&0&0\\\
0&1&0&0\\\ 0&\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}&0\\\
\nicefrac{{3}}{{4}}&0&0&\nicefrac{{1}}{{4}}\end{array}\right]$

is likewise feasible and optimal in (P).

##  Properties of $\overline{U}$ and its Inverse

In this section, we identify the matrix $\overline{V}$ that is the inverse of
$\overline{U}$, then we discuss the properties of these matrices. First, we
show that $\overline{V}$ is a $Z$-matrix and moreover an $M$-matrix, and that
$\overline{U}$ is accordingly an inverse $M$-matrix (i.e., a matrix that is
the inverse of an $M$-matrix). These classes of matrices are noteworthy for
their numerous and varied characterizations [12, 13]. Independently, we show
that the diagonal entries of $\overline{U}$ and $\overline{V}$ are the
eigenvalues of those matrices.

For stochastic vectors $\bm{p}>\bm{0}$ and $\bm{q}>\bm{0}$, let $\overline{V}$
be the corresponding matrix with entries

$\overline{v}_{ij}\triangleq\begin{cases}1-[1-q_{i}/p_{i}]^{-},&i=j,\\\\[5.0pt]
0,&i\neq j~{}\text{and}~{}\bm{p}=\bm{q},\\\\[2.5pt]
\displaystyle\frac{[1-q_{i}/p_{i}]^{-}[p_{j}-q_{j}]^{+}}{\sum_{k=1}^{n}[p_{k}-q_{k}]^{+}},&i\neq
j~{}\text{and}~{}\bm{p}\neq\bm{q}.\end{cases}$ (3)

We now prove that $\overline{V}$ is the inverse of $\overline{U}$.

######  Theorem 9.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the corresponding matrices $\overline{U}$ and
$\overline{V}$ satisfy $\overline{U}\overline{V}=I$.

###### Proof.

If $\bm{p}=\bm{q}$, then $\overline{U}=\overline{V}=I$, and the result is
trivially true. Otherwise, observe that

$\displaystyle\overline{u}_{kk}=1-[1-p_{k}/q_{k}]^{+}=\min\\{p_{k}/q_{k},1\\},$
$\displaystyle\overline{v}_{kk}=1-[1-q_{k}/p_{k}]^{-}=\max\\{q_{k}/p_{k},1\\}.$

If $p_{k}\geq q_{k}$, then $\overline{u}_{kk}=1$ and $\overline{v}_{kk}=1$. If
$p_{k}<q_{k}$, then $\overline{u}_{kk}=p_{k}/q_{k}$ and
$\overline{v}_{kk}=q_{k}/p_{k}$. Hence,
$\overline{u}_{kk}\overline{v}_{kk}=1$. Additionally, observe that
$[p_{k}-q_{k}]^{+}[1-q_{k}/p_{k}]^{-}=0$, so

$\overline{u}_{ik}\overline{v}_{kj}=\frac{[1-p_{i}/q_{i}]^{+}[p_{k}-q_{k}]^{+}}{\sum_{l=1}^{n}[p_{l}-q_{l}]^{+}}\cdot\frac{[1-q_{k}/p_{k}]^{-}[p_{j}-q_{j}]^{+}}{\sum_{l=1}^{n}[p_{l}-q_{l}]^{+}}=0$

for all $i,j,k=1,\ldots,n,i\neq k,k\neq j$. As such,

$\left[\overline{U}\overline{V}\right]_{ij}=\sum_{k=1}^{n}\overline{u}_{ik}\overline{v}_{kj}=\begin{cases}1~{}\text{if}~{}i=j,\\\
0~{}\text{otherwise.}\end{cases}$

∎

Since $\bm{1}$ is a fixed point of $\overline{U}$, it is also a fixed point of
its inverse $\overline{V}$. Hence, $\overline{V}\bm{1}=\bm{1}$. Also,

$\overline{U}^{\top}\bm{p}=\bm{q}\implies\overline{V}^{\top}\overline{U}^{\top}\bm{p}=\overline{V}^{\top}\bm{q}\implies\overline{V}^{\top}\bm{q}=\bm{p}.$

Geometrically, $\overline{U}$ is the matrix representation of a simplex that
has a $\bm{p}$-weighted barycenter of $\bm{q}$ and is enclosed by the standard
simplex. Its inverse $\overline{V}$ is the matrix representation of a simplex
that has a $\bm{q}$-weighted barycenter of $\bm{p}$ and is an enclosure of the
standard simplex.

###  4.1 Classification of $\overline{U}$ and $\overline{V}$

Using the fact that $\overline{U}\overline{V}=I$, we now classify these
matrices.

######  Lemma 10.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the corresponding $\overline{V}$ is a $Z$-matrix.

###### Proof.

A $Z$-matrix is a real-valued square matrix whose off-diagonal entries are
nonpositive [13]. From (3), we see that the offdiagonal entries of
$\overline{V}$ are either zero (if $\bm{p}=\bm{q}$) or nonpositive (if
$\bm{p}\neq\bm{q}$). ∎

######  Theorem 11.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the corresponding $\overline{V}$ is an $M$-matrix.

###### Proof.

For a matrix $A$ to be an $M$-matrix, it is necessary and sufficient for $A$
to be a $Z$-matrix that is nonsingular with ${A^{-1}\geq 0}$ [13], which for
$\overline{V}$ follows from Theorem 1, Theorem 9, and Lemma 10. ∎

######  Corollary 12.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the corresponding $\overline{U}$ is an inverse $M$-matrix.

###  4.2 Eigenvalues of $\overline{U}$ and $\overline{V}$

In Section 3 we showed that $\overline{U}$ is an optimal solution to the
matrix optimization problem (P), which we noted is an eigenvalue optimization
problem. Interestingly, the eigenvalues of $\overline{U}$ and $\overline{V}$
are their diagonal entries, which we now prove.

######  Lemma 13.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, for all $i=1,2,\ldots,n,$ either the
$i\textsuperscript{th}$ row or $i\textsuperscript{th}$ column of the
corresponding $\overline{U}$ consists entirely of zeros except for
$\overline{u}_{ii}>0$, and either the $i\textsuperscript{th}$ row or
$i\textsuperscript{th}$ column of the corresponding $\overline{V}$ consists
entirely of zeros except for $\overline{v}_{ii}>0$.

###### Proof.

If $\bm{p}=\bm{q}$, then $\overline{U}=\overline{V}=I$. In such a case, both
the $i\textsuperscript{th}$ row and $i\textsuperscript{th}$ column of
$\overline{U}$ are all zeros except for $\overline{u}_{ii}=1$. Similarly, both
the $i\textsuperscript{th}$ row and $i\textsuperscript{th}$ column of
$\overline{V}$ are all zeros except for $\overline{v}_{ii}=1$.

Otherwise, if $\bm{p}\neq\bm{q}$, recall for $i\neq j$ that

$\displaystyle\overline{u}_{ij}=\frac{[1-p_{i}/q_{i}]^{+}[p_{j}-q_{j}]^{+}}{\sum_{k=1}^{n}[p_{k}-q_{k}]^{+}},$
$\displaystyle\overline{v}_{ij}=\frac{[1-q_{i}/p_{i}]^{-}[p_{j}-q_{j}]^{+}}{\sum_{k=1}^{n}[p_{k}-q_{k}]^{+}}.$

Now observe that for all $i,j=1,\ldots,n,i\neq j$, either

$p_{i}\geq
q_{i}\implies[1-p_{i}/q_{i}]^{+}=[1-q_{i}/p_{i}]^{-}=0\implies\overline{u}_{ij}=\overline{v}_{ij}=0,$

or

$p_{i}\leq
q_{i}\implies[p_{i}-q_{i}]^{+}\implies\overline{u}_{ji}=\overline{v}_{ji}=0.$

∎

######  Theorem 14.

For any two $n$-dimensional stochastic vectors ${\bm{p}>\bm{0}}$ and
${\bm{q}>\bm{0}}$, the eigenvalues of the corresponding $\overline{U}$ are
$\overline{u}_{11},\overline{u}_{22},\ldots,\overline{u}_{nn}$, and the
eigenvalues of the corresponding $\overline{V}$ are similarly
$\overline{v}_{11},\overline{v}_{22},\ldots,\overline{v}_{nn}$.

###### Proof.

From Lemma 13, for $i=1,\ldots,n$ either the $i\textsuperscript{th}$ row or
$i\textsuperscript{th}$ column of $\overline{U}$ consists of all zeros except
for $\overline{u}_{ii}>0$. The same is true of $\overline{V}$. Using Laplace
expansion, one may thus expand strategically on rows or columns to get
characteristic equations

$\displaystyle\det(\overline{U}-\lambda
I)=\prod_{i=1}^{n}(\overline{u}_{ii}-\lambda),$
$\displaystyle\det(\overline{V}-\lambda
I)=\prod_{i=1}^{n}(\overline{v}_{ii}-\lambda).$

Ergo, the eigenvalues of $\overline{U}$ are
$\overline{u}_{11},\overline{u}_{22},\ldots,\overline{u}_{nn}$ and, similarly,
the eigenvalues of $\overline{V}$ are
$\overline{v}_{11},\overline{v}_{22},\ldots,\overline{v}_{nn}$. ∎

While $\overline{U}$, among $U\in\mathcal{U}$, maximizes
$\operatorname{tr}(U)$, it does not necessarily maximize $|\det(U)|$. That is,
among $U\in\mathcal{U}$, the matrix $\overline{U}$ does not necessarily
correspond to a simplex of maximum unsigned volume. The reason is that trace
maximization inherently promotes a simplex orientation that sites the
$i\textsuperscript{th}$ vertex near to $\bm{e}_{i}$. Consider the following
relaxation of (P) involving the joint optimization of $U\in\mathcal{U}$ and
$M\in\mathcal{P}$, the set of all $n\times n$ permutation matrices:

$\max\\{\operatorname{tr}(MU):U\in\mathcal{U},M\in\mathcal{P}\\}.$ (P-Perm)

The goal of this problem is to identify a $U\in\mathcal{U}$ whose
premultiplication with an appropriate $M\in\mathcal{P}$ yields a trace-
maximizing matrix. This relaxation of (P) promotes no particular simplex
orientation. Rather, it allows the simplex associated with $U$ to be oriented
freely via $M\in\mathcal{P}$.

For fixed $M\in\mathcal{P}$, a matrix $U\in\mathcal{U}$ that maximizes
$\operatorname{tr}(MU)$ is the $\overline{U}$ corresponding to stochastic
vectors $\bm{p}>0$ and $M^{\top}\bm{q}>0$. An optimal $M$ to (P-Perm) may thus
be identified via ∑_i ∈R ∑_j ∈R (1 - [1 - p_j / q_i]^+) m_ij M1 = 1 M^⊤1 = 1
M∈{0, 1}^n ×n This assignment problem features discrete variables. However,
the variable coefficients in the constraints comprise a totally unimodular
matrix and the constant terms in the constraints are all integral. As such,
every optimal extreme point solution to the linear programming relaxation is
an optimal $M$ to (P-Perm) [14].

That (P-Perm) is a relaxation of (P) means there may exist a
$\widehat{U}\in\mathcal{U}$ and $\widehat{M}\in\mathcal{P}$ for which
$\operatorname{tr}(\widehat{M}\widehat{U})\geq\operatorname{tr}(\overline{U})$.
Of course, if
$\operatorname{tr}(\widehat{M}\widehat{U})>\operatorname{tr}(\overline{U})$,
it is possible that $\det(\widehat{M}\widehat{U})>\det(\overline{U})$ and,
since the absolute value of the determinant of a matrix is invariant under
permutation, $|\det(\widehat{U})|>|\det(\overline{U})|$. We demonstrate this
now in an example.

######  Example 2.

Let
$\bm{p}^{\top}=[\nicefrac{{3}}{{10}},\nicefrac{{2}}{{5}},\nicefrac{{1}}{{10}},\nicefrac{{1}}{{5}}]$
and
$\bm{q}^{\top}=[\nicefrac{{1}}{{8}},\nicefrac{{3}}{{8}},\nicefrac{{3}}{{10}},\nicefrac{{1}}{{5}}]$.
Then

$\overline{U}=\left[\begin{array}[]{cccc}1&0&0&0\\\ 0&1&0&0\\\
\nicefrac{{7}}{{12}}&\nicefrac{{1}}{{12}}&\nicefrac{{1}}{{3}}&0\\\
0&0&0&1\end{array}\right]$

is the optimal solution to (P), and

$\widehat{M}=\left[\begin{array}[]{cccc}0&0&1&0\\\ 0&1&0&0\\\ 1&0&0&0\\\
0&0&0&1\end{array}\right],~{}\widehat{U}=\left[\begin{array}[]{cccc}0&\nicefrac{{1}}{{5}}&\nicefrac{{4}}{{5}}&0\\\
0&1&0&0\\\ 1&0&0&0\\\ 0&0&0&1\end{array}\right]$

are the optimal solution to (P-Perm). For this example, we have
$\operatorname{tr}(\widehat{M}\widehat{U})=\nicefrac{{19}}{{5}}>\nicefrac{{10}}{{3}}=\operatorname{tr}(\overline{U})$
and
$|\det(\widehat{U})|=\nicefrac{{4}}{{5}}>\nicefrac{{1}}{{3}}=|\det(\overline{U})|$.
The simplices associated with $\overline{U}$ and $\widehat{U}$ are illustrated
in Figure 1. Indeed, the simplex associated with $\widehat{U}$ has a visibly
larger volume than that associated with $\overline{U}$.

Figure 1: The simplices associated with $\overline{U}$ (left) and
$\widehat{U}$ (right) from Example 2.

##  Application

Let $X$ be a random variable (RV) with support $\Omega$ and associated CDF
$F(x)$. We wish to synthesize conditional CDFs with respect to a discrete RV
$Y$ with support $\mathcal{N}=\\{1,2,\ldots,n\\}$ according to

$F(x\,|\,Y=i)=S_{i}(F(x)),\quad\forall i\in\mathcal{N}.$ (4)

Now define $p_{i}=\operatorname{Pr}(Y=i)$. Also, define
$\bm{p}=[p_{1},p_{2},\ldots,p_{n}]^{\top}$, and
$\bm{S}(z)=[S_{1}(z),S_{2}(z),\ldots,S_{n}(z)]^{\top}$. For such synthesized
conditional CDFs to be coherent, $\bm{p}$ and $\bm{S}(z)$ must satisfy

$\displaystyle\bm{p}^{\top}\geq\bm{0},$ (5)
$\displaystyle\bm{p}^{\top}\bm{1}=1,$ (6) $\displaystyle\bm{S}(0)=\bm{0},$ (7)
$\displaystyle\bm{S}(1)=\bm{1},$ (8)
$\displaystyle\bm{S}(z)\leq\bm{S}(\hat{z}),$ $\displaystyle\forall
z,\hat{z}\in[0,1],z\leq\hat{z},$ (9) $\displaystyle\bm{p}^{\top}\bm{S}(z)=z,$
$\displaystyle\forall z\in[0,1].$ (10)

Conditions (5) and (6) are simply the first two axioms of probability.
Conditions (7)-(9) ensure for each $i\in\mathcal{N}$ that $S_{i}(F(x))$ is the
CDF of an RV with support $\Omega_{i}\subseteq\Omega$. Condition (10),
equivalent to $\bm{p}^{\top}\bm{S}(F(x))=F(x),\forall x\in\Omega$, is the law
of total probability.

Suppose there exist independent RVs $X_{1},X_{2},\ldots,X_{m}$ all identically
distributed according to $F(x)$. Essentially, we wish to partition the RVs
into sets enumerated $i=1,\ldots,n$ with relative sizes $p_{1},\ldots,p_{n}$,
and then synthesize conditional CDFs to force a distinction between RVs from
different sets while retaining $F(x)$ as the marginal CDF.

As we showed in our original work on this application [15], and as we show in
the sequel, one may identify with little effort special cases of $\bm{p}$ and
$S(z)$ that satisfy (5)-(10). However, the question that motivates
$\mathcal{U}$ and $\overline{U}$ pertains to more general cases. Specifically,
for any given $\bm{p}$ that satisfies (5) and (6), do there exist unique
$S_{i}(z),\forall i\in\mathcal{N}$ that satisfy (7)-(10)? If so, which exhibit
maximum distinguishability (a notion we discuss further after the following
theorem)?

######  Theorem 15.

Suppose $\bm{p}>\bm{0}$ and $\bm{S}(z)$ satisfy (5)-(10), and let
$\bm{q}>\bm{0}$ be a given vector that satisfies (5) and (6). Then for any
$U\in\mathcal{U}$, $\bm{q}$ and $\bm{T}(z)=U\bm{S}(z)$ satisfy (7)-(10).

###### Proof.

Given $\bm{S}(0)=\bm{0}$, it follows that ${\bm{T}(0)=U\bm{S}(0)=\bm{0}}$.
Given $\bm{S}(1)=\bm{1}$ and $U\bm{1}=\bm{1}$, it follows that
${\bm{T}(1)=U\bm{S}(1)=U\bm{1}=\bm{1}}$. That $U\bm{1}=\bm{1}$ and $U\geq 0$
means that each $T_{i}(z)$ is a convex combination of functions that are
nondecreasing on $z\in[0,1]$. Each $T_{i}(z)$ is, as such, also nondecreasing
on $z\in[0,1]$. Finally, recall that ${\bm{q}^{\top}U=\bm{p}^{\top}}$. Given
$\bm{p}^{\top}\bm{S}(z)=z$, it follows that
${\bm{q}^{\top}\bm{T}(z)=\bm{q}^{\top}U\bm{S}(z)=\bm{p}^{\top}\bm{S}(z)=z}$. ∎

This theorem guarantees that for any given $\bm{q}$ that satisfies (5) and (6)
there exists a $\bm{T}(z)$ that satisfies (7)-(10) provided
${\mathcal{U}\neq\varnothing}$ and there exist $\bm{p}$ and $\bm{S}(z)$ that
satisfy (5)-(10). Of course,
$\overline{U}\in\mathcal{U}\implies\mathcal{U}\neq\varnothing$. Additionally,
note that $\overline{U}$ maximizes the contribution of $S_{i}(z)$ to
$T_{i}(z)$ in the mapping $\bm{T}(z)=U\bm{S}(z)$. So if
$S_{i}(z),i=1,\ldots,n$ are distinguishable in the sense that $S_{i}(z)\geq
S_{i+1},\forall z\in[0,1]$ and
$\int_{0}^{1}\left(S_{i}(z)-S_{i+1}(z)\right)\mathop{}\\!\mathrm{d}z>0$ for
all $1\leq i<n$, mapping $\bm{S}(z)$ to $\bm{T}(z)$ via $\overline{U}$ in a
sense maximizes the distinguishability of $T_{i}(z),i=1,\ldots,n$. Regarding
the existence of $\bm{p}$ and $\bm{S}(z)$ that satisfy (5)-(10), we now
present a pair of examples.

First, for $i=1,\ldots,n$ let $p_{i}=1/n$ such that $\bm{p}$ satisfies (5) and
(6), and let $S_{i}(z)$ be the CDF of the continuous uniform distribution with
support interval $[\frac{i-1}{n},\frac{i}{n})$:

$S_{i}(z)=\begin{cases}0,&z<\frac{i-1}{n},\\\ nz-(i-1),&\frac{i-1}{n}\leq
z<\frac{i}{n},\\\ 1,&\frac{i}{n}\leq z.\end{cases}$ (11)

Since each $S_{i}(z)$ is a CDF, $\bm{S}(z)$ satisfies (7)-(9). For any
$\hat{z}\in[0,1)$, ${\exists!~{}\hat{i}\in\\{1,2,\ldots,n\\}}$ such that
$\hat{z}\in[\frac{\hat{i}-1}{n},\frac{\hat{i}}{n})$. So ${S_{i}(\hat{z})=1}$
for ${i\in\\{1,\ldots,\hat{i}-1\\}}$,
${S_{\hat{i}}(\hat{z})=n\hat{z}-(\hat{i}-1)}$, and ${S_{i}(\hat{z})=0}$ for
${i\in\\{\hat{i}+1,\ldots,n\\}}$. Ergo,

$\bm{p}^{\top}\bm{S}(z)=\frac{1}{n}\left[(\hat{i}-1)\cdot
1+nz-(\hat{i}-1)+(n-\hat{i})\cdot 0\right]=z,$

so $\bm{p}$ and $\bm{S}(z)$ also satisfy (10).

Clearly, ${S_{1}(z)\geq S_{2}(z)\geq\cdots\geq S_{n}(z)}$. The 1-Wasserstein
distance measured between consecutive transformations is

$\displaystyle\int_{0}^{1}\\!\left(S_{i}(z)-S_{i+1}(z)\right)\mathop{}\\!\mathrm{d}z$
$\displaystyle=\int_{\frac{i-1}{n}}^{\frac{i}{n}}\\!\left(nz-(i-1)\right)\mathop{}\\!\mathrm{d}z+\int_{\frac{i}{n}}^{\frac{i+1}{n}}\\!\left(nz-i\right)\mathop{}\\!\mathrm{d}z$
$\displaystyle=n\int_{\frac{i-1}{n}}^{\frac{i}{n}}\\!\left(z-\tfrac{i-1}{n}\right)\mathop{}\\!\mathrm{d}z+n\int_{\frac{i}{n}}^{\frac{i+1}{n}}\\!\left(z-\tfrac{i}{n}\right)\mathop{}\\!\mathrm{d}z$
$\displaystyle=2n\int_{0}^{\frac{1}{n}}z\mathop{}\\!\mathrm{d}z$
$\displaystyle=\frac{1}{n}.$

That is, $S_{1}(z),S_{2}(z),\ldots,S_{n}(z)$ are equally spaced according to
the $1$-Wasserstein distance.

Second, we consider $S_{i}(z)$ based on the CDFs of beta distributions. Note
that the probability density function (PDF) for a beta distribution with
integer parameters $i$ and $n-i+1$ is

$\displaystyle
f(z;i,n-i+1)=\\!\binom{n}{i}iz^{i-1}(1-z)^{n-i}=\\!\sum_{j=0}^{n-i}\binom{n}{i}\binom{n-i}{j}i(-1)^{j}z^{i+j-1},$

For $i=1,\ldots,n$ again let $p_{i}=1/n$, and let

$S_{i}(z)=F(z;i,n-i+1)=\sum_{j=0}^{n-1}\binom{n}{i}\binom{n-i}{j}\left(\frac{i}{i+j}\right)(-1)^{j}z^{i+j}.$
(12)

Again, since each $S_{i}(z)$ is a CDF, $\bm{S}(z)$ satisfies (7)-(9). Also,

$\displaystyle\bm{p}^{\top}\bm{S}(z)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=0}^{n-i}\binom{n}{i}\binom{n-i}{j}\left(\frac{i}{i+j}\right)(-1)^{j}z^{i+j}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\sum_{k=i}^{n}\binom{n}{i}\binom{n-i}{k-i}\left(\frac{i}{k}\right)(-1)^{k-i}z^{k}$
$\displaystyle=\frac{1}{n}\sum_{k=1}^{n}\sum_{i=1}^{k}\binom{n}{i}\binom{n-i}{k-i}\left(\frac{i}{k}\right)(-1)^{k-i}z^{k}$
$\displaystyle=\frac{1}{n}\sum_{k=1}^{n}\left(\sum_{i=1}^{k}\binom{k-1}{i-1}(-1)^{-i}\right)\binom{n}{k}(-1)^{k}z^{k}$
$\displaystyle=z$

Above, the final equality follows from the inner sum being an alternating sum
of binomial coefficients. For $k>1$, the inner sum is zero. For $k=1$, the
inner sum is $-1$. Hence, $\bm{p}$ and $\bm{S}(z)$ satisfy (10).

Since $F(z;\alpha,\beta)\geq F(z;\alpha^{\prime},\beta^{\prime}),\forall
z\in[0,1]$ if and only if $\alpha\leq\alpha^{\prime}$ and
$\beta\geq\beta^{\prime}$ [16, 17], we have $S_{1}(z)\geq
S_{2}(z)\geq\cdots\geq S_{n}(z)$. The beta distribution is related to the
Bernstein basis polynomials. Let
$b_{i}^{n}(z)=\binom{n}{i}z^{i}(1-z)^{n-i},i=0,\ldots,n$ be the $n+1$
degree-$n$ Bernstein basis polynomials [18]. Then,
${S_{i}(z)=F(z;i,n-i+1)=n\int_{0}^{z}b_{i-1}^{n-1}(z^{\prime})\mathop{}\\!\mathrm{d}z^{\prime}}$.
Following properties of indefinite and definite integrals of Bernstein basis
polynomials, the 1-Wasserstein distance measured between consecutive
transformations is

$\displaystyle\int_{0}^{1}\left(S_{i}(z)-S_{i+1}(z)\right)\mathop{}\\!\mathrm{d}z$
$\displaystyle=\int_{0}^{1}\int_{0}^{z}\left(nb_{i-1}^{n-1}(z^{\prime})-nb_{i}^{n-1}(z^{\prime})\right)\mathop{}\\!\mathrm{d}z^{\prime}\mathop{}\\!\mathrm{d}z$
$\displaystyle=\int_{0}^{1}\left(\sum_{j=i}^{n}b_{j}^{n}(z)-\sum_{j=i+1}^{n}b_{j}^{n}(z)\right)\mathop{}\\!\mathrm{d}z$
$\displaystyle=\int_{0}^{1}b_{i}^{n}(z)\mathop{}\\!\mathrm{d}z$
$\displaystyle=\frac{1}{n+1}.$

Again, $S_{1}(z),S_{2}(z),\ldots,S_{n}(z)$ are equally spaced according to the
$1$-Wasserstein distance.

We now conclude this section with an example that demonstrates how solutions
to (P) or (P-Perm) are applied to synthesize conditional probability
distributions as we described.

######  Example 3.

Let
$\bm{p}^{\top}\\!=\\![\nicefrac{{1}}{{4}},\nicefrac{{1}}{{4}},\nicefrac{{1}}{{4}},\nicefrac{{1}}{{4}}]^{\top}$,
and
$\bm{q}^{\top}\\!=\\![\nicefrac{{1}}{{3}},\nicefrac{{1}}{{9}},\nicefrac{{1}}{{2}},\nicefrac{{1}}{{18}}]^{\top}$.
For these vectors, the matrices

$\overline{U}=\left[\begin{array}[]{cccc}\nicefrac{{3}}{{4}}&\nicefrac{{5}}{{48}}&0&\nicefrac{{7}}{{48}}\\\
0&1&0&0\\\ 0&\nicefrac{{5}}{{24}}&\nicefrac{{1}}{{2}}&\nicefrac{{7}}{{24}}\\\
0&0&0&1\end{array}\right]~{}\text{and}~{}\widehat{U}=\left[\begin{array}[]{cccc}0&0&\nicefrac{{3}}{{4}}&\nicefrac{{1}}{{4}}\\\
0&0&0&1\\\ \nicefrac{{7}}{{18}}&\nicefrac{{1}}{{2}}&0&\nicefrac{{1}}{{9}}\\\
1&0&0&0\end{array}\right]$

are optimal solutions to (P) and (P-Perm), respectively. To accompany
$\bm{p}$, for $n=4$ we consider $\bm{S}^{\text{UD}}(z)$ based on continuous
uniform distributions as defined in (11) and also $\bm{S}^{\text{BD}}(z)$
based on beta distributions as defined in (12). Finally, let $F(x)=\Phi(x)$,
the CDF of a standard normal distribution.

We show $\bm{S}\textsuperscript{UD}(z)$,
${\overline{\bm{T}}\textsuperscript{UD}(z)=\overline{U}\bm{S}\textsuperscript{UD}(z)}$,
${\widehat{\bm{T}}\textsuperscript{UD}(z)=\widehat{U}\bm{S}\textsuperscript{UD}(z)}$,
$\bm{S}\textsuperscript{BD}(z)$,
${\overline{\bm{T}}\textsuperscript{BD}(z)=\overline{U}\bm{S}\textsuperscript{BD}(z)}$,
${\widehat{\bm{T}}\textsuperscript{BD}(z)=\widehat{U}\bm{S}\textsuperscript{BD}(z)}$,
as well as their application to synthesizing conditional probability
distributions based on $F(x)$ in Figure 2.

The piecewise-linearity of each $S_{i}^{\text{UD}}(z)$ leads to the
perturbations of $F(x)$, a smooth function, being non-smooth. In contrast,
that each $S_{i}^{\text{UD}}(z)$ is a polynomial leads to the perturbations of
$F(x)$ being smooth. Additionally, each $S_{i}^{\text{UD}}(z)$ is non-
increasing on portions of the unit interval whereas each
$S_{i}^{\text{BD}}(z)$ is strictly increasing. In the context of our
application, the consequence is that the support set associated with
$S_{i}^{\text{UD}}(F(x))$ is $\Omega_{i}\subset\Omega$ whereas that associated
with $S_{i}^{\text{BD}}(F(x))$ is $\Omega_{i}=\Omega$.

Applying $\widehat{U}$ leads to relatively larger 1-Wasserstein distances
between the consecutive conditional CDFs, as seen on the right side of Figure
2. However, the orientation of $\widehat{U}$ leads to those CDFs having a
different order, which may not ideal for certain applications of the method.
While $\overline{U}$ does a more modest job of separating the conditional
CDFs, its orientation maintains the ordering.

Figure 2: The transformations (left column) from Example 3 and their
application to synthesizing conditional CDFs based on $F(x)$ (right column).

##  Conclusion

We presented an optimization model involving simplices that have a given
barycenter and that are enclosed by the standard simplex. We presented the
analytical form of an optimal solution to the model, and the conditions under
which it is the unique optimal solution. We showed the solution is an inverse
$M$-matrix whose eigenvalues are the same as its diagional entries. Finally,
we demonstrated how the model and its solutions apply to the task of
synthesizing conditional cumulative distribution functions that, in tandem
with a given discrete marginal distribution, coherently preserve a given CDF.

## Competing Interests

The authors have no competing interests to declare.

## Data Availability

No data was used for the research described in the article.

## References

  * Craig [1994] M. Craig,  Minimum-volume transforms for remotely sensed data,  IEEE Transactions on Geoscience and Remote Sensing 32 (1994) 542–552.
  * Li and Bioucas-Dias [2008] J. Li, J. M. Bioucas-Dias,  Minimum Volume Simplex Analysis: A Fast Algorithm to Unmix Hyperspectral Data,  in: IGARSS 2008 - 2008 IEEE International Geoscience and Remote Sensing Symposium, volume 3, 2008, pp. III – 250–III – 253.
  * Hendrix et al. [2013] E. M. T. Hendrix, I. García, J. Plaza, A. Plaza,  On the minimum volume simplex enclosure problem for estimating a linear mixing model,  Journal of Global Optimization 56 (2013) 957–970.
  * Lombardi et al. [2009] W. Lombardi, S. Olaru, S. I. Niculescu,  Invariant sets for a class of linear systems with variable time-delay,  in: 2009 European Control Conference (ECC), 2009, pp. 4757–4762.
  * Kuti et al. [2014] J. Kuti, P. Galambos, P. Baranyi,  Minimal Volume Simplex (MVS) approach for convex hull generation in TP Model Transformation,  in: IEEE 18th International Conference on Intelligent Engineering Systems INES 2014, 2014, pp. 187–192.
  * Tordesillas and How [2022] J. Tordesillas, J. P. How,  MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial Curves,  Computer-Aided Design 151 (2022) 103341.
  * Douik and Hassibi [2019] A. Douik, B. Hassibi,  Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry,  IEEE Transactions on Signal Processing 67 (2019) 5761–5774.
  * Rachev and Rüschendorf [1998] S. T. Rachev, L. Rüschendorf,  Applications of the Duality Theory,  in: Mass Transportation Problems: Volume I: Theory, Springer New York, New York, NY, 1998, pp. 275–370.
  * Karush [2014] W. Karush, Minima of Functions of Several Variables with Inequalities as Side Conditions, Springer Basel, Basel, 2014, pp. 217–245.
  * Kuhn and Tucker [2014] H. W. Kuhn, A. W. Tucker, Nonlinear Programming, Springer Basel, Basel, 2014, pp. 247–258.
  * Mangasarian [1979] O. Mangasarian,  Uniqueness of solution in linear programming,  Linear Algebra and its Applications 25 (1979) 151–162.
  * Fiedler and Pták [1962] M. Fiedler, V. Pták,  On matrices with non-positive off-diagonal elements and positive principal minors,  Czechoslovak Mathematical Journal 12 (1962) 382–400.
  * Berman and Plemmons [1994] A. Berman, R. J. Plemmons, Nonnegative matrices in the mathematical sciences, SIAM, 1994.
  * Wolsey [2020] L. A. Wolsey, Integer Programming, John Wiley & Sons, 2020.
  * Austgen et al. [2022] B. Austgen, M. Garcia, B. Pierre, J. Hasenbein, E. Kutanoglu,  Winter Storm Scenario Generation for Power Grids Based on Historical Generator Outages,  in: 2022 IEEE/PES Transmission and Distribution Conference and Exposition (T D), 2022.
  * Lisek [1978] B. Lisek,  Comparability of special distributions,  Series Statistics 9 (1978) 587–598.
  * Arab et al. [2021] I. Arab, P. E. Oliveira, T. Wiklund,  Convex transform order of Beta distributions with some consequences,  Statistica Neerlandica 75 (2021) 238–256.
  * Farouki [2012] R. T. Farouki,  The Bernstein polynomial basis: A centennial retrospective,  Computer Aided Geometric Design 29 (2012) 379–419.


# Protecting President Zelenskyy against Deep Fakes

Matyáš Boháček
Gymnasium of Johannes Kepler
Parléřova 2/118, 169 00 Praha 6, Czech Republic
<EMAIL_ADDRESS>
Hany Farid
Department of Electrical Engineering and Computer Sciences
School of Information
University of California, Berkeley
<EMAIL_ADDRESS>

###### Abstract

The 2022 Russian invasion of Ukraine is being fought on two fronts: a brutal
ground war and a duplicitous disinformation campaign designed to conceal and
justify Russia’s actions. This campaign includes at least one example of a
deep-fake video purportedly showing Ukrainian President Zelenskyy admitting
defeat and surrendering. In anticipation of future attacks of this form, we
describe a facial and gestural behavioral model that captures distinctive
characteristics of Zelenskyy’s speaking style. Trained on over eight hours of
authentic video from four different settings, we show that this behavioral
model can distinguish Zelenskyy from deep-fake imposters.This model can play
an important role – particularly during the fog of war – in distinguishing the
real from the fake.

_Keywords_ Deep fakes $\cdot$ Disinformation $\cdot$ Digital Forensics $\cdot$
Facial Mannerisms $\cdot$ Gestural Mannerisms

##  1 Introduction

In the early days of the Russian invasion of Ukraine, President Zelenskyy
warned the world that Russia’s digital disinformation machinery would create a
deep fake of him admitting defeat and surrendering. A few weeks later in mid-
March of 2022, a deep fake of Zelenskyy appeared with just this message
(Allyn, 2022). This video, Figure 1, was quickly debunked thanks to the rather
crude audio and video and to Zelenskyy’s pre-bunking. This type of deep fake,
however, is likely just the beginning of a new digital front that we might
expect in this and future conflicts.

|
---|---
Figure 1: One video frame of the real (left) and deep-fake version (right) of
Ukrainian President Zelenskyy.

A recent set of perceptual studies (Groh et al., 2022) examined the ability of
untrained observers to distinguish between real and deep-fake videos. In one
condition, participants viewed a single video and categorized it as real or
fake. Participants correctly identified $66\%$ of the deep-fake videos, as
compared to chance performance of $50\%$ (pooled responses from all
participants – so-called crowd wisdom – yields an improved accuracy of
$80\%$). In a second condition, participants were shown the prediction by the
top-performing DFDC computational model (Ferrer, 2020) and given the
opportunity to update their response. In this collaborative condition,
individual participant accuracy improved to $73\%$.

While we may have the ability to perceptually detect some deep-fake videos,
our ability is not terribly reliable and this task will become increasingly
more difficult as deep fakes continue to improve in quality and
sophistication. We must, therefore, turn to computational methods to assist in
the task of distinguishing the real from the fake.

The computational detection of deep-fake videos can be partitioned into three
basic categories: (1) learning-based, in which features that distinguish real
from fake content are explicitly learned by any of a range of different
machine-learning techniques (Zhou et al., 2017; Afchar et al., 2018; Li et
al., 2019); (2) artifact-based, in which a range of low-level (pixel based) to
high-level (semantic based) features are explicitly designed to distinguish
between real and fake content (Li et al., 2018; Agarwal and Farid, 2021;
Agarwal et al., 2020a); and (3) identity-based, in which biometric-style
features are used to identify if the person depicted in a video is who it
purports to be (Agarwal et al., 2019, 2020b, 2021; Cozzolino et al., 2021).

The advantage of learning-based approaches is they are able to learn detailed
and subtle video-synthesis artifacts. The disadvantage is these techniques
often struggle to generalize to new content not explicitly part of the
training data set, and can be vulnerable to adversarial attacks (Carlini and
Farid, 2020), and simple laundering attacks where the synthesized media is
trans-coded or resized (Barni et al., 2018). In the 2019-2020 Deepfake
Detection Challenge (Ferrer, 2020), for example, $2116$ teams competed for one
million dollars (USD) in prizes. Teams were provided $23,654$ real videos and
$104,500$ deep-fake videos created from the provided real videos. The top
performing learning-based detector achieved a detection accuracy of only
$65\%$ on a set of $4000$ holdout videos, half of which were real and half of
which were deep fakes (i.e., chance performance is $50\%$). These results
reveal that fully automatic detection of deep fakes in the wild remains a
challenging problem.

On the other hand, the advantage of artifact-based techniques is they can
exploit inconsistencies that are difficult to circumvent or launder. The
disadvantage is these techniques are typically narrowly applicable to a subset
of deep-fake videos, and often require human annotation as part of the
process.

The advantage of identity-based techniques is they are also resilient to
adversarial and laundering attacks and are typically applicable to many
different forms of deep fakes. The disadvantage of these approaches is an
identity-specific model must be constructed for each individual, typically
from hours of authentic video footage. This may be practical when it comes to,
for example, protecting a few world leaders from deep fakes – for which hours
of video can typically be found online – but is otherwise impractical. The
other disadvantage is that the learned mannerisms are somewhat context
dependent: when a world leader is giving a public address, for example, she
may be more formal than when she is giving an unscripted interview, and so the
specific mannerisms may not generalize across different contexts.

Because we are focused here on protecting one world leader – Ukrainian
President Zelenskyy – and because we can easily acquire hours of video of
Zelenskyy, we contend that an identity-based approach is the most sensible and
robust approach. We start with the identity-based technique of (Agarwal et
al., 2019), leveraging distinct patterns of facial and head movements, to
distinguish Zelenskyy from an imposter or deep fake. We then augment this
identity-based model with new gestural features capturing how a speaker uses
their hands when speaking.

After reviewing the facial mannerisms portion of the model and describing the
new gestural mannerisms portion, we evaluate the efficacy of our model in
distinguishing Zelenskyy from deep-fake Zelenskyy and a range of other
identities.

(a) | (b) | (c) | (d)
---|---|---|---
|  |  |
Figure 2: Four representative examples of President Zelenskyy in different
contexts: (a) public address; (b) press briefing; (c) bunker; and (d)
armchair.

##  2 Methods

###  2.1 Data Set

We downloaded $506$ minutes of video of Zelenskyy from YouTube and the
official website of the office of the Ukranian
president111https://www.president.gov.ua/en/videos/videos-archive in four
different contexts: (a) public address ($91$ min); (b) press briefing ($207$
min); (c) bunker ($47$ min); and (d) armchair ($161$ min). Shown in Figure 2
are representative examples from each of these settings.

Portions of each video with large camera motions (e.g., zoom, translation,
cross-fade) were automatically detected and removed from the data set. In
particular, the inter-frame difference was computed between each successive
pair of video frames. Assuming each video depicts a speaker in the center of
the frame, a camera motion was detected if the absolute difference on the left
and right margin (defined as $10\%$ of the frame width) was above a specified
threshold.

A total of $57$ minutes of interview-style videos of seven world leaders
(Jacinda Ardern, Joe Biden, Kamala Harris, Boris Johnson, Wladimir Klitschko,
Angela Merkel, and Vladimir Putin) were used as decoys (i.e., not Zelenskyy).
Our deep-fake detection is designed to distinguish Zelenskyy’s behavioral and
gestural mannerisms from imposters driving the creation of a deep fake, and so
these decoy videos – regardless of the identities – serve as proxies for deep
fakes. An additional $50$ minutes of video across $27$ distinct individuals
taken from the FaceForensics++ (Rössler et al., 2019) dataset were used as
additional decoys. In addition to these proxies, three commissioned lip-sync
deep fakes ($2$ min) created by the team at
Colossyan222https://www.colossyan.com, and one in-the-wild deep fake ($1$ min)
were added to this decoy dataset (Figure 1).

|  |  |  |
---|---|---|---|---

---

Figure 3: Shown above are five equally-spaced and cropped frames from a
$10$-second video clip annotated with the estimated facial landmarks (red
markers) and head pose (blue box). Shown below are two of the $16$ action
units as a function of time (inner brow raiser [AU01] and lid tightener
[AU07]).

###  2.2 Facial Mannerisms

The identity-based forensic technique of (Agarwal et al., 2019) is based on
the observation that individuals have distinct speaking styles in terms of
facial expressions and head movements. Former President Obama, for example,
tends to tilt his head upwards when he smiles, and downwards when he frowns.

Starting with a single video as input, the OpenFace2 toolkit (Baltrusaitis et
al., 2018) extracts facial landmark positions, facial action units, head pose,
and eye gaze on a per-frame basis. Facial muscle movement and expression are
encoded using facial action units (AU) (Ekman and Friesen, 1976). The
OpenFace2 toolkit provides – on a per-frame basis – the strength of $17$
different AUs: inner brow raiser (AU01), outer brow raiser (AU02), brow
lowerer (AU04), upper lid raiser (AU05), cheek raiser (AU06), lid tightener
(AU07), nose wrinkler (AU09), upper lip raiser (AU10), lip corner puller
(AU12), dimpler (AU14), lip corner depressor (AU15), chin raiser (AU17), lip
stretcher (AU20), lip tightener (AU23), lip part (AU25), jaw drop (AU26), and
eye blink (AU45).

The forensic facial model incorporates $16$ AUs (AU45, eye blink, was found
not to be distinctive and therefore eliminated from consideration) and four
additional features: (1) head rotation about the x-axis; (2) head rotation
about the z-axis (as with AU45, head rotation about the y-axis was found not
to be distinctive); (3) the horizontal distance between the corners of the
mouth (mouthh); and (4) the vertical distance between the lower and upper lip
(mouthv), yielding a total of $20$ facial-mannerism features. Shown in Figure
3 are several frames of the facial and head tracking and two representative
examples of the measured action units across a $10$-second clip.

These features are combined with gestural mannerisms, described next, to form
a person-specific behavioral model.

|  |  |  |
---|---|---|---|---

---

Figure 4: Shown above are five equally-spaced frames from a $10$-second video
clip annotated with the estimated gestural tracking. Shown below are two of
the $12$ gestural features corresponding to the vertical position of the left
and right wrist (the spatial position of the wrists are reported in normalized
units relative to a body-centric action plane).

###  2.3 Gestural Mannerisms

Across cultures and languages, hand gestures provide additional information
not always captured by a speaker’s words alone (Church et al., 2017). In
addition to distinct gestural patterns found across age (Özer D. et al.,
2017), sex (Özçalışkan and Goldin-Meadow, 2010), and culture (Pika et al.,
2006), recent work also finds that individuals exhibit distinct gestural
patterns (Özer D and T., 2020). We, therefore, hypothesize that hand gestures,
in addition to the facial expressions and head movements described above, will
improve our ability to identify an individual’s distinct speaking patterns.

Arm and hand position and movement are estimated in each input video frame
using Blazepose (Bazarevsky et al., 2020) from the MediaPipe library (Lugaresi
et al., 2019). Because we are interested only in the upper body, we consider
the image $x$-, $y$-coordinates corresponding to the shoulder, elbow, and
wrist of both arms, Figure 4, yielding a total of $12$ individual
measurements. These upper-body coordinates, initially specified relative to
the video-frame size, are normalized into a speaker-centric action plane
(Boháček and Hrúz, 2022). This action plane is a rectangular bounding box
centered on the speaker’s chest with a width $8\times$ and height $6\times$
the measured head height (De Silva, 2008; Bauer, 2014). In this normalized
bounding box, the upper left-hand corner is $(0,0)$ and the lower right-hand
corner is $(1,1)$. This normalization ensures that the tracked upper-body
coordinates can be compared across different speaker locations and sizes.
Shown in Figure 4 are several frames of the upper-body tracking and
representative examples of the extracted gestural features across a
$10$-second clip.

Whereas the tracked $x,y$ facial features are converted into a higher-level
representation in the form of action units, we find that a similar approach
with the hand gestures was less effective than simply considering the
normalized $x,y$ locations of the tracked shoulders, elbows, and wrists.

###  2.4 Behavioral Model

Correlations between all pairs of the $20$ facial features and $12$ gestural
features are used to capture individualized mannerisms (e.g., head tilt and
smiling/frowning). A total of $~{}_{32}C_{2}=(32\times 31)/2=496$ correlations
are extracted from overlapping $10$-second video clips extracted from an input
video in question.

Trained on authentic video of a person of interest, a novelty detection model
in the form of a one-class, non-linear support vector machine (SVM) (Schölkopf
et al., ; Pedregosa et al., 2011) is used to distinguish an individual from
imposters and deep fakes. An advantage of this classifier is that it only
requires examples of authentic videos.

The $506$ minutes of Zelenskyy video is partitioned into overlapping (by $5$
seconds) $10$-second video clips, yielding a total of $157,752$ clips. The
$110$ minutes of other identities in the World Leaders, FaceForensics++, and
Deep-Fake Zelenskyy videos are similarly partitioned, yielding a total of
$25,077$ clips.

These clips are randomly partitioned into a $80/20$ training/testing split.
The SVM is trained on the $496$ facial- and gestural-feature pairwise
correlations. The SVM hyper-parameters, consisting of the Gaussian kernel
width ($\gamma$) and outlier percentage ($\nu$), are optimized by performing a
grid search over these parameters across the training set. The trained
classifier is then evaluated against the hold-out testing set. This entire
process is repeated $100$ times with randomized training/testing splits, from
which we report average classification accuracy.

Three different classifiers are trained on facial features only, gestural
features only, and facial and gestural features combined. The SVM
classification threshold for the individual features is selected to yield a
$95\%$ training accuracy of correctly classifying real Zelenskyy clips. The
classification threshold for the combined features is selected to yield a
$99\%$ training accuracy.

##  3 Results

Shown in Table 1 is the classification accuracy (averaged over $100$ random
training/testing data splits) of our behavioral model evaluated against the
$10$-second video clips of seven different world-leaders, $28$ distinct
identities in the FaceForensics++ dataset (Rössler et al., 2019), and real and
deep-fake versions of Zelenskyy.

We find that the facial features and gestural features alone are insufficient
to consistently detect deep-fake version of Zelenskyy (see the last two
columns of Table 1). The combination of facial and gestural, however, yields
significant improvements in detection accuracy. Because deep-fake techniques
are – rightfully – focused on high-quality facial and audio synthesis, and
because of the expected difficulty in synthesizing realistic hands and hand
gestures, we posit that the combination of facial and gestural signals will
prove reliable for at least a few years.

As compared to the best-performing DFDC model (last row of Table 1)
(Seferbekov, 2020), our model achieves significantly higher classification
across all non-Zelenskyy data sets. This comparison, however, is not entirely
fair as our behavioral model is trained to detect deep-fake versions of just
one identity, whereas the DFDC model is a generic deep-fake detector. On the
other hand, our classifier operates on $10$-second video clips whereas the
DFDC model has the advantage of operating on the entire video. This comparison
does, nevertheless, show the power of identity-specific models.

|  |  |  | Lip-Sync | In-The-Wild
---|---|---|---|---|---
| World |  | Real | Deep-Fake | Deep-Fake
Model | Leaders | FF++ | Zelenskyy | Zelenskyy | Zelenskyy
facial | $91.7$ | $91.1$ | $94.7$ | $17.4$ | $83.9$
gestural | $77.4$ | $95.7$ | $95.0$ | $12.1$ | $33.3$
facial + gestural | $100.0$ | $100.0$ | $97.1$ | $94.9$ | $100.0$
DFDC | $73.1$ | $84.5$ | $93.5$ | $13.3$ | $1.7$
Table 1: Classification accuracy (reported as percentages) for our behavioral
model with facial, gestural, and these two features combined evaluated against
seven different world leaders, $28$ identities in the FaceForensics++ dataset
and against both real and deep-fake versions of Zelenskyy. By comparison, our
model significantly outperforms the best-performing DFDC model (Seferbekov,
2020).

###  3.1 Ablation

To determine how many of the $496$ pairwise facial and gestural correlations
are needed to achieve the classification accuracy reported in Table 1, we
trained a series of one-class SVMs on randomly selected subsets – ranging in
size between $10$ and $400$ – of all facial and gestural features. Shown in
Figure 5 is the median accuracy of classifying the identities in the world
leaders and deep-fake Zelenskyy videos. In this figure, each data point
corresponds to the median accuracy ($50\%$ quantile) from $25$ independent and
randomly selected features of each subset size; the error bars correspond to
the $25\%$ and $75\%$ quantile.

With the full set of $496$ facial and gestural features, detection accuracy is
$99.88\%$. Detection accuracy grows relatively linearly between feature
subsets of size $10$ and $300$ plateauing at $99.52\%$ with $400$ features.
Here we see that a significant fraction of the facial and gestural features
are, collectively, rich and informative.

Figure 5: Each data point corresponds to the median ($50\%$ quantile) accuracy
for classifiers trained on between $10$ and $496$ randomly selected facial and
gestural features; the error bars correspond to the $25\%$ and $75\%$
quantile.

To determine which specific facial and gestural features are most
discriminative, we next trained $500$ classifiers on random feature subsets of
size $10$. The discriminatory power of each feature is computed from the
average accuracy of each classifier to which a feature contributed. Across all
$500$ classifiers, the detection accuracy on the world leaders and deep-fake
Zelenskyy data sets ranges from $44.4\%$ to $4.3\%$. The top $20$ most
discriminative correlation features and respective classifier accuracy are:

Feature 1 |  | Feature 2 | Classifier Accuracy ($\%$)
---|---|---|---
head-pose-Rx | $\Leftrightarrow$ | right-elbow-y | $44.4$
head-pose-Rx | $\Leftrightarrow$ | right-wrist-y | $36.9$
head-pose-Rx | $\Leftrightarrow$ | left-elbow-y | $33.7$
left-elbow-x | $\Leftrightarrow$ | left-shoulder-x | $32.8$
head-pose-Rx | $\Leftrightarrow$ | left-shoulder-y | $32.5$
head-pose-Rx | $\Leftrightarrow$ | lip-vertical | $29.3$
left-elbow-x | $\Leftrightarrow$ | right-elbow-y | $27.4$
right-elbow-y | $\Leftrightarrow$ | right-shoulder-y | $27.4$
right-elbow-x | $\Leftrightarrow$ | right-shoulder-x | $27.3$
head-pose-Rx | $\Leftrightarrow$ | left-wrist-y | $26.9$
AU14 | $\Leftrightarrow$ | AU17 | $26.2$
AU06 | $\Leftrightarrow$ | right-elbow-y | $25.6$
mouthv | $\Leftrightarrow$ | AU14 | $25.5$
AU12 | $\Leftrightarrow$ | AU15 | $25.4$
AU12 | $\Leftrightarrow$ | AU14 | $25.0$
right-elbow-y | $\Leftrightarrow$ | left-shoulder-y | $25.0$
pose-Rz | $\Leftrightarrow$ | right-shoulder-x | $24.4$
mouthv | $\Leftrightarrow$ | AU15 | $23.7$
pose-Rx | $\Leftrightarrow$ | right-shoulder-y | $23.0$
AU06 | $\Leftrightarrow$ | AU14 | $22.7$

where *-Rx and *-Rz correspond to 3-D head rotations, *-x and *-y correspond
to the horizontal and vertical image position, and AU* corresponds to specific
facial action units (see Section 2.2). Here we see that the correlation
between head rotation and hand gestural features are the most discriminative,
highlighting the importance of the addition of gestural features to the
original facial-based model. For President Zelenskyy, in particular, head
rotation (as in nodding affirmatively) is highly correlated to his hand
movements.

As compared to the median accuracy of $8.4\%$ across random features of subset
size $10$ (Figure 5), these top-ranked features achieve accuracies between
three and five times higher. A single classifier trained on the top $10$ and
$20$ features, however, only yields a prediction accuracy on the world leaders
and deep-fake Zelenskyy data sets of $59.2\%$ and $63.4\%$, providing further
evidence that a full set of facial and gestural features are necessary to
achieve a high classification accuracy.

##  4 Discussion

Although the term deep fakes first splashed on the screen in 2017, the
precursor to what we now call deep fakes dates back two decades. In the
seminal video-rewrite work Bregler et al. (1997), a video of a person speaking
is automatically modified to yield a video of them saying things not found in
the original footage. The resulting video quality and resolution were
generally lower than today’s deep-fake videos, but the results were
nevertheless impressive. Some $25$ years later, deep neural networks, GANs,
massive data sets, and unlimited compute cycles have led to increasingly more
realistic and sophisticated deep-fake videos.

While the democratization of access to techniques for manipulating and
synthesizing videos has led to interesting and entertaining applications, they
have also given rise to complex ethical and legal question Chesney and Citron
(2019). In the fog of war, in particular, deep fakes pose a significant threat
to our ability to understand and respond to rapidly evolving events.

While our approach to protecting a single individual – Ukrainian President
Zelenskyy – does not address the broader issue of deep fakes, it does bring
some level of digital protection to the arguably most important Ukrainian
voice at this time of war.

## Acknowledgement

We are grateful to Zoltan Kovacs, Muhammad Shahzaib Aslam, and the rest of the
Colossyan team for creating the Zelenskyy lip-sync deep fakes.

## References

  * Allyn [2022] Bobby Allyn.  Deepfake video of Zelenskyy could be ‘tip of the iceberg’ in info war, experts warn.  https://www.npr.org/2022/03/16/1087062648/deepfake-video-zelenskyy-experts-war-manipulation-ukraine-russia, 2022\.
  * Groh et al. [2022] Matthew Groh, Ziv Epstein, Chaz Firestone, and Rosalind Picard.  Deepfake detection by human crowds, machines, and machine-informed crowds.  _Proceedings of the National Academy of Sciences_ , 119(1), 2022.
  * Ferrer [2020] Cristian Canton Ferrer.  Deepfake detection challenge results: An open initiative to advance AI.  https://ai.facebook.com/blog/deepfake-detection-challenge-results-an-open-initiative-to-advance-ai, 2020\.
  * Zhou et al. [2017] Peng Zhou, Xintong Han, Vlad I. Morariu, and Larry S. Davis.  Two-stream neural networks for tampered face detection.  In _International Conference on Computer Vision and Pattern Recognition_ , 2017.
  * Afchar et al. [2018] Darius Afchar, Vincent Nozick, Junichi Yamagishi, and Isao Echizen.  MesoNet: A compact facial video forgery detection network.  In _IEEE International Workshop on Information Forensics and Security_ , 2018.
  * Li et al. [2019] Lingzhi Li, Jianmin Bao, Ting Zhang, Hao Yang, Dong Chen, Fang Wen, and Baining Guo.  Face X-ray for more general face forgery detection.  arXiv:1912.13458, 2019.
  * Li et al. [2018] Yuezun Li, Ming-Ching Chang, and Siwei Lyu.  In ictu oculi: Exposing AI created fake videos by detecting eye blinking.  In _International Workshop on Information Forensics and Security_ , pages 1–7, 2018.
  * Agarwal and Farid [2021] Shruti Agarwal and Hany Farid.  Detecting deep-fake videos from aural and oral dynamics.  In _CVPR Workshop on Media Forensics_ , pages 981–989, 2021.
  * Agarwal et al. [2020a] Shruti Agarwal, Hany Farid, Ohad Fried, and Maneesh Agrawala.  Detecting deep-fake videos from phoneme-viseme mismatches.  In _CVPR Workshop on Media Forensics_ , pages 660–661, 2020a.
  * Agarwal et al. [2019] Shruti Agarwal, Hany Farid, Yuming Gu, Mingming He, Koki Nagano, and Hao Li.  Protecting world leaders against deep fakes.  In _CVPR Workshop on Media Forensics_ , volume 1, 2019.
  * Agarwal et al. [2020b] Shruti Agarwal, Hany Farid, Tarek El-Gaaly, and Ser-Nam Lim.  Detecting deep-fake videos from appearance and behavior.  In _International Workshop on Information Forensics and Security_ , pages 1–6, 2020b.
  * Agarwal et al. [2021] Shruti Agarwal, Liwen Hu, Evonne Ng, Trevor Darrell, Hao Li, and Anna Rohrbach.  Watch those words: Video falsification detection using word-conditioned facial motion.  arXiv:2112.10936, 2021.
  * Cozzolino et al. [2021] Davide Cozzolino, Andreas Rössler, Justus Thies, Matthias Nießner, and Luisa Verdoliva.  ID-reveal: Identity-aware deepfake video detection.  In _International Conference on Computer Vision_ , pages 15108–15117, 2021.
  * Carlini and Farid [2020] Nicholas Carlini and Hany Farid.  Evading deepfake-image detectors with white-and black-box attacks.  In _CVPR Workshop on Media Forensics_ , pages 658–659, 2020.
  * Barni et al. [2018] Mauro Barni, Matthew C Stamm, and Benedetta Tondi.  Adversarial multimedia forensics: Overview and challenges ahead.  In _European Signal Processing Conference_ , pages 962–966, 2018\.
  * Rössler et al. [2019] Andreas Rössler, Davide Cozzolino, Luisa Verdoliva, Christian Riess, Justus Thies, and Matthias Nießner.  FaceForensics++: Learning to detect manipulated facial images.  In _International Conference on Computer Vision and Pattern Recognition_ , 2019.
  * Baltrusaitis et al. [2018] Tadas Baltrusaitis, Amir Zadeh, Yao Chong Lim, and Louis-Philippe Morency.  Openface 2.0: Facial behavior analysis toolkit.  In _IEEE International Conference on Automatic Face & Gesture Recognition_, pages 59–66, 2018.
  * Ekman and Friesen [1976] Paul Ekman and Wallace V Friesen.  Measuring facial movement.  _Environmental Psychology and Nonverbal Behavior_ , 1(1):56–75, 1976.
  * Church et al. [2017] R. Breckinridge Church, Marha W. Alibali, and Spencer D. Kelly.  _Why Gesture?: How the hands function in speaking, thinking and communicating_ , volume 7.  John Benjamins Publishing Company, 2017.
  * Özer D. et al. [2017] Özer D., Tansan M., Özer E. E., Malykhina K., Chatterjee A., and Göksun T.  The effects of gesture restriction on spatial language in young and elderly adults.  In _38th Annual Conference of the Cognitive Science Society_ , pages 1471––1476, 2017.
  * Özçalışkan and Goldin-Meadow [2010] Şeyda Özçalışkan and Susan Goldin-Meadow.  Sex differences in language first appear in gesture.  _Developmental Science_ , 13(5):752–760, 2010\.
  * Pika et al. [2006] Simone Pika, Elena Nicoladis, and Paula F Marentette.  A cross-cultural study on the use of gestures: Evidence for cross-linguistic transfer?  _Bilingualism: Language and Cognition_ , 9(3):319–327, 2006.
  * Özer D and T. [2020] Özer D and Göksun T.  Gesture use and processing: A review on individual differences in cognitive resources.  _Frontiers in Psycholology_ , 2020.
  * Bazarevsky et al. [2020] Valentin Bazarevsky, Ivan Grishchenko, Karthik Raveendran, Tyler Zhu, Fan Zhang, and Matthias Grundmann.  Blazepose: On-device real-time body pose tracking.  arXiv:2006.10204, 2020.
  * Lugaresi et al. [2019] Camillo Lugaresi, Jiuqiang Tang, Hadon Nash, Chris McClanahan, Esha Uboweja, Michael Hays, Fan Zhang, Chuo-Ling Chang, Ming Guang Yong, Juhyun Lee, et al.  Mediapipe: A framework for building perception pipelines.  arXiv:1906.08172, 2019.
  * Boháček and Hrúz [2022] Matyáš Boháček and Marek Hrúz.  Sign pose-based transformer for word-level sign language recognition.  In _IEEE/CVF Winter Conference on Applications of Computer Vision Workshops_ , pages 182–191, 2022.
  * De Silva [2008] Liyanage De Silva.  Audiovisual sensing of human movements for home-care and security in a smart environment.  _International Journal On Smart Sensing and Intelligent Systems_ , 1, 2008.
  * Bauer [2014] Anastasia Bauer.  _The Use of Signing Space in a Shared Sign Language of Australia_.  De Gruyter, 1 edition, 2014.
  * [29] Bernhard Schölkopf, John C. Platt, John C. Shawe-Taylor, Alex J. Smola, and Robert C. Williamson.  Estimating the support of a high-dimensional distribution.  _Neural Computation_ , 13(7):1443–1471.
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Seferbekov [2020] Selim Seferbekov.  DFDC deepfake challenge solution.  https://github.com/selimsef/dfdc_deepfake_challenge, 2020.
  * Bregler et al. [1997] Christoph Bregler, Michele Covell, and Malcolm Slaney.  Video rewrite: Driving visual speech with audio.  In _24th Annual Conference on Computer Graphics and Interactive Techniques_ , pages 353–360, 1997.
  * Chesney and Citron [2019] Bobby Chesney and Danielle Citron.  Deep fakes: A looming challenge for privacy, democracy, and national security.  _California Law Review_ , 107:1753, 2019.