{'fraction_non_alphanumeric': 0.04910401647785788, 'fraction_numerical': 0.015942327497425336, 'mean_word_length': 4.136690647482014, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 3, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Estimate Exchange over Network is Good for Distributed Hard Thresholding Pursuit

We investigate an existing distributed algorithm for learning sparse signals or data over networks. The algorithm is iterative and exchanges intermediate estimates of a sparse signal over a network. This learning strategy using exchange of intermediate estimates over the network requires a limited communication overhead for information transmission. Our objective in this article is to show that the strategy is good for learning in spite of limited communication. In pursuit of this objective, we first provide a restricted isometry property (RIP)-based theoretical analysis on convergence of the iterative algorithm. Then, using simulations, we show that the algorithm provides competitive performance in learning sparse signals vis-a-vis an existing alternate distributed algorithm. The alternate distributed algorithm exchanges more information including observations and system parameters.


I. INTRODUCTION
The topic of estimating and/or learning of sparse signals has many applications, such as machine learning [1], [2], multimedia processing [3], compressive sensing [4], wireless communications [5], just to mention a few. Here we consider a distributed sparse learning problem. Consider a network consisting of L nodes with a network matrix H ∈ R L×L describing the connections among the nodes. The (l, r)'th element h lr of H specifies the weight of the link from node r to node l. A zero valued h lr signifies the absence of a direct link from node r to node l. In the literature, H is also known as a network policy matrix. Let x ∈ R N be the underlying sparse signal to estimate/learn. Further assume that node l has the observation Here e l is the error term and A l ∈ R M l ×N is the system matrix (a sensing matrix or dictionary, depending on a particular application) at node l. For distributed learning, the nodes of a network exchange various information, for example, intermediate estimates of x, observations y l , system matrices A l , or their parameters. Using such information, a distributed algorithm learns x at each node over iterations. Few important aspects of a distributed algorithm are scalability with the number of nodes, low computational requirements at each node, and limited communication between nodes. These aspects are required to realize a large distributed system with many nodes and high-dimensional system matrices. To comply with the low computational aspect, we focus on greedy algorithms. Standard greedy algorithms, such as orthogonal matching pursuit [6], subspace pursuit [7], CoSaMP [8], and their variants [9], [10] are of low computational load and fast in execution. Further, for limited communication aspect, we prefer that intermediate estimates of x are exchanged over the network. Therefore we focus on developing distributed greedy sparse learning algorithms that exchange intermediate estimates of x or relevant parameters over network. Relevant past works in this direction are [11], [12], [13] where we proposed some rules for information exchange over network and developed new greedy algorithms for various signal models.
In this current article, we investigate an existing distributed greedy algorithm in the literature [14]. Our interest is to analyze performance of the algorithm. We do not propose any new rule or new algorithm. The existing algorithm of [14] exchanges intermediate estimates of x between the nodes of the network. We refer to this algorithm as the distributed hard thresholding pursuit (DHTP). DHTP has not received due attention in [14] -minor simulation results were reported and no theoretical analysis was performed. For the DHTP, our main objective is to show that estimate-exchange is a good strategy for achieving a good learning performance. In pursuit of this objective, we provide theoretical analysis and extensive simulation results. Using simulations, we show that there is no significant incentive in performance gain due to exchange of observations y l and system matrices A l . Exchange of intermediate estimates over network is good and that helps in communication and computation constrained scenarios.

A. Literature survey
We provide a literature survey for the problem of sparse learning over network. For this problem, learning by consensus is a popular strategy. A consensus strategy achieves estimates that are all the same at network nodes after convergence. That means ∀l,x l =x, wherex l denotes the signal estimate at node l at convergence of a distributed sparse learning algorithm. Using a greedy learning approach, a consensus seeking algorithm was recently proposed in [14]. This algorithm is referred to as the distributed hard thresholding (DiHaT). To achieve consensus, the DiHaT exchanges intermediate estimates of x, observations y l and system matrices A l . Furthermore, DiHaT uses a consensus seeking network matrix H with special properties; DiHaT requires that H be a doubly stochastic matrix. Here consensus seeking means that each and every node have estimates that are same at convergence. Alternatively, without seeking consensus, there exist several greedy sparse learning algorithms. DHTP of [14] is one example. Other examples include algorithms from [15], [16], [12], [17], [18].
For distributed sparse learning, there exist several convex optimization based algorithms, mainly in the application area of distributed compressed sensing [19], [20]. Some of the algorithms provide a centralized solution using a distributed convex optimization algorithm called the alternatingdirection-method-of-multipliers (ADMM) [21]. ADMM based distributed learning algorithms were proposed in [22], [23]. Specifically, the ADMM based method of [23] is called D-LASSO. It is worth mentioning that the D-LASSO is shown to provide a slower convergence compared to greedy DiHaT in [14]. Using adaptive signal processing techniques such as gradient search, distributed sparse learning and sparse regression were realized in [24], [25], [26]. These adaptive algorithms typically use a mean-square-error cost averaged over all the nodes in a network to find an optimal solution via gradient search. Distributed learning and regression are then performed via diffusion of information over a network and adaptation in all individual nodes. Using a Bayesian framework for finding the posterior with sparsity promoting priors, a distributedmessage-passing based method was proposed in [27] and a sparse Bayesian learning based method was proposed in [28]. Further, to promote sparsity in solutions, distributed system learning such as distributed dictionary learning was also considered in [29], [30]. Next, we mention that there exist several signal models in the literature where sparse signals are not the same for all nodes of a network. For example, denoting the signal at node l by x l , supports of x l are the same in [17], [31], [32], [33], but not their signal values; further, x l have common and private support and/or signal parts in [34], [12], [18]. In this article, we consider the setup (1) where ∀l, x l = x.

B. Contributions
Our objective is to show that signal estimate exchange is good for distributed sparse learning. There is no need to exchange y l and A l . In pursuit of this objective, we investigate DHTP and our contributions are as follows.
1) We provide a restricted-isometry-property (RIP) based theoretical analysis and convergence guarantee for DHTP. For error-free condition, that means ∀l, e l = 0, learned estimates at all nodes converge to the true signal x under some technical conditions. 2) Using simulations, we show instances where DHTP provides better learning performance than DiHaT. For a fair comparison, we evaluate practical performance using doubly stochastic H matrix. 3) We show that DHTP performs good for a general network matrix, not necessarily a doubly stochastic matrix.

C. Notation
. .] ⊤ is defined as T = {i : x i = 0}. We use |T | and T c to denote the cardinality and complement of the set T , respectively. For a matrix A ∈ R M×N , a sub-matrix A T ∈ R M×|T | consists of the columns of A indexed by i ∈ T . Similarly, for x ∈ R N , a sub-vector x T ∈ R |T | is composed of the components Algorithm 1 Distributed HTP -at node l Input: y l , A l , s, {h lr } Initialization: k ← 0;x l,k ← 0 (Estimate at k'th iteration) Iteration: repeat k ← k + 1 (Iteration counter) until stopping criterion Output:x l ,T l of x indexed by i ∈ T . Also we denote (.) ⊤ and (.) † as transpose and pseudo-inverse, respectively. We define the function supp(x, s) {the set of indices corresponding to the s largest amplitude components of x}. We usex l,k to denote the signal estimate at node l and iteration k.

II. DHTP ALGORITHM AND THEORETICAL ANALYSIS
The pseudo-code of the DHTP algorithm is shown in Algorithm 1. In every iteration k, the nodes use standard algorithmic steps of Hard Thresholding Pursuit algorithm (HTP) [35] along-with an extra step to include information about the estimates at the neighbors to refine the local estimate (see Step 3 of Algorithm 1). Here, we denote the neighborhood of node l by N l , i.e. N l {r : h lr = 0}. For theoretical analysis, we use the standard definition of RIP of a matrix as given in [36]. We denote the s-Restricted Isometry Constant (RIC) of a matrix by δ s . We use . and . 0 to denote the standard ℓ 2 and ℓ 0 norm of a vector, respectively. Throughout the paper unless specified, we have the following assumptions.
Assumption 1: The network matrix H is a right stochastic matrix. This assumption is quite general as any non-negative matrix can be reduced to a right stochastic matrix by appropriately scaling the rows of the matrix. Assumption 2: The sparsity level of the signal x, denoted by s x 0 is known a-priori. This assumption is used in the greedy algorithms such as CoSaMP [8], subspace pursuit [7], HTP [35], etc.
We first provide a recurrence inequality for DHTP, which provides performance bounds of the algorithm over iterations. For notational clarity, we define RIC constant where δ as (A l ) is the RIC of A l and a is a positive integer such as 1, 2 or 3.
Theorem 1 (Recurrence inequality): The performance of the DHTP algorithm at iteration k can be bounded as Detailed proof of the above theorem is shown in Section V. We use some intermediate steps in the proof of theorem 1 for addressing convergence of DHTP. We show convergence by two alternative approaches, in the following two theorems.
Theorem 2 (Convergence): Let x * j denote the magnitude of the j'th highest amplitude element of x and e max max l e l . If δ 3s < 1/3 and e max ≤ γx * s , then the DHTP algorithm converges afterk = cs iterations, and its performance is bounded by 1−δ3s and γ < 1 are positive constants in terms of δ 3s . Under the above conditions, estimated support sets across all nodes are equal to the correct support set, that means For an interpretation of the above theorem, we provide a numerical example. If δ 3s ≤ 0.2 then we have c ≤ 5, d ≤ 4.47; for an appropriate γ such that e max ≤ γx * s , the performance x −x l,k is upper bounded by 4.47 e max after 5s iterations.
Corollary 1: Consider the special case of a doubly stochastic network matrix H. Under the same conditions stated in Theorem 2, we have This upper bound is tighter than the bound of Theorem 2.
Theorem 3 (Convergence): If δ 3s < 1/3 and iterations, DHTP algorithm converges and its performance is bounded by A relevant numerical example for interpretation of Theorem 3 is as follows: if δ 3s ≤ 0.2 and x e max = 20 dB, then we havek = 9 and d = 13.68. The proofs of the theorems and corollary are presented in Section V.
It can be seen that the DHTP algorithm has a convergence guarantee when δ 3s < 1/3. Note that the requirement on signal-to-noise relation x e max > 1 in Theorem 3 is weaker than the requirement e max ≤ γx * s in Theorem 2. The above results can be readily extended to the noiseless case, that means ∀l, e l = 0. For the noiseless case, DHTP provides the exact estimate of the sparse signal x at every node.

A. Similarities and differences between DHTP and DiHaT
The DiHaT algorithm of [14] is shown in Algorithm 2. Comparing with Algorithm 1, the similarities and differences between DHTP and DiHaT are given in the list below.
until stopping criterion Output:x l ,T l 2) DiHaT requires H to be a doubly stochastic matrix. This is not a requirement for the case of DHTP. 3) For theoretical convergence proof of DiHaT, an assumption is that the average noise over nodes 1 L l e l → 0.
On the other hand, DHTP requires a signal-to-noise-ratio term x e max > 1.

4) DenotingĀ
DiHaT provides consensus in the sense of achieving same estimation at all nodes under certain technical conditions. DHTP does not provide consensus except in the noiseless case under certain technical conditions. 6) DiHaT requires all A l to be of the same size. DHTP does not require this condition, that means dimension of y l can vary across nodes. This is an important advantage in practical scenarios.

III. SIMULATION RESULTS
In this section, we study the practical performance of DHTP using simulations and compare with DiHaT (Algorithm 2). We perform the study using Monte-Carlo simulations over many instances of A l , x, and e l in the system model (1). The nonzero scalars of sparse signal are i.i.d. Gaussian. This is referred to as a Gaussian sparse signal. We set the number of nodes L = 20, and every node in the network is randomly connected to three other nodes apart from itself. The stopping criterion for the algorithms is that the maximum allowable number of iterations equal to 30. We used both right stochastic and doubly stochastic H in simulations. Given an edge matrix of network connection between nodes, a right stochastic matrix generation is a simple task. The doubly stochastic matrix is generated through the second largest eigenvalue modulus (SLEM) optimization problem [37]. Finally, we also show performance for real image data.

A. Performance measures
For performance evaluation, we used a mean signalto-estimation-noise ratio (mSENR) metric, mSENR = To generate noisy observations, we used Gaussian noise. The signal-to-noise ratio (SNR), SNR = SNR l = E{ x 2 } E{ e l 2 } is considered to be the same across all nodes.

B. Experiments using Simulated Data
We use all A l that have same row size, that is, ∀l, M l = M . Same row size is necessary to use DiHaT for comparison.
For the experiments, we set M = 100, and signal dimension N = 500. In our first experiment, we compare DHTP, DiHaT and HTP for right stochastic and doubly stochastic H. The H matrices are shown in the appendix. We set sparsity level s = 20. The results are shown in Fig. 1 where we show mSENR versus SNR. We recall that DiHaT was not designed for right stochastic H and HTP is a standalone algorithm that does not use the network. For right stochastic H, we observe from Fig. 1 (a) that DiHaT does not provide considerable gain over HTP, but DHTP does. On the other hand, for doubly stochastic H, we observe from Fig. 1 (b) that DiHaT provides a considerable gain over HTP, but DHTP outperforms DiHaT. The experiment validates that DHTP works for right stochastic H. We did experiments with many instances of H, and noted similar trend in performance.
Next, we study the probability of perfect signal estimation under a no-noise condition. Under this condition, the probability of perfect signal estimation is equivalent to the probability of perfect support-set estimation (PSE) at all nodes. Keeping M = 100 and N = 500 fixed, we vary the value of s and compute the probability of PSE using the frequentist approach -how many times PSE occurred. We used the same doubly stochastic H of the first experiment. The result is shown in Fig. 2. It can be seen that the DHTP outperforms DiHaT in the sense of phase transition from perfect to imperfect estimation.
In the third experiment, we observe convergence speed of algorithms. A fast convergence leads to less usage of communication and computational resources, and less time delay in learning. We set s = 20. The results are shown in Fig. 3 where we show mSENR versus the number of iterations, for the noiseless condition and 30 dB SNR. We note that the DHTP has a significantly quicker convergence. In our experiments, the DHTP achieved convergence typically within five iterations.
Finally, we experiment to find the sensitivity of the DHTP and the DiHaT algorithms to the prior knowledge of sparsity level. For this, we use 30 dB SNR and s = 20. Fig. 4 shows the results for different assumed s that varies as s = 18, 20, 25, and 30. We observe that DHTP performs better than DiHaT for all assumed sparsity levels. Also, a typical trend is that the assumption of higher sparsity level is always better than lower sparsity level.

C. Experiments for real data
We evaluate the performance on three standard grayscale images: Peppers, Lena and Baboon of size 512 × 512 pixels. We consider 11% of highest magnitude DCT coefficients of an image to decide a sparsity level choice. In DCT domain, the signal is split into 256 equal parts (or blocks) for ease of computation. This leads to the value of s for each part as close to 120. We perform reconstruction of the original images using the DHTP, DiHaT and HTP algorithms over the doubly stochastic network matrix H chosen in the previous subsection. The performance measure is the peak-signal-tonoise-ratio (PSNR), defined as PSNR = x−x 2 , where . ∞ denotes the ℓ ∞ norm. We show performance for a randomly chosen node among the set of 20 nodes. Fig. 5 shows a plot of the PSNR versus number of observations at each node (M ). In the same figure, we also show visual reconstruction quality (reconstructed image) at M = 240 for DHTP. We observe that DHTP has a better convergence rate and PSNR performance than the other two algorithms.

D. Reproducible research
In the spirit of reproducible research, we provide relevant Matlab codes at www.ee.kth.se/reproducible/ and the link https://sites.google.com/site/saikatchatt/softwares. The code produces the results shown in the figures.

IV. CONCLUSION
For sparse learning over a network using distributed greedy algorithms such as the hard thresholding approach, we show that the strategy of exchanging signal estimates between nodes is good for learning. This has an explicit advantage of low communication overhead. We show that appropriate algorithmic strategies work for right stochastic network matrices. Use of right stochastic network matrices has higher generality than the popularly used doubly stochastic network matrices.

A. Useful Lemmas
We provide three lemmas here that will be used in the proofs later. The first lemma provides a bound for the orthogonal projection operation used in DHTP.
The next lemma gives a useful inequality on squares of polynomials commonly encountered in the proofs.
The last lemma provides a bound for the energy content in the pruned indices. Lemma 3: [11, Lemma 3] Consider two vectors x and z with x 0 = s 1 , z 0 = s 2 and s 2 ≥ s 1 . We have S 1 supp(x, s 1 ) and S 2 supp(z, s 2 ). Let S ∇ denote the set of indices of the s 2 − s 1 smallest magnitude elements in z. Then,

B. Proof of Theorem 1
At Step 2, using Lemma 1, we have where (a) follows from the construction ofx l,k . Following the proof of [35, Theorem 3.8], we can write, Substituting the above equation in (2) , we have where where (a) follows as r∈N l h lr = 1 and (b) follows from the fact that h lr is non-negative. Now, we bound the performance over the pruning step in steps 4-5 as follows, where (a) follows from the triangle inequality and (b) follows from the fact thatx l,k is the best s-size approximation tox l,k . Combining (4), (5) and (6), we get Summing the above equation ∀l and denoting w l = r h rl , we get the result of Theorem 1.

C. Proof of Theorem 2
Let π be the permutation of indices of x such that |x π(j) |= In other words, x * is sorted x in the descending order of magnitude. Assuming π({1, 2, . . . , p}) ⊆T l,k1 , we need to find the condition such that π ({1, 2, . . . , p + q}) ⊆T l,k2 where k 2 > k 1 . First, we have the following corollary. Proof The first part of the proof of this lemma is similar to the proof of [39,Lemma 3]. It is enough to prove that the s highest magnitude indices of x l,k−1 + A ⊤ l (y l − A lxl,k−1 ) contains the indices π(j) for j ∈ {1, 2, . . . , p + q}. Mathematically, we need to prove, min j∈{1,2,...,p+q} The LHS of (7) can be written as where (a) follows from the reverse triangle inequality. Similarly, the RHS of (7) can be written as Using the bounds on LHS and RHS, (7) simplifies to Let RHS of the sufficient condition at node l be denoted as RHS l . Then, where (a) follows from [38, and (b) follows from substituting (2), (5) and (6). At iteration k 2 , RHS l can be vectorized as Applying Corollary 2 repeatedly, we can write for k 1 < k 2 , where (a) follows from the assumption that for any l, xT c l,k 1 ≤ x * {p+1,...,s} and the right stochastic property of H. Now, it can be seen that the bound in (7) is satisfied when Next, we find the condition that π({1, 2, . . . , p + q}) ⊆T l,k in the following Lemma.
Mathematically, we need to prove, min j∈{1,2,...,p+q} The LHS of (8) can be written as where (a) and (b) follows from the fact that π({1, 2, . . . , p + q}) ⊂T l,k2 , ∀l. Similarly, the RHS of (8) can be bounded as Using the above two bounds, the condition (8) can now be written as Define the RHS of the required condition from (9) at node l as RHS l . Then, we can write the sufficient condition as From the above equation and (4), we can bound RHS l as where (a) follows from substituting (2), (5) and (6). At iteration k 2 , RHS l can be vectorized as Applying Corollary 2 repeatedly, we can write for k 1 < k 2 , where (a) follows from the assumption that for any l, xT c l,k 1 ≤ x * {p+1,...,s} and the right stochastic property of H. From the above bound on RHS, it can be easily seen that (9) is satisfied when Corollary 3: For δ 3s < 1, we have c 1 < c 3 . Therefore, the sufficient condition for Lemma 4 and Lemma 5 to hold is Next, the above corollary can be used to prove theorem 2 by similar steps as outlined in [39,Theorem 6]. In the proof, the number of iterations k i between different steps for our case should be defined as k i := log(16(c3/c1) 2 (|Qi|+|Qi+1|/2+...+|Qr|/2 r−i )) log(1/c 2 1 ) . All the variables in the above definition are defined in [39,Theorem 6] except c 1 , c 3 which are defined in this paper. With the above definition, the number of iterations is bounded ask = cs. The proof steps in [39,Theorem 6] require that c 1 < 1 which holds as δ 3s < 0.362. Note that the constant γ is defined as γ = 2 The constant d in the theorem statement can be derived as follows. From Step 2 of DHTP at node l, we have y l − A lxl,k ≤ y l − A l x = e l ≤ e max . This follows becauseT l,k = T . Next, we can write where (a) follows from (5), (6) and the last inequality follows from the fact that δ 2s < δ 3s and the right stochastic property of H.

D. Proof of Corollary 1
From Step 2 of DHTP, we have y−Axk . .x ⊤ L,k ] ⊤ and A = I L ⊗A. The first inequality follows becauseT l,k = T , ∀l.
Define H H ⊗ I L . Then, we have, where (a) follows from (6), and (b), (c) follows from the doubly stochastic property of H ( H = 1). Also, (d) follows from the RIP property of A. Further, we can write where the last inequality follows from the fact that δ 2s < δ 3s .

E. Proof of Theorem 3
We define, ∇T l,k { ∪ where (a) follows from the right stochastic property of H. Also, from Lemma 3, we have where (a) and (b) follows from the assumption that ∀l, x −x r,k−1 + d1 Using Lemma 2, the above equation can be simplified as . This equation can be vectorized as From the proof of Theorem 1, we have the following relation in vectorized form Applying the above relation repeatedly, and using the fact that c 1 < 1 (as δ 3s < 0.362), we can write (12) at the iterationk as where (a) follows from the fact that c 2 < c 1 , the initial condition, x −x l,0 = x , ∀l and the right stochastic property of H. We have also defined, x = [ x . . . x ] ⊤ . Substituting the value ofk in the above equation, we get