The study of tail behaviour of \textbf{\texttt{SGD}}-induced processes has been attracting a lot of interest, due to offering strong guarantees with respect to individual runs of an algorithm. While many works provide high-probability guarantees, quantifying the error rate for a fixed probability threshold, there is a lack of work directly studying the probability of failure, i.e., quantifying the tail decay rate for a fixed error threshold. Moreover, existing results are of finite-time nature, limiting their ability to capture the true long-term tail decay which is more informative for modern learning models, typically trained for millions of iterations. Our work closes these gaps, by studying the long-term tail decay of \textbf{\texttt{SGD}}-based methods through the lens of large deviations theory, establishing several strong results in the process. First, we provide an upper bound on the tails of the gradient norm-squared of the best iterate produced by (vanilla) \textbf{\texttt{SGD}}, for non-convex costs and bounded noise, with long-term decay at rate $e^{-\frac{t}{\log(t)}}$. Next, we relax the noise assumption by considering clipped \textbf{\texttt{SGD}} (\textbf{\texttt{c-SGD}}) under heavy-tailed noise with bounded moment of order $p \in (1,2]$, showing an upper bound with long-term decay at rate $e^{-\frac{t^{\beta_p}}{\log(t)}}$, where $\beta_p = \frac{4(p-1)}{3p-2}$ for $p \in (1,2)$ and $e^{-\frac{t}{\log^2(t)}}$ for $p = 2$. Finally, we provide lower bounds on the tail decay, at rate $e^{-t}$, showing that our rates for both \textbf{\texttt{SGD}} and \textbf{\texttt{c-SGD}} are tight, up to poly-logarithmic factors. Notably, our results demonstrate \textit{an order of magnitude faster} long-term tail decay compared to existing work based on finite-time bounds, which show rates $e^{-\sqrt{t}}$ and $e^{-t^{\beta_p/2}}$, $p \in (1,2]$, for \textbf{\texttt{SGD}} and \textbf{\texttt{c-SGD}}, respectively. As such, we uncover regimes where the tails decay much faster than previously known, providing stronger long-term guarantees for individual runs.

Distributed decision-making over networks involves multiple agents collaborating to achieve a common goal. In the social learning process, where agents aim at inferring an unknown state from a stream of local observations, the probability of error in their decisions converges to zero exponentially in the asymptotic regime. The rate of this convergence, known as the error exponent, is influenced by the combination policy employed by the network. This work addresses the challenge of identifying the optimal combination policies to maximize the error exponent. We establish an upper bound on the achievable error exponents by the social learning rule and provide the conditions for the combination policy to reach this upper bound. By implementing the optimized policy, we enhance the error exponent, leading to improved accuracy and efficiency in the distributed decision-making process.

This paper studies the problem of interconnected agents collaborating to track a dynamic state from partially informative observations, where the dynamic state evolves according to a slowly varying finite-state Markov chain. Although the centralized version of this problem has been extensively studied in the literature, the decentralized setting, particularly in the context of social learning, remains largely underexplored. The main result of this work is to establish that adaptive social learning (ASL), a recent social learning strategy suited for non-stationary environments, achieves the same error probability scaling law as the centralized solution in the rare transitions regime. Theoretical findings are supported by simulations, offering valuable insights into social learning under Markovian state transitions.

This work employs a social learning strategy to estimate the global state in a partially observable multi-agent reinforcement learning (MARL) setting. We prove that the proposed methodology can achieve results within an ε-neighborhood of the solution for a fully observable setting, provided that a sufficient number of social learning updates are performed. We illustrate the results through computer simulations.

In this paper, we study a dynamic game between two networks. The networks compete by optimizing two coupled objective functions. Agents within the same network work toward a common goal and are regarded as cooperative agents; they exchange their strategies via links with other agents. Additionally, in the assumed model, each agent receives information from some adversary agents following a bipartite cross-network topology. The networks employ a diffusion learning strategy that allows them to learn and pursue the equilibrium state adaptively. We show that the networks converge to the Nash equilibrium in the mean-square-error sense under some reasonable assumptions.

Online distributed optimization is particularly useful for solving optimization problems with streaming data collected by multiple agents over a network. When the solutions lie on a Riemannian manifold, such problems become challenging to solve, particularly when efficiency and continuous adaptation are required. This work tackles these challenges and devises a diffusion adaptation strategy for decentralized optimization over general manifolds. A theoretical analysis shows that the proposed algorithm is able to approach network agreement after sufficient iterations, which allows a non-asymptotic convergence result to be derived. We apply the algorithm to the online decentralized principal component analysis problem and Gaussian mixture model inference. Experimental results with both synthetic and real data illustrate its performance.

This paper proposes a theoretical framework to evaluate and compare the performance of stochastic gradient algorithms for distributed learning in relation to their behavior around local minima in nonconvex environments. Previous works have noticed that convergence toward flat local minima tend to enhance the generalization ability of learning algorithms. This work discovers three interesting results. First, it shows that decentralized learning strategies are able to escape faster away from local minima and favor convergence toward flatter minima relative to the centralized solution. Second, in decentralized methods, the consensus strategy has a worse excess-risk performance than diffusion, giving it a better chance of escaping from local minima and favoring flatter minima. Third, and importantly, the ultimate classification accuracy is not solely dependent on the flatness of the local minimum but also on how well a learning algorithm can approach that minimum. In other words, the classification accuracy is a function of both flatness and optimization performance. In this regard, since diffusion has a lower excess-risk than consensus, when both algorithms are trained starting from random initial points, diffusion enhances the classification accuracy. The paper examines the interplay between the two measures of flatness and optimization error closely. One important conclusion is that decentralized strategies deliver in general enhanced classification accuracy because they strike a more favorable balance between flatness and optimization performance compared to the centralized solution.

This paper studies the probability of error associated with the social machine learning framework, which involves an independent training phase followed by a cooperative decision-making phase over a graph. This framework addresses the problem of classifying a stream of unlabeled data in a distributed manner. In this work, we examine the classification task with limited observations during the decision-making phase, which requires a non-asymptotic performance analysis. We establish a condition for consistent training and derive an upper bound on the probability of error for classification. The results clarify the dependence on the statistical properties of the data and the combination policy used over the graph. They also establish the exponential decay of the probability of error with respect to the number of unlabeled samples.

To protect both local gradients and estimated parameters in distributed learning, this paper introduces a masked diffusion (MD) strategy, leading to two algorithms: the MD stochastic gradient (MD-SG) and the MD primal-dual stochastic gradient (MPD-SG). The two algorithms distinguish themselves from existing privacy diffusion methods by incorporating two mechanisms: non-zero mean protection noise and a random matrix step-size. The first mechanism ensures the confidentiality of the transmitted values, while the second protects the gradient information. We analyze the mean-square stability and privacy of the proposed methods under standard assumptions. The results indicate that the MPD-SG algorithm, with a sufficiently small parameter γ, can achieve better steady-state performance than the MD-SG algorithm in heterogeneous data scenarios. Finally, simulations illustrate the effectiveness of the proposed algorithms and support the theoretical analysis.

The vulnerability of machine learning models to adversarial attacks has been attracting considerable attention in recent years. Most existing studies focus on the behavior of stand-alone single-agent learners. In comparison, this work studies adversarial training over graphs, where individual agents are subjected to perturbations of varied strength levels across space. It is expected that interactions by linked agents, and the heterogeneity of the attack models that are possible over the graph, can help enhance robustness in view of the coordination power of the group. Using a min-max formulation of distributed learning, we develop a decentralized adversarial training framework for multi-agent systems. Specifically, we devise two decentralized adversarial training algorithms by relying on two popular decentralized learning strategies–diffusion and consensus. We analyze the convergence properties of the proposed framework for strongly-convex, convex, and non-convex environments, and illustrate the enhanced robustness to adversarial attacks.

This article proposes an exploration technique for multiagent reinforcement learning (MARL) with graph-based communication among agents. We assume that the individual rewards received by the agents are independent of the actions by the other agents, while their policies are coupled. In the proposed framework, neighboring agents collaborate to estimate the uncertainty about the state-action space in order to execute more efficient explorative behavior. Different from existing works, the proposed algorithm does not require counting mechanisms and can be applied to continuous-state environments without requiring complex conversion techniques. Moreover, the proposed scheme allows agents to communicate in a fully decentralized manner with minimal information exchange. And for continuous-state scenarios, each agent needs to exchange only a single parameter vector. The performance of the algorithm is verified with theoretical results for discrete-state scenarios and with experiments for the continuous ones.

This work introduces and studies the convergence of a stochastic diffusion-optimistic learning (DOL) strategy for solving distributed nonconvex (NC) and Polyak–Lojasiewicz (PL) min-max optimization problems. Problems of this type are of interest due to a wide range of applications, including in generative adversarial networks (GANs), adversarial machine learning, and reinforcement learning. We prove that the DOL algorithm approaches an ε-stationary point through cooperation among agents following a left-stochastic communication protocol. The good performance of the proposed algorithm is illustrated by means of computer simulations.

In social learning, a network of agents assigns probability scores (beliefs) to some hypotheses of interest, based on the observation of streaming data. First, each agent updates locally its belief with the information extracted from the current data through a suitable likelihood model. Then, these beliefs are diffused across the network, and the agents aggregate the beliefs received from their neighbors by means of a pooling rule. This work studies social learning in the context of fully online problems, where the true hypothesis and the likelihood models can drift over time. Traditional social learning fails to address both cases. To overcome this limitation, we propose the doubly adaptive social learning (A2SL) strategy, which infuses traditional social learning with the necessary adaptation capabilities to face drifts in the hypotheses and/or models. The A2SL strategy achieves this goal by employing two adaptation stages, and we show that all agents learn well (i.e., they end up placing full belief mass on the correct hypothesis) in the regime of small adaptation parameters.

In this work, we examine a network of agents operating asynchronously, aiming to discover an ideal global model that suits individual local datasets. Our assumption is that each agent independently chooses when to participate throughout the algorithm and the specific subset of its neighbourhood with which it will cooperate at any given moment. When an agent chooses to take part, it undergoes multiple local updates before conveying its outcomes to the sub-sampled neighbourhood. Under this setup, we prove that the resulting asynchronous diffusion strategy is stable in the mean-square error sense and provide performance guarantees specifically for the federated learning setting. We illustrate the findings with numerical simulations.

Traditional social learning frameworks consider environments with a homogeneous state where each agent receives observations conditioned on the same hypothesis. In this work, we study the distributed hypothesis testing problem for graphs with a community structure, assuming that each cluster receives data conditioned on some different true state. This situation arises in many scenarios, such as when sensors are spatially distributed, or when individuals in a social network have differing views or opinions. We show that the adaptive social learning strategy is not only superior in nonstationary environments, but also allows each cluster to discover its own truth.

We consider a collaborative decision-making frame-work where heterogeneous agents receive streaming and partially informative observations. We consider two asynchronous scenarios that differ based on the agents' participation patterns and the fusion center's policies. By using hypothetical interventions on individual agents to conduct credit assignment, we attribute causal impact scores to each agent for the joint decision. By further employing these scores in a guided theoretical analysis, we compare the fusion center's two policies by evaluating their vulnerability to adversarial attacks, robustness against moderate deviations, and fairness.

Non-Bayesian social learning is a framework for distributed hypothesis testing aimed at learning the true state of the environment. Traditionally, the agents are assumed to receive observations conditioned on the same true state, although it is also possible to examine the case of heterogeneous models across the graph. One important special case is when heterogeneity is caused by the presence of malicious agents whose goal is to move the agents toward a wrong hypothesis. In this letter, we propose an algorithm that allows discovering the true state of every individual agent based on thesequenceof their beliefs. In so doing, the methodology is also able to locate malicious behavior.

This work focuses on adversarial learning over graphs. We propose a general adversarial training framework for multi-agent systems using diffusion learning. We analyze the convergence properties of the proposed scheme for convex optimization problems, and illustrate its enhanced robustness to adversarial attacks.

We examine the learning performance achievable by a network of agents that solve a distributed regression problem using the recently proposed ACTC (Adapt-Compress-Then-Combine) diffusion strategy. The agents operate under communication constraints: they are allowed to communicate only with their immediate neighbors, and the exchanged signals are encoded by using randomized differential compression operators. We show that the mean-square estimation error of each agent comprises the error that the agents would achieve without communication constraints plus a compression loss. Our results reveal the fundamental quantitative relationship existing between the compression loss and the peculiar attributes of the distributed regression problem. We show how these quantitative relationships can be used to optimize the allocation of communication resources across the agents and improve their learning performance as compared to a uniform allocation.

Social learning algorithms provide a model for the formation and propagation of opinions over social networks. However, most studies focus on the case in which agents share their information synchronously over regular intervals. In this work, we analyze belief convergence and steady-state learning performance for both traditional and adaptive formulations of social learning under asynchronous behavior by the agents, where some of the agents may decide to abstain from sharing any information with the network at some time instants. We also show how to recover the underlying graph topology from observations of the asynchronous network behavior.

In social learning, a group of agents linked by a graph topology collect data and exchange opinions on some topic of interest, represented by a finite set of hypotheses. Traditional social learning algorithms allow all agents in the network to gain full confidence on the true underlying hypothesis as the number of observations increases. Under partial information sharing, agents can exchange opinions only on a single hypothesis. This introduces significant challenges as compared to the standard case of full opinion sharing. We propose a novel strategy where each agent forms a valid belief by completing the partial beliefs received from its neighbors. The completion process exploits the knowledge accumulated in the past beliefs, thanks to a principled memory-aware rule inspired by a Bayesian criterion. We provide a detailed characterization of the memory-aware strategy, which reveals novel learning dynamics and highlights its advantages over previously considered schemes.

This work examines the problem of learning a network graph from signals emitted by the network nodes, according to a diffusion model ruled by a Laplacian combination policy. The challenging regime of partial observability is considered, where signals are collected from a limited subset of nodes, and we wish to estimate the subgraph of connections between these probed nodes. For the static setting where the network graph is fixed during the estimation process, we examine the sample complexity (number of time samples necessary to achieve consistent learning as the network size grows) of Erdős-Rényi and Bollobás-Riordan graphs. This complexity is almost quadratic for the former and almost linear for the latter class of graphs. We then examine the dynamic graph setting where the graph of latent nodes grows over time, while the probed subset remains fixed. We show that in this case the sample complexity can be reduced, implying the unexpected conclusion that dynamic graphs might help topology inference under partial observability.

This paper studies the non-asymptotic classification performance of the social machine learning strategy. This strategy involves an independent training phase followed by a cooperative inference phase to classify a growing number of samples. By considering instead a finite number of samples, we provide an upper bound for the probability of misclassification. This bound helps characterize the generalization ability of the social machine learning strategy, in terms of the statistical properties of the classification problem and the combination policy among the distributed classifiers. The analysis establishes the exponential decay of the probability of error with the number of samples when the training phase is consistent.

We study the generation of dependent random numbers in a distributed fashion in order to enable privatized distributed learning by networked agents. We propose a method that we refer to as local graph-homomorphic processing; it relies on the construction of particular noises over the edges to ensure a certain level of differential privacy. We show that the added noise does not affect the performance of the learned model. This is a significant improvement to previous works on differential privacy for distributed algorithms, where the noise was added in a less structured manner without respecting the graph topology and has often led to performance deterioration. We illustrate the theoretical results by considering a linear regression problem over a network of agents.

The adaptive social learning paradigm deals with the opinion formation process by a network of communicating agents in a dynamic environment. In this study, we show that a sequence of publicly exchanged beliefs allows users to discover rich information about the underlying model. In particular, it is shown that it is possible (i) to identify the influence of each individual agent to the objective of truth learning, (ii) to discover how well-informed each agent is, and (iii) to learn the underlying network topology.

This work addresses the problem of sharing partial information within social learning strategies. In social learning, agents solve a distributed multiple hypothesis testing problem by performing two operations at each instant: first, agents incorporate information from private observations to form their beliefs over a set of hypotheses; second, agents combine the entirety of their beliefs locally among neighbors. Within a sufficiently informative environment and as long as the connectivity of the network allows information to diffuse across agents, these algorithms enable agents to learn the true hypothesis. Instead of sharing the entirety of their beliefs, this work considers the case in which agents will only share their beliefs regarding one hypothesis of interest, with the purpose of evaluating its validity, and draws conditions under which this policy does not affect truth learning. We propose two approaches for sharing partial information, depending on whether agents behave in a self-aware manner or not. The results show how different learning regimes arise, depending on the approach employed and on the inherent characteristics of the inference problem. Furthermore, the analysis interestingly points to the possibility of deceiving the network, as long as the evaluated hypothesis of interest is close enough to the truth.

This work proposes a decentralized architecture, where individual agents aim at solving a classification problem while observing streaming features of different dimensions and arising from possibly different distributions. In the context of social learning, several useful strategies have been developed, which solve decision making problems through local cooperation across distributed agents and allow them to learn from streaming data. However, traditional social learning strategies rely on the fundamental assumption that each agent has significant prior knowledge of the underlying distribution of the observations. In this work we overcome this issue by introducing a machine learning framework that exploits social interactions over a graph, leading to a fully data-driven solution to the distributed classification problem. In the proposed social machine learning (SML) strategy, two phases are present: in the training phase, classifiers are independently trained to generate a belief over a set of hypotheses using a finite number of training samples; in the prediction phase, classifiers evaluate streaming unlabeled observations and share their instantaneous beliefs with neighboring classifiers. We show that the SML strategy enables the agents to learn consistently under this highly-heterogeneous setting and allows the network to continue learning even during the prediction phase when it is deciding on unlabeled samples. The prediction decisions are used to continually improve performance thereafter in a manner that is markedly different from most existing static classification schemes where, following training, the decisions on unlabeled data are not re-used to improve future performance.

This work addresses the problem of learning the topology of a network from the signals emitted by the network nodes. These signals are generated over time through a linear diffusion process, where neighboring nodes exchange messages according to the underlying network topology, and aggregate them according to a certain combination matrix. We consider the demanding setting of graph learning under partial observability, where signals are available only from a limited fraction of nodes, and we want to establish whether the topology of these nodes can be estimated faithfully, despite the presence of possibly many latent nodes. Recent results examined this problem when the network topology is generated according to an Erdős-Rényi random model. However, Erdős-Rényi graphs feature homogeneity across nodes and independence across edges, while, over several real-world networks, significant heterogeneity is observed between very connected “hubs” and scarcely connected peripheral nodes, and the edge construction process entails significant dependencies across edges. Preferential attachment random graphs were conceived primarily to fill these gaps. We tackle the problem of graph learning over preferential attachment graphs by focusing on the following setting: first-order vector autoregressive models equipped with a stable Laplacian combination matrix, and a network topology drawn according to the popular Bollobás-Riordan preferential attachment model. The main result established in this work is that a combination-matrix estimator known as Granger estimator achieves graph learning under partial observability.

Adaptive social learning is a useful tool for studying distributed decision-making problems over graphs. This paper investigates the effect of combination policies on the performance of adaptive social learning strategies. Using large-deviation analysis, it first derives a bound on the steady-state error probability and characterizes the optimal selection for the Perron eigenvectors of the combination policies. It subsequently studies the effect of the combination policy on the transient behavior of the learning strategy by estimating the adaptation time in the low signal-to-noise ratio regime. In the process, it is discovered that, interestingly, the influence of the combination policy on the transient behavior is insignificant, and thus it is more critical to employ policies that enhance the steady-state performance. The theoretical conclusions are illustrated by means of computer simulations.

In this paper we study the problem of social learning under multiple true hypotheses andself-interestedagents that exchange information over a graph. In this setup, each agent receives data that might be generated from a different hypothesis (or state) than the data received by the other agents. In contrast to the related literature on social learning, which focuses on showing that the network achieves consensus, here we study the case where every agent is self-interested and wishes to find the hypothesis that generates its own observations. Moreover, agents do not know which other agents among their peers want to discover the same state as theirs. As a result they do not know which agents they should cooperate with. To enable learning under these conditions, we propose a strategy withadaptivecombination weights and study the consistency of the agents’ learning process. The method allows each agent to identify and collaborate with neighbors that observe the same hypothesis, while excluding others, thus resulting in improved performance compared to both non-cooperative learning and cooperative social learning solutions. We analyze the asymptotic behavior of agents’ beliefs and provide conditions that enable all agents to correctly identify their true hypotheses. The theoretical analysis is corroborated by numerical simulations.

We consider multi-agent networks that aim at solving, cooperatively and online, distributed optimization problems under communication constraints. We propose the ACTC (Adapt-Compress-Then-Combine) diffusion strategy, which leverages differential randomized compression to infuse the classical ATC strategy with the ability to handle compressed data. We consider the flexible setting of directed graphs and left-stochastic policies, and require strong convexity only at a network level (i.e., some agents might even have non-convex risks). We prove that each agent is able to learn the optimal solution up to a small error on the order of the step-size, achieving remarkable savings in terms of bits exchanged between neighboring agents.

This paper investigates the effect of combination policies on the performance of adaptive social learning in non-stationary environments. By analyzing the relation between the error probability and the underlying graph topology, we prove that in the slow adaptation regime, combination policies with a uniform Perron eigenvector will provide the smallest steady-state error probability. This result indicates that in terms of learning accuracy, doubly-stochastic combination policies yield optimal performance. Moreover, we estimate the adaptation time of adaptive social learning in the small signal-to-noise regime and show that in this regime, the influence of combination policies on the adaptation time is insignificant.

Observations collected by agents in a network may be unreliable due to observation noise or interference. This paper proposes a distributed algorithm that allows each node to improve the reliability of its own observation by relying solely on local computations and interactions with immediate neighbors, assuming that the field (graph signal) monitored by the network lies in a low-dimensional subspace and that a low-rank noise is present in addition to the usual full-rank noise. While oblique projections can be used to project measurements onto a low-rank subspace along a direction that is oblique to the subspace, the resulting solution is not distributed. Starting from the centralized solution, we propose an algorithm that performs the oblique projection of the overall set of observations onto the signal subspace in an iterative and distributed manner. We then show how the oblique projection framework can be extended to handle distributed learning and adaptation problems over networks.

We consider a distributed binary hypothesis testing setup where multiple nodes send quantized information to a central processor, which is oblivious to the nodes’ statistics. We study the regime where the missed detection (type-II error) probability decays exponentially and the false alarm (type-I error) probability vanishes. For memoryless quantization, we characterize a tradeoff curve that yields a lower bound for the feasible region of type-II error exponents and the average number of bits sent under the null hypothesis. Moreover, we show that the tradeoff curve is approached at high rates with lattice quantization.

We study a social learning scheme where at every time instant, each agent chooses to receive information from one of its neighbors at random. We show that under this sparser communication scheme, the agents learn the truth eventually and the asymptotic convergence rate remains the same as the standard algorithms, which use more communication resources. We also derive large deviation estimates of the log-belief ratios for a special case where each agent replaces its belief with that of the chosen neighbor.

We address the challenge of learning factored policies in cooperative MARL scenarios. In particular, we consider the situation in which a team of agents collaborates to optimize a common cost. The goal is to obtain factored policies that determine the individual behavior of each agent so that the resulting joint policy is optimal. The main contribution of this work is the introduction of Logical Team Q-learning (LTQL). LTQL does not rely on assumptions about the environment and hence is generally applicable to any collaborative MARL scenario. We derive LTQL as a stochastic approximation to a dynamic programming method we introduce in this work. We conclude the paper by providing experiments (both in the tabular and deep settings) that illustrate the claims.

This work proposes a new way of combining independently trained classifiers over space and time. Combination over space means that the outputs of spatially distributed classifiers are aggregated. Combination over time means that the classifiers respond to streaming data during testing and continue to improve their performance even during this phase. By doing so, the proposed architecture is able to improve prediction performance over time with unlabeled data. Inspired by social learning algorithms, which require prior knowledge of the observations distribution, we propose a Social Machine Learning (SML) paradigm that is able to exploit the imperfect models generated during the learning phase. We show that this strategy results in consistent learning with high probability, and it yields a robust structure against poorly trained classifiers. Simulations with an ensemble of feedforward neural networks are provided to illustrate the theoretical results.

This work examines the problem of learning the topology of a network (graph learning) from the signals produced at a subset of the network nodes (partial observability). This challenging problem was recently tackled assuming that the topology is drawn according to an Erdős-Rényi model, for which it was shown that graph learning under partial observability is achievable, exploiting in particular homogeneity across nodes and independence across edges. However, several real-world networks do not match the optimistic assumptions of homogeneity/independence, for example, high het-erogeneity is often observed between very connected nodes (hubs) and scarcely connected peripheral nodes. Random graphs with preferential attachment were conceived to overcome these issues. In this work, we discover that, over first-order vector autoregressive systems with a stable Laplacian combination matrix, graph learning is achievable under partial observability, when the network topology is drawn according to a popular preferential attachment model known as the Bollobás-Riordan model.

This paper presents an adaptive combination strategy for distributed learning over diffusion networks. Since learning relies on the collaborative processing of the stochastic information at the dispersed agents, the overall performance can be improved by designing combination policies that adjust the weights according to the quality of the data. Such policies are important because they would add a new degree of freedom and endow multi-agent systems with the ability to control the flow of information over their edges for enhanced performance. Most adaptive and static policies available in the literature optimize certain performance metrics related to steady-state behavior, to the detriment of transient behavior. In contrast, we develop an adaptive combination rule that aims at optimizing the transient learning performance, while maintaining the enhanced steady-state performance obtained using policies previously developed in the literature.

A common assumption in the social learning literature is that agents exchange information in an unselfish manner. In this work, we consider the scenario where a subset of agents aims at driving the network beliefs to the wrong hypothesis. The adversaries are unaware of the true hypothesis. However, they will "blend in" by behaving similarly to the other agents and will manipulate the likelihood functions used in the belief update process to launch inferential attacks. We will characterize the conditions under which the network is misled. Then, we will explain that it is possible for such attacks to succeed by showing that strategies exist that can be adopted by the malicious agents for this purpose. We examine both situations in which the agents have minimal or no information about the network model.

Federated learning involves a mixture of centralized and decentralized processing tasks, where a server regularly selects a sample of the agents and these in turn sample their local data to compute stochastic gradients for their learning updates. The sampling of both agents and data is generally uniform; however, in this work we consider non-uniform sampling. We derive optimal importance sampling strategies for both agent and data selection and show that under convexity and Lipschitz assumptions, non-uniform sampling without replacement improves the performance of the original FedAvg algorithm. We run experiments on a regression and classification problem to illustrate the theoretical results.

Decentralized algorithms for stochastic optimization and learning rely on the diffusion of information through repeated local exchanges of intermediate estimates. Such structures are particularly appealing in situations where agents may be hesitant to share raw data due to privacy concerns. Nevertheless, in the absence of additional privacy-preserving mechanisms, the exchange of local estimates, which are generated based on private data can allow for the inference of the data itself. The most common mechanism for guaranteeing privacy is the addition of perturbations to local estimates before broadcasting. These perturbations are generally chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible (to first order in the step-size) to the network centroid, while preserving privacy guarantees. The analysis allows for general nonconvex loss functions, and is hence applicable to a large number of machine learning and signal processing problems, including deep learning.

This work proposes a novel strategy for social learning by introducing the critical feature of adaptation. In social learning, several distributed agents update continually their belief about a phenomenon of interest through: i) direct observation of streaming data that they gather locally; and ii) diffusion of their beliefs through local cooperation with their neighbors. Traditional social learning implementations are known to learn well the underlying hypothesis (which means that the belief of every individual agent peaks at the true hypothesis), achieving steady improvement in the learning accuracy under stationary conditions. However, these algorithms do not perform well under nonstationary conditions commonly encountered in online learning, exhibiting a significant inertia to track drifts in the streaming data. In order to address this gap, we propose an Adaptive Social Learning (ASL) strategy, which relies on a small step-size parameter to tune the adaptation degree. First, we provide a detailed characterization of the learning performance by means of a steady-state analysis. Focusing on the small step-size regime, we establish that the ASL strategy achieves consistent learning under standard global identifiability assumptions. We derive reliable Gaussian approximations for the probability of error (i.e., of choosing a wrong hypothesis) at each individual agent. We carry out a large deviations analysis revealing the universal behavior of adaptive social learning: the error probabilities decrease exponentially fast with the inverse of the step-size, and we characterize the resulting exponential learning rate. Second, we characterize the adaptation performance by means of a detailed transient analysis, which allows us to obtain useful analytical formulas relating the adaptation time to the step-size. The revealed dependence of the adaptation time and the error probabilities on the step-size highlights the fundamental trade-off between adaptation and learning emerging in adaptive social learning.

Adaptation and learning over multi-agent networks is a topic of great relevance with important implications. Elaborating on previous works on single-task networks engaged in decision problems, here we consider the multi-task version in the challenging scenario where the state of nature may change arbitrarily. We propose a data diffusion scheme for tracking these changes in real time, and investigate by numerical simulations the corresponding steady-state decision performance. For the slow-adaptation regime, the complete analytical characterization of the agents' status is provided, under the simplifying assumption that the network connection matrix is correctly estimated.

This work studies the learning abilities of agents sharing partial beliefs over social networks. The agents observe data that could have risen from one of several hypotheses and interact locally to decide whether the observations they are receiving have risen from a particular hypothesis of interest. To do so, we establish the conditions under which it is sufficient to share partial information about the agents' belief in relation to the hypothesis of interest. Some interesting convergence regimes arise.

In social learning, agents form their opinions or beliefs about certain hypotheses by exchanging local information. This work considers the recent paradigm of weak graphs, where the network is partitioned into sending and receiving components, with the former having the possibility of exerting a domineering effect on the latter. Such graph structures are prevalent over social platforms. We will not be focusing on the direct social learning problem (which examines what agents learn), but rather on the dual or reverse learning problem (which examines how agents learned). Specifically, from observations of the stream of beliefs at certain agents, we would like to examine whether it is possible to learn the strength of the connections (influences) from sending components in the network to these receiving agents.

Under appropriate cooperation protocols and parameter choices, fully decentralized solutions for stochastic optimization have been shown to match the performance of centralized solutions and result in linear speedup (in the number of agents) relative to non-cooperative approaches in the strongly-convex setting. More recently, these results have been extended to the pursuit of first-order stationary points in non-convex environments. In this work, we examine in detail the dependence of second-order convergence guarantees on the spectral properties of the combination policy for non-convex multi agent optimization. We establish linear speedup in saddle-point escape time in the number of agents for symmetric combination policies and study the potential for further improvement by employing asymmetric combination weights. The results imply that a linear speedup can be expected in the pursuit of second-order stationary points, which exclude local maxima as well as strict saddle-points and correspond to local or even global minima in many important learning settings.

This special issue provides a comprehensive overview of modern optimization tools and methods for the purposes of data-driven learning and control.

Many optimization, inference, and learning tasks can be accomplished efficiently by means of decentralized processing algorithms where the network topology (i.e., the graph) plays a critical role in enabling the interactions among neighboring nodes. There is a large body of literature examining the effect of the graph structure on the performance of decentralized processing strategies. In this article, we examine the inverse problem and consider the reverse question: How much information does observing the behavior at the nodes of a graph convey about the underlying topology? For large-scale networks, the difficulty in addressing such inverse problems is compounded by the fact that usually only a limited fraction of the nodes can be probed, giving rise to a second important question: Despite the presence of unobserved nodes, can partial observations still be sufficient to discover the graph linking the probed nodes? The article surveys recent advances on this challenging learning problem and related questions.

We study the problem of distributed estimation over adaptive networks where communication delays exist between nodes. In particular, we investigate the diffusion Least-Mean-Square (LMS) strategy where delayed intermediate estimates (due to the communication channels) are employed during the combination step. One important question is: Do the delays affect the stability condition and performance? To answer this question, we conduct a detailed performance analysis in the mean and in the mean-square-error sense of the diffusion LMS with delayed estimates. Stability conditions, transient and steady-state mean-square-deviation (MSD) expressions are provided. One of the main findings is that diffusion LMS with delays can still converge under the same step-sizes condition of the diffusion LMS without delays. Finally, simulation results illustrate the theoretical findings.

The utilization of online stochastic algorithms is popular in large-scale learning settings due to their ability to compute updates on the fly, without the need to store and process data in large batches. When a constant step-size is used, these algorithms also have the ability to adapt to drifts in problem parameters, such as data or model properties, and track the optimal solution with reasonable accuracy. Building on analogies with the study of adaptive filters, we establish a link between steady-state performance derived under stationarity assumptions and the tracking performance of online learners under random walk models. The link allows us to infer the tracking performance from steady-state expressions directly and almost by inspection.

This article studies the problem of reconstructing the topology of a network of interacting agents via observations of the state-evolution of the agents. We focus on the large-scale network setting with the additional constraint of partial observations, where only a small fraction of the agents can be feasibly observed. The goal is to infer the underlying subnetwork of interactions and we refer to this problem as local tomography. In order to study the large-scale setting, we adopt a proper stochastic formulation where the unobserved part of the network is modeled as an Erdös-Rényi random graph, while the observable subnetwork is left arbitrary. The main result of this work is to establish that, under this setting, local tomography is actually possible with high probability, provided that certain conditions on the network model are met (such as stability and symmetry of the network combination matrix). Remarkably, such conclusion is established under the low-observability regime, where the cardinality of the observable subnetwork is fixed, while the size of the overall network scales to infinity.

This work presents a fully distributed algorithm for learning the optimal policy in a multi-agent cooperative reinforcement learning scenario. We focus on games that can only be solved through coordinated team work. We consider situations in which K players interact simultaneously with an environment and with each other to attain a common goal. In the algorithm, agents only communicate with other agents in their immediate neighborhood and choose their actions independently of one another based only on local information. Learning is done off-policy, which results in high data efficiency. The proposed algorithm is of the stochastic primal-dual kind and can be shown to converge even when used in conjunction with a wide class of function approximators.

We consider a distributed social learning problem where a network of agents is interested in selecting one among a finite number of hypotheses. The data collected by the agents might be heterogeneous, meaning that different sub-networks might observe data generated by different hypotheses. For example, some sub-networks might be receiving (or even intentionally generating) data from a fake hypothesis and will bias the rest of the network via social influence. This work focuses on a two-step diffusion algorithm where each agent: i) first updates individually its belieffunction using its private data; ii) then computes a new belief function by exponentiating a linear combination of the log-beliefs of its neighbors. We obtain analytical formulas that reveal how the agents' detection capability and the network topology interplay to influence the asymptotic beliefs of the agents. Some interesting behaviors arise, such as the “mind-control” effect or the “truth-is-somewhere-in-between” effect.

This paper considers optimization problems over networks where agents have individual objectives to meet, or individual parameter vectors to estimate, subject to subspace constraints that enforce the objectives across the network to lie in a low-dimensional subspace. This constrained formulation includes consensus optimization as a special case, and allows for more general task relatedness models such as smoothness. While such formulations can be solved via projected gradient descent, the resulting algorithm is not distributed. Motivated by the centralized solution, we propose an iterative and distributed implementation of the projection step, which runs in parallel with the gradient descent update. We establish that, for small step-sizes µ, the proposed distributed adaptive strategy leads to small estimation errors on the order of µ.

Driven by the need to solve increasingly complex optimization problems in signal processing and machine learning, recent years have seen rising interest in the behavior of gradient-descent based algorithms in non-convex environments. Most of the works on distributed non-convex optimization focus on the deterministic setting, where exact gradients are available at each agent. In this work, we consider stochastic cost functions, where exact gradients are replaced by stochastic approximations and the resulting gradient noise persistently seeps into the dynamics of the algorithm. We establish that the diffusion algorithm continues to yield meaningful estimates in these more challenging, non-convex environments, in the sense that (a) despite the distributed implementation, restricted to local interactions, individual agents cluster in a small region around a common and well-defined vector, which will carry the interpretation of a network centroid, and (b) the network centroid inherits many properties of the centralized, stochastic gradient descent recursion, including the return of an O(μ)-mean-square-stationary point in at most O(1/μ2) iterations.

In this paper, we develop a stochastic-gradient learning algorithm for situations involving streaming data that arise from an underlying clustered structure. In such settings, the variance of gradient noise can be decomposed into the in-cluster variance σin2plus the between-cluster variance σbet2. We develop a cluster-based online variancereduced method (COVER) to eliminate σbet2and improve the MSD performance of stochastic-gradient descent (SGD) to the order of O(σin2). We establish the convergence property of COVER and derive a tight closed-form mean-square deviation (MSD) performance expression. Our simulations illustrate the improved performance of COVER in terms of steady-state performance.

In this work we consider the problem of learning an Erdös-Rényi graph over a diffusion network when: i) data from only a limited subset of nodes are available (partial observation); ii) and the inferential goal is to discover the graph of interconnections linking the accessible nodes (local structure learning). We propose three matrix estimators, namely, the Granger, the one-lag correlation, and the residual estimators, which, when followed by a universal clustering algorithm, are shown to retrieve the true subgraph in the limit of large network sizes. Remarkably, it is seen that a fundamental role is played by the uniform concentration of node degrees, rather than by sparsity.

Decentralized optimization is a powerful paradigm that finds applications in engineering and learning design. This work studies decentralized composite optimization problems with non-smooth regularization terms. Most existing gradient-based proximal decentralized methods are known to converge to the optimal solution with sublinear rates, and it remains unclear whether this family of methods can achieve global linear convergence. To tackle this problem, this work assumes the non-smooth regularization term is common across all networked agents, which is the case for many machine learning problems. Under this condition, we design a proximal gradient decentralized algorithm whose fixed point coincides with the desired minimizer. We then provide a concise proof that establishes its linear convergence. In the absence of the non-smooth term, our analysis technique covers the well known EXTRA algorithm and provides useful bounds on the convergence rate and step-size.

This letter proposes a general regularization framework for inference over multitask networks. The optimization approach relies on minimizing a global cost consisting of the aggregate sum of individual costs regularized by a term that allows to incorporate global information about the graph structure and the individual parameter vectors into the solution of the inference problem. An adaptive strategy, which responds to streaming data and employs stochastic approximations in place of actual gradient vectors, is devised and studied. Methods allowing the distributed implementation of the regularization step are also discussed. This letter shows how to blend real-time adaptation with graph filtering and a generalized regularization framework to result in a graph diffusion strategy for distributed learning over multitask networks.

This paper studies the operation of multi-agent networks engaged in binary decision tasks, and derives performance expressions and performance operating curves under challenging conditions with some revealing insights. One of the main challenges in the analysis is that agents are only allowed to exchange one-bit messages, and the information at each agent therefore consists of both continuous and discrete components. Due to this mixed nature, the steady-state distribution of the state of each agent cannot be inferred from direct application of central limit arguments. Instead, the behavior of the continuous component is characterized in integral form by using a log-characteristic function, while the behavior of the discrete component is characterized by means of an asymmetric Bernoulli convolution. By exploiting these results, this paper derives reliable approximate performance expressions for the network nodes that match well with the simulated results for a wide range of system parameters. The results also reveal an important interplay between continuous adaptation under constant step-size learning and the binary nature of the messages exchanged with neighbors.

This paper studies the problem of inferring whether an agent is directly influenced by another agent over a network. Agent i influences agent j if they are connected (according to the network topology), and if agent j uses the data from agent i to update its online learning algorithm. The solution of this inference task is challenging for two main reasons. First, only the output of the learning algorithm is available to the external observer that must perform the inference based on these indirect measurements. Second, only output measurements from a fraction of the network agents is available, with the total number of agents itself being also unknown. The main focus of this paper is ascertaining under these demanding conditions whether consistent tomography is possible, namely, whether it is possible to reconstruct the interaction profile of the observable portion of the network, with negligible error as the network size increases. We establish a critical achievability result, namely, that for symmetric combination policies and for any given fraction of observable agents, the interacting and non-interacting agent pairs split into two separate clusters as the network size increases. This remarkable property then enables the application of clustering algorithms to identify the interacting agents influencing the observations. We provide a set of numerical experiments that verify the results for finite network sizes and time horizons. The numerical experiments show that the results hold for asymmetric combination policies as well, which is particularly relevant in the context of causation.

This work develops an effective distributed algorithm for the solution of stochastic optimization problems that involve partial coupling among both local constraints and local cost functions. While the collection of networked agents is interested in discovering a global model, the individual agents are sensing data that is only dependent on parts of the model. Moreover, different agents may be dependent on different subsets of the model. In this way, cooperation is justified and also necessary to enable recovery of the global information. In view of the local constraints, we show how to relax the optimization problem to a penalized form, and how to enable cooperation among neighboring agents. We establish mean-square-error convergence of the resulting strategy for sufficiently small step-sizes and large penalty factors. We also illustrate performance by means of simulations.

This work studies the problem of inferring from streaming data whether an agent is directly influenced by another agent over an adaptive network of interacting agents. Agent i influences agent j if they are connected, and if agent j uses the information from agent i to update its inference. The solution of this inference task is challenging for at least two reasons. First, only the output of the learning algorithm is available to the external observer and not the raw data. Second, only observations from a fraction of the network agents is available, with the total number of agents itself being also unknown. This work establishes, under reasonable conditions, that consistent tomography is possible, namely, that it is possible to reconstruct the interaction profile of the observable portion of the network, with negligible error as the network size increases. We characterize the decaying behavior of the error with the network size, and provide a set of numerical experiments to illustrate the results.

Most works on graph signal processing assume static graph signals, which is a limitation even in comparison to traditional DSP techniques where signals are modeled as sequences that evolve over time. For broader applicability, it is necessary to develop techniques that are able to process dynamic or streaming data. Many earlier works on adaptive networks have addressed problems related to this challenge by developing effective strategies that are particularly well-suited to data streaming into graphs. We are thus faced with two paradigms: one where signals are modeled as static and sitting on the graph nodes, and another where signals are modeled as dynamic and streaming into the graph nodes. The objective of this work is to blend these concepts and propose diffusion strategies for adaptively learning from streaming graph signals.

Several useful variance-reduced stochastic gradient algorithms, such as SVRG, SAGA, Finito, and SAG, have been proposed to minimize empirical risks with linear convergence properties to the exact minimizers. The existing convergence results assume uniform data sampling with replacement. However, it has been observed that random reshuffling can deliver superior performance and, yet, no formal proofs or guarantees of exact convergence exist for variance-reduced algorithms under random reshuffling. This paper makes two contributions. First, it resolves this open issue and provides the first theoretical guarantee of linear convergence under random reshuffling for SAGA; the argument is also adaptable to other variance-reduced algorithms. Second, under random reshuffling, the paper proposes a new amortized variance-reduced gradient (AVRG) algorithm with constant storage requirements compared to SAGA and with balanced gradient computations compared to SVRG. AVRG is also shown analytically to converge linearly.

This work considers a diffusion network responding to streaming data, and studies the problem of identifying the topology of a subnetwork of observable agents by tracking their output measurements. Topology inference from indirect and/or incomplete datasets (network tomography) is in general an ill-posed problem. Under an appropriate Erdos-Renyi random graph model for the unobserved part, the problem of network tomography is well-posed in the thermodynamic limit: when the number of network agents grows to infinity, any arbitrary subnetwork topology associated with the observed agents can be recovered with high probability.

In diffusion social learning over weakly-connected graphs, it has been shown that influential agents end up shaping the beliefs of non-influential agents. In this paper, we analyse this control mechanism more closely and reveal some critical properties. In particular, we characterize the set of beliefs that can be imposed on non-influential agents (i.e., the set of attainable beliefs) and how the graph topology of these latter agents helps resist manipulation but only to a certain degree. We also derive a design procedure that allows influential agents to drive the beliefs of non-influential agents to desirable attainable states. We illustrate the results with two examples.

Using duality arguments from optimization theory, this work develops an effective distributed gradient boosting strategy for inference and classification by networked clusters of learners. By sharing local dual variables with their immediate neighbors through a diffusion learning protocol, the clusters are able to match the performance of centralized boosting solutions even when the individual clusters only have access to partial information about the feature space.

In many scenarios of interest, agents may only have access to partial information about an unknown model or target vector. Each agent may be sensing only a subset of the entries of a global target vector, and the number of these entries can be different across the agents. If each of the agents were to solve an inference task independently of the other agents, then they would not benefit from neighboring agents that may be sensing similar entries. This work develops cooperative distributed techniques that enable agents to cooperate even when their interactions are limited to exchanging estimates of select few entries. In the proposed strategies, agents are only required to share estimates of their common entries, which results in a significant reduction in communication overhead. Simulations show that the proposed approach improves both the performance of individual agents and the entire network through cooperation.

Considering groups of variables, rather than variables individually, can be beneficial for estimation accuracy if structural relationships between variables exist (e.g., spatial, hierarchical or related to the physics of the problem). Group-sparsity inducing estimators are typical examples that benefit from such type of prior knowledge. Building on this principle, we show that the diffusion LMS algorithm for distributed inference over networks can be extended to deal with structured criteria built upon groups of variables, leading to a flexible framework that can encode various structures in the parameters to estimate. We also propose an unsupervised online strategy to differentially promote or inhibit collaborations between nodes depending on the group of variables at hand.

Diffusion LMS is an efficient strategy for solving distributed optimization problems with cooperating agents. In some applications, the optimum parameter vectors may not be the same for all agents. Moreover, agents usually exchange information through noisy communication links. In this work, we analyze the theoretical performance of the single-task diffusion LMS when it is run, intentionally or unintentionally, in a multitask environment in the presence of noisy links. To reduce the impact of these nuisance factors, we introduce an improved strategy that allows the agents to promote or reduce exchanges of information with their neighbors.

In this paper, we study diffusion social learning over weakly-connected graphs. We show that the asymmetric flow of information hinders the learning abilities of certain agents regardless of their local observations. Under some circumstances that we clarify in this work, a scenario of total influence (or "mind-control") arises where a set of influential agents ends up shaping the beliefs of non-influential agents. We derive useful closed-form expressions that characterize this influence, and which can be used to motivate design problems to control it. We provide simulation examples to illustrate the results.

We develop an effective distributed strategy for seeking the Pareto solution of an aggregate cost consisting of regularized risks. The focus is on stochastic optimization problems where each risk function is expressed as the expectation of some loss function and the probability distribution of the data is unknown. We assume each risk function is regularized and allow the regularizer to be non-smooth. Under conditions that are weaker than assumed earlier in the literature and, hence, applicable to a broader class of adaptation and learning problems, we show how the regularizers can be smoothed and how the Pareto solution can be sought by appealing to a multi-agent diffusion strategy. The formulation is general enough and includes, for example, a multi-agent proximal strategy as a special case.

This work examines the performance of stochastic sub-gradient learning strategies, for both cases of stand-alone and networked agents, under weaker conditions than usually considered in the literature. It is shown that these conditions are automatically satisfied by several important cases of interest, including support-vector machines and sparsity-inducing learning solutions. The analysis establishes that sub-gradient strategies can attain exponential convergence rates, as opposed to sub-linear rates, and that they can approach the optimal solution within O(p), for sufficiently small step-sizes, p. A realizable exponential-weighting procedure is proposed to smooth the intermediate iterates and to guarantee these desirable performance properties.

This work examines a stochastic formulation of the generalized Nash equilibrium problem (GNEP) where agents are subject to randomness in the environment of unknown statistical distribution. Three stochastic gradient strategies are developed by relying on a penalty-based approach where the constrained GNEP formulation is replaced by a penalized unconstrained formulation. It is shown that this penalty solution is able to approach the Nash equilibrium in a stable manner within O(p), for small step-size values p. The operation of the algorithms is illustrated by considering the Cournot competition problem.

This paper examines the convergence rate and mean-square-error performance of momentum stochastic gradient methods in the constant step-size and slow adaptation regime. The results establish that momentum methods are equivalent to the standard stochastic gradient method with a re-scaled (larger) step-size value. The equivalence result is established for all time instants and not only in steady-state. The analysis is carried out for general risk functions, and is not limited to quadratic risks. One notable conclusion is that the well-known benefits of momentum constructions for deterministic optimization problems do not necessarily carry over to the stochastic setting when gradient noise is present and continuous adaptation is necessary. The analysis suggests a method to enhance performance in the stochastic setting by tuning the momentum parameter over time.

The article examines in some detail the convergence rate and mean-square-error performance of momentum stochastic gradient methods in the constant step-size and slow adaptation regime. The results establish that momentum methods are equivalent to the standard stochastic gradient method with a re-scaled (larger) step-size value. The size of the re-scaling is determined by the value of the momentum parameter. The equivalence result is established for all time instants and not only in steady-state. The analysis is carried out for general strongly convex and smooth risk functions, and is not limited to quadratic risks. One notable conclusion is that the well-known benefits of momentum constructions for deterministic optimization problems do not necessarily carry over to the adaptive online setting when small constant step-sizes are used to enable continuous adaptation and learning in the presence of persistent gradient noise. From simulations, the equivalence between momentum and standard stochastic gradient methods is also observed for non-differentiable and non-convex problems.

This paper examines the close interplay between cooperation and adaptation for distributed detection schemes over fully decentralized networks. The combined attributes of cooperation and adaptation are necessary to enable networks of detectors to continually learn from streaming data and to continually track drifts in the state of nature when deciding in favor of one hypothesis or another. The results in this paper establish a fundamental scaling law for the steady-state probabilities of miss detection and false alarm in the slow adaptation regime, when the agents interact with each other according to distributed strategies that employ small constant step-sizes. The latter are critical to enable continuous adaptation and learning. This paper establishes three key results. First, it is shown that the output of the collaborative process at each agent has a steady-state distribution. Second, it is shown that this distribution is asymptotically Gaussian in the slow adaptation regime of small step-sizes. Third, by carrying out a detailed large deviations analysis, closed-form expressions are derived for the decaying rates of the false-alarm and miss-detection probabilities. Interesting insights are gained from these expressions. In particular, it is verified that as the step-size μ decreases, the error probabilities are driven to zero exponentially fast as functions of 1μ, and that the exponents governing the decay increase linearly in the number of agents. It is also verified that the scaling laws governing the errors of detection and the errors of estimation over the network behave very differently, with the former having exponential decay proportional to 1μ, while the latter scales linearly with decay proportional to μ. Moreover, and interestingly, it is shown that the cooperative strategy allows each agent to reach the same detection performance, in terms of detection error exponents, of a centralized stochastic-gradient solution. The results of this paper are illustrated by applying them to canonical distributed detection problems.

This paper studies the learning ability of consensus and diffusion distributed learners from continuous streams of data arising from different but related statistical distributions. Four distinctive features for diffusion learners are revealed in relation to other decentralized schemes even under left-stochastic combination policies. First, closed-form expressions for the evolution of their excess-risk are derived for strongly convex risk functions under a diminishing step-size rule. Second, using these results, it is shown that the diffusion strategy improves the asymptotic convergence rate of the excess-risk relative to non-cooperative schemes. Third, it is shown that when the in-network cooperation rules are designed optimally, the performance of the diffusion implementation can outperform that of naive centralized processing. Finally, the arguments further show that diffusion outperforms consensus strategies asymptotically and that the asymptotic excess-risk expression is invariant to the particular network topology. The framework adopted in this paper studies convergence in the stronger mean-square-error sense, rather than in distribution, and develops tools that enable a close examination of the differences between distributed strategies in terms of asymptotic behavior, as well as in terms of convergence rates.

This paper examines the learning mechanism of adaptive agents over weakly connected graphs and reveals an interesting behavior on how information flows through such topologies. The results clarify how asymmetries in the exchange of data can mask local information at certain agents and make them totally dependent on other agents. A leader-follower relationship develops with the performance of some agents being fully determined by the performance of other agents that are outside their domain of influence. This scenario can arise, for example, due to intruder attacks by malicious agents or as the result of failures by some critical links. The findings in this paper help explain why strong-connectivity of the network topology, adaptation of the combination weights, and clustering of agents are important ingredients to equalize the learning abilities of all agents against such disturbances. The results also clarify how weak-connectivity can be helpful in reducing the effect of outlier data on learning performance.

We study the performance of diffusion least-mean squares algorithms for distributed parameter estimation in multi-agent networks when nodes exchange information over wireless communication links. Wireless channel impairments, such as fading and path-loss, adversely affect the exchanged data and cause instability and performance degradation if left unattended. To mitigate these effects, we incorporate equalization coefficients into the diffusion combination step and update the combination weights dynamically in the face of randomly changing neighborhoods due to fading conditions. When channel state information (CSI) is unavailable, we determine the equalization factors from pilot-aided channel coefficient estimates. The analysis reveals that by properly monitoring the CSI over the network and choosing sufficiently small adaptation step-sizes, the diffusion strategies are able to deliver satisfactory performance in the presence of fading and path loss.

In [1], an important step toward the characterization of distributed detection over adaptive networks has been made by establishing the fundamental scaling law of the error probabilities. However, empirical evidence reported in [1] revealed that a refined asymptotic analysis is necessary in order to capture the exact impact of network connectivity on the detection performance of each individual agent. Here we address this open issue by exploiting the framework of exact asymptotics.

In this work, a diffusion-type algorithm is proposed to solve multitask estimation problems where each cluster of nodes is interested in estimating its own optimum parameter vector in a distributed manner. The approach relies on minimizing a global mean-square error criterion regularized by a term that promotes piecewise constant transitions in the parameter vector entries estimated by neighboring clusters. We provide some results on the mean and mean-square-error convergence. Simulations are conducted to illustrate the effectiveness of the strategy.

This work studies distributed primal-dual strategies for adaptation and learning over networks from streaming data. Two first-order methods are considered based on the Arrow-Hurwicz (AH) and augmented Lagrangian (AL) techniques. Several results are revealed in relation to the performance and stability of these strategies when employed over adaptive networks. It is found that these methods have worse steady-state mean-square-error performance than primal methods of the consensus and diffusion type. It is also found that the AH technique can become unstable under a partial observation model, while the other techniques are able to recover the unknown under this scenario. It is further shown that AL techniques are stable over a narrower range of step-sizes than primal strategies.

We consider networks of agents cooperating to minimize a global objective, modeled as the aggregate sum of regularized costs that are not required to be differentiable. Since the subgradients of the individual costs cannot generally be assumed to be uniformly bounded, general distributed subgradient techniques are not applicable to these problems. We isolate the requirement of bounded subgradients into the regularizer and use splitting techniques to develop a stochastic proximal diffusion strategy for solving the optimization problem by continuously learning from streaming data. We represent the implementation as the cascade of three operators and invoke Banach's fixed-point theorem to establish that, despite gradient noise, the stochastic implementation is able to converge in the mean-square-error sense within O(μ) from the optimal solution, for a sufficiently small step-size parameter, μ.

In this paper, we examine the learning mechanism of adaptive agents over weakly-connected graphs and reveal an interesting behavior on how information flows through such topologies. The results clarify how asymmetries in the exchange of data can mask local information at certain agents and make them totally dependent on other agents. A leader-follower relationship develops with the performance of some agents being fully determined by other agents that can even be outside their immediate domain of influence. This scenario can arise, for example, from intruder attacks by malicious agents or from failures by some critical links. The findings in this work help explain why strong-connectivity of the network topology, adaptation of the combination weights, and clustering of agents are important ingredients to equalize the learning abilities of all agents against such disturbances. The results also clarify how weak-connectivity can be helpful in reducing the effect of outlier data on learning performance.

This paper carries out a detailed transient analysis of the learning behavior of multiagent networks, and reveals interesting results about the learning abilities of distributed strategies. Among other results, the analysis reveals how combination policies influence the learning process of networked agents, and how these policies can steer the convergence point toward any of many possible Pareto optimal solutions. The results also establish that the learning process of an adaptive network undergoes three (rather than two) well-defined stages of evolution with distinctive convergence rates during the first two stages, while attaining a finite mean-square-error level in the last stage. The analysis reveals what aspects of the network topology influence performance directly and suggests design procedures that can optimize performance by adjusting the relevant topology parameters. Interestingly, it is further shown that, in the adaptation regime, each agent in a sparsely connected network is able to achieve the same performance level as that of a centralized stochastic-gradient strategy even for left-stochastic combination strategies. These results lead to a deeper understanding and useful insights on the convergence behavior of coupled distributed learners. The results also lead to effective design mechanisms to help diffuse information more thoroughly over networks.

Part I of this paper examined the mean-square stability and convergence of the learning process of distributed strategies over graphs. The results identified conditions on the network topology, utilities, and data in order to ensure stability; the results also identified three distinct stages in the learning behavior of multiagent networks related to transient phases I and II and the steady-state phase. This Part II examines the steady-state phase of distributed learning by networked agents. Apart from characterizing the performance of the individual agents, it is shown that the network induces a useful equalization effect across all agents. In this way, the performance of noisier agents is enhanced to the same level as the performance of agents with less noisy data. It is further shown that in the small step-size regime, each agent in the network is able to achieve the same performance level as that of a centralized strategy corresponding to a fully connected network. The results in this part reveal explicitly which aspects of the network topology and operation influence performance and provide important insights into the design of effective mechanisms for the processing and diffusion of information over networks.

Diffusion adaptation techniques based on the least-mean-squares criterion have been proposed for distributed detection of a signal in Gaussian-distributed noise, forgoing the need for a fusion center. However, least-mean-squares solutions are generally non-robust against impulsive noise. In this work, we combine nonlinear filtering with diffusion adaptation and propose a strategy for distributed detection in the presence of impulsive noise. The superiority of the algorithm is validated experimentally.

In distributed inference, local cooperation among network nodes can be exploited to enhance the performance of each individual agent, but a challenging requirement for networks operating in dynamic real-world environments is that of adaptation. The interplay between these two fundamental aspects of cooperation and adaptation has been investigated in recent years in the context of estimation problems. Less explored in the literature is the case of detection, which is our focus. Capitalizing on the powerful tool of large deviations analysis, we show how to design and characterize the performance of diffusion strategies that reconcile both needs of adaptation and detection in decentralized systems.

Recent research works on distributed adaptive networks have intensively studied the case where the nodes estimate a common parameter vector collaboratively. However, there are many applications that are multitask-oriented in the sense that there are multiple parameter vectors that need to be inferred simultaneously. In this paper, we employ diffusion strategies to develop distributed algorithms that address clustered multitask problems by minimizing an appropriate mean-square error criterion with ℓ2-regularization. Some results on the mean-square stability and convergence of the algorithm are also provided. Simulations are conducted to illustrate the theoretical findings.

In this paper, we consider learning dictionary models over a network of agents, where each agent is only in charge of a portion of the dictionary elements. This formulation is relevant in big data scenarios where multiple large dictionary models may be spread over different spatial locations and it is not feasible to aggregate all dictionaries in one location due to communication and privacy considerations. We first show that the dual function of the inference problem is an aggregation of individual cost functions associated with different agents, which can then be minimized efficiently by means of diffusion strategies. The collaborative inference step generates local error measures that are used by the agents to update their dictionaries without the need to share these dictionaries or even the coefficient models for the training data. This is a useful property that leads to an efficient distributed procedure for learning dictionaries over large networks.

We show how the convergence time of an adaptive network can be estimated in a distributed manner by the agents. Using this procedure, we propose a distributed mechanism for the nodes to switch from using fixed doubly-stochastic combination weights to adaptive combination weights. By doing so, and by knowing when to switch, the agents are able to enhance their steady-state mean-square-error performance without degrading the rate of convergence during the transient phase of the learning algorithm.

This paper surveys recent advances related to adaptation, learning, and optimization over networks. Various distributed strategies are discussed that enable a collection of networked agents to interact locally in response to streaming data and to continually learn and adapt to track drifts in the data and models. Under reasonable technical conditions on the data, the adaptive networks are shown to be mean square stable in the slow adaptation regime, and their mean square error performance and convergence rate are characterized in terms of the network topology and data statistical moments. Classical results for single-agent adaptation and learning are recovered as special cases. The performance results presented in this work are useful in comparing network topologies against each other, and in comparing adaptive networks against centralized or batch implementations. The presentation is complemented with various examples linking together results from various domains.

The research community is witnessing expansive efforts aimed at understanding one of the most wondrous manifestations of cognition in nature. The Blue Brain Project and the Human Brain Project in Europe are examples of ambitious drives aimed at building a virtual brain machine and at understanding the complexities of the human brain. In the United States, the recently launched Brain Initiative aspires to understand the dynamics of the billions of neurons in the brain at the cellular level. These are laudable efforts that will likely lead to new insights and treatment methods. They will also influence progress in many supporting disciplines including biology, chemistry, physics, and engineering. We are only touching the surface of this immense landscape and even today, we continue to have limited understanding of how networks of simple neurons are capable of producing so much sophistication. It is an astounding feat that elements with limited sensing and processing abilities, interacting locally, are able to transcend into a complex system with superior sensing and cognitive abilities at the higher level.

We propose a distributed least-mean squares (LMS) procedure based on a diffusion strategy for localization and tracking of mobile terminals in cellular networks. In the proposed algorithm, collaborating base stations measure two sets of parameters, namely, the received signal strength (RSS) and the signal propagation time (SPT) to estimate mobile locations. The proposed algorithm has a simple operational structure, offers agile tracking performance and helps the network to save energy and radio resources by benefiting from its decentralized and adaptive signal processing features.

This work examines the flow of information among electrodes attached to the brain and uses diffusion adaptation strategies to assess brain cortical connectivity. The method uses the directed transfer function (DTF) technique to estimate combination coefficients to drive the adaptation and learning process. The diffusion strategy is then applied to the problem of recognizing left and right hand movements and its superior performance is demonstrated relative to solutions that rely on stand-alone electrodes and do not exploit coordination among multiple electrodes.

We apply diffusion strategies to propose a cooperative reinforcement learning algorithm, in which agents in a network communicate with their neighbors to improve predictions about their environment. The algorithm is suitable to learn off-policy even in large state spaces. We provide a mean-square-error performance analysis under constant step-sizes. The gain of cooperation in the form of more stability and less bias and variance in the prediction error, is illustrated in the context of a classical model. We show that the improvement in performance is especially significant when the behavior policy of the agents is different from the target policy under evaluation.

One major source of nonlinear distortion in analog-to-digital converters (ADCs) is clipping. The problem introduces spurious noise across the bandwidth of the sampled data. Prior works recover the signal from the acquired samples by relying on oversampling or on the assumption of vacant frequency bands and on the use of sparse signal representations. In this work, we propose a different approach, which uses two streams of data to mitigate the clipping distortion. Simulation results show an SNR improvement of 9dB, while the conventional approaches may even degrade the SNR in some situations.

We study the distributed inference task over regression and classification models where the likelihood function is strongly log-concave. We show that diffusion strategies allow the KL divergence between two likelihood functions to converge to zero at the rate 1/Ni on average and with high probability, where N is the number of nodes in the network and i is the number of iterations. We derive asymptotic expressions for the expected regularized KL divergence and show that the diffusion strategy can outperform both non-cooperative and conventional centralized strategies, since diffusion implementations can weigh a node's contribution in proportion to its noise level.

This work proposes a strategy to adjust the combination weights of an adaptive network in order to attain both faster convergence during the transient phase and lower mean-square-error during the steady-state phase. Optimal combination weights are designed for both phases, and a procedure for detecting the transition from one phase to the other is also described. Simulation results illustrate the operation of the proposed strategy.

This work shows how the combination weights of diffusion strategies for adaptation and learning over networks can be chosen in order for the network mean-square-error performance to match that of an optimized centralized (or batch) solution. The results show that this is possible regardless of the network topology, however sparse it is, as long as the network is connected without disjoint sub-graphs.

We propose a modified diffusion strategy for parameter estimation in sensor networks where nodes exchange information over fading wireless channels. We show that the effect of fading can be mitigated by incorporating local equalization coefficients into the diffusion process. We explain how the equalization coefficients are chosen and show that the (mean) stability of the network continues to be insensitive to the choice of the combination weights and to the network topology. Our computer experiments demonstrate that the performance of the modified diffusion algorithm in fading scenario is nearly identical to that of centralized least-mean square (LMS) with equalized input data.

The goal of this letter is to propose an adaptive and distributed approach to cooperative sensing for wireless small cell networks. The method uses a basis expansion model of the power spectral density (PSD) to be estimated, and exploits spectral sparsity to improve estimation accuracy and adaptation capabilities. An estimator of the model coefficients is developed based on sparse diffusion strategies, which are able to exploit and track sparsity while at the same time processing data in real-time and in a fully decentralized manner. Simulation results illustrate the advantages of the proposed sparsity-aware strategies for cooperative spectrum sensing applications.

We derive an adaptive diffusion mechanism to optimize global cost functions in a distributed manner over a network of nodes. The cost function is assumed to consist of the sum of individual components, and diffusion adaptation is used to enable the nodes to cooperate locally through in-network processing in order to solve the desired optimization problem. We analyze the mean-square-error performance of the algorithm, including its transient and steady-state behavior. We illustrate one application in the context of least-mean-squares estimation for sparse vectors.

The goal of this paper is to propose diffusion LMS techniques for distributed estimation over adaptive networks, which are able to exploit sparsity in the underlying system model. The approach relies on convex regularization, common in compressive sensing, to improve the performance of the diffusion strategies. We provide convergence and performance analysis of the proposed method, showing under what conditions it outperforms the unregularized diffusion version. Simulation results illustrate the advantage of the proposed filter under the sparsity assumption on the true coefficient vector.

We propose an adaptive diffusion strategy with limited communication overhead by cutting off all links but one for each node in the network. We keep the “best” neighbor that has the smallest estimated variance-product measure and ignore the other neighbors. The combination coefficients for the interacting nodes are calculated via a maximal-ratio-combining rule to minimize the steady-state meansquare-deviation. Simulation results illustrate that, with less communication overhead and less computations, the proposed algorithm performs well and outperforms other related methods with similar overheads.

This work develops a decentralized adaptive strategy for throughput maximization over peer-to-peer (P2P) networks. The adaptive strategy can cope with changing network topologies, is robust to network disruptions, and does not rely on central processors. The algorithm is obtained as a special case of a more general diffusion strategy for the distributed solution of optimization problems with constraints. Simulation results illustrate how the proposed technique is competitive with other methods.

Adaptive networks rely on in-network and collaborative processing among distributed agents to deliver enhanced performance in estimation and inference tasks. Information is exchanged among the nodes, usually over noisy links. This paper first investigates the mean-square performance of adaptive diffusion algorithms in the presence of various sources of imperfect information exchanges and quantization errors. Among other results, the analysis reveals that link noise over the regression data modifies the dynamics of the network evolution, and leads to biased estimates in steady-state. The analysis also reveals how the network mean-square performance is dependent on the combination weight matrices. We use these observations to show how the combination weights can be optimized and adapted. Simulation results illustrate the theoretical findings and match well with theory.

In biological systems, animals exhibit organized behavior that arises from localized interactions. The interaction is implemented through information exchange, either directly or indirectly. Adaptive networks, consisting of a collection of nodes with learning abilities that interact with each other to solve distributed inference problems in real-time, are well-suited to model these kinds of behavior. Usually the information exchange between two nodes is imperfect and the data from neighbors are noisy. In this paper, we examine the effect of noisy communication links on network performance and derive an optimal strategy for adjusting the combination weights.

Inspired by bacterial motility, we propose an algorithm for adaptation over networks with mobile nodes. The nodes have limited abilities and they are allowed to cooperate with their neighbors to optimize a common objective function. In contrast to traditional adaptation formulations, an important consideration in this work is the fact that the nodes do not know the form of the cost function beforehand. The nodes can only sense variations in the values of the objective function as they diffuse through the space, such as sensing the variation in the concentration of nutrients in the environment. We propose a technique for the nodes to pick the search vector as a linear combination of the neighbors' last steps, by attempting to maximize the nutritional gradient. The procedure enables information to flow from "information-rich" nodes to the other nodes.

In a non-ideal PLL circuit, leakage of the reference signal into the control line produces spurious tones. When the distorted PLL signal is used as a clock signal, it creates spurious tones in the sampled data. Our prior work used a training signal to estimate the distortions and then correct the samples. In this work, we propose an alternative approach that estimates and removes the distortions directly from the sampled data without a training signal. Simulations indicate that the proposed solution is able to reduce the root-mean-square (RMS) sampling errors to about 15% of the original values.

Mobile adaptive networks consist of a collection of nodes with learning and motion abilities that interact with each other locally in order to solve distributed processing and distributed inference problems in real-time. In this paper, we develop adaptation algorithms that exhibit self-organization properties and apply them to the model of cooperative hunting among predators. The results help provide an explanation for the agile adjustment of network patterns in the interaction between fish schools and predators.

In this work we analyze the mean-square performance of different strategies for adaptation over two-node least-mean-squares (LMS) networks. The results highlight some interesting properties for adaptive networks in comparison to centralized solutions. The analysis reveals that the adapt-then-combine (ATC) adaptive network algorithm can achieve lower excess-mean-square-error (EMSE) than a centralized solution that is based on either block or incremental LMS strategies with the same convergence rate.

In a non-ideal PLL circuit, leakage of the reference signal into the control line produces spurious tones. When the distorted PLL signal is used in an analog-to-digital converter (ADC), it creates spurious tones in the sampled data as well. In spectrum sensing applications, the presence of spurious tones can lead to false detection of signals in otherwise empty channels. In a typical spectrum sensing application, there usually exists a Fourier transform block. We propose an algorithm to use this block to estimate the jitter errors from the spurious sidebands and to compensate the distorted samples in the digital domain. Index Terms-PLL, sideband suppression, spurious tones.

Clock timing jitter refers to random perturbations in the sampling time in analog-to-digital converters (ADCs). The perturbations are caused by circuit imperfections in the sampling clock. This paper analyzes the effect of sampling clock jitter on the acquired samples in the midst of quantization noise and random Gaussian noise. The paper proposes a method for estimating the jitter for cognitive radio architectures at high sampling rates. The paper also examines the fixed- point implementation of the algorithm and its theoretical performance.

An adaptive diffusion augmented complex least mean square (D-ACLMS) algorithm for collaborative processing of the generality of complex signals over distributed networks is proposed. The algorithm enables the estimation of both second order circular (proper) and noncircular (improper) signals within a unified framework of augmented complex statistics. The analysis shows that the performance advantage of the widely linear D-ACLMS over the strictly linear D-CLMS increases with the degree of noncircularity while maintaining similar performance for proper data. Simulations on both synthetic benchmark and real world noncircular data support the approach.

Spectrum sensing is one of the enabling functionalities for cognitive radio systems to operate in the spectrum white space. To protect the primary incumbent users from interference, the cognitive radio is required to detect incumbent signals at very low signal-to-noise ratio (SNR). In this paper, we study a spectrum sensing technique based on spectral correlation for detection of television (TV) broadcasting signals. The basic strategy is to correlate the periodogram of the received signal with the a priori known spectral features of the primary signal. We show that this sensing technique is asymptotically equivalent to the likelihood ratio test (LRT) at very low SNR, but with less computational complexity. That is, the spectral correlation-based detector is asymptotically optimal according to the Neyman-Pearson criterion. From the system design perspective, we analyze the effect of the spectral features on the spectrum sensing performance. Through the optimization analysis, we obtain useful insights on how to choose effective spectral features to achieve reliable sensing. Simulation results show that the proposed sensing technique can reliably detect analog and digital TV signals at SNR levels as low as -20 dB.

We study the problem of distributed state-space estimation, where a set of nodes are required to estimate the state of a nonlinear state-space system based on their observations. We extend our previous work on distributed Kalman filtering to the nonlinear case, and propose algorithms for Extended and Unscented Kalman filtering. The resulting algorithms are robust to node and link failure, scalable, and fully distributed, in the sense that no fusion center is required, and nodes communicate with their neighbors only. We apply the algorithms to the problem of estimating the position of every node in an ad-hoc network, also known as wireless localization. Simulation results illustrate the performance of the proposed algorithms.

In this paper, we design cooperative beamforming weights for source, relay and destination nodes based on a minimum means-quare-error (MMSE) formulation under network power constraints. We also propose a mode selection procedure based on the instantaneous system throughput. Simulation results indicate that the MMSE cooperative beamforming method with mode selection achieves better performance compared to other beamforming methods: direct beamforming, relay beamforming, and cooperative beamforming without mode selection.

We introduce an incremental cooperation mode into the framework of adaptive networks (AN). The method applies to generic topologies and avoids the need to establish a Hamiltonian cycle over the network, generalizing the original incremental mode, while keeping nearly the same mean-square performance, as illustrated by the simulations. We motivate the new mode by relying on an LMS rule at the nodes, and mean-square analysis is provided.

In a non-ideal PLL circuit, leakage of the reference signal into the control line produces spurious tones. When the distorted PLL signal is used in an analog-to-digital converter (ADC), it creates spurious tones in the sampled data as well. This paper analyzes this effect and proposes a solution to remove the leakage effects. The algorithm estimates the jitter errors from the spurious sidebands and provides a way to compensate the distorted sampled data in the digital domain.

Clock timing jitters refer to random perturbations in the sampling time in analog-to-digital converters (ADCs). The perturbations are caused by circuit imperfections in the sampling clock. This paper analyzes the effect of sampling clock jitter on the acquired samples. The paper proposes two methods to estimate the jitter for superheterodyne receiver architectures and cognitive radio architectures at high sampling rates. The paper also proposes a method to compensate for the jitter. The methods are tested and validated via computer simulations and theoretical analysis.

Advertisement: IEEE.

In this paper, we design a multiuser two-way relay system using space division multiple access (SDMA) communications and devise an optimal scheduling method that maximizes the sum rate while ensuring fairness among users. To reduce the computational load at the relays, we propose rate- and angle-based suboptimal scheduling methods. The numerical results illustrate tradeoff between complexity and the performance. Specifically, when the relay has two antennas, we verify that the rate-based method can provide significant computational savings at the cost of a rate reduction of less than 4% when compared with the optimal scheduling method.

Under uncertain channel conditions, local and global power control factors for amplify-and-forward relay processing and source-destination beamforming are jointly and iteratively designed based on a minimum mean-square-error (MMSE) criterion. The influence of imperfect channel information on system performance is examined by computer simulation. As a result, it is verified that the proposed power control methods can relieve the performance degradation arising from channel uncertainties.

Spectrum sensing is one of the enabling functionalities for cognitive radio (CR) systems to operate in the spectrum white space. To protect the primary incumbent users from interference, the CR is required to detect incumbent signals at very low signal-to-noise ratio (SNR). In this paper, we present a spectrum sensing technique based on correlating spectra for detection of television (TV) broadcasting signals. The basic strategy is to correlate the periodogram of the received signal with the a priori known spectral features of the primary signal. We show that according to the Neyman-Pearson criterion, this spectra correlation-based sensing technique is asymptotically optimal at very low SNR and with a large sensing time. From the system design perspective, we analyze the effect of the spectral features on the spectrum sensing performance. Through the optimization analysis, we obtain useful insights on how to choose effective spectral features to achieve reliable sensing. Simulation results show that the proposed sensing technique can reliably detect analog and digital TV signals at SNR as low as -20 dB.

We study the problem of distributed estimation, where a set of nodes are required to collectively estimate some parameter of interest from their measurements. Diffusion algorithms have been shown to achieve good performance, increased robustness and are amenable for real-time implementations. In this work we focus on multi-level diffusion algorithms, where a network running a diffusion algorithm is enhanced by adding special nodes that can perform different processing. These special nodes form a second network where a second diffusion algorithm is implemented. We illustrate the concept using diffusion LMS, provide performance analysis for multi-level collaboration and present simulation results showing improved performance over conventional diffusion.

As an enabling functionality of overlay cognitive radio networks, spectrum sensing needs to reliably detect licensed signal in the band of interest. To achieve reliable sensing, we propose a linear fusion scheme for distributed spectrum sensing to combine the sensing results from multiple spatially distributed cognitive radios. The optimal linear fusion design is formulated into a nonconvex optimization problem. We show that the optimal solution of such a nonconvex problem can be solved via semi-definite programming reformulation.

This paper presents an efficient adaptive combination strategy for diffusion algorithms over adaptive networks in order to improve the robustness against the spatial variation of SNR over the network. The diffusion least-mean square (LMS) algorithm with the proposed combination rule and its mean transient analysis are included. Simulation results show that the diffusion LMS algorithm with our combiners outperforms those with existing static combiners and the incremental LMS algorithm.

Physical impairments like IQ imbalance and phase noise can cause significant degradation in the performance of wireless communication systems. In this paper, the joint effects of IQ imbalance and phase noise on OFDM systems are analyzed, and a compensation scheme is proposed to improve the system performance in the presence of IQ imbalance and phase noise. The scheme consists of a joint estimation of channel and impairment parameters and a joint data symbol estimation algorithm. It is shown both by theory and computer simulations that the proposed scheme can effectively improve the signal-to-noise ratio at the receiver. As a result, the sensitivity of OFDM receivers to the physical impairments can be significantly lowered, simplifying the RF and analog circuitry design in terms of implementation cost, power consumption, and silicon fabrication yield.

Advertisement: IEEE.

Advertisement: Free Electronic Access to Signal Processing Publications.

Adaptive networks (AN) have been recently proposed to address distributed estimation problems [1]-[4]. Here we extend prior work to changing topologies and data-normalized algorithms. The resulting framework may also treat signals with general distributions, rather than Gaussian, provided that certain data statistical moments are known. A byproduct of this formulation is a probabilistic diffusion adaptive network: a simpler yet robust variant of the standard diffusion algorithm [2].

Spectrum sensing is an essential functionality that enables cognitive radios to detect spectral holes and opportunistically use under-utilized frequency bands without causing harmful interference to primary networks. Since individual cognitive radios might not be able to reliably detect weak primary signals due to channel fading/shadowing, this paper proposes a cooperative wideband spectrum sensing scheme, referred to as spatial-spectral joint detection, which is based on a linear combination of the local statistics from spatially distributed multiple cognitive radios. The cooperative sensing problem is formulated into an optimization problem, for which suboptimal but efficient solutions can be obtained through mathematical transformation under practical conditions.

The wideband RF receiver in a software-defined radio (SDR) system suffers from the nonlinear effects caused by the front-end analog processing. In the presence of strong blocker (interference) signals, nonlinearities introduce severe cross modulation over the desired signals. This paper investigates how the nonlinear distortions can be compensated for by using digital signal processing techniques. In the proposed solution, the SDR scans the wide spectrum and locates the desired signal and strong blocker signals. After down-converting these signals separately into the baseband, the baseband processor processes them jointly to mitigate the cross-modulation interferences. As a result, the sensitivity of the wideband RF receiver to the non-linearity impairment can be significantly lowered, simplifying the RF and analog circuitry design in terms of implementation cost and power consumption.

Spectrum sensing is an essential enabling functionality for cognitive radio networks to detect spectrum holes and opportunistically use the under-utilized frequency bands without causing harmful interference to legacy networks. This paper introduces a novel wideband spectrum sensing technique, called multiband joint detection, which jointly detects the signal energy levels over multiple frequency bands rather than consider one band at a time. The proposed strategy is efficient in improving the dynamic spectrum utilization and reducing interference to the primary users. The spectrum sensing problem is formulated as a class of optimization problems in interference limited cognitive radio networks. By exploiting the hidden convexity in the seemingly non-convex problem formulations, optimal solutions for multiband joint detection are obtained under practical conditions. Simulation results show that the proposed spectrum sensing schemes can considerably improve the system performance. This paper establishes important principles for the design of wideband spectrum sensing algorithms in cognitive radio networks.

Spectrum sensing is a key enabling functionality in cognitive radio (CR) networks, where the CRs act as secondary users that opportunistically access free frequency bands. Due to the effects of channel fading, individual CRs may not be able to reliably detect the existence of a primary radio, who is a licensed user for the particular band. In this paper, we present optimal cooperation strategies for spectrum sensing to combat the effects of destructive channels and malfunctioning devices. Our approach conducts spectrum sensing based on the linear combination of local test statistics from individual secondary users. We propose two optimization schemes to control the combining weights, and compare their performance. Our first approach is to optimize the probability distribution function of the global test statistics at the fusion center. For the second scheme, we maximize the global detection sensitivity under constraints on the false alarm probability. Simulation results illustrate the significant cooperative gain achieved by the proposed strategies.

Distributed adaptive algorithms are proposed to address the problem of estimation in distributed networks. We extend recent work by relying on static and adaptive diffusion strategies. The resulting adaptive networks are robust to node and link failures and present a substantial improvement over the non-cooperative case asserting that cooperation improves estimation performance. The distributed algorithms are peer-to-peer implementations suitable for networks with general topologies.

We consider an estimation network of many distributed sensors, where each senor takes a noisy measurement of some unknown parameter. Due to energy limitation, the network selects only a subset of sensors for data fusion as long as the distortion is tolerable. In this paper, we present a sampling framework based on linear minimum variance unbiased estimation. The framework enables the system to achieve a desired estimation fidelity level and to improve the network lifetime. Simulations illustrate the effectiveness of the proposed sampling schemes.

OFDM systems are susceptible to receiver impairments like frequency offset, IQ imbalance and phase noise. In this paper, OFDM channel estimation in the presence of these impairments is studied, and an iterative algorithm is proposed to jointly estimate the channel coefficients and the impairment parameters. It is shown by computer simulations that the algorithm performs close to its associated Cramer-Rao lower bound.

This paper considers an estimation network of many distributed sensors with a certain correlation structure. Due to limited communication resources, the network selects only a subset of sensor measurements for estimation as long as the resulting fidelity is tolerable. We present a distributed sampling and estimation framework based on innovations diffusion, within which the sensor selection and estimation are accomplished through local computation and communications between sensor nodes. In order to achieve energy efficiency, the proposed algorithm uses a greedy heuristics to select a nearly minimum number of active sensors in order to ensure the desired fidelity for each estimation period. Extensive simulations illustrate the effectiveness of the proposed sampling scheme.

OFDM systems are susceptible to receiver impairments such as IQ imbalance and phase noise. These impairments can severely degrade the achievable effective signal-to-noise ratio at the receiver. In this paper, we propose a joint compensation scheme to mitigate the effects of the IQ imbalance and phase noise in multiple-input multiple-output (MIMO) OFDM systems. For ease of notation, a system with one transmit and two receive antennas is used to illustrate how to exploit the structure of MIMO transceivers to efficiently compensate for such impairments. We exploit the fact that the two received signals suffer from the same phase noise distortion, making it possible to achieve better compensation results than the single-input single-output case. The pilot tones in OFDM symbols are exploited to aid data recovery, and the data symbols are jointly estimated with the phase noise components that are parameterized by using the principle component analysis technique. The sensitivity of OFDM receivers to the analog impairments is significantly lowered, which helps simplify the RF and analog circuitry design in terms of implementation cost, power consumption, and silicon fabrication yield.

The emergence of wireless sensor networks has imposed many challenges on network design such as severe energy constraints, limited bandwidth and computing capabilities. This kind of networks necessitates network protocol architectures that are robust, energy-efficient, scalable, and easy for deployment. This paper proposes a robust energy-aware clustering architecture (REACA) for large-scale wireless sensor networks. We analyze the performance of the REACA network in terms of quality-of-service, asymptotic throughput capacity, and power consumption. In particular, we study how the throughput capacity scales with the number of nodes and the number of clusters. We show that by exploiting traffic locality, clustering can achieve performance improvement both in capacity and in power consumption over general-purpose ad hoc networks. We also explore the fundamental trade-off between throughput capacity and power consumption for single-hop and multi-hop routing schemes in cluster-based networks. The protocol architecture and performance analysis developed in this paper provide useful insights for practical design and deployment of large-scale wireless sensor network.

The emergence of wireless sensor networks has imposed many challenges on network design such as severe energy constraints, limited bandwidth and computing capabilities. This kind of networks necessitates network protocol architectures that are robust, energy-efficient, scalable, and easy for deployment. This paper proposes a robust energy-aware clustering architecture (REACA) for large-scale wireless sensor networks. We analyze the performance of the REACA network in terms of quality-of-service, asymptotic throughput capacity, and power consumption. In particular, we study how the throughput capacity scales with the number of nodes and the number of clusters. We show that by exploiting traffic locality, clustering can achieve performance improvement both in capacity and in power consumption over general-purpose ad hoc networks. We also explore the fundamental trade-off between throughput capacity and power consumption for single-hop and multi-hop routing schemes in cluster-based networks. The protocol architecture and performance analysis developed in this paper provide useful insights for practical design and deployment of large-scale wireless sensor network.

In multiuser MIMO downlink communications, it is necessary to design precoding schemes that are able to suppress co-channel interference. This paper proposes designing precoders by maximizing the so-called signal-to-leakage-and-noise ratio (SLNR) for all users simultaneously. The presentation considers communications with both single- and multi-stream cases, as well as MIMO systems that employ Alamouti coding. The effect of channel estimation errors on system performance is also studied. Compared with zero-forcing solutions, the proposed method does not impose a condition on the relation between the number of transmit and receive antennas, and it also avoids noise enhancement. Simulations illustrate the performance of the scheme

The implementation of OFDM-based systems suffers from impairments such as in-phase and quadrature-phase (IQ) imbalances in the front-end analog processing. Such imbalances are caused by the analog processing of the radio frequency (RF) signal and can be present at both the transmitter and receiver. The resulting IQ distortion limits the achievable operating SNR at the receiver and the achievable data rates. In this paper, the effect of both the transmitter and receiver IQ imbalances in an OFDM system is studied and algorithms are developed to compensate for such distortions in the digital domain. The algorithms include post-FFT least-squares and adaptive equalization, as well as a pre-distortion scheme at the transmitter and a pre-FFT correction at the receiver

This paper proposes multi-user precoding schemes for MIMO wireless networks. We design precoders that minimize the interference power caused by a user on all other users, as opposed to forcefully nulling the interference. The resulting scheme relaxes the traditional constraint on the number of transmit and receive antennas.

An adaptive distributed estimation strategy is developed based on incremental gradient techniques. The proposed scheme addresses the problem of distributed linear estimation in a cooperative fashion, resulting in a distributed algorithm that can respond in real time to changes in the environment. Each node is allowed to communicate only with its immediate neighbor in order to exploit the spatial dimension while at the same time reducing the communications burden. A spatial-temporal energy conservation argument is used to evaluate the steady-state mean-square-error performance of the individual nodes across the adaptive distributed network. Computer simulations illustrate the results.

We propose a robust energy-aware clustering architecture for large-scale wireless sensor networks and analyze its performance in terms of throughput capacity and power consumption. The results show that clustered networks can achieve performance improvement by exploiting traffic locality and spatial separation.

The performance of multiband-OFDM UWB systems is analyzed using the S-V indoor channel model. Based on the analysis, two methods are proposed to improve the reliable transmission range of UWB devices by exploiting the rich spectral and spatial diversity available in the system. It is shown both by theory and computer simulations that the proposed methods can effectively enlarge the transmission range of UWB devices.

Mobile wearable computers are intended to provide users with real-time access to information in a natural and unobtrusive manner. Computing and sensing in these devices must be reliable, easy to interact with, transparent, and configured to support different needs and complexities. This paper presents a vision-based robust finger tracking algorithm combined with audio-based control commands that is integrated into a multimodal unobtrusive user interface, wherein the interface may be used to segment out objects of interest in the environment by encircling them with the user's pointing fingertip. In order to quickly extract the objects encircled by the user from a complex scene, this unobtrusive interface uses a single head-mounted camera to capture color images, which are then processed using algorithms to perform: color segmentation, fingertip shape analysis, perturbation model learning, and robust fingertip tracking. This interface is designed to be robust to changes in the environment and user's movements by incorporating a state-space estimation with uncertain models algorithm, which attempts to control the influence of uncertain environment conditions on the system's fingertip tracking performance by adapting the tracking model to compensate for the uncertainties inherent in the data collected with a wearable computer.

Combination approaches can improve the performance of adaptive schemes. In this paper, we study the steady-state performance of an adaptive convex combination of transversal filters and show its universality in the sense that the combination performs, in steady-state, at least as well as its best component. We specialize the results to a convex combination of LMS filters using energy conservation arguments.

This paper proposes a globally distributed synchronization algorithm for wireless sensor networks. In the proposed scheme, there is a master node that controls the network synchronization and the other sensors periodically broadcast synchronization pulses; they also monitor different frequency channels in an effort to overcome the effect of channel fading.

Multi-user multiple-input multiple-output (MU-MIMO) wireless systems can provide a substantial gain in network downlink throughput by allowing multiple users to communicate in the same frequency and time slots. The challenge is to design transmit beamforming vectors for every user while limiting the co-channel interference (CCI) from other users. One approach is to perfectly cancel the CCI at every user, which requires a relatively large number of transmit antennas. In this paper, we consider an alternative approach based on maximizing the signal-to-leakage ratio (SLR) for designing transmit beamforming vectors in a multi-user system. One advantage of the proposed scheme is that it does not impose a restriction on the number of available transmit antennas; it also outperforms the conventional beamforming scheme.

This letter shows that the matrix structure with 2/spl times/2 Alamouti sub-blocks remains invariant under several nontrivial matrix operations, including matrix inversion, Schur complementation, Riccati recursion, triangular factorization, and QR factorization.

This letter provides a unified mean-square performance analysis of the class of data reusing adaptive algorithms. The derivation relies on energy conservation arguments, and it does not restrict the regression data to being Gaussian. Simulation results show that there is a relatively good match between theory and practice.

Kalman filtering has been proposed in the literature for wireless channel estimation, however, it is not sufficiently robust to uncertainties in the channel auto-correlation model as well as to multiple access interference (MAI). This paper presents a receiver structure for direct-sequence code-division multiple-access (DS-CDMA) systems by using robust Kalman estimation and post-correlation (i.e., symbol rate) processing for channel estimation. The proposed structure is also generalized to incorporate multiple-antenna combining and interference cancellation techniques. The resulting receiver outperforms earlier structures in the presence of channel modeling uncertainties, MAI, and low-received signal-to-noise ratio. The enhancement in performance is achieved at the same order of complexity as a standard Kalman-based receiver.

In this paper, we propose resource allocation strategies for a class of wireless networks with a clustering protocol. The nodes are assumed stationary and establish connections with the master node according to a priority scheme that relates to their distances from the master node. The paper considers bandwidth allocation with soft and hard constraints, as well as power allocation strategies. Simulation results illustrate the performance of the proposed strategies.

OFDM is a widely recognized and standardized modulation scheme for future high bit rate communications. Implementation of OFDM-based systems suffers from inphase-quadrature phase (IQ) imbalances in the front-end analog processing. The IQ imbalances can severely limit the operating SNR and, consequently, the supported constellation sizes. In this paper, the effect of IQ imbalances on OFDM receivers is analyzed and system level algorithms to compensate for these distortions are proposed. The algorithms include different post and pre-FFT estimation and correction techniques.

We present a receiver design for joint interference suppression and equalization of asynchronous multi-user space-time block coded (STBC) systems. We describe the design of front end prefilters to synchronize the received blocks from all users. Simulation results show significant performance improvement for asynchronous transmissions.

We propose resource allocation strategies for a class of wireless networks with a clustering protocol. The nodes are assumed stationary and establish connections with the master node according to a priority scheme that relates to their distances from the master node. The paper considers bandwidth and rate allocation.

This letter proposes two new variable step-size algorithms for normalized least mean square and affine projection. The proposed schemes lead to faster convergence rate and lower misadjustment error.

The mean-squared-error criterion is widely used in the literature. However, there are applications where the squared-error is not the primary parameter affecting the performance of a system. In many communication systems, for instance, the information bits are carried over the phase of the transmitted signal. In this letter, we introduce a cost function that is based on both the error magnitude and the phase error. The criterion is useful for applications where the performance depends primarily on the phase of the estimated (recovered) signal. An adaptive filter is then developed using the proposed criterion with essentially the same complexity as the standard least mean squared (LMS) algorithm. The filter outperforms LMS specially in situations with fast channel variations. Bit error rate (BER) simulations for two communication systems using the proposed algorithm support the claims.

Among the challenging issues that affect the performance of wireless location techniques is the temporal and spatial variations of the channel, and the distribution of the scatterers, which introduce non-line-of sight errors at the base station. This paper develops a technique for addressing this problem by exploiting the topology of the cellular network.

Most analytical results on affine projection algorithms assume special regression models or Gaussian regression data. The available analyses also treat different affine projection filters separately. This paper provides a unified treatment of the transient performance of a family of affine projection algorithms. The treatment relies on energy conservation arguments and does not restrict the input data to being Gaussian or white. Simulation results illustrate the analysis and the derived performance expressions.

Location finding for CDMA subscribers using an antenna array at the base station is studied. Two methods are considered for radio location that are based on time of arrival (TOA) and angle of arrival (AOA) measurements. For TOA estimates, a maximum likelihood algorithm and a practical structure are proposed when an antenna array is available. For AOA estimates, a least-squares (LS) algorithm is used. The LS module is combined with a multiple access interference (MAI) cancellation technique to improve the AOA estimation accuracy in multiuser multipath scenarios.

Orthogonal frequency division multiplexing (OFDM) is a promising technique for multi-antenna broadband systems, since it significantly reduces receiver complexity by providing orthogonal subchannels. A drawback of OFDM systems is the performance/rate reduction due to the cyclic prefix overhead. We propose receiver structures that exploit the cyclic prefix to increase the performance of the link. The proposed structures use the standard OFDM transmitter, and the modifications are only made at the receiver. Optimum receivers in both the least-mean-squares and least-squares senses are presented, and they do not result in any extra processing complexity compared to the standard OFDM receiver. The proposed architecture is further extended to a MIMO OFDM structure. Simulation results validate the improved performance of the proposed receiver.

We develop an efficient adaptive receiver for joint equalization and interference cancellation for multi-user space-time block-coded transmissions. The receiver exploits the rich code structure and allows multiple user transmissions over frequency-selective fading channels with reduced complexity and lower system overhead. The adaptation scheme is based on a recursive least-squares implementation for faster convergence; nevertheless, it exploits the code structure to attain RLS performance at LMS complexity.

We develop an efficient adaptive receiver for joint equalization and interference cancellation for multi-user space-time block-coded transmissions. The receiver exploits the code structure and allows multiple user transmission over frequency-selective fading channels with reduced complexity and lower system overhead. The adaptation scheme is based on a recursive least-squares implementation for faster convergence; nevertheless, it exploits the code structure to attain RLS performance at LMS complexity.

This paper presents a robust receiver for uplink direct sequence code-division multiple access (DS-CDMA) systems. The receiver uses low order auto-regressive models to approximate the multi-path fading channel taps, and a post correlation-based uncertain model for estimation purposes.

In this paper, we consider the class of adaptive filters with error nonlinearities. In particular, we derive an expression for the optimum nonlinearity that minimizes the steady-state error and attains the limit mandated by the Cramer-Rae bound of the underlying estimation process.

We discuss the limitations of conventional closed loop power control (CLPC). We derive a closed-form expression for the control error. We then propose two algorithms that reduce this error. Simulations show a reduced power error compared to current CLPC techniques.

In this work, two algorithms for closed loop power control in CDMA wireless systems are proposed. These algorithms aim to minimize the power control error by predicting the inverse of the channel fading: For this purpose, a channel fading prediction scheme is also proposed.

We develop an adaptive equalization scheme for space-time block-coded (STBC) transmissions. The scheme is based on a modified low-complexity version of the fast-converging RLS algorithm. Complexity reduction is achieved by exploiting the rich structure of STBC.

This paper develops a framework for the mean-square analysis of adaptive filters with general data and error nonlinearities. The approach relies on energy conservation arguments and is carried out without restrictions on the probability distribution of the input sequence. In particular, for adaptive filters with diagonal matrix nonlinearities, we provide closed form expressions for the steady-state performance and necessary and sufficient conditions for stability. We carry out a similar study for long adaptive filters that employ error nonlinearities relying on a weaker form of the independence assumption. We provide expressions for the steady-state error and bounds on the step-size for stability by exploiting the Cramer-Rao bound of the underlying estimation process.

We propose and study an adaptive delta modulator that has improved SNR performance and robustness in tracking highly varying signals. The step-size adaptation used in this modulator is based on information about the absolute value of the quantizer input. The modulator is shown to be free of zero-input limit cycles and is BIBO stable.

The existing derivations of fast RLS adaptive filters are dependent on the shift structure in the input regression vectors. This structure arises when a tapped-delay line (FIR) filter is used as a modeling filter. We show, unlike what original derivations may suggest, that fast fixed-order RLS adaptive algorithms are not limited to FIR filter structures. We show that fast recursions in both explicit and array forms exist for more general data structures, such as orthonormally-based models. One of the benefits of working with an orthonormal basis is that fewer parameters can be used to model long impulse responses.

We study leaky adaptive algorithms that employ a general scalar or matrix data nonlinearity. We perform mean-square analysis of this class of algorithms without imposing restrictions on the distribution of the input signal. In particular, we derive conditions on the step-size for stability, and provide closed form expressions for the steady-state performance.

The steady-state performance of adaptive equalizers can significantly vary when they are implemented in finite precision arithmetic, which makes it vital to analyze their performance in a quantized environment. We present a fixed point analysis for the steady-state mean square error (MSE) of a blind adaptive equalizer and the optimal value of the step-size that minimizes this MSE. Such expressions are useful for selecting the adequate wordlength of a blind equalizer to achieve a specific desired steady-state performance.

The Federal Communications Commission (FCC) mandate for locating the position of wireless 911 callers is fueling research in the area of mobile-positioning technologies. Overlapping multipath propagation is one of the main sources of mobile-positioning errors, especially in fast channel fading situations. In this paper we develop a technique for detecting and providing an estimate of the number of overlapping fading multipath components. Such information is vital for accurate resolution of overlapping multipath components as well as avoiding unnecessary computations and errors in single-path propagation cases. The proposed technique exploits the fact that multipath components fade independently as well as the pulse shape symmetry. The paper also presents supporting simulation results.

This paper derives an expression for the optimal error nonlinearity in adaptive filter design. Using an energy conservation relation, and some typical assumptions, the choice of the error function is optimized by minimizing the mean-square deviation subject to a fixed rate of convergence. The resulting optimal choice is shown to subsume earlier results as special cases.

This paper solves the problem of designing an exact RLS lattice (or order-recursive) algorithms for adaptive filters that do not involve tapped-delay-line structures. As a special case, an exact RLS Laguerre lattice filter is obtained.

This paper derives new tracking results for adaptive filtering algorithms operating in the presence of two sources of non-stationarities: a carrier frequency offset and random variations. Both impairments are common in digital communications due to variations in channel characteristics and to mismatches between transmitter and receiver carrier generators.

This paper addresses the problem of adaptive channel tracking and equalization for multi-input multi-output (MIMO) time-variant frequency-selective channels. A finite-length minimum-mean-squared-error decision-feedback equalizer (MMSE-DFE) performs the equalization task, while a Kalman filter tracks the MIMO channel, which models the corrupting effects of inter-symbol interference (ISI), inter-user interference (IUI), and noise. The Kalman tracking is aided by previous hard decisions produced by the DFE, with a decision delay /spl Delta/>0, which causes the Kalman filter to track the channel with a delay. A channel prediction module bridges the time gap between the channel estimates produced by the Kalman filter and those needed for the DFE adaptation. The proposed algorithm offers good tracking behavior for multi-user fading ISI channels at the expense of higher complexity.

The steady-state performance of adaptive filters can significantly vary when they are implemented in finite precision arithmetic, which makes it vital to analyze their performance in a quantized environment. Such analyses can become difficult for adaptive algorithms with nonlinear update equations. This paper develops a new feedback approach to the steady-state analysis of quantized adaptive algorithms that bypasses many of the difficulties encountered in traditional approaches. In so doing, we not only re-derive several earlier results in the literature, but we often do so under weaker assumptions, in a more compact way, and we also obtain new results.

Location finding searchers have recently emerged as essential elements in future CDMA wireless systems. In this paper we present a new combined architecture for location searchers and conventional RAKE receivers, which is based on multiplexing common hardware blocks between the two structures. In so doing, most of the needed hardware for the conventional RAKE fingers and channel searcher is saved with no performance degradation. Furthermore, the new architecture can avoid the need to use delay locked loops.

The author begins by discussing the fundamental energy relation, then goes on to consider steady state analysis and tracking analysis. Adaptive filtering is also mentioned in the study.

This paper studies the behavior of the error sequence of stop-anti-go variants of two adaptive blind equalizers, namely CMA2-2 and Sato's (1975) algorithm. It is shown that for transmitted signals with constant modulus /spl gamma/, the equalizer output can be made to lie within the circle of radius /spl gamma//spl radic/c infinitely often, for some value of c that is only slightly larger than one.

This paper proposes two modifications of the filtered-x least mean squares (FxLMS) algorithm with improved convergence behavior albeit at the same computational cost of 2M operations per time step as the original FxLMS update. The paper further introduces a generalized FxLMS recursion and establishes that the various algorithms are all of filtered-error form. A choice of the stepsize parameter that guarantees faster convergence and conditions for robustness are also derived. Several simulation results are included to illustrate the discussions.

This paper deals with the important problem of parameter estimation in the presence of bounded data uncertainties. Its recent closed-form solution leads to more meaningful results than alternative methods (e.g., total least-squares and robust estimation), when a priori bounds about the uncertainties are available. The derivation requires the computation of the SVD of the data matrix and the determination of the unique positive root of a nonlinear equation. This paper establishes the existence of a fundamental contraction mapping and uses this observation to propose an approximate recursive algorithm that avoids the need for explicit SVDs and for the solution of the nonlinear equation. Simulation results are included to demonstrate the good performance of the recursive scheme.

We formulate and solve a new parameter estimation problem in the presence of bounded data uncertainties. The new method is suitable when a priori bounds on the uncertain data are available; its solution guarantees that the effect of the uncertainties will never be unnecessarily overestimated beyond what is reasonably assumed by the a priori bounds.

The problem of approximating a long FIR filter by a reduced-parameter stable pole-zero filter is addressed. We derive a computationally efficient order-recursive algorithm that achieves this task with high accuracy. Our main emphasis is on applying this algorithm to reduce the implementation complexity of the decision feedback equalizer's long FIR feedforward and feedback filters encountered in high-speed data transmission on digital subscriber loops.

The study of matrices with a displacement structure is mainly concerned with recursions for the so-called generator matrices. The recursion usually involves free parameters, which can be chosen in several ways so as to simplify the resulting algorithm. In this correspondence we present a choice for the parameters that is motivated by a maximum-entropy formulation, This choice further motivates the introduction of the so-called generalized reflection coefficients which are, in general, different from the better known Schur coefficients.

This paper provides a time-domain feedback analysis of the perceptron learning algorithm and of training schemes for dynamic networks with output feedback. It studies the robustness performance of the algorithms in the presence of uncertainties that might be due to noisy perturbations in the reference signals or due to modeling mismatch. In particular, bounds are established on the step-size parameters in order to guarantee that the resulting algorithms will behave as robust filters. The paper also establishes that an intrinsic feedback structure can be associated with the training schemes. The feedback configuration is motivated via energy arguments and is shown to consist of two major blocks: a time-variant lossless (i.e., energy preserving) feedforward path and a time-variant feedback path. The stability of the feedback structure is then analyzed via the small gain theorem, and choices for the step-size parameter in order to guarantee faster convergence are deduced by using the mean-value theorem. Simulation results are included to demonstrate the findings.

We study the relation between the solutions of two estimation problems with indefinite quadratic forms. We show that a complete link between both solutions can be established by invoking a fundamental set of inertia conditions. While these inertia conditions are automatically satisfied in a standard Hilbert space setting, they nevertheless turn out to mark the differences between the two estimation problems in indefinite metric spaces. They also include, as special cases, the well-known conditions for the existence of H/sup -/spl infin//-filters and controllers. Given two Hermitian matrices {/spl Pi/, W}, a column vector y, and an arbitrary matrix A of appropriate dimensions, we study the relation between two minimization problems with quadratic cost functions, and also refer to the indefinite-weighted least-squares problem.

Gradient-descent adaptive algorithms are among the most widely used in current practice, with many different variants that generally fit into two major groups: one group includes algorithms that are especially suited for FIR (or finite-impulse-response) modeling, while the other group includes algorithms that are tailored for IIR (or infinite-impulse-response) modeling. In the first group, the regression (or data) vectors do not depend on the unknown parameters, which leads to convenient linear models that often facilitate the analysis of the algorithms. In the second category, on the other hand, the regression vectors are dependent on the unknown parameters, thus giving rise to nonlinear functionals and to a richer structure that requires a more thorough analysis. This paper focuses on a widely used adaptive IIR algorithm, the so-called Feintuch's (1976) algorithm, and provides a study of its robustness, stability, and convergence properties in a deterministic framework.

The authors use the classical Schur reduction procedure to give a lattice filter implementation of the Chandrasekhar recursions. The derivation is based on the observation that the covariance matrix of a process with a time-invariant state-space model is structured. This allows one to easily derive the connection between the Schur algorithm and spectral factorization and to extend the Chandrasekhar recursions to the case of nonsymmetric Riccati equations. The Chandrasekhar recursions can be implemented in scalar steps using a sequence of well-defined elementary (hyperbolic and Givens) rotations.>