\section{Introduction}

\IEEEPARstart{C}{}{ompressed} sensing (\textsc{cs}\xspace)~\cite{Donoho:compressed_sensing,Candes:stable_signal_recovery} refers to a class of under-sampling problems, where the sampled (or measured) data is inherently sparse. 
A standard \textsc{cs}\xspace problem typically considers a single-sensor scenario, where the main task is reconstruction of a large-dimensional signal-vector from a small-dimensional measurement-vector by using a-priori knowledge that the signal is sparse in a known domain. 
Several \textsc{cs}\xspace reconstruction algorithms have been developed in the literature, for example convex optimization- \cite{Mota:distributed_basis_pursuit, Bazerque:distributed_spectrum_sensing} and Bayesian- \cite{Ji:bayesian_compressive_sensing, Donoho:message_passing_for_cs} algorithms. 
An important class of reconstruction algorithms is the greedy pursuits (\textsc{gp}\xspace)
which are popular to use for large \textsc{cs}\xspace problems due to a good trade-off between computational complexity and reconstruction performance. 
From a measurement vector, the \textsc{gp}\xspace algorithms use simple linear algebraic tools to estimate the underlying support-set of the sparse signal-vector followed by estimating associated signal values on the support-set. Here we mention that a good support-set estimation is an important engineering aspect for the \textsc{gp}\xspace algorithms. 
Considering support-set estimation strategy, \textsc{gp}\xspace algorithms can be categorized in two broad classes: sequential and parallel. Sequential strategy estimates a support-set by finding elements of the support-set one-by-one over iterations. On the other hand, parallel strategy estimates all elements of a support-set simultaneously in an iteration, but improves the support-set estimate over iterations. For example, the sequential types include matching pursuit \cite{Mallat:matching_pursuit_with_time_frequency_dictionaries}, orthogonal matching pursuit (\textsc{omp})~\cite{Tropp:signal_recovery}, and their algorithmic variations \cite{Donoho:sparse_solution_of_underdetermined_systems_stomp,Chatterjee:projection_based_look_ahead,Sundman:frogs,Needell:signal_recovery_from_incomplete_and_inaccurate_measurements_via_romp}. On the other hand, parallel types include \textsc{c}o\textsc{s}a\textsc{mp}\xspace \cite{Needell:cosamp}, subspace pursuit (\sp)~\cite{Dai:subspace_pursuit} and their algorithmic variations \cite{Sundman:look_ahead_parallel_pursuit}. 
For any \textsc{cs}\xspace reconstruction algorithm (convex optimization and \textsc{gp}\xspace), providing theoretical reconstruction guarantees with relevant system requirements is a desired feature.
\textsc{cs}\xspace for a single-sensor scenario including dynamic \textsc{cs}\xspace \cite{Vaswani_KF_CS_2008,Carmi_KF_CS_2010,Zachariah_Chatterjee_Jansson_TSP_2012} has been substantially investigated in literature.

{{In this paper, we consider a distributed (or de-centralized) \textsc{cs}\xspace (\textsc{dcs}\xspace) problem where many sensors measure correlated sparse signals and the sensors are connected via a network. 
The task in a \textsc{dcs}\xspace problem is reconstruction of correlated signals from the measurements collected in all sensor nodes.
\textsc{dcs}\xspace has a wide range of application areas, 
for example, distributed sensor perception~\cite{Yang:distributed_perception} and distributed spectrum estimation~\cite{Feng:distributed_compressive_spectrum_sensing, Bazeraque:distributed_spectrum_sensing,Ling:decenteralized_support_detection,Sundman:psd}. Algorithms for the \textsc{dcs}\xspace problem can be developed either in a central manner (by a fusion center) or distributed manner.
There are many centralized solutions, for example~\cite{Tropp:simultaneous_sparse_approx_part1,Rakotomamonjy:surveying,Leviatan:simultaneous,Cotter:sparse_solutions,Chen:theoretical_results_on_sparse,Sundman:greedy_pursuit_for_jointly} where measurements from all sensor nodes are collected in a central node and then the correlated sparse signals are reconstructed in the central node.
On the other hand, there are distributed algorithms where relevant information about correlations is exchanged over network and each sensor node reconstructs its own measured signal. Exchange of correlation information helps to improve quality of reconstruction in each sensor node.
A distributed algorithm is of high interest and we refer to such algorithms as \textsc{dcs}\xspace algorithms. \textsc{dcs}\xspace algorithms can be developed based on two principles: convex and \textsc{gp}\xspace.
There is a tangible effort in the literature~\cite{Mota:distributed_basis_pursuit,Bazeraque:distributed_spectrum_sensing,Feng:distributed_compressive_spectrum_sensing,Ling:decenteralized_support_detection} to develop convex optimization based \textsc{dcs}\xspace algorithms with theoretically proven convergence. The analytical tractability is due to use of convexity via implementation of distributed convex algorithms. 
For example, the work of~\cite{Mota:distributed_basis_pursuit} considered that a large measurement matrix in \textsc{cs}\xspace is divided into many senors measuring one single source and the proposed algorithm is a distributed implementation of alternating-direction-method-of-multipliers (ADMM) \cite{Boyd_ADMM_2011}.
On the other hand, we note a limited endeavor to develop \textsc{dcs}\xspace algorithms based on \textsc{gp}\xspace principles. In this regard, our earlier attempts are in \cite{Sundman:diprsp,Sundman:a_greedy_pursuit_algorithm,Sundman:distributed_gp_algorithms} and some attempts by others are in \cite{Wimalajeewa:cooperative,Zhang:side_information_based_omp}. 
Most of these earlier attempts (including all our earlier attempts) were made for designing algorithms that can provide
a reasonable practical performance, but lacks theoretical guarantees on reconstruction performance. The relevant questions are: (a) what are system and signal properties so that a distributed algorithm converges, and (b) what is the quality of reconstruction performance at convergence? In fact, to the best of authors' knowledge, no significant theoretical results are available in current literature for \textsc{dcs}\xspace algorithms based on \textsc{gp}\xspace principles.
Naturally the limited endeavor may be attributed to the lack of analytical tractability.}}

{{We develop a new \textsc{dcs}\xspace algorithm based on \textsc{gp}\xspace principles that provide a good practical performance and have theoretical reconstruction guarantees.
Noting the important role of support-set estimation in \textsc{gp}\xspace, sensor nodes exchange support set information over a network. 
For a signal model, we use the recent mixed support-set signal model of ~\cite{Sundman:a_greedy_pursuit_algorithm,Sundman:distributed_gp_algorithms} that considers correlation over support-sets of all underlying sparse signals in a \textsc{dcs}\xspace problem. The correlation is incorporated via existence of a partial common (or joint) support-set; the common support-set is a subset of all individual supports of all sparse signals. Using the mixed support set model and appropriate assumptions about system setup, our contributions in this paper are:
\begin{itemize}
 \item Development of a distributed \textsc{gp}\xspace algorithm.
 \item Analytical study of performance in the sense of provable reconstruction guarantees and convergence.
\end{itemize}
The new \textsc{dcs}\xspace algorithm is referred to as \emph{distributed parallel pursuit} (\ensuremath{\textsc{dipp}}\xspace) and it comprises of two main parts: data fusion and local \textsc{cs}\xspace reconstruction. The task of the fusion is to provide an estimation of the correlation (i.e., estimation of the common support-set) which in turn helps to improve quality of the local \textsc{cs}\xspace reconstruction.
For fusion, we use a democratic voting strategy. Typically a decision in voting strategy is made by majority counting (which may be considered a hard decision based approach), but the use of voting is motivated by simplicity and good performance to estimate the common support-set\footnote{We mention that a soft decision based approach does not suit well to estimate common support-set in our distributed setup where information about estimated support-sets for sensor nodes is exchanged over network.}.
The local \textsc{cs}\xspace reconstruction algorithm use the output from the fusion as side information to improve reconstruction performance.
Based on the parallel pursuit algorithm \sp of~\cite{Dai:subspace_pursuit}, we design a new algorithm that can use the side information. The new algorithm is called \ensuremath{\textsc{sipp}}\xspace (parallel pursuit with side information) and it is used as the local \textsc{cs}\xspace re-constructor. While we develop \ensuremath{\textsc{sipp}}\xspace by extending \sp, we could have used other parallel pursuit algorithms such as \textsc{c}o\textsc{s}a\textsc{mp}\xspace \cite{Needell:cosamp} instead of \sp. The choice of parallel pursuit is due to algorithmic ease of incorporating side information and analytical tractability\footnote{In our distributed \textsc{cs}\xspace setup we have found that the use of serial pursuit algorithms (such as \textsc{omp}\xspace) comes with significant hurdles in analytical tractability and hence we do not explore serial pursuit algorithms in this paper.}.}}

{{\ensuremath{\textsc{dipp}}\xspace works iteratively, where it improves the estimation of correlation by exchanging relevant information over the network.
Analysis of \ensuremath{\textsc{dipp}}\xspace is non-trivial. In the literature, for analysis of \textsc{cs}\xspace algorithms (or in general sparse representation problems), worst case analysis tools such as mutual-coherence and restricted-isometry-property (RIP) have been used \cite{Elad_book_2010}. The RIP was introduced in \cite{Candes:decoding_linear_programming} for analysis of convex optimization based \textsc{cs}\xspace algorithms and later used significantly for analyzing \textsc{gp}\xspace algorithms, such as \sp \cite{Dai:subspace_pursuit}. Instead of worst case approaches, average case analysis approaches such as replica method tools from statistical physics field \cite{Nishimori-2001} have been used for convex optimization based \textsc{cs}\xspace algorithms \cite{Rangan_Replica_CS_TIT_2012,Kabashima_Vehkapera_Chatterjee_2012,Vehkapera_Kabashima_Chatterjee_TIT_2014}, but there is no precedence to use them for analyzing \textsc{gp}\xspace algorithms due to analytical intractability.
Further, in worst case analysis tools, RIP is found to offer more analytical tractability than mutual-coherence and is recently in more use, such as analysis of \textsc{omp}\xspace \cite{Davenport_2010_Orthogonal_Matching_pursuit}, model based \textsc{cs}\xspace \cite{Baraniuk_Model_Based_CS_TIT_2010} and fusion framework where several \textsc{cs}\xspace algorithms are used jointly \cite{Ambat:facs,Ambat_Chatterjee_Hari_2013_CoMACS}.  
Therefore we decide to use RIP to analyze \ensuremath{\textsc{dipp}}\xspace. We show -- under certain theoretical requirements on the quality of information processing over network and RIP parameters of sensor nodes -- that the \ensuremath{\textsc{dipp}}\xspace algorithm converges to a performance level (convergence in theory). At convergence, the performance level is a scaled additive measurement noise power where the scaling coefficient is a function of RIP parameters and information processing quality parameters. That means, under those theoretical requirements, the algorithm provides exact reconstruction if the measurement noise is absent. In practice, the algorithm iterates until the quality of correlation estimation saturates (convergence in practice) -- this happens when further information exchange does not help to improve reconstruction performance. Using simulations, we show how practical reconstruction performance of \ensuremath{\textsc{dipp}}\xspace behaves with respect to change in number of measurements, signal-to-measurement-noise ratios and  network-connectivity conditions.}}


The remaining parts of the paper are organized as follows. In section~\ref{sec:setup}, we formally define the \textsc{dcs}\xspace problem, the signal model and network models. Section~\ref{sec:algorithm} deals with developing \ensuremath{\textsc{dipp}}\xspace. In section~\ref{sec:performance}, we derive performance bounds and reconstruction guarantees for \ensuremath{\textsc{dipp}}\xspace. Lastly, in section~\ref{sec:numerical}, we perform practical evaluation of the \ensuremath{\textsc{dipp}}\xspace algorithm by simulations.


\subsection{Notations and Preliminaries}
For enumerating sensor-nodes in the \textsc{dcs}\xspace setup, we will reserve sub-indices `$\ensuremath{\mathsf{p}}$', `$\ensuremath{\mathsf{q}}$' and `$\r$'. However, to keep the paper clean from notational clutter, we will only use these sub-indices when it is necessary for the discussion. We reserve sub-indices `$l$' and `$k$' for denoting iteration counter in inner- and outer loops, respectively. Typically, `$l$' associates with the iteration counter of \ensuremath{\textsc{sipp}}\xspace and `$k$' associates with \ensuremath{\textsc{dipp}}\xspace.

Calligraphic letters are used for sets; in particular $\mathcal{T}$, $\ensuremath{\mathcal{J}}$ and $\mathcal{I}$ denote support-sets while $\mathcal{L}$ is a set of sensor nodes. We denote the full support set, $\Omega \triangleq \{1, 2, \dots, N \}$. Using $\Omega$, we define the complement $\mathcal{T}^{\complement} \triangleq \Omega \setminus \mathcal{T}$. If an algorithm at node $\ensuremath{\mathsf{p}}$ estimates the support-set, this estimate is denoted by $\ensuremath{\hat{\mathcal{T}}_{\p}}$. $\mathbf{x}_{\mathcal{T}}$ may refer to two things; either $\mathbf{x}_{\mathcal{T}}$ may be the non-zero sub-vector of $\mathbf{x}$ (i.e., $\mathbf{x}_{\mathcal{T}} = \{ x_i : i \in \mathcal{T}\}$), or $\mathbf{x}_{\mathcal{T}}$ may be a zero-padded signal, where $\mathbf{x} \in \mathbb{R}^N$, $\mathbf{x}_{\mathcal{T}} \neq 0$ and $\mathbf{x}_{\mathcal{T}^{\complement}} = 0$. Which one of these referred to will be clear from the context. When nothing else is stated the norm used is by default the induced $\ell_2$-norm (i.e., spectral norm) $\| \cdot \| \triangleq \| \cdot \|_2$. We define the pseudo-inverse for a matrix $\mathbf{A}$ as $\mathbf{A}^{\dagger} \triangleq (\mathbf{A}^*\mathbf{A})^{-1}\mathbf{A}^*$ (where full column rank is assumed)
.

We now introduce some existing definitions and results for the standard \textsc{cs}\xspace setup, that we will later use for the \textsc{dcs}\xspace setup. In standard single-sensor \textsc{cs}\xspace:
\begin{align}
\mathbf{y} = \mathbf{A} \mathbf{x} + \mathbf{e}, \pgfkeysvalueof{/tikz/dsp/label}}{eqn:single_sensor_model}
\end{align}
where $\mathbf{x} \in \mathbb{R}^{N}$ is a sparse signal, $\mathbf{y} \in \mathbb{R}^{M}$ is a measurement vector, $\mathbf{A} \in \mathbb{R}^{M\times N}$ is a measurement matrix and $\mathbf{e} \in \mathbb{R}^{M}$ is a measurement noise, and $M<N$.
\begin{definition}[RIP: Restricted Isometry Property \cite{Candes:decoding_linear_programming}]\pgfkeysvalueof{/tikz/dsp/label}}{def:rip}
A matrix $\mathbf{A}$ satisfies the RIP with Restricted Isometry Constant (RIC) $\delta_T$ if
\begin{align}
  (1-\delta_T)\|\mathbf{x}\|^2 \leq \| \mathbf{A} \mathbf{x} \|^2 \leq (1+\delta_T) \|\mathbf{x}\|^2
\end{align}
holds for all $T$-sparse vectors $\mathbf{x}$ where $0 \leq \delta_T < 1$.
\end{definition}

\begin{proposition}[Proposition 3.1 in \cite{Needell:cosamp}]\pgfkeysvalueof{/tikz/dsp/label}}{prop:cosamp}
  Suppose $\mathbf{A}$ has RIC $\delta_T$. Let $\mathcal{T}$ be a set of $T$ indices or fewer. Then
  \begin{subequations}
    \begin{align}
      \left\| \mathbf{A}_{\mathcal{T}}^* \mathbf{y} \right\| & \leq \sqrt{1+\delta_T}\left\| \mathbf{y} \right\|, \pgfkeysvalueof{/tikz/dsp/label}}{prop3.1:1} \\
      \left\| \mathbf{A}_{\mathcal{T}}^{\dagger} \mathbf{y} \right\| & \leq \frac{1}{\sqrt{1-\delta_T}} \left\| \mathbf{y} \right\|, \pgfkeysvalueof{/tikz/dsp/label}}{prop3.1:3}  \\
      (1-\delta_T) \left\| \mathbf{x} \right\| & \leq \left\| \mathbf{A}_{\mathcal{T}}^* \mathbf{A}_{\mathcal{T}} \mathbf{x} \right\| \leq (1+\delta_T) \left\| \mathbf{x} \right\|, \pgfkeysvalueof{/tikz/dsp/label}}{prop3.1:4} \\
      \frac{1}{1+\delta_T}\left\| \mathbf{x} \right\|\leq & \left\| (\mathbf{A}_{\mathcal{T}}^* \mathbf{A}_{\mathcal{T}})^{-1} \mathbf{x} \right\| \leq \frac{1}{1-\delta_T}\left\| \mathbf{x} \right\|. \pgfkeysvalueof{/tikz/dsp/label}}{prop3.1:5}
    \end{align}
  \end{subequations}
\end{proposition}
{{Here we mention that $\mathbf{A}_{\mathcal{T}}^*$ and $\mathbf{A}_{\mathcal{T}}^{\dagger}$ should be interpreted as $(\mathbf{A}_{\mathcal{T}})^*$ and $(\mathbf{A}_{\mathcal{T}})^{\dagger}$.}}
\begin{proposition}[Approximate Orthogonality] \textit{Proposition 3.2 in \cite{Needell:cosamp}} \pgfkeysvalueof{/tikz/dsp/label}}{prop:approx_orthogonality}.
Suppose $\mathbf{A}$ has RIC $\delta_T$. Let $\S$ and $\mathcal{T}$ be disjoint sets of indices whose combined cardinality does not exceed $S+T$. Then
\begin{align}
  \| \mathbf{A}_{\S}^* \mathbf{A}_{\mathcal{T}} \| \leq \delta_{S+T}.
\end{align}
\end{proposition}
\begin{corollary}[Corollary 3.3 in \cite{Needell:cosamp}] \pgfkeysvalueof{/tikz/dsp/label}}{cor:approx_orthogonality}
Suppose $\mathbf{A}$   has RIC $\delta_T$. Let $\mathcal{T}$ be a set of indices, and let $\mathbf{x}$ be a vector. Provided that $T \geq |\mathcal{T} \cup \ensuremath{\texttt{supp}}(\mathbf{x})|$,
\begin{align}
  \| \mathbf{A}_{\mathcal{T}}^* \mathbf{A} \mathbf{x}_{\mathcal{T}^{\complement}} \| = \| \mathbf{A}_{\mathcal{T}}^* \mathbf{A}_{{\mathcal{T}}^{\complement}} \mathbf{x}_{{\mathcal{T}}^{\complement}} \| \leq \delta_T\| \mathbf{x}_{{\mathcal{T}}^{\complement}} \|.
\end{align}
\end{corollary}
\begin{lemma}\pgfkeysvalueof{/tikz/dsp/label}}{lemma:bound_complement} For the setup \eqref{eqn:single_sensor_model}, if $\hat{\mathcal{T}}$ is the estimate of the support-set of a signal $\mathbf{x}$ and $\hat{\mathbf{x}}$ is constructed by $\hat{\mathbf{x}}_{\hat{\mathcal{T}}} \leftarrow \mathbf{A}^{\dagger}_{\hat{\mathcal{T}}} \mathbf{y}$, $\hat{\mathbf{x}}_{\hat{\mathcal{T}}^{\complement}} \leftarrow \mathbf{0}$, then the following relation holds:
\begin{align}
 \| \mathbf{x} - \hat{\mathbf{x}} \| \leq \frac{1}{1-\delta_{3T}} \| \mathbf{x}_{\hat{\mathcal{T}}^c} \| + \frac{1}{\sqrt{1-\delta_{3T}}} \|  \mathbf{e} \|. \pgfkeysvalueof{/tikz/dsp/label}}{lemma:compl1}
\end{align}
We also have that
  \begin{align}
    \| \mathbf{x}_{\hat{\mathcal{T}}^c} \| \leq \| \mathbf{x} - \hat{\mathbf{x}}\|. \pgfkeysvalueof{/tikz/dsp/label}}{lemma:compl2}
  \end{align}
\begin{IEEEproof} 
See 
