In this paper, we study the problem of fair multi-agent multi-arm bandit learning when agents do not communicate with each other, except collision information, provided to agents accessing the same arm simultaneously. We provide an algorithm with regret O(N3f(log T)log T) (assuming bounded rewards, with unknown bound), where f(t) is any function diverging to infinity with t. In contrast to optimal algorithms which share the rewards with a selected leader, our algorithm does not require a centralized collection of the arm rewards, allowing each agent to keep its rewards private. We also significantly improved previous privacy-preserving algorithms with the same upper bound on the regret of order O(f(log T)log T) but an exponential dependence on the number of agents. Simulation results present the dependence of the regret on log T.

In this paper, we propose a provably convergent and practical framework for multi-objective reinforcement learning with max-min criterion. From a game-theoretic perspective, we reformulate max-min multi-objective reinforcement learning as a two-player zero-sum regularized continuous game and introduce an efficient algorithm based on mirror descent. Our approach simplifies the policy update while ensuring global last-iterate convergence. We provide a comprehensive theoretical analysis on our algorithm, including iteration complexity under both exact and approximate policy evaluations, as well as sample complexity bounds. To further enhance performance, we modify the proposed algorithm with adaptive regularization. Our experiments demonstrate the convergence behavior of the proposed algorithm in tabular settings, and our implementation for deep reinforcement learning significantly outperforms previous baselines in many MORL environments.

Federated learning is a technique that allows multiple entities to collaboratively train models using their data without compromising data privacy. However, despite its advantages, federated learning can be susceptible to false data injection attacks. In these scenarios, a malicious entity with control over specific agents in the network can manipulate the learning process, leading to a suboptimal model. Consequently, addressing these data injection attacks presents a significant research challenge in federated learning systems. In this paper, we propose a novel approach to detect and mitigate data injection attacks on federated learning systems. Our mitigation strategy is a local scheme, performed during a single instance of training by the coordinating node, allowing for mitigation during the convergence of the algorithm. Whenever an agent is suspected of being an attacker, its data will be ignored for a certain period; this decision will often be re-evaluated. We prove that with probability one, after a finite time, all attackers will be ignored while the probability of ignoring a trustful agent becomes zero, provided that there is a majority of truthful agents. Simulations show that when the coordinating node detects and isolates all the attackers, the model recovers and converges to the truthful model.

In this paper, we consider multi-objective reinforcement learning, which arises in many real-world problems with multiple optimization goals. We approach the problem with a max-min framework focusing on fairness among the multiple goals and develop a relevant theory and a practical model-free algorithm under the max-min framework. The developed theory provides a theoretical advance in multi-objective reinforcement learning, and the proposed algorithm demonstrates a notable performance improvement over existing baseline methods.

Vertically distributed learning exploits the local features collected by multiple learning workers to form a better global model. However, data exchange between the workers and the model aggregator for parameter training incurs a heavy communication burden, especially when the learning system is built upon capacity-constrained wireless networks. In this paper, we propose a novel hierarchical distributed learning framework, where each worker separately learns a low-dimensional embedding of their local observed data. Then, they perform communication-efficient distributed max-pooling to efficiently transmit the synthesized input to the aggregator. For data exchange over a shared wireless channel, we propose an opportunistic carrier sensing-based protocol to implement the max-pooling of the output of all the workers. Our simulation experiments show that the proposed learning framework is able to achieve almost the same model accuracy as the learning model using the concatenation of all the raw outputs from the learning workers while significantly reducing the communication load.

Generalized Nash games differ from strategic form games by allowing the strategy set available for each player to depend on the strategies selected by the other players. The strong dependence of the strategies of the players make these generalized games harder to analyze. While convex generalized games are well understood, the case where the constraint sets and rewards are non-convex is significantly more complicated. In this paper we analyze a family of monotonic generalized games (not necessarily convex). We provide uniqueness and existence theorems for these games as well as rapidly converging algorithm for obtaining a Nash equilibrium. We then use the proposed solution to optimize access probability and energy consumption in ALOHA networks, where users have fixed but heterogeneous QoS requirements.

This paper considers a resource allocation problem where several Internet-of-Things (IoT) devices send data to a base station (BS) with or without the help of the reconfigurable intelligent surface (RIS) assisted cellular network. The objective is to maximize the sum rate of all IoT devices by finding the optimal RIS and spreading factor (SF) for each device. Since these IoT devices lack prior information of the RISs or the channel state information (CSI), a distributed resource allocation framework with low complexity and learning features is required to achieve this goal. Therefore, we model this problem as a two-stage multi-player multi-armed bandit (MPMAB) framework to learn the optimal RIS and SF sequentially. Then, we put forth an exploration and exploitation boosting (E2Boost) algorithm to solve this two-stage MPMAB problem by combining the$\epsilon $-greedy algorithm, Thompson sampling (TS) algorithm, and non-cooperation game method. We derive an upper regret bound for the proposed algorithm, i.e.,$\mathcal {O}(\log ^{1+\delta }_{2} T)$, increasing logarithmically with the time horizon$T$. Numerical results show that the E2Boost algorithm has the best performance among the existing methods and exhibits a fast convergence rate. More importantly, the proposed algorithm is not sensitive to the number of combinations of the RISs and SFs thanks to the two-stage allocation mechanism, which can benefit the high-density networks.

We study a decentralized channel allocation problem in an ad-hoc Internet of Things network underlaying on the spectrum licensed to a primary cellular network. In the considered network, the impoverished channel sensing/probing capability and computational resource on the IoT devices make them difficult to acquire the detailed Channel State Information (CSI) for the shared multiple channels. In practice, the unknown patterns of the primary users' transmission activities and the time-varying CSI (e.g., due to small-scale fading or device mobility) also cause stochastic changes in the channel quality. Decentralized IoT links are thus expected to learn channel conditions online based on partial observations, while acquiring no information about the channels that they are not operating on. They also have to reach an efficient, collision-free solution of channel allocation with limited coordination. Our study maps this problem into a contextual multi-player, multi-armed bandit game, and proposes a purely decentralized, three-stage policy learning algorithm through trial-and-error. Theoretical analyses shows that the proposed scheme guarantees the IoT links to jointly converge to the social optimal channel allocation with a sub-linear (i.e., polylogarithmic) regret with respect to the operational time. Simulations demonstrate that it strikes a good balance between efficiency and network scalability when compared with the other state-of-the-art decentralized bandit algorithms.

The Corona virus disease 2019 (COVID-19) has significantly affected lives of people around the world. Today, isolation policy is mostly enforced by identifying infected individuals based on symptoms when these appear or by testing people and quarantining those who have been in close contact with infected people. In addition, many countries have imposed complete or partial lock-downs to control the spread of the disease. While lock-downs have succeeded to slow down the spread of the virus, they have devastating effects on the economy and social life. We argue that controlling the spread of the virus can be done by using active feedback to control testing for infection by actively testing individuals with a high probability of being infected. We develop an active testing strategy to achieve this goal, and demonstrate that it would have tremendous success in controlling the spread of the virus. Our results show up to a 50% reduction in quarantine rate and morbidity rate in typical settings as compared to existing methods.

Federated edge learning has emerged as a promising technique to enable distributed machine learning using local datasets from large-scale edge devices, e.g., mobile phones or parked vehicles, that share only model updates without uploading raw training data. This technique not only preserves data privacy of edge devices but also simultaneously ensures high learning performance. However, the emerging federated edge learning still confronts serious challenges, such as the lack of efficient training task assignment schemes with reliable edge devices acting as workers. To address this challenge, we utilize a many-to-one matching model to solve the training task assignment problem between the workers and multiple task publishers. In the matching model, we minimize not only the overall training time of the task publishers but also the energy consumption of the workers. To define against malicious model updates from unreliable workers, we present reputation as a metric to evaluate the reliability and trustworthiness of the edge devices, and also take the reputation into consideration when assigning training tasks. The numerical results indicate that the proposed schemes can efficiently improve the performance of federated edge learning.

Wireless cellular communication networks are bandwidth and interference limited. An important means to overcome these resource limitations is the use of multiple antennas. Base stations equipped with a very large (massive) number of antennas have been the focus of recent research. A bottleneck in such systems is the cost of a large number of transmit/receive chains requiring ADCs, low noise amplifiers and power amplifiers. The present work considers a line-of-sight channel model. It is shown that given a sufficiently large antenna array, it suffices that the number of transmit/receive chains exceeds the number of desired users by one in order to reduce the interference to any desired level by judiciously selecting the antenna elements.

Packet scheduling in 5G networks can significantly affect the performance of beamforming techniques since the allocation of multiple users to the same time-frequency block causes interference between users. A combination of beamforming and scheduling can thus improve the performance of multi-user MIMO systems. Furthermore, in realistic conditions, data packets have both priority and deadlines beyond which they become obsolete. In this paper we propose a simple scheduling algorithm which takes priorities and deadlines into account and allocates users dynamically to resource blocks and spatial beams according to the Tomlinson-Harashima precoder. We demonstrate the merits of the proposed technique compared to other state-of-the art scheduling methods through simulations.

Consider N cooperative but non-communicating players where each plays one out of M arms for T turns. Players have different utilities for each arm, representable as an NxM matrix. These utilities are unknown to the players. In each turn players receive noisy observations of their utility for their selected arm. However, if any other players selected the same arm that turn, they will all receive zero utility due to the conflict. No other communication or coordination between the players is possible. Our goal is to design a distributed algorithm that learns the matching between players and arms that achieves max-min fairness while minimizing the regret. We present an algorithm and prove that it is regret optimal up to a \log\log T factor. This is the first max-min fairness multi-player bandit algorithm with (near) order optimal regret.

We introduce noisy beeping networks, where nodes have limited communication capabilities, namely, they can only emit energy or sense the channel for energy. Furthermore, imperfections may cause devices to malfunction with some fixed probability when sensing the channel, which amounts to deducing a noisy received transmission. Such noisy networks have implications for ultra-lightweight sensor networks and biological systems.

It is shown that a receiver equipped with two antennas may null an arbitrary large number of spatial directions to any desired level, while maintaining the interference-free signal-to-noise ratio, by judiciously adjusting the distance between the antenna elements. The main theoretical result builds on ergodic theory. The practicality of the scheme for systems operating at a moderate signal-to-noise ratio is demonstrated for a scenario where each transmitter is equipped with a single antenna and each receiver has two antenna elements, the separation of which can be arbitrarily set. As an example, for a five-user planar line-of-sight interference channel, with the directions of users being uniformly distributed, at a signal-to-noise ratio of 10 dB, a near interference-free average transmission rate is achievable. This amounts to roughly doubling the average rate attained by non-naive time-division multiple access.

Channel allocation is the task of assigning channels to users such that some objective (e.g., sum-rate) is maximized. In centralized networks such as cellular networks, this task is carried by the base station (BS) which gathers the channel state information (CSI) from the users and computes the optimal solution. In distributed networks such as ad-hoc and device-to-device (D2D) networks, no BS exists and conveying global CSI between users is costly or simply impractical. When the CSI is time varying and unknown to the users, the users face the challenge of both learning the channel statistics online and converging to a good channel allocation. This introduces a multi-armed bandit (MAB) scenario with multiple decision makers. If two or more users choose the same channel, a collision occurs and they all receive zero reward. We propose a distributed channel allocation algorithm that each user runs and converges to the optimal allocation while achieving an order optimal regret of O (log T ), where T denotes the length of time horizon. The algorithm is based on a carrier sensing multiple access (CSMA) implementation of the distributed auction algorithm. It does not require any exchange of information between users. Users need only to observe a single channel at a time and sense if there is a transmission on that channel, without decoding the transmissions or identifying the transmitting users. We demonstrate the performance of our algorithm using simulated LTE and 5G channels.

We consider the problem of distributed channel allocation in large networks under the frequency-selective interference channel. Performance is measured by the weighted sum of achievable rates. Our proposed algorithm is a modified Fictitious Play algorithm that can be implemented distributedly, and its stable points are the pure Nash equilibria of a given game. Our goal is to design a utility function for a non-cooperative game, such that all of its pure Nash equilibria have close to optimal global performance. This will make the algorithm close to optimal while requiring no communication between users. We propose a novel technique to analyze the Nash equilibria of a random interference game, determined by the random channel gains. Our analysis is asymptotic in the number of users. First, we present a natural non-cooperative game where the utility of each user is his achievable rate. It is shown that, asymptotically in the number of users and for strong enough interference, this game exhibits many bad equilibria. Then, we propose a novel non-cooperative M frequency-selective interference channel game as a slight modification of the former, where the utility of each user is artificially limited. We prove that even its worst equilibrium has asymptotically optimal weighted sum rate for any interference regime and even for correlated channels. This is based on an order statistics analysis of the fading channels that is valid for a broad class of fading distributions (including Rayleigh, Rician, m-Nakagami, and more). We carry out simulations that show fast convergence of our algorithm to the proven asymptotically optimal pure Nash equilibria.

In this paper, we consider the simultaneous connectivity of primary and secondary networks forming a cognitive model. It is assumed that the cognitive model includes guard zones that prevent the nodes of the secondary network from being active in the vicinity of primary nodes to limit interference. Under these assumptions, we characterize the region of densities, the transmission radii of the nodes in each of the networks, and the guard zones for which the two networks have a unique unbounded connected component. We prove that this model is feasible, that is, there exists simultaneous connectivity with the unique unbounded connected component in each of the networks. We also provide necessary and sufficient conditions for the simultaneous connectivity of this cognitive model.

Consider a channel allocation problem over a frequency-selective channel. There are K channels (frequency bands) and N users such that K = bN for some positive integer b. We want to allocate b channels (or resource blocks) to each user. Due to the nature of the frequency-selective channel, each user considers some channels to be better than others. The optimal solution to this resource allocation problem can be computed using the Hungarian algorithm. However, this requires knowledge of the numerical value of all the channel gains, which makes this approach impractical for large networks. We suggest a suboptimal approach that only requires knowing what the M-best channels of each user are. We find the minimal value of M such that there exists an allocation where all the b channels each user gets are among his M-best. This leads to the feedback of significantly less than one bit per user per channel. For a large class of fading distributions, including Rayleigh, Rician, m-Nakagami, and others, this suboptimal approach leads to both an asymptotically (in K) optimal sum rate and an asymptotically optimal minimal rate. Our non-opportunistic approach achieves (asymptotically) full multiuser diversity as well as optimal fairness in contrast to all other limited feedback algorithms.

In a sponsored content scheme, a wireless network operator negotiates with a sponsored content service provider where the latter can pay the former to lower the cost of the mobile subscribers/users to access certain content. As such, the scheme motivates the entities in the sponsored content ecosystem to be more actively involved. Meanwhile, with the forthcoming 5G cellular networks, edge caching becomes a promising technology for traffic offloading to reduce cost and improve service quality of the content service. The key idea is that an edge caching content service provider caches content on edge networks. The cached content is then delivered to mobile users locally, reducing latency substantially. In this paper, we propose the joint sponsored and edge caching content service market model. We investigate an interplay between the sponsored content service provider and the edge caching content service provider under the non-cooperative game framework. Furthermore, the interactions among the wireless network operator, content service providers, and mobile users are modeled as a hierarchical three-stage Stackelberg game. In the game model, we analyze the sub-game perfect equilibrium in each stage through backward induction analytically. Additionally, the existence of the proposed Stackelberg equilibrium is validated by capitalizing on the bilevel optimization programming. Based on the analysis of the game properties, we propose a sub-gradient-based iterative algorithm, which guarantees to converge to the Stackelberg equilibrium.

With a sponsored content scheme in a wireless network, a sponsored content service provider can pay to a network operator on behalf of the mobile users/subscribers to lower down the network subscription fees at the reasonable cost in terms of receiving some amount of advertisements. As such, content providers, network operators and mobile users are all actively motivated to participate in the sponsored content ecosystem. Meanwhile, in 5G cellular networks, caching technique is employed to improve content service quality, which stores potentially popular contents on edge networks nodes to serve mobile users. In this work, we propose the joint sponsored and edge caching content service market model. We investigate an interplay between the sponsored content service provider and the edge caching content service provider under the non-cooperative game framework. Furthermore, a three-stage Stackelberg game is formulated to model the interactions among the network operator, content service provider, and mobile users. Sub-game perfect equilibrium in each stage is analyzed by backward induction. The existence of Stackelberg equilibrium is validated by employing the bilevel optimization programming. Based on the game properties, we propose a sub-gradient based iterative algorithm, which ensures to converge to the Stackelberg equilibrium.

Celestial transient radio sources have attracted considerable scientific interest recently, but their investigation is hampered by the fact that they cannot be effectively detected by commonly used radio astronomy imaging techniques. One significant obstacle to observing radio transients is intermittent terrestrial radio frequency interference, which can appear as a transient signal. In this paper we propose two schemes for the detection of transient sources. The first is a generalized likelihood ratio test designed for terrestrial interferences that appear in the near field region. The second is a modification of the first one, designed for sources whose steering vector is known to be in the array manifold, such as astronomical sources. Both of the proposed detectors are based on two consecutive sample covariance matrices computed by the array, and they have the desirable property of a constant false alarm rate. We provide a simple analysis of the proposed method as well as a computer simulation. The computer simulation results suggest that the proposed detectors outperform the detector that is currently used by the low frequency array (LOFAR) radio telescope processor.

Linear Least Squares is a very well known technique for parameter estimation, which is used even when sub-optimal, because of its very low computational requirements and the fact that exact knowledge of the noise statistics is not required. Surprisingly, bounding the probability of large errors with finitely many samples has been left open, especially when dealing with correlated noise with unknown covariance. In this paper we analyze the finite sample performance of the linear least squares estimator under sub-Gaussian martingale difference noise. In order to analyze this important question we used concentration of measure bounds. When applying these bounds we obtained tight bounds on the tail of the estimator's distribution. We show the fast exponential convergence of the number of samples required to ensure a given accuracy with high probability. We provide probability tail bounds on the estimation error's norm. Our analysis method is simple and uses simple L∞ type bounds on the estimation error. The tightness of the bounds is tested through simulation. The proposed bounds make it possible to predict the number of samples required for least squares estimation even when least squares is sub-optimal and used for computational simplicity. The finite sample analysis of least squares models with this general noise model is novel.

This paper studies the security aspect of gossip-based decentralized optimization algorithms for multi agent systems against data injection attacks. Our contributions are two-fold. First, we show that the popular distributed projected gradient method (by Nedić et al.) can be attacked bycoordinated insiderattacks, in which the attackers are able to steer the final state to a point of their choosing. Second, we propose a metric that can be computed locally by the trustworthy agents processing their own iterates and those of their neighboring agents. This metric can be used by the trustworthy agents to detect and localize the attackers. We conclude the paper by supporting our findings with numerical experiments.

Blockchains enable tamper-proof, ordered logging for transactional data in a decentralized manner over open-access, overlay peer-to-peer networks. In this paper, we propose a decentralized framework of proactive caching in a hierarchical wireless network based on blockchains. We employ the blockchain-based smart contracts to construct an autonomous content caching market. In the market, the cache helpers are able to autonomously adapt their caching strategies according to the market statistics obtained from the blockchain, and the truthfulness of trustless nodes are financially enforced by smart contract terms. Further, we propose an incentive-compatible consensus mechanism based on proof-of-stake to financially encourage the cache helpers to stay active in service. We model the interaction between the cache helpers and the content providers as a Chinese restaurant game. Based on the theoretical analysis regarding the Nash equilibrium of the game, we propose a decentralized strategy-searching algorithm using sequential best response. The simulation results demonstrate both the efficiency and reliability of the proposed equilibrium searching algorithm.

We consider a binary hypothesis testing problem using Wireless Sensor Networks (WSNs). The decision is made by a fusion center and is based on received data from the sensors. We focus on an energy and spectrum efficient transmission scheme used to reduce the energy consumption and spectrum usage during the detection task. We propose a Density-Based Multiple Access (DBMA) transmission protocol that performs a censoring-type transmission based on the density of observations using multiple access channels (MAC). Specifically, in DBMA, only sensors with highly informative observations transmit their data in each data collection. The sensors transmit a common shaping waveform and the fusion center receives a superposition of the analog transmitted signals. DBMA has important advantages for detection tasks in WSNs. First, it is highly energy and bandwidth efficient due to transmissions saving and narrowband transmission over MAC. Second, it can be implemented by simple and dumb sensors (oblivious of observation statistics, and local data processing is not required) which simplifies the implementation as compared to existing MAC transmission schemes for detection in WSNs. We establish both finite sample analysis and asymptotic analysis of the error probability with respect to the network size and provide conditions for obtaining exponential decay of the error. Numerical examples are provided to demonstrate the DBMA performance.

We consider a multi-armed bandit game where N players compete for K arms for T turns. Each player has different expected rewards for the arms, and the instantaneous rewards are independent and identically distributed. Performance is measured using the expected sum of regrets, compared to the optimal assignment of arms to players. We assume that each player only knows her actions and the reward she received each turn. Players cannot observe the actions of other players, and no communication between players is possible. We present a distributed algorithm and prove that it achieves an expected sum of regrets of near-O\left(\log^{2}T\right). This is the first algorithm to achieve a poly-logarithmic regret in this fully distributed scenario. All other works have assumed that either all players have the same vector of expected rewards or that communication between players is possible.

Consider a channel allocation problem over a frequency-selective channel. There are K channels (frequency-bands) and N users such that K = bN for some positive integer b. We want to allocate b channels (or resource blocks) for each user. Due to the nature of the frequency-selective channel, each user considers some channels to be better than others. Allocating each user only good channels will result in better performance than an allocation that ignores the selectivity of the channel. The optimal solution for this resource allocation problem can be computed using the Hungarian algorithm. However, this requires knowledge of the numerical value of all the channel gains, which makes this approach impractical for large networks. We suggest a suboptimal approach, that only requires knowing what the M-best channels of each user are. We find the minimal value of M such that there exists an allocation where all the b channels each user gets are among his M-best. This leads to a feedback of significantly less than one bit per user per channel. For a large class of fading distributions, including Rayleigh, Rician, m-Nakagami and more, this suboptimal approach leads to both an asymptotically (in K) optimal sum-rate and asymptotically optimal minimal rate. Our non-opportunistic approach achieves asymptotically full multiuser diversity and optimal fairness, in contrast to all existing limited feedback algorithms.

Conventional overlay and underlay spectrum sharing strategies enable the cognitive Small Cells (SCeNBs) to access a spectrum of macrocells. The problem of the overlay approach is strong dependency of its efficiency on an activity of macrocell users. Thus, not enough resources remain for the SCeNB users if the macrocell is loaded heavily. The main weakness of the underlay approach is that it can result in a low transmission efficiency because the transmission power level of the SCeNBs is restricted. To overcome the above-mentioned problems of both spectrum sharing strategies, a hybrid spectrum sharing combining both overlay and underlay has been introduced in literature. In this paper, we propose a new distributed resource allocation algorithm for hybrid spectrum sharing tailored for realistic scenarios considering varying channel quality over individual resource blocks. The algorithm considers the buffer state at the SCeNBs, ratio of the resources available in the overlay and underlay modes, and channel quality experienced by the users at individual resource blocks. The proposed scheme increases the amount of traffic served for SCeNB users by 22.7% and reduces the packet delay by 27.1% for heavy loaded network comparing to existing schemes.

We address the problem of existence of unbiased constrained parameter estimators. We show that if the constrained set of parameters is compact and the hypothesized distributions are absolutely continuous with respect to one another, then there exists no unbiased estimator. Weaker conditions for the absence of unbiased constrained estimators are also specified. We provide several examples, which demonstrate the utility of these conditions.

In this paper we consider the problem of channel allocation for users who access a common channel using OFDMA. The spectrum is divided into subchannels and we assume that the bandwidth of each subchannel is smaller than the coherence bandwidth. This leads to correlations between the channel coefficients for each user. We model these correlated channels as an m-dependent sequence and generate an interference game at random, according to some marginal fading distribution. Performance is measured by the sum of achievable rates. Using a novel analysis of the random pure NE of the game, we prove that even for correlated channels the M-frequency selective interference game, suggested in previous work, has only Nash equilibria that exhibit good performance with high probability, asymptotically with the number of users. This game is the basis for an asymptotically optimal and fully distributed OFDMA channel allocation algorithm, presented in simulations.

In this paper, we investigate the global energy efficiency of a bidirectional amplify-and-forward relay MIMO system. It is assumed that the relay serves two end-users, each requiring a minimum target rate. Two algorithms are proposed, a suboptimal one with lower complexity, and an optimal one with slightly higher complexity. We present numerical results that compare the two algorithms and exhibit several optimality properties concerning the global energy efficiency function.

We study stochastic linear optimization problem with bandit feedback. The set of arms take values in an N-dimensional space and belongs to a bounded polyhedron described by finitely many linear inequalities. We present an algorithm that has O(Nlog1+ε(T)) expected regret for any ε > 0 in T rounds. The algorithm alternates between exploration and exploitation phases where it plays a deterministic set of arms in the exploration phases and a greedily selected arm in the exploitation phases. The regret bound of SEE compares well to the lower bounds of Ω(N log T) that can be derived by a direct adaptation of Lai-Robbin's lower bound proof [1]. Our key insight is that for a polyhedron the optimal arm is robust to small perturbations in the reward function. Consequently, a greedily selected arm is guaranteed to be optimal when the estimation error falls below a suitable threshold. Our solution resolves a question posed by [2] that left open the possibility of efficient algorithms with logarithmic regret bounds. The simplicity of our approach allows us to derive probability one bounds on the regret, in contrast to the weak convergence results of other papers. This ensures that with probability one only finitely many errors occur in the exploitation phase. Numerical investigations show that while theoretical results are asymptotic the performance of our algorithms compares favorably to state-of-the-art algorithms in finite time as well.

The core component of a cognitive radio is its detector. When a device is equipped with multiple antennas, the detection method is usually based on an eigenvalue analysis. This paper explores the performance of the most common largest eigenvalue detector, for the case of a narrowband temporally white signal and calibrated receiver noise. In contrast to popular Gaussian assumption, our performance bounds are valid for any signal and noise that belong to the wide class of sub-Gaussian random processes. Moreover, the results are given in closed-form for any finite number of observations and antennas, in contrary to the widespread asymptotic analysis approach.

This paper considers an online optimization algorithm for actively learning trusts on social networks. We first introduce a DeGroot model for opinion dynamics under the influence of stubborn agents and demonstrate how an observer with estimates of the individuals opinions can actively learn the relative trusts among different agents, by fitting the opinions to the steady state equations of the social system equations. The main contribution of this article is an online algorithm for extracting the trust parameters from streaming data of randomly sampled, noisy opinion estimates. The algorithm is based on the stochastic proximal gradient method and it is proven to converge almost surely. Finally, numerical results are presented to corroborate our findings.

In this paper we analyze the connectivity of cognitive radio ad-hoc networks. Contrary to previous works, we pursue the connectivity of both the primary and secondary networks, a state we call “simultaneous connectivity”. We determine that if the networks are simultaneously connected then their infinite connected components are unique. In addition, we characterize the region of densities in which both the primary and secondary networks have a unique infinite connected component.

This paper deals with the problem of distributed resource allocation in multiple-input multiple-output multi-carrier multiple-access channel networks. The assignment between users and subcarriers is allocated together with the users' transmit powers for energy efficiency maximization, by means of a novel approach which merges the popular Dinkelbach's algorithm with the frameworks of distributed auction theory and stable matching. Two distributed algorithms are presented, which can be implemented in a fully decentralized way. The former is guaranteed to converge to the global optimum of the system energy efficiency, up to a threshold which can be set in advance, while the latter enjoys weaker optimality properties, but has an even lower computational complexity. Additionally, we develop a novel energy consumption model which explicitly accounts for the energy consumption due to feedback transmissions. Employing this new model, it is shown that the proposed distributed algorithms can even outperform centralized resource allocations which require a larger feedback energy consumption.

In this paper, we introduce the two-user asynchronous cognitive multiple access channel (ACMAC). This channel model includes two transmitters, an uninformed one and an informed one, which knows prior to the beginning of a transmission the message which the uninformed transmitter is about to send. We assume that the channel from the uninformed transmitter to the receiver suffers a fixed but unknown delay. We further introduce a modified model, referred to as the asynchronous codeword cognitive multiple access channel (ACC-MAC), which differs from the ACMAC in that the informed user knows the signal that is to be transmitted by the other user, rather than the message that it is about to transmit. We state inner and outer bounds on the ACMAC and the ACC-MAC capacity regions, and we specialize the results to the Gaussian case. Furthermore, we characterize the capacity regions of these channels in terms of multi-letter expressions. Finally, we provide an example that instantiates the difference between message side-information and codeword side-information.

The problem of distributed rate maximization in multichannel ALOHA networks is considered. First, we study the problem of constrained distributed rate maximization, where user rates are subject to total transmission probability constraints. We propose a best-response algorithm, where each user updates its strategy to increase its rate according to the channel state information and the current channel utilization. We prove the convergence of the algorithm to a Nash equilibrium in both homogeneous and heterogeneous networks using the theory of potential games. The performance of the best-response dynamic is analyzed and compared to a simple transmission scheme, where users transmit over the channel with the highest collision-free utility. Then, we consider the case where users are not restricted by transmission probability constraints. Distributed rate maximization under uncertainty is considered to achieve both efficiency and fairness among users. We propose a distributed scheme where users adjust their transmission probability to maximize their rates according to the current network state, while maintaining the desired load on the channels. We show that our approach plays an important role in achieving the Nash bargaining solution among users. Sequential and parallel algorithms are proposed to achieve the target solution in a distributed manner. The efficiencies of the algorithms are demonstrated through both theoretical and simulation results.

We propose a new sequential deconvolution algorithm, that is applicable to imaging using moving and synthetic aperture arrays. The new method results in a higher resolution and a more accurate estimation than commonly used methods when strong interfering sources are present inside and outside the field of view (terrestrial interference, confusing sources). We demonstrate the algorithm performance over both simulated and real radio astronomical data.

Linear image deconvolution for radio-astronomy is an ill-posed problem. For this reason, a-priori knowledge is crucial for improving the performance of the deconvolution. In this paper we show that combining non-negativity constraints with an upper bound on the magnitude of each pixel in the image can significantly improve the image formation algorithm. We also show that the minimum variance distortionless response (MVDR) dirty image provides the tightest upper bound out of all beamformers. We then show how the LS-MVI image formation algorithm can be reformulated as a preconditioned weighted least squares algorithm. The resulting algorithm can be efficiently solved using the active-set method. The performance of the algorithm is demonstrated in simulation and compared with constrained least squares based on the classical dirty image.

In this paper, the problem of joint multi-pitch and direction-of-arrival (DOA) estimation for multichannel harmonic sinusoidal signals is considered. A spatio-temporal matrix signal model for a uniform linear array is defined, and then the ESPRIT method based on subspace techniques that exploits the invariance property in the time domain is first used to estimate the multi pitch frequencies of multiple harmonic signals. Followed by the estimated pitch frequencies, the DOA estimations based on the ESPRIT method are also presented by using the shift invariance structure in the spatial domain. Compared to the existing state-of-the-art algorithms, the proposed method based on ESPRIT without 2-D searching is computationally more efficient but performs similarly. An asymptotic performance analysis of the DOA and pitch estimation of the proposed method are also presented. Finally, the effectiveness of the proposed method is illustrated on a synthetic signal as well as real-life recorded data.

Several channels with asynchronous side information are introduced. We first consider single-user state-dependent channels with asynchronous side information at the transmitter. It is assumed that the state information sequence is a possibly delayed version of the state sequence, and that the encoder and the decoder are aware of the fact that the state information might be delayed. It is additionally assumed that an upper bound on the delay is known to both the encoder and the decoder, but other than that, they are ignorant of the actual delay. We consider both the causal and the noncausal cases and present achievable rates for these channels, and the corresponding coding schemes. We find the capacity of the asynchronous Gel'fand-Pinsker channel with feedback. Finally, we consider a memoryless state-dependent channel with asynchronous side information at both the transmitter and the receiver, and establish a single-letter expression for its capacity.

In this paper, a new analog error correcting code with an iterative decoder is presented for real-valued signals corrupted by impulsive noises. In the proposed algorithm, a redundancy coding matrix is used as an analog version of the cyclic redundancy check (CRC) that is commonly used for data verification in digital communication. Using this analog CRC enables an alternate decoding scheme in which iterative decoding is possible without transferring new errors between consecutive iterations. In each iteration of the algorithm, the problem of decoding the long block code is decoupled into two sets of parallel small linear programming problems. Simulation results show that this leads to a reduction in decoding complexity as compared to one-step linear programming decoding.

This paper studies the problem of competitive spectrum management in the presence of channel estimation errors. In particular, we study the effect of the channel estimation error on the Bayesian Interference Game (BIG), in which two selfsh wireless systems (players) share the same frequency band, where each player knows its own channel gains but does not know the other players channel gains. In the case where the channel is estimated perfectly, the BIG is known to have a spectrally effcient equilibrium point, which produces a higher payoff to both players than the trivial equilibrium, in which both players always interfere with each other. However, the assumption that each player knows its own channel gains impeccably is not practical due to estimation error. The latter leads to payoff perturbations, which can reduce spectral effciency by driving the spectrally effcient equilibrium point unstable. In this paper, we show that the spectral effciency is robust to small estimation errors; i.e., the BIGs spectrally effcient equilibrium point preserves its properties in the presence of estimation errors.

In this paper, the problem of self-calibration for large astronomical arrays such as the Dutch Low Frequency Array (LOFAR) is considered. We assume direction dependent gain and phase errors which need to be estimated and calibrated out. Combining the subspace fitting and least square approaches, the signal subspace of the received single short-term interval (STI) sample data of the LOFAR is used to build a cost function whose minimizer is a statistically efficient estimator of the unknown parameters-the gains and phases of the telescopes. Subsequently, an iterative algorithm for finding the minimum of the cost function is presented and the unknown calibration parameters of both the core stations and the external subarray are separated. As a result, the computational complexity of the proposed method is significantly reduced compared to the existing methods based on a direct covariance fitting. Finally, the performance of the proposed method is compared with the conventional peeling method in computer simulation. An example for calibrating the core of the LOFAR array on Cyg A is also provided.

We introduce the asynchronous cognitive multiple-access channel with an uninformed encoder and an informed one. We assume that the informed encoder knows in advance the message of the uninformed encoder and consequently its codeword, up to some delay. In addition, the informed encoder knows the set of all possible delays in the channel. We characterize the capacity region of the ACMAC in terms of multi-letter expressions. In addition, we present single-letter inner and outer bounds on the capacity region of this channel. We conclude by studying the special case of the Gaussian asynchronous multiple-access channels with an uninformed encoder.

This paper examines the problem of rate allocation for multicasting over slow Rayleigh fading channels using network coding. In the proposed model, the network is treated as a collection of Rayleigh fading multiple access channels. In this model, rate allocation schemes that are based solely on the statistics of the channels are presented. The schemes are aimed to minimize the outage probability. An upper bound is presented for the probability of outage in the fading MAC. A suboptimal solution based on this bound is given for the MAC network model. We also consider outage probability minimization for TDMA schemes for the multiple access channels.

In this paper we consider the problem of distributed throughput maximization of cognitive radio networks with the multi-channel ALOHA medium access protocol. First, we characterize the Nash Equilibrium Points (NEPs) of the network when users solve an unconstrained rate maximization (i.e., the total transmission probability equals one). Then, we focus on constrained rate maximization, where user rates are subject to a total transmission probability constraint. We propose a simple best-response algorithm that solves the constrained rate maximization, where each user updates its strategy using its local channel state information (CSI) and by monitoring the channel utilization. We prove the convergence of the proposed algorithm using the theory of potential games. Furthermore, we show that the network approaches a unique equilibrium as the number of users increases. Then, we formulate the problem of choosing the access probability as a leader-followers Stackelberg game, where a single user is chosen to be the leader to manage the network. We show that a fully distributed setup can be applied to approximately optimize the network throughput for a large number of users. Finally, we extend the model to the case where primary and secondary users co-exist in the same frequency band.

DSL systems use multi-channel processing to mitigate the electromagnetic coupling between the wires in a binder and provide high data rates to multiple users. In recent years, most multichannel processing for DSL had focused on zero-forcing (ZF) processing that was proven to be near optimal. This near optimality has been observed in numerical evaluations as well as in real life systems. However, this near optimality has only been demonstrated theoretically by relatively loose bounds. In this paper we prove novel bounds on the performance of ZF processing in DSL systems. These bounds are simpler and yet tighter than currently known bounds. These novel bounds support previously published results, and further confirm the near optimality of ZF processing.

In this paper, we consider the binary hypothesis testing problem using wireless sensor networks. We analyze the case where sensors transmit their local log-likelihood ratio (LLR) directly to a fusion center (FC) using an analog transmission scheme over multiple-access fading channels. Due to the nature of the wireless medium, the FC receives a superposition of sensor transmissions. The decision is made by the FC and is based on received data from the sensors. In contrast to the case of identical channels and i.i.d observations, the analog transmission of the LLR over multiple-access fading channels does not achieve the centralized error exponent. Large deviation tools are used in this paper to characterize the error exponent in the asymptotic regime (when the number of sensors approaches infinity) in the case of non-i.i.d observations and non-i.i.d fading channels. Chernoff bounding techniques are used to provide bounds on the error probability for a finite number of sensors when the observations and the fading channels are independent across sensors. Specific performance analysis is provided for detection over both i.i.d and spatially correlated Markovian fading channels. Simulation results then illustrate the detector's performance.

In this paper we propose to use the well known game theoretic Gale-Shapley stable marriage theorem from game theory as a basis for spectrum allocation in cognitive radio networks. We analyze the performance of the proposed solution and provide tight lower and upper bounds on both the stable allocation and the optimal allocation performance. Then we present a novel opportunistic multichannel medium access control technique that achieves stable allocation within a single CSMA contention window. We discuss practical implementation issues and put forward two other varieties of the algorithm which have lower implementation complexity. Finally, we provide simulated examples.

In this paper, we present a new analog error correcting coding scheme for real valued signals that are corrupted by impulsive noise. This product code improves Donoho's deterministic construction by using a probabilistic approach. More specifically, our construction corrects more errors than the Donoho matrices by allowing a vanishingly small probability of error (with the increase in block size). The problem of decoding the long block code is decoupled into two sets of parallel Linear Programming problems. This leads to a significant reduction in decoding complexity as compared to one-step Linear Programming decoding.

In this paper, a new adaptive beamforming algorithm with joint robustness against covariance matrix uncertainty as well as steering vector mismatch is proposed. First, the theoretical covariance matrix is estimated based on the shrinkage method. Subsequently, the difference between the actual and the presumed steering vector is estimated by solving a quadratic convex optimization problem, which enables correction of the presumed steering vector. Unlike other robust beamforming techniques, neither the norm of the steering vector nor the upper bound of the norm of the mismatch vector is assumed in our approach. Simulation results show the effectiveness of the proposed algorithm both in terms of output performance and computational complexity.

In this paper we discuss rate control for multiuser multi carrier systems, where the transmitter has a single antenna and is subject to a PSD mask limitation while the receiver has multiple receive antennas. This case is typical in many systems, where each mobile unit has a single transmit stream, and its transmit PSD is limited by regulatory constraints. This scenario is also typical DSL upstream transmission with a vector receiver. In both scenarios we are given a vector of target rates determined by the network operator and we want to set up a transmission strategy for each user at each tone. We show that in this case the problem can be solved using linear programming, rather than general convex optimization. The proposed rate allocation technique has two important applications. First, it provides a computationally simple tool to evaluate the optimal performance of multiple access systems under various operator utility functions. Second, it can serve as a practical tool for rate control of multiple access OFDM systems.

In a wireless OFDM communication system multiple players share the same spectrum while experiencing different channel realizations. Allocation algorithms exploit this feature and optimize the allocation of frequency bins according to various optimization criteria (e.g., weighted Max-Min, Nash Bargaining Solution (NBS), etc). These allocations do not allow players to transmit on the same frequency bin simultaneously. Thus, the communication channel is not fully utilized when the mutual interferences are weak. Here we propose a more general allocation scheme, called Partial Orthogonal Allocation (POA), where players can transmit simultaneously on some of the frequency bins, and maintain orthogonality of transmission on the other frequency bins. For this schema, the Nash Bargaining Solution is proposed and analyzed.

In this paper we investigate transmission scheduling by Medium Access Control (MAC) for energy-efficient detection using Wireless Sensor Networks (WSN). We consider the binary hypothesis testing problem. The decision is made by an access point and is based on received data from sensors that transmit through a fading channel. We study the significance of exploiting both Channel-State Information (CSI) and Likelihood-Ratio Information (LRI) to design an adequate MAC protocol that minimizes the total transmission energy required for optimal detection. We formulate the access problem as a history-dependent decision process. The optimal solution is mathematically intractable and suffers from exponential complexity as a function of model size. Hence, we propose an approximate solution using the Markov property to reduce complexity and make the problem mathematically tractable. We designed the LRI and CSI Based Access (LCBA) protocol based on this solution. The LCBA protocol trades off between LRI and CSI to reduce the total transmission energy. Simulation results show a significant performance gain of LCBA over existing approaches.

This paper proposes a new detection algorithm for MIMO communication systems employing high-order QAM constellations. The factor graph that corresponds to this problem is very loopy; in fact, it is a complete graph. Hence, a straightforward application of the Belief Propagation (BP) algorithm yields very poor results. Our algorithm is based on an optimal tree approximation of the Gaussian density of the unconstrained linear system. The finite-set constraint is then applied to obtain a cycle-free discrete distribution. Simulation results show that even though the approximation is not directly applied to the exact discrete distribution, applying the BP algorithm to the cycle-free factor graph outperforms current methods in terms of both performance and complexity. The improved performance of the proposed algorithm is demonstrated on the problem of MIMO detection.

In the distributed linear source coding problem a set of distributed sensors observe subsets of a data vector, and provide the fusion center with linearly encoded data. The goal is to determine the encoding matrix of each sensor such that the fusion center reconstructs the entire data vector with minimum mean square error (MSE). The recently proposed local Karhunen Loève transform (KLT) approach performs this task by optimally determining the encoding matrix of each sensor assuming the other matrices are fixed. This approach is implemented iteratively until convergence is reached. Herein, we propose a greedy-based non-iterative algorithm. In each step, one of the encoding matrices is updated by appending an additional row. The algorithm selects in a greedy fashion one sensor that provides the largest improvement in MSE, and terminates when all the encoding matrices reach their predefined encoded data size. The algorithm can be implemented recursively, and it reduces the complexity from cubic dependency on the data size, using the iterative method, to quadratic dependency. This makes it a prime candidate for on-line and real-time implementations of the distributed KLT. Simulation results show that for many covariance matrix types, the MSE performance of the suggested algorithm is equivalent to the iterative approach.

This paper considerers a symmetric Gaussian interference game with incomplete information where players choose between frequency division multiplexing (FDM) and full spread (FS) of their transmit power. Previously, the only known Nash equilibrium point for this game was the point where players mutually choose FS and interfere with each other. This point may lead to undesirable outcome from global network point of view and even for each user individually. It happens when mutual FDM is better to both users than mutual FS. In this paper, we show that if users agree to use different sub-bands in the case of FDM, then there exist a non pure-FS Nash equilibrium point, i.e. an equilibrium point where players choose FDM for some channel realizations and FS for the others. This Nash equilibrium point increases each user's throughput and therefore improves the spectrum utilization. Furthermore, to reach this point, the only instantaneous channel state information (CSI) required by each user is its interference-to-signal ratio.

In this paper we analyze an adaptive downstream multichannel VDSL precoder that is based on error signal feedback. The analysis presents sufficient conditions for precoder convergence and an upper bound on the precoder steady state error. The paper also considers and analyzes the case of partial FEXT cancellation. The analysis shows that in some scenarios (and in particular in mixed-length binders) the use of partial FEXT cancellation is crucial to achieve precoder convergence in a reasonable time. Based on this analysis we determine that convergence is achievable in most practical channels. These bounds also allow for the proper setting of the convergence parameters. The paper presents several simulations to demonstrate the theoretical results. In these simulations, setting the precoder parameters according to the analysis leads to convergence in less than 400 OFDM symbols.

We consider transmission scheduling by medium access control (MAC) protocols for energy limited wireless sensor networks (WSN) in order to maximize the network lifetime. Time-varying opportunistic protocol (TOP) for maximizing the network lifetime is proposed. By executing TOP each sensor exploits local channel state information (CSI) and local residual energy information (REI). TOP implements opportunistic strategy in terms of favoring sensors with better channels when the network is young, while less opportunistic and more conservative strategy in terms of prioritizing sensors with higher residual energy when the network is old. TOP significantly simplifies the implementation of carrier sensing as compared to other distributed MAC protocols. Simulation results show that TOP achieves significant performance gains over other distributed MAC protocols.

Least squares (LS) fitting is one of the most fundamental techniques in science and engineering. It is used to estimate parameters from multiple noisy observations. In many problems the parameters are known a-priori to be bounded integer valued, or they come from a finite set of values on an arbitrary finite lattice. In this case finding the closest vector becomes NP-Hard problem. In this paper we propose a novel algorithm, the Tomographic Least Squares Decoder (TLSD), that not only solves the ILS problem, better than other sub-optimal techniques, but also is capable of providing the a-posteriori probability distribution for each element in the solution vector. The algorithm is based on reconstruction of the vector from multiple two-dimensional projections. The projections are carefully chosen to provide low computational complexity. Unlike other iterative techniques, such as the belief propagation, the proposed algorithm has ensured convergence. We also provide simulated experiments comparing the algorithm to other sub-optimal algorithms.

This paper proposes a new algorithm for the linear least squares problem where the unknown variables are constrained to be in a finite set. The factor graph that corresponds to this problem is very loopy; in fact, it is a complete graph. Hence, applying the Belief Propagation (BP) algorithm yields very poor results. The algorithm described here is based on an optimal tree approximation of the Gaussian density of the unconstrained linear system. It is shown that even though the approximation is not directly applied to the exact discrete distribution, applying the BP algorithm to the modified factor graph outperforms current methods in terms of both performance and complexity. The improved performance of the proposed algorithm is demonstrated on the problem of MIMO detection.

In this letter we propose a novel distributed technique for dynamic spectrum management of DSL lines. The proposed method generalizes several known techniques, by imposing pricing for use of spectrum. We propose a simple mechanism that allows each line to choose an appropriate pricing function independently of the other lines. Finally, by incorporating a total power constraint, the algorithm is capable of self-correcting an overly ambitious pricing function. We also provide simulated examples based on measured DSL lines.

In this paper we derive performance bounds for tracking time-varying OFDM multiple-input multiple-output (MIMO) communication channel in the presence of additive white Gaussian noise (AWGN). We discuss two channel tracking schemes. The first tracks the filter coefficients directly in time-domain, while the second separately tracks each tone in the frequency-domain. The Kalman filter, with known channel statistics, is utilized for evaluating the performance bounds. It is shown that the time-domain tracking scheme, which exploits the sparseness of the channel impulse response, outperforms the computationally more efficient, frequency-domain tracking scheme, which does not exploit the smooth frequency response of the channel.

Crosstalk interference is the limiting factor in transmission over copper lines. Crosstalk cancellation techniques show great potential for enabling the next leap in DSL transmission rates. An important issue is the effect of finite world length on performance. In this paper we provide an analysis of the performance of linear zero-forcing precoders, used for crosstalk compensation, in the presence of quantization noise. We quantify analytically the trade off between quantization level and transmission rate degradation. We demonstrate, through simulations on real lines, the accuracy of our estimates. Finally, we show how to use these estimates as a design tool for DSL linear crosstalk precoders.

In this paper we discuss the use of cooperative game theory for analyzing interference channels. We extend our previous work, to games with N players as well as frequency selective channels and joint TDM/FDM strategies. We show that the Nash bargaining solution can be computed using convex optimization techniques. We also show that the same results are applicable to interference channels where only statistical knowledge of the channel is available. Moreover, for the special case of two player 2 times K frequency selective channel (with K frequency bins) we provide an O(K log2K) complexity algorithm for computing the Nash bargaining solution under mask constraint and using joint FDM/TDM strategies. Simulation results are also provided.

In this paper we describe the optimization of an information theoretic criterion for radar waveform design. The method is used to design radar waveforms suitable for simultaneously estimating and tracking parameters of multiple targets. Our approach generalizes the information theoretic water-filling approach of Bell. The paper has two main contributions. First, a new information theoretic design criterion for designing multiple waveforms under a joint power constraint when beamforming is used both at transmitter and receiver. Then we provide a highly efficient algorithm for optimizing the transmitted waveforms, by approximating the information theoretic cost function. We show that using Lagrange relaxation the optimization problem can be decoupled into a parallel set of low-dimensional search problems at each frequency, with dimension defined by the number of targets instead of the number of frequency bands used.

An algorithm for approximating crosstalk channel matrix inversion is proposed in this paper. The algorithm decomposes the crosstalk channel matrix into a tridiagonal matrix plus a residual matrix composed of the remaining elements. By using diagonal dominance property, the inverse of the crosstalk channel matrix is approximated. Based on these results we propose a novel precoding method with lower computational complexity for canceling the crosstalk in downstream VDSL. Computer simulation results based on measured channel data are provided to verify the efficiency of the proposed algorithm.

In this paper we analyze the interference channel as a conflict situation. This viewpoint implies that certain points in the rate region are unreasonable to one of the players. Therefore these points cannot be considered achievable based on game theoretic considerations. We then propose to use Nash bargaining solution as a tool that provides preferred points on the boundary of the game theoretic rate region. We provide analysis for the 2times2 interference channel using the FDM achievable rate region. We also outline how to generalize our results to other achievable rate regions for the interference channel as well as the multiple access channel

A time domain equalizer is a finite impulse response filter that shortens the channel impulse response to mitigate inter-symbol interference (ISI). Al-Dhahir and Cioffi proposed a design criterion for single input single output TEQ based on designing an MMSE decision feedback equalizer. They also extended this method to MIMO channels. We propose a simple implementation of time domain equalizer for MIMO channels, also based on the MMSE criterion. The solution is simplified compared to the above solution by eliminating the cross channel linear equalizers. This results in a set of M independent equalizers, each designed to meet a multi-objective channel shortening MMSE criterion. The new method is simple and provides good results for the MIMO problem. Finally, we demonstrate the efficiency of the proposed approach compared to Al-Dhahir's on measured channels, where the NEXT channels are simultaneously shortened with the direct channels. These are the first published results demonstrating MIMO-TEQ design on real life measured DSL channels.

A probabilistic sequential polling protocol (PSPP) is presented for the estimation of the sensor population in a large-scale sensor network with a mobile access point. It is shown that PSPP requires O(log/sub 2/N) sensor transmissions and a total of O((log/sub 2/N)/sup 2/) polls to achieve an arbitrarily predetermined level of accuracy.

We assess the capacity potential of very short very-high data-rate digital subscriber line loops using full-binder channel measurements collected by France Telecom R&D. Key statistics are provided for both uncoordinated and vectored systems employing coordinated transmitters and coordinated receivers. The vectoring benefit is evaluated under the assumption of transmit precompensation for the elimination of self-far-end crosstalk, and echo cancellation of self-near-end crosstalk. The results provide useful bounds for developers and providers alike.

In this paper, we demonstrate how super-resolution techniques can be used to estimate WLAN channels. The method is based on the non-stationarity of the channel impulse response over time. We then use the method to study the delay spread properties of the measured WLAN channels in the 5 GHz band. We demonstrate how super-resolution techniques can be used to estimate the different delays of the reflections as well as the power variation. We validate the method, based on an extensive set of channel measurements. We also estimate the statistical parameters of the fading process.

Constant modulus algorithms try to separate linear mixtures of sources with modulus 1. We study the identifiability of this problem: the number of samples needed to ensure that in the noiseless case we have a unique solution. For finite alphabet (L-PSK) sources, finite sample identifiability can hold only with a probability close to but not equal to 1. In a previous paper (Leshem, A. et al., Proc. IEEE Workshop on Sensor Array and Multichannel Signal Processing, 2002), we provided a subexponentially decaying upper bound on the probability of non-identifiability. Here, we provide an improved exponentially decaying upper bound, based on Chernoff bounds. We show that, under practical assumptions, this upper bound is much tighter than previously known bounds.

We prove that mixtures of continuous alphabet constant modulus sources can be identified with probability 1 with a finite number of samples (under noise-free conditions). This strengthens earlier results which only considered an infinite number of samples. The proof is based on the linearization technique of the analytical constant modulus algorithm (ACMA), together with a simple inductive argument. We then study the finite-alphabet case. In this case, we provide a subexponentially decaying upper bound on the probability of nonidentifiability for a finite number of samples. We show that under practical assumptions, this upper bound is tighter than the currently known bound. We then provide an improved exponentially decaying upper bound for the case of L-PSK signals (L is even).

Radio-astronomical observations are increasingly contaminated by interference, and suppression techniques become essential. A powerful candidate for interference mitigation is adaptive spatial filtering. We study the effect of spatial filtering techniques on radio astronomical imaging. Current deconvolution procedures such as CLEAN are shown to be unsuitable for spatially filtered data, and the necessary corrections are derived. To that end, we reformulate the imaging (deconvolution/calibration) process as a sequential estimation of the locations of astronomical sources.

We consider the detection of unknown Gaussian signals received by an array of uncalibrated nonidentical sensors, which is a problem that appears in radio astronomy. The problem is formulated as a test on the covariance structure. The generalized likelihood ratio test (GLRT) for this problem is stated and related to a simpler ad-hoc detector. We compare the method to the conventional multichannel subspace detector and show its robustness to nonidentical channels on data collected with the Westerbork radio telescope.

The fast growth of the wireless communication industry poses severe limitations on radio-astronomical observations. This is largely due to the fact that in radio astronomy, in contrast to communication systems, the signals of interest are many orders of magnitude below the receiver noise power levels. The structure of some communication signals opens the possibility to reduce the effect on radio-astronomical observations using advanced array processing techniques. One such structure is time slots, used in TDMA communication systems such as the Iridium system and the GSM system. We present the results of blanking of time-slotted interfering signals measured at the Westerbork Synthesis Radio Telescope.

We study the location of local minima of the finite sample approximation to the constant modulus cost function. This paper concentrates on source separation. The main result is a connection between the number of samples and the probability of obtaining a local minimum of the finite approximation within a given sphere around the local minimum of the CM cost function. The motivations for our study are two problems: equalization of communication signals, and blind separation of a desired signal in multiuser environment. In order to maintain simplicity we focus on the case of blind beamforming which is somewhat simpler to analyze.

Abstract In this paper we prove the equiconsistency of “Every ω1 –tree which is first order definable over ( , ε) has a cofinal branch” with the existence of a reflecting cardinal. We also prove that the addition of MA to the definable tree property increases the consistency strength to that of a weakly compact cardinal. Finally we comment on the generalization to higher cardinals.

Radio-astronomical observations are increasingly contaminated by interference, and suppression techniques become essential. A powerful candidate for interference mitigation is adaptive spatial filtering. We study the effect of spatial filtering techniques on radio-astronomical imaging. Current deconvolution procedures, such as CLEAN, are shown to be unsuitable for spatially filtered data, and the necessary corrections are derived. To that end, we reformulate the imaging (deconvolution/calibration) process as a sequential estimation of the locations of astronomical sources. This not only leads to an extended CLEAN algorithm, but also the formulation allows the insertion of other array signal processing techniques for direction finding and gives estimates of the expected image quality and the amount of interference suppression that can be achieved. Finally, a maximum-likelihood (ML) procedure for the imaging is derived, and an approximate ML image formation technique is proposed to overcome the computational burden involved. Some of the effects of the new algorithms are shown in simulated images.

In this paper we present a Newton scoring algorithm for the maximum likelihood separation and direction of arrival estimation of constant modulus signals, using a calibrated array. The main technical step is the inversion of the Fisher information matrix, and an analytic formula for the update step in the Newton method. We present the algorithm based on the derived update and discuss potential initializations. We also present the computational complexity of the update. Finally we present simulation results comparing the method to the ESPRIT and the CM-DOA.

Abstract In this paper we prove the independence of for n ≥ 3. We show that can be forced to be above any ordinal of L using set forcing. For we prove that it can be forced, using set forcing, to be above any L cardinal κ such that κ is Π1 definable without parameters in L. We then show that cannot be forced by a set forcing to be above every cardinal of L Finally we present a class forcing construction to make greater than any given L cardinal.

We present an algorithm for the calibration of sensor arrays in the presence of multipath. The algorithm is based on two sets of calibration data obtained from two angularly separated transmitting points. Simulation results demonstrating the performance of the algorithm are included.

An efficient algorithm for estimating the time delays and the directions-of-arrival of multiple reflections of a known signal is presented. The algorithm is based on an iterative scheme that transforms the multidimensional maximum likelihood criterion into two sets of simple one dimensional maximisations. Simulation results illustrating the performance of the algorithm in comparison with the Cramer-Rao bound are included.