# Sparse recovery guarantees for block orthogonal binary matrices constructed
via Generalized Euler Squares

Pradip Sasmal†, Phanindra Jampana and C. S. Sastry  †Dept. of ECE, Indian
Institute of Science, Bangalore, India
email<EMAIL_ADDRESS>
Indian Institute of Technology, Hyderabad, Telangana. 502285, India.
Email:{pjampana<EMAIL_ADDRESS>
###### Abstract

In recent times, the construction of deterministic matrices has gained
popularity as an alternative of random matrices as they provide guarantees for
recovery of sparse signals. In particular, the construction of binary matrices
has attained significance due to their potential for hardware-friendly
implementation and appealing applications. Our present work aims at
constructing incoherent binary matrices consisting of orthogonal blocks with
small block coherence. We show that the binary matrices constructed from Euler
squares exhibit block orthogonality and possess low block coherence. With a
goal of obtaining better aspect ratios, the present work generalizes the
notion of Euler Squares and obtains a new class of deterministic binary
matrices of more general size. For realizing the stated objectives, to begin
with, the paper revisits the connection of finite field theory to Euler
Squares and their construction. Using the stated connection, the work proposes
Generalized Euler Squares (GES) and then presents a construction procedure.
Binary matrices with low coherence and general row-sizes are obtained, whose
column size is in the maximum possible order. Finally, the paper shows that
the special structure possessed by GES is helpful in resulting in block
orthogonal structure with small block coherence, which supports the recovery
of block sparse signals.

###### keywords:

Compressed Sensing, Euler Square, Generalized Euler Square, Block sparsity.

††journal:

##  1 Introduction

Recent developments at the intersection of algebra, probability and
optimization theory, by the name of Compressed Sensing (CS), aim at providing
sparse descriptions to linear systems. These developments are found to have
tremendous potential for several applications [7][20]. Sparse representations
of a vector are a powerful analytic tool in many application areas such as
image/signal processing and numerical computation [13], to name a few. The
need for sparse representation arises from the fact that several real life
applications demand expressing data in terms of as few basis elements as
possible. The developments of CS theory depend typically on sparsity and
incoherence [13][14].

For minimizing the computational complexity associated with the matrix-vector
multiplication, it is desirable that a CS matrix has smaller density. Here, a
CS matrix refers to a matrix that satisfies sparse recovery properties and
density refers to the ratio of number of nonzero entries to the total number
of entries of the matrix. Sparse CS matrices, especially binary matrices,
contribute to fast processing with low computational complexity in CS [20].
The low coherence of a CS matrix, on the other hand, provides guarantees for
recovering sparse signals via basis pursuit (BP) and orthogonal matching
pursuit (OMP). In case of recovery of block sparse signals, the block
coherence of a CS matrix plays an important role [25]. To date, less attention
has been paid to constructing binary matrices with small coherence which also
possess low block coherence. Our present work is on the construction of block
orthogonal binary matrices with small coherence and block coherence so that
they support recovery of sparse signals and block sparse signals
simultaneously.

In recent literature on deterministic CS matrices, several authors [4], [5],
[6], [18], [19], [21], [22], [23], [24] have made pioneering contributions
using novel ideas. Nevertheless, in most of these constructions, the
associated CS matrices have been constructed for sizes that are dictated by a
certain family of prime numbers. Additionally, none of the these constructions
are known to exhibit block orthogonal structure.

Recently in [3], the authors have proposed a method to construct compressed
sensing matrices from Euler Square. In particular, given a positive integer
$m$ different from $p,p^{2}$ for a prime $p$, the authors [3] have shown that
it is possible to construct a binary sensing matrix of size $m\times
c(m\mu)^{2}$ using Euler Squares, where $\mu$ is the coherence of the matrix
(the maximum off-diagonal entry, in magnitude, of Gram matrix) and
$c\in[1,2).$ One of the objectives of present work is to improve upon the
aspect ratio (the ratio of column size to row size) of the CS matrices. To
realize this objective, we propose a generalization of the concept of the
Euler Square, namely, Generalized Euler Square (GES). To begin with, we
construct an Euler Square of index $p,k$, where $p$ is a prime or prime power,
using polynomials of degree at most one over a finite field of order $p.$
Generalized Euler Square of index $p,k,t$ are then constructed using
polynomials of degree at most $t.$ Using a composition rule a new GES for non-
prime sizes are obtained from the combination of two GES of prime sizes.
Further, we propose a methodology to construct compressed sensing matrices
from GES. The matrices designed from GES show significant improvements in
terms of column size. In particular, the binary matrix constructed from
GES($n,k,t$) has $n^{t}$ number of orthogonal blocks, each of size $nk\times
n.$ We discuss the structure of the binary matrices generated from generalized
Euler Squares, and show that they possess block orthogonality. We also derive
that binary matrices constructed from Euler Square and GES possess low block
coherence, providing thereby guarantees for recovering block sparse signals.
The contributions of the present work may be summarized as follows:

  * 1.

presenting Euler Squares with a different perspective and associating them
with polynomials of degree at most one over a finite field.

  * 2.

establishing block orthogonal structure of binary matrices constructed via
Euler Squares in [3] and showing their compliance with block sparse recovery
properties

  * 3.

introducing Generalized Euler Squares (GES) and providing their construction
procedure

  * 4.

bringing significant increment in column size compared to the ones obtained
via Euler Squares

  * 5.

establishing block orthogonal structure of the GES based binary matrices.

The paper is organized in several sections. In section 2, we provide basics of
CS theory and Euler Squares. While in sections 3 and 4, we discuss
respectively the block sparse recovery through Euler Square based matrices and
block orthogonality, and construction of Euler Square based matrices using
polynomials of degree at most one over finite field. In sections 5 and 6, we
introduce Generalized Euler Squares and their construction respectively. In
sections 7 and 8, we present respectively the construction of Euler Squares
for composite order and construction of binary matrices using GES. In sections
9 and 10, we present GES as a rectangular array and the recovery guarantees
for block sparse signals via GES. The paper ends with concluding remarks in
Section 11.

##  2 Basics of Compressed Sensing and Euler Squares:

The objective of compressed sensing is to recover
$x=\\{x_{i}\\}^{M}_{i=1}\in\mathbb{R}^{M}$ from a few of its linear
measurements $y\in\mathbb{R}^{m}$ through a stable and efficient
reconstruction process via the concept of sparsity. From the measurement
vector $y$ and the sensing mechanism, one gets a system $y=\Phi x$, where
$\Phi$ is an $m\times M\;(m<M)$ measurement matrix. An excellent overview of
Compressed Sensing and the applicability of several sensing matrices may be
seen in [16].

Given the pair $(y,\Phi)$, the problem of recovering $x$ can be formulated as
finding the sparsest solution (solution containing most number of zero
entries) of linear system of equations $y=\Phi x$. Sparsity is measured by
$\|.\|_{0}$ “norm”. $\|x\|_{0}$ denotes the number of non-zero entries in $x$,
that is, $\|x\|_{0}=|\\{j:x_{j}\neq 0\\}|$, where $\|.\|_{0}$ is neither a
norm nor a quasi-norm. Now finding the sparsest solution can be formulated as
the following minimization problem, generally denoted as $P_{0}$ problem:

$P_{0}:\min_{x}\|{x}\|_{0}\;\mbox{subject to}\quad\Phi x=y.$

This is a combinatorial optimization problem and is known to be NP-hard [7].
One may use greedy methods and convex relaxation of $P_{0}$ problem to recover
the $k-$sparse signals (i.e., signals for which $\|x\|_{0}\leq k$). The convex
relaxation of $P_{0}$ problem can be posed as $P_{1}$ problem [8] [11], which
is defined as follows:

$P_{1}:\min_{x}\|{x}\|_{1}\;\mbox{subject to}\quad\Phi x=y.$

Candes and Tao [9] have introduced the following isometry condition on
matrices $\Phi$ and have established its important role in CS. An $m\times M$
matrix $\Phi$ is said to satisfy the Restricted Isometry Property(RIP) of
order $k$ with constant $\delta_{k}$ $(0<\delta_{k}<1)$ if for all vectors
$x\in\mathbb{R}^{M}$ with $\|x\|_{0}\leq k$, we have

$(1-\delta_{k})\left\|x\right\|^{2}_{2}\leq\left\|\Phi
x\right\|^{2}_{2}\leq(1+\delta_{k})\left\|x\right\|^{2}_{2}.$ (1)

Equivalently, for all vectors $x\in\mathbb{R}^{M}$ with
$\left\|x\right\|_{2}=1$ and $\|x\|_{0}\leq k$, one may rewrite (1) as

$(1-\delta_{k})\leq\left\|\Phi x\right\|^{2}_{2}\leq(1+\delta_{k}).$

The following theorem [11] establishes the equivalence between $P_{0}$ and
$P_{1}$ problems:

######  Theorem 2.1.

Suppose an $m\times M$ matrix $\Phi$ has the $(2k,\delta)$ restricted isometry
property for some $\delta<\sqrt{2}-1$, then $P_{0}$ and $P_{1}$ have same
$k-$sparse solution if $P_{0}$ has a $k-$sparse solution.

The coherence $\mu(\Phi)$ of a given matrix $\Phi$ is the largest absolute
inner-product between different normalized columns of $\Phi$, i.e.,
$\mu_{\Phi}=\max_{1\leq\;i,j\leq\;M,\;i\neq
j}\frac{|\;\Phi_{i}^{T}\phi_{j}|}{\|\Phi_{i}\|_{2}\|\Phi_{j}\|_{2}}$. Here,
$\Phi_{k}$ stands for the $k$-th column in $\Phi$. The following proposition
[7] relates the RIP constant $\delta_{k}$ and $\mu_{\Phi}.$

######  Proposition 2.2.

Suppose that $\phi_{1},\ldots,\phi_{M}$ are the unit norm columns of a matrix
$\Phi$ with the coherence $\mu_{\Phi}.$ Then $\Phi$ satisfies RIP of order $k$
with constant $\delta_{k}=(k-1)\mu_{\Phi}$.

The Orthogonal Matching Pursuit (OMP) algorithm and and the $l_{1}-$norm
minimization (also called basis pursuit) are two widely studied CS
reconstruction algorithms [15]. One of the important problems in CS theory
deals with constructing CS matrices that satisfy the RIP for the largest
possible range of $k$. It is known that the widest possible range of $k$ is of
the order $\frac{m}{\log(\frac{M}{m})}$ [10], [12], [17]. However the only
known matrices that satisfy the RIP for this range are based on random
constructions [11], [12].

###  2.1 Block sparse signal recovery

Block sparse signals are sparse signals where the nonzero coefficients occur
in clusters. A signal $x\in\mathbb{R}^{M}$ is viewed as a concatenation of $R$
number of blocks of length $d$ with $M=Rd.$ Denote the $\ell-$th block as
$x[\ell],$ then

$x=(x^{T}[1],x^{T}[2],\dots,x^{T}[R]),$

where $x^{T}[\ell]=(x_{(\ell-1)d+1},x_{(\ell-1)d+2},\dots,x_{\ell d}).$ The
measurements can then be written as

$y=\Phi x=\sum^{R}_{\ell=1}\Phi[\ell]x[\ell],$

where $\Phi[\ell]=[\phi_{(\ell-1)d+1},\phi_{(\ell-1)d+2},\dots,\phi_{\ell d}]$
and $\phi_{j}$ is the $j-$th column of $\Phi.$ The vector $x$ is called block
$k-$sparse if $x[\ell]$ has nonzero Euclidean norm for at most $k$ indices
$\ell$. When $d=1$, block sparsity reduces to conventional sparsity. Define
$\|x\|_{2,0}$ as

$\|x\|_{2,0}=\sum^{R}_{\ell=1}I(\|x[\ell]\|_{2}>0),$

where $I(\cdot)$ is the indicator function. A block $k-$sparse signal $x$ is
defined as the signal that satisfies $\|x\|_{2,0}\leq k$ [25], by definition.

######  Definition 2.3.

[25] Block coherence of a matrix $\Phi$ with normalized columns is defined as

$\mu_{B_{\Phi}}=\frac{1}{d}\max_{\ell,\ell\neq
r}\lambda^{\frac{1}{2}}_{\max}(M^{T}[\ell,r]M[\ell,r]),$

where $M[\ell,r]=\Phi^{T}[\ell]\Phi[r]$ and $\lambda_{\max}(A)$ is the largest
eigen value of a positive semidefinite matrix $A.$

It is known that $0\leq\mu_{B_{\Phi}}\leq\mu_{\Phi}$ [25].

######  Proposition 2.4.

[25] If $\Phi$ consists of orthogonal blocks, that is,
$\Phi^{T}[\ell]\Phi[\ell]=I_{d\times d},\,\forall\,\ell,$ then
$\mu_{B_{\Phi}}\leq\frac{1}{d}.$

######  Theorem 2.5.

[25] A sufficient condition for the Block OMP to recover a block $k-$sparse
signal $x$, with each block length $d$, from $y=\Phi x$ is

$kd<\frac{\mu^{-1}_{B_{\Phi}}+d}{2},$

where $\Phi$ is block orthogonal, that is,
$\Phi^{T}[\ell]\Phi[\ell]=I_{d\times d},\,\forall\,\ell.$

###  2.2 Euler Square and Generalized Latin square

An Euler Square (ES) of order $n$, degree $k$ and index $n,k$ is a square
array of $n^{2}$ $k-$ads of numbers, $(a_{ij1},a_{ij2},\ldots,a_{ijk})$, where
$a_{ijr}=0,1,2,\ldots,n-1;r=1,2,\ldots,k;i,j=1,2,\ldots,n;n>k;a_{ipr}\neq
a_{iqr}$ and $a_{pjr}\neq a_{qjr}$ for $p\neq q$ and
$(a_{ijr},a_{ijs})\neq(a_{pqr},a_{pqs})$ for $i\neq p$ and $j\neq q.$ In short
we denote an Euler Square of order $n$, degree $k$ and index $n,k$ as
ES($n,k$). Harris F. MacNeish [1] has constructed Euler Squares for the
following cases:

  1. 1.

Index $p,p-1$, where $p$ is a prime number

  2. 2.

Index $p^{r},p^{r}-1$, for $p$ prime

  3. 3.

Index $n,k$, where $n=2^{r}p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots,p^{r_{l}}_{l}$ for
distinct odd primes $p_{1},p_{2},\ldots,p_{l}$. Here,
$k=\min\\{2^{r},p^{r_{1}}_{1},p^{r_{2}}_{2},\ldots,p^{r_{l}}_{l}\\}-1.$

######  Lemma 2.6.

[1] Let $k^{\prime}<k$. Then the existence of the Euler Square of index $n,k$
implies that the Euler Square of index $n,k^{\prime}$ exists.

An Euler Square of degree one is called a Latin Square and of degree two a
Graeco-Latin Square [1, 2]. Euler squares are also called as mutually
orthogonal Latin squares. In [26, 27], the authors have proposed
generalization of latin squares and their orthogonality.

##  3 Block sparse signal recovery for matrices constructed from Euler Square

The authors of [3] have constructed binary matrix $\Phi^{n}_{k}$ of size
$nk\times n^{2}$ with coherence at most $\frac{1}{k}$, whenever ES($n,k$)
exists. In this section, it is shown that the binary matrices obtained from
Euler Squares also contain a block orthogonal structure.

An Euler square can be observed to be an $n\times n$ square array of
$k$-tuples with the following properties:

  * 1.

(ES 1) : each array entry is a $k-$tuple of numbers obtained from
$\\{0,\dots,n-1\\}$

  * 2.

(ES 2) : there is no intersection between any two $k-$tuples on the same row
and same column

  * 3.

(ES 3) : there is at most one intersection between any two distinct $k-$tuples
which are not from the same row or column

Here intersection between two $k-$tuples denotes the number of indices where
the corresponding entries of both the tuples are same.

For example, the Euler Square of index $3,2$ is stated as

$0,0\ \ \ \ 1,1\ \ \ \ 2,2$ $1,2\ \ \ \ 2,0\ \ \ \ 0,1$ $2,1\ \ \ \ 0,2\ \ \ \
1,0$

###  3.1 Block orthogonality

######  Theorem 3.1.

If ES$(n,k)$ exists, then a sparse matrix of size $nk\times n^{2}$ exists
which consists of $n$ orthonormal blocks, each of size $nk\times n.$

###### Proof.

From the construction procedure given in [3], a binary matrix $\Phi^{n}_{k}$
of size $nk\times n^{2}$ is obtained from ES($n,k$). Every column of
$\Phi^{n}_{k}$ corresponds to a unique $k-$tuple of ES($n,k$). We arrange the
columns of $\Phi^{n}_{k}$ to form a block orthogonal matrix. We form the
$\ell-$th block (of block size $n$) by taking $n$ columns of $\Phi^{n}_{k}$
corresponding to $n$ $k-$tuples coming from $\ell-$th column of ES($n,k$).
From the definition of Euler Squares, two distinct $k-$tuples belonging to
same column of an Euler Square do not have any intersection. As a result, the
inner product between any two distinct columns within a block is zero,
implying thereby that each block is orthogonal. Consequently, the block matrix
$\frac{1}{\sqrt{k}}\Phi^{n}_{k}$ has $n$ orthonormal blocks, where each block
is of size $nk\times n.$ ∎

For example, let $\Phi^{3}_{2}$ be the binary matrix constructed from the
ES($3,2$). Now the blocks of $\Phi^{3}_{2}$ corresponding to first, second and
third columns are

$\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\\\ 1&0&0\\\ 0&0&1\\\
0&1&0\end{pmatrix},$ $\begin{pmatrix}0&0&1\\\ 1&0&0\\\ 0&1&0\\\ 0&1&0\\\
1&0&0\\\ 0&0&1\end{pmatrix}$ and $\begin{pmatrix}0&1&0\\\ 0&0&1\\\ 1&0&0\\\
0&0&1\\\ 0&1&0\\\ 1&0&0\end{pmatrix}$ respectively.

Now it is easy to see that the blocks are orthogonal. Therefore $\Phi^{3}_{2}$
consists of $3$ orthogonal blocks, where each block is of size $6\times 3.$

##  4 Construction of Euler Squares using finite fields

In [1], the author has used group theoretical results to construct Euler
Squares. In [2], R. C. Bose has constructed Euler square using polynomials
over finite field. In this section, we revisit the construction given in [2]
and present a construction of Euler square using polynomials of degree at most
one over finite fields.

###  4.1 Construction procedure for prime or prime power order

######  Theorem 4.1.

Suppose $p$ is prime prime power. Then ES($p,p-1$) exists.

###### Proof.

Let $D^{p}_{1}=\\{P^{1}_{ij}=f_{i}x+f_{j}:i,j=1,2,\dots,p\\}$ denote
polynomials of degree at most one over a finite field
$\mathbb{F}_{p}=\\{f_{0}=0,f_{1}\dots,f_{p-1}\\}$ of order $p.$ There are
$p^{2}$ number of polynomials of degree at most one. Form the $k-$tuple,
$S_{k}=(f_{1},\dots,f_{k}),$ for $1\leq k\leq p-1.$ Evaluating a polynomial
$P^{1}_{ij}$ of $D^{p}_{1}$ at every point of $S_{k},$ we form an ordered
$k-$tuple
$P^{1}_{ij}(S_{k})=(P^{1}_{ij}(f_{1}),\dots,P^{1}_{ij}(f_{k}))\in\mathbb{F}^{k}_{p}.$
Let us denote
$S^{1}_{k}=\\{P^{1}_{ij}(S_{k}):i,j=1,\dots,p\\}\subseteq\mathbb{F}^{k}_{p}.$
It can be noted that $|S^{1}_{k}|=p^{2}.$ To make $P^{1}_{ij}(S_{k_{p}})$ a
$k-$tuple of numbers on $\\{0,1,\cdots,p-1\\},$ we replace $f_{i}$ with its
index $i$.

We now claim that $S^{1}_{k}$ forms an Euler square of index $p,k$, where $i$
and $j$ denote row and column indices respectively. To show that
$S^{1}_{k}=\\{P^{1}_{ij}(S_{k})=(P^{1}_{ij}(f_{2}),\dots,P^{1}_{ij}(f_{k+1})\\}:i,j=1,\dots,p\\}$
forms an Euler Square of index $p,k,$ we need to show that, for
$q,s=1,\dots,k$, $P^{1}_{in}(f_{q})\neq P^{1}_{im}(f_{q})$ and
$P^{1}_{nj}(f_{q})\neq P^{1}_{mj}(f_{q})$ for $n\neq m$ and
$(P^{1}_{ij}(f_{q}),P^{1}_{ij}(f_{s}))\neq(P^{1}_{nm}(f_{q}),P^{1}_{nm}(f_{s}))$
for $i\neq n$ and $j\neq m.$

For $n\neq m,$ $P^{1}_{in}=f_{i}x+f_{n}$ and $P^{1}_{im}=f_{i}x+f_{m}$ do not
have any common root, which shows that $P^{1}_{in}(f_{q})\neq
P^{1}_{im}(f_{q}).$ For $n\neq m,$ $P^{1}_{nj}=f_{n}x+f_{j}$ and
$P^{1}_{mj}=f_{m}x+f_{j}$ have one common root at $f_{1}=0,$ which shows that
$P^{1}_{nj}(f_{q})\neq P^{1}_{mj}(f_{q}),$ as $1\neq q.$ For $i\neq n$ and
$j\neq m,$ $P^{1}_{ij}$ and $P^{1}_{nm}$ can have at most one common root,
which shows that
$(P^{1}_{ij}(f_{q}),P^{1}_{ij}(f_{s}))\neq(P^{1}_{nm}(f_{q}),P^{1}_{nm}(f_{s})).$
Therefore, for prime or prime power $p$ and $k\leq p-1$, one can construct
$\text{ES}(p,k)$ using polynomials of degree at most one. ∎

###  4.2 Example in a prime or prime power case

For constructing the Euler Square of index $3,2$, we consider the field
$F_{3}=\mathbb{Z}_{3}=\\{0,1,2\\}.$ Then, the set
$D^{1}_{3}=\\{P^{1}_{ij}:i,j=0,1,2\\}$ consists of all polynomials of degree
at most one over $\mathbb{Z}_{3}.$ Note that $|D^{1}_{3}|=9.$ Fix
$S_{2}=(1,2)$ as the ordered $2-$tuple. Evaluating every polynomial of
$D^{1}_{3}$ at every point of $S_{2},$ we get the set:
$S^{1}_{2}=\\{(0,0),(1,2),(2,1);(1,1),(2,0),(0,2);(2,2),(0,1),(1,0)\\}\subseteq\mathbb{Z}^{2}_{3}.$
Now it is easy to check that $S^{1}_{2}$ forms an Euler square of index $3,2.$

###  4.3 Euler Square for composite order

Once $\text{ES}(p,k)$ is obtained for $p$ being a prime or prime power, one
can follow the composition rule described in [1] to obtain $\text{ES}(n,k)$
for composite $n=2^{r}p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots,p^{r_{l}}_{l}$ and
$k\leq\min\\{2^{r},p^{r_{1}}_{1},p^{r_{2}}_{2},\ldots,p^{r_{l}}_{l}\\}-1$,
where $p_{1},p_{2},\ldots,p_{l}$ are distinct odd primes.

##  5 Generalized Euler Square

In this section, we propose a generalization of Euler Squares.

######  Definition 5.1.

Generalized Euler Square (GES):
A GES of index $n,k,t$, denoted GES($n,k,t$), with $n>k>t$, is a hyper-
rectangle of $n^{t+1}$ $k-$ads of numbers, $(a_{i_{1}i_{2}\dots
i_{t+1}1},\dots,a_{i_{1}i_{2}\dots i_{t+1}k})$, where $a_{i_{1}i_{2}\dots
i_{t+1}r}\in\\{0,1,\dots,n-1\\};$ $r=1,2,\dots,k;$ $1\leq i_{s}\leq n$ for
$s=1,\cdots,t+1;$ $a_{i_{1}\dots i_{j-1}ui_{j+1}\dots i_{t+1}r}\neq
a_{i_{1}\dots i_{j-1}vi_{j+1}\dots i_{t+1}r}$ for $u\neq v$ and for
$i_{x_{1}}\neq j_{x_{1}},i_{x_{2}}\neq j_{x_{2}};1\leq x_{1}\neq x_{2}\leq
t+1,$ $(a_{i_{1}i_{2}\dots i_{t+1}r_{1}},\dots,a_{i_{1}i_{2}\dots
i_{t+1}r_{t+1}})\neq(a_{j_{1}j_{2}\dots j_{t+1}r_{1}},\dots,a_{j_{1}j_{2}\dots
j_{t+1}r_{t+1}})$, where $1\leq r_{l}\leq k$, $1\leq l\leq k+1$.

######  Remark 5.2.

It is easy to check that an Euler Square of index $n,k$ is a GES of index
$n,k,1.$

In line with Harris F. MacNeish’s construction [1] for Euler Square, we
construct the Generalized Euler Squares for the following cases:

  * 1.

Index $p,p-1,t$, where $p$ is a prime number

  * 2.

Index $p^{r},p^{r}-1,t$, for $p$ prime

  * 3.

Index $n,k,t$, where $n=2^{r}p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots,p^{r_{l}}_{l}$
for distinct odd primes $p_{1},p_{2},\ldots,p_{l}$. Here, $k+1$ equals the
least of the numbers $2^{r},p^{r_{1}}_{1},p^{r_{2}}_{2},\ldots,p^{r_{l}}_{l}.$

In the next section, we use higher degree polynomials over finite field for
constructing GES.

##  6 Construction of Generalized Euler Squares

One of the main objectives of proposing Generalized Euler Square is to obtain
a binary matrix possessing a larger number of columns. However, this comes at
the cost of increased number of intersections between the $k-$tuples.
Therefore, in GES we allow more than one intersections in order to produce
large number of $k-$tuples. The intersection between any two distinct
$k-$tuples is the number of common roots between the two corresponding
polynomials. The use of polynomials of higher degree allows for more
intersections between the $k-$tuples.

###  6.1 Construction of GES of index $p,k,t$ where $p$ is a prime or prime
power

Consider the polynomials of degree at most $t$ over a finite field
$\mathbb{F}_{p}=\\{f_{0}=0,f_{1},\dots,f_{p-1}\\}$ of order $p.$ Form an
ordered $k-$tuple $S_{k}=(f_{1},....,f_{k}).$ Let us denote the set of
polynomials of degree at most $t$ as $D_{t}.$ As there are $p^{t+1}$ number of
polynomials of degree at most $t$, we can write
$D_{t}=\\{P^{t}_{i_{1}i_{2}\dots
i_{t+1}}=\sum^{t+1}_{j=1}f_{i_{j}}x^{j-1}:f_{i_{j}}\in\mathbb{F}_{p},1\leq
i_{j}\leq p\\}.$ Evaluating a polynomial $P^{t}_{i_{1}i_{2}\dots i_{r+1}}$ at
every point of $S_{k},$ we form an ordered $k-$tuple $P^{t}_{i_{1}i_{2}\dots
i_{t+1}}(S_{k})=(P^{t}_{i_{1}i_{2}\dots
i_{t+1}}(f_{1}),\dots,P^{t}_{i_{1}i_{2}\dots
i_{t+1}}(f_{k}))\in\mathbb{F}^{k}_{p}.$ Let
$S^{t}_{k}=\\{P^{t}_{i_{1}i_{2}\dots i_{t+1}}(S_{k}):P^{t}_{i_{1}i_{2}\dots
i_{t+1}}\in D^{p}_{t}\\}\subseteq\mathbb{F}^{k}_{p}.$ Now
$|S^{t}_{k}|=p^{t+1}.$ Similar to the Euler Square case, in order to make
$P^{t}_{i_{1}i_{2}\dots i_{r+1}}({S_{k}})$ a $k-$tuple of numbers on
$\\{0,\cdots,p-1\\},$ we replace $f_{i}$ with its index $i$. It will be shown
next that the $k$-tuples in the set $S^{t}_{k}$ form a GES($n,k,t$).

For $u\neq v,$ $P^{t}_{i_{1}\dots i_{j-1}ui_{j+1}\dots i_{t+1}}$ and
$P^{t}_{i_{1}\dots i_{j-1}vi_{j+1}\dots i_{t+1}}$ can have either no common
root when $j=1$ or $0\in\mathbb{F}_{p}$ as its common root when $1<j\leq t+1$.
This shows that, $P^{t}_{i_{1}\dots i_{j-1}ui_{j+1}\dots i_{t+1}}(S_{k})$ and
$P^{t}_{i_{1}\dots i_{j-1}vi_{j+1}\dots i_{t+1}}(S_{k})$ have no intersection
as $0\notin{S_{k}}$. For $i_{x_{1}}\neq j_{x_{1}},i_{x_{2}}\neq
j_{x_{2}};1\leq x_{1}\neq x_{2}\leq t+1$, $P^{t}_{i_{1}i_{2}\dots i_{t+1}}$
and $P^{t}_{j_{1}j_{2}\dots j_{t+1}}$ have at most $t$ number of common roots.
This proves that $S^{t}_{k}$ forms GES($n,k,t$).

##  7 Construction of GES for composite order

In this section, we construct GES for composite dimensions. We now describe a
procedure to combine two GES to produce a new GES. The resulting GES can have
more general row sizes which are different from prime or prime powers.

Let $p^{\prime}$ and $p^{\prime\prime}$ be two primes or prime powers. Then,
with $1\leq t<k<p^{\prime\prime}\leq p^{\prime},$ we can obtain one GES of
index $p^{\prime},k,t$ and another GES of index $p^{\prime\prime},k,t$ from
the previous construction. Let
$\\{(c^{\prime}_{i_{1},i_{2},\ldots,i_{t+1},1},c^{\prime}_{i_{1},i_{2},\ldots,i_{t+1},2}\ldots,c^{\prime}_{i_{1},i_{2},\ldots,i_{t+1},k})\\}^{p^{\prime}}_{i_{s}=1}$
denote the GES$(p^{\prime},k,t)$ and
$\\{(c^{\prime\prime}_{j_{1},j_{2},\ldots,j_{t+1},1},c^{\prime\prime}_{j_{1},j_{2},\ldots,j_{t+1},2}\ldots,c^{\prime\prime}_{j_{1},j_{2},\ldots,j_{t+1},k})\\}^{p^{\prime\prime}}_{j_{s}=1}$
denote GES$(p^{\prime\prime},k,t).$ Let us define that

$c_{i_{1}+p^{\prime}(j_{1}-1),i_{2}+p^{\prime}(j_{2}-1),\ldots,i_{t+1}+p^{\prime}(j_{t+1}-1),r}=c^{\prime}_{i_{1},i_{2},\ldots,i_{t+1},r}+p^{\prime}(c^{\prime\prime}_{j_{1},j_{2},\ldots,j_{t+1},r}-1).$

Take $m_{s}=i_{s}+p^{\prime}(j_{s}-1).$ It is clear that

  1. 1.

$1\leq m_{s}\leq p^{\prime}p^{\prime\prime}$ as $1\leq i_{s}\leq p^{\prime}$
and $1\leq j_{s}\leq p^{\prime\prime}$

  2. 2.

$0\leq c_{m_{1},m_{2},\ldots,m_{t+1},r}\leq p^{\prime}p^{\prime\prime}-1$ as
$0\leq c^{\prime}_{i_{1},i_{2},\ldots,i_{t+1},r}\leq p^{\prime}-1$ and $0\leq
c^{\prime\prime}_{j_{1},j_{2},\ldots,j_{t+1},r}\leq p^{\prime\prime}-1.$

It is now shown that the $k$-ads consisting of elements
$c_{m_{1},m_{2},\ldots,m_{t+1},r}$ for $r=1,2,\cdots,k$ for
$m_{i}=1,2,\cdots,p^{\prime}p^{\prime\prime}$, $i=1,2,\cdots,t+1$ form
GES$(p^{\prime}p^{\prime\prime},k,t)$.

  1. 1.

$m_{s}^{a}\neq m_{s}^{b}$ implies that $i_{s}^{a}+p^{\prime}(j_{s}^{a}-1)\neq
i_{s}^{b}+p^{\prime}(j_{s}^{b}-1)$. This can happen for $i_{s}^{a}\neq
i_{s}^{b}$ or $j_{s}^{a}\neq j_{s}^{b}$ or both. By definition, for
$i_{s}^{a}\neq i_{s}^{b},$
$c^{\prime}_{i_{1},i_{2},\ldots,i_{s-1},i_{s}^{a},i_{s+1},\ldots,i_{t+1},r}\neq
c^{\prime}_{i_{1},i_{2},\ldots,i_{s-1},i_{s}^{b},i_{s+1},\ldots,i_{t+1},r}$
and for $j_{s}^{a}\neq j_{s}^{b},$
$c^{\prime\prime}_{j_{1},j_{2},\ldots,j_{s-1},j_{s}^{a},j_{s+1},\ldots,j_{t+1},r}\neq
c^{\prime\prime}_{j_{1},j_{2},\ldots,j_{s-1},j_{s}^{b},i_{j+1},\ldots,j_{t+1},r}$.
Also note that
$|c^{\prime}_{i_{1},i_{2},\ldots,i_{s-1},i_{s}^{a},i_{s+1},\ldots,i_{t+1},r}-c^{\prime}_{i_{1},i_{2},\ldots,i_{s-1},i_{s}^{b},i_{s+1},\ldots,i_{t+1},r}|<p^{\prime}$.
Now, if we have $m_{s}^{a}\neq m_{s}^{b},$
$c_{m_{1},m_{2},\ldots,m_{s-1},m_{s}^{a},m_{s+1},\ldots,m_{t+1},r}\neq
c_{m_{1},m_{2},\ldots,m_{s-1},m_{s}^{b},m_{s+1},\ldots,m_{t+1},r}.$

  2. 2.

Suppose that $m_{s}^{a}\neq m_{s}^{b}$ and $m_{\tilde{s}}^{a}\neq
m_{\tilde{s}}^{b}.$ Now $m_{s}^{a}\neq m_{s}^{b}$ can happen for
$i_{s}^{a}\neq i_{s}^{b}$ or $j_{s}^{a}\neq j_{s}^{b}$ or for both whereas
$m_{\tilde{s}}^{a}\neq m_{\tilde{s}}^{b}$ can occur if $i_{\tilde{s}}^{a}\neq
i_{\tilde{s}}^{b}$ or $j_{\tilde{s}}^{a}\neq j_{\tilde{s}}^{b}$ or both. Hence
$m_{s}^{a}\neq m_{s}^{b}$ and $m_{\tilde{s}}^{a}\neq m_{\tilde{s}}^{b}$ can
happen for nine possible pairs of combinations which can be formed by taking
one case from occurrence of $m_{s}^{a}\neq m_{s}^{b}$ and another case from
the occurrence of $m_{\tilde{s}}^{a}\neq m_{\tilde{s}}^{b}.$ For
$i_{s}^{a}\neq i_{s}^{b}$ or $i_{\tilde{s}}^{a}\neq i_{\tilde{s}}^{b}$ or
both,

$\begin{split}&(c^{\prime}_{i_{1}^{a},\ldots,i_{s}^{a}-1,i_{s}^{a},i_{s}^{a}+1,\ldots,i_{\tilde{s}}^{a}-1,i_{\tilde{s}}^{a},i_{\tilde{s}}^{a}+1,\ldots,i_{t+1}^{a},r_{z}})^{t+1}_{z=1}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\neq(c^{\prime}_{i_{1}^{b},\ldots,i_{s}^{b}-1,i_{s}^{b},i_{s}^{b}+1,\ldots,i_{\tilde{s}}^{b}-1,i_{\tilde{s}}^{b},i_{\tilde{s}}^{b}+1,\ldots,i_{t+1}^{b},r_{z}})^{t+1}_{z=1}.\end{split}$

Similarly for $j_{s}^{a}\neq j_{s}^{b}$ or $j_{\tilde{s}}^{a}\neq
j_{\tilde{s}}^{b}$ or both,

$\begin{split}&(c^{\prime\prime}_{j_{1}^{a},\ldots,j_{s}^{a}-1,j_{s}^{a},j_{s}^{a}+1,\ldots,j_{\tilde{s}}^{b}-1,j_{\tilde{s}}^{b},j_{\tilde{s}}^{b}+1,\ldots,j_{t+1}^{a},r_{z}})^{t+1}_{z=1}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\neq(c^{\prime\prime}_{j_{1}^{b},\ldots,j_{s}^{b}-1,j_{s}^{b},j_{s}^{b}+1,\ldots,j_{\tilde{s}}^{b}-1,j_{\tilde{s}}^{b},j_{\tilde{s}}^{b}+1,\ldots,j_{t+1}^{b},r_{z}})^{t+1}_{z=1}.\end{split}$

Hence,

$\begin{split}&(c_{m_{1}^{a},\ldots,m_{s}^{a}-1,m_{s}^{a},m_{s}^{a}+1,\ldots,m_{\tilde{s}}^{a}-1,m_{\tilde{s}}^{a},m_{\tilde{s}}^{a}+1,\ldots,m_{t+1}^{a},r_{z}})^{t+1}_{z=1}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\neq(c_{m_{1}^{b},\ldots,m_{s}^{b}-1,m_{s}^{b},m_{s}^{b}+1,\ldots,m_{\tilde{s}}^{b}-1,m_{\tilde{s}}^{b},m_{\tilde{s}}^{b}+1,\ldots,m_{t+1}^{b},r_{z}})^{t+1}_{z=1}.\end{split}$

###  7.1 GES for general order

A natural extension of the above composition can be stated as follows:

######  Theorem 7.1.

Suppose $n=2^{r}p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots,p^{r_{l}}_{l}$ for distinct
odd primes $p_{1},p_{2},\ldots,p_{l}$ and
$t<k<\min\\{2^{r},p^{r_{1}}_{1},p^{r_{2}}_{2},\ldots,p^{r_{l}}_{l}\\},$ then
GES($n,k,t$) exists.

Similar to the Euler Square case (Lemma 2.6), we have the following result:

######  Lemma 7.2.

Let $t<k^{\prime}<k$. Then the existence of GES($n,k,t$) implies that
GES($n,k^{\prime},t$) exists.

##  8 Construction of binary matrices via GES

In this section, a construction of CS matrices from GES($n,k,t$) is proposed.
Let us represent $n^{t+1}$ number of $k-$tuples as
$\\{(t^{j}_{1},\ldots,t^{j}_{k}):j=1,\ldots,n^{r+1}\\},$ obtained from
GES($n,k,t$). Note that, $0\leq t^{j}_{i}\leq n-1,$ for all
$j=1,\ldots,n^{r+1}$ and $i=1,\dots,k.$ From a $k-$tuple
$(t^{j}_{1},\ldots,t^{j}_{k}),$ we form a binary vector $v^{j}$ of length $nk$
such that

$v^{j}(i)=\begin{cases}1,&\text{if}\,i=(l-1)n+t^{j}_{l}+1,1\leq l\leq k\\\
0,&\text{elsewhere}\end{cases}$

Using $n^{t+1}$ number of $k-$tuples, $n^{t+1}$ binary vectors, each of length
$nk$, are obtained. By taking the binary vectors as columns, we obtain a
binary matrix $\Phi(n,k,t)$ of size $nk\times n^{t+1}.$ We treat $\Phi(n,k,t)$
as the GES matrix of index $n,k,t.$

###  8.1 Properties of GES matrix

  1. 1.

$\Phi(n,k,t)$ has $k$ number of blocks with each block size being $n.$

  2. 2.

Each column of $\Phi(n,k,t)$ has exactly $k$ number of ones and contains a
single $1$ in each block.

  3. 3.

As intersection between any two distinct $k-$tuples of GES($n,k,t$) is at most
$t,$ the non-zero overlap between any two distinct columns of $\Phi(n,k,t)$ is
at most $t.$

######  Lemma 8.1.

The coherence $\mu_{\Phi(n,k,r)}$ of $\Phi(n,k,r)$ is at most equal to
$\frac{r}{k}$.

###### Proof.

Each column of $\Phi(n,k,r)$ has exactly $k$ number of ones, which implies
$\ell_{2}-$norm of each column is $\sqrt{k}.$ Also the non-zero overlap
between any two distinct columns of $\Phi(n,k,r)$ is at most $r.$ So, the
absolute value of the inner product between any two distinct columns is at
most $r.$ Hence the coherence $\mu_{\Phi(n,k,r)}$ of $\Phi(n,k,r)$ is at most
$\frac{r}{k}.$ ∎

######  Remark 8.2.

The maximum possible column size of any binary matrix is $\frac{{m\choose
t+1}}{{k\choose t+1}}$ [19], where $m$ is the row size, $k$ is the number of
ones in each column and $t$ is the maximum overlap between any two columns. If
$m=nk,$ which is the case for $\Phi(n,k,t),$ and $t$ is fixed, then the
maximum possible column size is

$\frac{{nk\choose t+1}}{{k\choose t+1}}=\Theta(n^{t+1}),$ (2)

where $a=\Theta(b)$ implies that, there exist two constants $c_{1},c_{2}$ such
that $c_{1}b\leq a\leq c_{2}b$. Hence the column size of $\Phi(n,k,t)$ is in
the maximum possible order.

From lemma 8.1 and Proposition 2.2, it follows that the matrix $\Phi(n,k,t)$
so constructed satisfies RIP.

######  Theorem 8.3.

The matrix $\Phi_{0}=\frac{1}{\sqrt{k}}\Phi(n,k,t)$ satisfies RIP with
$\delta_{k^{\prime}}=\frac{t(k^{\prime}-1)}{k}$ for any
$k^{\prime}<\frac{k}{t}+1$.

##  9 GES as rectangular array

######  Definition 9.1.

(Rectangular Array:) A rectangular array is a two dimensional array of
$k$-tuples with the following properties:

  * 1.

(GES 1) : each array entry is a $k-$tuple of numbers obtained from
$\\{0,\dots,n-1\\}$,

  * 2.

(GES 2) : two distinct $k-$tuples from the same column do not intersect,

  * 3.

(GES 3) : two distinct $k-$tuples from same row have at most $t-1$
intersections,

  * 4.

(GES 4) : any two distinct $k-$tuples in the array can have at most $t$
intersections.

######  Theorem 9.2.

For $p$ being a prime or prime power, ES($p,p-1$) is a $p\times p$ square
matrix of $(p-1)-$tuple such that

  * 1.

each entry is a $(p-1)-$tuple of numbers obtained from $\\{0,\dots,p-1\\}$,

  * 2.

there is no intersection between any two $(p-1)-$tuples on the same row and
same column,

  * 3.

there is exactly one intersection between any two distinct $(p-1)-$tuples
which are not from the same row or column.

###### Proof.

Consider the finite field $\mathbb{F}_{p}=\\{f_{0}=0,f_{1},\dots,f_{p-1}\\}$
where $p$ is a prime or a prime power. Let $S^{p}$ be the collection of
polynomials of degree at most $1$, with zero being the constant term. It is
easy to check that the cardinality of $S^{p}$ is $|S^{p}|=p.$ For $P\in
S^{p},$ define the set $S^{p}_{P}=\\{P_{j}=P+f_{j}:j=0,\dots,p-1\\}$. Fix any
ordered $(p-1)-$tuple $z\in\mathbb{F}_{p}^{(}p-1)$ with $k=p-1$. For
simplicity, we consider $z=(f_{1},\dots,f_{p-1})$. An ordered $(p-1)-$tuple is
formed after evaluating $P_{j}$ at each of the points of $z$, that is,
$d^{P}_{j}:=\big{(}P_{j}(f_{1}),\cdots,P_{j}(f_{p-1})\big{)}$. In order to
make $d^{P}_{j}$ a $(p-1)-$tuple of numbers on $\\{0,\cdots,p-1\\},$ we
replace $f_{i}$ with its index $i$. Now $d^{P}_{j}$ for $j=0,\dots,p-1$ forms
one column and as $|S^{p}|=p,$ there are $p$ such columns. Therefore we get a
matrix of size $p\times p$ with each entry being $(p-1)-$tuples.

Let us take two $(p-1)-$tuples from same column. As they belong to same column
the corresponding polynomials are of the form $P+f_{i}$ and $P+f_{j}$ for
$i\neq j$ and $P$ being a polynomial of degree at most $1$, with zero being
the constant term. Since $P+f_{i}$ and $P+f_{j}$ does not share any common
root, there is no intersection between the tuples coming from same column.

Let us take two $(p-1)-$tuples from same row. As they belong to same row the
corresponding polynomials are of the form $P_{1}+f_{i}$ and $P_{2}+f_{i}$ for
$P_{1}$ and $P_{2}$ being a polynomial of degree at most $1$ with zero being
the constant term. Since $P_{1}+f_{i}$ and $P_{2}+f_{i}$ share zero as their
only common root, there is no intersection between the tuples coming from same
row as the polynomials are not evaluated at zero while forming the tuples. Let
us take two $(p-1)-$tuples from different row and column. As they belong to
different row and different column the corresponding polynomials are of the
form $P_{1}+f_{i}$ and $P_{2}+f_{j}$ for $i\neq j$ with $P_{1}$ and $P_{2}$
being polynomials of degree at most $1$ and zero being the constant term.
Since $P_{1}+f_{i}$ and $P_{1}+f_{j}$ share exactly one nonzero common root,
there is exactly one intersection between the tuples coming from different row
and different column.

∎

######  Example 9.3.

Let us first take $\mathbb{F}_{3}=\mathbb{Z}_{3}=\\{0,1,2\\}$ and fix the
ordered $5-$tuple $\mathbb{Z}^{2}_{3}=\\{1,2\\}.$ Now the set of polynomials
of degree at most one with constant term zero is $S^{3}=\\{0,x,2x\\}.$ Let us
look at the arrangement of the polynomials in the construction of
GES($3,2,2$).

$\begin{bmatrix}0&x&2x\\\ 1&x+1&2x+1\\\ 2&x+2&2x+2\end{bmatrix}.$

After evaluating the polynomials at $\mathbb{Z}^{2}_{3},$ we get GES($3,2,1$)
as a $3\times 3$ square matrix with entries being $2-$tuples:

$\begin{bmatrix}(0,0)&(1,2)&(2,1)\\\ (1,1)&(2,0)&(0,2)\\\
(2,2)&(0,1)&(1,0)\end{bmatrix}.$

One may observe that GES($3,2,1$) satisfies the properties of theorem 9.2.

######  Remark 9.4.

Note that, the third condition of theorem 9.2 is stronger than (ES 3) given in
Section 3. Later, we use this property while calculating block coherence of
binary matrices coming Euler Square.

###  9.1 GES($p,k,t$) as a rectangular array

Consider a two dimensional matrix where the rows correspond to the $p$
different values of the dimension (corresponding to the degree $t$ in the
polynomials) and the columns correspond to particular values for the other $t$
dimensions ($0,1,2,\cdots,t-1$). The entries of each column are the $k$-tuples
obtained by evaluating the $p$ number of polynomials in the dimension $t$. The
matrix obtained is of size $p\times p^{t}$, with each entry being a $k-$tuple,
and satisfies (GES 1),(GES 2), (GES 3) and(GES 4).

Consider the finite field $\mathbb{F}_{p}=\\{f_{0}=0,f_{1},\dots,f_{p-1}\\}$
where $p$ is a prime or a prime power. Let $S^{p}$ be the collection of
polynomials of degree at most $t$ (where $t<p-1$), with zero being the
constant term. It is easy to check that the cardinality of $S^{p}$ is
$|S^{p}|=p^{t}.$ For $P\in S^{p},$ define the set
$S^{p}_{P}=\\{P_{j}=P+f_{j}:j=0,\dots,p-1\\}$. Fix any ordered $k-$tuple
$z\in\mathbb{F}_{p}^{k}$ with $t<k\leq p-1$. For simplicity, we consider
$z=(f_{1},\dots,f_{k})$. An ordered $k-$tuple is formed after evaluating
$P_{j}$ at each of the points of $z$, that is,
$d^{P}_{j}:=\big{(}P_{j}(f_{1}),\cdots,P_{j}(f_{k})\big{)}$. In order to make
$d^{P}_{j}$ a $k-$tuple of numbers on $\\{0,\cdots,p-1\\},$ we replace $f_{i}$
with its index $i$. Now $d^{P}_{j}$ for $j=0,\dots,p-1$ forms one column and
as $|S^{p}|=p^{t}$ there are $p^{t}$ such columns. Therefore we get a matrix
of size $p\times p^{t}$ with each entry being a $k-$tuple.

Let us take two $k-$tuples from same column. As they belong to same column,
the corresponding polynomials are of the form $P+f_{i}$ and $P+f_{j}$ for
$i\neq j$ and $P$ being a polynomial of degree at most $t$, with zero being
the constant term. Since $P+f_{i}$ and $P+f_{j}$ does not share any common
root, there is no intersection between the tuples coming from same column.

Let us take two $k-$tuples from same row. As they belong to same row the
corresponding polynomials are of the form $P_{1}+f_{i}$ and $P_{2}+f_{i}$ for
$P_{1}$ and $P_{2}$ being a polynomial of degree at most $t$ with zero being
the constant term. Since $P_{1}+f_{i}$ and $P_{2}+f_{i}$ share at most $t-1$
non zero common roots and $0$ as a common root, there is at most $t-1$
intersection between the tuples coming from same row as the polynomials are
not evaluated at zero while forming the tuples.

Let us take two $k-$tuples from different row and column. As they belong to
different row and column the corresponding polynomials are of the form
$P_{1}+f_{i}$ and $P_{2}+f_{j}$ for $i\neq j$ and $P_{1}$ and $P_{2}$ being a
polynomial of degree at most $r$ with zero being the constant term. Since
$P_{1}+f_{i}$ and $P_{1}+f_{j}$ share at most $r$ non zero common root, there
is at most $r$ intersection between the tuples coming from different row and
column.

Example: Let us first take $\mathbb{F}_{5}=\mathbb{Z}_{5}=\\{0,1,2,3,4\\}$ and
fix the ordered $5-$tuple $\mathbb{Z}^{2}_{3}=\\{1,2,3,4\\}.$ Let us look at
the arrangement of the polynomials in the construction of GES($5,4,2$):

$\begin{bmatrix}0&x&2x&\dots&4x^{2}+3x&4x^{2}+4x\\\
1&x+1&2x+1&\dots&4x^{2}+3x+1&4x^{2}+4x+1\\\
2&x+2&2x+2&\dots&4x^{2}+3x+2&4x^{2}+4x+2\\\
3&x+3&2x+3&\dots&4x^{2}+3x+3&4x^{2}+4x+3\\\
4&x+4&2x+4&\dots&4x^{2}+3x+4&4x^{2}+4x+4\\\ \end{bmatrix}.$

Now, evaluating polynomials at $\mathbb{Z}^{2}_{3}=\\{1,2,3,4\\},$ we obtain
GES($5,4,2$):

$\begin{bmatrix}(0,0,0,0)&(1,2,3,4)&(1,4,2,3)&\dots&(2,2,0,1)&(3,4,3,0)\\\
(1,1,1,1)&(2,3,4,0)&(2,0,3,4)&\dots&(3,3,1,2)&(4,0,4,1)\\\
(2,2,2,2)&(3,4,0,1)&(3,1,4,0)&\dots&(4,4,2,3)&(0,1,0,2)\\\
(3,3,3,3)&(4,0,1,2)&(4,2,0,1)&\dots&(0,0,3,4)&(1,2,1,3)\\\
(4,4,4,4)&(0,1,2,3)&(0,3,1,2)&\dots&(1,1,4,0)&(2,3,2,4)\\\ \end{bmatrix}.~{}$

###  9.2 GES($p^{\prime}p^{\prime\prime},k,t$) as rectangular array

As in prime or prime power cases, one can arrange

$\\{(c_{m_{1},m_{2},\ldots,m_{t+1},1},c_{m_{1},m_{2},\ldots,m_{t+1},2}\ldots,c_{m_{1},m_{2},\ldots,m_{t+1},k})\\}^{p^{\prime}p^{\prime\prime}}_{m_{s}=1}$

as a rectangular matrix of size
$p^{\prime}p^{\prime\prime}\times(p^{\prime}p^{\prime\prime})^{t}$ which
satisfies the same properties given before. We provide an equivalent form of
GES($p^{\prime}p^{\prime\prime},k,t$) as a rectangular matrix of size
$p^{\prime}p^{\prime\prime}\times(p^{\prime}p^{\prime\prime})^{t}$ in the
following way:

Following the construction in subsection 9.1, let $d^{P}_{i}$, for
$i=1,\dots,(p^{\prime})^{t}$, form $i^{\text{th}}$ column of
GES($p^{\prime},k,t$) and $d^{Q}_{j}$, for $j=1,\dots,(p^{\prime\prime})^{t}$,
form the $j^{\text{th}}$ column of GES($p^{\prime\prime},k,t$). Now a column
$d^{P,Q}_{i,j}$ is formed by

$d^{P,Q}_{i,j}=d^{P}_{i}+(d^{Q}_{j}-\mathbf{1_{k}})p^{\prime},$

where $\mathbf{1_{k}}$ is a $k-$tuple of all ones. Since $d^{P}_{i}$ has
$p^{\prime}$ number of $k-$tuples and $d^{Q}_{j}$ has $p^{\prime\prime}$
number of $k-$tuples, one gets $p^{\prime}p^{\prime\prime}$ such $k-$tuples in
a column and each entry of $d^{P,Q}_{i,j}$ lies in
$\\{0,1,\dots,p^{\prime}p^{\prime\prime}-1\\}$ as each entry of $d^{P}_{i}$
lies in $\\{0,1,\dots,p^{\prime}-1\\}$ and each entry of $d^{Q}_{j}$ lies in
$\\{0,1,\dots,p^{\prime\prime}-1\\}.$ For every possible combination of $i$
and $j,$ we get $(p^{\prime}p^{\prime\prime})^{t}$ columns. Therefore, we can
obtain a rectangle $D^{P,Q}$ of size
$p^{\prime}p^{\prime\prime}\times(p^{\prime}p^{\prime\prime})^{t}$ with entry
being a $k-$tuple and each entry of the $k-$tuples lies between $0$ and
$p^{\prime}p^{\prime\prime}-1.$ For $1\leq\ell\leq k,$ let us denote the
$\ell^{\text{th}}$ entry of $s^{\text{th}}$ $k-$tuple of $d^{P}_{i},$
$\ell^{\text{th}}$ entry of $n^{\text{th}}$ $k-$tuple of $d^{Q}_{j}$ and
$\ell^{\text{th}}$ entry of $m^{\text{th}}$ $k-$tuple of $d^{P,Q}_{i,j}$ as
$d^{P}_{i}(s,\ell),$ $d^{Q}_{j}(n,\ell)$ and $d^{P,Q}_{i,j}(m,\ell)$,
respectively, where $1\leq s\leq p^{\prime},$ $1\leq n\leq p^{\prime\prime}$
and $1\leq m\leq p^{\prime}p^{\prime\prime}.$ Let $m_{1}\neq m_{2},$ then we
get, $d^{P,Q}_{i,j}(m_{1},\ell)\neq d^{P,Q}_{i,j}(m_{2},\ell).$ It follows
from the fact that $d^{P}_{i}(s_{1},\ell)\neq d^{P}_{i}(s_{2},\ell)$ and
$d^{P}_{j}(n_{1},\ell)\neq d^{Q}_{j}(n_{2},\ell)$ for $s_{1}\neq s_{2}$ and
$n_{1}\neq n_{2}.$ Hence $D^{P,Q}$ satisfies (GES 2). Using properties of
GES$(p^{\prime},k,t)$ and GES$(p^{\prime\prime},k,t)$ and from construction
procedure, it is easy to check that $D^{P,Q}$ satisfies (GES 3) and (GES 4)
too. Hence, $D^{P,Q}$ forms a GES($p^{\prime}p^{\prime\prime},k,t$).

######  Theorem 9.5.

Suppose $n=2^{r}p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots,p^{r_{l}}_{l}$ for distinct
odd primes $p_{1},p_{2},\ldots,p_{l}$ and
$t<k<\min\\{2^{r},p^{r_{1}}_{1},p^{r_{2}}_{2},\ldots,p^{r_{l}}_{l}\\}$. Then
GES($n,k,t$) exists, which can be represented as an $n\times n^{t}$ matrix
with each entry being a $k-$tuple of numbers taken from $\\{1,2,\dots,n\\}$
and has the following properties:

  * 1.

Two distinct $k-$tuples from the same column do not intersect.

  * 2.

Two distinct $k-$tuples from same row have at most $t-1$ intersections.

  * 3.

Any two distinct $k-$tuples in the array can have at most $t$ intersections.

##  10 Recovery guarantees for block sparse signals via GES

In this section, making use of the properties of GES, we show that the binary
matrices constructed from GES are capable of recovering block sparse signals.

###  10.1 Block orthogonality

######  Theorem 10.1.

If GES$(n,k,t)$ exists, then a sparse matrix of size $nk\times n^{t+1}$
exists, which consists of $n^{t}$ orthonormal blocks, each of size $nk\times
n$.

###### Proof.

The binary matrix $\Phi(n,k,t)$ of size $nk\times n^{t+1}$ is obtained from
GES($n,k,t$). Every column of $\Phi(n,k,t)$ corresponds to a unique $k-$tuple
of GES($n,k,t$). We arrange the columns of $\Phi(n,k,t)$ to form a block
orthogonal matrix. We form the $\ell-$th block (of block size $nk\times n$) by
taking $n$ columns of $\Phi(n,k,t)$ corresponding to $n$ $k-$tuples coming
from $\ell-$th column of GES($n,k,t$). From Theorem 9.5, we know that two
$k-$tuples belonging to same column of a GES do not have any intersection. As
a result, the inner product between any two different columns within a block
is zero, implying thereby that each block is orthogonal. Consequently, the
block matrix $\frac{1}{\sqrt{k}}\Phi(n,k,t)$ has $n^{t}$ orthonormal blocks,
where each block is of size $nk\times n.$ ∎

In the case of generalized Euler square, the conditions given in Theorem 2.5
for the successful recovery of block sparse signal of block size $d$ via BOMP
makes sense provided the block coherence of $\frac{1}{\sqrt{k}}\Phi(n,k,t)$ is
strictly less than $\frac{1}{d}.$ In view of this, our next objective is to
choose $n,k$ and $d$ such that the block coherence of
$\frac{1}{\sqrt{k}}\Phi(n,k,t)$ becomes strictly less than $\frac{1}{d}.$ For
simplicity, we first establish the block coherence of Euler square matrices.

###  10.2 Block coherence of Euler Square

######  Theorem 10.2.

Suppose $p$ is a prime or a power of prime, $d\leq p-1$ and $d$ divides $p.$
Then a binary matrix of size $p(p-1)\times p^{2}$ with block coherence
$\frac{1}{p-1}$ exists, which consists of $\frac{p^{2}}{d}$ number of
orthonormal blocks, each of size $p(p-1)\times d$.

###### Proof.

Recall that ES($n,k$) is same as GES($n,k,1$). Hence, from theorem 10.1, we
get the binary matrix $\frac{1}{\sqrt{k}}\Phi(n,k,1)$ consisting of
$\frac{n^{2}}{d}$ number of orthonormal blocks, where each block is of size
$nk\times d.$ Now take, $k=p-1.$ Let $\frac{1}{\sqrt{k}}\Phi(n,k,1)[\ell]$
denote the $\ell^{th}$ block of $\frac{1}{\sqrt{k}}\Phi(n,k,1).$ From the
construction of Euler square described in Theorem 9.2 and the properties of
Euler square, it follows, for $\ell\neq q,$ that

(i)When $\Phi(n,k,1)[\ell]$ and $\Phi(n,k,1)[q]$ correspond to $k-$tuples
coming from different columns but from the same rows of ES($n,k$), we have

$(\frac{1}{\sqrt{k}}\Phi(n,k,1)[\ell])^{T}(\frac{1}{\sqrt{k}}\Phi(n,k,1)[q])=\frac{1}{k}\begin{pmatrix}0&1&1&1&\cdots&1\\\
1&0&1&1&\cdots&1\\\ 1&1&0&1&\cdots&1\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
1&1&1&\cdots&1&0\end{pmatrix}_{d\times d},$

that is, all diagonal entries of $(\Phi(n,k,1)[\ell])^{T}\Phi(n,k,1)[q]$ are
zero and all off-diagonal entries are one. The maximum eigen value of
$(\frac{1}{\sqrt{k}}\Phi(n,k,1)[\ell])^{T}(\frac{1}{\sqrt{k}}\Phi(n,k,1)[q])$
is $\frac{d-1}{k}.$

ii) When $\Phi(n,k,1)[\ell]$ and $\Phi(n,k,1)[q]$ correspond to $k-$tuples
coming from different columns and rows of ES($n,k$), we have

$(\frac{1}{\sqrt{k}}\Phi(n,k,1)[\ell])^{T}(\frac{1}{\sqrt{k}}\Phi(n,k,1)[q])=\frac{1}{k}\begin{pmatrix}1&1&1&1&\cdots&1\\\
1&1&1&1&\cdots&1\\\ 1&1&1&1&\cdots&1\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
1&1&1&\cdots&1&1\end{pmatrix}_{d\times d},$

that is, $(\Phi(n,k,1)[\ell])^{T}\Phi(n,k,1)[q]$ is an all one matrix. The
maximum eigen value of
$(\frac{1}{\sqrt{k}}\Phi(n,k,1)[\ell])^{T}(\frac{1}{\sqrt{k}}\Phi(n,k,1)[q])$
is $\frac{d}{k}.$

(iii) When $\Phi(n,k,1)[\ell]$ and $\Phi(n,k,1)[q]$ correspond to $k-$tuples
coming from the same column of ES($n,k$), we have

$(\frac{1}{\sqrt{k}}\Phi(n,k,1)[\ell])^{T}(\frac{1}{\sqrt{k}}\Phi(n,k,1)[q])=\mathbf{0}.$

Here, $\mathbf{0}$ denotes the zero matrix.

Consequently, the block coherence $\mu_{B_{\frac{1}{\sqrt{k}}\Phi(n,k,1)}}$ is
$\frac{d}{dk}=\frac{1}{k}.$

∎

######  Remark 10.3.

The block coherence of $\frac{1}{\sqrt{p-1}}\Phi(p,p-1,1)$ is at most
$\frac{1}{p-1}$, which can also be obtained from the fact that the coherence
of $\Phi(p,p-1,1)$ is at most $\frac{1}{p-1}.$ The significance of the Theorem
10.2 is that it uses the fact that there is exactly one intersection between
any two distinct $(p-1)-$tuples which are not from the same row or column and
proves that the block coherence of $\frac{1}{\sqrt{p-1}}\Phi(p,p-1,1)$ is
exactly $\frac{1}{p-1}.$

######  Theorem 10.4.

Suppose, GES($n,k,1$) exists, then for $d<k$ and $n$ being a multiple of $d$,
a sparse matrix of size $nk\times n^{2}$ exists which consists of
$\frac{n^{2}}{d}$ orthonormal blocks, each of size $nk\times d.$ Then the
block coherence of $\frac{1}{\sqrt{k}}\Phi(n,k,1)$ is at most $\frac{1}{k}.$

###### Proof.

The proof follows from the Theorem 10.1 and the fact that the coherence of
$\frac{1}{\sqrt{k}}\Phi(n,k,1)$ is at most $\frac{1}{k}$. ∎

Now from Theorem 2.5, the following theorem follows immediately.

######  Theorem 10.5.

A sufficient condition for the BOMP to recover a block $s-$sparse signal
$x_{0}$, with each block length $d$, from
$y=\frac{1}{\sqrt{k}}\Phi(n,k,1)x_{0}$ is

$s<\frac{1}{2}\bigg{(}1+\frac{k}{d}\bigg{)},$

provided $d\leq k.$

###  10.3 Block coherence of GES matrices

Now we derive the expression for block coherence of binary matrices
constructed from GES.

######  Theorem 10.6.

Suppose, GES($n,k,t$) exists, then for $d\leq\lfloor\frac{k}{t}\rfloor$ and
$n$ being a multiple of $d$, a sparse matrix of size $nk\times n^{t+1}$ exists
which consists of $\frac{n^{t+1}}{d}$ orthonormal blocks, each of size
$nk\times d.$ Then the block coherence of $\frac{1}{\sqrt{k}}\Phi(p,p-1,t)$ is
at most $\frac{t}{k}.$

###### Proof.

The proof follows from the Theorem 10.1 and the fact that the coherence of
$\frac{1}{\sqrt{k}}\Phi(n,k,r)$ is at most $\frac{r}{k}$. ∎

Now from Theorem 2.5, the following theorem follows immediately.

######  Theorem 10.7.

A sufficient condition for the BOMP to recover a block $s-$sparse signal
$x_{0}$, with $nk\times d$ as size of each block, from
$y=\frac{1}{\sqrt{k}}\Phi(n,k,r)x_{0}$ is

$s<\frac{1}{2}\bigg{(}1+\frac{k}{dr}\bigg{)},$

provided $d\leq\lfloor\frac{k}{r}\rfloor.$

##  11 Concluding Remarks :

In our present work, we have constructed block orthogonal binary matrices via
Euler Squares with low block coherence which supports recovery of block sparse
signals. We have also introduced and constructed Generalized Euler Squares
(GES) by evaluating higher degree polynomials over a finite field. The binary
matrices constructed from GES have been shown to possess better aspect ratio
compared to their counterparts generated using Euler Squares. Finally, block
orthogonal structure of the GES based binary matrices has been established.

##  12 Acknowledgments

The first author is thankful for the support that he receives from Science and
Engineering Research Board (SERB), Government of India (PDF/2017/002966).

## References

## References

  * [1] Harris F. MacNeish, “Euler Squares,” Ann. Math., vol-23, 221-227, 1922.
  * [2] R. C. Bose, “ On the application of the properties of Galois fields to the problem of construction of Hyper- Graeco-latin squares,” Sankhya, The Indian Journal of Statistics, Vol.3, Part 4, 1938.
  * [3] R. R. Naidu, P. Jampana and C. S. Sastry, “Deterministic Compressed Sensing Matrices: Construction via Euler Squares and Applications,” in IEEE Transactions on Signal Processing, vol. 64, no. 14, pp. 3566-3575, July 15, 2016.
  * [4] P. Indyk, “Explicit constructions for compressed sensing of sparse signals,” in Proc. ACM-SIAM Symp. Discrete Algorithms, pp. 30-33, 2008.
  * [5] S.Li and G. Ge, “Deterministic Construction of Sparse Sensing Matrices via Finite Geometry,” IEEE Transactions on Signal Processing, VOL. 62, NO. 11, JUNE 1, 2014.
  * [6] W. Z. Lu, K. Kpalma and J. Ronisn, “Sparse binary matrices of LDPC codes for compressed sensing,” in Data Compression Conference, Snowbird, Utah, USA, pp. 405-405, 2012.
  * [7] J. Bourgain, S. Dilworth, K. Ford, S. Konyagin and D. Kutzarova, “Explicit constructions of RIP matrices and related problems,” Duke Math. J. 159, 145-185, 2011.
  * [8] E. Candes, “The restricted isometry property and its implications for compressed sensing,” Comptes Rendus Mathematique, Vol. 346, pp. 589-592, 2008.
  * [9] E. Candes, J. Romberg and T. Tao, “Stable signal recovery from incomplete and inaccurate mea- surements,” Comm. Pure and Appl. Math, 59, 1207-1223, 2006.
  * [10] Ronald A. DeVore, “Deterministic constructions of compressed sensing matrices,” Journal of Complexity, Volume 23,pp 918-925, 2007.
  * [11] E. Candes and T. Tao, “Decoding by linear programming,” IEEE Trans. Inform. Theory 51, 42-4215, 2005.
  * [12] R. Baraniuk, M. Davenpor, R. De Vore, and M. Wakin, “A Simple Proof of the Restricted Isometry Property for Random Matrices,” Constructive Approximation, 28(3),253-263, 2008.
  * [13] A. M. Bruckstein, D. L. Donoho and M. Elad, “From sparse solutions of systems of equations to sparse modeling of signals and images,” SIAM Review, Vol. 51, No. 1, pp: 34-81, 2009.
  * [14] B.S. Kashin and V.N. Temlyakov, “A remark on compressed sensing,” Matematicheskie Zametki, Vol. 82, No. 6, pp. 829–837, 2007.
  * [15] J. A. Tropp and S. J. Wright, “Computational methods for sparse solution of linear inverse problems,” Proceedings of the IEEE, vol. 98, no. 6, pp.948–958, 2010.
  * [16] E. Candes and M.B. Wakin, “An introduction to Compressive sampling,” Signal Processing Magazine, pp:21-30, March 2008.
  * [17] B.S. Kashin, “Widths of certain finite-dimensional sets and classes of smooth functions,” Izv. Akad. Nauk SSSR, Ser.Mat. 41 (1977), 334 351; English transl. in Math. USSR IZV. 11, 317-333, 1978.
  * [18] S. Li, F. Gao, G. Ge, and S. Zhang, “Deterministic construction of compressed sensing matrices via algebraic curves,” IEEE Trans. Inf. Theory, vol. 58, 5035-5041, 2012.
  * [19] A. Amini and F. Marvasti, “Deterministic construction of binary, bipolar and ternary compressed sensing matrices,” IEEE Trans. Inf. Theory, vol. 57, 2360-2370, 2011.
  * [20] A. Gilbert and P. Indyk, “Sparse recovery using sparsematrices,” Proc. IEEE, vol. 98, no. 6, pp. 937-947, 2010.
  * [21] B. Adcock, A. Hansen, C. Poon and B. Roman, “Breaking the coherence barrier: A new theory for compressed sensing” arXiv:1302.0561v3, 2013.
  * [22] D. Bryant and P. Cathain, “An asymptotic existence result on compressed sensing matrices” ,arXiv:1403.2807v1, 2014.
  * [23] M. Fickus, D. G. Mixon and J. C. Tremain, “Steiner equiangular tight frames”, Linear Algebra Appl., 436(5):10141027, 2012.
  * [24] A. G. Dimakis, R. Smarandache, and P. O. Vontobel,“LDPC codes for compressed sensing,” IEEE Trans. Inf. Theory, vol. 58, no. 5, pp. 3093-3114, May 2012.
  * [25] Y. C. Eldar, P. Kuppinger and H. Bolcskei, “Block-Sparse Signals: Uncertainty Relations and Efficient Recovery,” in IEEE Transactions on Signal Processing, vol. 58, no. 6, pp. 3042-3054, June 2010.
  * [26] A. Hedayat and E. Seiden, “F-Square and Orthogonal F-Squares Design: A Generalization of Latin Square and Orthogonal Latin Squares Design,” The Annals of Mathematical Statistics Vol. 41, No. 6, pp. 2035-2044, Dec., 1970.
  * [27] X. Shen, Y.Z.Cai, C.L.Liu, and C. P.Kruskal, “Generalized latin squares I ’” Discrete Applied Mathematics, Volume 25, Issues 1–2, Pp. 155-178, October 1989.