1,721,050 research outputs found
Topological signal processing: Making sense of data building on multiway relations
No full textUncovering hidden relations in complex data sets is a key step to making sense of the data, which is a hot topic in our era of data deluge. Graph-based representations are examples of tools able to encode relations in a mathematical structure enabling the uncovering of patterns like clusters and paths. However, graphs only capture pairwise relations encoded in the presence of edges, but there are many forms of interaction that cannot be reduced to pairwise relations. To overcome the limitations of graph-based representations, it is necessary to incorporate multiway relations. In this article, we exploit tools from algebraic topology to handle multiway relations. Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study a topological space, that is, a set of points, along with a set of neighborhoods. More specifically, we illustrate topological signal processing (TSP), a framework encompassing a class of methods for analyzing signals defined over a topological space. Given its generality, TSP incorporates graph signal processing (GSP) as a particular case. After motivating the use of topological and geometrical methods for detecting patterns in the data, we present the signal processing tools based on algebraic topology and then illustrate their advantages with respect to graph-based methodology
Distributed detection and estimation in wireless sensor networks
No full textWireless sensor networks (WSNs) are becoming more and more a pervasive tool to monitor a wide range of physical phenomena. The opportunities arising from the many potential applications raise a series of technical challenges coupled with implementation constraints, such as energy supply, latency and vulnerability. The need for an efficient design of a WSN requires a strict interplay between the sensing and communication phases. In this article, we provide an overview of various distributed detection and estimation algorithms, incorporating the constraints imposed by the communication channel and the application requirements. We consider both cases where sensing is distributed, but the decision is centralized, and the case where the decision itself is totally decentralized. Specific attention is devoted to achieve globally optimal results through the interaction of nearby nodes only. We show how the topology of the network plays a significant role in the performance of the distributed algorithms, in terms of energy expenditure and latency. Then, we show how to optimize the network topology in order to minimize energy consumption or to match the graph describing the statistical dependencies among the variables observed by the nodes
Distributed estimation and control of algebraic connectivity over random graphs
No full textIn this paper, we propose a distributed algorithm for the estimation and control of the connectivity of ad-hoc networks in the presence of a random topology. First, given a generic random graph, we introduce a novel stochastic power iteration method that allows each node to estimate and track the algebraic connectivity of the underlying expected graph. Using results from stochastic approximation theory, we prove that the proposed method converges almost surely (a.s.) to the desired value of connectivity even in the presence of imperfect communication scenarios. The estimation strategy is then used as a basic tool to adapt the power transmitted by each node of a wireless network, in order to maximize the network connectivity in the presence of realistic medium access control (MAC) protocols or simply to drive the connectivity toward a desired target value. Numerical results corroborate our theoretical findings, thus illustrating the main features of the algorithm and its robustness to fluctuations of the network graph due to the presence of random link failures
Sampling and Recovery of Graph Signals
No full textThe aim of this chapter is to give an overview of the recent advances related to sampling and recovery of signals defined over graphs. First, we illustrate the conditions for perfect recovery of bandlimited graph signals from samples collected over a selected set of vertices. Then, we describe some sampling design criteria proposed in the literature to mitigate the effect of noise and model mismatching when performing graph signal recovery. Finally, we illustrate algorithms and optimal sampling strategies for adaptive recovery and tracking of dynamic graph signals, where both sampling set and signal values are allowed to vary with time. Numerical simulations carried out over both synthetic and real data illustrate the potential advantages of graph signal processing methods for sampling, interpolation, and tracking of signals observed over irregular domains such as, e.g., technological or biological networks
Enabling prediction via multi-layer graph inference and sampling
No full textIn this work we propose a novel method to efficiently predict dynamic signals over both space and time, exploiting the theory of sampling and recovery of band-limited graph signals. The approach hinges on a multi-layer graph topology, where each layer refers to a spatial map of points where the signal is observed at a given time, whereas different layers pertain to different time instants. Then, a dynamic learning method is employed to infer space-time relationships among data in order to find a band-limited representation of the observed signal over the multi-layer graph. Such a parsimonious representation is then instrumental to use sampling theory over graphs to predict the value of the signal on a future layer, based on the observations over the past graphs. The method is then tested on a real data-set, which contains the outgoing cellular data traffic over the city of Milan. Numerical simulations illustrate how the proposed approach is very efficient in predicting the calls activity over a grid of nodes at a given daily hour, based on the observations of previous traffic activity over both space and time
Joint optimization of radio and computational resources for multicell mobile cloud computing
No full textWe consider a MIMO multicell system wherein several Mobile Users (MUs) ask for computation offloading to a common cloud server through their femto-access points. We formulate the computation offloading problem as a joint optimization of the radio resources the transmit precoding matrices of the MUs and the computational resources the CPU cycles/second assigned by the cloud to each MU in order to minimize the overall users' energy consumption while meeting the latency constraints imposed by the applications running on the MUs. The resulting optimization problem is nonconvex (in the objective function and the constraints), and there are constraints coupling all the optimization variables. To cope with the nonconvexity, we hinge on successive convex approximation techniques and propose an iterative algorithm converging to a local optimal solution of the original nonconvex problem. The algorithm is also suitable for a parallel implementation across the access point, with limited coordination/signaling with the cloud. Numerical results show that the proposed joint optimization yields significant energy savings with respect to more traditional schemes performing a separate optimization of the radio and computational resources
Online learning of time-varying signals and graphs
No full textThe aim of this paper is to propose a method for online learning of time-varying graphs from noisy observations of smooth graph signals collected over the vertices. Starting from an initial graph, and assuming that the topology can undergo the perturbation of a small percentage of edges over time, the method is able to track the graph evolution by exploiting a small perturbation analysis of the Laplacian matrix eigendecomposition, while assuming that the graph signal is bandlimited. The proposed method alternates between estimating the time-varying graph signal and recovering the dynamic graph topology. Numerical results corroborate the effectiveness of the proposed learning strategy in the joint online recovery of graph signal and topology
RIS-Aided Wireless Fingerprinting Localization Based on Multilayer Graph Representations
Full text linkThe aim of this paper is to propose a novel method for wireless fingerprinting localization empowered by reconfigurable intelligent surfaces (RISs), exploiting the flexibility offered by RIS configuration control, and coping with the possible lack of received signal strength information (RSSI) at certain locations. The proposed approach hinges on a graph-based radio map interpolation method, which encodes similarities between model-generated RSSI, collected across spatial and fingerprints domains through the topology of a multi-layer graph. Numerical results illustrate the advantages of the proposed approach with respect to previous methods, in terms of both radio map recovery and accuracy of wireless localization
Learning from signals defined over simplicity complexes
No full textIn the last years, several new tools have been devised to analyze signals defined over the vertices of a graph, i.e., over a discrete domain whose structure is described by pairwise relations. In this paper, we expand these tools to the analysis of signals defined on simplicial complexes, whose domain has a structure specified by various multi-way relations. Within this framework, we show how to filter signals and how to reconstruct edge and vertex signals from a subset of observations. Finally, we propose two alternative algorithms to infer the structure of the simplicial complex from the observations
Distributed mobile cloud computing. joint optimization of radio and computational resources
No full textWe consider a scenario composed by multiple mobile users asking for computation offloading of their applications to a set of cloud servers. A set of radio access points, small cell base stations possibly coexisting with macro base stations, are available to provide radio proximity access to fixed computational resources. Our objective is to find the optimal assignment of each mobile user to a cloud server through the most convenient base station and, contextually, the optimal MIMO precoding matrices and computational rates (virtual machines) to each user, under latency constraints dictated by the users Quality of Experience (QoE). The radio resources assigned to users belonging to the same cell are orthogonal to each other, whereas users of different cells might interfere against each other. The latency constraint imposes a strict relationship between the time spent for transferring the program execution from the mobile device to the fixed server (and viceversa) and the time needed to execute the computation. To properly exploit this relationship, we formulate the computation offloading problem as a joint optimization of the radio and computational resources, with the objective of minimizing the overall energy consumption, at the mobile terminal side, while meeting the latency constraints. The resulting optimization problem is nonconvex in both the objective function and in the constraints. Nevertheless, by hinging on successive convex approximation techniques, we propose an iterative algorithm able to converge to a local optimal solution of the original nonconvex problem
- …
