# Optimality and Constructions of
Spanning Bipartite Block Designs

aShoko Chisaki, bRyoh Fuji-Hara and cNobuko Miyamoto

aDepartment of Information Systems, Osaka Institute of Technology
bFaculty of Engineering, Information and Systems, University of Tsukuba
cDepartment of Information Science, Tokyo University of Science

###### Abstract

We consider a statistical problem to estimate variables (effects) that are
associated with the edges of a complete bipartite graph
$K_{v_{1},v_{2}}=(V_{1},V_{2}\,;E)$. Each data is obtained as a sum of
selected effects, a subset of $E$. In order to estimate efficiently, we
propose a design called Spanning Bipartite Block Design (SBBD). For SBBDs such
that the effects are estimable, we proved that the estimators have the same
variance (variance balanced). If each block (a subgraph of $K_{v_{1},v_{2}}$)
of SBBD is a semi-regular or a regular bipartite graph, we show that the
design is A-optimum. We also show a construction of SBBD using an
($r,\lambda$)-design and an ordered design. A BIBD with prime power blocks
gives an A-optimum semi-regular or regular SBBD. At last, we mention that this
SBBD is able to use for deep learning.
Keywords. spanning bipartite block design, A-optimum, variance balanced,
($r,\lambda$)-design, balanced incomplete block design, ordered design, deep
learning
AMS classification. 62K05, 62K10, 05B05

##  1 Introduction

Let $V_{1}$ and $V_{2}$ be point sets, and $E$ the set of edges between the
$V_{1}$ and $V_{2}$, it is a complete bipartite graph,
$K_{v_{1},v_{2}}=(V_{1},V_{2}\,;E)$, where $\lvert V_{1}\rvert=v_{1},\lvert
V_{2}\rvert=v_{2}$. We consider a statistical problem estimating the variables
associated with $E$ from experimental data. For example, communication
capacities between two sets of cities, traffic volume between two sets of
cities, etc (see Fig. 1).

Figure 1: Image of bipartite problem

Let $\tau_{ij}$ be a variable (or an effect) to estimate corresponding to the
edge $(i,j)$, $i\in V_{1}\,\,j\in V_{2}$, of the complete bipartite graph
$K_{v_{1},v_{2}}$, and $\boldsymbol{\tau}$ be the vector of $\tau_{ij}$
arranged in the following lexicographical order:

$\boldsymbol{\tau}=(\tau_{11},\tau_{12},\ldots,\tau_{1v_{2}}\ ;\
\tau_{21},\tau_{22},\ldots,\tau_{2v_{2}}\ ;\ \cdots\ ;\
\tau_{v_{1}1},\ldots,\tau_{v_{1}v_{2}})^{t}.$ (1)

We consider the following statistical model (2) that each data $y_{i}$ is
obtained as a sum of selected effects, i.e. a subset of
$\\{\tau_{11},\tau_{12},\ldots,\tau_{v_{1}v_{2}}\\}$:

$\begin{split}&\mathbf{y}=\mathbf{X}\boldsymbol{\tau}+\boldsymbol{\epsilon}\\\
&\sum_{j=1}^{v_{2}}\tau_{ij}=0,\ \ 1\leq i\leq v_{1}\\\
&\sum_{i=1}^{v_{1}}\tau_{ij}=0,\ \ 1\leq j\leq v_{2},\end{split}$ (2)

where the data vector $\mathbf{y}=(y_{1},y_{2},\ldots,y_{N})^{t}$ is assumed
that the mean of all data was subtracted and $\boldsymbol{\epsilon}$ is a
vector of random variables of errors with N$(0,\sigma^{2})$. $X$ is a
$(0,1)$-matrix of size ($N\times v_{1}v_{2}$) such that $1$ for selected
effects and $0$ for other effects in each row. Our purpose is to estimate all
effects with high precision. The main problem here is how to design the matrix
$X$.

######  Example 1.1.

This is an example that each data is obtained as a sum of selected effects.
The effects have a bipartite graph structure. Let $v_{1}=2,v_{2}=3$.

$\begin{split}y_{1}&=\tau_{11}+\tau_{13}+\tau_{22}+\tau_{23}+\epsilon_{1}\\\
y_{2}&=\tau_{12}+\tau_{13}+\tau_{21}+\tau_{22}+\epsilon_{2}\\\ &\ \
\vdots\hskip 56.9055pt\vdots\\\
y_{N}&=\tau_{13}+\tau_{21}+\tau_{22}+\tau_{23}+\epsilon_{N}\end{split}$

$\begin{bmatrix}y_{1}\\\ y_{2}\\\ \vdots\\\
y_{N}\end{bmatrix}=\begin{bmatrix}1&0&1&0&1&1\\\ 0&1&1&1&1&0\\\ &&&\vdots&&\\\
0&0&1&1&1&1\\\ \end{bmatrix}\cdot\begin{bmatrix}\tau_{11}\\\ \tau_{12}\\\
\tau_{13}\\\ \tau_{21}\\\ \tau_{22}\\\
\tau_{23}\end{bmatrix}+\begin{bmatrix}\epsilon_{1}\\\ \epsilon_{2}\\\
\vdots\\\ \epsilon_{N}\end{bmatrix}$

There is a similar model which is a two-way factorial design having a block
factor called an incomplete split-block design, see [7]. The model is the
following:

$\boldsymbol{y}=X_{1}\boldsymbol{\alpha}+X_{2}\boldsymbol{\gamma}+X_{12}(\boldsymbol{\alpha\gamma})+X_{3}\boldsymbol{\beta}+\boldsymbol{\epsilon},$

where $X_{1},X_{2},X_{12},X_{3}$ are (0,1)-matrices having exactly one $1$ in
each row, $\boldsymbol{\alpha},\boldsymbol{\gamma}$ are vectors of main
effects, $(\boldsymbol{\alpha\gamma})$ is a vector of interaction effects of
$\boldsymbol{\alpha}$ and $\boldsymbol{\gamma}$, $\boldsymbol{\beta}$ is a
vector of block effects, and $\boldsymbol{\epsilon}$ is the error vector. In
our model, there are no main or block effects, and each data is obtained as
the sum of interaction effects within a block instead of blocking effects.
Furthermore, we insist on spreading out the interaction effects in each block
as much as possible.

In this paper, we propose a new design named spanning bipartite block design
for application to the statistical model (2) and discuss the precision of the
estimators in the designs. In Section $2$, a spanning bipartite block design
(SBBD) is defined precisely. In Section $3$, we discuss optimality of designs.
Optimality problems of new designs are discussed in [7] and [6]. We argue the
optimality of SBBD and show a design is A-optimum in a certain class. In
Section $4$, a construction of SBBD is shown using an $(r,\lambda)$-design and
an ordered design. Finally, in Section $5$, we mention the relationship
between SBBD and deep learning.

##  2 Spanning Bipartite Block Design

Let $\mathcal{B}=\\{B_{1},B_{2},\ldots,B_{N}\\}$ be a collection of subgraphs
of $K_{v_{1},v_{2}}=(V_{v_{1}},V_{v_{2}}\,;E)$ called spanning bipartite
blocks (SB-blocks). If $\mathcal{B}$ satisfies the following five conditions,
then we call $(K_{v_{1},v_{2}}\,;\mathcal{B})$ a spanning bipartite block
design (SBBD):

  1. (i)

Each subgraph $B_{i}$ of $\mathcal{B}$ is incident with all points of $V_{1}$
and $V_{2}$. This is called the spanning condition.

  2. (ii)

Each edge of $E$ appears in $\mathcal{B}$ exactly $\mu$ times.

  3. (iii)

Any two edges $e_{ij},e_{ij^{\prime}}\in E$ such that $i\in V_{1}$,
$j,j^{\prime}\in V_{2},\,(j\neq j^{\prime})$ are included together in
$\lambda_{12}$ subgraphs in $\mathcal{B}$.

  4. (iv)

Any two edges $e_{ij},e_{i^{\prime}j}\in E$ such that $i,i^{\prime}\in
V_{1},\,(i\neq i^{\prime})$, $j\in V_{2}$ are included together in
$\lambda_{21}$ subgraphs in $\mathcal{B}$.

  5. (v)

Any two edges $e_{ij}$, $e_{i^{\prime}j^{\prime}}\in E$ such that
$i,i^{\prime}\in V_{1},\,(i\neq i^{\prime})$, $j,j^{\prime}\in V_{2},\,(j\neq
j^{\prime})$ are included together in $\lambda_{22}$ subgraphs in
$\mathcal{B}$.

Next, we define a $(0,1)$-matrix $X$, called a design matrix, from the SB-
blocks.

  * •

Suppose that the edges $e_{ij}$ of $K_{v_{1},v_{2}}$ are arranged in the same
lexicographical order as Equation (1).

$(e_{11},e_{12},\ldots,e_{1v_{2}}\ ;\ e_{21},e_{22},\ldots,e_{2v_{2}}\ ;\
\cdots\ ;\ e_{v_{1}1},\ldots,e_{v_{1}v_{2}}).$ (3)

This sequence of edges corresponds to the columns of $X$. Denote $(e_{ij})$
for the column number which corresponds to the edge $e_{ij}$.

  * •

Put $X=[x_{k,(e_{ij})}]$, then $x_{k,(e_{ij})}$ is the element of the $k$-th
row and the $(e_{ij})$-th column of $X$. The design matrix $X$ is defined by
the SB-blocks $B_{1},B_{2},\ldots,B_{N}$ as follows:

$\displaystyle x_{k,(e_{ij})}=\begin{cases}1&\mbox{ if}\ \ e_{ij}\in B_{k}\\\
0&\mbox{ otherwise}\end{cases}$ (4)

  * •

$X$ is an $N\times v_{1}v_{2}$ matrix.

This is a convenient way to represent a $(0,1)$-matrix for checking the
conditions. Let $X_{i}$ be an $N\times v_{2}$ submatrix of $X$ consisting of
$v_{2}$ columns of $X$ corresponding to $(e_{i1},e_{i2},\ldots,$
$e_{iv_{2}})$. Then the design matrix $X$ is partitioned into $v_{1}$
submatrices expressed as $X=(X_{1}\mid X_{2}\mid\cdots$ $\mid X_{v_{1}})$. The
conditions of a spanning bipartite block design
$(K_{v_{1},v_{2}}\,;\,\mathcal{B})$ can be re-expressed using the design
matrix $X=(X_{1}\mid X_{2}\mid\cdots\mid X_{v_{1}})$ as follows:

  1. (I)

If $\mathcal{B}$ satisfies the condition (i), any row of $X_{i}$ is not zero-
vector for $1\leq i\leq v_{1}$ and $\sum_{i=1}^{v_{1}}X_{i}$ has no zero
element (the spanning condition).

  2. (II)

If $\mathcal{B}$ satisfies the condition (ii), all diagonal elements of
$X_{i}^{\,t}X_{i}$ are $\mu$ for $1\leq i\leq v_{1}$.

  3. (III)

If $\mathcal{B}$ satisfies the condition (iii), all off-diagonal elements of
$X_{i}^{\,t}X_{i}$ are $\lambda_{12}$ for $1\leq i\leq v_{1}$.

  4. (IV)

If $\mathcal{B}$ satisfies the condition (iv), all diagonal elements of
$X_{i}^{\,t}X_{j}$ are $\lambda_{21}$ for $1\leq i\neq j\leq v_{1}$.

  5. (V)

If $\mathcal{B}$ satisfies the condition (v), all off-diagonal elements of
$X_{i}^{\,t}X_{j}$ are $\lambda_{22}$ for $1\leq i\neq j\leq v_{1}$.

$X^{\,t}X$ is called an information matrix. The information matrix of an SBBD
is expressed as follows:

$\displaystyle X^{t}X$ $\displaystyle=$ $\displaystyle
I_{v_{1}}\otimes(X_{i}^{\,t}X_{i})+(J_{v_{1}}-I_{v_{1}})\otimes(X_{i}^{\,t}X_{j})$
(5) $\displaystyle=$ $\displaystyle
I_{v_{1}}\otimes\begin{bmatrix}\mu&\lambda_{12}&\cdots&\lambda_{12}\\\
\lambda_{12}&\mu&\cdots&\lambda_{12}\\\ \vdots&\vdots&\ddots&\vdots\\\
\lambda_{12}&\lambda_{12}&\cdots&\mu\end{bmatrix}+(J_{v_{1}}-I_{v_{1}})\otimes\begin{bmatrix}\lambda_{21}&\lambda_{22}&\cdots&\lambda_{22}\\\
\lambda_{22}&\lambda_{21}&\cdots&\lambda_{22}\\\
\vdots&\vdots&\ddots&\vdots\\\
\lambda_{22}&\lambda_{22}&\cdots&\lambda_{21}\end{bmatrix},$

where $1\leq i\neq j\leq v_{1}$, and $I_{n}$ is the identity matrix of size
$n$ and $J_{n}$ is the $(n\times n)$ all-ones matrix.

A matrix expressed by $aI_{n}+b(J_{n}-I_{n})$ is called completely symmetric.
The information matrix above has a double structure of a completely symmetric
matrix. We call the matrix double completely symmetric. A spanning bipartite
block design $(K_{v_{1},v_{2}}\,;\mathcal{B})$ is denoted as
SBBD($v_{1},v_{2},N\,;\Lambda$), where
$\Lambda=(\mu,\lambda_{12},\lambda_{21},\lambda_{22})$.

######  Example 2.1.

Let

$X=[X_{1}\mid X_{2}\mid X_{3}]=$
$\left[\begin{array}[]{ccc|ccc|ccc}0&1&1&1&1&0&1&1&0\\\ 1&0&1&0&1&1&0&1&1\\\
1&1&0&1&0&1&1&0&1\\\ 0&1&1&0&1&1&1&0&1\\\ 1&0&1&1&0&1&1&1&0\\\
1&1&0&1&1&0&0&1&1\\\ 0&1&1&1&0&1&0&1&1\\\ 1&0&1&1&1&0&1&0&1\\\
1&1&0&0&1&1&1&1&0\\\ \end{array}\right]$

be a design matrix of an SBBD. Then its information matrix is

$X^{t}X=I_{3}\otimes\left[\begin{array}[]{ccc}6&3&3\\\ 3&6&3\\\
3&3&6\end{array}\right]+(J_{3}-I_{3})\otimes\left[\begin{array}[]{ccc}4&4&4\\\
4&4&4\\\ 4&4&4\end{array}\right].$

The design matrix $X$ satisfies the spanning condition since any row of
$X_{i}$ is not the zero-vector and $X_{1}+X_{2}+X_{3}$ does not contain $0$.
So we have an SBBD$(3,3,9\,;\Lambda),$ $\Lambda=(6,3,4,4)$.

As you can see from the above example, the spanning condition can not be
confirmed from the information matrix $X^{t}X$. If $v_{1}\ll v_{2}$, there is
a high possibility that the spanning condition is not met. Such a design in
which the spanning condition (I) is not guaranteed is denoted by SBBD∗.

##  3 Optimality

###  3.1 Variance balanced

For a design matrix, we have a statistical problem of whether it is optimum
under certain conditions. There are some criteria for the precision of the
estimators (variances of estimators), see [8]. Here we use a criterion called
A-optimality (or A-criterion).

Let $e_{ij}^{(v)}=(e_{1},e_{2},\ldots,e_{v})$ be a $(0,1)$-vector of length
$v$ such that $e_{i}=1$, $e_{j}=-1$ and $e_{k}=0,k\neq i,j$.
$(e_{ij}^{(v_{1})}\otimes
e_{i^{\prime}j^{\prime}}^{(v_{2})})^{t}\boldsymbol{\tau}$ for any $1\leq
i<j\leq v_{1}$ and $1\leq i^{\prime}<j^{\prime}\leq v_{2}$ are called
elementary contrasts.

Suppose an information matrix $X^{t}X$ has a double structure of completely
symmetric matrices $A$ and $B$ of size $(v_{1}\times v_{1})$ and $(v_{2}\times
v_{2})$, respectively. Let
$\boldsymbol{p}_{1},\boldsymbol{p}_{2},\ldots,\boldsymbol{p}_{v_{1}-1}$ be
orthonormal eigenvectors of $A$ orthogonal to $\boldsymbol{1}_{v_{1}}$, and
also $\boldsymbol{q}_{1},\boldsymbol{q}_{2},\ldots,\boldsymbol{q}_{v_{2}-1}$
be similar vectors of $B$ with size $v_{2}$, where $\boldsymbol{1}_{n}$ is the
all-one $n$-vector. A basic contrast of $A\otimes B$ is defined by

$(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}\boldsymbol{\tau}.$ (6)

Since every $e_{ij}^{(v_{1})}\otimes e_{i^{\prime}j^{\prime}}^{(v_{2})}$ for
any $1\leq i<j\leq v_{1}$ and $1\leq i^{\prime}<j^{\prime}\leq v_{2}$ lies in
the subspace spanned by $\boldsymbol{p}_{1}\otimes\boldsymbol{q}_{1},\
\boldsymbol{p}_{1}\otimes\boldsymbol{q}_{2},\ldots,\
\boldsymbol{p}_{v_{1}-1}\otimes\boldsymbol{q}_{v_{2}-1}$, we here use basic
contrasts for the proofs in this section, although elementary contrasts are
commonly used as contrasts.

Let $\theta_{1,1},\theta_{1,2},\ldots,\theta_{(v_{1}-1),(v_{2}-1)}$ be non-
zero eigenvalues of $A\otimes B$, and
$\boldsymbol{p}_{1}\otimes\boldsymbol{q}_{1},\
\boldsymbol{p}_{1}\otimes\boldsymbol{q}_{2},\ldots,\
\boldsymbol{p}_{v_{1}-1}\otimes\boldsymbol{q}_{v_{2}-1}$ be orthonormal
eigenvectors, that is,
$(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}\boldsymbol{1}_{v_{1}v_{2}}=0$,
$(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})=1$
and
$(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}(\boldsymbol{p}_{i^{\prime}}\otimes\boldsymbol{q}_{j^{\prime}})=0$,
$i\neq i^{\prime}$ or $j\neq j^{\prime}$ then we have

$\mbox{Var}((\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}\hat{\boldsymbol{\tau}})=(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}(A\otimes
B)^{-}(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})\sigma^{2}=\frac{1}{\theta_{i,j}}\sigma^{2},$
(7)

where $(A\otimes B)^{-}$ is a Moore-Penrose generalized inverse matrix of
$(A\otimes B)$.

######  Definition 3.1.

(A-optimum, [5]) Let $\Xi$ be the set of $(N\times v_{1}v_{2})$ design
matrices $X$ with a certain number of $1^{\prime}$s. Assume $X^{t}X$,
$X\in\Xi$, has $(v_{1}-1)(v_{2}-1)$ non-zero eigenvalues
$\alpha_{1},\alpha_{2},\ldots,\alpha_{(v_{1}-1)(v_{2}-1)}$. For a design
matrix $X\in\Xi$, if the sum of $1/\alpha_{i}$ is minimum among $\Xi$, then
$X$ is called A-optimum relative to $\Xi$.

$\mbox{A-optimum:}\ \min_{X\in\Xi}\ \bigg{\\{}\sum_{1\leq
i\leq(v_{1}-1)(v_{2}-1)}\frac{1}{\alpha_{i}}\bigg{\\}}$ (8)

######  Definition 3.2.

(Variance Balanced, [10]) If all variances for the estimators of basic
contrasts are the same, that is, if $X^{t}X$ has $(v_{1}-1)(v_{2}-1)$
identical non-zero eigenvalues, then the design is called variance balanced:

$\begin{split}\mathrm{Var}((\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}\boldsymbol{\hat{\tau}})=\frac{1}{\alpha}\sigma^{2}\mbox{\
\ for }1\leq i\leq v_{1}-1\mbox{ and }1\leq j\leq v_{2}-1.\end{split}$ (9)

It is known that any A-optimum design is variance balanced, but the reverse
has not been proven.

Consider a statistical model (2) of SBBD. If we compare to an ordinal two-way
factorial model with interactions, the treatment effects of Equation (1) have
the exact same structure as the interaction effects whose information matrix
is double completely symmetric, see [7].

######  Theorem 3.3.

SBBD∗ is variance balanced whenever all basic contrasts of $\boldsymbol{\tau}$
are estimable.

Proof Let $X^{t}X$ be a double completely symmetric information matrix from an
SBBD∗ which can be expressed with four integers, $a,b,c,d$ as follows:

$X^{t}X=I_{v_{1}}\otimes(aI_{v_{2}}+bJ_{v_{2}})+(J_{v_{1}}-I_{v_{1}})\otimes(cI_{v_{2}}+dJ_{v_{2}}).$
(10)

Consider a Moore-Penrose generalized inverse matrix of $X^{t}X$ by putting
$A_{1},A_{2},B_{1}$ and $B_{2}$ as follows:

$A_{1}=I_{v_{1}}-\frac{1}{v_{1}}J_{v_{1}},\ A_{2}=\frac{1}{v_{1}}J_{v_{1}},\
B_{1}=I_{v_{2}}-\frac{1}{v_{2}}J_{v_{2}},\ B_{2}=\frac{1}{v_{2}}J_{v_{2}}.$

Using the spectral decomposition method, the information matrix $X^{t}X$ can
be rewritten as follows:

$\displaystyle X^{t}X$ $\displaystyle=$
$\displaystyle(A_{1}+A_{2})\otimes(a(B_{1}+B_{2})+bv_{2}B_{2})+(v_{1}A_{2}-(A_{1}+A_{2}))\otimes(c(B_{1}+B_{2})+dv_{2}B_{2})$
(11) $\displaystyle=$
$\displaystyle(A_{1}+A_{2})\otimes(aB_{1}+(a+bv_{2})B_{2})+((v_{1}-1)A_{2}-A_{1})\otimes(cB_{1}+(c+dv_{2})B_{2})$
$\displaystyle=$ $\displaystyle(a-c)(A_{1}\otimes
B_{1})+(a+bv_{2}-c-dv_{2})(A_{1}\otimes B_{2})+(a+c(v_{1}-1))(A_{2}\otimes
B_{1})$ $\displaystyle+\,(a+bv_{2}+(v_{1}-1)(c+dv_{2}))(A_{2}\otimes B_{2}).$

Then we can see the eigenvalues $\alpha$, $\beta$, $\gamma$, $\delta$ of
$X^{t}X$:

$\alpha=a-c,\ \beta=a-c+(b-d)v_{2},\gamma=a+c(v_{1}-1),\
\delta=a+bv_{2}+(v_{1}-1)(c+dv_{2}).$

We are interested in the first term, $\alpha(A_{1}\otimes B_{1})$, of Equation
(11). The matrix of the term can be represented as

$(A_{1}\otimes B_{1})=\sum_{\begin{subarray}{c}1\leq i\leq v_{1}-1\\\ 1\leq
j\leq
v_{2}-1\end{subarray}}\theta_{i,j}(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t},$

where $\boldsymbol{p}_{i}$ ($\boldsymbol{q}_{j}$) are orthonormal eigenvectors
of $A_{1}$ ($B_{1}$) orthogonal to $\boldsymbol{1}_{v_{1}}$
($\boldsymbol{1}_{v_{2}}$) and $\theta_{i,j}$ is the eigenvalue corresponding
to $\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j}$. From the matrix forms of
$A_{1}$ and $B_{1}$, non-zero eigenvalues $\theta_{i,j}$ are all $1$. So, all
basic contrasts of $\boldsymbol{\tau}$,
$(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}\boldsymbol{\tau}$ for
$1\leq i\leq v_{1}-1$ and $1\leq j\leq v_{2}-1$, are obtained from the first
term. Therefore, the Moore-Penrose generalized inverse matrix $(X^{t}X)^{-}$
including the ordinal inverse matrix is written as:

$(X^{t}X)^{-}=\frac{1}{\alpha}(A_{1}\otimes
B_{1})+\frac{1}{\beta}(A_{1}\otimes B_{2})+\frac{1}{\gamma}(A_{2}\otimes
B_{1})+\frac{1}{\delta}(A_{2}\otimes B_{2}).$ (12)

If $\alpha,\beta,\gamma,\delta$ are all non-zero, $(X^{t}X)^{-}$ is an inverse
matrix, otherwise, it is a Moore-Penrose generalized inverse matrix. If at
least one of the eigenvalues is 0, then it is obtained by removing the term
from Equation (12). Here we put $\alpha\neq 0,\ (a>c)$ from the assumption
that all basic contrasts of effects in the model (2) are estimable, and
algebraic multiplicity of $\alpha$ is $(v_{1}-1)(v_{2}-1)$. Using Equation
(7), it holds that

$\begin{split}\textrm{Var}((\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}\hat{\boldsymbol{\tau}})&=(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}(X^{t}X)^{-}(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})\sigma^{2}\\\
&=\frac{1}{\alpha}(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})^{t}(A_{1}\otimes
B_{1})(\boldsymbol{p}_{i}\otimes\boldsymbol{q}_{j})\sigma^{2}\\\
&=\frac{1}{\alpha}\sigma^{2}\end{split}$

for $1\leq i\leq v_{1}-1$ and $1\leq j\leq v_{2}-1$. Therefore, the theorem is
complete. ∎

The coefficients $a,b,c,d$ in the proof correspond to the parameters of SBBD
as follows:

$\displaystyle a=\mu-\lambda_{12},\ \ b=\lambda_{12},\ \
c=\lambda_{21}-\lambda_{22},\ \ d=\lambda_{22}.$

######  Example 3.4.

Eigenvalues of $X^{t}X$ in Example 2.1 are

$36,\ 3,\ 3,\ 3,\ 3,\ 3,\ 3,\ 0,\ 0.$

They include $(3-1)(3-1)=4$ same eigenvalues for $\alpha$ $(=3)$. The
parameters of Example 2.1 are $\mu=6$, $\lambda_{12}=3$, $\lambda_{21}=4$,
$\lambda_{22}=4$, $v_{1}=3$, $v_{2}=3$. Then we have the following four kinds
of eigenvalues, $\alpha,\beta,\gamma,\delta$.

$\begin{array}[]{ccll}\alpha&=&a-c=\mu-\lambda_{12}-\lambda_{21}+\lambda_{22}=3&(m_{\alpha}=(v_{1}-1)(v_{2}-1)=4)\\\
\beta&=&a+bv_{2}-c-dv_{2}=0&(m_{\beta}=v_{1}-1=2)\\\
\gamma&=&a+c(v_{1}-1)=3&(m_{\gamma}=v_{2}-1=2)\\\
\delta&=&a+bv_{2}+(v_{1}-1)(c+dv_{2})=36&(m_{\delta}=1),\end{array}$

where $m_{\alpha},m_{\beta},m_{\gamma},m_{\delta}$ are multiplicities. These
are consistent with the proof of Theorem 3.3.

From the proof, we have the following corollary:

######  Corollary 3.5.

If $X$, size ($N\times v_{1}v_{2}$), is a design matrix of an SBBD∗, where all
contrasts of effects are estimable, then $X^{t}X$ has $(v_{1}-1)(v_{2}-1)$
non-zero identical eigenvalues.

###  3.2 Optimality on semi-regular SBBD

Let $B=(V_{1},V_{2}\,;E^{\prime}),E^{\prime}\subseteq E$ be a subgraph of the
complete bipartite graph $K_{v_{1},v_{2}}=(V_{1},V_{2}\,;E)$. If all points in
$V_{1}$ and $V_{2}$ of $B$ have degrees $k_{1}$ and $k_{2}$, respectively,
then the subgraph $B$ is called a semi-regular bipartite subgraph, and called
regular bipartite subgraph if $k_{1}=k_{2}$. Let $\mathcal{B}$ be a set of $N$
semi-regular bipartite subgraphs of $K_{v_{1},v_{2}}$, degrees are $k_{1}$ and
$k_{2}$, that is, $v_{1}k_{1}=v_{2}k_{2}$. Assume $N\geq(v_{1}-1)(v_{2}-1)$.
Let $X$ be a design matrix of size $(N\times v_{1}v_{2})$ defined by Section 2
with respect to $\mathcal{B}$. Now we define a class $\Omega$ for matrices $X$
that satisfies the following conditions:

  * (C1)

the number of $1$’s in each column of $X$ is $\mu$,

  * (C2)

$X$ is a design matrix whose rows correspond to blocks of $\mathcal{B}$,

  * (C3)

the all elementary contrasts of $X^{t}X$, $(e_{ij}^{(v_{1})}\otimes
e_{i^{\prime}j^{\prime}}^{(v_{2})})^{t}\boldsymbol{\tau}$, are estimable for
$1\leq i<j\leq v_{1}$ and $1\leq i^{\prime}<j^{\prime}\leq v_{2}$.

If $X=(X_{1}\mid X_{2}\mid\cdots\mid X_{v_{1}})$ is a matrix in $\Omega$, then
$X$ has the following properties:

  * •

any row of $X_{i}$ has exactly $k_{1}$ $1$’s for $1\leq i\leq v_{1}$,

  * •

any row of $\sum_{i=1}^{v_{1}}X_{i}$ is $(k_{2},k_{2},\ldots,k_{2})$.

If a matrix $X\in\Omega$ satisfies the conditions 1 to 5 of SBBD, it is called
a semi-regular SBBD. And if all blocks of a semi-regular SBBD are regular
bipartite subgraphs then it is called a regular SBBD.

Let $\mathbf{z}_{1},\mathbf{z}_{2},\ldots,\mathbf{z}_{v_{1}-1}$ be the
orthonormal vectors orthogonal to $\boldsymbol{1}_{v_{1}}$, and also
$\mathbf{w}_{1},\mathbf{w}_{2}$, $\ldots,\mathbf{w}_{v_{2}-1}$ be the
orthonormal vectors orthogonal to $\boldsymbol{1}_{v_{2}}$ (they are not
necessary to be eigenvectors).

######  Lemma 3.6.

For any $X\in\Omega$, $X^{t}X$ has the following eigenvectors whose
eigenvalues are all $0$,

$\mathbf{z}_{1}\otimes\boldsymbol{1}_{v_{2}},\mathbf{z}_{2}\otimes\boldsymbol{1}_{v_{2}},\ldots,\mathbf{z}_{v_{1}-1}\otimes\boldsymbol{1}_{v_{2}},$
(13)

and

$\boldsymbol{1}_{v_{1}}\otimes\mathbf{w}_{1},\boldsymbol{1}_{v_{1}}\otimes\mathbf{w}_{2},\ldots,\boldsymbol{1}_{v_{1}}\otimes\mathbf{w}_{v_{2}-1},$
(14)

Proof Let $k=k_{1}v_{1}=v_{2}k_{2}$. Since
$X^{t}X\boldsymbol{1}_{v_{1}v_{2}}=\mu k\boldsymbol{1}_{v_{1}v_{2}}$,
$\boldsymbol{1}_{v_{1}v_{2}}$ is an eigenvector of $X^{t}X$ whose eigenvalue
is $\mu k$. Let $X=(X_{1}\mid X_{2}\mid\cdots\mid X_{v_{1}})$ and
$X_{i}=[x_{jh}^{(i)}]$. The inner product of the $j$-th row of $X$ and
$\mathbf{z}_{i}\otimes\boldsymbol{1}_{v_{2}}$ is

$\sum_{g=1}^{v_{1}}\sum_{h=1}^{v_{2}}x_{jh}^{(g)}z_{g}^{(i)}=k_{1}\sum_{g=1}^{v_{1}}z_{g}^{(i)}=0$

from the semi-regular condition, where $z_{g}^{(i)}$ is the $g$-th element of
$\mathbf{z}_{i}$. Similarly, we have

$\sum_{g=1}^{v_{1}}\sum_{h=1}^{v_{2}}x_{jh}^{(g)}w_{h}^{(i)}=k_{2}\sum_{h=1}^{v_{2}}w_{h}^{(i)}=0,$

where $w_{h}^{(i)}$ is the $h$-th element of $\mathbf{w}_{i}$. Therefore, the
vectors of (13) and (14) are eigenvectors of $X^{t}X$ corresponding to
eigenvalue zero. ∎

Let
$\boldsymbol{u}_{1},\boldsymbol{u}_{2},\ldots,\boldsymbol{u}_{(v_{1}-1)(v_{2}-1)}$
be orthonormal eigenvectors of $X^{t}X$ which are orthogonal to
$\boldsymbol{1}_{v_{1}v_{2}}$, (13) and (14).

######  Lemma 3.7.

Every $X$ in $\Omega$ is A-optimum if the eigenvalues corresponding to
$\boldsymbol{u}_{i}$’s are all equal.

Proof Let $\alpha_{i}$ be the eigenvalue corresponding to
$\boldsymbol{u}_{i}$. We have a spectrum decomposition of $X^{t}X$,

$X^{t}X=\sum_{i=1}^{(v_{1}-1)(v_{2}-1)}\alpha_{i}\boldsymbol{u}_{i}\boldsymbol{u}_{i}^{t}+\mu
k\frac{1}{v_{1}v_{2}}\boldsymbol{1}_{v_{1}v_{2}}(\boldsymbol{1}_{v_{1}v_{2}})^{t}.$
(15)

Every $e_{ij}^{(v_{1})}\otimes e_{i^{\prime}j^{\prime}}^{(v_{2})}$ for any
$1\leq i<j\leq v_{1}$ and $1\leq i^{\prime}<j^{\prime}\leq v_{2}$ lies in the
subspace spanned by
$\boldsymbol{u}_{1},\boldsymbol{u}_{2},\ldots,\boldsymbol{u}_{(v_{1}-1)(v_{2}-1)}$.
From the condition (C3), $\alpha_{i}>0$ for $1\leq i\leq(v_{1}-1)(v_{2}-1)$.
Let $\hat{\boldsymbol{\tau}}$ be the least square estimator of
$\boldsymbol{\tau}$. We have

$\textrm{Var}(\boldsymbol{u}_{i}^{t}\hat{\boldsymbol{\tau}})=\boldsymbol{u}_{i}^{t}(X^{t}X)^{-}\boldsymbol{u}_{i}\sigma^{2}=\frac{1}{\alpha_{i}}\sigma^{2}$

with Moore-Penrose generalized inverse of $X^{t}X$:

$(X^{t}X)^{-}=\sum_{i=1}^{(v_{1}-1)(v_{2}-1)}\frac{1}{\alpha_{i}}\boldsymbol{u}_{i}\boldsymbol{u}_{i}^{t}+\frac{1}{\mu
k}\frac{1}{v_{1}v_{2}}\boldsymbol{1}_{v_{1}v_{2}}(\boldsymbol{1}_{v_{1}v_{2}})^{t}.$

Consider A-criterion

$\sum_{i=1}^{(v_{1}-1)(v_{2}-1)}\frac{1}{\alpha_{i}}\ .$ (16)

From Equation (15), we have

$\textrm{tr}(X^{t}X)=\sum_{i=1}^{(v_{1}-1)(v_{2}-1)}\alpha_{i}+\mu k=\mu
v_{1}v_{2},$

that is,

$\sum_{i=1}^{(v_{1}-1)(v_{2}-1)}\alpha_{i}=\mu(v_{1}v_{2}-k).$

Since

$\frac{(v_{1}-1)(v_{2}-1)}{\sum_{i=1}^{(v_{1}-1)(v_{2}-1)}\frac{1}{\alpha_{i}}}\leq\frac{1}{(v_{1}-1)(v_{2}-1)}\sum_{i=1}^{(v_{1}-1)(v_{2}-1)}\alpha_{i},$

if
$\alpha_{1}=\alpha_{2}=\cdots=\alpha_{(v_{1}-1)(v_{2}-1)}=\frac{\mu(v_{1}v_{2}-k)}{(v_{1}-1)(v_{2}-1)}$,
then A-criterion (16) is minimum. ∎

From Theorem 3.3 and Corollary 3.5, an information matrix $X^{t}X$ of an SBBD
has non-zero $(v_{1}-1)(v_{2}-1)$ eigenvalues which are equal. Therefore, we
have the following theorem:

######  Theorem 3.8.

A semi-regular SBBD is A-optimum relative to $\Omega$.

##  4 Constructions of SBBD

###  4.1 A construction using an $(r,\lambda)$-design and an ordered design

######  Definition 4.1.

($(r,\lambda)$-design, [3]) Let $V$ be $v$-point set and
$\mathcal{B}=\\{B_{1},B_{2},\ldots,$ $B_{b}\\}$ a collection of subsets
(blocks) of $V$. If $(V,\mathcal{B})$ holds the following conditions, it is
called an $(r,\lambda)$-design:

  * •

each point of $V$ is contained in exactly $r$ blocks of $\mathcal{B}$,

  * •

any two distinct points of $V$ are contained in exactly $\lambda$ blocks of
$\mathcal{B}$.

Let $v$ be the number of points and $b$ the number of blocks, and put
$k_{i}=\lvert B_{i}\rvert$ as the block size. If the block sizes are constant
$k$, then the $(r,\lambda)$-design is called a balanced incomplete block
design (BIBD) and denoted by a $(v,k,\lambda)$-BIBD. An $(r,\lambda)$-design
is also called a regular pairwise balanced design. It is not hard to construct
because there is no block size restriction. Pairwise balanced designs (PBD,
the first condition of $(r,\lambda)$-design is not required) have been well
studied, and many recursive constructions are known, see [3] and [13]. It is
not difficult to modify a PBD to be regular.

Let $(V,\mathcal{B})$ be an $(r,\lambda)$-design, and $H=[x_{ij}]$ be the
$(b\times v)$ incidence matrix between
$\mathcal{B}=\\{B_{1},B_{2},\ldots,B_{b}\\}$ and
$V=\\{a_{1},a_{2},\ldots,a_{v}\\}$.

$x_{ij}=\begin{cases}1&\mbox{ if }a_{j}\in B_{i}\\\ 0&\mbox{
otherwise}.\end{cases}$

Then $H^{t}H$ is expressed as $rI_{v}+\lambda(J_{v}-I_{v})$.

######  Definition 4.2.

(Ordered design, [9]) Let $M$ be an $(\eta({n}^{2}-n)\times s)$-array with
entries from $\mathbf{N}_{n}=\\{1,2,\ldots,$ $n\\}$. If $M=[d_{pq}]$ holds the
following conditions, it is called an ordered design, denoted by
$OD_{\eta}(s,n)$.

  1. (1)

each row of M consists of $s$ distinct elements in $\mathbf{N}_{n}$, where
$s\leq n$,

  2. (2)

in any distinct two columns of $M$, every ordered pair $(x,y)$ of distinct
elements in $\mathbf{N}_{n}$ appears on the same rows exactly $\eta$ times.

In the condition (2), if the pair $(x,y)$ is not necessary to be distinct, the
$(\eta n^{2}\times(s+1))$ array is called orthogonal array. It is well known
that there exists an $(\eta(n^{2}-n)\times s)$ ordered design if there is an
orthogonal $(\eta n^{2}\times(s+1))$ array. We know that there is an
orthogonal $(q^{2}\times(q+1))$ array, $q$ a prime power, see [4]. That is:

######  Property 4.3.

For any prime power $q$, there exists an $OD_{1}(q,q)$.

Suppose $H$ is a $(b\times v)$ incidence matrix of an $(r,\lambda)$-design
with $v$ points and $b$ blocks, and let $\mathbf{h}_{i}$ be the $i$-th row
vector of $H$. Then, we can obtain a design matrix by arranging the vectors
$\mathbf{h}_{i}$ in according to an ordered design $OD_{\eta}(s,b)$
$M=[d_{pq}]$ as follows:

$X=[\mathbf{h}_{d_{pq}}]=(X_{1}\mid X_{2}\mid\cdots\mid X_{s}).$

Note that $X$ is of size $(\eta(b^{2}-b)\times vs)$, where each $X_{j}$ is an
$(\eta(b^{2}-b)\times v)$-submatrix of $X$ in which the row vector of ${H}$
are put in according to the $j$-th column of $M$.

######  Example 4.4.

The ordered design $OD_{1}(3,3)$ represented by the symbols $\\{1,2,3\\}$ is
on the left side of the following matrices. The design matrix $X$ with the
vectors $\boldsymbol{h}_{i},i=1,2,3$, is on the right side.

$OD_{1}(3,3)=\begin{bmatrix}1&2&3\\\ 2&3&1\\\ 3&1&2\\\ 1&3&2\\\ 2&1&3\\\
3&2&1\end{bmatrix},\hskip
28.45274ptX=\begin{bmatrix}\mathbf{h}_{1}&\mathbf{h}_{2}&\mathbf{h}_{3}\\\
\mathbf{h}_{2}&\mathbf{h}_{3}&\mathbf{h}_{1}\\\
\mathbf{h}_{3}&\mathbf{h}_{1}&\mathbf{h}_{2}\\\
\mathbf{h}_{1}&\mathbf{h}_{3}&\mathbf{h}_{2}\\\
\mathbf{h}_{2}&\mathbf{h}_{1}&\mathbf{h}_{3}\\\
\mathbf{h}_{3}&\mathbf{h}_{2}&\mathbf{h}_{1}\end{bmatrix}.$

Regarding the $j$-th row of $X$ as an SB-block $B_{j}$, $1\leq j\leq N$, which
is a spanning subgraph of $K_{s,v}$, we have an SBBD
$(K_{s,v}\,;\mathcal{B})$, where $N=\eta(b^{2}-b)$.

######  Lemma 4.5.

Let $H$ be the $(b\times v)$ incidence matrix of an $(r,\lambda)$-design, and
$\mathbf{h}_{1},\mathbf{h}_{2},\ldots,\mathbf{h}_{b}$ be the row vectors of
$H$. Then the following equations hold:

$\displaystyle\sum_{i=1}^{b}\mathbf{h}_{i}^{t}\,\mathbf{h}_{i}=rI_{v}+\lambda(J_{v}-I_{v}),$
(17)
$\displaystyle\sum_{i=1}^{b}\sum_{j=1}^{b}\mathbf{h}_{i}^{t}\,\mathbf{h}_{j}=r^{2}J_{v}.$
(18)

Proof From the definition of $(r,\lambda)$-design,
$H^{t}H=rI_{v}+\lambda(J_{v}-I_{v})$. Since
$\sum_{i=1}^{b}\mathbf{h}_{i}^{t}\mathbf{h}_{i}=H^{t}H$, it holds Equation
(17). Next,

$\displaystyle\begin{split}\sum_{i=1}^{b}\sum_{j=1}^{b}\mathbf{h}_{i}^{t}\,\mathbf{h}_{j}=\sum_{i=1}^{b}(\sum_{j=1}^{b}\mathbf{h}_{i}^{t}\,\mathbf{h}_{j})&=\sum_{i=1}^{b}\mathbf{h}_{i}^{t}(r,r,,\ldots,r)\\\
&=(r,r,\ldots,r)^{t}(r,r,,\ldots,r)\\\ &=r^{2}J_{v}.\end{split}$

∎

######  Theorem 4.6.

If there exists an $(r,\lambda)$-design with $b$ blocks and $v$ points, and an
ordered design $OD_{\eta}(s,b)$, then there is a spanning bipartite block
design SBBD∗($s,v,N\,;\Lambda$), $N=\eta({b}^{2}-b)$ and
$\Lambda=(\mu,\lambda_{12},\lambda_{21},$ $\lambda_{22})=(\eta
r(b-1),\eta\lambda(b-1),\eta r(r-1),\eta(r^{2}-\lambda)\ )$.

Proof Let $H$ be the $(b\times v)$ incidence matrix of an $(r,\lambda)$-design
with $b$ blocks and $v$ elements, and ${\mathbf{h}}_{i}$ ($1\leq i\leq b$) be
the $i$-th row of $H$. $M=[d_{pq}]$ is an ordered design $OD_{\eta}(s,b)$. Let
$X$ be the design matrix by arranging the row vector of $H$ in according to
the ordered design $M$.

$X=[{\mathbf{h}}_{d_{pq}}]=(X_{1}\mid X_{2}\mid\cdots\mid X_{s}).$

First, we compute a diagonal submatrix $X_{q}^{\,t}X_{q}$ of the information
matrix $X^{t}X$. In $X_{q}$, $1\leq q\leq s$, each vector ${\mathbf{h}}_{i}$
appears $\eta(b-1)$ times. Therefore, from Lemma 4.5, we have

$X_{q}^{\,t}X_{q}=\eta(b-1)\sum_{j=1}^{b}{\mathbf{h}}_{j}^{t}{\mathbf{h}}_{j}=\eta(b-1)\cdot(rI_{v}+\lambda(J_{v}-I_{v})).$

Next, we have the following off-diagonal submatrices of $X^{t}X$ for $1\leq
q\neq q^{\prime}\leq s$:

$\displaystyle X_{q}^{\,t}X_{q^{\prime}}$ $\displaystyle=\eta\,(\
\sum_{i=1}^{b}\sum_{j=1}^{b}{\mathbf{h}}_{i}^{t}{\mathbf{h}}_{j}-\sum_{i=1}^{b}{\mathbf{h}}_{i}^{t}{\mathbf{h}}_{i}\
)$ $\displaystyle=\eta(r^{2}J_{v}-(rI_{v}+\lambda(J_{v}-I_{v}))$
$\displaystyle=\eta((r^{2}-r)I_{v}+(r^{2}-\lambda)(J_{v}-I_{v})).$

∎

Let $P$ be a permutation matrix of size $(v\times v)$ (a $(0,1)$-matrix with
exactly one $1$ in every row and column).

######  Corollary 4.7.

If $X=(X_{1}\mid X_{2}\mid\cdots\mid X_{s})$ is an SBBD, then

$X^{(P)}=(X_{1}P\mid X_{2}P\mid\cdots\mid X_{s}P)$

is also an SBBD with the same parameters as $X$.

Proof For $1\leq i,j\leq s$,

$(X_{i}P)^{t}(X_{j}P)=P^{t}(X_{i}^{\,t}X_{j})P=X_{i}^{\,t}X_{j}$

because every $X_{i}^{t}X_{j}$ is a completely symmetric matrix. Therefore, it
holds that $(X^{(P)})^{t}X^{(P)}=X^{t}X.$ ∎

$X^{(P)}$ may include many different rows from $X$ and may have some
additional linearly independent rows in $X$. If we have the following combined
design matrix using permutation matrices $P_{1},P_{2},...,P_{u-1}$:

$X^{(I,P_{1},P_{2},...,P_{u-1})}=\begin{bmatrix}X_{1}&X_{2}&\cdots&X_{s}\\\
X_{1}P_{1}&X_{2}P_{1}&\cdots&X_{s}P_{1}\\\ \vdots&\vdots&&\vdots\\\
X_{1}P_{u-1}&X_{2}P_{u-1}&\cdots&X_{s}P_{u-1}\end{bmatrix}$

then it is an SBBD with the parameters $(s,v,N\,;\Lambda$), $N=\eta
u({b}^{2}-b)$ and $\Lambda=(\eta ur(b-1),\eta u\lambda(b-1),\eta ur(r-1),\eta
u(r^{2}-\lambda)\,)$.

######  Corollary 4.8.

In Theorem 4.6, if $s>b-r$ then there exists an SBBD$(s,v,N\,;\Lambda)$ with
the same parameters.

Proof Since any row $\boldsymbol{h}_{i}$ is not the zero vector, $X_{i}$
contains no zero row vector. If $s=b$, each row of $\sum_{q=1}^{s}X_{q}$ is
exactly equal to $\sum_{i=1}^{b}\mathbf{h}_{i}=(r,r,\ldots,r)$. Therefore if
$s>b-r$, any component of $\sum_{q=1}^{s}X_{q}$ is greater than or equal to
$1$. ∎

######  Example 4.9.

Consider an $(r,\lambda)$-design
($V=\\{0,1,2\\},\mathcal{B}=\\{0,1\\},\\{1,2\\}$,
$\\{0,2\\},\\{0,1,2\\}\\}$) with parameters $r=3,\lambda=2,v=3,b=4$. Its
incidence matrix is

$H=\left(\begin{array}[]{ccc}1&1&0\\\ 0&1&1\\\ 1&0&1\\\
1&1&1\end{array}\right).$

Then the row vectors of $H$ are

${\mathbf{h}}_{1}=\left(\begin{array}[]{ccc}1&1&0\end{array}\right),\ \
{\mathbf{h}}_{2}=\left(\begin{array}[]{ccc}0&1&1\end{array}\right),\ \
{\mathbf{h}}_{3}=\left(\begin{array}[]{ccc}1&0&1\end{array}\right),\ \
{\mathbf{h}}_{4}=\left(\begin{array}[]{ccc}1&1&1\end{array}\right).$

Now, we have a design matrix $X$ using an ordered design $OD_{1}(4,4)$,

$X=$
$\begin{bmatrix}{\mathbf{h}}_{1}&{\mathbf{h}}_{2}&{\mathbf{h}}_{3}&{\mathbf{h}}_{4}\\\
{\mathbf{h}}_{2}&{\mathbf{h}}_{1}&{\mathbf{h}}_{4}&{\mathbf{h}}_{3}\\\
{\mathbf{h}}_{3}&{\mathbf{h}}_{4}&{\mathbf{h}}_{1}&{\mathbf{h}}_{2}\\\
{\mathbf{h}}_{4}&{\mathbf{h}}_{3}&{\mathbf{h}}_{2}&{\mathbf{h}}_{1}\\\
{\mathbf{h}}_{1}&{\mathbf{h}}_{3}&{\mathbf{h}}_{4}&{\mathbf{h}}_{2}\\\
{\mathbf{h}}_{2}&{\mathbf{h}}_{4}&{\mathbf{h}}_{3}&{\mathbf{h}}_{1}\\\
{\mathbf{h}}_{3}&{\mathbf{h}}_{1}&{\mathbf{h}}_{2}&{\mathbf{h}}_{4}\\\
{\mathbf{h}}_{4}&{\mathbf{h}}_{2}&{\mathbf{h}}_{1}&{\mathbf{h}}_{3}\\\
{\mathbf{h}}_{1}&{\mathbf{h}}_{4}&{\mathbf{h}}_{2}&{\mathbf{h}}_{3}\\\
{\mathbf{h}}_{2}&{\mathbf{h}}_{3}&{\mathbf{h}}_{1}&{\mathbf{h}}_{4}\\\
{\mathbf{h}}_{3}&{\mathbf{h}}_{2}&{\mathbf{h}}_{4}&{\mathbf{h}}_{1}\\\
{\mathbf{h}}_{4}&{\mathbf{h}}_{1}&{\mathbf{h}}_{3}&{\mathbf{h}}_{2}\\\
\end{bmatrix}.$

It is an SBBD$(4,3,12\,;\Lambda)$,
$\Lambda=(\mu,\lambda_{12},\lambda_{21},\lambda_{22})=(9,6,6,7),$ with the
information matrix

$X^{t}X=I_{3}\otimes\left[\begin{array}[]{ccc}9&6&6\\\ 6&9&6\\\
6&6&9\end{array}\right]+(J_{3}-I_{3})\otimes\left[\begin{array}[]{ccc}6&7&7\\\
7&6&7\\\ 7&7&6\end{array}\right].$

###  4.2 Regular and semi-regular SBBD

In this part, we consider a case that $(V,\mathcal{B})$ is a
$(v,k,\lambda)$-BIBD and introduce the constructions of semi-regular and
regular SBBDs.

######  Theorem 4.10.

If there is a $(v,k,\lambda)$-BIBD with b blocks and an ordered design
$OD_{\eta}(b,b)$ then there exist a semi-regular
SBBD$(b,v,b^{2}-b\,;\,\Lambda)$, where $\Lambda=(\eta
r(b-1),\eta\lambda(b-1),\eta r(r-1),\eta(r^{2}-\lambda))$.

Proof Let $H$ be the ($b\times v$) incidence matrix of a $(v,k,\lambda)$-BIBD
with $b$ blocks. $H$ has $k$ ones in each row and $r=kb/v$ ones in each
column. Consider $X$ is the design matrix constructed from $H$ and
$OD_{\eta}(b,b)$. Each row of $X$ is a SB-block of the SBBD
$(K_{b,v}\,;\,\mathcal{B})$. From the construction above, each SB-block
$B\in\mathcal{B}$ consists of permuted rows of $H$. If we reconstruct
$(b\times v)$-array from an SB-block, the number of $1$s in each row and in
each column is exactly the same as $H$. That is, each SB-block of $X$ is a
semi-regular bipartite subgraph of $K_{b,v}$, where the degrees of each point
of $V_{1}$ and $V_{2}$ are $k$ and $r$, respectively. ∎

A BIBD with $b=v$ is said to be a symmetric BIBD. From Property 4.3, an
$OD_{1}(b,b)$ exists if $b$ is a prime power.

######  Corollary 4.11.

If there is a $(v,k,\lambda)$-BIBD with a prime power number of blocks then
there exists a semi-regular SBBD, and if the $(v,k,\lambda)$-BIBD is symmetric
then there exist a regular SBBD.

Table 1 is a list of existing BIBD with a prime power number of blocks less
then $100$ selected from the table in [3]. The BIBDs in the list are all
symmetric except one. We can construct many A-optimal SBBDs.

Table 1: BIBD with prime power $b$ blocks

$v$ | $b$ | $r$ | $k$ | $\lambda$ | Remark
---|---|---|---|---|---
7 | 7 | 3 | 3 | 1 | PG(2,2)
11 | 11 | 5 | 5 | 2 |
13 | 13 | 4 | 4 | 1 | PG(2,3)
19 | 19 | 9 | 9 | 4 |
23 | 23 | 11 | 11 | 5 |
25 | 25 | 9 | 9 | 3 |
27 | 27 | 13 | 13 | 6 | 27=$3^{3}$
31 | 31 | 6 | 6 | 1 | PG(2,5)
31 | 31 | 10 | 10 | 3 |
31 | 31 | 15 | 15 | 7 | PG(4,2)
37 | 37 | 9 | 9 | 2 |
41 | 41 | 16 | 16 | 6 |
43 | 43 | 21 | 21 | 10 |
47 | 47 | 23 | 23 | 11 |

$v$ | $b$ | $r$ | $k$ | $\lambda$ | Remark
---|---|---|---|---|---
7 | 49 | 21 | 3 | 7 |
49 | 49 | 16 | 16 | 5 | 49=$7^{2}$
59 | 59 | 29 | 29 | 14 |
61 | 61 | 16 | 16 | 4 |
61 | 61 | 25 | 25 | 10 |
67 | 67 | 33 | 33 | 16 |
71 | 71 | 15 | 15 | 3 |
71 | 71 | 21 | 21 | 6 |
71 | 71 | 35 | 35 | 17 |
73 | 73 | 9 | 9 | 1 | PG(2,8)
79 | 79 | 13 | 13 | 2 |
79 | 79 | 27 | 27 | 9 |
79 | 79 | 39 | 39 | 19 |

##  5 Application to Deep Learning

Deep learning, in other words, a multi-layer neural network model, is a
network consisting of a sequence of point sets (node layers) and complete
bipartite graphs (connection layers) between consecutive node layers. Ignoring
the difference between solid and dotted lines, Fig. 2 gives an example.

Figure 2: DropConnect

The weight variables are associated with the edges (connection), and they are
gradually estimated using a large amount of training data that are pairs of
input data $\boldsymbol{x}_{i}$ and correct answers
$\boldsymbol{d}_{i},i=1,2,\ldots,N$. Let $\boldsymbol{W}$ be the all weight
parameters, and $y(\boldsymbol{x}_{i},\boldsymbol{W})$ be output.
$\boldsymbol{W}$ is estimated in the same way as regression so that the
following error function is minimized:

$E(\boldsymbol{W})=\frac{1}{2}\sum_{i=1}^{N}\parallel\boldsymbol{d}_{i}-y(\boldsymbol{x}_{i},\boldsymbol{W})\parallel^{2}.$

During the learning process, we regularly test using data not used in the
learning processes. At this time, the training data are learning smoothly, but
it often gets worse in the test. This is called overlearning or overfitting.
It is known that similar overfitting occurs in regression when the model has a
large number of parameters to be estimated. In deep learning, [11] proposed a
method called Dropout in 2014 as a way to deal with overfitting. This is a
method of randomly invalidating the points of each node layer and joining only
the valid points by a complete bipartite subgraph. This is a kind of so-called
sparsification. Regarding this method, Chisaki et al. 2020 and 2021 [1, 2]
have proposed a method applying the combinatorial design theory.

In 2013, [12] proposed another method called DropConnect, it is a method of
sparsification by randomly selecting some edges in a connection layer instead
of points of a node layer, for an example, solid lines in Fig. 2. We propose
to sparsify the edges in connection layers using SBBD, not by random
selection. In the DropConnect method, a node without an incoming connection
can occur. From the spanning condition of SBBD, we can sparsify independently
for each connection layer without occurring of such nodes. We expect to have a
balanced sparsifying system for a multi-layer neural network which have
statistically high precision for weight parameter estimations.

### Acknowledgments

I would like to express our sincere gratitude to Professor Shinji Kuriki. He
provided very important comments and advice during the writing of this paper.
In particular, we received great help from him for the optimality proof. This
work was supported in part by JSPS KAKENHI Grant Number JP19K11866.

## References

  * [1] Shoko Chisaki, Ryoh Fuji-Hara, and Nobuko Miyamoto, _Combinatorial designs for deep learning_ , Journal of Combinatorial Designs 28 (2020), no. 9, 633–657.
  * [2] Shoko Chisaki, Ryoh Fuji-Hara, and Nobuko Miyamoto, _A construction for circulant type dropout designs_ , Designs, Codes and Cryptography (2021), no. 89, 1839–1852.
  * [3] Charles J. Colbourn and Jeffrey H. Dinitz (eds.), _Handbook of combinatorial designs second edition_ , Discrete Mathematics and its Applications, Chapman and Hall/CRC, 2007.
  * [4] A Samad Hedayat, Neil James Alexander Sloane, and John Stufken, _Orthogonal arrays: theory and applications_ , Springer Science & Business Media, 1999.
  * [5] J. C. Kiefer, _General equivalence theory for optimum designs_ , Annals of Statistics 2 (1974), no. 5, 849–879.
  * [6] Xiao-Nau Lu, Miwako Mishima, Nobuko Miyamoto, and Masakazu Jimbo, _Optimal and efficient designs for fmri experiments via two-level circulant almost orthogonal arrays_ , Journal of Statistical Planning and Inference 213 (2021), 33–49.
  * [7] Kazuhiro Ozawa, Masakazu Jimbo, Sampei Kageyama, and Stanisław Mejza, _Optimality and construction of incomplete split-block designs_ , Journal of statistical planning and inference 106 (2002), 135–157.
  * [8] Friedrich Pukelsheim, _Optimal design of experiments_ , SIAM, 2006.
  * [9] C. Radhakrishna Rao, _Combinatorial arrangements analogous to orthogonal arrays_ , Sankhyā: The Indian Journal of Statistics, Series A 23 (1961), no. 3, 283–286.
  * [10] V. R. Rao, _A note on balanced designs_ , The Annals of Mathematical Statistics 27 (1958), 290–294.
  * [11] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov, _Dropout: A simple way to prevent neural networks from overfitting_ , Journal of Machine Learning Research 15 (2014), 1929–1958.
  * [12] Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus, _Regularization of neural networks using dropconnect_ , International conference on machine learning, PMLR, 2013, pp. 1058–1066.
  * [13] R. M. Wilson, _Constructions and uses of pairwise balanced designs_ , vol. Combinatrics (Proc. NATO Advanced Study Inst., Breukelen, 1974) Part 1: Theory of designs, finite geometry and coding theory, Math. Centre Tracts, No. 55, no. 55, Math. Centrum, Amsterdam, 1974, pp. 18–41.


11institutetext: Indian Institute of Space Science and Technology,
Thiruvananthapuram, India - 695547
11email<EMAIL_ADDRESS>
11email<EMAIL_ADDRESS>22institutetext: Human Space Flight Center,
ISRO, Bengaluru, India - 560054
22email<EMAIL_ADDRESS>
# Domain Adaptive Egocentric Person Re-identification

Ankit Choudhary 11 Deepak Mishra 11 Arnab Karmakar 1122

###### Abstract

Person re-identification (re-ID) in first-person (egocentric) vision is a
fairly new and unexplored problem. With the increase of wearable video
recording devices, egocentric data becomes readily available, and person re-
identification has the potential to benefit greatly from this. However, there
is a significant lack of large scale structured egocentric datasets for person
re-identification, due to the poor video quality and lack of individuals in
most of the recorded content. Although a lot of research has been done in
person re-identification based on fixed surveillance cameras, these do not
directly benefit egocentric re-ID. Machine learning models trained on the
publicly available large scale re-ID datasets cannot be applied to egocentric
re-ID due to the dataset bias problem. The proposed algorithm makes use of
neural style transfer (NST) that incorporates a variant of Convolutional
Neural Network (CNN) to utilize the benefits of both fixed camera vision and
first-person vision. NST generates images having features from both egocentric
datasets and fixed camera datasets, that are fed through a VGG-16 network
trained on a fixed-camera dataset for feature extraction. These extracted
features are then used to re-identify individuals. The fixed camera dataset
Market-1501 [20] and the first-person dataset EGO Re-ID [3] are applied for
this work and the results are on par with the present re-identification models
in the egocentric domain.

###### Keywords:

Egocentric Person Re-identification Neural Style Transfer Deep Learning Domain
Adaptation.

##  1 Introduction

With the introduction of wearable cameras in the 1990s by Steve Mann, a new
field of egocentric vision has opened up in the computer vision community. Due
to the affordability of these first-person recording devices, huge data is
being generated almost every day. However, the currently available structured
datasets for egocentric vision are quite small, due to the inherent challenges
of first-person vision such as blurriness due to motion of the camera,
illumination change, and poor video quality. Also, most of these data cannot
be used for person re-identification tasks due to a lack of individuals in
these videos, creating a lack of dedicated egocentric videos that can be used
for the task of egocentric re-ID.

Ample research has been carried out in the field of fixed-camera based re-ID,
but their applicability is limited for egocentric re-ID. A re-ID model trained
on a third person re-ID dataset tends to learn the intricate features of that
specific dataset only, but it becomes obsolete when re-identifying individuals
in an egocentric dataset. The existing literature for first-person re-ID i.e.
body parts based [3] and multiple views based[2] methods also suffer from
dataset bias.

To overcome these challenges, we propose a neural style transfer (NST) based
domain adaptation technique for egocentric person re-identification, which
make use of present fixed camera re-ID datasets to improve the performance of
egocentric re-ID. The application of domain adaptation to fixed camera
datasets has been widely studied in literature [14][18]. But the idea of using
domain adaptation to bridge the gap between fixed camera datasets and first-
person datasets have never been studied before to the best of our knowledge.

In this work, the following contributions are made to the research on first-
person re-identification: (1) we use style-transferred images generated by NST
to develop a re-ID model which can accurately re-identify individuals from
first-person vision dataset even when trained on a fixed-camera dataset (i.e.,
domain adaptation), thus decreasing/eliminating dataset bias; (2) we compare
and contrast the accuracies of our re-ID model on the generated (or style-
transferred) images as well as normal first-person images.

##  2 Related Work

###  2.1 Classic Person Re-ID

The initial developments in person re-ID make use of handcrafted features such
as texture and color. Gray et al. [5] used color channels along with texture
filters to re-identify pedestrian images partitioned into six horizontal
stripes. Color histograms and moments are extracted followed by dimension
reduction using PCA and LFDA in Pedagadi et al. [8]. With the onset of deep
learning, CNNs have found wide applications in person re-ID. In [17], long
short-term memory (LSTM) modules are utilized through a Siamese network.
Gating functions after each convolutional layer are used in [16] to capture
discriminative patterns in re-ID.

###  2.2 Egocentric Person Re-ID

Person re-ID in first-person videos have gained popularity with the widespread
use of first-person recording devices. Visual and sensor metadata were used in
[1] to successfully perform re-ID. Local features are extracted followed by
the application of 3D convolution to encode temporal information. In [2],
facial features were extracted and similarities were computed between a pair
of cameras to yield optimal and consistent re-ID results. People are
identified by dividing their images into meaningful body parts in [3].
Furthermore, the contribution of different body parts is calculated by taking
into account human gaze information.

Our work utilizes an egocentric dataset shot through a single camera in [3].
Rather than depending on different body parts, we take into account the
complete image of a person while re-identifying him.

###  2.3 Domain Adaptation in Image-to-Image Translation and Person Re-ID

Domain adaptation has led to significant success in image-to-image translation
through GANs [19] and CNNs [7]. pix2pix framework for image-to-image
translation was proposed in [6]. A conditional GAN was used to learn mappings
between two different sets of images, i.e., source images and target images.
Adapting simulation data to real-world data was done through domain confusion
loss and pairwise loss in [15]. Gatys et al. [4] computed the differences
between the style and content of the source and target images. This allowed
the target images to be viewed as source images without the loss of content. A
deep generative correlation alignment network (DGCAN) was proposed in [9] to
bridge domain discrepancy between real and synthetic images. This was done by
applying the content loss to several different layers.

Person re-ID intrinsically requires domain adaption, since, a model trained on
a labeled dataset consisting of groups of individuals is required to perform
well on unlabelled datasets without supervised fine-tuning. Self-supervised
domain adaptation was used in [14] for person re-ID. The source data was pre-
processed using GAN and a baseline was trained in a supervised manner using
the pre-processed data. The authors then assigned pseudo labels to target data
using the trained model and this constructed dataset was trained in a
supervised learning manner. Xiao et al. [18] proposed the domain guided
dropout algorithm that discards ineffective neurons while re-identifying
individuals on several datasets. In [10], style based mapping from target
domain to source domain was learned between different camera views. An
effective and generalized re-ID model was proposed in [21] by investigating
the intra-domain variations of the target domain.

Our work uses the state-of-the-art image-to-image translation model proposed
by Gatys et al. in [4] for transferring styles between first-person and fixed
camera dataset.

##  3 Approach

The schematic of the proposed egocentric re-ID model is shown in Fig. 1. The
first step in our model is the generation of images which has combined
features of fixed camera dataset (Market-1501 [20]) and first-person vision
dataset (EGO Re-ID [3]). Our model makes use of a VGG-16 [12] based Neural
Style Transfer

Figure 1: Flow Diagram of our proposed egocentric re-ID model showing various
blocks including style transfer and domain adaptation.

(NST) model to produce high-quality images in a manner that helps in bringing
the qualities of Market-1501 [20] into EGO Re-ID [3] while preserving the
content of EGO Re-ID [3]. This is achieved by formulating image generation
problem as an optimization one that minimizes the following losses: (1)
Content Loss, (2) Style Loss and (3) Total Loss.

The content difference between the generated and the EGO Re-ID [3] images are
captured through the content loss using a CNN. The input image is transformed
along the processing hierarchy of the CNN such that the image representations
are oblivious to the precise appearance of the image but are aware of the
image’s actual content. Thus, a network’s higher layers do not worry about the
exact pixel values. To capture the content information we make use of these
image representations which are present at higher layers as shown in Block C
of Fig. 2

The style loss captures the difference between the generated and the
Market-1501 [20] images. The feature space responsible for capturing texture
information is used for the computation of style loss. By computing the
feature correlations between different filter responses, we obtain the style
representation of the image. This style representation can thus be used to
compute the style loss. Unlike content loss, the style loss is computed across
all the layers as shown in Block A of Fig. 2

After computing the content and style loss, the total loss is calculated as a
linear relationship between content and style loss. After the images are
generated by minimizing the total loss, a pre-trained VGG model is fine-tuned
using images from Market-1501 [20] and image features are calculated for these
generated images after passing them through this fine-tuned model employing
domain adaptation as shown in the flow diagram of Fig. 1. Furthermore, average
pooling

Figure 2: Detailed illustration of Style Transfer Algorithm [4]. Blocks A and
B are used for computing style loss between style image and the generated
image, Blocks B and C are used for computing content loss between content
image and the generated image.

operation is adopted for the image synthesis task. According to [4], replacing
the max pooling with an average pooling offer somewhat better results.

###  3.1 Content Loss

Block C in Fig. 2 shows the computation of content loss. Let $\vec{g}$ and
$\vec{c}$ be the generated and content image respectively. And $A_{mn}^{l}(I)$
be the feature representations of the $m^{th}$ feature map at position n in
layer l of image I. Hence, the squared error loss between the content image
and the generated image is:

$\mathcal{L}_{\text{content
}}=\frac{1}{2}\sum_{m,n}\left(A_{mn}^{l}(g)-A_{mn}^{l}(c)\right)^{2}$ (1)

The loss is back-propagated by taking its derivative with the activations
present in layer l as shown in Block B in Fig. 2. And the initial white noise
image $\vec{g}$ keeps on changing until we get the same response as the
content image $\vec{c}$.

###  3.2 Style Loss

Block A in Fig. 2 shows the computation of style loss. The feature map
correlations are given by Gram matrix:

$F_{mn}^{l}(I)=\sum_{o}A_{mo}^{l}(I)A_{no}^{l}(I)$ (2)

where, $F_{mn}^{l}(I)$ gives the inner product between the feature maps (in
vectorised form) m and n at layer l of image I.

Let $\vec{s}$ and $\vec{g}$ be the original and generated images respectively.
And $F_{mn}^{l}(I)$ be their feature representations of the $m^{th}$ filter
which is located at position n in the layer l of image I. Hence, the squared
error loss between the style image and generated image is:

$E_{l}=\frac{1}{4N_{l}^{2}M_{l}^{2}}\sum_{m,n}\left(F_{mn}^{l}(g)-F_{mn}^{l}(s)\right)^{2}$
(3)

where, the product of $N_{l}$ and $M_{l}$ represents the size of the layer l.

Since, style loss consists of multiple layers, we need to define a weighting
factor in order to incorporate the contribution of each layer to the loss.
Thus, giving us the total style loss as:

$\mathcal{L}_{\mathrm{style}}=\sum_{l=0}^{L}w_{l}E_{l}$ (4)

The derivatives of $E_{l}$ with respect to the activations of layer l can be
computed and backpropagated as shown in Block B in Fig. 2.

###  3.3 Total Loss

We intend to jointly minimize the content loss between the white noise image
and the content from the first-person image at one layer and the style loss
between the white noise image and the style from the fixed camera image on
several layers. The loss function to be minimized is:

$\mathcal{L}_{\text{total }}=\alpha\mathcal{L}_{\text{content
}}+\beta\mathcal{L}_{\text{style }}$ (5)

where $\alpha$ is the weight factor for content reconstruction while $\beta$
is the weight factor for style reconstruction.

There is a trade-off between content and style being represented in a
generated image. If the generated image has learned better content then its
style will be bad and vice-versa. To balance both content and style, weighting
factors are included in the final loss expression.

###  3.4 Style Transfer based Person Re-ID

The style transferred images generated by the NST algorithm are used to re-
identify individuals. VGG-16 [12] is used to extract the image descriptors.
The overfit reduction techniques used were weight decay and dropout. To merge
the EGO Re-ID dataset [3] (2343 images of 24 persons) with a fixed camera
dataset, we used an equal number of images from the fixed camera dataset
(Market-1501 [20]). The ‘Training Set 1’ consists of 2343 images from
Market-1501 dataset [20] which were used as style images with the EGO Re-ID
[3] content images. The ‘Training Set 2’ consists of arbitrary 2343 images
from the Market-1501 dataset [20]. These images were not used for style
transferring the EGO Re-ID dataset [3]. The ‘Training Set 3’ consists of
images from both Training Set 1 and Training Set 2. Thus, comprising a total
of 4686 images from Market-1501 dataset [20].

These three sets of images were used to finetune a VGG-16 model pre-trained on
ImageNet. The three separate trained models were then used to predict the
classes for the style transferred images from the EGO Re-ID dataset [3]. The
results obtained through various evaluation methods are presented in Table 1.

For predicting the classes of the individuals from the first-person dataset,
some changes were made to the trained model. The final softmax layer of the
models trained on Training Set 1, Training Set 2, and Training Set 3 image
sets were removed. So, after passing the images through the trained model, a
4096 length vector was extracted from the fifteenth layer of the network. This
vector comprises all the features present in the style transferred images and
is referred to as the image descriptor. The distance between these image
descriptors was calculated using the Euclidean metric. Also, CMC curves are
generated based on the Euclidean distance between these extracted feature
vectors. Since there are multiple ground truths for a single query image, mAP
scores were also computed.

##  4 Experiments and Results

###  4.1 Datasets

The experiment was conducted using two datasets to evaluate our model, (1)
Market-1501 [20] as style dataset, and (2) EGO Re-ID [3] as content dataset.

The Market-1501 dataset [20] consists of over 32,000 annotated bboxes with
over 1500 identities, plus a distractor set of over 500K images

EGO Re-ID dataset [3] is recorded in 3 different locations through a frontal
camera of an eye-tracking device. Each location consists of 8 persons with 100
images of each under different viewpoints. There are a total of 2343 images
across 24 identities.

###  4.2 Evaluation Methodologies

Cumulative matching characteristic (CMC) curves are most commonly used for
evaluating person re-ID algorithms. They are accurate for evaluating re-ID
methodology when only one ground truth for each query exists. In this work, a
query can have multiple ground truths, so using only CMC curves does not fully
reflect the true ranking results as well as the accuracy of the model. To
tackle this issue we use both CMC and mAP (mean Average Precision) scores as
the evaluation metric.

###  4.3 Implementation Details

TensorFlow was used to build our model. Style loss is calculated across layers
1_1, 2_1, 3_1, 4_1 and 5_1 of VGG-16 as shown in Block A of Fig. 2. For
content loss, layer 5_2 was used as shown in Block C of Fig. 2. Each layer
contributed equally to the style loss, hence the value of $w_{l}$ for all the
layers was set at 0.2. The ratio of $\alpha$ and $\beta$ was set to 1 $\times$
$10^{-3}$ in the final loss function. The L2 regularization was set to a value
of 5 $\times$ $10^{-4}$ in VGG to reduce overfitting of data. Also, the
dropout rate was set to 0.5. 100 epochs were performed to generate style
transferred images using NST. The learning rate was set to 1 $\times$
$10^{-3}$. Each image took 3-4 minutes to generate. During training Adam
optimizer was used with its default parameter values, i.e., $\beta_{1}$ = 0.9
and $\beta_{2}$ = 0.999.

###  4.4 Results

Given a content and style image, NST generated flawless images which
incorporates both style and content images. A large number of generated images
were successful in blending content and style (Fig. 3) whereas only a few
images were unsuccessful in blending the styles (Fig. 4). These failure cases
can be attributed to the lack of proper transfer of content or style features
from the content and style images respectively.

(a)

(b)

(c)

Figure 3: Success Case of image generated by NST: (a) Content image (EGO Re-ID
dataset [3]); (b) Style image (Market-1501 dataset [20]); (c) Style
transferred image. The incorporation of style into the content is very well.

The training data for our work was divided into three sets as mentioned
earlier. The details of the nomenclature used are provided below:

  * •

Basic Model is the VGG model trained on the ImageNet dataset. No other fine-
tuning was done on this model.

  * •

Training Set 1, 2, and 3 were used to fine-tune the Basic Model to obtain
Model 1, 2, and 3 respectively.

  * •

Style transferred images are the images generated by the NST algorithm.

  * •

Normal images are the images from EGO Re-ID dataset [3] without undergoing
style transfer.

The details mentioned above about different models will be helpful in
understanding the contents of Table 1.

(a)

(b)

(c)

Figure 4: Failure Case of image generated by NST: (a) Content image (EGO Re-ID
dataset [3]); (b) Style image (Market-1501 dataset [20]); (c) Style
transferred image. The content and generated images are similar except for the
blur due to similarity in content and style images. Major reason for the loss
of perceptual quality can be attributed to the fact that the style images are
of low quality, hence the quality of all the generated images is degraded to
an extent.

From Table 1, we can observe that the style transferred images whose features
were extracted through Model 1 has the highest mAP score and the highest
recognition rate across all ranks. We can also observe that the recognition
rate of normal images across all the training models when compared with their
style-transferred counterparts are the lowest.

Table 1: Column 1 lists the training sets which were used. Recognition percentage (%) at r-1, r-5 and r-10 are provided for different training sets. The mean Average Precision (mAP) scores of model trained under different training sets are provided in the last column. Training Model | Style Transferred | Rank 1 | Rank 5 | Rank 10 | mAP
---|---|---|---|---|---
Model 1 | Yes | 57.66 | 75.07 | 81.63 | 65.88
No | 19.60 | 43.74 | 59.32 | 31.79
Model 2 | Yes | 34.47 | 55.12 | 66.23 | 44.32
No | 26.60 | 45.67 | 56.26 | 36.35
Model 3 | Yes | 44.53 | 65.70 | 75.33 | 55.22
No | 18.98 | 44.27 | 59.23 | 31.61
Basic Model | Yes | 33.42 | 62.12 | 75.15 | 47.30
No | 29.22 | 47.94 | 59.32 | 38.85

The high values of recognition rate obtained after computing the distance
between the features of style transferred images extracted from Model 1
implies that individuals in first-person domain can be re-identified through
domain adaptive techniques. For rank-1, the recognition percentage has jumped
from 18.98% when using Model 3 and non-style transferred images to 57.66% when
Model 1 and style transferred images are utilised. This is a 203.8% increment
in the recognition rate. Even when considering the same model, i.e., Model 1,
the recognition rate for rank-1 has jumped from 19.6% to 57.66% when non-style
transferred images were replaced by style transferred images, which is a
194.2% increment in recognition percentage. Similar trends can be observed
across all the ranks.

The main aim of this work was to present a egocentric person re-ID algorithm
with good accuracy and a technique to eliminate dataset bias so that the
models trained on third-person dataset does not become obsolete while testing
on a first-person dataset. From Table 1 it is clear that this re-ID algorithm
has good accuracy and the increment in recognition percentage when non-style
transferred images are replaced with style transferred images is significant
which shows that even though the model is trained on a third-person dataset,
it’s quite accurate when tested on a first-person dataset. The first-person
dataset used in this work has been used for a different re-ID algorithm as
well [3]. The comparison of the mAP scores of both the models has been
provided in Table 2.

Table 2: Comparison of mean Average Precision (mAP) scores between [3] and our approach Approach | mAP scores
---|---
Using Torso description | 53.1
Using Face description | 60.3
Using Full body (with uniform weights) | 67.5
Using Full body (with gaze weights) | 70.3
Ours | 65.88

From Table 2 we can infer that our approach has better mAP scores when a few
body parts of the individuals are used for re-ID in [3]. But when the full
body of the individual is considered for re-ID in [3], our approach falls
behind, but not by a large margin. Even though, our mAP score is lower than
the approach in [3] when considering full body of the individual, our approach
utilizes style transfer, which can give consistent results irrespective of the
dataset it is trained on. The approach in [3] will fall behind in mAP scores
when it is tested on a different dataset due to the issue of dataset bias. Our
work can thus perform superior irrespective of datasets it will be trained on.

Table 3: Recognition percentage (%) at r-1 and r-5 are provided to compare our approach with different state-of-the-arts approaches. The mean Average Precision (mAP) scores of our approach and different state-of-the-arts approaches are provided in the last column. Approach | Rank-1 | Rank-5 | mAP scores
---|---|---|---
PSE+ECN [11] | 15.17 | 25.79 | 8.58
MGCAM [13] | 18.48 | 29.79 | 14.60
EgoRe-ID [1] | 53.02 | 63.52 | 44.79
Ours | 57.66 | 75.07 | 65.88

There has been other works on egocentric person re-ID using a different ego
re-ID dataset. The comparison of the results of all those work with ours are
provided in Table 3. The datasets used in the state-of-the-art approaches
mentioned in Table 3 are different from our dataset. EgoRe-ID dataset is much
bigger than EGO Re-ID dataset [3]. The difference in our results can be
attributed to the differences in sizes of the dataset. Overall our approach
performed well as can be seen from Table 2 and 3.

##  5 Conclusion

We have proposed a novel egocentric person re-ID approach by transferring
styles of fixed camera datasets into first-person datasets. Fixed camera
approaches cannot be used for re-identifying when the dataset changes due to
dataset bias. Extensive experimentation by using different sets of training
data has shown that our approach of re-identifying individuals through domain
adaptation is acceptable. Increment in recognition rate as high as 203.8% was
observed when style-transferred images were used. The best model came out to
be Model 1, which was trained on the same images from Market-1501 [20] which
were used for style transferring the EGO Re-ID dataset [3]. NST algorithm
learns the style features from the Market-1501 dataset [20] in a really good
way with some exceptions. The computation time required to generate these
images is the bottleneck. Although our model performs well, some of the images
generated by NST are not incorporating elements of the fixed camera dataset as
discussed in failure cases. This problem can be solved by using GAN based
image translation algorithms.

## References

  * [1] Basaran, E., Tesfaye, Y.T., Shah, M.: Egoreid dataset: Person re-identification in videos acquired by mobile devices with first-person point-of-view. arXiv preprint arXiv:1812.09570 (2018)
  * [2] Chakraborty, A., Mandal, B., Yuan, J.: Person reidentification using multiple egocentric views. IEEE Transactions on Circuits and Systems for Video Technology 27(3), 484–498 (2017)
  * [3] Fergnani, F., Alletto, S., Serra, G., Mira, J.D., Cucchiara, R.: Body part based re-identification from an egocentric perspective. 2016 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) pp. 355–360 (2016)
  * [4] Gatys, L.A., Ecker, A.S., Bethge, M.: Image style transfer using convolutional neural networks. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) p. 2414–2423 (2016)
  * [5] Gray, D., Tao, H.: Viewpoint invariant pedestrian recognition with an ensemble of localized features. European Conference on Computer Vision (2008)
  * [6] Isola, P., Zhu, J.Y., Zhou, T., Efros, A.A.: Image-to-image translation with conditional adversarial networks. arXiv preprint arXiv:1611.07004 (2016)
  * [7] Jing, Y., Yang, Y., Feng, Z., Ye, J., Yu, Y., Song, M.: Neural style transfer: A review. IEEE Transactions on Visualization and Computer Graphics pp. 1–1 (2019)
  * [8] Pedagadi, S., Orwell, J., Velastin, S., Boghossian, B.: Local fisher discriminant analysis for pedestrian re-identification. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) pp. 3318–3325 (2013)
  * [9] Peng, X., Saenko, K.: Synthetic to real adaptation with deep generative correlation alignment networks. arXiv preprint arXiv:1701.05524 (2017)
  * [10] Ren, C., Liang, B., Ge, P., Zhai, Y., Lei, Z.: Domain adaptive person re-identification via camera style generation and label propagation. IEEE Transactions on Information Forensics and Security 15, 1290–1302 (2020)
  * [11] Sarfraz, M.S., Schumann, A., Eberle, A., Stiefelhagen, R.: A pose-sensitive embedding for person re-identification with expanded cross neighborhood re-ranking. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) pp. 420–429 (2018)
  * [12] Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 (2014)
  * [13] Song, C., Huang, Y., Ouyang, W., Wang, L.: Mask-guided contrastive attention model for person re-identification. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) pp. 1179–1188 (2018)
  * [14] Tang, H., Zhao, Y., Lu, H.: Unsupervised person re-identification with iterative self-supervised domain adaptation. The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops (2019)
  * [15] Tzeng, E., Devin, C., Hoffman, J., Finn, C., Abbeel, P., Levine, S., Saenko, K., Darrell, T.: Adapting deep visuomotor representations with weak pairwise constraints. CoRR (2015)
  * [16] Varior, R.R., Haloi, M., G.Wang: Gated siamese convolutional neural network architecture for human re-identification. European Conference on Computer Vision (ECCV) (2016)
  * [17] Varior, R.R., Shuai, B., Lu, J., Xu, D., Wang, G.: A siamese long short-term memory architecture for human re-identification. European Conference on Computer Vision (ECCV) (2016)
  * [18] Xiao, T., Li, H., Ouyang, W., Wang, X.: Learning deep feature representations with domain guided dropout for person re-identification. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition pp. 1249–1258 (2016)
  * [19] Yongxin, Z.: A survey of image to image translation with gans (2020)
  * [20] Zheng, L., Shen, L., Tian, L., Wang, S., Wang, J., Tian, Q.: Scalable person re-identification: A benchmark. IEEE International Conference on Computer Vision (ICCV) (2015)
  * [21] Zhong, Z., Zheng, L., Luo, Z., Li, S., Yang, Y.: Invariance matters: Exemplar memory for domain adaptive person re-identification. Computer Vision and Pattern Recognition (CVPR) (2019)