We study a matrix completion problem which leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that users are categorized into clusters, each of which comprises sub-clusters (or what we call “groups”). We consider a hierarchical stochastic block model that well respects practically-relevant social graphs and follows a low-rank rating matrix model. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. One important consequence of this result is that leveraging the hierarchical structure of similarity graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. Another implication of the result is when the graph information is rich, the optimal sample complexity is proportional to the number of clusters, while it nearly stays constant as the number of groups in a cluster increases. We empirically demonstrate through extensive experiments that the proposed algorithm achieves the optimal sample complexity.

We explore a fairness-related challenge that arises in generative models. The challenge is that biased training data with imbalanced demographics may yield a high asymmetry in size of generated samples across distinct groups. We focus on practically-relevant scenarios wherein demographic labels are not available and therefore the design of a fair generative model is non-straightforward. In this paper, we propose an optimization framework that regulates the unfairness under such practical settings via one statistical measure, LeCam (LC)-divergence. Specifically to quantify the degree of unfairness, we employ a balanced-yet-small reference dataset and then measure its distance with generated samples using the LC-divergence, which is shown to be particularly instrumental to a small size of the reference dataset. We take a variational optimization approach to implement the LC-based measure. Experiments on benchmark real datasets demonstrate that the proposed framework can significantly improve the fairness performance while maintaining realistic sample quality for a wide range of the reference set size all the way down to 1% relative to training set.

Model fairness is an essential element for Trustworthy AI. While many techniques for model fairness have been proposed, most of them assume that the training and deployment data distributions are identical, which is often not true in practice. In particular, when the bias between labels and sensitive groups changes, the fairness of the trained model is directly influenced and can worsen. We make two contributions for solving this problem. First, we analytically show that existing in-processing fair algorithms have fundamental limits in accuracy and group fairness. We utilize the notion of correlation shifts between labels and groups, which can explicitly capture the change of the above bias. Second, we propose a novel pre-processing step that samples the input data to reduce correlation shifts and thus enables the in-processing approaches to overcome their limitations. We formulate an optimization problem for adjusting the data ratio among labels and sensitive groups to reflect the shifted correlation. A key benefit of our approach lies in decoupling the roles of pre- and in-processing approaches: correlation adjustment via pre-processing and unfairness mitigation on the processed data via in-processing. Experiments show that our framework effectively improves existing in-processing fair algorithms w.r.t. accuracy and fairness, both on synthetic and real datasets.

We study a matrix completion problem that leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that users are categorized into clusters, each of which comprises sub-clusters (or what we call “groups”). We consider a low-rank matrix model for the rating matrix, and a hierarchical stochastic block model that well respects practically-relevant social graphs. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. Furthermore, we develop a matrix completion algorithm and empirically demonstrate via extensive experiments that the proposed algorithm achieves the optimal sample complexity.

We consider a matrix completion problem that exploits social graph as side information. We develop a computationally efficient algorithm that achieves the optimal sample complexity for the entire regime of graph information under the multiple cluster setting (to be detailed). The key idea is to incorporate a switching mechanism which selects the information employed in the first clustering step, between the following two types: graph & matrix ratings. Our experimental results on both synthetic and real data corroborate our theoretical result as well as demonstrate that our algorithm outperforms prior algorithms that leverage graph side information.

We consider a matrix completion problem that leverages graph as side information. One common approach in recently developed efficient algorithms is to take a two-step procedure: (i) clustering communities that form the basis of the graph structure; (ii) exploiting the estimated clusters to perform matrix completion together with iterative local refinement of clustering. A major limitation of the approach is that it achieves the information-theoretic limit on the number of observed matrix entries, promised by maximum likelihood estimation, only when a sufficient amount of graph side information is provided (the quantified measure is detailed later). The contribution of this work is to develop a computationally efficient algorithm that achieves the optimal sample complexity for the entire regime of graph information. The key idea is to make a careful selection for the information employed in the first clustering step, between two types of given information: graph & matrix ratings. Our experimental results conducted both on synthetic and real data confirm the superiority of our algorithm over the prior approaches in the scarce graph information regime.

Fairness and robustness are critical elements of Trustworthy AI that need to be addressed together. Fairness is about learning an unbiased model while robustness is about learning from corrupted data, and it is known that addressing only one of them may have an adverse affect on the other. In this work, we propose a sample selection-based algorithm for fair and robust training. To this end, we formulate a combinatorial optimization problem for the unbiased selection of samples in the presence of data corruption. Observing that solving this optimization problem is strongly NP-hard, we propose a greedy algorithm that is efficient and effective in practice. Experiments show that our method obtains fairness and robustness that are better than or comparable to the state-of-the-art technique, both on synthetic and benchmark real datasets. Moreover, unlike other fair and robust training baselines, our algorithm can be used by only modifying the sampling step in batch selection without changing the training algorithm or leveraging additional clean data.

We investigate a K-user parallel packet-erasure broadcast channel. There is an ongoing effort to harness millimeter-wave bands, which are known to be unstable having high outage probabilities, by combining them with stable legacy bands. Motivated by this effort, we consider a heterogeneous scenario in which the parallel subchannels are categorized into two classes having different outage probabilities. For the two-user case, we characterize the sum capacity by developing an explicit achievable scheme and deriving a matching upper bound. In contrast to suboptimal schemes that apply coding on a per-subchannel basis only, our scheme applies coding across subchannels to exploit coding opportunities that arise from asymmetric outage probabilities more efficiently, thereby achieving optimality. By extending our scheme systematically to be applicable for the K-user case, we show that it can provide significant gains over existing schemes. Compared to the K-user scheme currently employed in practice, which allocates chunks of subchannels to users exclusively, we demonstrate the performance improvement attainable by our scheme to be substantial, as the multiplicative gain scales with K. Moreover, we find that our scheme outperforms a per-subchannel extension of state-of-the-art K-user schemes by large margins, further reducing the optimality gap. Our results suggest a potential coding scheme that can be employed in future wireless systems to meet ever-growing mobile data demands.

Trustworthy AI is a critical issue in machine learning where, in addition to training a model that is accurate, one must consider both fair and robust training in the presence of data bias and poisoning. However, the existing model fairness techniques mistakenly view poisoned data as an additional bias to be fixed, resulting in severe performance degradation. To address this problem, we propose FR-Train, which holistically performs fair and robust model training. We provide a mutual information-based interpretation of an existing adversarial training-based fairness-only method, and apply this idea to architect an additional discriminator that can identify poisoned data using a clean validation set and reduce its influence. In our experiments, FR-Train shows almost no decrease in fairness and accuracy in the presence of data poisoning by both mitigating the bias and defending against poisoning. We also demonstrate how to construct clean validation sets using crowdsourcing, and release new benchmark datasets.

As machine learning becomes prevalent in our daily lives involving a widening array of applications such as medicine, finance, job hiring and criminal justice, one morally & legally motivated need for machine learning algorithms is to ensure fairness for disadvantageous against advantageous groups. Fairness in machine learning aims at guaranteeing the irrelevancy of a prediction output to sensitive attributes like race, sex and religion. To this end, we take an information- theoretic approach using mutual information (MI) which can fully capture such independence. Inspired by the fact that MI between prediction and the sensitive attribute being zero is the "sufficient and necessary condition" for independence, we develop an MI-based algorithm that well trades off prediction accuracy for fairness performance often quantified as Disparate Impact (DI) or Equalized Odds (EO). Our experiments both on synthetic and benchmark real datasets demonstrate that our algorithm outperforms prior fair classifiers in tradeoff performance both w.r.t. DI and EO.

We consider the problem of recovering communities of users and communities of items (such as movies) based on a partially observed rating matrix as well as side-information in the form of similarity graphs of the users and items. The user-to-user and item-to-item similarity graphs are generated according to the celebrated stochastic block model (SBM). We develop a lower bound on the minimum expected number of observed ratings (also known as the sample complexity) needed for this recovery task, which is a function of various parameters including the quality of the graph side-information manifested in the intra-and inter-cluster probabilities of the SBMs. Our information-theoretic results quantify the benefits of the two-sided graph side-information for recovery, and further analysis reveals that the two pieces of graph side-information produce an interesting synergistic effect under certain scenarios. This means that if one observes only one of the two graphs, then the required sample complexity worsens to the case in which none of the graphs is observed. Thus both graphs are strictly needed to reduce the sample complexity.

As machine learning becomes prevalent in a widening array of sensitive applications such as job hiring and criminal justice, one critical aspect that machine learning classifiers should respect is to ensure fairness: guaranteeing the irrelevancy of a prediction output to sensitive attributes such as gender and race. In this work, we develop a kernel density estimation trick to quantify fairness measures that capture the degree of the irrelevancy. A key feature of our approach is that quantified fairness measures can be expressed as differentiable functions w.r.t. classifier model parameters. This then allows us to enjoy prominent gradient descent to readily solve an interested optimization problem that fully respects fairness constraints. We focus on a binary classification setting and two well-known definitions of group fairness: Demographic Parity (DP) and Equalized Odds (EO). Our experiments both on synthetic and benchmark real datasets demonstrate that our algorithm outperforms prior fair classifiers in accuracy-fairness tradeoff performance both w.r.t. DP and EO.

We consider a matrix completion problem that exploits social or item similarity graphs as side information. We develop a universal, parameter-free, and computationally efficient algorithm that starts with hierarchical graph clustering and then iteratively refines estimates both on graph clustering and matrix ratings. Under a hierarchical stochastic block model that well respects practically-relevant social graphs and a low-rank rating matrix model (to be detailed), we demonstrate that our algorithm achieves the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) that is derived by maximum likelihood estimation together with a lower-bound impossibility result. One consequence of this result is that exploiting the hierarchical structure of social graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. We conduct extensive experiments both on synthetic and real-world datasets to corroborate our theoretical results as well as to demonstrate significant performance improvements over other matrix completion algorithms that leverage graph side information.

We explore the role of interaction for the problem of reliable computation over two-way multicast networks. Specifically we consider a four-node network in which two nodes wish to compute a modulo-sum of two independent Bernoulli sources generated from the other two, and a similar task is done in the other direction. The main contribution of this work lies in the characterization of the computation capacity region for a deterministic model of the network via a novel transmission scheme. One consequence of this result is that, not only we can get an interaction gain over the one-way non-feedback computation capacities, but also we can get all the way to perfect-feedback1computation capacities simultaneously in both directions for some channel regimes. This result draws a parallel with the recent result developed in the context of two-way interference channels.This is an idealistic case where feedback links are perfect with infinite capacities and are given for free. We left the exact definition in Section II.

Developing a computer vision-based algorithm for identifying dangerous vehicles requires a large amount of labeled accident data, which is difficult to collect in the real world. To tackle this challenge, we first develop a synthetic data generator built on top of a driving simulator. We then observe that the synthetic labels that are generated based on simulation results are very noisy, resulting in poor classification performance. In order to improve the quality of synthetic labels, we propose a new label adaptation technique that first extracts internal states of vehicles from the underlying driving simulator, and then refines labels by predicting future paths of vehicles based on a well-studied motion model. Via real-data experiments, we show that our dangerous vehicle classifier can reduce the missed detection rate by at least 18.5% compared with those trained with real data when time-to-collision is between 1.6s and 1.8s.

The goal of differentially private data publishing is to release a modified dataset so that its privacy can be ensured while allowing for efficient learning. We propose a new data publishing algorithm in which a released dataset is formed by mixing ℓ randomly chosen data points and then perturbing them with an additive noise. Our privacy analysis shows that as ℓ increases, noise with smaller variance is sufficient to achieve a target privacy level. In order to quantify the usefulness of our algorithm, we adopt the accuracy of a predictive model trained with our synthetic dataset, which we call the utility of the dataset. By characterizing the utility of our dataset as a function of ℓ, we show that one can learn both linear and nonlinear predictive models so that they yield reasonably good prediction accuracies. Particularly, we show that there exists a sweet spot on ℓ that maximizes the prediction accuracy given a required privacy level, or vice versa. We also demonstrate that given a target privacy level, our datasets can achieve higher utility than other datasets generated with the existing data publishing algorithms.

Coding for distributed computing supports low-latency computation by relieving the burden of straggling workers. While most existing works assume a simple master-worker model, we consider a hierarchical computational structure consisting of groups of workers, motivated by the need to reflect the architectures of real-world distributed computing systems. In this work, we propose a hierarchical coding scheme for this model, as well as analyze its decoding cost and expected computation time. Specifically, we first provide upper and lower bounds on the expected computing time of the proposed scheme. We also show that our scheme enables efficient parallel decoding, thus reducing decoding costs by orders of magnitude over non-hierarchical schemes. When considering both decoding cost and computing time, the proposed hierarchical coding is shown to outperform existing schemes in many practical scenarios.

Rich experimental evidences show that one can better estimate users' unknown ratings with the aid of graph side information such as social graphs. However, the gain is not theoretically quantified. In this work, we study the binary rating estimation problem to understand the fundamental value of graph side information. Considering a simple correlation model between a rating matrix and a graph, we characterize the sharp threshold on the number of observed entries required to recover the rating matrix (called the optimal sample complexity) as a function of the quality of graph side information (to be detailed). To the best of our knowledge, we are the first to reveal how much the graph side information reduces sample complexity. Further, we propose a computationally efficient algorithm that achieves the limit. Our experimental results demonstrate that the algorithm performs well even with real-world graphs.

We investigate the benefits of incorporating relays in future multi-user wireless networks that seek to exploit unexplored bands of very high frequency spectrum, where transmitted signals are known to be highly susceptible to outages. To this end, we examine a two-user bursty MIMO Gaussian interference channel with an in-band relay, where Bernoulli random states conceptually capture signal outages. As our main result, we show that an in-band relay can provide a degrees of freedom (DoF) gain in this bursty channel. This beneficial role of in-band relays in the bursty channel is in direct contrast to their role in the non-bursty channel which is not as significant to provide a DoF gain. More importantly, we demonstrate that in certain antenna configurations, an in-band relay can help achieve interference-free performances with increased DoF. We find the benefits particularly substantial in high-outage circumstances, as the DoF gain can grow linearly with the number of antennas at the relay. In this paper, first we derive an outer bound from which we obtain a necessary condition for interference-free DoF performances. Then we develop a novel scheme that exploits information of the bursty channel states to achieve them.

We explore an active top-$K$ ranking problem based on pairwise comparisons that are collected possibly in a sequential manner as per our design choice. We consider two settings: (1) top-$K$ sorting in which the goal is to recover the top-$K$ items in order out of $n$ items; (2) top-$K$ partitioning where only the set of top-$K$ items is desired. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize upper bounds on the sample size required for top-$K$ sorting as well as for top-$K$ partitioning. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around $\frac{\log n}{\log \log n}$ to $\frac{ n^2 \log n }{\log \log n}$. We also present an algorithm that is applicable to both settings.

Subspace clustering is a celebrated problem that comes up in a variety of applications such as motion segmentation and face clustering. The goal of the problem is to find clusters in different subspaces from similarity measurements across data points. While the algorithmic aspect of this problem has been extensively studied in the literature, the information-theoretic limit on the number of similarities required for reliable clustering has been unknown. In this paper, we translate the problem into an instance of community recovery in hypergraphs, and characterize the sharp threshold on the limit required for exact subspace clustering. Moreover, we present a computationally efficient algorithm that achieves the fundamental limit.

Motivated by recent efforts to harness millimeter-wave (mmWave) bands, known to have high outage probabilities, we explore a K-user parallel packet-erasure broadcast channel that consists of orthogonal subchannels prone to packet-erasures. Our main result is two-fold. First, in the homogeneous channel where all subchannels have the same erasure probability, we show that the separation principle holds, i.e., coding across subchannels provides no gain. Second, in the heterogeneous channel where the subchannels have different erasure probabilities, we devise a scheme that employs coding across subchannels and show that the principle fails to hold, i.e., coding across subchannels provides a gain. Inspired by this finding, we demonstrate our scheme to be effective in harnessing the mmWave bands. Compared to the current approach in the 4G systems which allocates subchannels to users exclusively, we show that our scheme offers a huge gain. We find the gain to be significant in scenarios where the erasure probabilities are largely different, and importantly to increase with the growth of K. Our result calls for joint coding schemes in future wireless systems to meet growing mobile data demands.

Coded computation is a framework for providing redundancy in distributed computing systems to make them robust to slower nodes, or stragglers. In [1], the authors propose a coded computation scheme based on maximum distance separable (MDS) codes for computing the product ATB, and this scheme is suitable for the case where one of the matrices is small enough to fit into a single compute node. In this work, we study coded computation involving large matrix multiplication where both matrices are large, and propose a new coded computation scheme, which we call product-coded matrix multiplication. Our analysis reveals interesting insights into which schemes perform best in which regimes. When the number of backup nodes scales sub-linearly in the size of the product, the product-coded scheme achieves the best run-time performance. On the other hand, when the number of backup nodes scales linearly in the size of the product, the MDS-coded scheme achieves the fundamental limit on the run-time performance. Further, we propose a novel application of low-density-parity-check (LDPC) codes to achieve linear-time decoding complexity, thus allowing our proposed solutions to scale gracefully.

Two-way communication is prevalent and its fundamental limits are first studied in the point-to-point setting by Shannon. One natural extension is a two-way interference channel (IC) with four independent messages: two associated with each direction of communication. In this paper, we explore a deterministic two-way IC, which captures the key properties of the wireless Gaussian channel. Our main contribution lies in the complete capacity region characterization of the two-way IC (with respect to the forward and backward sum-rate pair) via a new achievable scheme and a new converse. One surprising consequence of this result is that not only we can get an interaction gain over the one-way non-feedback capacities, we can sometimes get all the way to perfect feedback capacities in both directions simultaneously. In addition, our novel outer bound characterizes channel regimes in which interaction has no bearing on capacity.

We explore the top-K rank aggregation problem in which one aims to recover a consistent ordering that focuses on top-K ranked items based on partially revealed preference information. We examine an M-wise comparison model that builds on the Plackett-Luce (PL) model where for each sample, M items are ranked according to their perceived utilities modeled as noisy observations of their underlying true utilities. As our result, we characterize the minimax optimality on the sample size for top-K ranking. The optimal sample size turns out to be inversely proportional to M. We devise an algorithm that effectively converts M-wise samples into pairwise ones and employs a spectral method using the refined data. In demonstrating its optimality, we develop a novel technique for deriving tight $\ell_\infty$ estimation error bounds, which is key to accurately analyzing the performance of top-K ranking algorithms, but has been challenging. Recent work relied on an additional maximum-likelihood estimation (MLE) stage merged with a spectral method to attain good estimates in $\ell_\infty$ error to achieve the limit for the pairwise model. In contrast, although it is valid in slightly restricted regimes, our result demonstrates a spectral method alone to be sufficient for the general M-wise model. We run numerical experiments using synthetic data and confirm that the optimal sample size decreases at the rate of 1/M. Moreover, running our algorithm on real-world data, we find that its applicability extends to settings that may not fit the PL model.

We study the top-K ranking problem where the goal is to recover the set of top-K ranked items out of a large collection of items based on partially revealed preferences. We consider an adversarial crowdsourced setting where there are two population sets, and pairwise comparison samples drawn from one of the populations follow the standard Bradley-Terry-Luce model (i.e., the chance of item i beating item j is proportional to the relative score of item i to item j), while in the other population, the corresponding chance is inversely proportional to the relative score. When the relative size of the two populations is known, we characterize the minimax limit on the sample size required (up to a constant) for reliably identifying the top-K items, and demonstrate how it scales with the relative size. Moreover, by leveraging a tensor decomposition method for disambiguating mixture distributions, we extend our result to the more realistic scenario, in which the relative population size is unknown, thus establishing an upper bound on the fundamental limit of the sample size for recovering the top-K set.

In this paper, we propose an opportunistic downlink interference alignment (ODIA) for interference-limited cellular downlink, which intelligently combines user scheduling and downlink IA techniques. The proposed ODIA not only efficiently reduces the effect of inter-cell interference from other-cell base stations (BSs) but also eliminates intra-cell interference among spatial streams in the same cell. We show that the minimum number of users required to achieve a target degrees-of-freedom can be fundamentally reduced, i.e., the fundamental user scaling law can be improved by using the ODIA, compared with the existing downlink IA schemes. In addition, we adopt a limited feedback strategy in the ODIA framework, and then analyze the number of feedback bits required for the system with limited feedback to achieve the same user scaling law of the ODIA as the system with perfect channel state information. We also modify the original ODIA in order to further improve the sum-rate, which achieves the optimal multiuser diversity gain, i.e., log log N, per spatial stream even in the presence of downlink inter-cell interference, where N denotes the number of users in a cell. Simulation results show that the ODIA significantly outperforms existing interference management techniques in terms of sum rate in realistic cellular environments. Note that the ODIA operates in a non-collaborative and decoupled manner, i.e., it requires no information exchange among BSs and no iterative beamformer optimization between BSs and users, thus leading to an easier implementation.

Motivated by applications in domains such as social networks and computational biology, we study the problem of community recovery in graphs with locality. In this problem, pairwise noisy measurements of whether two nodes are in the same community or different communities come mainly or exclusively from nearby nodes rather than uniformly sampled between all node pairs, as in most existing models. We present two algorithms that run nearly linearly in the number of measurements and which achieve the information limits for exact recovery.

We explore the role of a relay in multiuser networks where some physical perturbation shared around the users may generate data traffic for them simultaneously, hence cause their transmission patterns to be correlated. We investigate how the gain from the help of a relay varies with correlations across the users' transmission patterns in a bursty multiple access channel where the users send signals intermittently. As our main results, we show that in most cases a relay can provide a greater degrees-of-freedom (DoF) gain when the users' transmission patterns are more correlated. Furthermore, we demonstrate that the DoF gain can scale with the number of users.

We explore two-way interference channels (ICs) where there are forward and backward ICs with four independent messages: two associated with the forward IC and the other two with respect to the backward IC. For a linear deterministic model of this channel, we develop inner and outer bounds on the capacity region. As a consequence, we demonstrate that interaction across forward and backward channels enables a more beneficial use of the channels, thereby yielding strict capacity improvements over non-interactive independent transmission. Moreover, our novel outer bound establishes the characterization of channel regimes in which interaction has no bearing on sum capacity.

This paper is concerned with jointly recovering n node variables {xi}1≤i≤nfrom a collection of pairwise difference measurements. Imagine we acquire a few observations taking the form of xi- xj; the observation pattern is represented by a measurement graph G with an edge set ℰ, such that xi-xjis observed if and only if (i, j) ε ℰ. To account for noisy measurements in a general manner, we model the data acquisition process by a set of channels with given input/output transition measures. Employing information-theoretic tools applied to channel decoding problems, we develop a unified framework to characterize the fundamental recovery criterion, which accommodates general graph structures, alphabet sizes, and channel transition measures. In particular, our results isolate a family of minimum channel divergence measures to characterize the degree of measurement corruption, which together with the size of the minimum cut of G dictates the feasibility of exact information recovery. For various homogeneous graphs, the recovery condition depends almost only on the edge sparsity of the measurement graph irrespective of other graphical metrics; alternatively, the minimum sample complexity required for these graphs scales like (n log n)/(Hel1/2min) for certain information metric Hel1/2mindefined in the main text, as long as the alphabet size is not super-polynomial in n. We apply our general theory to three concrete applications, including the stochastic block model, the random corruption model, and the haplotype assembly problem. Our theory leads to orderwise tight recovery conditions for all these scenarios.

An uplink-downlink two-cell cellular network is studied in which the first base station (BS) with M1antennas receives independent messages from its N1serving users, while the second BS with M2antennas transmits independent messages to its N2serving users. That is, the first and second cells operate as uplink and downlink, respectively. Each user is assumed to have a single antenna. Under this uplink-downlink setting, the sum degrees of freedom (DoFs) is completely characterized as the minimum of (N1N2+ min(M1, N1)(N1- N2)++ min(M2, N2)(N2- N1)+)/ max(N1, N2), M1+ N2, M2+ N1, max(M1, M2), and max(N1, N2), where a+denotes max(0, a). The result demonstrates that, for a broad class of network configurations, operating one of the two cells as uplink and the other cell as downlink can strictly improve the sum DoF compared with the conventional uplink or downlink operation, in which both cells operate as either uplink or downlink. The DoF gain from such uplink-downlink operation is further shown to be achievable for heterogeneous cellular networks having hotspots and with delayed channel state information.

The classical problem in a network coding theory considers communication over multicast networks. Multiple transmitters send independent messages to multiple receivers that decode the same set of messages. In this paper, computation over multicast networks is considered: each receiver decodes an identical function of the original messages. For a countably infinite class of two-transmitter two-receiver single-hop linear deterministic networks, the computation capacity is characterized for a linear function (modulo-2 sum) of Bernoulli sources. A new upper bound is derived that is tighter than cut-set-based and genie-aided bounds. A matching inner bound is established via the development of a network decomposition theorem, which identifies elementary parallel subnetworks that can constitute an original network without loss of optimality. The decomposition theorem provides a conceptually simple proof of achievability that generalizes to L-transmitter L-receiver networks.

This paper explores the preference-based top-K rank aggregation problem. Suppose that a collection of items is repeatedly compared in pairs, and one wishes to recover a consistent ordering that emphasizes the top-K ranked items, based on partially revealed preferences. We focus on the Bradley-Terry-Luce (BTL) model that postulates a set of latent preference scores underlying all items, where the odds of paired comparisons depend only on the relative scores of the items involved. We characterize the minimax limits on identifiability of top-K ranked items, in the presence of random and non-adaptive sampling. Our results highlight a separation measure that quantifies the gap of preference scores between the K-th and (K+1)-th ranked items. The minimum sample complexity required for reliable top-K ranking scales inversely with the separation measure irrespective of other preference distribution metrics. To approach this minimax limit, we propose a nearly linear-time ranking scheme, called Spectral MLE, that returns the indices of the top-K items in accordance to a careful score estimate. In a nutshell, Spectral MLE starts with an initial score estimate with minimal squared loss (obtained via a spectral method), and then successively refines each component with the assistance of coordinate-wise MLEs. Encouragingly, Spectral MLE allows perfect top-K item identification under minimal sample complexity. The practical applicability of Spectral MLE is further corroborated by numerical experiments.

This paper is concerned with jointly recovering n node-variables {x1,..., xn} from a collection of pairwise difference measurements. Specifically, several noisy measurements of xi- xjare acquired. This is represented by a graph with an edge set ε such that xi- xjis observed only if (i, j) ∈ ε. To accommodate the noisy nature of data acquisition in a general way, we model the measurements by a set of channels with given input/output transition measures. Using information-theoretic tools applied to the channel decoding problem, we develop a unified framework to characterize a sufficient and a necessary condition for exact information recovery, which accommodates general graph structures, alphabet sizes, and channel transition measures. In particular, we isolate and highlight a family of minimum distance measures underlying the channel transition probabilities, which plays a central role in determining the recovery limits. For a broad class of homogeneous graphs, the recovery conditions we derive are tight up to some explicit constant, which depend only on the graph sparsity irrespective of other second-order graph metrics like the spectral gap.

We explore the benefits of relays1in multi-user wireless networks with bursty user traffic, where intermittent data traffic restricts the users to bursty transmissions. Specifically, we investigate a two-user bursty MIMO Gaussian interference channel (IC) with a relay, where two Bernoulli random states govern the bursty user traffic. We show that an in-band relay can provide a degrees of freedom (DoF) gain in this bursty channel. This beneficial role is in contrast to the role in the non-bursty channel which is not as significant to provide a DoF gain. More importantly, we demonstrate that for certain antenna configurations, an in-band relay can help achieve an interference-free performance with increased DoF. Particularly, we find the benefits of a relay substantial with low user traffic, as the DoF gain can scale linearly with the number of antennas at the relay. To this end, we derive an outer bound from which we obtain a necessary condition for interference-free DoF performances. Then, we develop a novel scheme that exploits information of the bursty traffic states to achieve the performances.

We study the sum degrees of freedom (DoFs) of the K-user rank-deficient interference channel with feedback. For the two-user case, we characterize the sum DoF by developing an achievable scheme and deriving a matching upper bound. For the three-user case, we develop a new achievable scheme which employs interference alignment to efficiently utilize the dimension of the received signal space. In addition, we derive an upper bound for the general K-user case and show the tightness of the bound when the number of antennas at each node is sufficiently large. As a consequence of these results, we show that feedback can increase the DoF when the number of antennas at each node is large enough as compared with the ranks of channel matrices. This finding is in contrast to the full-rank interference channel where feedback provides no DoF gain. The gain comes from using feedback to provide alternative signal paths, thereby effectively increasing the ranks of desired channel matrices.

In this paper, we extend the information theoretic framework that was developed in earlier works to multi-hop network settings. For a given network, we construct a novel deterministic model that quantifies the ability of the network in transmitting private and common messages across users. Based on this model, we formulate a linear optimization problem that explores the throughput of a multi-layer network, thereby offering the optimal strategy as to what kind of common messages should be generated in the network to maximize the throughput. With this deterministic model, we also investigate the role of feedback for multi-layer networks, from which we identify a variety of scenarios in which feedback can improve transmission efficiency. Our results provide fundamental guidelines as to how to coordinate cooperation between users to enable efficient information exchanges across them.

In this paper, we propose an opportunistic interference alignment (OIA) technique for cellular downlink networks, which efficiently reduces the effect of inter-cell interference from base stations (BSs) in other cells and eliminates intra-cell interference among spatial streams in the same cell. We show that the user scaling per cell required to achieve a target degrees-of-freedom can be fundamentally lowered, compared with the previous results. In addition, we relate the derived user scaling law to the interference decaying rate with respect to the number of users for given signal-to-noise ratio. Simulation results show that the proposed OIA significantly outperforms the previous schemes in terms of both sum-interference and achievable sum-rate even in practical environments.

An uplink-downlink cellular network is studied in which the first base station (BS) with M1antennas receives independent messages from its N1serving users, while the second BS with M2antennas transmits independent messages to its N2serving users. Each user is assumed to have a single antenna. Under this uplink-downlink setting, the sum degrees of freedom (DoF) is completely characterized as the minimum of (N1N2+ min(M1,N1)(N1- N2)++ min(M2,N2)(N2-N1)+)/ max(N1,N2), M1+ N2,N1+ M2, max(M1,M2), and max(N1,N2), where a+denotes max(0, a). The result demonstrates that, depending on the network configuration, operating one of the cells as uplink and the other cell as downlink can improve DoF compared to the conventional uplink or downlink operation, in which both cells operate as either uplink or downlink.

We introduce an opportunistic downlink interference alignment (ODIA) for interference-limited cellular downlink, which intelligently combines user scheduling and downlink IA techniques. The proposed ODIA not only efficiently reduces the effect of inter-cell interference from other-cell base stations (BSs) but also eliminates intra-cell interference among spatial streams in the same cell. We show that compared to the existing downlink IA schemes, the minimum number of users required to achieve a target degrees-of-freedom (DoF) can be fundamentally reduced, i.e., the fundamental user scaling law can be improved, by using the ODIA. In addition, we introduce a limited feedback strategy in our ODIA framework, and then analyze the minimum number of feedback bits required to obtain the same performance as that of the ODIA assuming perfect feedback.

We establish the degrees of freedom (DoF) of the two-user X-channel with delayed channel knowledge at transmitters [i.e., delayed channel state information at the transmitters (CSIT)], assuming linear coding strategies at the transmitters. We derive a new upper bound and characterize the linear DoF of this network to be 6/5. The converse builds upon our development of a general lemma that shows that, if two distributed transmitters employ linear strategies, the ratio of the dimensions of received linear subspaces at the two receivers cannot exceed 3/2, due to delayed CSIT. As a byproduct, we also apply this general lemma to the three-user interference channel with delayed CSIT, thereby deriving a new upper bound of 9/7 on its linear DoF. This is the first bound that captures the impact of delayed CSIT on the DoF of this network, under the assumption of linear encoding strategies.

We characterize the total degrees of freedom (DoF) of the two-user rank-deficient interference channel with feedback, in which transmitter i and receiver j use Miand Njantennas, respectively, and the rank of the channel matrix between transmitter i and receiver j is given by Dji≤ min(Mi, Nj) ∀i, j = 1,2. One consequence of this result is that feedback can increase the DoF when the number of antennas at each node is large enough as compared to the ranks of channel matrices. This finding is in contrast to the full-rank interference channel where feedback provides no DoF gain. The gain comes from using feedback to provide alternative signal paths, thereby effectively increasing the ranks of desired channel matrices.

In this paper, we extend the information theoretical framework that was developed in [1] to multi-hop communication networks. For a given network, we construct a deterministic model that models the ability of the channels in transmitting private and common messages between users in this network. Based on this model, we formulate a linear optimization problem to study the network throughput, where the solution indicates what kind of common messages should be generated in a network to optimize the throughput. Our results provide fundamental guidelines of how users in a network should cooperate with each other to communicate efficiently.

We establish an achievable rate region for discrete memoryless interference relay channels that consist of two source-destination pairs and one or more relays. We develop an achievable scheme combining Han-Kobayashi and noisy network coding. We apply our achievability to two cases. First, we characterize the capacity region of some classes of discrete memoryless interference relay channels. These classes naturally generalize the injective deterministic discrete memoryless interference channel by El Gamal and Costa and the discrete memoryless relay channel. Moreover, for the Gaussian interference relay channel with orthogonal receiver components, we show that our scheme achieves a better sum rate than that of noisy network coding.

We investigate the role of interaction for computation problem settings where nodes intend to compute functions of the raw messages generated at other nodes. In this work, we make some progress on a more elementary research component: feedback. Specifically we characterize the feedback computing capacity of a two-transmitter two-receiver linear deterministic network in which both receivers wish to decode a linear function (modulo-2 sum) of Bernoulli sources generated at the transmitters. Inspired by the concept of interference alignment and compute-and-forward, we develop a new achievable scheme called interactive function alignment. A new converse theorem is established that is tighter than cut-set based and genie-aided bounds. As a consequence of this result, we show that interaction can provide an arbitrarily large gain for computation, as in classical communication settings.

We explore the benefit of feedback for physical layer interference management in wireless networks without centralized upper layer control mechanisms. Lack of coordination in the upper layer could make the interference experienced in the physical layer bursty. To understand how to harness such burstiness with feedback, we investigate a two-user bursty interference channel (IC), where the presence of interference is governed by a Bernoulli random state. We completely characterize the capacity region of the symmetric two-user linear deterministic bursty IC with feedback. The proposed two-phase scheme exploits feedback either for refining the previous interfered reception or for relaying additional information to the legitimate receiver of the other user. Matching outer bounds are derived by novel techniques that take the effect of delayed state information into account. We also use insights from the deterministic case to characterize the approximate symmetric capacity for the symmetric Gaussian bursty IC with feedback in the weak interference regime.

The high repair bandwidth cost of (n,k) maximum distance separable (MDS) erasure codes has motivated a new class of codes that can reduce repair bandwidth over that of conventional MDS codes. In this paper, we address (n,k,d) exact repair MDS codes, which allow for any single failed node to be repaired exactly with access to any arbitrary set ofdsurvivor nodes. We show the existence of exact repair MDS codes that achieve minimum repair bandwidth (matching the cut-set lower bound) for arbitrary admissible (n,k,d), i.e.,k≤d≤n-1. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set ofr≤n-kfailed nodes needs to repaired. Our approach is based on asymptotic interference alignment proposed by Cadambe and Jafar. As a byproduct, we also characterize the capacity of a class of multisource nonmulticast networks.

We consider the scalar K-user Gaussian interference channel (IC) with feedback, where channel coefficients are fixed over time and frequency. We focus on two feedback models: (1) each receiver feeds back its received signal to all the transmitters and (2) functions of the received signals are fed back through a backward IC. We show that the feedback degrees-of-freedom (fdof) of the first model is k/2 if the global channel matrix is invertible. For the second feedback model, we show that fdof = 3/2 is achievable for the 3-user IC. Then, we show how nontrivial fdof can be achieved for the K-user IC, when the global channel matrix belongs to a specific spectral family of matrices. Our achievable schemes are linear and require a finite number of signal-space dimensions, contrasting the asymptotic interference alignment by Cadambe et al. and the real interference alignment by Motahari et al. Another consequence of feedback is that it can strictly increase the degrees-of-freedom for some classes of ICs.

We characterize the capacity region to within log {2(M - 1)} bits/s/Hz for the M-transmitter K-receiver Gaussian multicast channel with feedback where each receiver wishes to decode every message from the M transmitters. Extending Cover-Leung's achievable scheme intended for (M, K) = (2, 1), we show that this generalized scheme achieves the cutset-based outer bound within log {2(M - 1)} bits per transmitter for all channel parameters. In contrast to the capacity in the nonfeedback case, the feedback capacity improves upon the naive intersection of the feedback capacities of K individual multiple access channels. We find that feedback provides unbounded multiplicative gain at high signal-to-noise ratios as was shown in the Gaussian interference channel. To complement the results, we establish the exact feedback capacity of the Avestimehr-Diggavi-Tse deterministic model, from which we make the observation that feedback can also be beneficial for function computation.

We consider two-way interference channels (ICs) where forward and backward channels are ICs but not necessarily the same. We first consider a scenario where there are only two forward messages and feedback is offered through the backward IC for aiding forward-message transmission. For a linear deterministic model of this channel, we develop inner and outer bounds that match for a wide range of channel parameters. We find that the backward IC can be more efficiently used for feedback rather than if it were used for independent backward-message transmission. As a consequence, we show that feedback can provide a net increase in capacity even if feedback cost is taken into consideration. Moreover we extend this to a more general scenario with two additional independent backward messages, from which we find that interaction can provide an arbitrarily large gain in capacity.

Determining the capacity of multi-receiver networks with arbitrary message demands is an open problem in the network coding literature. In this paper, we consider a multi-source, multi-receiver symmetric deterministic network model parameterized by channel coefficients (inspired by wireless network flow) in which the receivers compute a sum of the symbols generated at the sources. Scalar and vector linear coding strategies are analyzed. It is shown that computation alignment over finite field vector spaces is necessary to achieve the computation capacities in the network. To aid in the construction of coding strategies, network equivalence theorems are established for the decomposition of deterministic models into elementary sub-networks. The linear coding capacity for computation is characterized for all channel parameters considered in the model for a countably infinite class of networks. The constructive coding schemes introduced herein for a specific class of networks provide an optimistic viewpoint for the application of structured codes in network communication.

We consider the two-user interference channel with rate-limited feedback. Related prior works focus on the case where feedback links have infinite capacity, while no research has been done for the rate-limited feedback problem. Several new challenges arise due to the capacity limitations of the feedback links, both in deriving inner bounds and outer bounds. We study this problem under three different interference models: the El Gamal-Costa deterministic model, the linear deterministic model, and the Gaussian model. For the first two models, we develop an achievable scheme that employs three techniques: Han-Kobayashi message splitting, quantize-and-binning, and decode-and-forward. We also derive new outer bounds for all three models and we show the optimality of our scheme under the linear deterministic model. In the Gaussian case, we propose a transmission strategy that incorporates lattice codes, inspired by the ideas developed in the first two models. For symmetric channel gains, we prove that the gap between the achievable sum rate of the proposed scheme and our new outer bounds is bounded by a constant number of bits, independent of the channel gains.

Distributed storage systems often introduce redundancy to increase reliability. When coding is used, the repair problem arises: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. This amounts to a partial recovery of the code, whereas conventional erasure coding focuses on the complete recovery of the information from a subset of encoded packets. The consideration of the repair network traffic gives rise to new design challenges. Recently, network coding techniques have been instrumental in addressing these challenges, establishing that maintenance bandwidth can be reduced by orders of magnitude compared to standard erasure codes. This paper provides an overview of the research results on this topic.

We develop an interference alignment (IA) technique for a downlink cellular system. In the uplink, IA schemes need channel-state-information exchange across base-stations of different cells, but our downlink IA technique requires feedback only within a cell. As a result, the proposed scheme can be implemented with a few changes to an existing cellular system where the feedback mechanism (within a cell) is already being considered for supporting multi-user MIMO. Not only is our proposed scheme implementable with little effort, it can in fact provide substantial gain especially when interference from a dominant interferer is significantly stronger than the remaining interference: it is shown that in the two-isolated cell layout, our scheme provides four-fold gain in throughput performance over a standard multi-user MIMO technique. We also show through simulations that our technique provides respectable gain under a more realistic scenario: it gives approximately 28% gain for a 19 hexagonal wrap-around-cell layout. Furthermore, we show that our scheme has the potential to provide substantial gain for macro-pico cellular networks where pico-users can be significantly interfered with by the nearby macro-BS.

The high repair cost of$(n,k)$Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of MDS codes, called Repair MDS codes, that can significantly reduce repair bandwidth over conventional MDS codes. In this paper, we describe$(n,k,d)$Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to$d$survivor nodes, where$k\leq d\leq n-1$. We construct Exact-Repair MDS codes that are optimal in repair bandwidth for the cases of:$(a)~k/n\leq 1/2$and$d\geq 2k-1$In this paper, we assume that all of the survivor systematic nodes participate in the repair.;$(b)~k\leq 3$. Our codes are deterministic and require a finite-field size of at most$2(n-k)$. Our constructive codes are based on interference alignment techniques.

We characterize the capacity region to within 2 bits/s/Hz and the symmetric capacity to within 1 bit/s/Hz for the two-user Gaussian interference channel (IC) with feedback. We develop achievable schemes and derive a new outer bound to arrive at this conclusion. One consequence of the result is that feedback provides multiplicative gain at high signal-to-noise ratio: the gain becomes arbitrarily large for certain channel parameters. This finding is in contrast to point-to-point and multiple-access channels where feedback provides no gain and only bounded additive gain respectively. The result makes use of a linear deterministic model to provide insights into the Gaussian channel. This deterministic model is a special case of the El Gamal-Costa deterministic model and as a side-generalization, we establish the exact feedback capacity region of this general class of deterministic ICs.

We develop an interference alignment (IA) technique for a downlink cellular system. In the uplink, IA schemes need channel-state-information exchange across base-stations of different cells, but our downlink IA technique requires feedback only within a cell. As a result, the proposed scheme can be implemented with minimal changes to an existing cellular system where the feedback mechanism (within a cell) is already being considered for supporting multi-user MIMO. Not only is our proposed scheme implementable with little effort, it can in fact provide substantial gain especially when interference from a dominant interferer is significantly stronger than the remaining interference: it is shown that in the two-isolated cell layout, our scheme provides four-fold gain in throughput performance over a standard multi-user MIMO technique. We show through simulations that our technique provides respectable gain under a more realistic scenario: it gives approximately 20% gain for a 19 hexagonal wrap-around-cell layout.

The high repair cost of (n, k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. In this paper, we address bandwidth-optimal (n, k, d) Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to arbitrary d survivor nodes, where k ≤ d ≤ n - 1. Under scalarlinear codes which do not permit symbol-splitting, we construct Exact-Repair MDS codes that are optimal in repair bandwidth for the case of k/n ≤ 1/2 and d ≥ 2k - 1. Our codes are deterministic and require a finite-field size of at most 2(n - k). Under vector-linear codes which allow for the break-up of stored symbols into arbitrarily small subsymbols, we show the existence of optimal Exact-Repair codes for the entire admissible range of possible (n, k, d), i.e., k ≤ n and k ≤ d ≤ n - 1. That is, we establish the existence of vector-linear Exact-Repair MDS codes that match the fundamental cutset lower bound. Our approach for both the constructive scalar-linear code design and for the existence of vector-linear codes is based on interference alignment techniques.

We characterize the symmetric capacity of the two-user Gaussian interference channel withfeedbackto within 1 bit/s/Hz. The result makes use of a deterministic model to provide insights into the Gaussian channel. We derive a new outer bound to show that a proposed scheme can achieve the symmetric capacity to within one bit for all channel parameters. One consequence of the result is that feedback providesunboundedgain, i.e., the gain becomes arbitrarily large for certain channel parameters. It is a surprising result because feedback has been so far known to provide no gain in memoryless point-to-point channels and only power gain (boundedgain) in the multiple access channels. The gain comes from using feedback to fully exploit the side information provided by the broadcast nature of the wireless medium.

We consider a multicast resource allocation problem for the downlink in OFDM-based wireless cellular network systems. In a conventional multicast system, to accommodate users with bad channel conditions, the transmission is based on the worst case user. We show that such a multicast system saturates the capacity when the number of users increases in fading environments. We exploit the multicarrier nature of OFDM and advances in coding techniques such as MDC (multiple description coding), in which arbitrary combinations of layers can be decoded at the receiver. Different MDC layers are carried over different subcarriers and users with good channels receive data from more subcarriers than users with poor channel conditions. We present an optimal subcarrier/bit allocation method requiring full search of possible candidates. To reduce the complexity, we propose a two-step suboptimum algorithm by separating subcarrier allocation and bit loading. Numerical results show that the proposed heuristics significantly outperform the conventional multicast transmission scheme. The difference between optimum and heuristic solutions is less than 5%.

We consider a multicast resource allocation problem for the downlink in OFDM-based wireless cellular network systems. In a conventional multicast system, to accommodate users with bad channel conditions, the transmission is based on the worst case user. We show that such a multicast system saturates the capacity when the number of users increases in fading environments. We exploit the multicarrier nature of OFDM and advances in,coding techniques such as MDC (multiple description coding), in which arbitrary combinations of layers can be decoded at the receiver. Different MDC layers are carried over different subcarriers and users with good channels receive data from more subcarriers than users with poor channel conditions. We present an optimal subcarrier/bit allocation method requiring full search of possible candidates. To reduce the complexity, we propose a two-step suboptimum algorithm by separating subcarrier allocation and bit loading. Numerical results show that the proposed heuristics significantly outperform the conventional multicast transmission scheme. The difference between optimum and heuristic solutions is less than 5%.

Maximum-likelihood (ML) channel estimation for multiple-input-multiple-output (MIMO) channels is derived when orthogonal frequency division multiplexing (OFDM) is employed in cellular systems. While conventional single-cell ML estimation (SCMLE) disregards the effects of inter-cell interference (ICI), multi-cell ML estimation (MCMLE) exploits the knowledge of the preambles from neighboring base stations (BSs) to combat severe ICI. The mean square error (MSE) of the MCMLE is smaller than the conventional SCMLE at the cell boundaries where signal-to-interference ratio (SIR) is about 0 dB. However, the MCMLE performs worse than the SCMLE when the mobile station (MS) is near BS because the MCMLE estimates more parameters than the SCMLE. In addition, we evaluate the influence of non-ideal preambles to the performance of channel estimation because all the preambles in cells cannot be mutually orthogonal in practice. Numerical results confirm the superiority of the MCMLE to the SCMLE when SIR has a range of 0/spl sim/15 dB.

This paper presents recursive construction of Golay complementary sequences in order to give a flexibility to GCS length and the constellation. The recursive constructions for QPSK-GCS, 8PSK-GCS, and 8QAM-GCS have upper bound (3 dB) of PAPR and the constellation aggregation of 8-PSK and 8-QAM constitutes 16-QAM. The GCS are applied to orthogonal frequency division multiplexing (OFDM) systems to design the channel code providing both error correction capability and to generate the training sequence with low PAPR.

In multicast orthogonal frequency division multiplexing (OFDM) systems, the difference in link conditions of users complicates adaptive modulation because modulation should be adjusted to serve the user who experiences the worst channel condition. If we assume that the multicast data are separated into layers and any combination of the layers can be decoded at the receiver, the network throughput can be increased by performing subcarrier/bit allocation. In this paper, in order to increase network throughput, we develop the optimum subcarrier/bit allocation method that maximizes the sum of data rate of all the users employing integer programming (IP) which is NP-hard problem. To reduce the complexity, suboptimum two-step algorithm is proposed: firstly, subcarriers are allocated to users under the assumption that the same power is distributed to each subcarrier; in the second step, the number of bits loaded to each subcarrier is determined using the modified Levin-Campello algorithm. Numerical results show that the performance difference between the optimum and suboptimum algorithms is within about 5%, and that total throughput of the proposed algorithm is larger than that of the lowest channel gain (LCG) method where modulation is determined to serve the user with the lowest channel gain.

In this paper we propose and analyze an adaptive spatial modulation scheme for MIMO-OFDM systems which adaptively and optimally selects one of the following transmission modes: diversity, spatial multiplexing and a hybrid combination of these two modes. Two criterias are used for mode selection, namely, the minimum Euclidean distance and a simple threshold based stochastic method exploiting channel quality estimations. We consider practically implementable antenna configuration with four transmit antennas and two or four receive antennas. Simulation results show that considerable BER performance gains can be obtained by the adaptive spatial modulation system, as compared with systems based on fixed modulation schemes.

A maximum-likelihood (ML) channel estimation and preamble design rules for the multiple-input-multiple-output (MIMO) channels are described when orthogonal frequency division multiplexing (OFDM) is employed with null subcarriers at both DC and high frequencies. The ML channel estimator in the time domain is derived assuming the knowledge of the maximum length of channel. To reduce the mean square error (MSE) of the estimation, three design rules are proposed: orthogonality between the preambles of different antennas, orthogonality between the circular shifted preamble sequences, and the condition that the number of subcarriers is larger than the maximum length of channel multiplied by the number of transmit antennas. In addition, we prove that the use of Golay complementary sequence (GCS) for preamble limits the peak to average power ratio (PAPR) by 3 dB although there are null subcarriers at high frequencies. Numerical results show that the MSE of the proposed method approaches that of optimum ML estimation when the number of null subcarriers and maximum length of channel are small.

The time-domain channel estimator is compared with the frequency-domain channel estimator when multiple-input-multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) is employed. The time-domain maximum likelihood channel estimation (TMLE) and its mean square error (MSE) are derived assuming the knowledge of the maximum channel length. If we use only one OFDM symbol for the estimation, the preamble sequence of each transmit antenna uses a different set of subcarriers in MIMO-OFDM systems. As a result, the MSE of the frequency-domain least square channel estimation (FLSE) is derived assuming that linear interpolation is employed, numerical results show that the MSE of TMLE is smaller than that of FLSE and that the performance difference increases as the number of transmit antenna increases.

This paper deals with carrier frequency estimation for transmissions with antenna diversity. Joint maximum likelihood estimates (MLE) of channel and frequency offset are derived and periodic space-time training sequences that can simplify the implementation of the ML frequency estimate, while minimizing the mean square error (MSE) of the estimate are designed. Statistical analysis indicates that the MLE is unbiased and almost achieves the Cramer-Rao bound (CRB). Simulation shows that MLE with optimal training sequences is preferable to one with arbitrary training sequences in mobile communications.