Causal tracing systematically intervenes on a large language model's (LLM's) internal representations to uncover and quantify the causal pathways linking specific inputs or computations to specific metrics of interest, quantifying the LLM's behavior.Building on previous single-component or single-layer studies, this paper presents a unified framework for causally tracing multiple components simultaneously.This framework systematically identifies the subsets of components (e.g., attention heads and multi-layer perceptron neurons) most critical to a desired target performance metric (e.g., accuracy and fairness).This is achieved by incorporating flexible interventions applied to a wide range of desired metrics.To address the combinatorial complexity of the multicomponent problem, an efficient algorithm is designed that leverages soft interventions and a carefully designed metric transformation, converting the combinatorial search problem into a continuous one that can be solved efficiently under proper constraints, thereby generating proper binary decisions for selecting components.Experimental results demonstrate that the proposed method efficiently identifies subsets of the model's components that have a high impact on the target metric, outperforming existing baseline approaches.Our code is available at https://github.com/ZiruiYan/ multi-component-causal-tracing.

This paper introduces a general framework for risk-sensitive bandits that integrates the notions of risk-sensitive objectives by adopting a rich class of {\em distortion riskmetrics}. The introduced framework subsumes the various existing risk-sensitive models. An important and hitherto unknown observation is that for a wide range of riskmetrics, the optimal bandit policy involves selecting a \emph{mixture} of arms. This is in sharp contrast to the convention in the multi-arm bandit algorithms that there is generally a \emph{solitary} arm that maximizes the utility, whether purely reward-centric or risk-sensitive. This creates a major departure from the principles for designing bandit algorithms since there are uncountable mixture possibilities. The contributions of the paper are as follows: (i) it formalizes a general framework for risk-sensitive bandits, (ii) identifies standard risk-sensitive bandit models for which solitary arm selections is not optimal, (iii) and designs regret-efficient algorithms whose sampling strategies can accurately track optimal arm mixtures (when mixture is optimal) or the solitary arms (when solitary is optimal). The algorithms are shown to achieve a regret that scales according to $O((\log T/T )^{\nu})$, where $T$ is the horizon, and $\nu>0$ is a riskmetric-specific constant.

Causal representation learning (CRL) is the process of disentangling the *latent* low-dimensional causally-related generating factors underlying high-dimensional observable data. Extensive recent studies have characterized CRL identifiability and *perfect* recovery of the latent variables and their attendant causal graph. This paper introduces the notion of *reward-oriented* CRL, the purpose of which is to move away from perfectly learning the latent representation and instead learning it to the extent needed for optimizing a desired downstream task (reward). In reward-oriented CRL, perfectly learning the latent representation can be excessive; instead, it must be learned at the *coarsest* level sufficient for optimizing the desired task. Reward-oriented CRL is formalized as the optimization of a desired function of the observable data over the space of all possible interventions and focuses on linear causal and transformation models. To sequentially identify the optimal subset of interventions, an adaptive exploration algorithm is designed that learns the latent causal graph and the variables needed to identify the best intervention. It is shown that for an $n$-dimensional latent space and a $d$-dimensional observation space, over a horizon $T$ the algorithm's regret scales as $\tilde O(d^{\frac{1}{3}}n^{\frac{1}{3}}u^{\frac{2}{3}}T^{\frac{2}{3}} + u\sqrt{T})$, where $u$ measures total uncertainty in the graph estimates. Furthermore, an almost-matching lower bound is shown to scale as $\Omega(d^{\frac{1}{3}}n^{\frac{1}{3}}p^{\frac{2}{3}}T^{\frac{2}{3}} + p\sqrt{T})$, in which $u$ is replaced by $p$ that counts the number of causal paths in the graph.

This paper addresses intervention-based causal representation learning (CRL) under a general nonparametric latent causal model and an unknown transformation that maps the latent variables to the observed variables. Linear and general transformations are investigated. The paper addresses both the identifiability and achievability aspects. Identifiability refers to determining algorithm-agnostic conditions that ensure the recovery of the true latent causal variables and the underlying latent causal graph. Achievability refers to the algorithmic aspects and addresses designing algorithms that achieve identifiability guarantees. By drawing novel connections between score functions (i.e., the gradients of the logarithm of density functions) and CRL, this paper designs a score-based class of algorithms that ensures both identifiability and achievability. First, the paper focuses on linear transformations and shows that one stochastic hard intervention per node suffices to guarantee identifiability. It also provides partial identifiability guarantees for soft interventions, including identifiability up to mixing with parents for general causal models and perfect recovery of the latent graph for sufficiently nonlinear causal models. Secondly, it focuses on general transformations and demonstrates that two stochastic hard interventions per node are sufficient for identifiability. This is achieved by defining a differentiable loss function whose global optima ensure identifiability for general CRL. Notably, one does not need to know which pair of interventional environments has the same node intervened. Finally, the theoretical results are empirically validated via experiments on structured synthetic data and image data.

This paper investigates two hitherto unaddressed aspects of best arm identification (BAI) in stochastic multi-armed bandits in the fixed-confidence setting. The first aspect is related to the optimality and efficiency tradeoff. Specifically, the two key metrics for assessing bandit algorithms are their computational efficiency and performance optimality (e.g., in sample complexity). In the stochastic BAI literature, there have been advances in designing algorithms to achieve optimal performance at the expense of being computationally expensive (e.g., optimization-based methods). Similarly, there have been also advances in designing algorithms with high computational efficiency that have provable gaps to the optimal performance (e.g., the$\beta $-optimal approaches in top-two methods). This paper introduces a framework for BAI that achieves optimal performance with a computationally efficient set of decision rules. The central process that facilitates this is a routine for sequentially estimating the optimal allocations up to sufficient fidelity. Specifically, these estimates are accurate enough for identifying the best arm (hence, achieving optimality) but not overly accurate to an unnecessary extent that creates excessive computational complexity (hence, maintaining efficiency). The second aspect pertains to the class of parametric stochastic bandits. The existing literature has only focused on the exponential family of distributions. This paper addresses any arbitrary family of distributions parameterized by their mean values (under mild regularity conditions). The optimality is established analytically, and numerical evaluations are provided to assess the analytical guarantees and compare the performance with those of the existing ones.

This paper focuses on causal representation learning (CRL) under a general nonparametric latent causal model and a general transformation model that maps the latent data to the observational data. It establishes identifiability and achievability results using two hard uncoupled interventions per node in the latent causal graph. Notably, one does not know which pair of intervention environments have the same node intervened (hence, uncoupled). For identifiability, the paper establishes that perfect recovery of the latent causal model and variables is guaranteed under uncoupled interventions. For achievability, an algorithm is designed that uses observational and interventional data and recovers the latent causal model and variables with provable guarantees. This algorithm leverages score variations across different environments to estimate the inverse of the transformer and, subsequently, the latent variables. The analysis, additionally, recovers the identifiability result for two hard coupled interventions, that is when metadata about the pair of environments that have the same node intervened is known. This paper also shows that when observational data is available, additional faithfulness assumptions that are adopted by the existing literature are unnecessary.

This paper considers causal bandits (CBs) for the sequential design of interventions in a causal system. The objective is to optimize a reward function via minimizing a measure of cumulative regret with respect to the best sequence of interventions in hindsight. The paper advances the results on CBs in three directions. First, the structural causal models (SCMs) are assumed to be unknown and drawn arbitrarily from a general class $\mathcal{F}$ of Lipschitz-continuous functions. Existing results are often focused on (generalized) linear SCMs. Second, the interventions are assumed to be generalized soft with any desired level of granularity, resulting in an infinite number of possible interventions. The existing literature, in contrast, generally adopts atomic and hard interventions. Third, we provide general upper and lower bounds on regret. The upper bounds subsume (and improve) known bounds for special cases. The lower bounds are generally hitherto unknown. These bounds are characterized as functions of the (i) graph parameters, (ii) eluder dimension of the space of SCMs, denoted by $\mathrm{dim}(\mathcal{F})$, and (iii) the covering number of the function space, denoted by $\mathrm{cn}(\mathcal{F})$. Specifically, the cumulative achievable regret over horizon $T$ is $\mathcal{O}(K d^{L-1}\sqrt{T\,\mathrm{dim}(\mathcal{F}) \log(\mathrm{cn}(\mathcal{F}))})$, where $K$ is related to the Lipschitz constants, $d$ is the graph’s maximum in-degree, and $L$ is the length of the longest causal path. The upper bound is further refined for special classes of SCMs (neural network, polynomial, and linear), and their corresponding lower bounds are provided.

This paper investigates a hitherto unaddressed as-pect of best arm identification (BAI) in stochastic multi-armed bandits in the fixed -confidence setting. Two essential metrics for assessing bandit algorithms are computational efficiency and performance optimality (e.g., in sample complexity). In stochastic BAI literature, there have been advances in designing algorithms to achieve optimal performance, but they are generally computationally expensive to implement (e.g., optimization-based methods). There also exist approaches that have high computationally efficiency but do not achieve the optimal performance (e.g., UCB-based methods) or achieve it up to a gap (e.g., the$\beta-$optimal approaches in top-two methods). This paper introduces a framework and an algorithm for BAI that achieves optimal performance with a computationally efficient set of decision rules. The central process that facilitates this is a routine for sequentially estimating the optimal allocations up to sufficient fidelity. Specifically, these estimates are accurate enough for identifying the best arm (hence, achieving optimality) but not excessively accurate to an unnecessary extent (hence, maintaining efficiency). Numerical evaluations are provided to (i) establish the optimality and efficiency of the algorithm, (ii) showcase the implicit estimation property of the proposed allocation rules, and (ii) demonstrate the superior performance of the proposed algorithms compared to the existing ones.

This paper investigates the robustness of causal bandits (CBs) in the face of temporal model fluctuations. This setting deviates from the existing literature's widely-adopted assumption of constant causal models. The focus is on causal systems with linear structural equation models (SEMs). The SEMs and the time-varying pre- and post-interventional statistical models are all unknown and subject to variations over time. The goal is to design a sequence of interventions that incur the smallest cumulative regret compared to an oracle aware of the entire causal model and its fluctuations. A robust CB algorithm is proposed, and its cumulative regret is analyzed by establishing both upper and lower bounds on the regret. It is shown that in a graph with maximum in-degree$d$, length of the largest causal path$L$, and an aggregate model deviation$C$, the regret is upper bounded by$\tilde{\mathrm{O}}(d^{L-\frac{1}{2}}(\sqrt{T}+C))$and lower bounded by$\Omega(d^{\frac{L}{2}-2}\max\{\sqrt{T}\,\ d^{2}C\})$. The proposed algorithm achieves nearly optimal$\tilde{\mathcal{O}}(\sqrt{T})$regret when$C$is$o(\sqrt{T})$, maintaining sub-linear regret for a broad range of C.

Consider a data-generation process that transforms low-dimensional _latent_ causally-related variables to high-dimensional _observed_ variables. Causal representation learning (CRL) is the process of using the observed data to recover the latent causal variables and the causal structure among them. Despite the multitude of identifiability results under various interventional CRL settings, the existing guarantees apply exclusively to the _infinite-sample_ regime (i.e., infinite observed samples). This paper establishes the first sample-complexity analysis for the finite-sample regime, in which the interactions between the number of observed samples and probabilistic guarantees on recovering the latent variables and structure are established. This paper focuses on _general_ latent causal models, stochastic _soft_ interventions, and a linear transformation from the latent to the observation space. The identifiability results ensure graph recovery up to ancestors and latent variables recovery up to mixing with parent variables. Specifically, ${\cal O}((\log \frac{1}{\delta})^{4})$ samples suffice for latent graph recovery up to ancestors with probability $1 - \delta$, and ${\cal O}((\frac{1}{\epsilon}\log \frac{1}{\delta})^{4})$ samples suffice for latent causal variables recovery that is $\epsilon$ close to the identifiability class with probability $1 - \delta$.

Despite the multifaceted recent advances in interventional causal representation learning (CRL), they primarily focus on the stylized assumption of single-node interventions. This assumption is not valid in a wide range of applications, and generally, the subset of nodes intervened in an interventional environment is *fully unknown*. This paper focuses on interventional CRL under unknown multi-node (UMN) interventional environments and establishes the first identifiability results for *general* latent causal models (parametric or nonparametric) under stochastic interventions (soft or hard) and linear transformation from the latent to observed space. Specifically, it is established that given sufficiently diverse interventional environments, (i) identifiability *up to ancestors* is possible using only *soft* interventions, and (ii) *perfect* identifiability is possible using *hard* interventions. Remarkably, these guarantees match the best-known results for more restrictive single-node interventions. Furthermore, CRL algorithms are also provided that achieve the identifiability guarantees. A central step in designing these algorithms is establishing the relationships between UMN interventional CRL and score functions associated with the statistical models of different interventional environments. Establishing these relationships also serves as constructive proof of the identifiability guarantees.

Causal interactions among a group of variables are often modeled by a single causal graph. In some domains, however, these interactions are best described by multiple co-existing causal graphs, e.g., in dynamical systems or genomics. This paper addresses the hitherto unknown role of interventions in learning causal interactions among variables governed by a mixture of causal systems, each modeled by one directed acyclic graph (DAG). Causal discovery from mixtures is fundamentally more challenging than single-DAG causal discovery. Two major difficulties stem from (i) an inherent uncertainty about the skeletons of the component DAGs that constitute the mixture and (ii) possibly cyclic relationships across these component DAGs. This paper addresses these challenges and aims to identify edges that exist in at least one component DAG of the mixture, referred to as the *true* edges. First, it establishes matching necessary and sufficient conditions on the size of interventions required to identify the true edges. Next, guided by the necessity results, an adaptive algorithm is designed that learns all true edges using ${\cal O}(n^2)$ interventions, where $n$ is the number of nodes. Remarkably, the size of the interventions is optimal if the underlying mixture model does not contain cycles across its components. More generally, the gap between the intervention size used by the algorithm and the optimal size is quantified. It is shown to be bounded by the *cyclic complexity number* of the mixture model, defined as the size of the minimal intervention that can break the cycles in the mixture, which is upper bounded by the number of cycles among the ancestors of a node.

Designing causal bandit algorithms depends on two central categories of assumptions: (i) the extent of information about the underlying causal graphs and (ii) the extent of information about interventional statistical models. There have been extensive recent advances in dispensing with assumptions on either category. These include assuming known graphs but unknown interventional distributions, and the converse setting of assuming unknown graphs but access to restrictive hard/$\operatorname{do}$ interventions, which removes the stochasticity and ancestral dependencies. Nevertheless, the problem in its general form, i.e., _unknown_ graph and _unknown_ stochastic intervention models, remains open. This paper addresses this problem and establishes that in a graph with $N$ nodes, maximum in-degree $d$ and maximum causal path length $L$, after $T$ interaction rounds the regret upper bound scales as $\tilde{\mathcal{O}}((cd)^{L-\frac{1}{2}}\sqrt{T} + d + RN)$ where $c>1$ is a constant and $R$ is a measure of intervention power. A universal minimax lower bound is also established, which scales as $\Omega(d^{L-\frac{3}{2}}\sqrt{T})$. Importantly, the graph size $N$ has a diminishing effect on the regret as $T$ grows. These bounds have matching behavior in $T$, exponential dependence on $L$, and polynomial dependence on $d$ (with the gap $d\ $). On the algorithmic aspect, the paper presents a novel way of designing a computationally efficient CB algorithm, addressing a challenge that the existing CB algorithms using soft interventions face.

This paper considers the problem of sequentially detecting a change in the joint distribution of multiple data sources under a sampling constraint. Specifically, the channels or sources generate observations that are independent over time, but not necessarily across channels. The joint distribution of an unknown subset of sources changes at an unknown time instant. Moreover, there is a hard constraint that only a fixed number of sources can be sampled at each time instant, but the sources can be selected dynamically based on the already collected data. The goal is to sequentially observe the sources according to the constraint, and stop sampling as quickly as possible after the change while controlling the false alarm rate below a user-specified level. Thus, a policy for this problem consists of a joint sampling and change-detection rule. A non-randomized policy is studied, and an upper bound is established on its worst-case conditional expected detection delay with respect to both the change point and the observations from the affected sources before the change. In certain cases, this rule achieves first-order asymptotic optimality as the false alarm rate tends to zero, simultaneously under every possible post-change distribution and among all schemes that satisfy the same sampling and false alarm constraints. These general results are subsequently applied to the problems of (i) detecting a change in the marginal distributions of (not necessarily independent) information sources, and (ii) detecting a change in the covariance structure of Gaussian information sources.

We study best arm identification in a restless multi-armed bandit setting with finitely many arms. The discrete-time data generated by each arm forms a homogeneous Markov chain taking values in a common, finite-state space. The state transitions in each arm are captured by an ergodic transition probability matrix (TPM) that is a member of a single-parameter exponential family of TPMs. The real-valued parameters of the arm TPMs are unknown and belong to a given space. Given a function f defined on the common state space of the arms, the goal is to identify the best arm—the arm with the largest average value of f evaluated under the arm’s stationary distribution—with the fewest number of samples, subject to an upper bound on the decision’s error probability (i.e., the fixed-confidence regime). A lower bound on the growth rate of the expected stopping time is established in the asymptote of a vanishing error probability. Furthermore, a policy for best arm identification is proposed, and its expected stopping time is proved to have an asymptotic growth rate that matches the lower bound. It is demonstrated that tracking the long-term behavior of a certain Markov decision process and its state-action visitation proportions are the key ingredients in analyzing the converse and achievability bounds. It is shown that under every policy, the state-action visitation proportions satisfy a specific approximate flow conservation constraint and that these proportions match the optimal proportions dictated by the lower bound under any asymptotically optimal policy. The prior studies on best arm identification in restless bandits focus on independent observations from the arms, rested Markov arms, and restless Markov arms with known arm TPMs. In contrast, this work is the first to study best arm identification in restless bandits with unknown arm TPMs.

Domain generalization (DG) aims to train a model to perform well in unseen domains under different distributions. This paper considers a more realistic yet more challenging scenario, namely Single Domain Generalization (Single-DG), where only a single source domain is available for training. To tackle this challenge, we first try to understand when neural networks fail to generalize? We empirically ascertain a property of a model that correlates strongly with its generalization that we coin as "model sensitivity". Based on our analysis, we propose a novel strategy of Spectral Adversarial Data Augmentation (SADA) to generate augmented images targeted at the highly sensitive frequencies. Models trained with these hard-to-learn samples can effectively suppress the sensitivity in the frequency space, which leads to improved generalization performance. Extensive experiments on multiple public datasets demonstrate the superiority of our approach, which surpasses the state-of-the-art single-DG methods by up to 2.55%. The source code is available at https://github.com/DIAL-RPI/Spectral-Adversarial-Data-Augmentation.

This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model to minimize cumulative regret with respect to the best intervention in hindsight. This is, naturally, posed as a causal bandit problem. The focus is on causal bandits for linear structural equation models (SEMs) and soft interventions. It is assumed that the graph's structure is known and has $N$ nodes. Two linear mechanisms, one soft intervention and one observational, are assumed for each node, giving rise to $2^N$ possible interventions. The majority of the existing causal bandit algorithms assume that at least the interventional distributions of the reward node's parents are fully specified. However, there are $2^N$ such distributions (one corresponding to each intervention), acquiring which becomes prohibitive even in moderate-sized graphs. This paper dispenses with the assumption of knowing these distributions or their marginals. Two algorithms are proposed for the frequentist (UCB-based) and Bayesian (Thompson sampling-based) settings. The key idea of these algorithms is to avoid directly estimating the $2^N$ reward distributions and instead estimate the parameters that fully specify the SEMs (linear in $N$) and use them to compute the rewards. In both algorithms, under boundedness assumptions on noise and the parameter space, the cumulative regrets scale as $\tilde{\cal O} (d^{L+\frac{1}{2}} \sqrt{NT})$, where $d$ is the graph's maximum degree, and $L$ is the length of its longest causal path. Additionally, a minimax lower of $\Omega(d^{\frac{L}{2}-2}\sqrt{T})$ is presented, which suggests that the achievable and lower bounds conform in their scaling behavior with respect to the horizon $T$ and graph parameters $d$ and $L$.

This paper considers the problem of estimating the structure of structurally similar graphical models in high dimensions. This problem is pertinent in multi-modal or multi-domain datasets that consist of multiple information domains, each modeled by one probabilistic graphical model (PGM), e.g., in brain network modeling using different neuroimaging modalities. Induced by an underlying shared causal source, the domains, and subsequently their associated PGMs, can have structural similarities. This paper focuses on Gaussian and Ising models and characterizes the information-theoretic sample complexity of estimating the structures of a pair of PGMs in the degree-bounded and edge-bounded subclasses. The PGMs are assumed to have$p$nodes with distinct and unknown structures. Their similarity is accounted for by assuming that a pre-specified set of$q$nodes form identical subgraphs in both PGMs. Necessary and sufficient conditions on the sample complexity for a bounded probability of error are characterized. The necessary conditions are information-theoretic (algorithm-independent), delineating the statistical difficulty of the problem. The sufficient conditions are based on deploying maximum likelihood decoders. While the specifics of the results vary across different subclasses and parameter regimes, one key observation is that in specific subclasses and regimes, the sample complexity varies with$p$and$q$according to$\Theta (\log (p-q))$. For Ising models, a low complexity, online structure estimation (learning) algorithm based on multiplicative weights is also proposed. Numerical evaluations are also included to illustrate the interplay among different parameters on the sample complexity when the structurally similar graphs are recovered by a maximum likelihood-based graph decoder and the proposed online estimation algorithm.

A wide range of multi-agent decision-making problems can be abstracted as a federated multi-armed bandit (FMAB) problem. A key challenge of the FMAB problem is that the exploration-exploitation dichotomy inherited from the multi-armed bandit aspect is compounded with data heterogeneity in federated learning. This renders the exploration and exploitation of different agents inherently entangled. This paper focuses on overcoming the difficulty of exploration in FMAB problems, and it proposes a novel federated upper confidence bound (UCB) algorithm that requires uncoordinated exploration (UE) decisions by the agents. The major distinction of this algorithm, referred to as FedUCB-UE, with the existing FMAB algorithms is that it allows the agents to explore the non-optimal arms and make personalized arm-selection decisions without coordination. While such uncoordinated exploration makes the regret analysis non-trivial, it comes with both the theoretical and empirical benefit of diversity in explorations. Under certain mild assumptions, this paper establishes that FedUCB-UE has a $\mathcal{O}(\log T)$ regret bound. Furthermore, experiments performed on synthetic datasets show that FedUCB-UE outperforms the state-of-the-art algorithms.

This paper investigates the problem of best arm identification (BAI) in stochastic multi-armed bandits in the fixed confidence setting. A novel formulation based on sequential hypothesis testing is provided, and an algorithm for BAI is proposed that, in spirit, follows the structure of the canonical sequential probability ratio test (SPRT). The algorithm has three features: (1) its sample complexity is asymptotically optimal, (2) it is guaranteed to be δ-PAC, and (3) it addresses the computational challenge of the state-of-the-art approaches. Specifically, the existing approaches rely on Thompson sampling for dynamically identifying the best arm and a challenger. This paper shows that identifying the challenger can be computationally expensive and demonstrates that the SPRT-based approach addresses that computational weakness.

This paper considers the problem of estimating unknown intervention targets in causal directed acyclic graphs from observational and interventional data in the presence of latent variables. The focus is on linear structural equation models with soft interventions. The existing approaches to this problem involve performing extensive conditional independence tests, and they estimate the unknown intervention targets alongside learning the structure of the causal model in its entirety. This joint learning approach results in algorithms that are not scalable as graph sizes grow. This paper proposes an approach that does not necessitate learning the entire causal model and focuses on learning only the intervention targets. The key idea of this approach is leveraging the property that interventions impose sparse changes in the precision matrix of a linear model. The proposed framework consists of a sequence of precision difference estimation steps. Furthermore, the necessary knowledge to refine an observational Markov equivalence class (MEC) to an interventional MEC is inferred. Simulation results are provided to illustrate the scalability of the proposed algorithm and compare it with those of the existing approaches.

Consider$n$random variables forming a Markov random field (MRF). The true model of the MRF is unknown, and it is assumed to belong to a binary set. The objective is to sequentially sample the random variables (one-at-a-time) such that the true MRF model can be detected with the fewest number of samples, while in parallel, the decision reliability is controlled. The core element of an optimal decision process is a rule for selecting and sampling the random variables over time. Such a process, at every time instant and adaptively to the collected data, selects the random variable that is expected to be most informative about the model, rendering an overall minimized number of samples required for reaching a reliable decision. The existing studies on detecting MRF structures generally sample the entire network at the same time and focus on designing optimal detection rules without regard to the data-acquisition process. This paper characterizes the sampling process for general MRFs, which is shown to be optimal in the asymptote of large$n$. The critical insight in designing the sampling process is devising an information measure that captures the decisions’ inherent statistical dependence over time. Furthermore, when the MRFs can be modeled by acyclic probabilistic graphical models, the sampling rule is shown to take a computationally simple form. Performance analysis for the general case is provided, and the results are interpreted in several special cases: Gaussian MRFs, non-asymptotic regimes, Chernoff’s rule for controlled (active) sensing, and the problem of cluster detection.

Probabilistic graphical models (PGMs) are effective for capturing the statistical dependencies in stochastic databases. In many domains (e.g., working with multimodal data), one faces multiple information layers that can be modeled by structurally similar PGMs. While learning the structures of PGMs in isolation is well-investigated, the algorithmic design and performance limits of learning from multiple coupled PGMs are investigated far less. This paper considers learning the structural similarities shared by a pair of Ising PGMs. The objective is learning the shared structure with no regard for the structures exclusive to either of the graphs, and significantly different from the existing approaches that focus on entire structure of the graphs. We propose an algorithm for the shared structure learning objective, evaluate its performance empirically, and compare with existing approaches on structure learning of single graphs.

The paper considers the problem of estimating a covariate parameter shared by multiple statistical models. Under the objective of estimating the parameter with target reliability with the fewest number of samples from these models, a fundamental question is how to glean samples from the statistical models. This question is especially important when the models are not equally descriptive or informative about the parameter, each being the most informative only for a specific regime of the parameter. This paper provides 1) an active sampling framework that specifies how the samples should be collected from different models over time in a data-adaptive fashion; 2) a stopping criterion specifying when the collected data is informative enough to form a reliable estimate for the covariate parameter; and 3) a terminal estimation rule. These rules, collectively, are shown to admit certain optimality guarantees. Numerical evaluations are provided to compare the performance with relevant existing approaches.

The problem of sequentially detecting a change in the correlation structure of multiple Gaussian information sources is considered when it is possible to sample only two of them at each time instance. It is assumed that all sources are initially independent and that at least two of them become positively correlated after the change. The problem is to stop sampling as quickly as possible after the change, while controlling the false alarm rate and without assuming any prior information on the number of sources that become correlated. A joint sampling and change-detection rule is proposed and is shown to achieve the smallest possible worst-case conditional expected detection delay among all processes that satisfy the same constraints, to a first order approximation as the false alarm rate goes to 0, for any possible number of post-change correlated sources.

In statistical inference, the information-theoretic performance limits can be often expressed in terms of a notion of divergence between the underlying statistical models (e.g., in binary hypothesis testing, the total error probability is related to the total variation between the models). As the data dimension grows, computing the statistics involved in decision-making and the attendant performance limits (divergence measures) face complexity and stability challenges. Dimensionality reduction addresses these challenges at the expense of compromising the performance (divergence reduces due to the data processing inequality for divergence). This paper considers linear dimensionality reduction such that the divergence between the models is maximally preserved. Specifically, this paper focuses on the Gaussian models and characterizes an optimal projection of the data onto a lower dimensional subspace with respect to four$f$-divergence measures (Kullback-Leibler,$\chi^{2}$, Hellinger, and total variation). There are two key observations. First, projections are not necessarily along the largest modes of the covariance matrix of the data, and even in some situations can be along the smallest modes. Secondly, under specific regimes, the optimal design of subspace projection is identical under all the$f$-divergence measures considered, rendering a degree of universality to the design, independently of the inference problem of interest.

Consider a sequence of$n$random variables$\mathrm{X}\ {\buildrel \triangle\over=} (X_{1},\cdots, X_{n})$forming a random field (RF). X is assumed to be generated according to one of the two possible classes of probability measures$\mathcal{P}\ {\buildrel \triangle\over=}\ \{\mathbb{P}_{i}: i\in\{1,\cdots, m\}\}$and$\mathcal{Q}\ {\buildrel \triangle\over=}\ \{\mathbb{Q}_{i}: i\in\{1, \cdots, m\}\}$. Up to$s$realizations of each random variable$X_{i}$are available for sampling. This paper addresses the following two questions. 1) Given a target classification reliability, what is the minimum number of samples, on average, required to classify X? 2) What is an optimal sequence of sampling the random variables such that a classification decision can be formed with the fewest number of samples? This paper addresses these questions in the asymptote of large$n$.

This paper considers the problem of estimating the unknown intervention targets in a causal directed acyclic graph from observational and interventional data. The focus is on soft interventions in linear structural equation models (SEMs). Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets even for linear SEMs. This severely limits their scalability and sample complexity. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The pivotal idea is to estimate the intervention sites from the difference between the precision matrices associated with the observational and interventional datasets. It involves repeatedly estimating such sites in different subsets of variables. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class. Consistency, Markov equivalency, and sample complexity are established analytically. Finally, simulation results on both real and synthetic data demonstrate the gains of the proposed approach for scalable causal structure recovery. Implementation of the algorithm and the code to reproduce the simulation results are available at \url{https://github.com/bvarici/intervention-estimation}.

Effective interference management in the multiuser interference channel strongly hinges on the channel state information's availability at the transmitters (CSIT). In a broad range of emerging large-scale and distributed networks (e.g., the Internet of Things), acquiring the CSIT is prohibitive due to the extensive information exchange that it imposes. As a result, the interference management approaches that rely on the CSIT lose their effectiveness in such circumstances. This article focuses on the two-user interference channel and proposes a broadcast approach to interference management. Its hallmark is that the transmitters, unlike the receivers, are entirely oblivious to instantaneous channel states. Each transmitter splits its message into multiple superimposed encoded information layers, where each layer is adapted to a given possible state for the combined states of all channels. Depending on the relative gain between the direct and interfering channels, each receiver opportunistically decodes a subset of both transmitters' received layers. An average achievable rate region is delineated, serving as an inner bound on the Gaussian interference channel's average capacity region in the absence of CSIT. Finally, an upper bound on the gap between the achievable sum-rate and the sum-rate capacity is established.

This paper considers the problem of recovering the edge structures of two partially identical graphs in the class of Ising models. It is assumed that both graphs have the same number of nodes and a known subset of nodes have identical structures in both graphs. Therefore, inferring the structure of one graph can provide the side information that could be leveraged for inference related to the other graph. The objective is to recover the connectivity of both graphs under an approximate recovery criterion. The degree- and edge-bounded subclass of Ising models is considered and necessary conditions (information-theoretic) and sufficient conditions for the sample complexity to achieve a bounded probability of error are established. Furthermore, the scaling behavior of the sample complexity is analyzed in different regimes and specific regimes are identified for which the necessary and sufficient conditions coincide, thus, establishing the optimal sample complexity.

Effective interference management in the multiuser interference channel strongly hinges on the availability of the channel state information at the transmitters (CSIT). In a broad range of emerging large-scale and distributed networks (e.g., the Internet of Things), however, acquiring the CSIT is prohibitive, due to the extensive information exchange that it imposes. In such circumstances, as a result, the interference management approaches that rely on the CSIT lose their effectiveness. This paper focuses on the two-user interference channel, and proposes a broadcast approach to interference management. Its hallmark is that the transmitters, unlike the receivers, are completely oblivious to instantaneous channel states. Each transmitter splits its message into multiple superimposed encoded information layers, where each layer is adapted to a given possible state for the combined states of all channels. Depending on the relative strengths of the direct and interfering channels, each receiver opportunistically decodes a subset of the received layers from both transmitters. An average achievable rate region is delineated serving as an inner bound on the average capacity region of the Gaussian interference channel in the absence of CSIT. Finally, it characterizes the gap between the achievable average sum-rate and the sum-rate capacity with the full CSIT in the asymptote of high signal-to-noise ratio. Numerical evaluations show that the cost of lacking CSIT is often insignificant.

This paper considers the problem of jointly recovering the structures of two graphical models with unknown edge structures. It is assumed that both graphs have the same number of nodes and a known subset of nodes have identical structures in both graphs. The classes of Ising models and Gaussian models are considered. For Ising models, the objective is to recover the connectivity of both graphs under an approximate recovery criterion. For Gaussian models, the objectives of edge structure recovery and inverse covariance estimation are considered. Information-theoretic bounds on the sample complexity for bounded probability of error under the aforementioned criteria are established and compared with the corresponding bounds on the sample complexity for recovering the graphs independently.

This paper considers a sequence of random variables that undergo periods of transient changes at an unknown set of time instants, referred to as transient change-points. The objective is to constantly monitor the sequence in order to detect one of the change-points subject to a hard constraint on the detection delay, while in parallel, the rate of false alarms is controlled. This setting is fundamentally different from the conventional change-point detection problems, in which there exists at most one change-point that can be either persistent or transient. In this paper, the exact optimal decision rules are characterized. Furthermore, it is shown that in the special case that the objective is detecting a transient change-point at exactly the instant that a change occurs (i.e., no detection delay), the test reduces to the well-known Shewhart test. Numerical evaluations are also provided to assess the performance of the decision rules.

This paper considers the problem of estimating the structures of a pair of structurally similar graphs associated with two distinct Ising models. It is assumed that the graphs have the same number of nodes with unknown structures, with the additional side information that a known subset of nodes have identical structures (connectivity) in both graphs. The objective is the exact recovery of the structures of both graphs. The bounded degree and bounded edge sub-classes of Ising models are investigated, and necessary and sufficient conditions on the sample complexity for bounded probability of error under the two criteria are established. Furthermore, the results are compared with the conditions on the sample complexity of recovering the graphs independently. One major observation is that by judicially leveraging the information about the identical sub-graphs by jointly recovering both structures, the sample complexity reduces by a factor cp2, where p is the number of nodes in the graph and c is some constant.

This paper considers the problem of secure parameter estimation when the estimation algorithm is prone to causative attacks. Causative attacks, in principle, target decision-making algorithms (e.g., inference and learning algorithms) to alter their decisions by making them oblivious to specific attacks. Such attacks influence inference algorithms by tampering with the mechanism through which the algorithm is provided with the statistical model of the population about which an inferential decision is made. Causative attacks are viable, for instance, by contaminating the historical or training data, or by compromising an expert who provides the model. In the presence of causative attacks, the inference algorithms operate under a distorted statistical model for the population from which they collect data samples. This paper introduces specific notions of secure estimation and provides a framework under which secure estimation under causative attacks can be formulated. Closed-form decision rules, and the fundamental tradeoffs between security guarantee and decision qualities are characterized. To circumvent the computational complexity associated with growing parameter dimension or attack complexity, a scalable estimation algorithm and its attendant optimality guarantees are provided.

Graphical models encode the stochastic dependencies among random variables (RVs). The vertices represent the RVs, and the edges signify the conditional dependencies among the RVs. Structure learning is the process of inferring the edges by observing realizations of the RVs, and it has applications in a wide range of technological, social, and biological networks. Learning the structure of graphs when the vertices are treated in isolation from inferential information known about them is well-investigated. In a wide range of domains, however, often there exist additional inferred knowledge about the structure, which can serve as valuable side information. For instance, the gene networks that represent different subtypes of the same cancer share similar edges across all subtypes and also have exclusive edges corresponding to each subtype, rendering partially similar graphical models for gene expression in different cancer subtypes. Hence, an inferential decision regarding a gene network can serve as side information for inferring other related gene networks. When such side information is leveraged judiciously, it can translate to significant improvement in structure learning. Leveraging such side information can be abstracted as inferring structures of distinct graphical models that are {\sl partially} similar. This paper focuses on Ising graphical models, and considers the problem of simultaneously learning the structures of two {\sl partially} similar graphs, where any inference about the structure of one graph offers side information for the other graph. The bounded edge subclass of Ising models is considered, and necessary conditions (information-theoretic ), as well as sufficient conditions (algorithmic) for the sample complexity for achieving a bounded probability of error, are established. Furthermore, specific regimes are identified in which the necessary and sufficient conditions coincide, rendering the optimal sample complexity.

This letter considers a network of sensors that collectively sense a number of unknown parameters. Each sensor can possibly sense only a subset of the parameters, gather data only about these parameters, and has access to only the statistical model of the data that it collects locally. The objective is that each sensor forms optimal estimates for its designated parameters (i.e., the parameters that it can sense). This letter proposes an estimation cost function that strikes a balance between the sensors being autonomous in forming local estimates based on their locally available data and statistical models, and enforcing consistency among the local estimates formed for the parameters that are sensed by multiple sensors. Exact optimal estimators are characterized, and it is shown that the optimal estimators can be implemented in a distributed way, through a single-shot exchange of local decisions. Specifically, the distributed implementation consists of forming local estimates and exchanging certain sufficient statistics values in a single round of communication exchange among some of the sensors. Furthermore, the optimal performance under the proposed cost function is also compared analytically with the performance of the widely used mean squared error estimator.

This paper proposes a broadcast strategy for the single-user slowly fading channel in which the transmission power is supplied by an energy harvesting unit. In this strategy, the channel state information (CSI) is known only to the receiver, and the transmitter is assumed to be oblivious to the CSI. The broadcast approach enables preventing outage events in the face of the lack of CSI at the transmitter. In the proposed broadcast approach, the transmitter splits its message into multiple superimposed information layers. This facilitates sustaining reliably decodable transmission rates adapted to the unknown state of the randomly-varying fading state of the channel. The objective is to characterize the optimal allocation of the randomly varying harvested power over time and across information layers in the contexts of maximizing the average communication rate and minimizing the likelihood of outage. First, the setting in which the transmitter has non-causal and complete information about the state of the energy harvesting process is considered. A closed-form characterization of the optimal allocation of power across layers is established, and an algorithm that analytically determines the exact optimal allocation of power over time is provided. Furthermore, an online algorithm is proposed for a setting in which the energy harvesting process is known only causally to the transmitter.

A two-user multiple access channel is considered, in which the channels undergo slow block fading and the state of each channel is known only to its corresponding transmitter. This paper proposes a novel broadcast strategy for multiple access communication in this channel. In the broadcast approach, in principle, a transmitter with CSI uncertainty sends multiple independent superimposed information layers where the rate of each layer is adapted to a specific channel realization. In the existing broadcast approaches to multiuser communication, the transmitters often directly adopt a single-user strategy and each transmitter adapts its transmission to one unknown channel. The novel aspect of the proposed strategy is that it adapts the designed codebooks to the state of the entire network. This is motivated by the fact that the contribution of each user to the network-wide measures (e.g., capacity region) depends not only on the user’s direct channel to the receiver, but also on the qualities of other channels. Average achievable rate region and outer bounds on the capacity region are characterized. Furthermore, the expected capacity region is investigated, where most part of the capacity region boundary is characterized. Finally, an asymptotic capacity region is also characterized.

A new broadcast strategy is designed for multiple access communication with partial channel state information at the transmitters. Specifically, a two-user multiple access channel is considered, in which the state of each channel is known only to its corresponding transmitter. In broadcast approaches, in principle, the transmitter sends multiple independent superimposed information layers, where the rate of each layer is adapted to a specific channel realization. The novel aspect of the proposed strategy is that it adapts the designed codebooks to the state of the whole network, which in contrast to the existing ones in which each transmitter adapts its transmission strategy only to the state of its direct channel to the receiver. Noting that the contribution of each user to a network-wide measure (e.g., capacity region) depends not only on the user's direct channel to the receiver, but also on the qualities of other channels, in the proposed strategy the transmitters adapt their transmissions to the combined states resulting from all users' channels. This leads to a larger achievable rate region, which is characterized and compared to two outer bounds. Furthermore, the proposed strategy is proved to achieve the sum-rate capacity asymptotically.

This paper considers the problem of distributed state estimation in an interconnected network, in which there is uncertainty in the true model. Such uncertainties are due to the possibility of disruptions or changes in the nominal model. The focus is on the setting in which the true network model belongs to a set of possible models. Forming an optimal estimate has high computational complexity in large networks and, therefore, this paper treats this problem in a distributed framework. The key observation is that the estimation quality critically depends on successful isolation of the true model. On the other hand, the true model cannot be determined perfectly due to noisy measurements. Based on these observations, this paper formulates a composite hypotheses testing problem and provides optimal decision rules that account for estimation quality and detection performance. The theory developed in this paper is evaluated via a case study.

Multi-hypothesis testing, which is widely used in many domains for discerning the true model governing the data, is often studied in a fixed sample-size setting. In such settings, the data-acquisition and decision-making processes are decoupled and the data-acquisition policies are pre-specified. Motivated by the advantages of sequential sampling, this paper treats the inherently coupled problems of data-acquisition and decision-making for multi-hypothesis testing, where data-acquisition can be abstracted as selecting one possible sensing action from a finite set. It aims to devise the quickest detection strategy by characterizing the minimum number of samples required to make a reliable decision as well as designing the dynamic attendant decision rules for selecting the best actions. The setting in which the available control actions are co-dependent is considered, which is a major distinction from the existing literature. Specifically, the existing data-adaptive approaches lose their optimality guarantees for this problem as they fail to account for such dependence. A novel sampling strategy that incorporates the dependence of the control actions into its decision rules is proposed, and its optimality properties are established.

A broadcast strategy for multiple access communication over slowly fading channels is introduced, in which the channel state information is known to only the receiver. In this strategy, the transmitters split their information streams into multiple independent information streams, each adapted to a specific actual channel realization. The major distinction between the proposed strategy and the existing ones is that in the existing approaches, each transmitter adapts its transmission strategy only to the fading process of its direct channel to the receiver, hence, directly adopting a single-user strategy previously designed for the single-user channels. However, the contribution of each user to a network-wide measure (e.g., sum-rate capacity) depends not only on the user's direct channel to the receiver, but also on the qualities of other channels. Driven by this premise, this paper proposes an alternative broadcast strategy in which the transmitters adapt their transmissions to the combined states resulting from all users' channels. This leads to generating a larger number of information streams by each transmitter and adopting a different decoding strategy by the receiver. An achievable rate region and an outer bound that capture the tradeoff among the rates of different information layers are established, and it is shown that the achievable rate region subsumes the existing known capacity regions obtained based on adapting the broadcast approach to the single-user channels.

This paper treats the problem of optimal resource allocation over time in a finite-horizon setting, in which the resource become available only sequentially and in incremental values, and the utility function is concave and can freely vary over time. Such resource allocation problems have direct applications in data communication networks (e.g., energy harvesting systems). This problem is studied extensively for special choices of the concave utility function (time invariant and logarithmic) in which case the optimal resource allocation policies are well-understood. This paper treats this problem in its general form and analytically characterizes the structure of the optimal resource allocation policy and devises an algorithm for computing the exact solutions analytically. An observation instrumental to devising the provided algorithm is that there exist time instances at which the available resources are exhausted, with no carryover to future. This algorithm identifies all such instances, which in turn, facilitates breaking the original problem into multiple problems with significantly reduced dimensions. Furthermore, some widely used special cases in which the algorithm takes simpler structures are characterized, and the application to the energy harvesting systems is discussed. Numerical evaluations are provided to assess the key properties of the optimal resource allocation structure and to compare the performance with the generic convex optimization algorithms.

This paper considers a network of agents generating correlated data according to a known kernel. The correlation structure might undergo a change at an unknown time instant, where the post-change kernel is not fully known. Moreover, due to the data processing and communication costs, only a subset of agents can be observed at any time instant. The objective is to detect the change-point with minimum average delay, while the rate of false alarms is controlled. This paper proposes a coupled data acquisition and decision-making process for change detection and establishes its optimality properties.

Consider a set of random sequences, each consisting of independent and identically distributed random variables. Each sequence is generated according to one of the two possible distributions F0or F1with unknown prior probabilities (1 - ϵ) and ϵ, respectively. The objective is to design a sequential decision-making procedure that identifies a sequence generated according to F1with the fewest number of measurements. Earlier analyses of this search problem have demonstrated that the optimal design of the sequential rules strongly hinge on the exact value of ϵ. Such information, however, might not be available in certain applications, especially in anomaly detection where the anomalous sequences occur with unpredicted patterns. Motivated by this premise, this paper designs a sequential inference mechanism that forms two coupled decisions for identifying a sequence of interest, and also learning the value of ϵ. The paper devises three strategies that place different levels of emphasis on each of these inference goals.

A broadcast strategy for multiple access communication over slowly fading channels is introduced, in which the channel state information is known to only the receiver. In this strategy, the transmitters split their information streams into multiple independent information layers, each adapted to a specific actual channel realization. The major distinction between the proposed strategy and the existing ones is that in the existing approaches, each transmitter adapts its transmission strategy only to the fading process of its direct channel to the receiver, hence directly adopting a single-user strategy previously designed for the single-user channels. However, the contribution of each user to a network-wide measure (e.g., sum-rate capacity) depends not only on the user's direct channel to the receiver, but also on the qualities of other channels. Driven by this premise, this paper proposes an alternative broadcast strategy in which the transmitters adapt their transmissions to the combined states resulting from all users' channels. This leads to generating a larger number of information layers by each transmitter and adopting a different decoding strategy by the receiver. An achievable rate region that captures the trade-off among the rates of different information is established and is shown to subsume the existing known regions.

We investigate the physical layer security of synchronous multiple access transmissions using the Alamouti space-time block code in fading channels where multiple users communicate with a single intended receiver in the presence of an eavesdropper. We propose an artificial-noise-aided technique to secure the transmissions by having the Alamouti users collaborate with each other, without exchanging information, to degrade the eavesdropper's channel. Unlike previous work, which assumes that the transmitters have complete knowledge of the legitimate as well as the eavesdropper's channels, our proposed technique requires no communications between the users, minimal knowledge of the legitimate channel, and no channel knowledge regarding the eavesdropper.

We investigate the physical layer security of synchronous multiple access transmissions using the Alamouti space-time block code in fading channels where multiple users communicate with a single intended receiver in the presence of an eavesdropper. We propose an artificial-noise-aided technique to secure the transmissions by having the Alamouti users collaborate with each other, without exchanging information, to degrade the eavesdropper's channel. Unlike previous work, which assumes that the transmitters have complete knowledge of the legitimate as well as the eavesdropper's channels, our proposed technique requires no communications between the users, minimal knowledge of the legitimate channel, and no channel knowledge regarding the eavesdropper.

An ordered set of data sequences is given where, broadly, the data sequences are categorized into normal and abnormal ones. The normal sequences consist of random variables generated according to a known distribution, while there exist uncertainties about the distributions of the abnormal sequences. Moreover, the generations of different sequences are correlated, induced by an underlying physical coupling, where a sequence being normal or abnormal depends on the status of the rest of the sequences according to a known dependency kernel. The objective is to design the quickest sequential and data-adaptive sampling procedure for identifying one abnormal sequence. This quickest search strategy strikes a balance between the quality and agility of the search process, as two opposing figures of merit. This paper characterizes the sampling and search strategy. Motivated by the fact that full characterization of such strategies can become computationally prohibitive, this paper also proposes asymptotically optimal sampling and search strategies that are computationally efficient.

Detecting correlation structures in large networks arises in many domains. Such detection problems are often studied independently of the underlying data acquisition process, rendering settings in which data acquisition policies and the associated sample size are pre-specified. Motivated by the advantages of data-adaptive sampling in data dimensionality reduction, especially in large networks, as well as enhancing the agility of the sampling process, this paper treats the inherently problems of data acquisition and correlation detection. Specifically, this paper considers a network of nodes generating random variables and designs the quickest sequential sampling strategy for collecting data and reliably deciding whether the network is a Markov network with a known correlation structure. By abstracting the Markov network as an undirected graph, in which the vertices represent the random variables and their connectivities model the correlation structure of interest, designing the quickest sampling strategy becomes equivalent to sequentially and data-adaptively identifying and sampling a sequence of vertices in the graph. Optimal sampling strategies are proposed and their associated optimality guarantees are established. Performance evaluations are provided to demonstrate the gains of the proposed sequential approaches.

Effective interference management in the multiuser interference channel necessitates that the users form their transmission and interference management decisions in coordination, and adapt them to the state of the channel. Establishing such coordination, often facilitated through information exchange, is prohibitive in fast-varying channels, especially when the network size grows. This paper focuses on the multiuser Gaussian interference channel and offers a receiver-centric approach to interference management. In this approach, the transmitters deploy rate-splitting and superposition coding to generate their messages according to independent Gaussian codebooks. The receivers can freely decode any arbitrary set of interfering messages along with their designated messages in any desired joint or ordered fashion, and treat the rest of the interferers as Gaussian noise. The proposed receiver-centric interference management approach is applied to two class of problems (outage optimization and fairness-constrained rate allocation), and constructive proofs are provided to establish the following properties for the proposed approach: 1) the optimal set of codebooks to be decoded by each receiver is a local decision made by each receiver based on its local channel state information (CSI); 2) the globally optimal transmission rates are related to locally optimal rates computed by the receivers based on their local information, which implies that the transmitters do not require explicit knowledge of the CSI and can determine their rates via limited feedback from the receivers; and 3) obtaining the optimal interference management strategy at each receiver has controlled complexity.

Consider a set of random sequences, each consisting of independent and identically distributed random variables drawn from one of the two known distributions$F_{0}$and$F_{1}$. The underlying distributions of different sequences are correlated, induced by an inherent physical coupling in the mechanisms generating these sequences. The objective is to design the quickest data-adaptive and sequential search procedure for identifying one sequence generated according to$F_{1}$. The optimal design involves striking a balance between the average delay in reaching a decision and the rate of false alarms, as two opposing figures of merit. Optimal and asymptotically optimal decision rules are derived, which can take radically different forms depending on the correlation structure. Performance and sampling complexity analyses are provided to delineate the tradeoff between decision delay and quality. The generalization to parallel sampling, in which multiple sequences are sampled at the same time, is also investigated.

In future smart grids, energy storage systems (ESSs) are expected to play a key role in reducing peak hour electricity generation cost and the associated level of carbon emissions. Considering their high acquisition, operation, and maintenance costs, ESSs are likely to serve a large number of users. Hence, optimal sizing of energy ESSs plays a critical role as over-provisioning ESS size leads to under-utilizing costly assets and under-provisioning it taxes operation lifetime. This paper proposes a stochastic framework for analyzing the optimal size of energy storage systems. In this framework the demand of each customer is modeled stochastically and the aggregate demand is accommodated by a combination of power drawn from the grid and the storage unit when the demand exceeds grid capacity. In this framework an analytical method is developed, which provides tractable solution to the ESS sizing problem of interest. The results indicate that significant savings in terms of ESS size can be achieved.

Quickest spectrum sensing seeks to optimize a balance between two opposing performance measures in spectrum sensing, one being the delay in identifying spectrum opportunities, and the other being the quality of the decision. The existing spectrum sensing approaches formed based on quickest detection theory rely on the assumption that the occupancy states of different spectrum bands over a wideband spectrum are statistically independent. This is an assumption that cannot be met in practice, especially in broadband communication schemes in which radio channels are dynamically grouped in bundles and allocated to different users based on the users' traffic needs. As a result of such channel grouping and allocation the occupancy states of the channels, especially the adjacent ones, are correlated. This paper, in contrast to the existing literature on quickest spectrum sensing, considers a wideband spectrum in which the occupancy states of different channels follow a pre-specified dependency kernel. The objective is to design the quickest spectrum sensing approach for identifying spectrum holes, which aims to minimize the average delay in identifying spectrum opportunities while assuring, in parallel, certain guarantees on the quality of the decision. The closed-form expression of the optimal sensing scheme are delineated and are shown to have low computational complexity.

Linear search arises in many application domains. The problem of linear search over multiple sequences in order to identify one sequence with a desired statistical feature is considered. The quickest linear search optimizes a balance between two opposing performance measures, one being the delay in detecting a desirable sequence, and the other one being the quality of the decision. The existing approaches in the quickest search literature rely on the assumption that the sequences are statistically independent. In many applications, however, due to the underlying physical couplings, generations of available sequences are not necessarily independent. Driven by such underlying couplings, this paper considers searching over correlated sequences, in which the distribution of each sequence depends on the distribution of its preceding one. The closed-form characterization of the sampling process for the optimal search is delineated. The analysis reveals that depending on the correlation structure, the optimal search strategy can be similar to (in spirit) or dramatically different from the optimal search strategy over independent sequences.

This paper focuses on the two-user relay-assisted X channel with no channel state information (CSI) available at the transmitter side. Two relaying modes, namely half-duplex decode-and-forward (DF) and cognitive relays, are considered and the degrees of freedom (DoF) are characterized. It is shown that assisted by a half-duplex DF relay that is equipped with 2M antennas, the X channel with two M-antenna users has 4M/3 DoF, which is achievable through interference alignment (IA). Furthermore, it is shown that in this channel, an M-antenna cognitive relay (with non-causal access to information streams) provides 2M DoF using interference cancellation (IC) technique. In this setting, IC outperforms interference alignment in the cognitive relay mode, since the latter achieves 4M/3 DoF.

Special issue on recent advances in network and information security - security and communication networks journal

Quickest spectrum sensing seeks to optimize a balance between two opposing performance measures, one being the delay in identifying spectrum opportunities, and the other being the quality of the decision. The existing spectrum sensing approaches formed based on quickest detection theory rely on the assumption that the occupancy states of different spectrum bands over a wideband spectrum are statistically independent. This is an assumption that cannot be met in practice, especially in broadband communication schemes in which radio channels are dynamically grouped in bundles and allocated to different users based on the users' traffic needs. As a result of such channel grouping and allocation, the occupancy states of the channels, especially the adjacent ones, are correlated. This paper, in contrast to the existing literature on quickest spectrum sensing, considers a wideband spectrum in which the occupancy states of different channels follow a pre-specified dependency kernel. The objective is to design the quickest spectrum sensing approach for identifying spectrum holes, which aims to minimize the average delay in identifying spectrum opportunities while assuring, in parallel, certain guarantees on the quality of the decision. The closed-form characterization of the optimal sensing scheme is delineated and it is shown that this optimal scheme has low computational complexity.

This paper considers multiuser interference channels in which the transmitters have imperfect channel state information (CSI) where CSI perturbations are modeled stochastically. Transmitters are assumed to be equipped with multiple antennas serving single-antenna receivers. Transmitters use pre-designed discrete codebooks for beamforming directions and dynamically (based on the available CSI) select the best set of beamformers from the given codebook. The objective is to perform optimal power allocation to different users while certain quality of service (QoS) guarantees are ensured for the users. Imposed by stochastic CSI uncertainties, guarantees provided for the QoS measures have a stochastic nature too. The primary focus is placed on the interference channels for which two power allocation problems are considered. The first problem minimizes power consumption subject to serving users at certain data rates and the second problem considers max-min rate allocation subject to given power budgets for the transmitters. The core step in formalizing these problems in mathematically tractable forms relies on using Bernstein approximation, which approximates and convexifies the non-convex stochastic guarantees by conservative convex and deterministic counterparts. For solving this resulting convex and deterministic optimization problem, a specialized version of the long-step logarithmic barrier cutting plane (LLBCP) algorithm is used. Effectiveness of the proposed solutions and comparisons with other existing methods are assessed via extensive simulation results.

This paper considers spectrum access in wideband channels and its objective is to design an agile and reliable mechanism for identifying spectrum opportunities. Driven by the need for reducing the time required for identifying spectrum opportunities, the idea of data-adaptive and sequential block sampling is proposed, through which instead of examining each channel individually, a cognitive user takes samples that are linear combinations of simultaneous measurements from multiple channels. If such coarse samples indicate that the block of channels contains at least a vacant (unused) channel, then the channels are examined individually in order to accumulate more information about their spectral occupancy states, and otherwise, the entire block is discarded and the process resumes sequentially by examining the next block of channels.

Rare events can potentially occur in many applications. When manifested as opportunities to be exploited, risks to be ameliorated, or certain features to be extracted, such events become of paramount significance. Due to their sporadic nature, the information-bearing signals associated with rare events often lie in a large set of irrelevant signals and are not easily accessible. This paper provides a statistical framework for detecting such events so that an optimal balance between detection reliability and agility, as two opposing performance measures, is established. The core component of this framework is a sampling procedure that adaptively and quickly focuses the information-gathering resources on the segments of the dataset that bear the information pertinent to the rare events. Particular focus is placed on Gaussian signals with the aim of detecting signals with rare mean and variance values.

This paper proposes group decoding and analyzes the associated rate allocation schemes for the relay interference channel where multiple relays assist the transmissions from the sources to destinations. All the relays and destinations employ an advanced decoding strategy called constrained group decoding, where the desired messages are decoded jointly with some interferers' messages when doing so is beneficial. This paper considers two types of relay systems, the hopping relay system with no direct source-destination links, and the inband relay system with direct source-destination links. For each relay type, the objective is to design the relay assignment and the group decoding strategies at the relays and destinations, in order to maximize the minimum information rate among all source-destination pairs. For hopping relays with pre-specified relay assignments, we provide the optimal distributed algorithm for solving the above max-min rate allocation problem. Moreover, for hopping relays with dynamic relay assignments, and for inband relays, the problem becomes intractable and we offer heuristic schemes that perform close to the optimum solutions. Numerical results demonstrate the significant performance improvement provided by the proposed group decoder over the traditional systems that employ the linear minimum mean-square error (MMSE) decoders at both the relays and the destinations, where all interference is treated as noise, as well as the effectiveness of the proposed dynamic relay assignment strategies.

We solve the problem of designing an affordable optimal transmission strategy for the recently proposed system of energy-harvesting active networked tags (EnHANTs), that is adapted to the identification request and the energy harvesting dynamic. We assume that the system operates in a time-slotted fashion, so that the problem is formulated as a Markov decision process (MDP). Both a static exhaustive search method and a modified policy iteration algorithm are employed to obtain the optimal transmission policy. Simulation results are provided to demonstrate that the obtained transmission policy can considerably improve the overall system performance which takes into consideration of both the system activity-time and the communication reliability.

We consider a well-defined joint detection and parameter estimation problem. By combining the Bayesian formulation of the estimation subproblem with suitable constraints on the detection subproblem, we develop optimum one- and two-step test for the joint detection/estimation setup. The proposed combined strategies have the very desirable characteristic to allow for the trade-off between detection power and estimation quality. Our theoretical developments are, then, applied to the problems of retrospective changepoint detection and multiple-input multiple-output (MIMO) radar. In the former case, we are interested in detecting a change in the statistics of a set of available data and provide an estimate for the time of change, while in the latter in detecting a target and estimating its location. Intense simulations in the MIMO radar example demonstrate that by using jointly optimum schemes, we can experience significant improvement in estimation quality, as compared to generalized the likelihood ratio test or the test that treats the two subproblems separately, with only small sacrifices in detection power.

Cognitive radios process their sensed information collectively in order to opportunistically identify and access underutilized spectrum segments (spectrum holes). Due to the transient and rapidly varying nature of the spectrum occupancy, the cognitive radios (secondary users) must be agile in identifying the spectrum holes in order to enhance their spectral efficiency. We propose a novel adaptive procedure to reinforce the agility of the secondary users for identifying multiple spectrum holes simultaneously over a wide spectrum band. This is accomplished by successively exploring the set of potential spectrum holes and progressively allocating the sensing resources to the most promising areas of the spectrum. Such exploration and resource allocation results in conservative spending of the sensing resources and translates into very agile spectrum monitoring. The proposed successive and adaptive sensing procedure is in contrast to the more conventional approaches that distribute the sampling resources equally over the entire spectrum. Besides improved agility, the adaptive procedure requires less-stringent constraints on the power of the primary users to guarantee that they remain distinguishable from the environment noise and renders more reliable spectrum hole detection.

This paper analyzes the gains of opportunistic communication in multiuser interference channels. Consider a fully connected n-user Gaussian interference channel. At each time instance, only K≤n transmitters are allowed to be communicating with their respective receivers and the remaining (n-K) transmitter-receiver pairs remain inactive. For finite n, if the transmitters can acquire the instantaneous channel realizations and if all channel gains are bounded away from zero and infinity, the seminal results on interference alignment establish that for any K arbitrary active pairs the total number of spatial degrees of freedom per orthogonal time and frequency domain is K/2. In dense networks (n → ∞), however, as the size of the network increases, it becomes less likely to sustain the bounding conditions on the channel gains. By exploiting this fact, we show that when n obeys certain scaling laws, by opportunistically and dynamically selecting the K active pairs at each time instance, the number of degrees of freedom can exceed K/2 and in fact can be made arbitrarily close to K. More specifically, for single-antenna transmitters and receivers, the network size scaling as n ∈ ω(SNRd⌈d-1⌉) when power allocation is allowed and scaling as n ∈ ω(SNRd(K-1)) without power allocation are sufficient conditions for achieving d ∈ [1, K] degrees of freedom. Moreover, for achieving these degrees of freedom the transmitters do not require the knowledge of the instantaneous channel realizations. Hence, invoking opportunistic communication in the context of interference channels leads to achieving higher degrees of freedom that are not achievable otherwise. We extend the results for multi-antenna Gaussian interference channels.

We propose novel coding and decoding methods for a fully connected K-user Gaussian interference channel via assigning multiple codebooks (layers) to each transmitter, such that at each receiver decoding interferers partially becomes feasible. Each receiver first identifies which interferers it should decode and which layers of them should be decoded, and then successively decodes a group of layers with a constraint on its group size treating the remaining layers as Gaussian noise. We provide a distributed algorithm that determines the transmission rate at each transmitter also finds the order of the layers to be successively decoded at each receiver. We also consider practical design of a system that employs the quadrature amplitude modulations (QAM) and rateless codes. Numerical results are provided on the achievable sum-rate under the ideal case of Gaussian signaling with random codes as well as on the system throughput under practical modulations and channel codes. The results show that the proposed multi-layer coding scheme with CPGD offers significant performance gain over the traditional un-layered transmission with single-user decoding.

In order to achieve the Han-Kobayashi rate region for the two-user interference channel each transmitter splits its message into two sub-messages, each drawn from an independent codebook. Generalizing this idea to the K-user interference channel implies that 2K-1codebooks should be allocated to each transmitter, where each of them carries the message that is public to one of the subsets of the K-1 non-designated receivers. While such a rate-splitting scheme yields the best known achievable rate region (with random coding), optimizing a rate-related utility function over this region presents certain challenges stemming from the computational complexities and the distributed nature of interference channels. This paper introduces the notion of partial group decoding which offers a practical rate optimization strategy over this achievable rate region and mitigates these challenges. The merits of partial group decoders are demonstrated through treating the problem of optimal rate allocation with fairness constraints.

The gains of opportunistic communication in multiuser interference channels is analyzed. Consider a network of fully connected n-user Gaussian interference channel that afford activating K ≤ n at-a-time. It is shown that when n obeys certain scaling laws, by opportunistically and dynamically selecting the K active pairs the number of degrees of freedom can exceed K/2 and, in fact, can be made arbitrarily close to K. More specifically the network size scaling as n ∈ ω (SNRd(K-1)) is a sufficient condition for achieving d ∈ [0, K] degrees of freedom.

We propose novel coding and decoding methods for a fully connected K-user Gaussian interference channel. Each transmitter encodes its information into multiple layers and transmits the superposition of those layers. Each receiver employs a constrained partial group decoder (CPGD) that decodes its designated message along with a part of the interference. In particular, each receiver performs a twofold task by first identifying which interferers it should decode and then determining which layers of them should be decoded. Determining the layers to be decoded and decoding them are carried out in a successive manner, where in each step a group of layers with a constraint on its group size is identified and jointly decoded while the remaining layers are treated as Gaussian noise. The decoded layers are then subtracted from the received signal and the same procedure is repeated for the remaining layers. We provide a distributed algorithm, tailored to the nature of the interference channels, that determines the transmission rate at each transmitter based on some optimality measure and also finds the order of the layers to be successively decoded at each receiver. We also consider practical design of a system that employs the quadrature amplitude modulations (QAM) and rateless codes. Numerical results are provided on the achievable sum-rate under the ideal case of Gaussian signaling with random codes as well as on the system throughput under practical modulations and channel codes. The results show that the proposed multi-layer coding scheme with CPGD offers significant performance gain over the traditional un-layered transmission with single-user decoding.

In frequency-selective channels linear receivers enjoy significantly-reduced complexity compared with maximum likelihood receivers at the cost of performance degradation which can be in the form of a loss of the inherent frequency diversity order or reduced coding gain. This paper demonstrates that the minimum mean-square error symbol-by-symbol linear equalizer incurs no diversity loss compared to the maximum likelihood receivers. In particular, for a channel with memory ν, it achieves the full diversity order of (ν+1) while the zero-forcing symbol-by-symbol linear equalizer always achieves a diversity order of one.

Vast segments of the frequency spectrum are licensed to specific users for particular applications. These legacy users, however, often under-utilize their designated spectrum segments. Unlicensed (secondary) users can benefit from this fact and opportunistically exploit the vacant spectrum segments (spectral holes). Due to the transient nature of the spectrum occupancy it becomes imperative for secondary users to quickly identify such spectral holes. To accomplish this, we propose a novel sequential and adaptive spectrum sensing procedure. The underlying notion of this procedure is to progressively allocate the sensing resources to only the most promising areas of the spectrum. This translates in a reduction of sensing resources and time needed to accurately identify spectrum holes, in contrast with more conventional approaches that allocate the sensing budget over the entire spectrum uniformly. The proposed method is theoretically sound and further supported by simulation results.

We consider the problem of designing robust linear transceivers for a memoryless narrowband Gaussian interference channel (GIC) where M multi-antenna sources communicate with their respective single-antenna receivers. The design of such linear transceivers heavily depends on the accuracy of the channel state information (CSI) available at the transmitters. In practice, the transmitters can acquire only imperfect or noisy CSI. We adopt a popular noisy CSI model which assumes that the noise terms (i.e., errors in the CSI) lie within known hyper-ellipsoids and design transceivers that optimize a worst-case quality of service measure. In particular, we focus on maximizing the worst-case weighted sum-rate as well as the worst-case minimum rate. For obtaining such transceiver designs, we exploit semidefinite programming methods and offer efficient centralized and distributed algorithms that entail different levels of information exchange among the transmitters.

For coordinated transmissions in multi-cell downlink channels, the base stations are required to acquire and share their channel state information (CSI). Acquiring CSI is often prone to errors and a globally-optimal coordination is not possible when the acquired CSI is imperfect. However, when the errors in the acquired CSI are guaranteed to lie within bounded regions, any quality-of-service (QoS) measure of interest will also lie within a bounded region. Motivated by this premise, by employing the notion of robustness in the worst-case sense, some worst-case guarantees on QoS can be offered. We assume that CSI perturbations belong to known hyper-spheres and aim to design linear transceivers that optimize the minimum worst-case rate of the network. We offer centralized (fully cooperative) and distributed (limited cooperation) procedures imposing different levels of complexity and information exchange among the base stations.

Achievable rate regions of multiuser fading interference channels depend on their fading realizations. Motivated by this premise we consider the problem of adapting the users' rates to fading variations. Channel-dependent rate adjustments are accomplished after each transition of the fading channel from one state to another. Such rate adjustments (increments or decrements) are constrained to meet some notion of fairness among the users and are designed to ensure that all users remain decodable. Here, we employ the notions of symmetric fair and max-min fair rate adaptations and offer algorithms for computing such fair rate adaptations. Besides fairness, the two other major features of these algorithms are that they are amenable to distributed implementation with limited information exchange among the users, and their complexities scale polynomially in the number of users.

Spectrum access is an important function of cognitive radios for detecting and utilizing spectrum holes without harming the legacy systems. In this paper, we propose novel cooperative communication models and show how deploying such cooperations between a pair of secondary transmitter and receiver assists them in identifying spectrum opportunities more reliably. These cooperations are facilitated by dynamically and opportunistically assigning one of the secondary users as a relay to assist the other one, which results in more efficient spectrum hole detection. Also, we investigate the impact of erroneous detection of spectrum holes and thereof missing communication opportunities on the capacity of the secondary channel. The capacity of the secondary users with interference-avoiding spectrum access is affected by 1) how effectively the availability of vacant spectrum is sensed by the secondary transmitter-receiver pair, and 2) how correlated are the perceptions of the secondary ransmitter-receiver pair about network spectral activity. We show that both factors are improved by using the proposed cooperative protocols. One of the proposed protocols requires explicit information exchange in the network. Such information exchange in practice is prone to wireless channel errors (i.e., is imperfect) and costs bandwidth loss. We analyze the effects of such imperfect information exchange on the capacity as well as the effect of bandwidth cost on the achievable throughput. The protocols are also extended to multiuser secondary networks.

Dynamic allocation of resources to the best link in large multiuser networks offers considerable improvement in spectral efficiency. This gain, often referred to as multiuser diversity gain, can be cast as double-logarithmic growth of the network throughput with the number of users. In this paper, we consider large cognitive networks granted concurrent spectrum access with license-holding users. The primary network affords to share its underutilized spectrum bands with the secondary users. We assess the optimal multiuser diversity gain in the cognitive networks by quantifying how the sum-rate throughput of the network scales with the number of secondary users. For this purpose, we look at the optimal pairing of spectrum bands and secondary users, which is supervised by a central entity fully aware of the instantaneous channel conditions, and show that the throughput of the cognitive network scales double-logarithmically with the number of secondary users$(N)$and linearly with the number of available spectrum bands$(M)$, i.e.,$M\log \log N$. We then propose a distributed spectrum allocation scheme, which does not necessitate a central controller or any information exchange among different secondary users and still obeys the optimal throughput scaling law. This scheme requires that some secondary transmitter–receiver pairs exchange$\log M$information bits among themselves. We also show that the aggregate amount of information exchange between secondary transmitter–receiver pairs is asymptotically equal to$M\log M$. Finally, we show that our distributed scheme guarantees fairness among the secondary users, meaning that they are equally likely to get access to an available spectrum band.

This paper analyzes the diversity gain achieved by single-carrier frequency-domain equalizers (SC-FDE) in frequency selective channels, and uncovers the interplay between diversity gain d, channel memory length ¿, transmission block length L, and the spectral efficiency R. We specifically show that for the class of minimum mean-square error (MMSE) SCFDE receivers, for rates R ¿ log L/¿ full diversity of d = ¿+ 1 is achievable, while for higher rates the diversity is given by d = [2-RL + 1. In other words, the achievable diversity gain depends not only on the channel memory length, but also on the desired spectral efficiency and the transmission block length. A similar analysis reveals that for zero forcing SC-FDE, the diversity order is always one irrespective of channel memory length and spectral efficiency. These results are supported by simulations.

We propose a novel cooperative communication protocol for multicasting a common message from one source to two destinations and based on that offer a spectrum access scheme for the cognitive radios that seek to utilizing the spectrum holes within the bands licensed to the legacy systems. The proposed cooperation model has two major traits; first, by opportunistically and dynamically assigning one of the destination nodes as relay for the other one, via a single-time relaying both destinations achieves a second order diversity gain. Secondly, it guarantees performance improvement over all SNR regimes, which is not the case in most cooperation protocols as diversity gain is a high SNR measure and yielding higher diversity orders ensures improvement only over high enough SNRs. Next, we consider cognitive users, to whom the codebook of the primary users is known as side information, and offer a beacon-assisted mechanism for spectrum access. We assume that a primary user multicasts a beacon message upon releasing a spectrum band and adopt the proposed cooperation model to strengthen a cognitive transmitter-receiver pair in decoding the beacon message. Finally, we quantify the effect of such cooperation on the capacity of the channel between the cognitive transmitter-receiver pair, as a meaningful measure to assess how the proposed cooperation model assists the secondary users in exploiting communication opportunities.

We consider decentralized multi-antenna cognitive radio networks where secondary (cognitive) users are granted simultaneous spectrum access along with license-holding (primary) users. We investigate the problem of designing beam- formers for the secondary users by maximizing the minimum rate, subject to a limited sum-power budget and constraints on the interference level imposed on each primary receiver. We consider two scenarios: the first one allows only single-user decoding at each secondary receiver whereas in the second case each secondary receiver is allowed to employ advanced multiuser decoding and is free to decode any subset of secondary users. We provide an optimal distributed algorithm for the first scenario and an explicit formulation of the optimization problem corresponding to the second scenario. This problem however is non-convex and hence cannot be efficiently solved even in a centralized setup. As a remedy, we suggest a two-step approach. In particular, the beamformers are first designed assuming single user decoding at each secondary receiver. An optimal distributed low-complexity algorithm is then proposed to allocate excess rates to the secondary users, which are made possible due to the use of advanced decoders at the secondary receivers. Simulation results demonstrate the gains yielded by the optimal beamformers as well as the rate allocation algorithms.

In this paper we investigate the diversity order of single-carrier frequency domain equalizers (SC-FDE). Specifically, we look at minimum mean square error (MMSE) linear equalizers utilizing block-transmission and cyclic prefix. It is shown that the diversity order in these systems depends on data transmission rate, channel memory length, as well as transmission block length. Analyses reveal that with memory length v and transmission block length L, for the rates Rleslog L/v full diversity of v+1 is achievable. For higher rates the achievable diversity order is degraded and is equal to [2-RL]+1. Therefore MMSE SC-FDE has a diversity that varies between 1 and v+1, and achieves full diversity only for a limited range of data rates.

Opportunistic cooperation is a technique where in each transmission the best relay (or k best relays) are chosen to assist. In a multiuser cooperative network, coordinating the cooperating users requires exchange of channel information between various nodes. As the number of nodes increases, this information exchange can get out of hand. In this work, we propose an opportunistic cooperation technique where at most two bits of information per relay are exchanged for each cooperation period (one bit feedback and one bit feedforward). Our method does not need any carrier sensing technique or any information regarding source-relay channels for its operation. We show that this frugal technique is capable of achieving the same diversity-multiplexing tradeoff (DMT) achieved by distributed space-time-coded cooperation protocols (DSTC) in Laneman and Wornell (2003). Also we show how bandwidth allocation between a user and its partner affects the diversity-multiplexing tradeoff.

This paper investigates the diversity order of single-carrier, symbol-by-symbol linear equalization (LE). It is shown that minimum mean square error (MMSE) linear equalizers achieve full diversity of v + 1 (the number of channel taps) independent of spectral efficiency. Our results also provide a new proof for the full diversity of decision feedback equalization (DFE), which was shown originally in A. Medles and D.T.M Slock (2004).

This paper introduces broadcasting relay nodes for orthogonal multiuser channels. The underlying idea is that a single relay node is shared by multiple source-destination pairs. In this scheme, the relay node receives the messages of multiple independent sources, and broadcasts a single superimposed signal to multiple destinations. Compared to dedicated relay scenarios, large gains in capacity region and outage capacity is possible with the shared relay scenario. We consider the special case of two pairs, and examine discrete memoryless channels and Gaussian channels assuming degradedness for the relay channels and physically degradedness for the broadcast channel. Upper bounds on capacity are obtained and shown to be achievable. The analysis is also extended to Rayleigh fading channels, where outage regions are investigated.