Kernel-Based Inference of Functions Over Graphs
Abstract The study of networks has witnessed an explosive growth over the past decades with several ground-breaking methods introduced. A particularly interesting—and prevalent in several fields of study—problem is that of inferring a function defined over the nodes of a network. This work presents a versatile kernel-based framework for tackling this inference problem that naturally subsumes and generalizes the reconstruction approaches put forth recently for the signal processing by the community studying graphs. Both the static and the dynamic settings are considered along with effective modeling approaches for addressing real-world problems. The analytical discussion herein is complement…
Inference of Spatio-Temporal Functions over Graphs via Multi-Kernel Kriged Kalman Filtering
Inference of space-time varying signals on graphs emerges naturally in a plethora of network science related applications. A frequently encountered challenge pertains to reconstructing such dynamic processes, given their values over a subset of vertices and time instants. The present paper develops a graph-aware kernel-based kriged Kalman filter that accounts for the spatio-temporal variations, and offers efficient online reconstruction, even for dynamically evolving network topologies. The kernel-based learning framework bypasses the need for statistical information by capitalizing on the smoothness that graph signals exhibit with respect to the underlying graph. To address the challenge o…
Blind Radio Tomography
From the attenuation measurements collected by a network of spatially distributed sensors, radio tomography constructs spatial loss fields (SLFs) that quantify absorption of radiofrequency waves at each location. These SLFs can be used for interference prediction in (possibly cognitive) wireless communication networks, for environmental monitoring or intrusion detection in surveillance applications, for through-the-wall imaging, for survivor localization after earthquakes or fires, etc. The cornerstone of radio tomography is to model attenuation as the bidimensional integral of the SLF of interest scaled by a weight function. Unfortunately, existing approaches (i) rely on heuristic assumpti…
Inference of Spatiotemporal Processes over Graphs via Kernel Kriged Kalman Filtering
Inference of space-time signals evolving over graphs emerges naturally in a number of network science related applications. A frequently encountered challenge pertains to reconstructing such dynamic processes given their values over a subset of vertices and time instants. The present paper develops a graph-aware kernel-based kriged Kalman filtering approach that leverages the spatio-temporal dynamics to allow for efficient online reconstruction, while also coping with dynamically evolving network topologies. Laplacian kernels are employed to perform kriging over the graph when spatial second-order statistics are unknown, as is often the case. Numerical tests with synthetic and real data ill…
Randomized Block Frank–Wolfe for Convergent Large-Scale Learning
Owing to their low-complexity iterations, Frank-Wolfe (FW) solvers are well suited for various large-scale learning tasks. When block-separable constraints are present, randomized block FW (RB-FW) has been shown to further reduce complexity by updating only a fraction of coordinate blocks per iteration. To circumvent the limitations of existing methods, the present work develops step sizes for RB-FW that enable a flexible selection of the number of blocks to update per iteration while ensuring convergence and feasibility of the iterates. To this end, convergence rates of RB-FW are established through computational bounds on a primal sub-optimality measure and on the duality gap. The novel b…