We propose a sensor placement method for spatio-temporal field estimation based on a kriged Kalman filter (KKF) using a network of static or mobile sensors. The developed framework dynamically designs the optimal constellation to place the sensors. We combine the estimation error (for the stationary as well as non-stationary component of the field) minimization problem with a sparsity-enforcing penalty to design the optimal sensor constellation in an economic manner. The developed sensor placement method can be directly used for a general class of covariance matrices (ill-conditioned or well-conditioned) modelling the spatial variability of the stationary component of the field, which acts as a correlated observation noise, while estimating the non-stationary component of the field. Finally, a KKF estimator is used to estimate the field using the measurements from the selected sensing locations. Numerical results are provided to exhibit the feasibility of the proposed dynamic sensor placement followed by the KKF estimation method.@en

Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochasticity in both the graph topology and the signal itself. To bridge this gap, we examine the statistical behavior of the two key filter types, finite impulse response and autoregressive moving average graph filters, when operating on random time-varying graph signals (or random graph processes) over random time-varying graphs. Our analysis shows that 1) in expectation, the filters behave as the same deterministic filters operating on a deterministic graph, being the expected graph, having as input signal a deterministic signal, being the expected signal, and 2) there are meaningful upper bounds for the variance of the filter output. We conclude this paper by proposing two novel ways of exploiting randomness to improve (joint graph-time) noise cancellation, as well as to reduce the computational complexity of graph filtering. As demonstrated by numerical results, these methods outperform the disjoint average and denoise algorithm and yield a (up to) four times complexity reduction, with a very little difference from the optimal solution.

@en

In wireless sensor networks, where energy is scarce, it is inefficient to have all nodes active because they consume a non-negligible amount of battery. In this paper we consider the problem of jointly selecting sensors, relays and links in a wireless sensor network where the active sensors need to communicate their measurements to one or multiple access points. Information messages are routed stochastically in order to capture the inherent reliability of the broadcast links via multiple hops, where the nodes may be acting as sensors or as relays. We aim at finding optimal sparse solutions where both, the consistency between the selected subset of sensors, relays and links, and the graph connectivity in the selected subnetwork are guaranteed. Furthermore, active nodes should ensure a network performance in a parameter estimation scenario. Two problems are studied: sensor and link selection; and sensor, relay and link selection. To solve such problems, we present tractable optimization formulations and propose two algorithms that satisfy the previous network requirements. We also explore an extension scenario: only link selection. Simulation results show the performance of the algorithms and illustrate how they provide a sparse solution, which not only saves energy but also guarantees the network requirements.

@en

One of the cornerstones of the field of signal processing on graphs are graph filters, direct analogs of classical filters, but intended for signals defined on graphs. This paper brings forth new insights on the distributed graph filtering problem. We design a family of autoregressive moving average (ARMA) recursions, which are able to approximate any desired graph frequency response, and give exact solutions for specific graph signal denoising and interpolation problems. The philosophy to design the ARMA coefficients independently from the underlying graph renders the ARMA graph filters suitable in static and, particularly, time-varying settings. The latter occur when the graph signal and/or graph topology are changing over time. We show that in case of a time-varying graph signal, our approach extends naturally to a two-dimensional filter, operating concurrently in the graph and regular time domain. We also derive the graph filter behavior, as well as sufficient conditions for filter stability when the graph and signal are time varying. The analytical and numerical results presented in this paper illustrate that ARMA graph filters are practically appealing for static and time-varying settings, as predicted by theoretical derivations.

@en

We develop algorithms that find and track the optimal solution trajectory of time-varying convex optimization problems that consist of local and network-related objectives. The algorithms are derived from the prediction-correction methodology, which corresponds to a strategy where the time-varying problem is sampled at discrete time instances, and then, a sequence is generated via alternatively executing predictions on how the optimizers at the next time sample are changing and corrections on how they actually have changed. Prediction is based on how the optimality conditions evolve in time, while correction is based on a gradient or Newton method, leading to decentralized prediction-correction gradient and decentralized prediction-correction Newton. We extend these methods to cases where the knowledge on how the optimization programs are changing in time is only approximate and propose decentralized approximate prediction-correction gradient and decentralized approximate prediction-correction Newton. Convergence properties of all the proposed methods are studied and empirical performance is shown on an application of a resource allocation problem in a wireless network. We observe that the proposed methods outperform existing running algorithms by orders of magnitude. The numerical results showcase a tradeoff between convergence accuracy, sampling period, and network communications.@en

Despite their widespread use for the analysis of graph data, current graph filters are designed for graph signals that do not change over time, and thus they cannot simultaneously process time and graph frequency content in an adequate manner. This work presents ARMA2D, an autoregressive moving average graph-temporal filter that captures jointly the signal variations over the graph and time. By its unique nature, this filter is able to achieve a separable 2-dimensional frequency response, making it possible to approximate the filtering specifications along both the graph and temporal frequency domains. Numerical results show that the proposed solution outperforms the state of the art graph filters when the graph signal is time-varying.@en

We develop sparsity-enforcing spatio-temporal sensor management methods for environmental field monitoring applications. Leveraging the space–time stationarity, an environmental field can be estimated with a desired spatio-temporal resolution based on recorded measurements. If the field is non-stationary, it can be monitored dynamically based on the collected measurements and predictions made through a state model, if known a priori. We develop algorithms to implement sparse sensing, i.e., sensing only the most informative locations in space and time for both spatio-temporally stationary and non-stationary field monitoring applications. The selected sensing locations form an underdetermined measurement model which can be used to estimate the field based on the prior knowledge regarding the space–time variability of the field. The task of locating the most informative sensing locations can be performed for both multiple snapshots and a single snapshot based on the availability of prior knowledge (space–time correlation and dynamics) regarding the field, available computing power and the application. Centralized sensor placement problems for the estimation of both stationary and non-stationary fields are formulated as relaxed convex optimization problems, constrained by static or dynamic performance criteria. Finally, an iterative sparsity-enhancing saddle point method is formulated to solve both of these sensor placement problems.@en

We have recently seen a surge of work on distributed graph filters, extending classical results to the graph setting. State of the art filters have however only been examined from a deterministic standpoint, ignoring the impact of stochasticity in the computation (e.g., temporal fluctuation of links) and input (e.g., the value of each node is a random process). Initiating the study of stochastic graph signal processing, this paper shows that a prominent class of graph filters, namely autoregressive moving average (ARMA) filters, are suitable for the stochastic setting. In particular, we prove that an ARMA filter that operates on a stochastic signal over a stochastic graph is equivalent, in the mean, to the same filter operating on the expected signal over the expected graph. We also characterize the variance of the output and we provide an upper bound for its average value among different nodes. Our results are validated by numerical simulations.@en

This paper considers unconstrained convex optimization problems with time-varying objective functions. We propose algorithms with a discrete time-sampling scheme to find and track the solution trajectory based on prediction and correction steps, while sampling the problem data at a constant rate of $1/h$, where $h$ is the sampling period. The prediction step is derived by analyzing the iso-residual dynamics of the optimality conditions. The correction step adjusts for the distance between the current prediction and the optimizer at each time step, and consists either of one or multiple gradient steps or Newton steps, which respectively correspond to the gradient trajectory tracking (GTT) or Newton trajectory tracking (NTT) algorithms. Under suitable conditions, we establish that the asymptotic error incurred by both proposed methods behaves as $O({h}^{2})$, and in some cases as $O({h}^{4})$, which outperforms the state-of-the-art error bound of $O(h)$ for correction-only methods in the gradient-correction step. Moreover, when the characteristics of the objective function variation are not available, we propose approximate gradient and Newton tracking algorithms (AGT and ANT, respectively) that still attain these asymptotical error bounds. Numerical simulations demonstrate the practical utility of the proposed methods and that they improve upon existing techniques by several orders of magnitude.

@en

We introduce DeNT, a decentralized Newton-based tracking algorithm that solves and track the solution trajectory of continuously varying networked convex optimization problems. DeNT is derived from the prediction-correction methodology, by which the time-varying optimization problem is sampled at discrete time instances and then a sequence is generated via alternatively executing predictions on how the optimizers are changing and corrections on how they actually have changed. Prediction is based on the sample dynamics of the optimality conditions, while correction is based on a Newton method. After presenting DeNT, we show how it can be implemented in a decentralized way and analyze its convergence. We extend it to cases in which the knowledge on how the optimization programs are changing in time is only approximate, proposing DeANT. We then present an application to a resource allocation problem in a wireless network, demonstrating the proposed method outperforms existing methods by orders of magnitude, and exhibits a trade-off between convergence accuracy, sampling interval, and network communications.@en

Dual decomposition has been successfully employed in a variety of distributed convex optimization problems solved by a network of computing and communicating nodes. Often, when the cost function is separable but the constraints are coupled, the dual decomposition scheme involves local parallel subgradient calculations and a global subgradient update performed by a master node. In this paper, we propose a consensus-based dual decomposition to remove the need for such a master node and still enable the computing nodes to generate an approximate dual solution for the underlying convex optimization problem. In addition, we provide a primal recovery mechanism to allow the nodes to have access to approximate near-optimal primal solutions. Our scheme is based on a constant stepsize choice, and the dual and primal objective convergence are achieved up to a bounded error floor dependent on the stepsize and on the number of consensus steps among the nodes.@en

We introduce the concept of autoregressive moving average (ARMA) filters on a graph and show how they can be implemented in a distributed fashion. Our graph filter design philosophy is independent of the particular graph, meaning that the filter coefficients are derived irrespective of the graph. In contrast to finite-impulse response (FIR) graph filters, ARMA graph filters are robust against changes in the signal and/or graph. In addition, when time-varying signals are considered, we prove that the proposed graph filters behave as ARMA filters in the graph domain and, depending on the implementation, as first or higher order ARMA filters in the time domain.@en