{'fraction_non_alphanumeric': 0.03839131757784765, 'fraction_numerical': 0.00791155289583122, 'mean_word_length': 4.483592880978866, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Near-Optimal Distributed Estimation for a Network of Sensing Units Operating Under Communication Constraints

We study the problem of distributed state estimation in a network of sensing units that can exchange their measurements but the rate of communication between the units is constrained. The units collect noisy, possibly only partial observations of the unknown state; they are assisted by a relay center which can communicate at a higher rate and schedules the exchange of measurements between the units. We consider the task of minimizing the total mean-square estimation error of the network while promoting balance between the individual units' performances. This problem is formulated as the maximization of a monotone objective function subject to a cardinality constraint. By leveraging the notion of weak submodularity, we develop an efficient greedy algorithm for the proposed formulation and show that the greedy algorithm achieves a constant factor approximation of the optimal objective. Our extensive simulation studies illustrate the efficacy of the proposed formulation and the greedy algorithm.

in minimizing the total mean-square estimation error for the entire network while promoting balanced performance of the individual units.
The well-known sensor selection problem [3]- [8] can be thought of as a special instance of the described task. There, one is interested in the design of an optimal estimation scheme under communication constraints for a single unit (i.e., the fusion center) which collects sensor data. More specifically, due to various practical considerations and limitations on resources including computational and communication constraints, the fusion center typically aggregates information by querying only a small subset of the available sensors. Since finding an optimal solution to the sensor selection problem is NP-hard, state-of-the-art sensor selection algorithms attempt to find an approximate solution in an iterative fashion by leveraging a greedy heuristic. For instance, [5]- [7] consider a greedy algorithm for the log det maximization formulation of the sensor selection problem. Since the log det of the Fisher information matrix is a monotone submodular function [9], the greedy scheme developed in [5]- [7] is a (1 − 1/e)-approximation algorithm. A randomized greedy approach proposed in [8] leverages the weak submodularity of the mean-square error (MSE) objective in the sensor selection problem. Greedy sensor selection solvers are employed in various related problems in control systems, signal processing, and machine learning. Examples include sensor selection for Kalman filtering [5], [7], [10], batch state estimation and stochastic process estimation [11], [12], minimal actuator placement [13], subset selection in machine learning [14], voltage control and meter placement in power networks [15], [16], and sensor scheduling in wireless sensor networks [6], [10]. None of these methods, nor the related distributed and consensus-based schemes in [17]- [19], are directly applicable for the setting that we consider: estimation in resource-constrained networks of sensing units with the goal of simultaneously minimizing the total MSE of the network while promoting balanced performance of the individual units.
In this paper, we address the above challenges by making the following key contributions: • We formulate the task of state estimation in a network of sensing units under a constraint on communication resources and a demand for balanced performance of the individual units as the problem of maximizing a monotone objective function subject to cardinality constraint. The cardinality constraint naturally captures the aforementioned communication constraint. The proposed objective function consists of two parts: the total MSE of the network and a regularizing term that promotes balanced performance of individual units. • We develop an efficient greedy algorithm for the proposed NP-hard formulation. By leveraging the notion of weak submodularity, we show that the greedy algorithm achieves a constant factor approximation of the optimal schedule. • In simulation studies, we illustrate that our proposed formulation promotes balanced performance of the individual units while minimizing the total MSE of the network.

A. Notation and preliminaries
First, we briefly summarize the notation used in the paper. Sets are denoted by calligraphic letters, [n] := {1, 2, . . . , n}, and |S| denotes the cardinality of set S. Bold capital letters are used to denote matrices while bold lowercase letters represent column vectors. A ij denotes the (i, j) entry of A, a j is the j th row of A, A S is a submatrix of A that contains rows indexed by the set S, and λ max (A) and λ min (A) are the largest and the smallest eigenvalues of A, respectively.
Finally, I n ∈ R n×n is the identity matrix.
Next, we overview some definitions that are essential in the development and analysis of the proposed framework.
for all subsets S ⊆ T ⊂ X and j ∈ X \T . The term f j (S) = f (S ∪ {j}) − f (S) is the marginal value of adding element j to set S. Furthermore, f is monotone if f (S) ≤ f (T ) for all S ⊆ T ⊆ X . Definition 2. The maximum element-wise curvature of a monotone non-decreasing function f is defined as The maximum element-wise curvature is a closely related concept to submodularility and essentially quantifies how close the set function is to being submodular. It is worth noting a set function f (S) is submodular if and only if its maximum element-wise curvature satisfies C f ≤ 1.

B. System model
We consider a fully connected distributed network of m nodes with sensing, communication, and processing capabilities. 1 The network also includes a relay node that schedules the exchange of information among the units, i.e., the relay node decides which information should be communicated from one unit to another. We assume that the communication among units is constrained but the channels between units 1 Throughout the paper, the words unit and node are used interchangeably. Also shown is a relay node R that schedules exchange of observations O i,j and O i,k to node i from nodes j and k, respectively. and the relay node have large bandwidth (e.g., the vehicle-tovehicle and vehicle-to-infrastructure communication settings, respectively [20]).
One can think of the described network as having an undirected graph structure, where edges and vertices represent the nodes and the connections among them, respectively. An example of such a network is illustrated in Fig. 1. There, the relay node R schedules exchange of observations O i,j and O i,k to node i from nodes j and k, respectively.
To model the dynamics of the underlying hidden state x ∈ R n , we assume a state-space model where A t ∈ R n×n is the state-transition matrix and w t ∈ R n is the zero-mean Gaussian state noise with covariance Q ∈ R n×n . We further assume that the state x t is uncorrelated with w t and the initial state x 0 is sampled from a Gaussian distribution, i.e., x 0 ∼ N (0, Σ x ).
The i th node in the network acquires partial noisy linear observations of the underlying state according to where i ∈ [m] and H i,t denotes the matrix that selects observable components of the underlying state. Let L i,t denote the set of noisy observations of the components of x t available to the i th node (i.e., the noisy observations collected by the vector y i,t ). Here, we do not make any assumptions on the structure of H i,t . 2 We assume that the observation noise n i,t ∈ R |Li,t| is spatially and temporally independent zero-mean Gaussian noise with covariance R i,t = σ 2 i I |Li,t| . Without communication, each node only uses its acquired local measurements and performs Kalman filtering to estimate the underlying state x t by minimizing the meansquared error of the linear least-mean square error (LLMSE) estimator. However, cooperation can greatly enhance the learning capabilities of the individual units as well as the entire network.
Let P Li,t be the filtered error covariance matrix of the i th agent at time t obtained by using only the local measurements Ł i,t . Then, is the prediction error covariance matrix. If the relay node R at time t allocates observations to node i, agent i receives the subset O i of the measurements from the agents selected by R. Let be the Fisher information matrix associated with the i th node that determines the prior information and confidence of the node i before receiving the partial observation set O i . The filtered error covariance matrix of the i th node will then be updated according to The global MSE of the network at time t is defined as the sum of the MSEs of the individual nodes. In particular, wherex i,t is the linear estimate of x t computed by the i th unit at time t. Since the MSE is equivalent to the trace of the filtered error covariance matrix, As stated in Section I, communication constraints limit the amount of information that can be exchanged among the nodes of the network at any given time step. More specifically, we assume that the subsets of partial observations {O i } m i=1 scheduled to be communicated to each agent should satisfy m i=1 |O i | ≤ K, where K denotes the total number of observations that are allowed to be exchanged among the nodes of the network. The relay node decides how to allocate measurements to individual nodes by solving the optimization problem A comparison of 7 to a (simpler) sensor selection problem reveals that finding the optimal solution to 7 is generally NP-hard. In addition to being computationally challenging, optimization 7 does not necessary lead to a solution that would promote balanced MSE performance of the individual units; this point is illustrated by the simulation results in Section V. To this end, we next add a regularization term to the objective function so as to promote balanced performance while still finding a near-optimal solution to the MSE estimation problem for the entire network.

III. PROMOTING BALANCED PERFORMANCE OF THE
The triplet (i, j, k) denotes that the k th measurement of node j is communicated to node i. The function f (S) is inversely related to the total MSE of the network. To arrive at a measurement exchange scheme that promotes balanced performance across the network units, we propose the optimization problem where is a regularization function and γ ≥ 0 denotes the regularization parameter that determines the significance of balancing with respect to the goal of minimizing the total MSE of the entire network. On one hand, when γ = 0 the relay node R attempts to find a schedule that results in the lowest total MSE while disregarding potential imbalance in performance of the individual units. On the other hand, when γ is relatively large, the exchange of information determined by R is such that the differences between the MSEs of individual sensing nodes in the network become as small as possible. Notation (i, −, −) ∈ S in 9 and 10 implies that it does not matter for g(S) which measurements are communicated to the i th node; instead, it is the number of communicated measurements that is used to promote balanced performance. Note that the proposed formulation 9 is an NP-hard combinatorial optimization problem, as it generalizes 7. However, as we show next, the proposed objective function u(S) = f (S)+γg(S) is monotone weak submodular, i.e., under some mild conditions it is characterized with a bounded maximum element-wise curvature. Hence, one can find an approximate solution to 9 using a greedy algorithm, as we state in the next section.
We proceed by providing two propositions to characterize the combinatorial properties of f (S) and g(S). For simplicity of the stated results, we assume that R i,t = σ 2 I |Li,t| , i.e., use the same measurement noise statistics for all sensing nodes of the network (a generalization is straightforward).
then it holds that Proof. Note that f (S) is the sum of the additive inverse of the MSE of the sensing nodes that receive partial observations. Let i be one such node. Theorem 1 in [8] states that if 1 then the maximum element-wise curvature of the additive inverse of the MSE of node i, C i , satisfies It is straightforward to see that the condition stated in 11 implies 13 and we have max i∈[m] C i ≤ (2 λ M λm ) 3 . Hence, definition of λ M , λ m , and f (S) yields C f ≤ max i∈[m] C i which in turn completes the proof.
Proposition 2. The set function g(S) is a monotone submodular function.
Proof. In order to prove the results, we first find the marginal gain g (i,−,−) (S) that in the following argument is denoted by g i (S) (with a slight abuse of notations for the sake of readability). By the definition of g(S) and the marginal gain, Since log(.) is a monotonically increasing function, |O i | ≥ 0, |Ł i | > 0, g i (S) > 0 and hence g(S) is monotone. We now prove the second part of the statement, i.e., submodularity of g(S). Specifically, we should prove that the marginal gain of adding (i, j, k) to S is greater than adding it to a larger set S ∪ {(i , j , k )} where (i, j, k) = (i , j , k ). Two cases might happen. First, assume that i = i . Then, (16) Now assume i = i . Then, (17) Combining 16 and 17 we conclude g i (S) ≥ g i (S ∪ {(i , j , k )}) which in turn implies submodularity.
By combining the results of Proposition 1 and Proposition 2, and by employing the matrix inversion lemma [21], we obtain the following theorem about the proposed objective function u(S).
Proof. First note that it clearly holds that u(∅) = f (∅) + γg(∅) = 0. Furthermore, since u(S) = f (S) + γg(S) is the sum of a monotone weak submodular and a submodular function, it is also monotone weak submodular and C u ≤ (2 λ M λm ) 3 . Finally, we introduce g (i,j,k) (S) in 15 and recursively find f (i,j,k) as where

IV. GREEDY EXCHANGE OF OBSERVATIONS
The analysis of combinatorial characteristics of the proposed utility set function reveals that the optimization problem in 9 is that of maximizing a monotone weak submodular set function subject to cardinality constraint. Therefore, in order to find a near-optimal scheduling of the observations Algorithm 1 Greedy Observation Distribution Scheduling 1: Input: P i,t−1 , H i,t , K, for i = 1, . . . , m. 2: Output: Subset S t ⊆ X with |S t | = K. 3: Initialize S t = ∅, F i,S = F i,t for i = 1, . . . , m. 4: for k = 1, . . . , K

5:
(i, j, k) = argmax (i ,j ,k ) / ∈St u (i ,j ,k ) (S t ). 6: exchange, we resort to their greedy selection. More specifically, at each time step t, the relay node observes the performances of the local nodes and calculates the marginal gain of the possible distribution patterns (i, j, k) using 18.
Then it adds the pattern yielding the highest marginal gain to the scheduling set S t and updates the performance records F i,S for each node using 20. After repeating this procedure K times, the relay node sends the instructions for the exchange of observations to the individual nodes.
The proposed method is formalized as Algorithm 1. Performance and complexity of the greedy algorithm are characterized by the following theoretical results.

V. SIMULATION RESULTS
In this section, we study the performance of the proposed algorithm in different scenarios. In particular, we simulate a fully connected network having 3 nodes, set the dimension of the state vector to n = 50, and assume that a relay node is given information about the observation matrices of the individual nodes. For the state-transition matrix of the linear dynamical system, we set A t = 0.8I n and randomly generate partial observation matrices H i,t . The observation patterns of the nodes vary with different runs; however, we preserve the rank of the matrices -in particular, rank(H 1,t ) = 21, rank(H 2,t ) = 37 and rank(H 3,t ) = 5. We assume a zeromean Gaussian process noise and a zero-mean Gaussian observation noise at individual nodes with covariance matrices Q = 0.2I n and R i,t = 0.05I n , respectively. We run 10 Monte-Carlo simulations and select time horizons for each run as T = 20.
We first consider the MSE performances of the individual nodes in the network under regularized (γ > 0) and non-regularized (γ = 0) settings. The total number of measurements that can be exchanged among the units is set to K = 40. The regularization coefficients are set to γ = 200 and γ = 0; the large difference between the regularization coeffcients will emphasize the effect of the balancing term on the individual node performance. In Fig. 2, we observe that the regularization term balances the individual node performances. We also observe that in the absence of regularization the nodes exhibit temporally rapidly varying MSE performance. This is primarily due to a deterministic nature of the greedy selection of the set of observations shared among the agents. In particular, when the regularization term is set to zero, at each time step the algorithm greedily schedules most of the observations to the node with the highest MSE. On the other hand, the nonzero regularization term ensures a temporally smoother and balanced MSE performances of the individual units.
To study the effect of the number of shared observations, we vary K from 20 to 100. We compare the total network MSE (the sum of individual MSEs) at the last time step of the regularized and non-regularized schemes in Fig. 3. We observe that the non-regularized scheme always yields a lower total MSE as compared to the regularized one; this is expected since it completely focused on minimization of the total MSE and ignores balance of the individual units performances. For K = 100, we observe that both networks essentially perform the same, which is expected due to sharing essentially all the observations in the network.
Finally, we investigate the effect of the regularization parameter γ on balancing the individual performances of the nodes in the network. We set K = 40 and vary γ for the regularized network from 0.1 to 100 with log-scale increments. We compare the sum of pairwise MSE distances of the nodes in the regularized and non-regularized networks in Fig 4. We observe that the use of higher regularization coefficients results in a more balanced performances between individual nodes.

VI. CONCLUSION
In this paper, we considered the task of distributed state estimation in a communication-constrained network of sensing units. The network consists of units with sensing and communication capabilities as well as a relay center that schedules the exchange of information in the network. In addition to minimizing the total mean-square error, a certain level of performance balancing is desired throughout the network. We formulated this task as that of maximizing a monotone objective function subject to cardinality constraint. The proposed objective function is the sum of two monotone set functions: the first function, that is weak submodular, is inversely related to the total MSE of the network while the second one is submodular and favors a schedule of observation exchange that promotes balanced performance of individual units. Since the proposed formulation is NPhard, we developed a simple greedy algorithm and theoreti-  cally analyzed its performance by deriving a constant factor approximation on its achievable utility as compared to the utility attained by the optimal schedule. Through a series of simulations, we demonstrated that the proposed formulation minimizes the total MSE of the network while balancing individual units performance. As part of the future work, we will extend the proposed framework to a network of potentially nonlinear dynamical systems with multiple relay centers and analyze its performance.