Deterministic construction of sparse binary and ternary matrices from existing binary sensing matrices
Name\corref{cor1
Pradip Sasmal\footnote{author for correspondence Telephone: 091-40-23016072
Fax: 091-40-23016032
Pradip Sasmal\footnote{Author for correspondence Telephone: 091-40-23016072
Fax: 091-40-23016032
P. V. Jampana
%In the present work, we discuss a procedure for constructing sparse binary and ternary matrices from existing two binary sensing matrices. The matrices that we construct have several attractive properties such as smaller density, which supports algorithms with low computational complexity. As an application of our method, we show that a CS matrix of general row size different from $p, p^2, pq$ (for different primes $p,q$) can be constructed. %%In Compressed Sensing the matrices that satisfy the Restricted Isometry Property (RIP) play an important role. %% But to date, very few results for designing such matrices are available. Of interest in several applications is a %%binary sensing matrix. The present work constructs the deterministic and binary sensing matrices using the Euler Squares. In particular, given a positive integer $m$ different from $p, p^2$ for a prime $p$, we show that it is possible to construct a binary sensing matrix whose row size is $m$ and the column size is a function of $m^2$. %
manuscriptamc.tex
\documentclass[fleqn,preprint,12pt,3p]{elsarticle}
%\documentclass[fleqn,review,12pt]{elsarticle}
%\documentclass[fleqn,review,3p,a4paper]{elsarticle}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm,subcaption,caption}


%\usepackage[figuresright]{rotating}

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{pseudocode}
\usepackage{multirow}
\usepackage{booktabs}
\usepackage{subfig}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epstopdf}



\usepackage{graphicx}
\usepackage{epsfig}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newdefinition{definition}[theorem]{Definition}
\newdefinition{remark}[theorem]{Remark}
\newdefinition{example}[theorem]{Example}

\newcommand{\NRV}[1]{{\color{red}{\llap{$\spadesuit$\quad NRao \;\;} #1}}}  %% Michal comments
 \newcommand{\BJ}[1]{{\color{blue}{\llap{$\blacklozenge$\quad Balu \;\;} #1}}} %% Balu comments

\begin{document}

\begin{frontmatter}

%% Title, authors and addresses

%% use the tnoteref command within \title for footnotes;
%% use the tnotetext command for the associated footnote;
%% use the fnref command within \author or \address for footnotes;
%% use the fntext command for the associated footnote;
%% use the corref command within \author for corresponding author footnotes;
%% use the cortext command for the associated footnote;
%% use the ead command for the email address,
%% and the form \ead[url] for the home page:
%%
%% \title{Title\tnoteref{label1}}
%% \tnotetext[label1]{}
%% \author{Name\corref{cor1}\fnref{label2}}
%% \ead{email address}
%% \ead[url]{home page}
%% \fntext[label2]{}
%% \cortext[cor1]{}
%% \address{Address\fnref{label3}}
%% \fntext[label3]{}

\title{Deterministic construction of sparse binary and ternary matrices from existing binary sensing matrices}

%% use optional labels to link authors explicitly to addresses:
%% \author[label1,label2]{<author name>}
%% \address[label1]{<address>}
%% \address[label2]{<address>}

%\author{Pradip Sasmal\footnote{author for correspondence Telephone: 091-40-23016072, Fax: 091-40-23016032 } R. Ramu Naidu, and C. S. Sastry \\ Department of Mathematics \\ Indian Institute of Technology, Hyderabad-502205, India \\
%Email: \{ma12p005, ma11p003, csastry\} @ iith.ac.in \\ P. V. Jampana \\ Department of Chemical Engineering\\ Indian Institute of Technology, Hyderabad-502205, India \\
%Email: pjampana@ iith.ac.in}

\author{Pradip Sasmal\footnote{Author for correspondence Telephone: 091-40-23016072, Fax: 091-40-23016032 }, R. Ramu Naidu and C. S. Sastry}
\address{Department of Mathematics \\ Indian Institute of Technology, Hyderabad-502205, India \\
Email: \{ma12p1005, ma11p003, csastry\} @ iith.ac.in}

\author{P. V. Jampana}
\address{Department of Chemical Engineering\\ Indian Institute of Technology, Hyderabad-502205, India \\
Email: pjampana@ iith.ac.in}
\begin{abstract}
In the present work, we discuss a procedure for constructing sparse binary and ternary matrices from existing two binary sensing matrices. The matrices that we construct have several attractive properties such as smaller density, which supports algorithms with low computational complexity. As an application of our method, we show that a CS matrix of general row size different from $p, p^2, pq$ (for different primes $p,q$) can be constructed. 
%In Compressed Sensing the matrices that satisfy the Restricted Isometry Property (RIP) play an important role.
% But  to date, very few results  for designing such matrices are available. Of interest in several applications is a
 %binary sensing matrix. The present work constructs the deterministic and binary sensing matrices using the Euler Squares. In particular, given a positive integer $m$ different from $p, p^2$ for a prime $p$, we show that it is possible to construct a binary sensing matrix  whose row size is $m$ and the column size is a function of $m^2$.
\end{abstract}

\begin{keyword}

Compressed Sensing, RIP, Binary and ternary sensing matrices.
%% keywords here, in the form: keyword \sep keyword

%% MSC codes here, in the form: \MSC code \sep code
%% or \MSC[2008] code \sep code (2000 is the default)

\end{keyword}

\end{frontmatter}

\section{Introduction}

%\par  The flows of data (e.g., signals and images) around us are enormous today and rapidly growing. But the number of important features hidden in huge data are usually much smaller than the number of coefficients in a standard representation of the data. Hence data are compressible. In data processing, the traditional practice is to measure (sense) data in full length and then compress the resulting measurements before storage or transmission. In such a scheme, recovery of data is generally straightforward. This traditional data-acquisition process can be described as full sensing plus compressing". Compressive sensing (CS), also known as compressed sensing or compressive sampling, represents a paradigm shift in which the number of measurements is reduced during acquisition so that no
%additional compression is necessary. The price to pay is that more sophisticated recovery procedures become necessary.
%
%\par In this paper, we will use the term ``signal" to represent generic data (so an image is a signal). Let
%$\bar{\alpha}\in R^{M}$ represent a discrete signal and $y\in R^{m}$ a vector of linear measurements formed by taking inner
%products of $\bar{\alpha}$ with a set of linearly independent vectors $\phi_{i}^{T}\in  R^{M}, i = 1, 2, \dots  ,m.$ In matrix format, the
%measurement vector is $y = \Phi\bar{\alpha}$, where $\Phi \in  R^{m\times M}$ has rows $\phi_{i}^{T}, i = 1, 2,\dots   ,m$. %This process of obtaining $y$ from an unknown signal $\bar{\alpha}$ is often called encoding, while the process of recovering $\bar{\alpha}$ from the measurement vector $y$ is called decoding.
%
%\par When the number of measurements $m$ is equal to $n$, solving a linear system of equations, i.e., $\bar{\alpha} = \Phi^{-1}y$. However, in many applications, it is much more desirable to take fewer measurements provided one can still recover the signal. When $m < M$, the linear system $\Phi \alpha = y$ is typically under-determined, permitting infinitely many solutions. In this case, is it still possible to recover $\bar{\alpha}$ from $y$ through a computationally tractable procedure?
%
%
%\par If we know that the measurement $y$ is from a highly sparse signal (i.e., it has very few nonzero components), then a reasonable decoding model is to look for the sparsest signal among all those that produce the measurement $y$; that is,
%%\begin{displaymath}
%%\begin{enumarate}
%\item
%\begin{equation}
%\lebel{
%P_0:\min_{\alpha} \Vert{\alpha} \Vert_0 \; \mbox{subject to} \quad \Phi \alpha=y.}
%\end{equation}
%%\end{enumarate}
%%\end{displaymath} 
%where the quantity $\Vert{\alpha} \Vert_0 $ denotes the number of non-zeros in $\alpha$. Model (1) is a combinatorial optimization
%problem with a prohibitive complexity if solved by enumeration, and thus does not appear tractable. An alternative model is to replace the ``$\latin{l}_{0}-$norm" by the ``$\latin{l}_{1}-$norm" and solve a computationally tractable linear
%program:
%\item
%\begin{equation}
%\lebel{
%P_1:\min_{\alpha} \Vert{\alpha} \Vert_1 \; \mbox{subject to} \quad \Phi \alpha=y.}
%\end{equation}
%This approach, often called basis pursuit, was popularized by Chen, Donoho and Sauders [9] in signal processing, though similar ideas existed earlier in other areas such as Geo-sciences.
%
%
%
%
%
%\par In most applications, sparsity is hidden in a signal $\bar{\alpha}$ so that it becomes sparse only under a ``sparsifying" basis $\Psi$; that is, $\Psi \bar{\alpha}$ is sparse instead of $\bar{\alpha}$ itself. %In this case, one can do a change of variable z = x and
%%replace the equation Ax = b by (A􀀀1)z = b. For an orthonormal basis , the null space of A􀀀1 is a
%%rotation of that of A, and such a rotation does not alter the success rate of CS recovery (as we will see later
%%that the probability measure for success or failure is rotation-invariant). 
%For simplicity and without loss of generality, we will assume $\Psi=I$ throughout this paper.
%
%
%\par Fortunately, under favorable conditions the combinatorial problem (1) and the linear program (2) can share common solutions. Specifically, if the signal $\bar{\alpha}$ is sufficiently sparse and the measurement matrix $\Phi$ possesses certain nice attributes (to be specified later), then $\bar{\alpha}$ will solve both (1) and (2) for $\Phi \bar{\alpha}=y$. This property is called recoverability. 
%%which, along with the fact that (1.2) can be solved eciently in theory, establishes the theoretical soundness of the decoding model (1.2).
%
%
%\par Generally speaking, compressive sensing refers to the following two-step approach: choosing a measurement matrix $\Phi \in  R^{m\times M}$ with $m < n$ and taking measurement $\Phi \bar{\alpha}=y$ on a sparse signal $\bar{\alpha}$, and then reconstructing $\bar{\alpha}\in R^{M}$ from $y\in R^{m}$ by some means. Since $m < M$, the measurement $y$ is already compressed during sensing, hence the name ``compressive sensing" or CS. Using the basis pursuit model (2) to recover $\bar{\alpha}$ from $y$ represents a fundamental instance of CS, but certainly not the only one. Other recovery techniques include greedy-type algorithms (see [29], for example).
%
%
%
%


Recent developments at the intersection of algebra 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 \cite{bourgain_2011, CS_2013, gil_2010, Chand_2014, Lura_2013}. Sparse representations of a function are a powerful analytic tool in many application areas such as image/signal processing and numerical computation \cite{Bruckstein_2009}, to name a few. The need for the sparse representation arises from the fact that several real life applications demand the representation of data in terms of as few basis (frame) type elements as possible. The elements or the columns of the associated matrix $\Phi$ are called atoms and the matrix so generated by them is called the dictionary. The developments of CS Theory depend typically on sparsity and incoherence \cite{Bruckstein_2009}\cite{Kashin_2007}. Sparsity expresses the idea that the “information rate” of a continuous time data may be much smaller than suggested by its bandwidth or that a discrete-time data depends on a number of degrees of freedom which is comparably much smaller than its (finite) length. On the other hand, incoherence extends the duality between the time and frequency contents of data. 
\par Since the sparsity of the CS matrix is key to minimizing the computational complexity associated with the matrix-vector multiplication, it is desirable that a CS matrix has smaller density. Here, by density, one refers to the ratio of number of nonzero entries to the total number of entries of the matrix. The sparse CS matrix may contribute to fast processing with low computational complexity in Compressed Sensing \cite{gil_2010}.

\par In the recent literature on CS \cite{adcock_2013, bryant_2014, dima_2012, mixon_2012, ind_2008}, deterministic construction of CS matrices has gained momentum.  R. Devore \cite{Ronald_2007} has constructed deterministic binary sensing  matrix of size $p^2 \times p^{r+1}$, where $p$ is prime or prime power. The density of this matrix is $\frac{1}{p}.$ S. Li et. al. \cite{li_2012} have generalized Devore's work, constructing binary sensing matrix of size $|\mathcal{P}|q \times q^{\mathcal{L}(G)}$, where $q$ is any prime power and  $\mathcal{P}$ is the set of all rational points on algebraic curve $\mathcal{X}$ over finite field $\mathbb{F}_q$. The density of this matrix is $\frac{1}{q}$. % P. Indyk \cite{ind_2008} has constructed binary sensing matrices using hash functions and extractor graphs with sizes $r2^{O(\log\log n)^{O(1)}} \times n$, where $r \ll n$.
 A. Amini et. al. \cite{amini_2011} have constructed binary sensing matrices %with sizes $(16^{a}-1) \times \frac{(16^{a}-1)(16^{a}-6)}{5}$ 
using OOC codes. The density of this matrix is $\frac{\lambda}{m}$, where $m$ is row size and $\lambda$ is the number of ones in each column. In all these constructions row sizes of associated matrices are given by some particular family of numbers.

\par CS matrices of general size will not impose any restriction on the data to be dealt with, when used in  applications such as data compression or classification.
The main contribution of the present work may be summarized as follows:
\begin{itemize}
\item Construction of sparse binary and ternary matrices from existing binary matrices.
\item As an application of our construction methodology, we show that, given $m \neq p,p^{2},pq$ (for different primes $p,q$), it is possible to construct sparse binary and ternary matrices of row size $m$.
\end{itemize}
\noindent Consequently, we believe that this work is an attempt towards constructing CS matrices of general size.



%\par In the present work, however, we construct binary and ternary CS matrices of very high sparsity (that is, low density) from existing binary sensing matrices. As an application of proposed method, we show that a CS matrix of general size different from $p, p^2, pq$ (for different primes $p,q$) can be constructed.
\par The paper is organized in several sections. In section 2, we provide basics of CS theory.  While in sections 3 and 4, we discuss in detail the construction of CS matrices of low density and an application of proposed method respectively. In the last two sections, we present respectively the construction of ternary matrices and concluding remarks.







\section{Basics of Compressed Sensing:}


\par The objective of compressed sensing is to recover $x = (x_{1},x_{2}\ldots,x_{M})^{T}\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. 

Denoting $\Phi^{r}_{k}$ as the $k^{\mbox{th}}$ row of $\Phi$, one may rewite the $k^{\mbox{th}}$ component in $y$ as $y_{k}=\left\langle \Phi^{r}_{k} ,x \right\rangle, k=1,2,\dots m$. Here $\left\langle \Phi^{r}_{k},x\right\rangle$ represents the inner-product between $\Phi^{r}_{k}$ and $x$. That is, the object $x$ to be acquired is correlated with the waveform $\Phi^{r}_{k}$. This is a standard setup in several applications \cite{Donoho_2006}\cite{candes_2008}. For example, if the sensing waveforms are Dirac delta functions, then $y$ is a vector of sampled values of $x$ in time or space domain. If the sensing waveforms are indicator functions of pixels, then $y$ is the image data typically collected by sensors in a digital camera. If the sensing waveforms are sinusoids, then $y$ is a vector of Fourier coefficients and this modality is used in the magnetic resonance imaging. Nevertheless, if the sensing waveforms have $0$ and $1$ (or $0$ and $\pm1$) as elements, then the associated  matrix (referred conventionally to as a sensing matrix) can have potential application for multiplier-less dimensionality reduction. An excellent overview of Compressed Sensing and the applicability of several sensing matrices may be seen in \cite{candes_2008}.

Given the pair $(y, \Phi)$, the problem of recovering $x$ can be formulated as finding the sparsest solution (that is, the solution containing most number of zero entries) of linear system of equations $y=\Phi x$. Sparsity is measured by $\| . \|_{0}$ norm and $\|x\|_{0} = |\{j: x_j \neq 0\}|$, the number of non-zero entries in $x$. 
%\footnote{it violates the triangular inequality, that is $\| x_{1} + x_{2} \|_{0} \geq \| x_{1}\|_{0} + \|x_{2} \|_{0} $.}).
 Now finding the sparsest solution  can be formulated as the following minimization problem (generally denoted as $P_{0}$ problem):
%\begin{displaymath}
\begin{equation}
P_0: \min_{x}\|x\|_{0}  \quad \mbox{subject to} \quad \Phi x=y.
%\lebel{}
\end{equation}

%\end{displaymath} 

This $P_{0}$ problem is a combinatorial minimization problem and is known to be NP-hard \cite{bourgain_2011}. One may use greedy methods and convex relaxation of $P_{0}$ problem to recover $k-$sparse signals (that is, $\|x\|_{0}=k$ or signals with $k$ number of nonzero entries). The convex relaxation of $P_{0}$ problem can be posed as $P_{1}$ problem \cite{can_2008, Candes_2005}, which is defined as follows:
\begin{equation}
P_1:\min_{x} \|x\|_{1} \quad \mbox{subject to} \quad \Phi x=y.
%\lebel{}
\end{equation}
\par The Orthogonal Matching Pursuit (OMP) algorithm and and the $l_{1}-$norm minimization (also called basis pursuit) are two widely studied
CS reconstruction algorithms \cite{troop_2010}. 

\par Candes and Tao \cite{Tao_2006} 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
\begin{equation} 
\label{eqn:rip}
(1-\delta_{k}) \left\|x\right\|^{2}_{2} \leq \left\|\Phi x\right\|^{2}_{2} \leq (1+\delta_{k}) \left\|x\right\|^{2}_{2}.
\end{equation} 
%Equivalently, for all vectors $x\in \mathbb{R}^{M}$ with $\left\|x\right\|_{2} = 1$ and $\|x\|_{0}\leq k$, one may rewrite (\ref{eqn:rip}) as
%\begin{displaymath}
%\label{eqn:r}
%(1-\delta_{k})  \leq \left\|\Phi x\right\|^{2}_{2} \leq (1+\delta_{k}) .
%\end{displaymath}
The following theorem \cite{Candes_2005} establishes the equivalence between $P_{0}$ and $P_{1}$ problems: 
\begin{theorem}
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.
\end{theorem}
\par The mutual-coherence $\mu(\Phi)$ of a given matrix $\Phi$ is the largest absolute inner-product between different  normalized columns of $\Phi$, that is, $\mu(\Phi)= \max_{1\leq\; i,j \leq\; M,\; i\neq j} \frac{|\; \Phi_i ^T\Phi_j|}{\Vert \Phi_i\Vert_{2} \Vert \Phi_j \Vert_2}$. Here, $\Phi_k$ stands for the $k$-th column in $\Phi$. 
\noindent The following proposition \cite{bourgain_2011} relates the RIP constant $\delta_{k}$ and $\mu.$
\begin{proposition}
\label{thm:pro}
Suppose that $\Phi_{1},\ldots,\Phi_{M}$ are the unit norm columns of the matrix $\Phi$ with coherence $\mu$. Then $\Phi$ satisfies RIP of order $k$ with constant $\delta_{k} = (k-1)\mu$.
\end{proposition}

\par 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})}$, for some well-behaved order constant \cite{Richard_2008, Ronald_2007, Kashin_1978}. However the only known matrices that satisfy the RIP for this range are based on random constructions \cite{Richard_2008, Candes_2005}. Presently the researchers working in CS theory attempt issues \cite{adcock_2013, apple_2009, mixon_2014} such as 
\begin{enumerate}
\item Maximizing the sparsity of the solution, that is, for a given pair $(y,\Phi )$, finding $x$ such that  $\|x\|_0$  is as small possible
\item	Improving the recovery process, that is, incorporating the prior information (for example, partial support solution) into the recovery process
\item Developing faster algorithms
\item	Designing matrices that satisfy recovery properties
\end{enumerate}
\par The recovery algorithms available to date use matrices $\Phi$  that are generated at random and there is no efficient method for verifying whether or not a given matrix $\Phi$ does indeed have the stronger reconstruction properties. For this and other reasons, it is useful to have an explicit construction of $\Phi$. 












%\noindent Expressing the linear measurements of $x$ in the form of a vector $y$ through the sensing matrix $\Phi$ of size $m \times M (m \ll M)$, one gets a system $y=\Phi x$.  The problem of recovering sparse $x$ from $y$ can be formulated as finding the solution of the following optimization problem:
%\begin{displaymath}
%P_0:\min_{\alpha} \Vert{\alpha} \Vert_0 \; \mbox{subject to} \quad \Phi \alpha=y.
%\end{displaymath} 
%This $P_{0}$ problem is a combinatorial minimization problem and is known to be NP-hard \cite{Donoho_2006}. One may use greedy methods \cite{trop_2007, dai_2009} and convex relaxation of $P_{0}$ problem to recover sparse signals. The convex relaxation of $P_{0}$ problem can be posed as
%\begin{displaymath}
%P_1:\min_{\alpha} \Vert{\alpha} \Vert_1 \; \mbox{subject to} \quad \Phi \alpha=y.
%\end{displaymath}
%\par Candes and Tao \cite{can_2008, Tao_2006, cand_2006} established an equivalent relation between $P_{0}$ and $P_{1}$ problem provided the sensing matrix $\Phi$ satisfies Restricted Isometry Property(RIP).



%Compressed Sensing(CS) aims at recovering high dimensional sparse vectors from considerably fewer linear measurements.
%The problem of sparse recovery through $l_{0}$ norm minimization (that is, minimization of number of
%nonzero components in the solution to be obtained) is not  tractable. Donoho et. al. \cite{cds_2001, Elad_2006},
%Candes et. al. \cite{can_2008, Tao_2006, cand_2006} and A.Cohen et. al \cite{bestk_2009} have made several pioneering
%contributions and have reposed the problem as a simple Linear Programming Problem (LPP). They have
%then established the conditions that ensure the stated equivalence between the original $l_{0}$ problem and its reposed
%version. It is known that RIP is one sufficient condition to ensure the eqivalence. Random matrices such as Gaussian or
%Bernouli as their entries satisfiy RIP with high probability.
%
%\par R.Devore \cite{Ronald_2007} has constructed deterministic RIP matrices with $0'$s and $1'$s as elements (excluding column normalization factors) using
%general univariate polynomials on finite fields.
%In the present work, we extend the ideas developed in
%\cite{Ronald_2007} and construct $0,1-$matrices that satisfy RIP with different row and column sizes using homogeneous multivariable
%polynomials.
%
%\par The paper is organized into several sections. In sections 2 and 3, we present basic CS theory and conditions
%that ensure the equivalence between $l_{0}-$norm problem and its LPP version problems. Motivated by the deterministic
%construction methodology proposed in \cite{Ronald_2007}, we present in section 4 our extension, which is based on
%homogeneous two variable polynomials over finite fields. In section 5, we extend the ideas to deal with circulant
%matrices. While in section 6, we state the results for $n-$variable homogeneous polynomials. In the last section, we
%present our concluding remarks.
%
%\section{Sparse recovery from linear measurements}


%As stated already CS refers to the problem of reconstruction of an unknown vector $u \in \mathbb{R}^{m}$ from the
%linear measurements $y = (\langle{u,\phi_{1}\rangle},\ldots,\langle{u,\phi_{n}\rangle})
%\in \mathbb{R}^{n}$ with $\langle{u,\phi_{j}}\rangle$ being the inner product between $u$ and $\phi_{j}$. The basic objective
%in CS is to design a recovery procedure based on the sparsity assumption on $u$ when the number of measurements $n$ is
%much small compared to $m$. Sparse representations seem to have merit for various applications in areas such as
%image/signal processing and numerical computation. \par A vector $u \in \mathbb{R}^{m}$ is $k-$spare if it has atmost $k$
%nonzero coordinates. The problem of obtaining the sparse vector from its linear measurements may be posed as
%\begin{align}
%P_0:\min_{v} \Vert{v} \Vert_0 \; \mbox{subject to} \quad \Phi v=y.
%\end{align}
%Here $\Vert{v} \Vert_0 = \left|\left\{i \mid v_{i}\neq 0\right\} \right|.$
%\par D.Donoho and others \cite{cds_2001}\cite{Elad_2006} have tried to understand the conditions under which
%the solution to $P_{0}$ is the same as the solution to the following LPP :-
%\begin{align}
%P_1:\min_{v} \Vert{v} \Vert_1 \; \mbox{subject to} \quad \Phi v=y.
%\end{align}
%Here $\Vert{v} \Vert_1$ denotes the $l_{1}$-norm of the vector $v \in \mathbb{R}^{m}$. Denote the solution to $P_{1}$ by $f_{\Phi}(y)$ and solution to $P_{0}$ by $u^{0}_{\Phi}(y) \in \mathbb{R}^{m}$.
%\section{On the equivalence between $P_{0}$ and $P_{1}$ problems}
%\begin{definition}
%The mutual-coherence $\mu(\Phi)$ of a given matrix $\Phi$ is the largest absolute normalized inner product between different columns of $A$. Denoting the $k$-th column in $A$ by $a_k$, the\textbf{mutual-coherence} is given by
%\begin{align}
%\mu(\Phi)= \max_{1\leq\; i,j \leq\; m,\; i\neq j} \frac{|\; \phi_i ^T\phi_j|}{\Vert \phi_i\Vert_{2} \Vert \phi_j \Vert_2}.
%\end{align}
%\end{definition}
%\noindent It is known \cite{Elad_2006} that for $\mu$-coherent matrices $\Phi$, one has
%\begin{align}
%\label{eqn:eqlnt of solns}
%u^{0}_{\Phi}(y)= f_{\Phi}(y) = u,
%\end{align}
%provided $u$ is $k-$sparse with $k < \frac{1}{2}\; (1+\frac{1}{\mu}).$ D.Donoho \cite{Donoho_2006} has given sufficient conditions on the matrix $\Phi$ for \eqref{eqn:eqlnt of solns} to hold.
%In recent time the flow of data across the world are enormous and exponentially growing. Data can be huge but the underline important features can be few. Compressed sensing is proving new techniques to capture salient features of a signal using few samples. Let $x$ be an unknown $m-$dimensional vector. Now if $x$ has at least $k-$number of non zero entries we will say that $x$ is $k-$sparse. The main moto of compressed sensing is to find out few linear measurements along with stable and efficient reconstruction process which makes use of sparsity. Expressing each measurement vector as row of an $n \times m(n<<m)$ matrix $\Phi$, we will get a system $y=\Phi x +z$ to noisy cases. Now given a measurement vector $y,$ how can reconstruct the original signal $x$ from $y=\Phi x$. The problem can be formulated as finding the sparsest solution of linear equations $y=\Phi x$.
%\begin{align}
%P_0:\min_{x} \Vert{x} \Vert_0 \; \mbox{subject to} \quad \Phi x=y.
%\end{align} 
%This $P_{0}$ problem is a combitorial minimization problem and known to be NP-hard.
%\par We can use greedy methods and convex relaxation of $P_{0}$ problem to recover $k-$sparse signals. The convex relaxation of $P_{0}$ problem can be posed as
%\begin{align}
%P_0:\min_{x} \Vert{x} \Vert_1 \; \mbox{subject to} \quad \Phi x=y.
%\end{align}
%%\par Candes and Tao \cite{can_2008, Tao_2006, cand_2006} established an equivalent relation between $P_{0}$ and $P_{1}$ problem provided the sensing matrix $\Phi$ satisfies Restricted Isometry Property(RIP).



%\section{Equivalence between $P_{0}$ and $P_{1}$ problem:}
%
%
%
%\par Basic theory of CS presently consists of two components: recoverability and stability. Recoverability addresses the central questions: what types of measurement matrices and recovery procedures ensure exact recovery of all $k-$sparse signals (those having
%exactly $k-$nonzeros) and how many measurements are sufficient to guarantee such a recovery? Existing results in CS recoverability and stability are mostly based on analyzing properties of the measurement matrix $\Phi$. The most widely used analytic tool is the so-called Restricted Isometry Property (RIP) of $\Phi$ Candes and Tao \cite{Tao_2006} 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}$ if for all $k-$sparse vectors $x\in \mathbb{R}^{m}$, we have
%\begin{displaymath}
%\label{eqn:ri}
%(1-\delta_{k}) \left\|x\right\|^{2}_{2} \leq \left\|\Phi x\right\|^{2}_{2} \leq (1+\delta_{k}) \left\|x\right\|^{2}_{2}.
%\end{displaymath}
%The following theorem guarantees the equivalence between $P_0$ and $P_1$ problems \cite{can_2008}.
%\begin{theorem}
%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 unique solution.
%\end{theorem}
%The mutual-coherence $\mu(\Phi)$ of a given matrix $\Phi$ is the largest absolute normalized inner product between different columns of $\Phi$, that is, $\mu(\Phi)= \max_{1\leq\; i,j \leq\; M,\; i\neq j} \frac{|\; \Phi_i ^T\phi_j|}{\Vert \Phi_i\Vert_{2} \Vert \Phi_j \Vert_2}$. Here, $\Phi_k$ stands for the $k$-th column in $\Phi$. 
%\noindent The following proposition \cite{bourgain_2011} relates the RIP constant $\delta_{k}$ and $\mu.$
%\begin{proposition}
%\label{thm:pro}
%Suppose that $\Phi_{1},\ldots,\Phi_{M}$ are the unit norm columns of the matrix $\Phi$ and have coherence $\mu$. Then $\Phi$ satisfies RIP of order $k$ with constant $\delta_{k} = (k-1)\mu$.
%\end{proposition}
%\begin{definition}
%The density of a matrix is the ratio of the number of its nonzero entries to the total number of its entries.
%\end{definition}
%\noindent Therefore, for a matrix of high sparsity, density is very small.
%%\noindent Candes and Tao \cite{Candes_2005} have shown that whenever $\Phi$ satisfies RIP of order $3k$ with $\delta_{3k} < 1,$ the CS reconstruction error satisfies the following estimate
%%\begin{align}
%%\label{eqn:rip}
%%\left\|u-f_{\Phi}(\Phi u)\right\|_{l^{m}_{2}} \leq C k^{\frac{-1}{2}} \sigma_{k}(u)_{l^{m}_{1}},
%%\end{align}
%%where $\sigma_k(u)_{l^m_1}$ denotes the $l_{1}$ error of the best $k-$term approximation, and the constant $C$ depends only on $\delta_{3k}$. This means that the bigger the value of $k$ for which we can verify the RIP then the better guarantee we have on the performance of $\Phi$.
%\par One of the important problems in CS theory deals with constructing CS matrices that asymptotically satisfy the RIP for the largest possible range of $k$. 
%It is known that the widest range possible is $k$ is of order $\frac{m}{\log(\frac{M}{m})}$ \cite{Richard_2008} \cite{Ronald_2007} \cite{Garnaev_1984} \cite{Kashin_1978}. However the only known matrices that satisfy the RIP for this range are based on random constructions. %\cite{Richard_2008}.
%R. Baraniuk et. al.  \cite{Richard_2008} have verified the RIP for random matrices with high probability.
%% using the following concentration of measure inequality:
%%\begin{align}
%%\label{eqn:cmi}
%%\Pr(\left| \left\|\Phi(\omega)u\right\|_{l_{2}}^{2} - \left\| u\right\|_{l_{2}}^{2}\right| \geq \epsilon\left\| u\right\|_{l_{2}}^{2}) \leq 2e^{-nc_{0}(\epsilon)}, \; 0< \epsilon <1.
%%\end{align}
%%Where the probability is taken over all $n\times m$ matrices $\Phi(\omega)$, and $c_{0}(\epsilon)$ is a constant dependent only on $\epsilon$ such that for all $\epsilon \in (0,1)$, $c_{0}(\epsilon) > 0$.\\
%There are, however, no deterministic constructions for $k$ of the order $\frac{m}{\log(\frac{M}{m})}$. To the best of our knowledge, designing the good deterministic constructions of RIP matrices is an important and open problem.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%










\section{ Construction Procedure:}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par In this section, we present our deterministic construction procedure taking two existing binary sensing matrices as inputs. We show that the resulting matrix has smaller density than the original two. Let $\Psi_{m \times M}$ be a binary sensing block matrix having $k''$ row blocks (the meaning of row blocks is explained later with example), each of size $n$ such that every block contains single $1$ and the overlap between any two columns is atmost $r$, that is $|\{l|\Psi_{l,p}=1\} \bigcap \{t|\Psi_{t,q}=1 \}|\leq r$ for any two columns $\Psi_{p}$ and $\Psi_{q}$. Let $\Psi'_{m' \times M'}$ be another binary sensing block matrix having $k'$ row blocks, each of size $n'$ such that each block contains single $1$ and the overlap between any two columns is atmost $r'$. Assume that $n' \leq n$ , $ k \leq \min \{ k' , k'' \}$ and $r \leq r' \leq k\leq n$. 
%Define the vector $V$, indexed on $i-1$(mod $n$), for $1 \leq i \leq nk=m$. There are $k$-blocks in $V$ and each block contains the numbers $0,1,\ldots,n-1$.
 Now a new matrix can be constructed by the following steps:

{\bf Step-1:} Let the $i^{th}$ column of $\Psi$ be  $\Psi_{i}$. For $1 \leq i \leq M$, define $S_{i} =  (((\text{supp}(\Psi_{i})-1)(\mod \;n))^{T}+ \mathbf{1} ^{T})$, where $\mathbf{1} ^{T}$ is the vector consisting of all ones of size $k'' \times 1$, supp$(\Psi_{i})$ is the support vector of $\Psi_{i}$. Since $\Psi$ has $k''$ blocks and each block contains one $1$, it follows that $|S_{i}| = k''$ where $S_{i}$ is a $k''-$ tuple on the set $X=\{1,2,\ldots,n\}$. Since $\Psi$ has $M$ columns, we have $M$ such $k''-$tuples. For example, suppose $m=9$ and $\Psi$ has 3 blocks, then each block is of size 3. Now, if the $i^{th}$ column $\Psi_{i}$ is $(1\; 0\; 0\; 0\; 1\; 0\; 0\; 0\; 1)^{T}$, supp$(\Psi_{i})$ is $[1\;5\;9]$, then the triplet, $S_{i}$, corresponding to this column  is $[1\;2\;3]$. Similarly from the matrix $\Psi'$, we can generate $M'$ number of $k'-$tuples on the set $Y = \{1,2,\ldots,n'\}.$  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\bf Step-2:} From $k''-$tuples of first matrix $\Psi$ we remove last $(k'' - k)$ entries from each tuple to make it a $k-$tuple.  Now add $(-1)$ to each of the entries of the $M$ number of $k-$tuples that are obtained from $\Psi$. Let the $k-$tuples be of the form $(c_{i1}, c_{i2}, \ldots,c_{ik})$ for $1 \leq i \leq M$. From $k'-$tuples of second matrix $\Psi'$, we remove last $(k' - k)$ entries from each tuple to make it $k-$tuple. By this process, we get $M'$ number of $k-$tuples from the second matrix $\Psi'$. Let each $k-$tuple have the form $(c'_{j1}, c'_{j2}, \ldots,c'_{jk})$ for $1 \leq j \leq M'$.

{\bf Step-3:} Now replace each $k-$tuple $(c_{i1}, c_{i2}, \ldots,c_{ik})$ with $M'$ number of $k-$tuples (obtained from $\Psi'$) by adding $n' (c_{i1}, c_{i2}, \ldots,c_{ik})$  to each of the $k-$tuples $(c'_{j1}, c'_{j2}, \ldots,c'_{jk})$ for $1 \leq j \leq M'$. This way, we get $MM'$ number of $k-$ tuples on the set $X'=\{1,2,\ldots,nn'\}$. Denote these $k-$tuples by $F$. Let $(a_{j1}, a_{j2}, \ldots,a_{jk})$ for $j= 1,2,....,MM'$ be the $k-$ tuples in $F$.

 
{\bf Step-4:} From these $k-$ tuples we form a binary vector of length $knn'$ where $1$ occurs in the positions $(l-1).nn'+a_{jl}$ for $l= 1,2,\dots,k$ and rest of the positions are zeros. Using these $MM'$ number of $k-$tuples, we form binary sensing matrix $\Phi$ having $k$ number of blocks and each block is of size $nn'$ and every block contains single $1$. The position of one's in each block is indexed by the $k-$ tuples. So the size of the matrix $\Phi$ becomes $nn'k \times MM'$.
The pseudo code of the proposed method is as follows: \\
%----------------------------------------------
\begin{center}
\begin{tabular}{|l l|}
\hline \\
1. & {\bf Input:}  Two matrices $\Psi$, $\Psi'$ of sizes $nk'' \times M$, $n'k' \times M'$ \\
2. & Suppose $|\text{supp}(\Psi_i) \cap \text{supp}(\Psi_j)| \leq r $ and \\
   & $ |\text{supp}(\Psi'_i) \cap \text{supp}(\Psi'_j)| \leq r'$, $\forall \ i \neq j$  \\
3. & Assume  $n' > n, k \leq \min \{k',k''\}$ and $r \leq r' \leq k \leq n$ \\
4. & Set $S_{i} =  (((\text{supp}(\Psi_{i})-1)(\mod \;n))^{T}+ \mathbf{1} ^{T})$, $|S_i| = k'', \; \forall \; i=1,2,\ldots,M$  \\
5. & Similarly, $S'_j$ with $|S'_j| = k'$ are defined for $j=1,2,\ldots,M'$ \\
6. & Set $S''_{i,j} = S'_{j,k} - \mathbf{1}+n' S_{i,k}$, $S'_{j,k}$ and $S_{i,k}$ are first $k$ entries of $S'_j$ and $S_{i}$ \\
7. & $|S''_{i,j}| = k$ and Let $S''_{i,j} = (S''_{i,j,1}, S''_{i,j,2}, \dots, S''_{i,j,k}) $ \\
   &  $1 \leq S''_{i,j,l} \leq nn', \forall l=1,2,...,k$ \\
8. & From each $S''_{i,j}$, create a vector $v_{i,j}$ of length $nn'k$ \\ 
   &  and $v_{i,j}=1$ at $(l-1).nn'+ S''_{i,j,l}$ for $l= 1,2,\dots,k$ and zero elsewheres\\  
9. & {\bf Output:} $\Phi'$, a matrix of size $nn'k \times MM'$, whose columns are $v_{i,j}.$ \\ \\
\hline
\end{tabular}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%This methodology is summarized in Fig.1
\begin{lemma}\label{lem:1}
The coherence of the enlarged matrix $\Phi$ of size $nn'k \times MM'$, $\mu(\Phi)$, is atmost $\frac{r'}{k}$.
\end{lemma}

\begin{proof}
Let $\Phi_{i}, \Phi_{j}$ be two arbitrary columns of matrix $\Phi$. There exist two $k-$ tuples $f_i ,f_j \in F$ such that $\Phi_{i}, \Phi_{j}$ are the corresponding vectors of $k-$ tuples $f_i ,f_j$ as defined in the above construction . Suppose $f_{i}= (c'_{k'1}, c'_{k'2}, \ldots,c'_{k'k})+n'(c_{k1}, c_{k2}, \ldots,c_{kk})$ and $f_{j}= (d'_{k'1}, d'_{k'2}, \ldots,d'_{k'k})+n'(d_{k1}, d_{k2}, \ldots,d_{kk})$, where $(c'_{k'1}, c'_{k'2}, \ldots,c'_{k'k}), (d'_{k'1}, d'_{k'2}, \ldots,d'_{k'k})$ are two $k-$tuples obtained from $\Psi'$ and $(c_{k1}, c_{k2}, \ldots,c_{kk}), (d_{k1}, d_{k2}, \ldots,d_{kk})$ are $k-$tuples obtained from $\Psi$.
Set $g_{ij} = f_{i}-f_{j}= (c'_{k'1}, c'_{k'2}, \ldots,c'_{k'k})-(d'_{k'1}, d'_{k'2}, \ldots,d'_{k'k}) + n'\biggl((c_{k1}, c_{k2}, \ldots,c_{kk})-(d_{k1}, d_{k2}, \ldots,d_{kk})\biggl).$ We will show that $g_{ij}$ has atmost $r'$ number of zero elements, which implies that intersection between the supports of $\Phi_{i}, \Phi_{j}$ is atmost $r'$. Now $|c'_{k^{'}i}-d'_{k^{'}i}|<n'$ and $|c_{ki}-d_{ki}|<n$. The $l^{th}$ element of $g_{ij}$ is $(g_{ij})_{l}= (c'_{k'l}-d'_{k'l})+ n'(c_{kl}-d_{kl}).$ We investigate the cases wherein $(g_{ij})_{l} =0.$\\
\textbf{Case 1:} Suppose $c'_{k'l} \neq d'_{k'l}$. \\
\textbf{Sub case 1.1:} If $c_{kl} = d_{kl}$, then $(g_{ij})_{l} \neq 0.$\\
\textbf{Sub case 1.2:} If $c_{kl} \neq d_{kl}$, then also $(g_{ij})_{l} \neq 0.$ Since $1 \leq |c_{kl}-d_{kl}|<n$ and $|c'_{k^{'}l}-d'_{k^{'}l}|<n'$, we have $(g_{ij})_{l} = (c'_{k^{'}l}-d'_{k^{'}l})+ n'(c_{kl}-d_{kl}) \neq 0$.\\
\textbf{Case 2:} Suppose $c'_{k'l} = d'_{k'l}$ then $(g_{ij})_{l} =0$ only when $c_{kl} = d_{kl}$.
\par From the above cases, we conclude that $(g_{ij})_{l} =0$ only when $c'_{k'l} = d'_{k'l}$ and $c_{kl} = d_{kl}$, but as  both matrices $\Psi$ and $\Psi'$ can have atmost $r'$ intersections, $(g_{ij})_{l} =0$ can occur for atmost $r'-$choices of $j$. So $\Phi_{i}, \Phi_{j}$ have atmost $r'-$intersections. So the coherence $\mu(\Phi)$ of $\Phi$ is atmost $\frac{r'}{k}$. 


% Now our claim is $f_{i}$ and $f_j$ can have atmost $r$ intersections. Since $(i_{k'1}, i_{k'2}, \ldots,i_{k'k})$ and $(j_{k'1}, j_{k'2}, \ldots,j_{k'k})$ are $k-$tuples corresponding to $\Psi'$, overlap of any two columns of $\Psi'$ is atmost $r$ implies that these two $k-$tuples have atmost $r$ intersections. With out loss of generality assume that $i_{k'i} = j_{k'i}$ for $i=1,2,\ldots,r.$ Now we have to analyze elements of $f_{i}$ and $f_j$ block-wise. Consider the $i^{th}$ block and let $g= (i_{k'i} + n' i_{ki})- (j_{k'i} + n' j_{ki}) = (i_{k'i} - j_{k'i})+ n' (i_{ki} -  j_{ki})$. If we show $g=0$ then intersection is occurring at $i^{th}$ block. Suppose assume that $i_{k'i} \neq j_{k'i}$, that is $(i_{k'i} - j_{k'i}) \neq 0$. Since $i_{k'i}, j_{k'i} \in Y$ and $i_{ki}, j_{ki} \in X$, we have $|i_{k'i} - j_{k'i}| < n'$ and either $i_{ki} = j_{ki}$ or $i_{ki} \neq j_{ki}$. If $i_{ki} = j_{ki}$, then $g \neq 0$. If $i_{ki} \neq j_{ki}$, then $|i_{ki} - j_{ki}| \geq 1$, which implies that $n'(i_{ki} - j_{ki}) \geq n'$. There fore we have $|i_{k'i} - j_{k'i}| < n'$ and $n'(i_{ki} - j_{ki}) \geq n'$, which implies that $g \neq 0.$ So, if in the $i^{th}$ block elements are different corresponds to matrix $\Psi'$ then intersection can not occur in that block position. Now suppose $i_{k'i} = j_{k'i}$, then $g=0$ only when $i_{ki} =  j_{ki}$. So, it shows that intersection can occur in the $i^{th}$ block only when elements in $i^{th}$ block are same. So as we assumed that $i_{k'i} = j_{k'i}$ for $i=1,2,\ldots,r.$ So there can have only $r-$intersections. Which implies that overlap between any two columns is $r$. Since the number of ones in each column of $\Phi$ is $k$, we have coherence of $\Phi$ is atmost $\frac{r}{k}$.  
\end{proof} 
\noindent The following theorem shows the RIP compliance of $\Phi$. 
\begin{theorem}
\label{thm:r}
The afore-constructed matrix $\Phi_{nn'k \times MM'}$ satisfies RIP with $\delta_{k'} = (k'-1)({\frac{r'}{k}})$ for any $k' < \frac{k}{r'} + 1.$    
\end{theorem}
\begin{proof}
Proof follows from the Proposition \ref{thm:pro} and Lemma \ref{lem:1}. 
\end{proof}
%\begin{theorem}
%Suppose $m$ is any positive integer different from $p, p^2, pq$ for distinct primes $p,q$. Then there exists a CS matrix of row sizes $m$.
 
%If $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$ such that $r_{i}\geq 2$ for $1 \leq i \leq l$, $r_{i} > 2$ for $i=1$ then there exist a matrix of row size $m$.
%\end{theorem} 
%\begin{proof}
%Without loss of generality assume that $2^{r} \leq p^{r_{1}}_{1} \leq p^{r_{2}}_{2} \leq \ldots \leq p^{r_{l}}_{l}$.\\
%\textbf{Case 1:} If $m = p^{i}, i>2$ then $m$ can be written as $m = p^{i-3}p^{2}p$. Take matrix $\Psi$ having $p'(>p)-$blocks and each block of size $p^{i-3}$. Take another matrix $\Psi'$ having $p''(>p)-$blocks and each block of size $p^{2}$ (existence of such kind of matrices in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices then we will generate matrix $\Phi$ of row size $p^{i}$.\\ 
%\textbf{Case 2:} Suppose $m=p^{r_{1}}_{1}p^{r_{2}}_{2}$ such that both $r_{1}, r_{2} \neq 1$ and $p^{r_{1}}_{1}>p^{r_{2}}_{2}$. Take matrix $\Psi$ having $p_{1}-$blocks and each block of size $p_{1}^{r_{1}-1}$. Take another matrix $\Psi'$ having $p_{1}-$blocks and each block of size $p_{2}^{r_{2}}$ (existence of such kind of matrices in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices then we will generate matrix $\Phi$ of row size $m$.\\ 
%\textbf{Case 3:} Suppose $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{s}}_{s}$ such that $ s\geq3, p^{r_{1}}_{1}>p^{r_{2}}_{2}> \ldots >p^{r_{s}}_{s}$. We will show that there exist a CS matrix of row size $m$ by induction on $s$. For $s=3$, $m=p^{r_{1}}_{1}p^{r_{2}}_{2}p^{r_{3}}_{3}$. Take matrix $\Psi$ having $p^{r_{3}}_{3}-$blocks and each block of size $p_{1}^{r_{1}}$. Take another matrix $\Psi'$ having $p^{r_{3}}_{3}-$blocks and each block of size $p_{2}^{r_{2}}$ (existence of such kind of matrices in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices then we will generate matrix $\Phi$ of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}p^{r_{3}}_{3}$. Assume that for $3<l<k$ there exist a matrix of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$. Now we have to show that there exist a CS matrix of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{k-2}}_{k-2}p^{r_{k-1}}_{k-1}p^{r_{k}}_{k}$. Take matrix $\Psi$ having $p^{r_{k}}_{k}-$blocks and each block of size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{k-2}}_{k-2}$. Take another matrix $\Psi'$ having $p^{r_{k}}_{k}-$blocks and each block of size $p_{k-1}^{r_{k-1}}$(existence of such kind of matrices in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices then we will generate matrix $\Phi$ of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{k-2}}_{k-2}p^{r_{k-1}}_{k-1}p^{r_{k}}_{k}$. By induction we have proved that there exist a CS matrix of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{s}}_{s}$ such that $ s\geq3, p^{r_{1}}_{1}>p^{r_{2}}_{2}> \ldots >p^{r_{s}}_{s}$. 


%Let $m$ be any integer such that $m \neq p^{i}$ for $i>2$. From the fundamental theorem of arithmetic $m$ is factorized as $m = 2^{r}p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$.  Let $k'= \min\{2^{r},p^{r_{1}}_{1},p^{r_{2}}_{2},\ldots ,p^{r_{l}}_{l}\}$ and $k = k'-1$. With out loss of generality assume that $k' = 2^r$ (The following arguments hold true even if  $k' = p^{r_{s}}_{s}$ for some $s \in \{1,2,\ldots, l\}$). From the construction of MacNeish \cite{euler_1922}, it is known that the Euler Square of index $m, k$ exists. Let $m_{1} = p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$, without loss of generality, consider that $p^{r_1}_{1}=\min\{p^{r_{1}}_{1},p^{r_{2}}_{2},\ldots ,p^{r_{l}}_{l}\}$. Since $2^{r} \leq (p^{r_1}_{1}-1)$, the Euler Square of index $m_{1}, (p^{r_1}_{1}-1)$ exists, which in view of lemma-\ref{lem:e} implies that the  Euler Square of index $m_{1}, 2^{r}$ exists. The binary CS matrix constructed through this Euler Square has a row size of $m_{1}2^{r}$, which is $m$. 
%\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent \textbf{Remark-1:} The density of the matrix $\Phi$ is $\frac{1}{nn'}$, which is smaller than the densities of the matrices $\Psi$ and $\Psi'$, which are $\frac{1}{n}$ and $\frac{1}{n'}$ respectively. Hence using our construction procedure we can construct more sparse binary matrices from existing binary sensing matrices.\\
\noindent \textbf{Remark-2:} The positions of $1'$s in the matrix $\Phi$ are known and we know that every block contains single one. So we can permute the columns of the matrix $\Phi$ so that the support of the permuted matrix has nice structured sparsity.  
\subsection{Example:} In this section, we demonstrate our proposed method of construction via an example.
\noindent Let $\Psi_{4 \times 4}$ be a binary sensing block matrix 


%$\vspace{10pt}$$\begin{pmatrix}
%1 & 0 & 1 & 0 \\
%0 & 1 & 0 & 1 \\
%\hline
%1 & 0 & 0 & 1 \\
%0 & 1 & 1 & 0 \
%
%\end{pmatrix}$



\[ \left( \begin{array}{cccc}                       
     1 & 0 & 1 & 0 \\
     0 & 1 & 0 & 1 \\
		\hline
     1 & 0 & 0 & 1 \\
     0 & 1 & 1 & 0 \end{array} \right)\] 
having $2$ row blocks, each of atmost size $2$ such that every block contains one $1$ and the overlap between any two columns is $1$. Let $\Psi'_{9 \times 9}$ be a binary sensing block matrix 
\[ \left( \begin{array}{ccccccccc}

     1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\
     0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\
     0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\
		\hline
     1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\
     0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1  \\
     0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0  \\
		\hline
     1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1  \\
     0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0  \\
     0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} \right)\]
having $3$ row blocks, each of atmost size $3$ such that every block contains one $1$ and the overlap between any two columns is $1$.

{\bf Step-1:} The corresponding four $2-$tuples obtained from $\Psi$ constitute $S$ as
 
$S=\Bigg\{ \begin{pmatrix}
1\\
1
\end{pmatrix},\begin{pmatrix}
2\\
2
\end{pmatrix},\begin{pmatrix}
1\\
2
\end{pmatrix},\begin{pmatrix}
2\\
1
\end{pmatrix} \Bigg\}$ $\mathbf{.}$






%
%\[ \left( \begin{array}{cccc}
      %
			%2 & 1 & 2 & 1 \\
			%2 & 1 & 1 & 2 \end{array} \right)\]
			
 The corresponding nine $3-$tuples obtained from $\Psi'$ constitute $S'$ as

$S'=\Bigg\{\begin{pmatrix}
1\\
1\\
1\end{pmatrix},
\begin{pmatrix}
2\\
2\\
2\end{pmatrix},\begin{pmatrix}
3\\
3\\
3\end{pmatrix},\begin{pmatrix}
1\\
2\\
3\end{pmatrix},\begin{pmatrix}
2\\
3\\
1\end{pmatrix},\begin{pmatrix}
3\\
1\\
2\end{pmatrix},\begin{pmatrix}
1\\
3\\
2\end{pmatrix},\begin{pmatrix}
2\\
1\\
3\end{pmatrix},\begin{pmatrix}
3\\
2\\
1\end{pmatrix}\Bigg\}$ $\mathbf{.}$


	
	
	
	
	%
	%\[ \left( \begin{array}{ccccccccc}
%
      %2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 \\
			%2 & 3 & 1 & 3 & 1 & 2 & 1 & 2 & 3 \\
			%2 & 3 & 1 & 1 & 1 & 3 & 3 & 1 & 2	\end{array} \right)\]

{\bf Step-2:} Now removing the last entries from each $3-$tuple of $S'$, we get $S''$ that contains nine $2-$tuples as
	
	
	
$S''=\Bigg\{\begin{pmatrix}
1\\
1\end{pmatrix},\begin{pmatrix}
2\\
2\end{pmatrix},\begin{pmatrix}
3\\
3\end{pmatrix},\begin{pmatrix}
1\\
2\end{pmatrix},\begin{pmatrix}
2\\
3\end{pmatrix},\begin{pmatrix}
3\\
1\end{pmatrix},\begin{pmatrix}
1\\
3\end{pmatrix},\begin{pmatrix}
2\\
1\end{pmatrix},\begin{pmatrix}
3\\
2\end{pmatrix}\Bigg\}$ $\mathbf{.}$
	
	
	
	
	
	
	%\[ \left( \begin{array}{ccccccccc}
%
      %2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 \\
			%2 & 3 & 1 & 3 & 1 & 2 & 1 & 2 & 3  \end{array} \right)\]

{\bf Step-3:} Let us add $(\mathbf{-1})$ to each of the entries of $S$ and then multiply each of the tuples by $3$. Now to each $2-$tuple add all $2-$tuples of $S''$ and generate $S'''$ with $|S'''|=36$. Now all the entrices of $S'''$ are less than or equal to $6$. All the tuples of $S'''$ are as follows:




\tiny{$\Bigg\{\begin{pmatrix}
1\\
1\end{pmatrix}$, $\begin{pmatrix}
4\\
4\end{pmatrix}$, $\begin{pmatrix}
1\\
4\end{pmatrix}$, $\begin{pmatrix}
4\\
1\end{pmatrix}$, $\begin{pmatrix}
2\\
2\end{pmatrix}$, $\begin{pmatrix}
5\\
5\end{pmatrix}$, $\begin{pmatrix}
2\\
5\end{pmatrix}$, $\begin{pmatrix}
5\\
2\end{pmatrix}$, $\begin{pmatrix}
3\\
3\end{pmatrix}$, $\begin{pmatrix}
6\\
6\end{pmatrix}$, $\begin{pmatrix}
3\\
6\end{pmatrix}$, $\begin{pmatrix}
6\\
3\end{pmatrix}$, $\begin{pmatrix}
1\\
2\end{pmatrix}$, $\begin{pmatrix}
4\\
5\end{pmatrix}$, $\begin{pmatrix}
1\\
5\end{pmatrix}$, $\begin{pmatrix}
4\\
2\end{pmatrix}$, $\begin{pmatrix}
2\\
3\end{pmatrix}$, $\begin{pmatrix}
5\\
6\end{pmatrix}$, $\begin{pmatrix}
2\\
6\end{pmatrix}$, $\begin{pmatrix}
5\\
3\end{pmatrix}$, $\begin{pmatrix}
3\\
1\end{pmatrix}$, $\begin{pmatrix}
6\\
4\end{pmatrix}$, $\begin{pmatrix}
3\\
4\end{pmatrix}$, $\begin{pmatrix}
6\\
1\end{pmatrix}$, $\begin{pmatrix}
1\\
3\end{pmatrix}$, $\begin{pmatrix}
4\\
6\end{pmatrix}$, $\begin{pmatrix}
1\\
6\end{pmatrix}$, $\begin{pmatrix}
4\\
3\end{pmatrix}$, $\begin{pmatrix}
2\\
1\end{pmatrix}$, $\begin{pmatrix}
5\\
4\end{pmatrix}$, $\begin{pmatrix}
2\\
4\end{pmatrix}$, $\begin{pmatrix}
5\\
1\end{pmatrix}$, $\begin{pmatrix}
3\\
2\end{pmatrix}$, $\begin{pmatrix}
6\\
5\end{pmatrix}$, $\begin{pmatrix}
3\\
5\end{pmatrix}$, $\begin{pmatrix}
6\\
2\end{pmatrix}\Bigg\}$} $\mathbf{.}$




  
 
%\tiny{
 %\[ \left( \begin{array}{*{36}c}
%%\begin{pmatrix} 
%5 & 6 & 4 & 5 & 6 & 4 & 5 & 6 & 4 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 5 & 6 & 4 & 5 & 6 & 4 & 5 & 6 & 4 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 \\
%5 & 6 & 4 & 6 & 4 & 5 & 4 & 5 & 6 & 2 & 3 & 1 & 3 & 1 & 2 & 1 & 2 & 3 & 2 & 3 & 1 & 3 & 1 & 2 & 1 & 2 & 3 & 5 & 6 & 4 & 6 & 4 & 5 & 4 & 5 & 6 
%%\end{pmatrix}
%\end{array} \right)\]}
\normalsize
 			
{\bf Step-4:} From each $2-$tuple of $S'''$, we form a column consisting of two blocks of size $6$ where the positions of $1's$ in each block are dictated by the two entries of the tuple. Finally, from all these steps, we obtain the following matrix 
$\Phi_{12 \times 36} :$ 		

\tiny{\[ \left( \begin{array}{*{36}c}
1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0\\
0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0\\
0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&0\\
0&1&0&1&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0\\
0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0\\
0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&1\\
\hline
1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0\\
0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&1\\
0&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&0\\
0&1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&0&0&0&0&0&0&1&1&0&0&0&0&0\\
0&0&0&0&0&1&1&0&0&0&0&0&0&1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&0\\
0&0&0&0&0&0&0&0&0&1&1&0&0&0&0&0&0&1&1&0&0&0&0&0&0&1&1&0&0&0&0&0&0&0&0&0\\
\end{array} \right)\]}











%\[ \left( \begin{array}{cccccccccccccccccccccccccccccccccccc}

%\[ \left( \begin{array}{*{36}c}
% \begin{pmatrix} 
%\begin{gather*}
%\setlength{arraycolsep}{.75\arraycolsep}
%\text{\footnotesize $ \displaystyle
%\begin{pmatrix}
%\tiny{
%\[ \left( \begin{array}{*{36}c}
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1 \\
	 %
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0 \\
	%
	 %0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%\hline
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0 \\
	%
	 %1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0 \\
	%
	 %0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1 
	%\end{array} \right)\]}
	\normalsize
	%$}
%\end{pmatrix}
	%\end{equation*}
%	\end{gather*}


			
      

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{sideways}
%\thispagestyle{empty}%
%\makebox[\textheight][c]{\begin{minipage}{\paperheight}
%\setlength\arraycolsep{4pt}
%\begin{align*}
         %&\left[ {\begin{array}{ccccccccccc}
         	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1 \\
	 %
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0 \\
	%
	 %0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0 \\
	%
	 %1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0 \\
	%
	 %0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1 
         %\end{array} } \right]
         %%\cdot\left[ {\begin{array}{c}
         %%E(\widetilde{A}_{kk}^{cn}|L_k^c)\\
         %%E(\widetilde{A}_{k k+1}^{cn}|L_{k+1})\\
         %%E(\widetilde{A}_{k k+1}^{cn}|L_{k+1}^c)\\
         %%E(\widetilde{A}_{k k+2}^{cn}|L_{k+2})\\
         %%E(\widetilde{A}_{k k+2}^{cn}|L_{k+2}^c)\\
         %%\vdots \\
         %%E(\widetilde{A}_{k c-1}^{cn}|L_{c-1})\\
         %%E(\widetilde{A}_{k c-1}^{cn}|L_{c-1}^c)\\
         %%E(\widetilde{A}_{kc}^{cn}|L_{c})\\
         %%\end{array} } \right]\\=
         %%&\left[ {\begin{array}{c}
         %%E(R_k|L_k^c) + P(N_k^s|L_k^c)   E\left(\widetilde{B}_{kk}^{c+n}|L_k^c\right) \\
         %%E(R_{k+1}|L_{k+1}) + P(N_{k+1}^s|L_{k+1})  E\left(\widetilde{B}_{kk+1}^{c+n}|L_{k+1}^c      \right)\\
         %%E(R_{k+1}|L_{k+1}^c) +P(N_{k+1}^s|L_{k+1}^c)   E\left(\widetilde{B}_{kk+1}^{c+n}|L_{k+1}^c      \right)\\
         %%E(R_{k+2}|L_{k+2}) + P(N_{k+2}^s|L_{k+2})  E\left(\widetilde{B}_{kk+2}^{c+n}|L_{k+2}^c      \right)\\
         %%E(R_{k+2}|L_{k+2}^c) +P(N_{k+2}^s|L_{k+2}^c)   E\left(\widetilde{B}_{kk+2}^{c+n}|L_{k+2}^c      \right)\\
         %%\vdots \\
         %%E(R_{k+2}|L_{c-1}) + P(N_{c-1}^s|L_{c-1})  E\left(\widetilde{B}_{kc-1}^{c+n}|L_{c-1}^c      \right)\\
         %%E(R_{k+2}|L_{c-1}^c) +P(N_{c-1}^s|L_{c-1}^c)   E\left(\widetilde{B}_{kc-1}^{c+n}|L_{c-1}^c      \right)\\
         %%E(\widetilde{A}_{kc}^{cn}|L_{c})\\
         %%\end{array}} \right]
%\end{align*}
%\end{minipage}}
%\end{sideways}
%
%
%\begin{sideways}
%\thispagestyle{empty}%
%\makebox[\textheight][c]{\begin{minipage}{\paperheight}
%\setlength\arraycolsep{4pt}
%\begin{align*}
         %&\[ \left( \begin{array}{*{36}c}
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1 \\
	 %
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0 \\
	%
	 %0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0 \\
	%
	 %1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0 \\
	%
	 %0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1 
	%\end{array} \right)\]
%\end{align*}
%\end{minipage}}
%\end{sideways}
















\subsection{Example}
Let $p_{1}, _{2}$ be two distinct primes and choose a positive integer $r$, such that $r<p_{2}<p_{1}$. Using the method in \cite{Ronald_2007}, one obtains binary matrices $\Psi, \Psi'$ of sizes $p^{2}_{2} \times p^{r+1}_{2}$ and $p^{2}_{1} \times p^{r+1}_{1}$ respectively. Thus we get $p^{r+1}_{1}$ number of $p_{1}-$tuples and $p^{r+1}_{2}$ number of $p_{2}-$tuples. If we apply our construction procedure on these matrices then we generate matrix $\Phi$ of size $p_{1}p^{2}_{2} \times (p_{1}p_{2})^{r+1}$ with coherence $\frac{r}{p_{2}}$. The density of this matrix $\Phi$ is $\frac{1}{p_{1}p_{2}}$, which is small compared to $\frac{1}{p_{1}}$ and $\frac{1}{p_{2}}$, the densities of $\Psi$ and $\Psi'$ respectively.
\par In the construction of $\Phi$, the row size is $p_{1}p^{2}_{2}$ and each column contains $p_{2}$ number of ones, and the overlap between any two columns is $r$, therefore the maximum possible column size for this construction \cite{amini_2011} is $\frac{{p_{1}p^{2}_{2}\choose r+1}}{{p_{2} \choose r+1}}$, which is of the order $(p_{1}p_{2})^{r+1}$, that is, $\frac{{p_{1}p^{2}_{2}\choose r+1}}{{p_{2} \choose r+1}} = O((p_{1}p_{2})^{r+1})$. Consequently, our enlarged matrix attains the maximum possible column size asymptotically. 
 
%\textbf{Remark-2:} In our previous work \cite{ram_2013}, using Euler Squares, we have constructed binary sensing matrices of any row size $m$ except for $ p, p^2$ (for prime $p$) with asymptotically optimal column size such that overlap between any two columns is $1$. In the present work, however, we construct sparse binary sensing matrices of any row size $m$ except for $p, p^2, pq$ for distinct primes $p,q$ such that overlap between any two columns is $r' \geq 1$ and these matrices too possess optimal possible column size asymptotically. Because of $r'>1$, the matrix so constructed here has better column-to-row 
%ratio than the one in \cite{ram_2013}. This has greater relevance to applications like dimensionality reduction \cite{Elad_2010}.  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{An application of proposed construction procedure:}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ As stated already, the present work helps us to construct deterministic CS matrices of lower density. In addition, we show that this methodology could be adopted to constructing CS matrices of general row sizes.

%We can construct binary matrices of row size different from $p, p^2, pq$ (for distinct primes $p,q$), by our construction procedure with the help of existing binary matrices.

\begin{theorem}
Suppose $m$ is any positive integer different from $p, p^2, pq$ for distinct primes $p,q$. Then there exists a binary CS matrix of row size $m$.
 
%If $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$ such that $r_{i}\geq 2$ for $1 \leq i \leq l$, $r_{i} > 2$ for $i=1$ then there exist a matrix of row size $m$.
\end{theorem} 
\begin{proof}
%Without loss of generality assume that $2^{r} \leq p^{r_{1}}_{1} \leq p^{r_{2}}_{2} \leq \ldots \leq p^{r_{l}}_{l}$.\\
\textbf{Case 1:} 
If $m = p^{i}, i>2$, then $m$ can be written as $m = p^{i-2}p\cdot p$  (let take $p=k\leq n'=p\leq p^{i-2}=n$). Suppose $\Psi$ is a matrix having $p'(>p)-$blocks where each block is of size $p^{i-2}$ with intersection between any two different columns is $r$. Let $\Psi'$ be a CS matrix having $p$ blocks where each block is of size $p$  with intersection between any two different columns is $r'$(It is guaranteed in \cite{Ronald_2007} that such matrices exist and in above Example 3.2). By applying our construction procedure on these two matrices, we generate matrix $\Phi$ of row size $p^{i}$.\\ %(if we work with the matrices constructed in \cite{Ronald_2007} and $r''=\max\{r,r'\}$, then the coherence of the resulting matrix $\Phi$ constructed by this choice of construction is $\frac{r''}{p}$ and column size is $p^{r(i-2)+r'+2}$)\\ 
\textbf{Case 2:} Suppose $m=p^{r_{1}}_{1}p^{r_{2}}_{2}$ such that both $r_{1} \neq 1 \neq r_{2}$ and $p^{r_{1}}_{1}>p^{r_{2}}_{2}$. Take a CS matrix $\Psi$ having $p_{1}-$ blocks with each block being of size $p_{1}^{r_{1}-1}$. Let $\Psi'$ be another CS matrix having $p_{1}-$blocks where each block is of size $p_{2}^{r_{2}}$ (existence of such matrices is guaranteed in \cite{Ronald_2007}). By applying our construction procedure on these two matrices, we generate matrix $\Phi$ of row size $m$.\\ 
\textbf{Case 3:} Suppose $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\cdots p^{r_{s}}_{s}$ such that $ s\geq3$ and $ p^{r_{1}}_{1}>p^{r_{2}}_{2}> \cdots >p^{r_{s}}_{s}$. By induction on $s$, we show that there exists a CS matrix of row size $m$. For $s=3$, set $m_3=p^{r_{1}}_{1}p^{r_{2}}_{2}p^{r_{3}}_{3}$. Suppose the CS matrix $\Psi$ has $p^{r_{3}}_{3}-$blocks where each block is of size $p_{1}^{r_{1}}$. Let $\Psi'$ be another CS matrix having $p^{r_{3}}_{3}-$blocks such that each block is of size $p_{2}^{r_{2}}$ (existence of such matrices is guaranteed in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices, then we generate matrix $\Phi$ of row size $p^{r_{1}}_{1}p^{r_{2}}_{2}p^{r_{3}}_{3}$, which is $m_3$. Assume that for $3<l<k$, there exists a matrix of row size $m_l=p^{r_{1}}_{1}p^{r_{2}}_{2}\cdots p^{r_{l}}_{l}$. Now we have to show that there exists a CS matrix of row size $m_k=p^{r_{1}}_{1}p^{r_{2}}_{2}\cdots p^{r_{k-2}}_{k-2}p^{r_{k-1}}_{k-1}p^{r_{k}}_{k}$. Take a CS matrix $\Psi$ having $p^{r_{k}}_{k}-$blocks such that each block is of size $m_{k-2}=p^{r_{1}}_{1}p^{r_{2}}_{2}\cdots p^{r_{k-2}}_{k-2}$. Suppose $\Psi'$ has $p^{r_{k}}_{k}-$blocks such that each block is of size $p_{k-1}^{r_{k-1}}$. By applying our construction procedure on these two matrices, we generate matrix $\Phi$ whose row size is $p^{r_{1}}_{1}p^{r_{2}}_{2}\cdots p^{r_{k-2}}_{k-2}p^{r_{k-1}}_{k-1}p^{r_{k}}_{k}$, which is $m$. By induction we conclude that there exists a CS matrix of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\cdots p^{r_{s}}_{s}.$
\end{proof}

\noindent \textbf{Remark-3:} In the process of obtaining a binary matrix of row size $m$ if we use matrices $\Psi_{1},\ldots,\Psi_{t}$ with column sizes $M_{1},\ldots,M_{t}$ respectively and with coherence $\mu_{1},\ldots, \mu_{t}$ respectively, then the resulting matrix $\Phi$ is of size $m \times (M_{1}\cdots M_{t})$ and the coherence $\mu_{\Phi}$ of $\Phi$ is $\text{max}{\{\mu_{1},\ldots, \mu_{t}\}}.$







\noindent \textbf{Remark-4:}
The authors of \cite{amni_2012} obtained general row size via Kronecker Delta product. If we apply Kronecker Delta product on $\Psi_{m \times M}$ and $\Psi'_{m' \times M'}$, the existing matrices that we started with, one obtains $\Psi''$, which is of the size $mm' \times MM'$. The method proposed herein, on the other-hand, results in $\Phi$ of size $nn'k \times MM'$. Although both the matrices have same coherence and same density, as $nn'k<mm'$, $\Phi$ has better aspect ratio or redundancy factor (column to row ratio) compared to $\Psi'$.\


\noindent \textbf{Remark-5:}
 As coherence of the resulting matrix depends on the choice of the two matrices, we can choose the two matrices in such a way that the resultant matrix has low coherence. In the above proof, we have used as an example the matrices constructed in \cite{Ronald_2007}. Nevertheless, one may use other suitable binary matrices like those constructed in \cite{li_2012}. \


\section{Construction of ternary matrices}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Let $\Phi_{m\times M}$ be a matrix having $k$ number of blocks where each block is of size $n$, containing single one's and intersection between any two different columns of $\Phi$ is atmost $r$. Let the $i^{th}$ column of $\Phi$ be  $\Phi_{i}$. For $1 \leq i \leq M$, define $f_{i} =  (((\text{supp}(\Phi_{i})-1)(\mod n))^{\bf{T}}+\bf{1}^{T})$, 
where $\bf{1}^{T}$ is the vector consisting of all ones of size $ k \times 1$, supp$(\Phi_{i})$ is the support vector of $\Phi_{i}$. Since $\Phi$ has $k$ blocks and each block contains one $1$, it follows that $|f_{i}| = k$ where $f_{i}$ is a $k-$ tuple on the set $X=\{1,2,\ldots,n\}$. Since $\Phi$ has $M$ columns, we have $M$ such $k-$tuples. Let $f_{i}=(f_{i_1}, f_{i_2}, \ldots,f_{i_k})$ be the $k-$ tuples. Now decompose this $k-$tuple into $k-$number of two tuples as $(l,f_{i_{l}})$, where $l$ denotes the $l^{th}$ block position and $f_{i_{l}}$ denotes the $l^{th}$ entry of $f_{i}$. It is to be noted here that $1 \leq l \leq k, 1 \leq f_{i_{l}} \leq n$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Construction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 From the $k-$ tuple $f_{i}=(f_{i_1}, f_{i_2}, \ldots,f_{i_k}),$ we form a binary vector of length $n \times k$ where $1$ occurrs in the positions $(l-1).n+f_{i_l}$ for $l= 1,2,....,k$ and rest of the positions are zeros (the vector is nothing but $\Phi_{i}$ )  and then we replace $1$ with $(-1)$ if $l>f_{i_{l}}$, which results in a vector consisting of $0,1,-1$ as entries. As we have $M$ such $k-$tuples, we get $M$ number of ternary vectors of length $n \times k$. This way, we get a ternary matrix $\Phi'_{m\times M}$ of size same as that of $\Phi_{m\times M}$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par Let $(0\; 1\; 0\; 0\; 0\; 1\; 1\; 0\; 0)^{T}$ be a column from a matrix having $3$ blocks and each block is of size $3$. Then the support of this column is the $3-$ tuple $(2\; 3\; 1)$. Break this $3$- tuple into three $2$- tuples $(1\;2), (2\;3), (3\;1)$ as we mentioned above.  Now in the 3rd block as $1$ occurs in the 1st position, we replace $1$ with $-1$ in the 3rd block of the binary vector  $(0\; 1\; 0\; 0\; 0\; 1\; 1\; 0\; 0)^{T}$ to generate the ternary vector $(0\; 1\; 0\; 0\; 0\; 1\; (-1)\; 0\; 0)^{T}$.  

\noindent \textbf{Remark-6:} The coherence and density of the ternary matrix $\Phi'$ remain same as that of the binary matrix $\Phi$. \\
\par As in the case of binary CS matrices, it is possible to construct ternary matrices of general row size as well, which is concluded as the following theorem:
\begin{theorem}
Suppose $m$ is any positive integer different from $p, p^2, pq$ for distinct primes $p,q$. Then there exists a ternary CS matrix of row size $m$. 
\end{theorem}
\begin{proof} 
Initially we construct a binary matrix of row size $m$, which is discussed in Section 4.  Then we use methodology in section 5.1  to obtain a ternary matrix of row size $m$.
\end{proof}
\subsection{A different approach to constructing ternary matrix:}
In this section, we present another deterministic construction procedure of ternary matrix by combining binary and Hadamard matrices . We show that the resulting matrix has same density and coherence as binary but with better aspect ratio (column to row ratio). Let $\Psi_{m \times M}$ be a binary sensing  matrix having $k$ number of one's in each column and overlap between any two columns is $r$. Suppose there exists a Hadamard matrix $H$ of size $(k+r')$ for some $r' \in { \{0,\dots, r\}}$. For each column of $\Psi$, we replace each of its $1$-valued entries with a distinct row of $H$ to obtain a ternary CS matrix $\Phi$ of size $m \times M(k+r')$. As the rows of Hadamard matrix $H$ are orthogonal, the rows of $\Phi$ are orthogonal. From the construction methodology, it is easy to check that the coherence of the matrix $\Phi$ is $\frac{r}{k}$. The density of the matrix $\Phi$ is $\frac{k}{m}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section {Simulation Results}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%With a view to comparing the performances of sparse recovery by the matrices constructed here in and the standard sparse
%Gaussian random matrices, we have generated binary matricx $\Phi$ for the sizes $ 45 \times 225$, $63 \times 441$, $99 \times 11979$ and $117 \times 59319$. We have used OMP to recover $x$ from $(y, \Phi)$, where $y= \Phi x$, for diffrent levels of sparsity. Let $\tilde x$ denote the recovered solution. From the reconstruction, we have computed the Signal-to-noise ratio (SNR) using
%\begin{displaymath}
%SNR(x) = 10 . \log_{10} \biggl( \frac{\|x \|_2}{\|x - \tilde x \|_2} \biggl) dB.
%\end{displaymath}
%For recovery at each sparsity level, we have considered 1000 input signals $x$. We have considered the recovery to be good if $SNR(x) \geq 100dB$. Simulation results on these matrices indicate (shown in Figure \ref{fig:comp_matrix}) that 
%the binary matrix constructed here in gives better performance than the sparse Gaussian matrix for 
%certain higher sparsity levels. While for other sparsity levels, both matrices give the same recovery performance.
%\begin{figure*}
%
%\centering
%\begin{subfigure}{0.45\textwidth}
%\centering
%\includegraphics[width=8cm]{45_by_225.eps}
%\caption{}
%\end{subfigure}
%\begin{subfigure}{0.45\textwidth}
%\centering
%\includegraphics[width=8cm]{63_by_441.eps}
%\caption{}
%\end{subfigure}
%\begin{subfigure}{0.45\textwidth}
%\centering
%\includegraphics[width=8cm]{99_by_11979.eps}
%\caption{}
%\end{subfigure}
%\begin{subfigure}{0.45\textwidth}
%\centering
%\includegraphics[width=8cm]{117_by_59319.eps}
%\caption{}
%\end{subfigure}
%
%\caption{Comparison of the reconstruction performances of binary matrix (continuous line)  and the Gausian matrix (dashed line) when the matrices are of size (a) $ 45 \times 225$, (b) $63 \times 441$, (c) $99 \times 11979$ and (d) $117 \times 59319$. These plots indicate that the binary matrix shows superior performance for some sparsity levels, while for other levels both matrices result in the same performance. The $x$ and $y$ axes in both plots refer respectively to the sparsity level and the success rate (in \% terms).}
%\label{fig:comp_matrix}
%
%\end{figure*}

\section{Concluding Remarks:}
As CS matrices of low density (or high sparsity) result in algorithms with low computational complexity, the present work has constructed sparse CS matrices from the existing two binary sensing matrices. As an application of proposed methodology, we have shown that binary and ternary CS matrices for a more general set of numbers can be constructed.

\section{\bf Acknowledgments}
The first author is thankful for the support (Ref No. 19-06/2011(i)EU-IV) that he receives from UGC, Govt of India. The second author gratefully acknowledges the support (Ref No. 20-6/2009(i)EU-IV) that he receives from UGC, Govt of India. The third author is thankful to DST (SR/FTP/ETA-054/2009) for the partial support that he received. We thank Mr. Roopak R Tamboli for helping us in simulation work.







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%\begin{abstract}
%In the present work, we discuss a procedure for constructing sparse binary and ternary matrices from existing two binary sensing matrices. The matrices that we construct have several attractive properties such as smaller density, which supports algorithms with low computational complexity. As an application of our method, we show that a CS matrix of general row size different from $p, p^2, pq$ (for different primes $p,q$) can be constructed. 
%%In Compressed Sensing the matrices that satisfy the Restricted Isometry Property (RIP) play an important role.
%% But  to date, very few results  for designing such matrices are available. Of interest in several applications is a
 %%binary sensing matrix. The present work constructs the deterministic and binary sensing matrices using the Euler Squares. In particular, given a positive integer $m$ different from $p, p^2$ for a prime $p$, we show that it is possible to construct a binary sensing matrix  whose row size is $m$ and the column size is a function of $m^2$.
%\end{abstract}
%
%\begin{keyword}
%
%Compressed Sensing, RIP, Binary and ternary sensing matrices.
%%% keywords here, in the form: keyword \sep keyword
%
%%% MSC codes here, in the form: \MSC code \sep code
%%% or \MSC[2008] code \sep code (2000 is the default)
%
%\end{keyword}
%
%\end{frontmatter}
%
%% \linenumbers
%
%%% main text
%%\section{}
%%\label{}
%\section{Introduction}
%
%%\par  The flows of data (e.g., signals and images) around us are enormous today and rapidly growing. But the number of important features hidden in huge data are usually much smaller than the number of coefficients in a standard representation of the data. Hence data are compressible. In data processing, the traditional practice is to measure (sense) data in full length and then compress the resulting measurements before storage or transmission. In such a scheme, recovery of data is generally straightforward. This traditional data-acquisition process can be described as full sensing plus compressing". Compressive sensing (CS), also known as compressed sensing or compressive sampling, represents a paradigm shift in which the number of measurements is reduced during acquisition so that no
%%additional compression is necessary. The price to pay is that more sophisticated recovery procedures become necessary.
%%
%%\par In this paper, we will use the term ``signal" to represent generic data (so an image is a signal). Let
%%$\bar{\alpha}\in R^{M}$ represent a discrete signal and $y\in R^{m}$ a vector of linear measurements formed by taking inner
%%products of $\bar{\alpha}$ with a set of linearly independent vectors $\phi_{i}^{T}\in  R^{M}, i = 1, 2, \dots  ,m.$ In matrix format, the
%%measurement vector is $y = \Phi\bar{\alpha}$, where $\Phi \in  R^{m\times M}$ has rows $\phi_{i}^{T}, i = 1, 2,\dots   ,m$. %This process of obtaining $y$ from an unknown signal $\bar{\alpha}$ is often called encoding, while the process of recovering $\bar{\alpha}$ from the measurement vector $y$ is called decoding.
%%
%%\par When the number of measurements $m$ is equal to $n$, solving a linear system of equations, i.e., $\bar{\alpha} = \Phi^{-1}y$. However, in many applications, it is much more desirable to take fewer measurements provided one can still recover the signal. When $m < M$, the linear system $\Phi \alpha = y$ is typically under-determined, permitting infinitely many solutions. In this case, is it still possible to recover $\bar{\alpha}$ from $y$ through a computationally tractable procedure?
%%
%%
%%\par If we know that the measurement $y$ is from a highly sparse signal (i.e., it has very few nonzero components), then a reasonable decoding model is to look for the sparsest signal among all those that produce the measurement $y$; that is,
%%%\begin{displaymath}
%%%\begin{enumarate}
%%\item
%%\begin{equation}
%%\lebel{
%%P_0:\min_{\alpha} \Vert{\alpha} \Vert_0 \; \mbox{subject to} \quad \Phi \alpha=y.}
%%\end{equation}
%%%\end{enumarate}
%%%\end{displaymath} 
%%where the quantity $\Vert{\alpha} \Vert_0 $ denotes the number of non-zeros in $\alpha$. Model (1) is a combinatorial optimization
%%problem with a prohibitive complexity if solved by enumeration, and thus does not appear tractable. An alternative model is to replace the ``$\latin{l}_{0}-$norm" by the ``$\latin{l}_{1}-$norm" and solve a computationally tractable linear
%%program:
%%\item
%%\begin{equation}
%%\lebel{
%%P_1:\min_{\alpha} \Vert{\alpha} \Vert_1 \; \mbox{subject to} \quad \Phi \alpha=y.}
%%\end{equation}
%%This approach, often called basis pursuit, was popularized by Chen, Donoho and Sauders [9] in signal processing, though similar ideas existed earlier in other areas such as Geo-sciences.
%%
%%
%%
%%
%%
%%\par In most applications, sparsity is hidden in a signal $\bar{\alpha}$ so that it becomes sparse only under a ``sparsifying" basis $\Psi$; that is, $\Psi \bar{\alpha}$ is sparse instead of $\bar{\alpha}$ itself. %In this case, one can do a change of variable z = x and
%%%replace the equation Ax = b by (A􀀀1)z = b. For an orthonormal basis , the null space of A􀀀1 is a
%%%rotation of that of A, and such a rotation does not alter the success rate of CS recovery (as we will see later
%%%that the probability measure for success or failure is rotation-invariant). 
%%For simplicity and without loss of generality, we will assume $\Psi=I$ throughout this paper.
%%
%%
%%\par Fortunately, under favorable conditions the combinatorial problem (1) and the linear program (2) can share common solutions. Specifically, if the signal $\bar{\alpha}$ is sufficiently sparse and the measurement matrix $\Phi$ possesses certain nice attributes (to be specified later), then $\bar{\alpha}$ will solve both (1) and (2) for $\Phi \bar{\alpha}=y$. This property is called recoverability. 
%%%which, along with the fact that (1.2) can be solved eciently in theory, establishes the theoretical soundness of the decoding model (1.2).
%%
%%
%%\par Generally speaking, compressive sensing refers to the following two-step approach: choosing a measurement matrix $\Phi \in  R^{m\times M}$ with $m < n$ and taking measurement $\Phi \bar{\alpha}=y$ on a sparse signal $\bar{\alpha}$, and then reconstructing $\bar{\alpha}\in R^{M}$ from $y\in R^{m}$ by some means. Since $m < M$, the measurement $y$ is already compressed during sensing, hence the name ``compressive sensing" or CS. Using the basis pursuit model (2) to recover $\bar{\alpha}$ from $y$ represents a fundamental instance of CS, but certainly not the only one. Other recovery techniques include greedy-type algorithms (see [29], for example).
%%
%%
%%
%%
%
%
%Recent developments at the intersection of algebra 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 \cite{bourgain_2011}\cite{gil_2010}. Sparse representations of a function are a powerful analytic tool in many application areas such as image/signal processing and numerical computation \cite{Bruckstein_2009} , to name a few. The need for the sparse representation arises from the fact that several real life applications demand the representation of data in terms of as few basis (frame) type elements as possible. The elements or the columns of the associated matrix $\Phi$ are called atoms and the matrix so generated by them is called the dictionary. The developments of CS Theory depend typically on sparsity and incoherence \cite{Bruckstein_2009}\cite{Kashin_2007}. Sparsity expresses the idea that the “information rate” of a continuous time data may be much smaller than suggested by its bandwidth, or that a discrete-time data depends on a number of degrees of freedom which is comparably much smaller than its (finite) length. On the other hand, incoherence extends the duality between the time and frequency contents of data. 
%\par Since the sparsity of the CS matrix is key to minimizing the computational complexity associated with the matrix-vector multiplication, it is desirable that a CS matrix has smaller density. Here, by density, one refers to the ratio of number of nonzero entries to the total number of entries of the matrix. The sparse CS matrix may contribute to fast processing with low computational complexity in compressed sensing \cite{gil_2010}.
%
%\par In the recent literature on CS \cite{ind_2008, adcock_2013, bryant_2014, mixon_2012, dima_2012}, the deterministic construction of CS matrices has gained momentum.  R. Devore \cite{Ronald_2007} has constructed deterministic binary sensing  matrix of size $p^2 \times p^{r+1}$, where $p$ is prime or prime power. The density of this matrix is $\frac{1}{p}.$ S. Li et. al.\cite{li_2012} have generalized Devore's work, constructing binary sensing matrix of size $|\mathcal{P}|q \times q^{\mathcal{L}(G)}$, where $q$ is any prime power and  $\mathcal{P}$ is the set of all rational points on algebraic curve $\mathcal{X}$ over finite field $\mathbb{F}_q$. The density of this matrix is $\frac{1}{q}$. % P. Indyk \cite{ind_2008} has constructed binary sensing matrices using hash functions and extractor graphs with sizes $r2^{O(\log\log n)^{O(1)}} \times n$, where $r \ll n$.
 %A. Amini et. al. \cite{amini_2011} have constructed binary sensing matrices %with sizes $(16^{a}-1) \times \frac{(16^{a}-1)(16^{a}-6)}{5}$ 
%using OOC codes. The density of this matrix is $\frac{\lambda}{m}$, where $m$ is row size and $\lambda$ is the number of ones in each column. In all these constructions row sizes of associated matrices are given by some particular family of numbers.
%
%\par The CS matrices of general size will not impose any restriction on the data to be dealt with, when used in  applications such as data compression or classifications.
%The main contribution of the present work may be summarized as follows
%\begin{itemize}
%\item Construction of sparse binary and ternary matrices from existing sensing matrices.
%\item As an application of our construction methodology, we show that, given $m \neq p,p^{2},pq$ (for different primes $p,q$), it is possible to construct sparse binary and ternary matrices of row size $m$.
%\end{itemize}
%\noindent Consequently, we believe that this work is an attempt towards constructing CS matrices of general size.
%
%
%
%%\par In the present work, however, we construct binary and ternary CS matrices of very high sparsity (that is, low density) from existing binary sensing matrices. As an application of proposed method, we show that a CS matrix of general size different from $p, p^2, pq$ (for different primes $p,q$) can be constructed.
%\par The paper is organized in several sections. In section 2, we provide basics of CS theory.  While in sections 3 and 4, we discuss in detail the construction of CS matrices of low density and an application of proposed method respectively. In the last two sections, we present respectively the construction of ternary matrices and concluding remarks.
%
%
%
%
%
%
%
%\section{Basics of Compressed Sensing:}
%
%
%\par 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. 
%
%Denoting $\Phi^{r}_{k}$ as the $k^{\mbox{th}}$ row of $\Phi$, one may rewite the $k^{\mbox{th}}$ component in $y$ as $y_{k}=\left\langle x,\Phi^{r}_{k}\right\rangle, k=1,2,\dots m$. Here $\left\langle x,\Phi^{r}_{k}\right\rangle$ represents the inner-product between $x$ and $\Phi^{r}_{k}$. That is, the object $x$ to be acquired is correlated with the waveform $\Phi^{r}_{k}$. This is a standard setup in several applications \cite{Donoho_2006}\cite{candes_2008}. For example, if the sensing waveforms are Dirac delta functions, the $y$ is a vector of sampled values of $x$ in time or space domain. If the sensing waveforms are indicator functions of pixels, then $y$ is the image data typically collected by sensors in digital camera. If the sensing waveforms are sinusoids, then $y$ is a vector of Fourier coefficients and this modality is used in the magnetic resonance imaging. Nevertheless, if the sensing waveforms have $0$ and $1$ (or $0$ and $\pm1$) as elements, then the associated  matrix (referred conventionally to as a sensing matrix) can have potential application for multiplier-less dimensionality reduction. An excellent overview of Compressed Sensing and the applicability of several sensing matrices may be seen in \cite{candes_2008}.
%
%Now 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 and $\|x\|_{0}$ denotes the number of non-zero entries in $x$, that is $\|x\|_{0} = |\{j: x_j \neq 0\}|$ . ($\| . \|_{0}$ is not a norm, it is actually quasi-norm\footnote{it violates the triangular inequality, that is $\| x_{1} + x_{2} \|_{0} \geq \| x_{1}\|_{0} + \|x_{2} \|_{0} $.}). Now finding the sparsest solution  can be formulated as the following minimization problem (generally denoted as $P_{0}$ problem):
%\begin{displaymath}
%P_0:\min_{x} \Vert{x} \Vert_0 \; \mbox{subject to} \quad \Phi x=y.
%\end{displaymath} 
%This $P_{0}$ problem is a combinatorial minimization problem and is known to be NP-hard \cite{bourgain_2011}. One may use greedy methods and convex relaxation of $P_{0}$ problem to recover $k-$sparse signals (that $\|x\|_{0}=k$ or signals with $k$ number of nonzero entries). The convex relaxation of $P_{0}$ problem can be posed as $P_{1}$ problem \cite{can_2008} \cite{Candes_2005}, which is defined as follows:
%\begin{displaymath}
%P_1:\min_{x} \Vert{x} \Vert_1 \; \mbox{subject to} \quad \Phi x=y.
%\end{displaymath}
%\par The Orthogonal Matching Pursuit (OMP) algorithm and and the $l_{1}-$norm minimization (also called basis pursuit) are two widely studied
%CS reconstruction algorithms \cite{troop_2010}. 
%
%\par Candes and Tao \cite{Tao_2006} 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
%\begin{equation} 
%\label{eqn:rip}
%(1-\delta_{k}) \left\|x\right\|^{2}_{2} \leq \left\|\Phi x\right\|^{2}_{2} \leq (1+\delta_{k}) \left\|x\right\|^{2}_{2}.
%\end{equation} 
%Equivalently, for all vectors $x\in \mathbb{R}^{M}$ with $\left\|x\right\|_{2} = 1$ and $\|x\|_{0}\leq k$, one may rewrite (\ref{eqn:rip}) as
%\begin{displaymath}
%\label{eqn:r}
%(1-\delta_{k})  \leq \left\|\Phi x\right\|^{2}_{2} \leq (1+\delta_{k}) .
%\end{displaymath}
%The following theorem \cite{Candes_2005} establishes the equivalence between $P_{0}$ and $P_{1}$ problems: 
%\begin{theorem}
%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 $k-$sparse solution.
%\end{theorem}
%\par The mutual-coherence $\mu(\Phi)$ of a given matrix $\Phi$ is the largest absolute inner-product between different  normalized columns of $\Phi$, that is, $\mu(\Phi)= \max_{1\leq\; i,j \leq\; M,\; i\neq j} \frac{|\; \Phi_i ^T\phi_j|}{\Vert \Phi_i\Vert_{2} \Vert \Phi_j \Vert_2}$. Here, $\Phi_k$ stands for the $k$-th column in $\Phi$. 
%\noindent The following proposition \cite{bourgain_2011} relates the RIP constant $\delta_{k}$ and $\mu.$
%\begin{proposition}
%\label{thm:pro}
%Suppose that $\Phi_{1},\ldots,\Phi_{M}$ are the unit norm columns of the matrix $\Phi$ with coherence $\mu$. Then $\Phi$ satisfies RIP of order $k$ with constant $\delta_{k} = (k-1)\mu$.
%\end{proposition}
%
%\par 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})}$ \cite{Richard_2008}, \cite{Ronald_2007}, \cite{Kashin_1978}. However the only known matrices that satisfy the RIP for this range are based on random constructions. Richard Baraniuk and co-authors \cite{Richard_2008} have verified the RIP for random matrices with some probability.
%
%
%Presently the researchers working in CS theory attempt issues \cite{mixon_2014, adcock_2013, apple_2009} such as 
%\begin{enumerate}
%\item Maximizing the sparsity of the solution, that is, for a given pair $(y,\Phi )$, find $x$ such that  $\|x\|_0$  is as small possible
%\item	Improving the recovery process, that is, incorporating the prior information (for example, partial support solution) into the recovery process
%\item Developing faster algorithms
%\item	Designing the matrices that satisfy recovery properties
%\end{enumerate}
%\par The recovery algorithms available to date use the matrices $\Phi$  that are generated at random and there is no efficient method for verifying whether or not a given matrix $\Phi$ does indeed have the stronger reconstruction properties. For this and other reasons, it is useful to have an explicit construction of $\Phi$. 
%
%
%
%
%
%
%
%
%
%
%
%
%%\noindent Expressing the linear measurements of $x$ in the form of a vector $y$ through the sensing matrix $\Phi$ of size $m \times M (m \ll M)$, one gets a system $y=\Phi x$.  The problem of recovering sparse $x$ from $y$ can be formulated as finding the solution of the following optimization problem:
%%\begin{displaymath}
%%P_0:\min_{\alpha} \Vert{\alpha} \Vert_0 \; \mbox{subject to} \quad \Phi \alpha=y.
%%\end{displaymath} 
%%This $P_{0}$ problem is a combinatorial minimization problem and is known to be NP-hard \cite{Donoho_2006}. One may use greedy methods \cite{trop_2007, dai_2009} and convex relaxation of $P_{0}$ problem to recover sparse signals. The convex relaxation of $P_{0}$ problem can be posed as
%%\begin{displaymath}
%%P_1:\min_{\alpha} \Vert{\alpha} \Vert_1 \; \mbox{subject to} \quad \Phi \alpha=y.
%%\end{displaymath}
%%\par Candes and Tao \cite{can_2008, Tao_2006, cand_2006} established an equivalent relation between $P_{0}$ and $P_{1}$ problem provided the sensing matrix $\Phi$ satisfies Restricted Isometry Property(RIP).
%
%
%
%%Compressed Sensing(CS) aims at recovering high dimensional sparse vectors from considerably fewer linear measurements.
%%The problem of sparse recovery through $l_{0}$ norm minimization (that is, minimization of number of
%%nonzero components in the solution to be obtained) is not  tractable. Donoho et. al. \cite{cds_2001, Elad_2006},
%%Candes et. al. \cite{can_2008, Tao_2006, cand_2006} and A.Cohen et. al \cite{bestk_2009} have made several pioneering
%%contributions and have reposed the problem as a simple Linear Programming Problem (LPP). They have
%%then established the conditions that ensure the stated equivalence between the original $l_{0}$ problem and its reposed
%%version. It is known that RIP is one sufficient condition to ensure the eqivalence. Random matrices such as Gaussian or
%%Bernouli as their entries satisfiy RIP with high probability.
%%
%%\par R.Devore \cite{Ronald_2007} has constructed deterministic RIP matrices with $0'$s and $1'$s as elements (excluding column normalization factors) using
%%general univariate polynomials on finite fields.
%%In the present work, we extend the ideas developed in
%%\cite{Ronald_2007} and construct $0,1-$matrices that satisfy RIP with different row and column sizes using homogeneous multivariable
%%polynomials.
%%
%%\par The paper is organized into several sections. In sections 2 and 3, we present basic CS theory and conditions
%%that ensure the equivalence between $l_{0}-$norm problem and its LPP version problems. Motivated by the deterministic
%%construction methodology proposed in \cite{Ronald_2007}, we present in section 4 our extension, which is based on
%%homogeneous two variable polynomials over finite fields. In section 5, we extend the ideas to deal with circulant
%%matrices. While in section 6, we state the results for $n-$variable homogeneous polynomials. In the last section, we
%%present our concluding remarks.
%%
%%\section{Sparse recovery from linear measurements}
%
%
%%As stated already CS refers to the problem of reconstruction of an unknown vector $u \in \mathbb{R}^{m}$ from the
%%linear measurements $y = (\langle{u,\phi_{1}\rangle},\ldots,\langle{u,\phi_{n}\rangle})
%%\in \mathbb{R}^{n}$ with $\langle{u,\phi_{j}}\rangle$ being the inner product between $u$ and $\phi_{j}$. The basic objective
%%in CS is to design a recovery procedure based on the sparsity assumption on $u$ when the number of measurements $n$ is
%%much small compared to $m$. Sparse representations seem to have merit for various applications in areas such as
%%image/signal processing and numerical computation. \par A vector $u \in \mathbb{R}^{m}$ is $k-$spare if it has atmost $k$
%%nonzero coordinates. The problem of obtaining the sparse vector from its linear measurements may be posed as
%%\begin{align}
%%P_0:\min_{v} \Vert{v} \Vert_0 \; \mbox{subject to} \quad \Phi v=y.
%%\end{align}
%%Here $\Vert{v} \Vert_0 = \left|\left\{i \mid v_{i}\neq 0\right\} \right|.$
%%\par D.Donoho and others \cite{cds_2001}\cite{Elad_2006} have tried to understand the conditions under which
%%the solution to $P_{0}$ is the same as the solution to the following LPP :-
%%\begin{align}
%%P_1:\min_{v} \Vert{v} \Vert_1 \; \mbox{subject to} \quad \Phi v=y.
%%\end{align}
%%Here $\Vert{v} \Vert_1$ denotes the $l_{1}$-norm of the vector $v \in \mathbb{R}^{m}$. Denote the solution to $P_{1}$ by $f_{\Phi}(y)$ and solution to $P_{0}$ by $u^{0}_{\Phi}(y) \in \mathbb{R}^{m}$.
%%\section{On the equivalence between $P_{0}$ and $P_{1}$ problems}
%%\begin{definition}
%%The mutual-coherence $\mu(\Phi)$ of a given matrix $\Phi$ is the largest absolute normalized inner product between different columns of $A$. Denoting the $k$-th column in $A$ by $a_k$, the\textbf{mutual-coherence} is given by
%%\begin{align}
%%\mu(\Phi)= \max_{1\leq\; i,j \leq\; m,\; i\neq j} \frac{|\; \phi_i ^T\phi_j|}{\Vert \phi_i\Vert_{2} \Vert \phi_j \Vert_2}.
%%\end{align}
%%\end{definition}
%%\noindent It is known \cite{Elad_2006} that for $\mu$-coherent matrices $\Phi$, one has
%%\begin{align}
%%\label{eqn:eqlnt of solns}
%%u^{0}_{\Phi}(y)= f_{\Phi}(y) = u,
%%\end{align}
%%provided $u$ is $k-$sparse with $k < \frac{1}{2}\; (1+\frac{1}{\mu}).$ D.Donoho \cite{Donoho_2006} has given sufficient conditions on the matrix $\Phi$ for \eqref{eqn:eqlnt of solns} to hold.
%%In recent time the flow of data across the world are enormous and exponentially growing. Data can be huge but the underline important features can be few. Compressed sensing is proving new techniques to capture salient features of a signal using few samples. Let $x$ be an unknown $m-$dimensional vector. Now if $x$ has at least $k-$number of non zero entries we will say that $x$ is $k-$sparse. The main moto of compressed sensing is to find out few linear measurements along with stable and efficient reconstruction process which makes use of sparsity. Expressing each measurement vector as row of an $n \times m(n<<m)$ matrix $\Phi$, we will get a system $y=\Phi x +z$ to noisy cases. Now given a measurement vector $y,$ how can reconstruct the original signal $x$ from $y=\Phi x$. The problem can be formulated as finding the sparsest solution of linear equations $y=\Phi x$.
%%\begin{align}
%%P_0:\min_{x} \Vert{x} \Vert_0 \; \mbox{subject to} \quad \Phi x=y.
%%\end{align} 
%%This $P_{0}$ problem is a combitorial minimization problem and known to be NP-hard.
%%\par We can use greedy methods and convex relaxation of $P_{0}$ problem to recover $k-$sparse signals. The convex relaxation of $P_{0}$ problem can be posed as
%%\begin{align}
%%P_0:\min_{x} \Vert{x} \Vert_1 \; \mbox{subject to} \quad \Phi x=y.
%%\end{align}
%%%\par Candes and Tao \cite{can_2008, Tao_2006, cand_2006} established an equivalent relation between $P_{0}$ and $P_{1}$ problem provided the sensing matrix $\Phi$ satisfies Restricted Isometry Property(RIP).
%
%
%
%%\section{Equivalence between $P_{0}$ and $P_{1}$ problem:}
%%
%%
%%
%%\par Basic theory of CS presently consists of two components: recoverability and stability. Recoverability addresses the central questions: what types of measurement matrices and recovery procedures ensure exact recovery of all $k-$sparse signals (those having
%%exactly $k-$nonzeros) and how many measurements are sufficient to guarantee such a recovery? Existing results in CS recoverability and stability are mostly based on analyzing properties of the measurement matrix $\Phi$. The most widely used analytic tool is the so-called Restricted Isometry Property (RIP) of $\Phi$ Candes and Tao \cite{Tao_2006} 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}$ if for all $k-$sparse vectors $x\in \mathbb{R}^{m}$, we have
%%\begin{displaymath}
%%\label{eqn:ri}
%%(1-\delta_{k}) \left\|x\right\|^{2}_{2} \leq \left\|\Phi x\right\|^{2}_{2} \leq (1+\delta_{k}) \left\|x\right\|^{2}_{2}.
%%\end{displaymath}
%%The following theorem guarantees the equivalence between $P_0$ and $P_1$ problems \cite{can_2008}.
%%\begin{theorem}
%%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 unique solution.
%%\end{theorem}
%%The mutual-coherence $\mu(\Phi)$ of a given matrix $\Phi$ is the largest absolute normalized inner product between different columns of $\Phi$, that is, $\mu(\Phi)= \max_{1\leq\; i,j \leq\; M,\; i\neq j} \frac{|\; \Phi_i ^T\phi_j|}{\Vert \Phi_i\Vert_{2} \Vert \Phi_j \Vert_2}$. Here, $\Phi_k$ stands for the $k$-th column in $\Phi$. 
%%\noindent The following proposition \cite{bourgain_2011} relates the RIP constant $\delta_{k}$ and $\mu.$
%%\begin{proposition}
%%\label{thm:pro}
%%Suppose that $\Phi_{1},\ldots,\Phi_{M}$ are the unit norm columns of the matrix $\Phi$ and have coherence $\mu$. Then $\Phi$ satisfies RIP of order $k$ with constant $\delta_{k} = (k-1)\mu$.
%%\end{proposition}
%%\begin{definition}
%%The density of a matrix is the ratio of the number of its nonzero entries to the total number of its entries.
%%\end{definition}
%%\noindent Therefore, for a matrix of high sparsity, density is very small.
%%%\noindent Candes and Tao \cite{Candes_2005} have shown that whenever $\Phi$ satisfies RIP of order $3k$ with $\delta_{3k} < 1,$ the CS reconstruction error satisfies the following estimate
%%%\begin{align}
%%%\label{eqn:rip}
%%%\left\|u-f_{\Phi}(\Phi u)\right\|_{l^{m}_{2}} \leq C k^{\frac{-1}{2}} \sigma_{k}(u)_{l^{m}_{1}},
%%%\end{align}
%%%where $\sigma_k(u)_{l^m_1}$ denotes the $l_{1}$ error of the best $k-$term approximation, and the constant $C$ depends only on $\delta_{3k}$. This means that the bigger the value of $k$ for which we can verify the RIP then the better guarantee we have on the performance of $\Phi$.
%%\par One of the important problems in CS theory deals with constructing CS matrices that asymptotically satisfy the RIP for the largest possible range of $k$. 
%%It is known that the widest range possible is $k$ is of order $\frac{m}{\log(\frac{M}{m})}$ \cite{Richard_2008} \cite{Ronald_2007} \cite{Garnaev_1984} \cite{Kashin_1978}. However the only known matrices that satisfy the RIP for this range are based on random constructions. %\cite{Richard_2008}.
%%R. Baraniuk et. al.  \cite{Richard_2008} have verified the RIP for random matrices with high probability.
%%% using the following concentration of measure inequality:
%%%\begin{align}
%%%\label{eqn:cmi}
%%%\Pr(\left| \left\|\Phi(\omega)u\right\|_{l_{2}}^{2} - \left\| u\right\|_{l_{2}}^{2}\right| \geq \epsilon\left\| u\right\|_{l_{2}}^{2}) \leq 2e^{-nc_{0}(\epsilon)}, \; 0< \epsilon <1.
%%%\end{align}
%%%Where the probability is taken over all $n\times m$ matrices $\Phi(\omega)$, and $c_{0}(\epsilon)$ is a constant dependent only on $\epsilon$ such that for all $\epsilon \in (0,1)$, $c_{0}(\epsilon) > 0$.\\
%%There are, however, no deterministic constructions for $k$ of the order $\frac{m}{\log(\frac{M}{m})}$. To the best of our knowledge, designing the good deterministic constructions of RIP matrices is an important and open problem.  
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%
%
%
%
%
%
%
%
%\section{ Construction Procedure:}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\par In this section, we present our deterministic construction procedure taking two existing binary sensing matrices as inputs. We show that the resulting matrix has smaller density than the original two. Let $\Psi_{m \times M}$ be a binary sensing block matrix having $k''$ row blocks, each of size $n$ such that every block contains one $1$ and the overlap between any two columns is atmost $r$, that is $|\{l|\Psi_{l,p}=1\} \bigcap \{t|\Psi_{t,q}=1 \}|\leq r$ for any two columns $\Psi_{p}$ and $\Psi_{q}$. Let $\Psi'_{m' \times M'}$ be another binary sensing block matrix having $k'$ row blocks, each of size $n'$ such that each block contains one $1$ and the overlap between any two columns is atmost $r'$. Without loss of generality assume that $n' \leq n, k \leq \inbox{min \{ k' , k'' \}}$ and $r \leq r' \leq k \leq n$. 
%%Define the vector $V$, indexed on $i-1$(mod $n$), for $1 \leq i \leq nk=m$. There are $k$-blocks in $V$ and each block contains the numbers $0,1,\ldots,n-1$.
 %Now a new matrix can be constructed by the following steps:
%
%{\bf Step-1:} Let the $i^{th}$ column of $\Psi$ be  $\Psi_{i}$. For $1 \leq i \leq M$, define $S_{i} =  (((supp(\Psi_{i})-1)(mod \;n))^{T}+\bf{1}^{T})$, 
%where $\bf{1}^{T}$ is the vector consisting of all ones of size $k'' \times 1$, supp$(\Psi_{i})$ is the support vector of $\Psi_{i}$. Since $\Psi$ has $k''$ blocks and each block contains one $1$, it follows that $|S_{i}| = k''$ where $S_{i}$ is a $k''-$ tuple on the set $X=\{1,2,\ldots,n\}$. Since $\Psi$ has $M$ columns, we have $M$ such $k''-$tuples. For example, suppose $m=9$ and $\Psi$ has 3 blocks, then each block is of size 3. Now, if the $i^{th}$ column $\Psi_{i}$ is $(1\; 0\; 0\; 0\; 1\; 0\; 0\; 0\; 1)^{T}$, supp$(\Psi_{i})$ is $[1\;5\;9]$, then the triplet, $S_{i}$, corresponding to this column  is $[1\;2\;3]$. Similarly from the matrix $\Psi'$, we can generate $M'$ number of $k'-$tuples on the set $Y = \{1,2,\ldots,n'\}.$  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%{\bf Step-2:} From $k''-$tuples of first matrix $\Psi$ we remove last $(k'' - k)$ entries from each tuple to make it a $k-$tuple.  Now add $(-1)$ to each of the entries of the $M$ number of $k-$tuples that are obtained from $\Psi$. Let the $k-$tuples be of the form $(c_{i1}, c_{i2}, \ldots,c_{ik})$ for $1 \leq i \leq M$. From $k'-$tuples of second matrix $\Psi'$, we remove last $(k' - k)$ entries from each tuple to make it $k-$tuple. By this process, we get $M'$ number of $k-$tuples from the second matrix $\Psi'$. Let each $k-$tuple have the form $(c'_{j1}, c'_{j2}, \ldots,c'_{jk})$ for $1 \leq j \leq M'$.
%
%{\bf Step-3:} Now replace each $k-$tuple $(c_{i1}, c_{i2}, \ldots,c_{ik})$ with $M'$ number of $k-$tuples (obtained from $\Psi'$) by adding $n' (c_{i1}, c_{i2}, \ldots,c_{ik})$  to each of the $k-$tuples $(c'_{j1}, c'_{j2}, \ldots,c'_{jk})$ for $1 \leq j \leq M'$. This way, we get $MM'$ number of $k-$ tuples on the set $X'=\{1,2,\ldots,nn'\}$. Denote these $k-$tuples by $F$. Let $(a_{j1}, a_{j2}, \ldots,a_{jk})$ for $j= 1,2,....,MM'$ be the $k-$ tuples in $F$.
%
 %
%{\bf Step-4:} From these $k-$ tuples we form a binary vector of length $nn' \times k$ where $1$ occurs in the positions $(l-1).nn'+a_{jl}$ for $l= 1,2,\dots,k$ and rest of the positions are zeros. Using these $MM'$ number of $k-$tuples, we form binary sensing matrix $\Phi$ having $k$ number of blocks and each block is of size $nn'$ and every block contains single $1$. The position of one's in each block is indexed by the $k-$ tuples. So the size of the matrix $\Phi$ becomes $nn'k \times MM'$.
%The pseudo code of the proposed method is as follows: \\
%%----------------------------------------------
%\begin{center}
%\begin{tabular}{|l l|}
%\hline \\
%1. & {\bf Input:}  Two matrices $\Psi$, $\Psi'$ of sizes $nk'' \times M$, $n'k' \times M'$ \\
%2. & Suppose $|Supp(\Psi_i) \cap Supp(\Psi_j)| \leq r $ and \\
   %& $ |Supp(\Psi'_i) \cap Supp(\Psi'_j)| \leq r'$, $\forall \ i \neq j$  \\
%3. & Assume  $n' > n, k \leq min \{k',k''\}$ and $r \leq r' \leq k \leq n$ \\
%4. & Set $S_{i} =  (((supp(\Psi_{i})-1)(mod \;n))^{T}+\bf{1}^{T})$, $|S_i| = k'', \; \forall \; i=1,2,\ldots,M$  \\
%5. & Similarly, $S'_j$ with $|S'_j| = k'$ are defined for $j=1,2,\ldots,M'$ \\
%6. & Set $S''_{i,j} = S'_{j,k} - \mathbf{1}+n' S_{i,k}$, $S'_{j,k}$ and $S_{i,k}$ are first $k$ entries of $S'_j$ and $S_{i}$ \\
%7. & $|S''_{i,j}| = k$ and Let $S''_{i,j} = (S''_{i,j,1}, S''_{i,j,2}, \dots, S''_{i,j,k}) $ \\
   %&  $1 \leq S''_{i,j,l} \leq nn', \forall l=1,2,...,k$ \\
%8. & From each $S''_{i,j}$, create a vector $v_{i,j}$ of length $nn'k$ \\ 
   %&  and $v_{i,j}=1$ at $(l-1).nn'+ S''_{i,j,l}$ for $l= 1,2,\dots,k$ and zero elsewheres\\  
%9. & {\bf Output:} $\Phi'$, a matrix of size $nn'k \times MM'$, whose columns are $v_{i,j}.$ \\ \\
%\hline
%\end{tabular}
%\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%%This methodology is summarized in Fig.1
%\begin{lemma}\label{lem:1}
%The coherence of the enlarged matrix $\Phi$ of size $nn'k \times MM'$, $\mu(\Phi)$, is atmost $\frac{r'}{k}$.
%\end{lemma}
%
%\begin{proof}
%Let $\Phi_{i}, \Phi_{j}$ be two arbitrary columns of matrix $\Phi$. There exist two $k-$ tuples $f_i ,f_j \in F$ such that $\Phi_{i}, \Phi_{j}$ are the corresponding vectors of $k-$ tuples $f_i ,f_j$ as defined in the above construction . Suppose $f_{i}= (c'_{k'1}, c'_{k'2}, \ldots,c'_{k'k})+n'(c_{k1}, c_{k2}, \ldots,c_{kk})$ and $f_{j}= (d'_{k'1}, d'_{k'2}, \ldots,d'_{k'k})+n'(d_{k1}, d_{k2}, \ldots,d_{kk})$, where $(c'_{k'1}, c'_{k'2}, \ldots,c'_{k'k}), (d'_{k'1}, d'_{k'2}, \ldots,d'_{k'k})$ are two $k-$tuples obtained from $\Psi'$ and $(c_{k1}, c_{k2}, \ldots,c_{kk}), (d_{k1}, d_{k2}, \ldots,d_{kk})$ are $k$ tuples obtained from $\Psi$.
%Set $g_{ij} = f_{i}-f_{j}= (c'_{k'1}, c'_{k'2}, \ldots,c'_{k'k})-(d'_{k'1}, d'_{k'2}, \ldots,d'_{k'k}) + n'\biggl((c_{k1}, c_{k2}, \ldots,c_{kk})-(d_{k1}, d_{k2}, \ldots,d_{kk})\biggl).$ We will show that $g_{ij}$ has atmost $r'$ number of zeros, which implies that intersection between the supports of $\phi_{i}, \phi_{j}$ is atmost $r'$. Now $|c'_{k^{'}i}-d'_{k^{'}i}|<n'$ and $|c_{ki}-d_{ki}|<n$. The $l^{th}$ element of $g_{ij}$ is $(g_{ij})_{l}= (c'_{k'l}-d'_{k'l})+ n'(c_{kl}-d_{kl}).$ We investigate the cases wherein $(g_{ij})_{l} =0.$\\
%\textbf{Case 1:} Suppose $c'_{k'l} \neq d'_{k'l}$. \\
%\textbf{Sub case 1.1:} If $c_{kl} = d_{kl}$, then $(g_{ij})_{l} \neq 0.$\\
%\textbf{Sub case 1.2:} If $c_{kl} \neq d_{kl}$, then also $(g_{ij})_{l} \neq 0.$ Since $|c_{kl}-d_{kl}|\geq 1, |c_{kl}-d_{kl}|<n$ and $|c'_{k^{'}l}-d'_{k^{'}l}|<n'$, we have $(g_{ij})_{l} = (c'_{k^{'}l}-d'_{k^{'}l})- n'(c_{kl}-d_{kl}) \neq 0$.\\
%\textbf{Case 2:} Suppose $c'_{k'l} = d'_{k'l}$ then $(g_{ij})_{l} =0$ only when $c_{kl} = d_{kl}$.
%\par From the above cases, we conclude that $(g_{ij})_{l} =0$ only when $c'_{k'l} = d'_{k'l}$ and $c_{kl} = d_{kl}$, but as  both matrices $\Psi$ and $\Psi'$ can have atmost $r'$ intersections, $(g_{ij})_{l} =0$ can occur for atmost $r'-$choices of $j$. So $\phi_{i}, \phi_{j}$ have atmost $r'-$intersections. So the coherence $\mu(\Phi)$ of $\Phi$ is atmost $\frac{r'}{k}$. 
%
%
%% Now our claim is $f_{i}$ and $f_j$ can have atmost $r$ intersections. Since $(i_{k'1}, i_{k'2}, \ldots,i_{k'k})$ and $(j_{k'1}, j_{k'2}, \ldots,j_{k'k})$ are $k-$tuples corresponding to $\Psi'$, overlap of any two columns of $\Psi'$ is atmost $r$ implies that these two $k-$tuples have atmost $r$ intersections. With out loss of generality assume that $i_{k'i} = j_{k'i}$ for $i=1,2,\ldots,r.$ Now we have to analyze elements of $f_{i}$ and $f_j$ block-wise. Consider the $i^{th}$ block and let $g= (i_{k'i} + n' i_{ki})- (j_{k'i} + n' j_{ki}) = (i_{k'i} - j_{k'i})+ n' (i_{ki} -  j_{ki})$. If we show $g=0$ then intersection is occurring at $i^{th}$ block. Suppose assume that $i_{k'i} \neq j_{k'i}$, that is $(i_{k'i} - j_{k'i}) \neq 0$. Since $i_{k'i}, j_{k'i} \in Y$ and $i_{ki}, j_{ki} \in X$, we have $|i_{k'i} - j_{k'i}| < n'$ and either $i_{ki} = j_{ki}$ or $i_{ki} \neq j_{ki}$. If $i_{ki} = j_{ki}$, then $g \neq 0$. If $i_{ki} \neq j_{ki}$, then $|i_{ki} - j_{ki}| \geq 1$, which implies that $n'(i_{ki} - j_{ki}) \geq n'$. There fore we have $|i_{k'i} - j_{k'i}| < n'$ and $n'(i_{ki} - j_{ki}) \geq n'$, which implies that $g \neq 0.$ So, if in the $i^{th}$ block elements are different corresponds to matrix $\Psi'$ then intersection can not occur in that block position. Now suppose $i_{k'i} = j_{k'i}$, then $g=0$ only when $i_{ki} =  j_{ki}$. So, it shows that intersection can occur in the $i^{th}$ block only when elements in $i^{th}$ block are same. So as we assumed that $i_{k'i} = j_{k'i}$ for $i=1,2,\ldots,r.$ So there can have only $r-$intersections. Which implies that overlap between any two columns is $r$. Since the number of ones in each column of $\Phi$ is $k$, we have coherence of $\Phi$ is atmost $\frac{r}{k}$.  
%\end{proof} 
%\noindent The following theorem shows the RIP compliance of $\Phi$. 
%\begin{theorem}
%\label{thm:r}
%The afore-constructed matrix $\Phi_{nn'k \times MM'}$ satisfies RIP with $\delta_{k'} = (k'-1)({\frac{r'}{k}})$ for any $k' < \frac{k}{r'} + 1.$    
%\end{theorem}
%\begin{proof}
%Proof follows from the Proposition \ref{thm:pro} and Lemma \ref{lem:1}. 
%\end{proof}
%%\begin{theorem}
%%Suppose $m$ is any positive integer different from $p, p^2, pq$ for distinct primes $p,q$. Then there exists a CS matrix of row sizes $m$.
 %
%%If $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$ such that $r_{i}\geq 2$ for $1 \leq i \leq l$, $r_{i} > 2$ for $i=1$ then there exist a matrix of row size $m$.
%%\end{theorem} 
%%\begin{proof}
%%Without loss of generality assume that $2^{r} \leq p^{r_{1}}_{1} \leq p^{r_{2}}_{2} \leq \ldots \leq p^{r_{l}}_{l}$.\\
%%\textbf{Case 1:} If $m = p^{i}, i>2$ then $m$ can be written as $m = p^{i-3}p^{2}p$. Take matrix $\Psi$ having $p'(>p)-$blocks and each block of size $p^{i-3}$. Take another matrix $\Psi'$ having $p''(>p)-$blocks and each block of size $p^{2}$ (existence of such kind of matrices in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices then we will generate matrix $\Phi$ of row size $p^{i}$.\\ 
%%\textbf{Case 2:} Suppose $m=p^{r_{1}}_{1}p^{r_{2}}_{2}$ such that both $r_{1}, r_{2} \neq 1$ and $p^{r_{1}}_{1}>p^{r_{2}}_{2}$. Take matrix $\Psi$ having $p_{1}-$blocks and each block of size $p_{1}^{r_{1}-1}$. Take another matrix $\Psi'$ having $p_{1}-$blocks and each block of size $p_{2}^{r_{2}}$ (existence of such kind of matrices in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices then we will generate matrix $\Phi$ of row size $m$.\\ 
%%\textbf{Case 3:} Suppose $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{s}}_{s}$ such that $ s\geq3, p^{r_{1}}_{1}>p^{r_{2}}_{2}> \ldots >p^{r_{s}}_{s}$. We will show that there exist a CS matrix of row size $m$ by induction on $s$. For $s=3$, $m=p^{r_{1}}_{1}p^{r_{2}}_{2}p^{r_{3}}_{3}$. Take matrix $\Psi$ having $p^{r_{3}}_{3}-$blocks and each block of size $p_{1}^{r_{1}}$. Take another matrix $\Psi'$ having $p^{r_{3}}_{3}-$blocks and each block of size $p_{2}^{r_{2}}$ (existence of such kind of matrices in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices then we will generate matrix $\Phi$ of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}p^{r_{3}}_{3}$. Assume that for $3<l<k$ there exist a matrix of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$. Now we have to show that there exist a CS matrix of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{k-2}}_{k-2}p^{r_{k-1}}_{k-1}p^{r_{k}}_{k}$. Take matrix $\Psi$ having $p^{r_{k}}_{k}-$blocks and each block of size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{k-2}}_{k-2}$. Take another matrix $\Psi'$ having $p^{r_{k}}_{k}-$blocks and each block of size $p_{k-1}^{r_{k-1}}$(existence of such kind of matrices in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices then we will generate matrix $\Phi$ of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{k-2}}_{k-2}p^{r_{k-1}}_{k-1}p^{r_{k}}_{k}$. By induction we have proved that there exist a CS matrix of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{s}}_{s}$ such that $ s\geq3, p^{r_{1}}_{1}>p^{r_{2}}_{2}> \ldots >p^{r_{s}}_{s}$. 
%
%
%%Let $m$ be any integer such that $m \neq p^{i}$ for $i>2$. From the fundamental theorem of arithmetic $m$ is factorized as $m = 2^{r}p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$.  Let $k'= \min\{2^{r},p^{r_{1}}_{1},p^{r_{2}}_{2},\ldots ,p^{r_{l}}_{l}\}$ and $k = k'-1$. With out loss of generality assume that $k' = 2^r$ (The following arguments hold true even if  $k' = p^{r_{s}}_{s}$ for some $s \in \{1,2,\ldots, l\}$). From the construction of MacNeish \cite{euler_1922}, it is known that the Euler Square of index $m, k$ exists. Let $m_{1} = p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$, without loss of generality, consider that $p^{r_1}_{1}=\min\{p^{r_{1}}_{1},p^{r_{2}}_{2},\ldots ,p^{r_{l}}_{l}\}$. Since $2^{r} \leq (p^{r_1}_{1}-1)$, the Euler Square of index $m_{1}, (p^{r_1}_{1}-1)$ exists, which in view of lemma-\ref{lem:e} implies that the  Euler Square of index $m_{1}, 2^{r}$ exists. The binary CS matrix constructed through this Euler Square has a row size of $m_{1}2^{r}$, which is $m$. 
%%\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\noindent \textbf{Remark-1:} The density of the matrix $\Phi$ is $\frac{1}{nn'}$, which is smaller than the densities of the matrices $\Psi$ and $\Psi'$, which are $\frac{1}{n}$ and $\frac{1}{n'}$ respectively. Hence using our construction procedure we can construct more sparse binary matrices from existing binary sensing matrices.\\
%\noindent \textbf{Remark-2:} The positions of $1'$s in the matrix $\Phi$ are known and we know that every block contains single one. So we can permute the columns of the matrix $\Phi$ so that the support of the permuted matrix has nice structured sparsity.  
%\subsection{Example:} In this section, we demonstrate our proposed method of construction via an example.
%\noindent Let $\Psi_{4 \times 4}$ be a binary sensing block matrix 
%\[ \left( \begin{array}{cccc}                       
     %1 & 0 & 1 & 0 \\
     %0 & 1 & 0 & 1 \\
		%\hline
     %1 & 0 & 0 & 1 \\
     %0 & 1 & 1 & 0 \end{array} \right)\] 
%having $2$ row blocks, each of size $2$ such that every block contains one $1$ and the overlap between any two columns is $1$.
%\par Let $\Psi'_{9 \times 9}$ be a binary sensing block matrix 
%\[ \left( \begin{array}{ccccccccc}
%
     %1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\
     %0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\
     %0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\
		%\hline
     %1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\
     %0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1  \\
     %0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0  \\
		%\hline
     %1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1  \\
     %0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0  \\
     %0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} \right)\]
%having $3$ row blocks, each of size $3$ such that every block contains one $1$ and the overlap between any two columns is $1$.
%
%{\bf Step-1:} The corresponding four $2-$tuples $S$ obtained from $\Psi$ are
 %\[ \left( \begin{array}{cccc}
      %
			%2 & 1 & 2 & 1 \\
			%2 & 1 & 1 & 2 \end{array} \right)\]
			%
 %The corresponding nine $3-$tuples $S'$ obtained from $\Psi'$ are
	%\[ \left( \begin{array}{ccccccccc}
%
      %2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 \\
			%2 & 3 & 1 & 3 & 1 & 2 & 1 & 2 & 3 \\
			%2 & 3 & 1 & 1 & 1 & 3 & 3 & 1 & 2	\end{array} \right)\]
%
%{\bf Step-2:} Now removing the last entries from each $3-$tuple of $S'$, we get nine $2-$tuples $S''$ , which are the following
	%\[ \left( \begin{array}{ccccccccc}
%
      %2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 \\
			%2 & 3 & 1 & 3 & 1 & 2 & 1 & 2 & 3  \end{array} \right)\]
%
%{\bf Step-3:} Now let us add $(\bf{-1})$ to each of the entries of $S$ and then multiply each of the tuples by $3$. Now to each $2-$tuple add all $2-$tuples of $S''$ and generate $S'''$ with $|S'''|=36$. Now all the entrices of $S'''$ are less or equal to $6$. All the tuples of $S'''$ are as follows:
  %
 %
%\tiny{
 %\[ \left( \begin{array}{*{36}c}
%%\begin{pmatrix} 
%5 & 6 & 4 & 5 & 6 & 4 & 5 & 6 & 4 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 5 & 6 & 4 & 5 & 6 & 4 & 5 & 6 & 4 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 \\
%5 & 6 & 4 & 6 & 4 & 5 & 4 & 5 & 6 & 2 & 3 & 1 & 3 & 1 & 2 & 1 & 2 & 3 & 2 & 3 & 1 & 3 & 1 & 2 & 1 & 2 & 3 & 5 & 6 & 4 & 6 & 4 & 5 & 4 & 5 & 6 
%%\end{pmatrix}
%\end{array} \right)\]}
%\normalsize
 			%
%{\bf Step-4:} From each $2-$tuple of $S'''$, we form a column consisting of two blocks of size $6$ where the positions of $1's$ in each block are dictated by the two entries of the tuple. Finally, from all these steps, we obtain the following matrix 
%$\Phi_{12 \times 36} :$ 		
%
%
%
%%\[ \left( \begin{array}{cccccccccccccccccccccccccccccccccccc}
%
%%\[ \left( \begin{array}{*{36}c}
%% \begin{pmatrix} 
%%\begin{gather*}
%%\setlength{arraycolsep}{.75\arraycolsep}
%%\text{\footnotesize $ \displaystyle
%%\begin{pmatrix}
%\tiny{
%\[ \left( \begin{array}{*{36}c}
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1 \\
	 %
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0 \\
	%
	 %0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%\hline
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%
	 %0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0 \\
	%
	 %1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0 \\
	%
	 %0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1 
	%\end{array} \right)\]}
	%\normalsize
	%%$}
%%\end{pmatrix}
	%%\end{equation*}
%%	\end{gather*}
%
%
			%
      %
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%\begin{sideways}
%%\thispagestyle{empty}%
%%\makebox[\textheight][c]{\begin{minipage}{\paperheight}
%%\setlength\arraycolsep{4pt}
%%\begin{align*}
         %%&\left[ {\begin{array}{ccccccccccc}
         	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1 \\
	 %%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0 \\
	%%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0 \\
	%%
	 %%0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0 \\
	%%
	 %%1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0 \\
	%%
	 %%0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1 
         %%\end{array} } \right]
         %%%\cdot\left[ {\begin{array}{c}
         %%%E(\widetilde{A}_{kk}^{cn}|L_k^c)\\
         %%%E(\widetilde{A}_{k k+1}^{cn}|L_{k+1})\\
         %%%E(\widetilde{A}_{k k+1}^{cn}|L_{k+1}^c)\\
         %%%E(\widetilde{A}_{k k+2}^{cn}|L_{k+2})\\
         %%%E(\widetilde{A}_{k k+2}^{cn}|L_{k+2}^c)\\
         %%%\vdots \\
         %%%E(\widetilde{A}_{k c-1}^{cn}|L_{c-1})\\
         %%%E(\widetilde{A}_{k c-1}^{cn}|L_{c-1}^c)\\
         %%%E(\widetilde{A}_{kc}^{cn}|L_{c})\\
         %%%\end{array} } \right]\\=
         %%%&\left[ {\begin{array}{c}
         %%%E(R_k|L_k^c) + P(N_k^s|L_k^c)   E\left(\widetilde{B}_{kk}^{c+n}|L_k^c\right) \\
         %%%E(R_{k+1}|L_{k+1}) + P(N_{k+1}^s|L_{k+1})  E\left(\widetilde{B}_{kk+1}^{c+n}|L_{k+1}^c      \right)\\
         %%%E(R_{k+1}|L_{k+1}^c) +P(N_{k+1}^s|L_{k+1}^c)   E\left(\widetilde{B}_{kk+1}^{c+n}|L_{k+1}^c      \right)\\
         %%%E(R_{k+2}|L_{k+2}) + P(N_{k+2}^s|L_{k+2})  E\left(\widetilde{B}_{kk+2}^{c+n}|L_{k+2}^c      \right)\\
         %%%E(R_{k+2}|L_{k+2}^c) +P(N_{k+2}^s|L_{k+2}^c)   E\left(\widetilde{B}_{kk+2}^{c+n}|L_{k+2}^c      \right)\\
         %%%\vdots \\
         %%%E(R_{k+2}|L_{c-1}) + P(N_{c-1}^s|L_{c-1})  E\left(\widetilde{B}_{kc-1}^{c+n}|L_{c-1}^c      \right)\\
         %%%E(R_{k+2}|L_{c-1}^c) +P(N_{c-1}^s|L_{c-1}^c)   E\left(\widetilde{B}_{kc-1}^{c+n}|L_{c-1}^c      \right)\\
         %%%E(\widetilde{A}_{kc}^{cn}|L_{c})\\
         %%%\end{array}} \right]
%%\end{align*}
%%\end{minipage}}
%%\end{sideways}
%%
%%
%%\begin{sideways}
%%\thispagestyle{empty}%
%%\makebox[\textheight][c]{\begin{minipage}{\paperheight}
%%\setlength\arraycolsep{4pt}
%%\begin{align*}
         %%&\[ \left( \begin{array}{*{36}c}
	%%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1 \\
	 %%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0 \\
	%%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0 \\
	%%
	 %%0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0 \\
	%%
	 %%0& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 1& 0& 0 \\
	%%
	 %%1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 1& 0 \\
	%%
	 %%0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1 
	%%\end{array} \right)\]
%%\end{align*}
%%\end{minipage}}
%%\end{sideways}
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%\subsection{Example}
%For distinct primes $p_{1}, p_{2}$ and any positive integer $r$, suppose $r<p_{2}<p_{1}$. Using the method in \cite{Ronald_2007}, one obtains binary matrices $\Psi, \Psi'$ of sizes $p^{2}_{2} \times p^{r+1}_{2}$ and $p^{2}_{1} \times p^{r+1}_{1}$ respectively. Thus we get $p^{r+1}_{1}$ number of $p_{1}-$tuples and $p^{r+1}_{2}$ number of $p_{2}-$tuples. If we apply our construction procedure on these matrices then we generate matrix $\Phi$ of size $p_{1}p^{2}_{2} \times (p_{1}p_{2})^{r+1}$ with coherence $\frac{r}{p_{2}}$. The density of this matrix $\Phi$ is $\frac{1}{p_{1}p_{2}}$, which is small compared to $\frac{1}{p_{1}}$ and $\frac{1}{p_{2}}$, the densities of $\Psi$ and $\Psi'$ respectively.
%\par In the construction of $\Phi$, the row size is $p_{1}p^{2}_{2}$ and each column contains $p_{2}$ number of ones, and the overlap between any two columns is $r$, therefore the maximum possible column size for this construction \cite{amini_2011} is $\frac{{p_{1}p^{2}_{2}\choose r+1}}{{p_{2} \choose r+1}}$, which is on the order of $(p_{1}p_{2})^{r+1}$, that is, $\frac{{p_{1}p^{2}_{2}\choose r+1}}{{p_{2} \choose r+1}} = O((p_{1}p_{2})^{r+1})$. Consequently, our enlarged matrix attains the maximum possible column size asymptotically. 
 %
%%\textbf{Remark-2:} In our previous work \cite{ram_2013}, using Euler Squares, we have constructed binary sensing matrices of any row size $m$ except for $ p, p^2$ (for prime $p$) with asymptotically optimal column size such that overlap between any two columns is $1$. In the present work, however, we construct sparse binary sensing matrices of any row size $m$ except for $p, p^2, pq$ for distinct primes $p,q$ such that overlap between any two columns is $r' \geq 1$ and these matrices too possess optimal possible column size asymptotically. Because of $r'>1$, the matrix so constructed here has better column-to-row 
%%ratio than the one in \cite{ram_2013}. This has greater relevance to applications like dimensionality reduction \cite{Elad_2010}.  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{An application of proposed construction procedure:}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\ As stated already, the present work helps us to construct deterministic CS matrices of lower density. In addition, we show that this methodology could be adopted to constructing CS matrices of general row sizes.
%
%%We can construct binary matrices of row size different from $p, p^2, pq$ (for distinct primes $p,q$), by our construction procedure with the help of existing binary matrices.
%
%\begin{theorem}
%Suppose $m$ is any positive integer different from $p, p^2, pq$ for distinct primes $p,q$. Then there exists a binary CS matrix of row size $m$.
 %
%%If $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$ such that $r_{i}\geq 2$ for $1 \leq i \leq l$, $r_{i} > 2$ for $i=1$ then there exist a matrix of row size $m$.
%\end{theorem} 
%\begin{proof}
%%Without loss of generality assume that $2^{r} \leq p^{r_{1}}_{1} \leq p^{r_{2}}_{2} \leq \ldots \leq p^{r_{l}}_{l}$.\\
%\textbf{Case 1:} 
%If $m = p^{i}, i>2$, then $m$ can be written as $m = p^{i-2}p.p$. Suppose $\Psi$ is a matrix having $p'(>p)-$blocks where each block is of size $p^{i-2}$. Let $\Psi'$ be a CS matrix having $p$ blocks where each block is of size $p$ (It is guaranteed in \cite{Ronald_2007} that such matrices exist, which is discussed in Section (2) and in 3.1 Example). By applying our construction procedure on these two matrices, we generate matrix $\Phi$ of row size $p^{i}$.\\ 
%\textbf{Case 2:} Suppose $m=p^{r_{1}}_{1}p^{r_{2}}_{2}$ such that both $r_{1} \neq 1 \neq r_{2}$ and $p^{r_{1}}_{1}>p^{r_{2}}_{2}$. Take a CS matrix $\Psi$ having $p_{1}-$ blocks with each block being of size $p_{1}^{r_{1}-1}$. Let $\Psi'$ be another CS matrix having $p_{1}-$blocks where each block is of size $p_{2}^{r_{2}}$ (existence of such matrices is guaranteed in \cite{Ronald_2007}). By applying our construction procedure on these two matrices, we generate matrix $\Phi$ of row size $m$.\\ 
%\textbf{Case 3:} Suppose $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{s}}_{s}$ such that $ s\geq3$ and $ p^{r_{1}}_{1}>p^{r_{2}}_{2}> \ldots >p^{r_{s}}_{s}$. By induction on $s$, we show that there exists a CS matrix of row size $m$. For $s=3$, set $m_3=p^{r_{1}}_{1}p^{r_{2}}_{2}p^{r_{3}}_{3}$. Suppose the CS matrix $\Psi$ has $p^{r_{3}}_{3}-$blocks where each block is of size $p_{1}^{r_{1}}$. Let $\Psi'$ be another CS matrix having $p^{r_{3}}_{3}-$blocks such that each block is of size $p_{2}^{r_{2}}$ (existence of such matrices is guaranteed in \cite{Ronald_2007}). If we apply our construction procedure on these two matrices, then we generate matrix $\Phi$ of row size $p^{r_{1}}_{1}p^{r_{2}}_{2}p^{r_{3}}_{3}$, which is $m_3$. Assume that for $3<l<k$, there exists a matrix of row size $m_l=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{l}}_{l}$. Now we have to show that there exists a CS matrix of row size $m_k=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{k-2}}_{k-2}p^{r_{k-1}}_{k-1}p^{r_{k}}_{k}$. Take a CS matrix $\Psi$ having $p^{r_{k}}_{k}-$blocks such that each block is of size $m_{k-2}=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{k-2}}_{k-2}$. Suppose $\Psi'$ has $p^{r_{k}}_{k}-$blocks such that each block is of size $p_{k-1}^{r_{k-1}}$. By applying our construction procedure on these two matrices, we generate matrix $\Phi$ whose row size is $p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{k-2}}_{k-2}p^{r_{k-1}}_{k-1}p^{r_{k}}_{k}$, which is $m$. By induction we conclude that there exists a CS matrix of row size $m=p^{r_{1}}_{1}p^{r_{2}}_{2}\ldots p^{r_{s}}_{s}$. s 
%\end{proof}
%
%
%\noindent \textbf{Remark-3:}
%The authors of \cite{amni_2012} claimed general row size via Kronecker Delta product. If we apply Kronecker Delta product on $\Psi_{m \times M}$ and $\Psi'_{m' \times M'}$, the existing matrices that we started with, one obtains $\Psi''$, which is of the size $mm' \times MM'$. The method proposed herein, on the otherhand, results in $\Phi$ of size $nn'k \times MM'$. Although both the matrices have same coherence and same density, as $nn'k<mm'$, $\Phi$ has better aspect ratio or redundancy factor (column to row ratio) compare to $\Psi'$.\
%
%
%\noindent \textbf{Remark-4:}
 %As coherence of the resulting matrix depends on the choice of the two matrices, we can choose the two matrices in such a way that the resultant matrix has low coherence. In the above proof, we have used as an example the matrices constructed in \cite{Ronald_2007}. Nevertheless, one may use other suitable binary matrices like those constructed in \cite{li_2012}. \
%
%
%\section{Construction of ternary matrices}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Let $\Phi_{m\times M}$ be a matrix having $k$ number of blocks where each block is of size $n$, containing single one's and intersection between any two different columns of $\Phi$ is atmost $r$. Let the $i^{th}$ column of $\Phi$ be  $\Phi_{i}$. For $1 \leq i \leq M$, define $f_{i} =  (((supp(\Phi_{i})-1)(mod \;n))^{T}+\bf{1}^{T})$, 
%where $\bf{1}^{T}$ is the vector consisting of all ones of size $ k \times 1$, supp$(\Phi_{i})$ is the support vector of $\Phi_{i}$. Since $\Phi$ has $k$ blocks and each block contains one $1$, it follows that $|f_{i}| = k$ where $f_{i}$ is a $k-$ tuple on the set $X=\{1,2,\ldots,n\}$. Since $\Phi$ has $M$ columns, we have $M$ such $k-$tuples. Let $f_{i}=(f_{i_1}, f_{i_2}, \ldots,f_{i_k})$ be the $k-$ tuples. Now decompose this $k-$tuple into $k-$number of two tuples as $(l,f_{i_{l}})$, where $l$ denotes the $l^{th}$ block position and $f_{i_{l}}$ denotes the $l^{th}$ entry of $f_{i}$. It is to be noted here that $1 \leq l \leq k, 1 \leq f_{i_{l}} \leq n$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection{Construction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %From the $k-$ tuple $f_{i}=(f_{i_1}, f_{i_2}, \ldots,f_{i_k}),$ we form a binary vector of length $n \times k$ where $1$ occurrs in the positions $(l-1).n+f_{i_l}$ for $l= 1,2,....,k$ and rest of the positions are zeros (the vector is nothing but $\Phi_{i}$ )  and then we replace $1$ with $(-1)$ if $l>f_{i_{l}}$, which results in a vector consisting of $0,1,-1$ as entries. As we have $M$ such $k-$tuples, we get $M$ number of ternary vectors of length $n \times k$. This way, we get a ternary matrix $\Phi'_{m\times M}$ of size same as that of $\Phi_{m\times M}$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\par Let $(0\; 1\; 0\; 0\; 0\; 1\; 1\; 0\; 0)^{T}$ be a column from a matrix having $3$ blocks and each block is of size $3$. Then the support of this column is the $3-$ tuple $(2\; 3\; 1)$. Break this $3$- tuple into three $2$- tuples $(1\;2), (2\;3), (3\;1)$ as we mentioned above.  Now in the 3rd block as $1$ occurs in the 1st position, we replace $1$ with $-1$ in the 3rd block of the binary vector  $(0\; 1\; 0\; 0\; 0\; 1\; 1\; 0\; 0)^{T}$ to generate the ternary vector $(0\; 1\; 0\; 0\; 0\; 1\; (-1)\; 0\; 0)^{T}$.  
%
%\noindent \textbf{Remark-5:} The coherence and density of the ternary matrix $\Phi'$ remain same as that of the binary matrix $\Phi$. \\
%\par As in the case of binary CS matrices, it is possible to construct ternary matrices of general row size as well, which is concluded as the following theorem:
%\begin{theorem}
%Suppose $m$ is any positive integer different from $p, p^2, pq$ for distinct primes $p,q$. Then there exists a ternary CS matrix of row size $m$. 
%\end{theorem}
%\begin{proof} 
%Initially we construct a binary matrix of row size $m$, which is discussed in Section 4.  Then we use methodology in section 5.1  to obtain a ternary matrix of row size $m$.
%\end{proof}
%\subsection{Another way to construct ternary matrix:}
%In this section, we present another deterministic construction procedure of ternary matrix by combining binary and hadamard matrix . We show that the resulting matrix has same properties as binary but with better aspect ratio. Let $\Psi_{m \times M}$ be a binary sensing  matrix having $k$ number of one's in each column and the overlap between any two columns is $r$. Suppose there exist a hadamard matrix $H$ of size $(k+r')$ for some $r' \in { \{0,\dots, r\}}$. Now to get a ternary CS matrix $\Phi$,  for each column of $\Psi$ we replace each of
%its $1$-valued entries with a distinct row of $H$. So the size of the matrix $\Phi$ becomes $m \times M(k+r')$. As the rows of hadamard matrix $H$ are orthogonal, the rows of $\Phi$ are orthogonal. By the construction it is very easy to check that the coherence of the matrix $\Phi$ is $\frac{r}{k}$. The density of the matrix $\Phi$ is $\frac{k}{m}$.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 \begin{thebibliography}{99}
\bibitem{adcock_2013}
 B. Adcock, A. Hansen, C. Poon and B. Roman, ``Breaking the coherence barrier: A new theory for compressed sensing" arXiv:1302.0561v3, 2013.

\bibitem{apple_2009}
 L. Applebauma, S. D. Howardb, S. Searlec and R. Calderbank, ``Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery," Appl.
Comput. Harmon. Anal., 283-290, Mar. 2009.

%\bibitem{Iwen_2009}
 %M. A. Iwen, ``Simple deterministically constructible RIP matrices with sublinear fourier sampling requirements," in Proc. 43rd Ann. Conf. Information Sciences and Systems, Baltimore, MD, USA, 870-875, 2009.
 

\bibitem{amni_2012}
  A. Amni, V. Montazerhodjat and F. Marvasti, ``Matrices with small coherence using p-ary Block Codes, " IEEE Trans. Sig. Proc., vol. 60, no. 1, pp. 172-181, Jan. 2012.
	\bibitem{amini_2011}
  A. Amini and F. Marvasti, ``Deterministic construction of binary, bipolar and ternary compressed sensing matrices," IEEE Trans. Inf. Theory, vol. 57, 2360-2370, 2011.

\bibitem{Richard_2008}
   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.

\bibitem{bryant_2014}
D. Bryant and P. Cathain, ``An asymptotic existence result on compressed sensing matrices" ,arXiv:1403.2807v1, 2014.


\bibitem{bourgain_2011}
   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.

\bibitem{Bruckstein_2009}	
	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.
	
\bibitem{can_2008}
   E. Candes, ``The restricted isometry property and its implications for compressed sensing," Comptes Rendus Mathematique,
Vol. 346, pp. 589-592, 2008.


\bibitem{Candes_2005}
  E. Candes and T. Tao, ``Decoding by linear programming," IEEE Trans. Inform. Theory 51, 42-4215, 2005.
	
	\bibitem{candes_2008}
E. Candes and M.B. Wakin, ``An introduction to Compressive sampling," Signal Processing Magazine, pp:21-30, March 2008.	

	
\bibitem{Tao_2006}
   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.

\bibitem{CS_2013}
   Y. C. Chen, C. S. Sastry, V. M. Patel, P. J. Phillips, R. Chellappa. ,``In-Plane Rotation and Scale Invariant Clustering Using Dictionaries,"
IEEE Tans. Image Processing, vol. 22, No. 6, pp.2166-2180, 2013.

\bibitem{dai_2009}
  W. Dai and O. Milenkovic, ``Subspace pursuit for compressive sensing signal reconstruction," IEEE Trans. Inf. Theory, vol. 55, 2230-2249, 2009.
  
   
\bibitem{Ronald_2007}
   Ronald A. DeVore, ``Deterministic constructions of compressed sensing matrices," Journal of Complexity, Volume 23,pp 918-925, 2007.

\bibitem{dima_2012}
 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.


\bibitem{Donoho_2006}
   D. Donoho, ``Compressed Sensing," IEEE Trans. Information Theory, 52, pp 1289-1306, 2006.
	
	\bibitem{mixon_2014}
 Dustin G. Mixon,``Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck" arXiv:1403.3427v1, 2014.

\bibitem{mixon_2012}
M. Fickus, D. G. Mixon and J. C. Tremain, ``Steiner equiangular tight frames", Linear Algebra Appl., 436(5):1014-1027, 2012.
	   
\bibitem{Garnaev_1984}
   A. Garnaev and E. Gluskin, ``The widths of a Euclidean ball," Dokl. Akad. Nauk USSR 277 (1984),
1048 1052; English transl. in Soviet Math. Dokl. 30, 200-204, 1984.  
    
\bibitem{gil_2010}
A. Gilbert and P. Indyk, ``Sparse recovery using sparsematrices," Proc. IEEE, vol. 98, no. 6, pp. 937-947, 2010.  


\bibitem{ind_2008}
   P. Indyk, ``Explicit constructions for compressed sensing of sparse signals," in Proc. ACM-SIAM Symp. Discrete Algorithms, pp. 30-33, 2008.
 	\bibitem{li_2012}
  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.
%\bibitem{lu_2012}
   %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.
   
\bibitem{Kashin_1978}
   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.


\bibitem{Kashin_2007}
B.S. Kashin and V.N. Temlyakov, ``A remark on compressed sensing," Matematicheskie Zametki, Vol. 82, No. 6, pp. 829–837, 2007.

	
\bibitem{Chand_2014}
  R. Prasad, C. R. Murthy, and B. D. Rao, ``Joint Approximately Sparse Channel Estimation and Data Detection in OFDM Systems using Sparse Bayesian Learning," IEEE Transactions on Sig. Proc., Vol. 62, no. 14, pp. 3591-3603, 2014.

	\bibitem{Lura_2013}
 L. Rebollo-Neira and J. Bowley,   ``Sparse representation of astronomical images," Journal of the Optical Society of America A, 30 (4), pp. 758-768, 2013.

\bibitem{troop_2010}
 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.	
 
\bibitem{trop_2007}
  J. Tropp and A.C. Gilbert, ``Signal recovery from partial information via orthogonal matching pursuit," IEEE Trans. Inf. Theory, vol. 53, 4655-4666, 2007.

  
\end{thebibliography}
\end{document}

%%
%% End of file `elsarticle-template-harv.tex'.

1503.01402.extracted_bib
{adcock_2013 B. Adcock, A. Hansen, C. Poon and B. Roman, ``Breaking the coherence barrier: A new theory for compressed sensing" arXiv:1302.0561v3, 2013.
1503.01402.extracted_bib
{apple_2009 L. Applebauma, S. D. Howardb, S. Searlec and R. Calderbank, ``Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery," Appl. Comput. Harmon. Anal., 283-290, Mar. 2009. %
1503.01402.extracted_bib
{Iwen_2009 %M. A. Iwen, ``Simple deterministically constructible RIP matrices with sublinear fourier sampling requirements," in Proc. 43rd Ann. Conf. Information Sciences and Systems, Baltimore, MD, USA, 870-875, 2009.
1503.01402.extracted_bib
{amni_2012 A. Amni, V. Montazerhodjat and F. Marvasti, ``Matrices with small coherence using p-ary Block Codes, " IEEE Trans. Sig. Proc., vol. 60, no. 1, pp. 172-181, Jan. 2012.
1503.01402.extracted_bib
{amini_2011 A. Amini and F. Marvasti, ``Deterministic construction of binary, bipolar and ternary compressed sensing matrices," IEEE Trans. Inf. Theory, vol. 57, 2360-2370, 2011.
1503.01402.extracted_bib
{Richard_2008 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.
1503.01402.extracted_bib
{bryant_2014 D. Bryant and P. Cathain, ``An asymptotic existence result on compressed sensing matrices" ,arXiv:1403.2807v1, 2014.
1503.01402.extracted_bib
{bourgain_2011 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.
1503.01402.extracted_bib
{Bruckstein_2009 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.
1503.01402.extracted_bib
{can_2008 E. Candes, ``The restricted isometry property and its implications for compressed sensing," Comptes Rendus Mathematique, Vol. 346, pp. 589-592, 2008.
1503.01402.extracted_bib
{Candes_2005 E. Candes and T. Tao, ``Decoding by linear programming," IEEE Trans. Inform. Theory 51, 42-4215, 2005.
1503.01402.extracted_bib
{candes_2008 E. Candes and M.B. Wakin, ``An introduction to Compressive sampling," Signal Processing Magazine, pp:21-30, March 2008.
1503.01402.extracted_bib
{Tao_2006 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.
1503.01402.extracted_bib
{CS_2013 Y. C. Chen, C. S. Sastry, V. M. Patel, P. J. Phillips, R. Chellappa. ,``In-Plane Rotation and Scale Invariant Clustering Using Dictionaries," IEEE Tans. Image Processing, vol. 22, No. 6, pp.2166-2180, 2013.
1503.01402.extracted_bib
{dai_2009 W. Dai and O. Milenkovic, ``Subspace pursuit for compressive sensing signal reconstruction," IEEE Trans. Inf. Theory, vol. 55, 2230-2249, 2009.
1503.01402.extracted_bib
{Ronald_2007 Ronald A. DeVore, ``Deterministic constructions of compressed sensing matrices," Journal of Complexity, Volume 23,pp 918-925, 2007.
1503.01402.extracted_bib
{dima_2012 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.
1503.01402.extracted_bib
{Donoho_2006 D. Donoho, ``Compressed Sensing," IEEE Trans. Information Theory, 52, pp 1289-1306, 2006.
1503.01402.extracted_bib
{mixon_2014 Dustin G. Mixon,``Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck" arXiv:1403.3427v1, 2014.
1503.01402.extracted_bib
{mixon_2012 M. Fickus, D. G. Mixon and J. C. Tremain, ``Steiner equiangular tight frames", Linear Algebra Appl., 436(5):1014-1027, 2012.
1503.01402.extracted_bib
{Garnaev_1984 A. Garnaev and E. Gluskin, ``The widths of a Euclidean ball," Dokl. Akad. Nauk USSR 277 (1984), 1048 1052; English transl. in Soviet Math. Dokl. 30, 200-204, 1984.
1503.01402.extracted_bib
{gil_2010 A. Gilbert and P. Indyk, ``Sparse recovery using sparsematrices," Proc. IEEE, vol. 98, no. 6, pp. 937-947, 2010.
1503.01402.extracted_bib
{ind_2008 P. Indyk, ``Explicit constructions for compressed sensing of sparse signals," in Proc. ACM-SIAM Symp. Discrete Algorithms, pp. 30-33, 2008.
1503.01402.extracted_bib
{li_2012 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. %
1503.01402.extracted_bib
{lu_2012 %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.
1503.01402.extracted_bib
{Kashin_1978 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.
1503.01402.extracted_bib
{Kashin_2007 B.S. Kashin and V.N. Temlyakov, ``A remark on compressed sensing," Matematicheskie Zametki, Vol. 82, No. 6, pp. 829–837, 2007.
1503.01402.extracted_bib
{Chand_2014 R. Prasad, C. R. Murthy, and B. D. Rao, ``Joint Approximately Sparse Channel Estimation and Data Detection in OFDM Systems using Sparse Bayesian Learning," IEEE Transactions on Sig. Proc., Vol. 62, no. 14, pp. 3591-3603, 2014.
1503.01402.extracted_bib
{Lura_2013 L. Rebollo-Neira and J. Bowley, ``Sparse representation of astronomical images," Journal of the Optical Society of America A, 30 (4), pp. 758-768, 2013.
1503.01402.extracted_bib
{troop_2010 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.
1503.01402.extracted_bib
{trop_2007 J. Tropp and A.C. Gilbert, ``Signal recovery from partial information via orthogonal matching pursuit," IEEE Trans. Inf. Theory, vol. 53, 4655-4666, 2007.