We study the problem of computing deterministic optimal policies for constrained Markov decision processes (MDPs) with continuous state and action spaces, which are widely encountered in constrained dynamical systems. Designing deterministic policy gradient methods in continuous state and action spaces is particularly challenging due to the lack of enumerable state-action pairs and the adoption of deterministic policies, hindering the application of existing policy gradient methods for constrained MDPs. To this end, we develop a deterministic policy gradient primal-dual method to find an optimal deterministic policy with non-asymptotic convergence. Specifically, we leverage regularization of the Lagrangian of the constrained MDP to propose a deterministic policy gradient primal-dual (D-PGPD) algorithm that updates the deterministic policy via a quadratic-regularized gradient ascent step and the dual variable via a quadratic-regularized gradient descent step. We prove that the primal-dual iterates of D-PGPD converge at a sub-linear rate to an optimal regularized primal-dual pair. We instantiate D-PGPD with function approximation and prove that the primal-dual iterates of D-PGPD converge at a sub-linear rate to an optimal regularized primal-dual pair, up to a function approximation error. Furthermore, we demonstrate the effectiveness of our method in two continuous control problems: robot navigation and fluid control. To the best of our knowledge, this appears to be the first work that proposes a deterministic policy search method for continuous-space constrained MDPs.

Antimicrobial Resistance (AMR) poses a significant global public health challenge, necessitating early detection strategies to enable timely clinical interventions. Electronic Health Records (EHRs) offer extensive real-world clinical data but present challenges due to their irregularly sampled, heterogeneous, and multivariate temporal structure. This paper investigates graph-based learning models to predict AMR in Intensive Care Unit patients by systematically modeling spatial and temporal dependencies within EHR data represented as Multivariate Time Series. We propose and evaluate a novel Spatio-Temporal Graph Convolutional Neural Network architecture, demonstrating its superior predictive performance by achieving a Receiver Operating Characteristic Area Under the Curve of 80.00%, surpassing baseline models by approximately 6%. Furthermore, our analysis of the learned graph structures highlights critical clinical interactions, notably emphasizing catheterrelated variables as central nodes, aligning well with established clinical knowledge. By combining high predictive performance with enhanced interpretability, our approach presents a robust and transparent framework, well-suited for clinical applications aimed at improving AMR risk assessment and patient care management.

Graph learning is the fundamental task of estimating unknown graph connectivity from available data. Typical approaches assume that not only is all information available simultaneously but also that all nodes can be observed. However, in many real-world scenarios, data can neither be known completely nor obtained all at once. We present a novel method for online graph estimation that accounts for the presence of hidden nodes. We consider signals that are stationary on the underlying graph, which provides a model for the unknown connections to hidden nodes. We then formulate a convex optimization problem for graph learning from streaming, incomplete graph signals. We solve the proposed problem through an efficient proximal gradient algorithm that can run in real-time as data arrives sequentially. Additionally, we provide theoretical conditions under which our online algorithm is similar to batch-wise solutions. Through experimental results on synthetic and real-world data, we demonstrate the viability of our approach for online graph learning in the presence of missing observations.

This work presents a low-rank tensor model for multidimensional Markov chains. A common approach to simplify the dynamical behavior of a Markov chain is to impose low-rankness on the transition probability matrix. Inspired by the success of these matrix techniques, we present low-rank tensors for representing transition probabilities on multi-dimensional state spaces. Through tensor decomposition, we provide a connection between our method and classical probabilistic models. Moreover, our proposed model yields a parsimonious representation with fewer parameters than matrix-based approaches. Unlike these methods, which impose low-rankness uniformly across all states, our tensor method accounts for the multi-dimensionality of the state space. We also propose an optimization-based approach to estimate a Markov model as a low-rank tensor. Our optimization problem can be solved by the alternating direction method of multipliers (ADMM), which enjoys convergence to a stationary solution. We empirically demonstrate that our tensor model estimates Markov chains more efficiently than conventional techniques, requiring both fewer samples and parameters. We perform numerical simulations for both a synthetic low-rank Markov chain and a real-world example with New York City taxi data, showcasing the advantages of multi-dimensionality for modeling state spaces.

Graph neural networks (GNNs) have become a workhorse approach for learning from data defined over irregular domains, typically by implicitly assuming that the data structure is represented by a homophilic graph. However, recent works have revealed that many relevant applications involve heterophilic data where the performance of GNNs can be notably compromised. To address this challenge, we present a simple yet effective architecture designed to mitigate the limitations of the homophily assumption. The proposed architecture reinterprets the role of graph filters in convolutional GNNs, resulting in a more general architecture while incorporating a stronger inductive bias than GNNs based on filter banks. The proposed convolutional layer enhances the expressive capacity of the architecture enabling it to learn from both homophilic and heterophilic data and preventing the issue of oversmoothing. From a theoretical standpoint, we show that the proposed architecture is permutation equivariant. Finally, we show that the proposed GNNs compares favorably relative to several state-of-the-art baselines in both homophilic and heterophilic datasets, showcasing its promising potential.

This paper introduces a probabilistic approach for tracking the dynamics of unweighted and directed graphs using state-space models (SSMs). Unlike conventional topology inference methods that assume static graphs and generate point-wise estimates, our method accounts for dynamic changes in the network structure over time. We model the network at each timestep as the state of the SSM, and use observations to update beliefs that quantify the probability of the network being in a particular state. Then, by considering the dynamics of transition and observation models through the update and prediction steps, respectively, the proposed method can incorporate the information of real-time graph signals into the beliefs. These beliefs provide a probability distribution of the network at each timestep, being able to provide both an estimate for the network and the uncertainty it entails. Our approach is evaluated through experiments with synthetic and real-world networks. The results demonstrate that our method effectively estimates network states and accounts for the uncertainty in the data, outperforming traditional techniques such as recursive least squares.

Graphons, as limit objects of dense graph sequences, play a central role in the statistical analysis of network data. However, existing graphon estimation methods often struggle with scalability to large networks and resolution-independent approximation, due to their reliance on estimating latent variables or costly metrics such as the Gromov-Wasserstein distance. In this work, we propose a novel, scalable graphon estimator that directly recovers the graphon via moment matching, leveraging implicit neural representations (INRs). Our approach avoids latent variable modeling by training an INR--mapping coordinates to graphon values--to match empirical subgraph counts (i.e., moments) from observed graphs. This direct estimation mechanism yields a polynomial-time solution and crucially sidesteps the combinatorial complexity of Gromov-Wasserstein optimization. Building on foundational results, we establish a theoretical guarantee: when the observed subgraph motifs sufficiently represent those of the true graphon (a condition met with sufficiently large or numerous graph samples), the estimated graphon achieves a provable upper bound in cut distance from the ground truth. Additionally, we introduce MomentMixup, a data augmentation technique that performs mixup in the moment space to enhance graphon-based learning. Our graphon estimation method achieves strong empirical performance--demonstrating high accuracy on small graphs and superior computational efficiency on large graphs--outperforming state-of-the-art scalable estimators in 75\% of benchmark settings and matching them in the remaining cases. Furthermore, MomentMixup demonstrated improved graph classification accuracy on the majority of our benchmarks.

This article studies the trajectory planning problem of an autonomous vehicle for exploring a spatiotemporal field subject to a constraint on cumulative information. Since the resulting problem depends on the signal strength distribution of the field, which is unknown in practice, we advocate the use of a model-free reinforcement learning (RL) method to find the solution. Given the vehicle's dynamical model, a critical (and open) question is how to judiciously merge the model-based optimality conditions into the model-free RL framework for improved efficiency and generalization, for which this work provides some positive results. Specifically, we discretize the continuous action space by leveraging analytic optimality conditions for the minimum-time optimization problem via Pontryagin's minimum principle (PMP). This allows us to develop a novel discrete PMP-based RL trajectory planning algorithm, which learns a planning policy faster than those based on a continuous action space. Simulation results: 1) validate the effectiveness of the PMP-based RL algorithm and 2) demonstrate its advantages, in terms of both learning efficiency and the vehicle's exploration time, over two baseline methods for continuous control inputs.

We propose a novel algorithm for the support estimation of partially known Gaussian graphical models that incorporates prior information about the underlying graph. In contrast to classical approaches that provide a point estimate based on a maximum likelihood or maximum a posteriori approach using (simple) priors on the precision matrix, we consider a prior on the graph and rely on annealed Langevin diffusion to generate samples from the posterior distribution. Since the Langevin sampler requires access to the score function of the underlying graph prior, we use graph neural networks to effectively estimate the score from a graph dataset (either available beforehand or generated from a known distribution). Numerical experiments in different setups demonstrate the benefits of our approach.

Heart failure exacerbations (HFE) represent a critical challenge in healthcare due to their significant role in global mortality. The rise of home and wearable devices capable of monitoring cardiac conditions provides valuable opportunities for data-driven analysis and HFE detection. However, these devices frequently generate low-quality measurements with irregular sampling frequencies and high rates of missing data. Our paper presents a methodology that processes these measurements as a three-dimensional tensor, applying a low-rank tensor completion scheme to manage missing data effectively, thus facilitating anomaly detection without necessitating data imputation. We validate our method on a dataset from 4 patients with chronic HF in the compensation phase, collected at the Hospital Fondazione Policlinico Universitario Campus Bio-Medico in Rome, Italy. Our results demonstrate the tensor-based method’s superiority over traditional techniques, highlighting its potential for detecting anomalies within complex multivariate time series data. This research emphasizes the critical role of advanced data analysis in enhancing HFE identification, which could lead to improved patient care and reduced hospitalization rates.

Graphs are widely used to represent complex information and signal domains with irregular support. Typically, the underlying graph topology is unknown and must be estimated from the available data. Common approaches assume pairwise node interactions and infer the graph topology based on this premise. In contrast, our novel method not only unveils the graph topology but also identifies three-node interactions, referred to in the literature as second-order simplicial complexes (SCs). We model signals using a graph autoregressive Volterra framework, enhancing it with structured graph Volterra kernels to learn SCs. We propose a mathematical formulation for graph and SC inference, solving it through convex optimization involving group norms and mask matrices. Experimental results on synthetic and real-world data showcase a superior performance for our approach compared to existing methods.

The goal of reinforcement learning is estimating a policy that maps states to actions and maximizes the cumulative reward of a Markov Decision Process (MDP). This is oftentimes achieved by estimating first the optimal (reward) value function (VF) associated with each state-action pair. When the MDP has an infinite horizon, the optimal VFs and policies are stationary under mild conditions. However, in finite-horizon MDPs, the VFs (hence, the policies) vary with time. This poses a challenge since the number of VFs to estimate grows not only with the size of the state-action space but also with the time horizon. This paper proposes a non-parametric low-rank stochastic algorithm to approximate the VFs of finite-horizon MDPs. First, we represent the (unknown) VFs as a multi-dimensional array, or tensor, where time is one of the dimensions. Then, we use rewards sampled from the MDP to estimate the optimal VFs. More precisely, we use the (truncated) PARAFAC decomposition to design an online low-rank algorithm that recovers the entries of the tensor of VFs. The size of the low-rank PARAFAC model grows additively with respect to each of its dimensions, rendering our approach efficient, as demonstrated via numerical experiments.

Node features bolster graph-based learning when exploited jointly with network structure. However, a lack of nodal attributes is prevalent in graph data. We present a framework to recover completely missing node features for a set of graphs, where we only know the signals of a subset of graphs. Our approach incorporates prior information from both graph topology and existing nodal values. We demonstrate an example implementation of our framework where we assume that node features depend on local graph structure. Missing nodal values are estimated by aggregating known features from the most similar nodes. Similarity is measured through a node embedding space that preserves local topological features, which we train using a Graph AutoEncoder. We empirically show not only the accuracy of our feature estimation approach but also its value for downstream graph classification. Our success embarks on and implies the need to emphasize the relationship between node features and graph structure in graph-based learning.

Blind deconvolution over graphs involves using (observed) output graph signals to obtain both the inputs (sources) as well as the filter that drives (models) the graph diffusion process. This is an ill-posed problem that requires additional assumptions, such as the sources being sparse, to be solvable. This paper addresses the blind deconvolution problem in the presence of imperfect graph information, where the observed graph is a perturbed version of the (unknown) true graph. While not having perfect knowledge of the graph is arguably more the norm than the exception, the body of literature on this topic is relatively small. This is partly due to the fact that translating the uncertainty about the graph topology to standard graph signal processing tools (e.g. eigenvectors or polynomials of the graph) is a challenging endeavor. To address this limitation, we propose an optimization-based estimator that solves the blind identification in the vertex domain, aims at estimating the inverse of the generating filter, and accounts explicitly for additive graph perturbations. Preliminary numerical experiments showcase the effectiveness and potential of the proposed algorithm.

Interest in bilevel optimization has grown in recent years, partially due to its relevance for challenging machine-learning problems. Several exciting recent works have been centered around developing efficient gradient-based algorithms that can solve bilevel optimization problems with provable guarantees. However, the existing literature mainly focuses on bilevel problems either without constraints, or featuring only simple constraints that do not couple variables across the upper and lower levels, excluding a range of complex applications. Our paper studies this challenging but less explored scenario and develops a (fully) first-order algorithm, which we term BLOCC, to tackle BiLevel Optimization problems with Coupled Constraints. We establish rigorous convergence theory for the proposed algorithm and demonstrate its effectiveness on two well-known real-world applications - support vector machine (SVM) - based model training and infrastructure planning in transportation networks.

We propose estimating Gaussian graphical models (GGMs) that are fair with respect to sensitive nodal attributes. Many real-world models exhibit unfair discriminatory behavior due to biases in data. Such discrimination is known to be exacerbated when data is equipped with pairwise relationships encoded in a graph. Additionally, the effect of biased data on graphical models is largely underexplored. We thus introduce fairness for graphical models in the form of two bias metrics to promote balance in statistical similarities across nodal groups with different sensitive attributes. Leveraging these metrics, we present Fair GLASSO, a regularized graphical lasso approach to obtain sparse Gaussian precision matrices with unbiased statistical dependencies across groups. We also propose an efficient proximal gradient algorithm to obtain the estimates. Theoretically, we express the tradeoff between fair and accurate estimated precision matrices. Critically, this includes demonstrating when accuracy can be preserved in the presence of a fairness regularizer. On top of this, we study the complexity of Fair GLASSO and demonstrate that our algorithm enjoys a fast convergence rate. Our empirical validation includes synthetic and real-world simulations that illustrate the value and effectiveness of our proposed optimization problem and iterative algorithm.

Graphs have become pervasive tools to represent information and datasets with irregular support. However, in many cases, the underlying graph is either unavailable or naively obtained, calling for more advanced methods to its estimation. Indeed, graph topology inference methods that estimate the network structure from a set of signal observations have a long and well established history. By assuming that the observations are both Gaussian and stationary in the sought graph, this paper proposes a new scheme to learn the network from nodal observations. Consideration of graph stationarity overcomes some of the limitations of the classical Graphical Lasso algorithm, which is constrained to a more specific class of graphical models. On the other hand, Gaussianity allows us to regularize the estimation, requiring less samples than in existing graph stationarity-based approaches. While the resultant estimation (optimization) problem is more complex and non-convex, we design an alternating convex approach able to find a stationary solution. Numerical tests with synthetic and real data are presented, and the performance of our approach is compared with existing alternatives.

Estimating a policy that maps states to actions is a central problem in reinforcement learning. Traditionally, policies are inferred from the so called value functions (VFs), but exact VF computation suffers from the curse of dimensionality. Policy gradient (PG) methods bypass this by learning directly a parametric stochastic policy. Typically, the parameters of the policy are estimated using neural networks (NNs) tuned via stochastic gradient descent. However, finding adequate NN architectures can be challenging, and convergence issues are common as well. In this paper, we put forth low-rank matrix-based models to estimate efficiently the parameters of PG algorithms. We collect the parameters of the stochastic policy into a matrix, and then, we leverage matrix-completion techniques to promote (enforce) low rank. We demonstrate via numerical studies how low-rank matrix-based policy models reduce the computational and sample complexities relative to NN models, while achieving a similar aggregated reward.

Learning graphs from sets of nodal observations represents a prominent problem formally known as graph topology inference. However, current approaches are limited by typically focusing on inferring single networks, and they assume that observations from all nodes are available. First, many contemporary setups involve multiple related networks, and second, it is often the case that only a subset of nodes is observed while the rest remain hidden. Motivated by these facts, we introduce a joint graph topology inference method that models the influence of the hidden variables. Under the assumptions that the observed signals are stationary on the sought graphs and the graphs are closely related, the joint estimation of multiple networks allows us to exploit such relationships to improve the quality of the learned graphs. Moreover, we confront the challenging problem of modeling the influence of the hidden nodes to minimize their detrimental effect. To obtain an amenable approach, we take advantage of the particular structure of the setup at hand and leverage the similarity between the different graphs, which affects both the observed and the hidden nodes. To test the proposed method, numerical simulations over synthetic and real-world graphs are provided.

The (efficient and parsimonious) decomposition of higher-order tensors is a fundamental problem with numerous applications in a variety of fields. Several methods have been proposed in the literature to that end, with the Tucker and PARAFAC decompositions being the most prominent ones. Inspired by the latter, in this work we propose a multi-resolution low-rank tensor decomposition to describe (approximate) a tensor in a hierarchical fashion. The central idea of the decomposition is to recast the tensor into multiple lower-dimensional tensors to exploit the structure at different levels of resolution. The method is first explained, an alternating least squares algorithm is discussed, and preliminary simulations illustrating the potential practical relevance are provided.

Electronic health records provide rich, heterogeneous data about the evolution of the patients’ health status. However, such data need to be processed carefully, with the aim of extracting meaningful information for clinical decision support. In this paper, we leverage interpretable (deep) learning and signal processing tools to deal with multivariate time-series data collected from the Intensive Care Unit (ICU) of the University Hospital of Fuenlabrada (Madrid, Spain). The presence of antimicrobial multidrug-resistant (AMR) bacteria is one of the greatest threats to the health system in general and to the ICUs in particular due to the critical health status of the patients therein. Thus, early identification of bacteria at the ICU and early prediction of their antibiotic resistance are key for the patients’ prognosis. While intelligent data-based processing and learning schemes can contribute to this early prediction, their acceptance and deployment in the ICUs require the automatic schemes to be not only accurate but also understandable by clinicians. Accordingly, we have designed trustworthy intelligent models for the early prediction of AMR based on the combination of meaningful feature selection with interpretable recurrent neural networks. These models were created using irregularly sampled clinical measurements, both considering the health status of the patient and the global ICU environment. We explored several strategies to cope with strongly imbalance data, since only a few ICU patients are infected by AMR bacteria. It is worth noting that our approach exhibits a good balance between performance and interpretability, especially when considering the difficulty of the classification task at hand. A multitude of factors are involved in the emergence of AMR (several of them not fully understood), and the records only contain a subset of them. In addition, the limited number of patients, the imbalance between classes, and the irregularity of the data render the problem harder to solve. Our models are also enriched with SHAP post-hoc interpretability and validated by clinicians who considered model understandability and trustworthiness of paramount concern for pragmatic purposes. Moreover, we use linguistic fuzzy systems to provide clinicians with explanations in natural language. Such explanations are automatically generated from a pool of interpretable rules that describe the interaction among the most relevant features identified by SHAP. Notice that clinicians were especially satisfied with new insights provided by our models. Such insights helped them to trust the automatic schemes and use them to make (better) decisions to mitigate AMR spreading in the ICU. All in all, this work paves the way towards more comprehensible time-series analysis in the context of early AMR prediction in ICUs and reduces the time of detection of infectious diseases, opening the door to better hospital care.

Inferring graph structure from observations on the nodes is an important and popular network science task. Departing from the more common inference of a single graph, we study the problem of jointly inferring multiple graphs from the observation of signals at their nodes (graph signals), which are assumed to be stationary in the sought graphs. Graph stationarity implies that the mapping between the covariance of the signals and the sparse matrix representing the underlying graph is given by a matrix polynomial. A prominent example is that of Markov random fields, where the inverse of the covariance yields the sparse matrix of interest. From a modeling perspective, stationary graph signals can be used to model linear network processes evolving on a set of (not necessarily known) networks. Leveraging that matrix polynomials commute, a convex optimization method along with sufficient conditions that guarantee the recovery of the true graphs are provided when perfect covariance information is available. Particularly important from an empirical viewpoint, we provide high-probability bounds on the recovery error as a function of the number of signals observed and other key problem parameters. Numerical experiments demonstrate the effectiveness of the proposed method with perfect covariance information as well as its robustness in the noisy regime.

When approaching graph signal processing tasks, graphs are usually assumed to be perfectly known. However, in many practical applications, the observed (inferred) network is prone to perturbations which, if ignored, will hinder performance. Tailored to those setups, this paper presents a robust formulation for the problem of graph-filter identification from input-output observations. Different from existing works, our approach consists in addressing the robust identification by formulating a joint graph denoising and graph-filter identification problem. Such a problem is formulated as a non-convex optimization, suitable relaxations are proposed, and graph-stationarity assumptions are incorporated to enhance performance. Finally, numerical experiments with synthetic and real-world graphs are used to assess the proposed schemes and compare them with existing (robust) alternatives.

The COVID-19 pandemic presents unprecedented challenges to the healthcare systems around the world. In 2020, Spain was among the countries with the highest Intensive Care Unit (ICU) hospitalization and mortality rates. This work analyzes data of COVID-19 patients admitted to a Spanish ICU during the first wave of the pandemic. The patients in our study either died (deceased patients) or were discharged from the ICU (non-deceased patients) and underwent the following landmarks: beginning of symptoms; arrival at the emergency department; beginning of the hospital stay; and ICU admission. Our goal is to create a graph-based data-science methodology to find associations among patients' comorbidities, previous medication, symptoms, and the COVID-19 treatment, and to analyze their evolution across landmarks. Towards that end, we first perform a hypothesis test based on bootstrap to identify discriminative features among deceased and non-deceased patients. Then, we leverage graph-based representations and network analytics to determine pairwise associations and complex relations among clinical features. The descriptive statistical analysis confirms that deceased patients exhibit multiple comorbidities with stronger levels of association and are treated with a wider range of drugs during the ICU stay. We also observe that the most common treatment was the simultaneous administration of lopinavir/ritonavir with hydroxychloroquine, regardless of the patients' outcome. Our results illustrate how graph tools and representations yield insights on the relations among comorbidities, drug treatments, and patients' evolution. All in all, the approach puts forth a new data-analysis tool for clinicians that can be applied to analyze (post-COVID) symptom/patient evolution.

We study the problem of missing data imputation for graph signals from signed one-bit quantized observations. More precisely, we consider that the true graph data is drawn from a distribution of signals that are smooth or bandlimited on a known graph. However, instead of observing these signals, we observe a signed version of them and only at a subset of the nodes on the graph. Our goal is to estimate the true underlying graph signals from our observations. To achieve this, we propose a generative adversarial network (GAN) where the key is to incorporate graph-aware losses in the associated minimax optimization problem. We illustrate the benefits of the proposed method via numerical experiments on hand-written digits from the MNIST dataset.

Graph neural networks (GNNs) regularize classical neural networks by exploiting the underlying irregular structure supporting graph data, extending its application to broader data domains. The aggregation GNN presented here is a novel GNN that exploits the fact that the data collected at a single node by means of successive local exchanges with neighbors exhibits a regular structure. Thus, regular convolution and regular pooling yield an appropriately regularized GNN. To address some scalability issues that arise when collecting all the information at a single node, we propose a multi-node aggregation GNN that constructs regional features that are later aggregated into more global features and so on. We show superior performance in a source localization problem on synthetic graphs and on the authorship attribution problem.

The era of "data deluge" has sparked the interest in graph-based learning methods in a number of disciplines such as sociology, biology, neuroscience, or engineering. In this paper, we introduce a graph recurrent neural network (GRNN) for scalable semi-supervised learning from multi-relational data. Key aspects of the novel GRNN architecture are the use of multi-relational graphs, the dynamic adaptation to the different relations via learnable weights, and the consideration of graph-based regularizers to promote smoothness and alleviate over-parametrization. Our ultimate goal is to design a powerful learning architecture able to: discover complex and highly non-linear data associations, combine (and select) multiple types of relations, and scale gracefully with respect to the size of the graph. Numerical tests with real datasets corroborate the design goals and illustrate the performance gains relative to competing alternatives.

Graph neural networks (GNNs) have been shown to replicate convolutional neural networks' (CNNs) superior performance in many problems involving graphs. By replacing regular convolutions with linear shift-invariant graph filters (LSI-GFs), GNNs take into account the (irregular) structure of the graph and provide meaningful representations of network data. However, LSI-GFs fail to encode local nonlinear graph signal behavior, and so do regular activation functions, which are nonlinear but pointwise. To address this issue, we propose median activation functions with support on graph neighborhoods instead of individual nodes. A GNN architecture with a trainable multirresolution version of this activation function is then tested on synthetic and real-word datasets, where we show that median activation functions can improve GNN capacity with marginal increase in complexity.

Next-generation communication networks are envisioned to extensively utilize storage-enabled caching units to alleviate unfavorable surges of data traffic by pro-actively storing anticipated highly popular contents across geographically distributed storage devices during off-peak periods. This resource pre-allocation is envisioned not only to improve network efficiency, but also to increase user satisfaction. In this context, the present paper designs optimal caching schemes for distributed caching scenarios. In particular, we look at networks where a central node (base station) communicates with a number of "regular" nodes (users or pico base stations) equipped with local storage infrastructure. Given the spatio-temporal dynamics of content popularities, and the decentralized nature of our setup, the problem boils down to select what, when and where to cache. To address this problem, we define fetching and caching prices that vary across contents, time and space, and formulate a global optimization problem which aggregates the costs across those three domains. The resultant optimization is solved using decomposition and dynamic programming techniques, and a reduced-complexity algorithm is finally proposed. Preliminary simulations illustrating the behavior of our algorithm are finally presented.

We study the problem of jointly estimating several network processes that are driven by the same input, recasting it as one of blind identification of a bank of graph filters. More precisely, we consider the observation of several graph signals - i.e., signals defined on the nodes of a graph - and we model each of these signals as the output of a different network process (represented by a graph filter) defined on a common known graph and driven by a common unknown input. Our goal is to recover the specifications of every network process by only observing the outputs. Since every process shares the same input, the estimation problems are coupled, and a joint inference method is proposed. We study two different scenarios, one where the orders of the filters are known, and one where they are not. For the former case we propose a least-squares approach and provide conditions for recovery. For the latter case, we put forth a sparse recovery algorithm with theoretical guarantees. Finally, we illustrate the methods here proposed via numerical experiments.

Small base stations (SBs) of fifth-generation (5G) cellular networks are envisioned to have storage devices to locally serve requests for reusable and popular contents by caching them at the edge of the network, close to the end users. The ultimate goal is to smartly utilize a limited storage capacity to serve locally contents that are frequently requested instead of fetching them from the cloud, contributing to a better overall network performance and service experience. To enable the SBs with efficient fetch-cache decision-making schemes operating in dynamic settings, this paper introduces simple but flexible generic time-varying fetching and caching costs, which are then used to formulate a constrained minimization of the aggregate cost across files and time. Since caching decisions per time slot influence the content availability in future slots, the novel formulation for optimal fetch-cache decisions falls into the class of dynamic programming. Under this generic formulation, first by considering stationary distributions for the costs as well as file popularities, an efficient reinforcement learning-based solver known as value iteration algorithm can be used to solve the emerging optimization problem. Later, it is shown that practical limitations on cache capacity can be handled using a particular instance of this generic dynamic pricing formulation. Under this setting, to provide a light-weight online solver for the corresponding optimization, the well-known reinforcement learning algorithm, Q-learning, is employed to find optimal fetch-cache decisions. Numerical tests corroborating the merits of the proposed approach wrap up the paper.

We analyze the sampling and posterior recovery of diffused sparse graph signals from observations gathered at a single node by using an aggregation sampling scheme. Diffused sparse graph signals can be modeled as the output of a linear graph filter to a sparse input and are useful in scenarios where a few seeding (source) nodes generate a non-zero input, which is then diffused according to the network dynamics dictated by the filter. Instead of considering a traditional setup where the observations correspond to the signal values at a subset of nodes, here the observations are obtained locally at a single node via the successive aggregation of its own value and that of its neighbors. Depending on the particular application, the goal is to use the local observations to recover the diffused signal or (the location and values of) the seeds. Different sampling configurations are investigated, including those of known and unknown locations of the sources as well as those of the diffusing filter being unknown.

An analytical algebraic approach for distributed network identification is presented in this paper. The information propagation in the network is modeled using a state-space representation. Using the observations recorded at a single node and a known excitation signal, we present algorithms to compute the eigenfrequencies and eigenmodes of the graph in a distributed manner. The eigenfrequencies of the graph may be computed using a generalized eigenvalue algorithm, while the eigenmodes can be computed using an eigenvalue decomposition. The developed theory is demonstrated using numerical experiments.

This paper develops new designs for recommender systems inspired by recent advances in graph signal processing. Recommender systems aim to predict unknown ratings by exploiting the information revealed in a subset of user-item observed ratings. Leveraging the notions of graph frequency and graph filters, we demonstrate that linear latent factor models, such as low-rank matrix completion, can be viewed as bandlimited interpolation algorithms that operate in a frequency domain given by the spectrum of a joint user and item network. This new interpretation paves the way to new methods for enhanced rating prediction. We propose a low complexity method by exploiting the eigenvector of correlation matrices constructed from known ratings. In the MovieLens 100k dataset, our designs reduce the root mean squared error compared to the ones in benchmark matrix completion by 0.6% and benchmark nearest neighbor methods by 4.2%.

This paper generalizes the classical joint problem of signal demixing and blind deconvolution to the realm of graphs. We investigate a setup where a single observation formed by the sum of multiple graph signals is available. The main assumption is that each individual signal is generated by an originally sparse input diffused through the graph via the application of a graph filter. In this context, we address the related problems of: 1) separating the individual graph signals, 2) identifying the unknown input supports, and 3) estimating the coefficients of the diffusing graph filters. We first consider the case where each signal - prior to mixing - is diffused in a different graph. We then particularize the results for the more challenging case where all the signals are diffused in the same graph. The corresponding demixing and blind graph-signal deconvolution problems are formulated, convex relaxations are presented, and recovery conditions are discussed. Numerical experiments in both the single and multiple graph cases show the capabilities of demixing in synthetic and biology-inspired graphs.

In next generation cellular networks (5G) the access points (APs) are anticipated to be equipped with storage devices to serve locally requests for reusable popular contents by caching them at the edge of the network. The ultimate goal is to shift part of the load on the back-haul links from on-peak to off-peak periods, contributing to a better overall network performance and service experience. In order to enable the APs with efficient (optimal) fetch-cache decision making schemes able to work in dynamic settings, we introduce simple but flexible generic time-varying fetching and caching costs, which are then used to formulate a constrained minimization of the aggregate cost across files and time. Since caching decisions in every time slot influence the content availability in future instants, the novel formulation for optimal fetch-cache decisions falls into the class of dynamic programming, for which efficient reinforcement-learning-based solvers are proposed. The performance of our algorithms is assessed via numerical tests, and discussions on the inherent fetching-versus-caching trade-off are provided.

We address the problem of inferring an undirected graph from nodal observations, which are modeled as non-stationary graph signals generated by local diffusion dynamics on the unknown network. We propose a two-step approach where we first estimate the unknown diffusion (graph) filter, from which we recover the eigenvectors of the so-called graph-shift operator (a matrix representation of the graph). We then estimate the eigenvalues by imposing desirable properties on the graph to be recovered. To carry out the initial system identification step, we assume that second-order statistics of the inputs are available. While such quadratic filter identification problem boils down to a non-convex fourth order polynomial minimization, we propose a semidefinite relaxation with provable performance guarantees. Finally, numerical tests illustrate the use of the proposed algorithm to unveil urban mobility patterns.

Track-before-detect (TBD) is a powerful approach that consists in providing the tracker directly with the sensor measurements without any predetection. Due to the measurement model nonlinearities, online state estimation in TBD is most commonly solved via particle filtering. Existing particle filters for TBD do not incorporate measurement information in their proposal distribution. The Langevin Monte Carlo (LMC) is a sampling method whose proposal is able to exploit all available knowledge of the posterior (that is, both prior and measurement information). This letter synthesizes recent advances in differential-geometric LMC-based filtering to introduce its application to TBD. The benefits of LMC filtering in TBD are illustrated in a challenging low-noise scenario.

This paper investigates the problems of signal reconstruction and blind deconvolution for graph signals that have been generated by an originally sparse input diffused through the network via the application of a graph filter operator. Assuming that the support of the sparse input signal is unknown, and that the diffused signal is observed only at a subset of nodes, we address the related problems of: 1) identifying the input and 2) interpolating the values of the diffused signal at the non-sampled nodes. We first consider the more tractable case where the coefficients of the diffusing graph filter are known and then address the problem of joint input and filter identification. The corresponding blind identification problems are formulated, novel convex relaxations are discussed, and modifications to incorporate a priori information on the sparse inputs are provided.

Advancing a holistic theory of networks and network processes requires the extension of existing results in the processing of time-varying signals to signals supported on graphs. This paper focuses on the definition of stationarity and power spectral density for random graph signals, generalizes the concepts of autoregressive and moving average random processes to the graph domain, and investigates their parametric spectral estimation. Theoretical and algorithmic results are complemented with numerical tests on synthetic and real-world graphs.

We address the problem of identifying a graph structure from the observation of signals defined on its nodes. Fundamentally, the unknown graph encodes direct relationships between signal elements, which we aim to recover from observable indirect relationships generated by a diffusion process on the graph. We put forth a novel network topology inference approach whereby we: i) identify the eigenvectors of a matrix representation of the graph from realizations of the diffused signal; and ii) rely on these (possibly imperfect) spectral templates to estimate the eigenvalues by imposing desirable properties on the graph to be recovered. Robust algorithms with quantifiable performance are developed for the pragmatic settings where the eigenvectors are estimated with errors, or, when the eigenbasis is only partially known. Numerical tests showcase the effectiveness of the proposed algorithm in recovering amino-acid networks.

We address the problem of inferring a graph from nodal observations, which are modeled as non-stationary graph signals generated by local diffusion dynamics that depend on the structure of the sought network. Using the so-called graph-shift operator (GSO) as a matrix representation of the graph, we first identify the eigenvectors of the shift matrix from realizations of the diffused signals, and then we rely on these spectral templates to estimate the eigenvalues by imposing desirable properties on the graph to be recovered. Different from the stationary setting where the GSO and the covariance matrix of the observed signals are simultaneously diagonalizable, here they are not. Hence, estimating the eigenvectors requires first estimating the unknown diffusion (graph) filter - a polynomial in the GSO which does preserve the sought eigenbasis. To carry out this initial system identification step, we leverage different sources of information on the input signal driving the diffusion process on the graph. Numerical tests showcase the effectiveness of the proposed algorithms in recovering social and structural brain graphs.

Contemporary cloud networks are being challenged by the rapid increase of user demands and growing concerns about global warming, due to their substantial energy consumption. This requires future data centers to be both energy efficient and sustainable, which calls for leveraging cutting-edge features and the flexibility provided by the modern smart grids. To fulfill those goals, this paper puts forward a systematic approach to designing energy-aware traffic-efficient geographicalload balancing schemesfor data-center networks that are not only optimal, but also computationally efficient and amenable todistributedimplementation. Under this comprehensive approach, workload and power balancing schemes are designed jointly across the network, both delay-tolerant andinteractive workloadsare accommodated, novel smart-grid features such as energy storage units are incorporated to cope with renewables, andincentive pricingmechanisms are adopted in the design. To further account for the spatio-temporal variation of demands, energy prices and renewables, the task is formulated as a two-timescale stochastic optimization. Leveraging dual stochastic approximation and the fast iterative shrinkage-thresholding algorithm (FISTA), the proposed optimization is decomposed across time slots (first-stage) and data centers (second-stage). While the resultant online algorithm is strictly feasible and provably optimal under a Markovian assumption for the underlying random processes, extensive numerical tests further demonstrate that it also works well in real-data scenarios, where the underlying randomness is highly correlated across time.

A novel scheme for sampling graph signals is proposed. Space-shift sampling can be understood as a hybrid scheme that combines selection sampling -- observing the signal values on a subset of nodes - and aggregation sampling - observing the signal values at a single node after successive aggregation of local data. Under the assumption of bandlimitedness, we state conditions and propose strategies for signal recovery in different settings. Being a more general procedure, space-shift sampling achieves smaller reconstruction errors than current schemes, as we illustrate through the reconstruction of the industrial activity in a graph of the U.S. economy.

Network processes are often represented as signals defined on the vertices of a graph. To untangle the latent structure of such signals, one can view them as outputs of linear graph filters modeling underlying network dynamics. This paper deals with the problem of joint identification of a graph filter and its input signal, thus broadening the scope of classical blind deconvolution of temporal and spatial signals to the less-structured graph domain. Given a graph signal y modeled as the output of a graph filter, the goal is to recover the vector of filter coefficients h, and the input signal x which is assumed to be sparse. While y is a bilinear function of x and h, the filtered graph signal is also a linear combination of the entries of the "lifted" rank-one, row-sparse matrix xhT. The blind graph filter identification problem can be thus tackled via rank and sparsity minimization subject to linear constraints, an approach amenable to convex relaxation. An algorithm for jointly processing multiple output signals corresponding to different sparse inputs is also developed. Numerical tests with synthetic and real-world networks illustrate the merits of the proposed algorithm, as well as the benefits of leveraging multiple signals to aid the blind identification task.

We introduce node-variant graph filters, which allow the simultaneous implementation of multiple (regular) graph filters at different nodes, and study their design to implement arbitrary linear transformations between graph signals. Node-variant graph filters can be implemented distributedly, making them suitable for networked settings. We determine spectral conditions under which a specific linear transformation can be implemented perfectly and, for the cases where perfect implementation is infeasible, the design of optimal approximations for different error metrics is analyzed. We demonstrate the practical relevance of the developed framework by studying the application of node-variant graph filters for analog network coding.

Effective operation of next-generation communication networks requires the deployment of a high number of base stations (BSs) capable of adapting dynamically their available resources to the changing environment. The resources include link layer variables (user-channel allocation and user-BS assignment) that, due to their binary nature, render the design challenging. This work proposes algorithms for user-BS allocation in cellular networks where users access orthogonally and close-by BSs use non-interfering channels. The user-BS allocation algorithms are designed jointly with the power, rate, and user-channel allocation, and take into account the dynamic environment. Three different algorithms are designed, each of them updates (adapts) the user-BS allocation at a different speed. We show that although the linear relaxation of all the binary variables is not optimal, a Benders' decomposition approach can be used to find the optimal solution. To accomplish this, we split the original problem so that the user-BS variables are isolated, relax the remaining binary variables, and solve the (sub-)problems iteratively.

Stochastic algorithms to allocate resources across different layers in an underlay multi-hop cognitive radio with primary and secondary users are presented. The algorithms aim to maximize the utility of the secondary users, while adhering to average interfering power constraints and accounting for the presence of imperfections in the state information. Interference among secondary users is modeled using a binary conflict graph, so that close-by secondary devices cannot transmit simultaneously. The optimal resource allocation dictates the power transmitted by each user, the rates at the transport, network and physical level, and the links to be activated. The design is casted as a nonlinear constrained optimization, and the solution is obtained using stochastic dual decomposition. Nu- merical experiments validate the theoretical claims.

In this paper, we propose a novel censoring policy for energy-efficient transmissions in energy-harvesting sensors. The problem is formulated as an infinite-horizon Markov Decision Process (MDP). The objective to be optimized is the expected sum of the importance (utility) of all transmitted messages. Assuming that such importance can be evaluated at the transmitting node, we show that, under certain conditions on the battery model, the optimal censoring policy is a threshold function on the importance value. Specifically, messages are transmitted only if their importance is above a threshold whose value depends on the battery level. Exploiting this property, we propose a model-based stochastic scheme that approximates the optimal solution, with less computational complexity and faster convergence speed than a conventional Q-learning algorithm. Numerical experiments in single-hop and multi-hop networks confirm the analytical advantages of the proposed scheme.

A system comprising a utility company serving a set of electricity end-users is considered. The utility company can purchase energy from the wholesale market. It is also connected to a renewable energy production facility, from which it can harvest energy at no cost, and also to a battery for energy storage. Ahead of a scheduling horizon, the utility purchases energy based on forecasted demand and renewable energy production. During online operation, if the renewable energy is not adequate, real-time decisions with respect to user load shedding, energy procurement, and battery charging or discharging need to be made. The problem is cast in a stochastic approximation framework, and is solved online via a dual stochastic subgradient method with low per-slot complexity.

Effective operation of cognitive radios (CRs) requires sensing the spectrum and dynamic adaptation of the available resources according to the sensed information. Although sensing and resource allocation are coupled, most existing designs optimize each of the tasks separately. This work optimizes them jointly for an underlay CR paradigm. The formulation considers that secondary users adapt their power and rate based on the available imperfect channel state information, while taking into account the cost associated with acquiring such an information. The objective of the optimization is twofold: maximize the (sum-rate) performance of the CR and protect the primary users through an average interference constraint. Designing the sensing in our underlay paradigm amounts to decide what channel/frequency slots are sensed at every time instant. Partial observability of the channel state (due to noisy and outdated information) calls for (Bayesian) sequential estimators to keep track of the interference channel gains, as well as for dynamic programming tools to design the optimal schemes. Together with the optimal schemes, a simple approximate solution is also developed.

Dynamic transmit-power control (DTPC) is critical to improve spectral efficiency and reduce interference in wireless local area networks (WLANs). DTPC schemes typically use signal-to-noise-ratio (SNR) information and require exchange of information between transmitters and receivers. However, that is not always easy to implement in actual WLAN deployments. In this paper, we present a simple but novel DTPC scheme for 802.11n Access Points (AP). The method, which is run by each AP without exchanging signaling information with other APs and associated Stations (STA), seeks for transmitting with the minimum power provided that the link is not overloaded. In lieu of using the SNR at the receiver side, the power is adapted based on the wireless link occupancy (rate load). As a result, no signaling exchange between stations and the AP is required. Reducing the transmit-power reduces both co-channel and adjacent channel interference and, hence, entails benefits for all nearby WLANs. The DTPC scheme was tested in a simulator and implemented in an actual 802.11n deployment, which confirmed the theoretical benefits.

A cross-layer resource allocation scheme for underlay multi-hop cognitive radio networks is formulated, in the presence of uncertain propagation gains and locations of primary users (PUs). Secondary network design variables are optimized under long-term probability-of-interference constraints, by exploiting channel statistics and maps that pinpoint areas where PU receivers are likely to reside. These maps are tracked using a Bayesian approach, based on 1-bit messages - here refereed to as "interference tweet" - broadcasted by the PU system whenever a communication disruption occurs due to interference. Although nonconvex, the problem has zero duality gap, and it is optimally solved using a Lagrangian dual approach. Numerical experiments demonstrate the ability of the proposed scheme to localize PU receivers, as well as the performance gains enabled by this minimal primary-secondary interplay.

Successful deployment of cognitive radios requires efficient sensing of the spectrum and dynamic adaptation of the available resources according to the sensed (imperfect) information. While most works design these two tasks separately, in this paper we address them jointly. In particular, we investigate an interweave cognitive radio with multiple secondary users that access orthogonally a set of frequency bands originally devoted to primary users. The schemes are designed to minimize the cost of sensing, maximize the performance of the secondary users (weighted sum rate), and limit the probability of interfering with the primary users. The joint design is addressed using nonlinear optimization and dynamic programming, which is able to leverage the time correlation in the activity of the primary network. A two-step strategy is implemented: it first finds the optimal resource allocation for any sensing scheme and then uses that solution as input to solve for the optimal sensing policy. The two-step strategy is optimal, gives rise to intuitive optimal policies, and entails a computational complexity much lower than that required to solve the original formulation.

Conventional spectrum sensing schemes can detect active transmitters but not passive receivers, which have to be nevertheless protected from excessive interference whenever their bands are reused. In this paper, a resource allocation scheme for underlay cognitive radios is formulated, taking into account uncertainty of both propagation gains and locations of incumbent receivers. The performance of orthogonal access by secondary users is maximized under average interference constraints, using channel statistics and maps that pin-point areas where primary receivers are likely to reside. These maps are tracked using a Bayesian approach, based on a 1-bit message sent by the primary system whenever a communication disruption occurs due to interference.

Convex optimization and dual decomposition have been successfully used to design cross-layer resource allocation algorithms for cellular access networks. However, less effort has been devoted to design optimal algorithms for systems equipped with relay stations. Presence of relay stations renders the design of the access schemes more difficult and requires consideration of additional constraints. The present paper relies on a sum-utility constrained maximization framework to design cross-layer algorithms that guarantee diverse quality of service (QoS) and consider different forwarding strategies at the relay stations. One of the main challenges in the design is the joint consideration of both long-term (elastic) and short-term (real-time) constraints. Such constraints account for diverse delay QoS requirements and relay forwarding strategies. A two-step methodology is proposed to efficiently deal with this challenge. Specifically, for each time instant it applies: a) an approximate online method to estimate the multipliers for the long-term constraints and the corresponding primal variables (resources), and b) a classical iterative method to calculate the multipliers for the short-term constraints and the corresponding primal variables. Our approach incurs an arbitrarily small loss of optimality, and can accommodate both static and fading channels.

Efficient design of cognitive radios (CRs) calls for secondary users implementing adaptive resource allocation schemes that exploit knowledge of the channel state information (CSI), while at the same time limiting interference to the primary system. This paper introduces stochastic resource allocation algorithms for both interweave (also known as overlay) and underlay cognitive radio paradigms. The algorithms are designed to maximize the weighted sum-rate of orthogonally transmitting secondary users under average-power and probabilistic interference constraints. The latter are formulated either as short- or as long-term constraints, and guarantee that the probability of secondary transmissions interfering with primary receivers stays below a certain pre-specified level. When the resultant optimization problem is non-convex, it exhibits zero-duality gap and thus, due to a favorable structure in the dual domain, it can be solved efficiently. The optimal schemes leverage CSI of the primary and secondary networks, as well as the Lagrange multipliers associated with the constraints. Analysis and simulated tests confirm the merits of the novel algorithms in: i) accommodating time-varying settings through stochastic approximation iterations; and ii) coping with imperfect CSI.

Efficient design of cognitive radio networks calls for secondary users implementing adaptive resource allocation, which requires knowledge of the channel state information in order to limit interference inflicted to primary users. In this context, the present paper develops stochastic resource allocation algorithms maximizing the sum-rate of secondary users while adhering to "average power" and "probability of interference" constraints. These constraints guarantee that the probability of the secondary network interfering with the primary one stays below a pre-specified level. The optimal schemes turn out to be a function of the quality of the secondary network links, the activity of the primary users, and the associated Lagrange multipliers. The focus is on algorithms that: i) use stochastic approximation tools to estimate the multipliers; and ii) are able to cope with imperfections in the information of the primary network state.

Scenarios where nodes have limited energy and forward messages of different importances (priorities) are frequent in the context of wireless sensor networks. Tailored to those scenarios, this paper relies on stochastic tools to develop selective message forwarding schemes. The schemes will depend on parameters such as the available battery at the node, the energy cost of retransmitting a message, or the importance of messages. The forwarding schemes are designed for three different cases: 1) when sensors maximize the importance of their own transmitted messages; 2) when sensors maximize the importance of messages that have been successfully retransmitted by at least one of its neighbors; and 3) when sensors maximize the importance of messages that successfully arrive to the sink. More sophisticated schemes will achieve better importance performance, but will also require information from other sensors. The results contribute to identify the variables that, when made available to other nodes, have a greater impact on the overall network performance. Suboptimal schemes that rely on local estimation algorithms and entail reduced computational cost are also designed.

Efficient design of wireless networks requires implementation of cross-layer algorithms that exploit channel state information. Capitalizing on convex optimization and stochastic approximation tools, this paper develops a stochastic algorithm that allocates resources at network, link, and physical layers so that a sum-utility of the average end-to-end rates is maximized. Focus is placed on networks where interference is strong and nodes transmit orthogonally over a set of parallel channels. Convergence of the developed stochastic schemes is characterized, and the average queue delays are obtained in closed form.

Dynamic spectrum access (DSA) is an integral part of cognitive radio technology aiming at efficient management of the available power and bandwidth resources. The present paper deals with cooperative DSA networks, where collaborating terminals adhere to diverse (maximum and minimum) quality-of-service (QoS) constraints in order to not only effect hierarchies between primary and secondary users but also prevent abusive utilization of the available spectrum. Peer-to-peer networks with co-channel interference are considered in both single- and multi-channel settings. Utilities that are functions of the signal-to-interference-plus-noise ratio (SINR) are employed as QoS metrics. By adjusting their transmit power, users can mitigate the generated interference and also meet the QoS requirements. A novel formulation accounting for heterogeneous QoS requirements is obtained after introducing a suitable relaxation and recasting a constrained sum-utility maximization as a convex optimization problem. The optimality of the relaxation is established under general conditions. Based on this relaxation, an algorithm for optimal power control that is amenable to distributed implementation is developed, and its convergence is established. Numerical tests verify the analytical claims and demonstrate performance gains relative to existing schemes.

Orthogonal frequency-division multiplexing (OFDM) is the most popular modulation in modern wireless communication systems. Among other features, OFDM has been able to successfully exploit channel state information (CSI) at the transmitter, allowing to implement dynamic resource allocation schemes that improve spectral efficiency and error resilience. Nevertheless, in most wireless communication systems achieving a perfect CSI at the transmitter is difficult. For this reason a limited-rate feedback mode has been proposed, in which only quantized CSI at the transmitter is available. In this paper we design joint channel quantization and resource allocation schemes for single-user OFDM systems, that use limited-rate feedback and do not assume any structure on the channel quantizer. The new schemes are obtained by solving an optimization problem that maximizes average ergodic rate subject to average power and bit error rate constraints. Necessary optimality conditions for the quantization and resource allocation schemes are derived and algorithms to find a solution satisfying such conditions are discussed. Since finding the overall global optimal solution is computationally cumbersome, suboptimal yet simple schemes are also explored. Three simplifications are investigated, namely: a worst-case robust design that reduces the dimensionality of the problem; optimal and provably convergent stochastic schemes that catch the average behavior of the system on-the-fly; and schemes that reduce the amount of feedback required from the receiver by exploiting the channel correlation among subcarriers. The signalling and computational costs associated to the implementation of the developed schemes and their extension to multiple user systems are also discussed. Numerical examples corroborate analytical claims and reveal that significant gains result even when suboptimal schemes based on affordable limited-rate feedback are used.

Dynamic allocation of power, rate and channel access is a critical task in wireless networks. Capitalizing on convex optimization and stochastic approximation tools, this paper develops a stochastic resource allocation algorithm that minimizes average transmit power under individual average rate constraints. Focus is placed on networks where users transmit orthogonally over a set of parallel channels and transmissions are adapted based on quantized channel state information (CSI) allowing even channel statistics to be unknown. Convergence of the developed stochastic scheme is characterized and the average queue delays are obtained in closed form.

An optimum selective transmission scheme for energy-limited sensor networks, where sensors send or forward messages of different importance (priority), is developed. Considering the energy costs, the available battery, the message importances and their statistical distribution, sensors decide whether to transmit or discard a message so that the importance sum of the effectively transmitted messages is maximized. It turns out that the optimal decision is made comparing the message importance with a time-variant threshold. Moreover, the gain of the selective transmission scheme, compared to a nonselective one, critically depends on the energy expenses, among other factors. Albeit suboptimal, practical schemes that operate under less demanding conditions than those for the optimal one are developed. Effort is placed into three directions: 1) the analysis of the optimal transmission policy for several stationary importance distributions; 2) the design of a transmission policy with invariant threshold that entails asymptotic optimality; and 3) the design of an adaptive algorithm that estimates the importance distribution from the actual received (or sensed) messages. Numerical results corroborating our theoretical claims and quantifying the gains of implementing the selective scheme close this paper.

Transmit-power control is a critical task in cognitive radio (CR) networks. In the present contribution, adherence to hierarchies between primary and secondary users in a peer-to-peer CR network is enabled through distributed power control. Hierarchies are effected by imposing minimum and maximum bounds on a quality-of-service (QoS) metric, such as communication rate. These bounds translate to signal-to-interference-plus-noise ratio (SINR) constraints. Furthermore, a utility function captures each user's satisfaction with the received SINR. The novel power control strategy maximizes the total utility while respecting individual SINR constraints - a task recast as a convex optimization problem under a suitable relaxation. Sufficient conditions, realistic for practical CR networks, are provided to obtain the optimal power allocation from the solution of the relaxed problem. Finally, a low-overhead distributed algorithm for optimal power control is developed, and tested against competing alternatives via simulations.

The present paper deals with dynamic resource management based on quantized channel state information (CSI) for multi-carrier cognitive radio networks comprising primary and secondary wireless users. For each subcarrier, users rely on adaptive modulation, coding and power modes that they select in accordance with the limited-rate feedback they receive from the access point. The access point uses CSI to maximize the sum of generic concave utilities of the individual average rates in the network while respecting rate and power constraints on the primary and secondary users. Using a stochastic dual approach, optimum dual prices are found to optimally allocate resources across users per channel realization without requiring knowledge of the channel distribution.

Emerging applications involving low-cost wireless sensor networks motivate well optimization of multi-user orthogonal frequency-division multiple access (OFDMA) in the power-limited regime. In this context, the present paper relies on limited-rate feedback (LRF) sent from the access point to terminals to minimize the total average transmit-power under individual average rate and error probability constraints. Along with the characterization of optimal bit, power and subcarrier allocation policies based on LRF, suboptimal yet simple schemes are developed for channel quantization. The novel algorithms proceed in two phases: (i) an off-line phase to construct the channel quantizer as well as the rate and power codebooks with moderate complexity; and (ii) an on-line phase to obtain, based on quantized channel state information, the optimum, rate, power and user-subcarrier allocation with linear complexity. Numerical examples corroborate the analytical claims and reveal that significant power savings result even with suboptimal schemes based on practically affordable LRF.

We deal with energy efficient time-division multiple access over fading channels with finite-rate feedback for use in the power-limited regime. Through FRP from the access point, users acquire quantized channel state information. The goal is to map channel quantization states to adaptive modulation and coding modes and allocate optimally time slots to users so that the average transmit-power is minimized. To this end, we develop a joint quantization and resource allocation approach, which decouples the complicated problem at hand into three minimization sub-problems and relies on a coordinate descent approach to iteratively effect energy efficiency. Numerical results are presented to evaluate the energy savings.

We consider minimizing average transmit-power with finite-rate feedback for coherent communications in a wireless sensor network (WSN). where sensors communicate with a fusion center (FC) using adaptive modulation and coding over a wireless fading channel. By viewing the coherent WSN setup as a distributed space-time multi-input single-output (MISO) system, we develop beamforming and resource allocation strategies and design optimal quantizers when the sensors only have available quantized (Q-) channel state information at the transmitters (CSIT) through a finite-rate feedback channel. Numerical results reveal that our novel design based on Q-CSIT yields significant power savings even for a small number of feedback bits.

Emerging applications involving low-cost wireless sensor networks motivate well optimization of multi-user orthogonal frequency-division multiple access (OFDMA) in the power-limited regime. In this context, the present paper relies on limited- rate feedback (LRF) sent from the access point to terminals to acquire quantized channel state information (CSI) in order to minimize the total average transmit-power under individual average rate and error probability constraints. Specifically, we introduce two suboptimal reduced-complexity schemes to: (i) allocate power, rate and subcarriers across users; and (ii) design accordingly the channel quantizer. The latter relies on the solution of (i) to design equally probable quantization regions per subcarrier and user. Numerical examples corroborate the analytical claims and reveal that the power savings achieved by our reduced-complexity LRF designs are close to those achieved by the optimal solution.

Energy is a valuable resource in wireless sensor networks since it constitutes a limiting factor for the network lifetime. In order to make an efficient use of its own energy resources, each node in the network should be aware of the energy resources at other nodes, which can be relevant to the success of their routing decisions. The proposal of this paper is twofold: (i) to design a routing algorithm based on learning patterns using geographic information and (ii) to focus on the cut down in energy consumption. We show that by exploiting local information from the signals detected at each node, sensor nodes can learn to route messages in order to improve the communication performance of the overall network and minimize the need of coordination or signalling protocols among nodes. Moreover, if messages are prioritized by some importance parameter, the overall importance of the successfully transmitted messages can be drastically improved. Experimental results highlight that our algorithm achieves a good performance in terms of successful delivery rate and maximizes the importance of the received messages.

Emerging applications involving low-cost wireless sensor networks motivate well optimization of multi-user orthogonal frequency-division multiple access (OFDMA) in the power-limited regime. In this context, the present paper relies on limited-rate feedback (LRF) sent from the access point to terminals to minimize the total average transmit-power under individual average rate and error probability constraints. The characterization of optimal bit, power and subcarrier allocation policies based on LRF, as well as optimal channel quantization are provided. Numerical examples corroborate the analytical claims and reveal that significant power savings result even with few fed back bits.

Scheduling amounts to allocating optimally channel, rate and power resources to multiple connections with diverse quality-of-service (QoS) requirements. It constitutes a throughput-critical task at the medium access control layer of today's wireless networks that has been tackled by seemingly unrelated information-theoretic and protocol design approaches. Capitalizing on convex optimization and stochastic approximation tools, the present paper develops a unified framework for channel-aware QoS-guaranteed scheduling protocols for use in adaptive wireless networks whereby multiple terminals are linked through orthogonal fading channels to an access point, and transmissions are (opportunistically) adjusted to the intended channel. The unification encompasses downlink and uplink with time-division or frequency-division duplex operation; full and quantized channel state information comprising a few bits communicated over a limited-rate feedback channel; different types of traffic (best effort, non-real-time, real-time); uniform and optimal power loading; off-line optimal scheduling schemes benchmarking fundamentally achievable rate limits; as well as on-line scheduling algorithms capable of dynamically learning the intended channel statistics and converging to the optimal benchmarks from any initial value. The take-home message offers an important cross-layer design guideline: judiciously developed, yet surprisingly simple, channel-adaptive, on-line schedulers can approach information-theoretic rate limits with QoS guarantees.

Motivated by the increasing demand for low-cost low-power wireless sensor networks and related applications, we develop suboptimal but simple bit and power loading algorithms that minimize transmit-power for orthogonal frequency division multiplexing (OFDM) under rate and error probability constraints. Bit and power loading adaptation are based on a quantized version of channel state information (D-CSI) conveyed from the receiver to the transmitter. Our design exploits the correlation among sub-carriers in order to reduce feedback overhead. Numerical examples support our claim that simple suboptimal schemes with a reduced number of feedback bits achieve near-optimal performance while providing significant power savings

In response to the growing demand for low-cost low-power wireless sensor networks and related applications, we develop bit and power loading algorithms that minimize transmit-power for orthogonal frequency division multiplexing (OFDM) under rate and error probability constraints. Our novel algorithms exploit one of three types of channel state information at the transmitter (CSIT): deterministic (per channel realization) for slow fading links, statistical (channel mean) for fast fading links, and quantized (Q-) CSIT whereby a limited number of bits are fed back from the transmitter to the receiver. By adopting average transmit-power as a distortion metric, a channel quantizer is also designed to obtain a suitable form of Q-CSI. Numerical examples corroborate the analytical claims and reveal that significant power savings result even with a few bits of Q-CSIT.

Emerging applications involving low-cost wireless sensor networks motivate well optimization of orthogonal frequency-division multiplexing (OFDM) in the power-limited regime. To this end, the present paper develops loading algorithms to minimize transmit-power under rate and error probability constraints, using three types of channel state information at the transmitter (CSIT): deterministic (per channel realization) for slow fading links, statistical (channel mean) for fast fading links, and quantized (Q), whereby a limited number of bits are fed back from the transmitter to the receiver. Along with optimal bit and power loading schemes, quantizer designs and reduced complexity alternatives with low feedback overhead are developed to obtain a suite of Q-CSIT-based OFDM transceivers with desirable complexity versus power-consumption tradeoffs. Numerical examples corroborate the analytical claims and reveal that significant power savings result even with a few bits of Q-CSIT