Recent work has argued that federated learning over wireless channels can be accelerated by a factor of$K$(the numbers of users), by using computation over multiple-access channels to directly average the gradients. This implicitly presumes that timely channel state information is available at the transmitters, which may not be feasible for large$K$. This paper presents a simple scheduling algorithm that only uses channel state information at the receiver to activate a subset of the users for computation, and accelerates averaging by a factor of$K^{2/3}$.

This paper introduces a framework for approximate message passing (AMP) in dynamic settings where the data at each iteration is passed through a linear operator. This framework is motivated in part by applications in large-scale, distributed computing where only a subset of the data is available at each iteration. An autoregressive memory term is used to mitigate information loss across iterations and a specialized algorithm, called projection AMP, is designed for the case where each linear operator is an orthogonal projection. Precise theoretical guarantees are provided for a class of Gaussian matrices and non-separable denoising functions. Specifically, it is shown that the iterates can be well-approximated in the high-dimensional limit by a Gaussian process whose second-order statistics are defined recursively via state evolution. These results are applied to the problem of estimating a rank-one spike corrupted by additive Gaussian noise using partial row updates, and the theory is validated by numerical simulations.

This paper considers the problem of distributed lossy compression where the goal is to recover one or more linear combinations of the sources at the decoder, subject to distortion constraints. For certain configurations, it is known that codes with algebraic structure can outperform i.i.d. codebooks. For the special case of finite-alphabet sources, recent work has demonstrated how to incorporate joint typicality decoding alongside linear encoding and binning. This work takes a discretization approach to extend this rate region to include both integer- and real-valued sources. As a case study, the rate region is evaluated for the Gaussian case. The resulting joint-typicality-based rate region recovers and generalizes the best-known rate region for this scenario, based on lattice encoding and sequential decoding.

Compute–forward is a coding technique that enables receiver(s) in a network to directly decode one or more linear combinations of the transmitted codewords. Initial efforts focused on Gaussian channels and derived achievable rate regions via nested lattice codes and single-user (lattice) decoding as well as sequential (lattice) decoding. Recently, these results have been generalized to discrete memoryless channels via nested linear codes and joint typicality coding, culminating in a simultaneous-decoding rate region for recovering one or more linear combinations from$K$users. Using a discretization approach, this paper translates this result into a simultaneous-decoding rate region for a wide class of continuous memoryless channels, including the important special case of Gaussian channels. Additionally, this paper derives a single, unified expression for both discrete and continuous rate regions via an algebraic generalization of Rényi’s information dimension.

This paper considers the problem of detecting whether two databases, each consisting of n users with d Gaussian features, are correlated. Under the null hypothesis, the databases are independent. Under the alternate hypothesis, the features are correlated across databases, under an unknown row permutation. A simple test is developed to show that detection is achievable above ${\rho ^2} \approx \frac{1}{d}$. For the converse, the truncated second moment method is used to establish that detection is impossible below roughly ${\rho ^2} \approx \frac{1}{{d\sqrt n }}$ . These results are compared to the corresponding recovery problem, where the goal is to decode the row permutation, and a converse bound of roughly ρ2≈1−n−4/dhas been previously shown. For certain choices of parameters, the detection achievability bound outperforms this recovery converse bound, demonstrating that detection can be easier than recovery in this scenario.

We present a novel unified framework of compute-forward achievable rate regions for simultaneous decoding of multiple linear codeword combinations. This framework covers a wide class of discrete and continuous-input channels, and computation over finite fields, integers, and reals. The resulting rate regions recover several well-known achievability results, and in some cases extend them. The framework is built upon a recently established achievable rate region based on linear codes and joint typicality decoding. The latter is extended from finite fields to computation over the integers and, via a discretization approach, to computation over the reals with integer coefficients and continuous inputs. Evaluating the latter with Gaussian distributions, we obtain a closed-form rate region which generalizes the classic compute-forward rates originally derived by means of lattice codes by Nazer and Gastpar.

Let X and Y be dependent random variables. This paper considers the problem of designing a scalar quantizer for Y to maximize the mutual information between the quantizer's output and X, and develops fundamental properties and bounds for this form of quantization, which is connected to the log-loss distortion criterion. The main focus is the regime of low I(X;Y), where it is shown that, if X is binary, a constant fraction of the mutual information can always be preserved usingO(log(1/I(X;Y))) quantization levels, and there exist distributions for which this many quantization levels are necessary. Furthermore, for larger finite alphabets 2X|X| /I(X;Y)))η·(|X| - 1)quantization levels.

We present novel information-theoretic limits on detecting sparse changes in Isingmodels, a problem that arises in many applications where network changes canoccur due to some external stimuli. We show that the sample complexity fordetecting sparse changes, in a minimax sense, is no better than learning the entiremodel even in settings with local sparsity. This is a surprising fact in light of priorwork rooted in sparse recovery methods, which suggest that sample complexityin this context scales only with the number of network changes. To shed light onwhen change detection is easier than structured learning, we consider testing ofedge deletion in forest-structured graphs, and high-temperature ferromagnets ascase studies. We show for these that testing of small changes is similarly hard, buttesting oflargechanges is well-separated from structure learning. These resultsimply that testing of graphical models may not be amenable to concepts such asrestricted strong convexity leveraged for sparsity pattern recovery, and algorithmdevelopment instead should be directed towards detection of large changes.

Algebraic network information theory is an emerging facet of network information theory, studying the achievable rates of random code ensembles that have algebraic structure, such as random linear codes. A distinguishing feature is that linear combinations of codewords can sometimes be decoded more efficiently than codewords themselves. The present work further develops this framework by studying the simultaneous decoding of multiple messages. Specifically, consider a receiver in a multi-user network that wishes to decode several messages. Simultaneous joint typicality decoding is one of the most powerful techniques for determining the fundamental limits at which reliable decoding is possible. This technique has historically been used in conjunction with random i.i.d. codebooks to establish achievable rate regions for networks. Recently, it has been shown that, in certain scenarios, nested linear codebooks in conjunction with “single-user” or sequential decoding can yield better achievable rates. For instance, the compute-forward problem examines the scenario of recovering L ≤ K linear combinations of transmitted codewords over a K-user multiple-access channel (MAC), and it is well established that linear codebooks can yield higher rates. This paper develops bounds for simultaneous joint typicality decoding used in conjunction with nested linear codebooks, and applies them to obtain a larger achievable region for compute-forward over a K-user discrete memoryless MAC. The key technical challenge is that competing codeword tuples that are linearly dependent on the true codeword tuple introduce statistical dependencies, which requires careful partitioning of the associated error events.

Consider an uplink cloud radio access network where users are observed simultaneously by several base stations, each with a rate-limited link to a central processor, which wishes to decode all transmitted messages. Recent efforts have demonstrated the advantages of compression-based strategies that send quantized channel observations to the central processor, rather than attempt local decoding. We study the setting where channel state information is not available at the transmitters, but known fully or partially at the base stations. We propose an end-to-end integer forcing framework for compression-based uplink cloud radio access, and show that it operates within a constant gap from the optimal outage probability if channel state information is fully available at the base stations.We demonstrate via simulations that our framework is competitive with state-of-the-art Wyner-Ziv-based strategies.

Consider the important special case of the K-user distributed source coding problem where the decoder only wishes to recover one or more linear combinations of the sources. The work of Körner and Marton demonstrated that, in some cases, the optimal rate region is attained by random linear codes, and strictly improves upon the best-known achievable rate region established via random i.i.d. codes. Recent efforts have sought to develop a framework for characterizing the achievable rate region for nested linear codes via joint typicality encoding and decoding. Here, we make further progress along this direction by proposing an achievable rate region for simultaneous joint typicality decoding of nested linear codes. Our approach generalizes the results of Körner and Marton to computing an arbitrary number of linear combinations and to the lossy computation setting.

We propose and analyze the problems of \textit{community goodness-of-fit and two-sample testing} for stochastic block models (SBM), where changes arise due to modification in community memberships of nodes. Motivated by practical applications, we consider the challenging sparse regime, where expected node degrees are constant, and the inter-community mean degree ($b$) scales proportionally to intra-community mean degree ($a$). Prior work has sharply characterized partial or full community recovery in terms of a ``signal-to-noise ratio'' ($\mathrm{SNR}$) based on $a$ and $b$. For both problems, we propose computationally-efficient tests that can succeed far beyond the regime where recovery of community membership is even possible. Overall, for large changes, $s \gg \sqrt{n}$, we need only $\mathrm{SNR}= O(1)$ whereas a na\"ive test based on community recovery with $O(s)$ errors requires $\mathrm{SNR}= \Theta(\log n)$. Conversely, in the small change regime, $s \ll \sqrt{n}$, via an information theoretic lower bound, we show that, surprisingly, no algorithm can do better than the na\"ive algorithm that first estimates the community up to $O(s)$ errors and then detects changes. We validate these phenomena numerically on SBMs and on real-world datasets as well as Markov Random Fields where we only observe node data rather than the existence of links.

Consider the following structural two-sample testing problem: given two sets of sample drawn from Ising models, determine whether the underlying network structure has changed. In [1], we showed that for Ising models over p variables with network structures that have degree bounded by d, under mild conditions on the model parameters, the sample complexity of this problem is very close to that of determining either of the network structures. Therefore, the naive scheme of learning and then comparing the structures of both sets of samples is near data-optimal. However, the minimax lower bounds in [1] relied on Ising models that differed in only one edge, which leads to the natural follow-up question: are large changes significantly easier to detect? We extend the previously developed framework to consider this problem, and show that, in a certain parameter regime, large changes do not provide any significant improvement in the number of necessary samples for reliable two-sample testing.

Consider a Gaussian multiple-input multiple-output (MIMO) multiple-access channel (MAC) with channel matrix H and a Gaussian MIMO broadcast channel (BC) with channel matrix HT. For the MIMO MAC, the integer-forcing architecture consists of first decoding integer-linear combinations of the transmitted codewords, which are then solved for the original messages. For the MIMO BC, the integer-forcing architecture consists of pre-inverting the integer-linear combinations at the transmitter, so that each receiver can obtain its desired codeword by decoding an integer-linear combination. In both the cases, integer-forcing offers higher achievable rates than zero-forcing while maintaining a similar implementation complexity. This paper establishes an uplink-downlink duality relationship for integer-forcing, i.e., any sum rate that is achievable via integer-forcing on the MIMO MAC can be achieved via integer-forcing on the MIMO BC with the same sum power and vice versa. Using this duality relationship, it is shown that integer-forcing can operate within a constant gap of the MIMO BC sum capacity. Finally, the paper proposes a duality-based iterative algorithm for the non-convex problem of selecting optimal beamforming and equalization vectors, and establishes that it converges to a local optimum.

This paper presents a joint typicality framework for encoding and decoding nested linear codes in multi-user networks. This framework provides a new perspective on compute-forward within the context of discrete memoryless networks. In particular, it establishes an achievable rate region for computing a linear combination over a discrete memoryless multiple-access channel (MAC). When specialized to the Gaussian MAC, this rate region recovers and improves upon the lattice-based compute-forward rate region of Nazer and Gastpar, thus providing a unified approach for discrete memoryless and Gaussian networks. Furthermore, our framework provides some valuable insights on establishing the optimal decoding rate region for compute-forward by considering joint decoders, progressing beyond most previous works that consider successive cancellation decoding. Specifically, this paper establishes an achievable rate region for simultaneously decoding two linear combinations of nested linear codewords from K senders.

Recent work has proposed the integer-forcing (IF) linear receiver architecture as a promising alternative to the joint maximum likelihood (ML) receiver. It has been proven that the IF linear receiver can operate very close to the (optimal) performance of the joint ML receiver, but with essentially the same implementation complexity as a zero-forcing (ZF) linear receiver. In this paper, we take the first steps towards a complete software-defined radio (SDR) implementation of the IF linear receiver. Using the Wireless Open-Access Radio Platform (WARP) and IEEE 802.11 protocols, we develop an OFDM-based experimental framework to evaluate the performance of IF linear receivers in realistic indoor settings, and compare it to the performance of ZF and joint ML receivers. Our framework includes a channel estimation protocol and algorithm for selecting the best integer matrix for approximating the channel matrix. We have performed indoor experiments for a 2 × 2 MIMO network, which demonstrate that the symbol error rate (SER) of the IF linear receiver indeed outperforms the ZF linear receiver and can operate close to the joint ML receiver. We also argue, via simulations, that IF continues to outperform conventional linear receivers, even in the presence of significant channel estimation errors.

Recent work has employed joint typicality encoding and decoding of nested linear code ensembles to generalize the compute-forward strategy to discrete memoryless multiple-access channels (MACs). An appealing feature of these nested linear code ensembles is that the coding strategies and error probability bounds are conceptually similar to classical techniques for random i.i.d. code ensembles. In this paper, we consider the problem of recovering K linearly independent combinations over a K-user MAC, i.e., recovering the messages in their entirety via nested linear codes. While the MAC rate region is well-understood for random i.i.d. code ensembles, new techniques are needed to handle the statistical dependencies between competing codeword K-tuples that occur in nested linear code ensembles.

Let X and Y be dependent random variables. We consider the problem of designing a scalar quantizer for Y to maximize the mutual information between its output and X, and study fundamental properties and bounds for this form of quantization. Our main focus is the regime of low I(X; Y), where we show that for a binary X, there always exists an M-level quantizer attaining mutual information of Ω(-M · I(X;Y)/log(I(X;Y)) and that there exist pairs of X, Y for which the mutual information attained by any M-level quantizer is O(-M · I (X;Y)/ log (I(X;Y))).

Integer-forcing is a technique that exploits the algebraic structure of a linear or lattice code to realize “single-user” encoding and decoding algorithms with significant rate gains over conventional strategies. It was originally proposed for the Gaussian MIMO multiple-access channel. Subsequent efforts have generalized this strategy to the Gaussian MIMO broadcast channel and the Gaussian distributed source coding problem. Our prior work has established uplink-downlink duality for integer-forcing. Here, we propose a successive cancellation generalization of integer-forcing source coding. We then develop source-channel duality results that connect the achievable rates of this scheme to those of successive integer-forcing channel coding.

The compute-and-forward framework permits each receiver in a Gaussian network to directly decode a linear combination of the transmitted messages. The resulting linear combinations can then be employed as an end-to-end communication strategy for relaying, interference alignment, and other applications. Recent efforts have demonstrated the advantages of employing unequal powers at the transmitters and decoding more than one linear combination at each receiver. However, neither of these techniques fit naturally within the original formulation of compute-and-forward. This paper proposes an expanded compute-and-forward framework that incorporates both of these possibilities and permits an intuitive interpretation in terms of signal levels. Within this framework, recent achievability and optimality results are unified and generalized.

For the K-user MIMO interference channel, some form of interference alignment is needed to attain the highest possible rates. For the important special case of linear alignment strategies, many iterative optimization algorithms have been proposed that aim to maximize the signal-to-interference-and-noise ratio (SINR) at each receiver. Recent work has demonstrated the advantages of integer-forcing interference alignment (IFIA), which first decodes aligned integer-linear combinations of the codewords and then solves for the desired messages. This paper proposes a class of iterative optimization algorithms for IFIA and demonstrates its advantages via simulations.

Consider several single-antenna transmitters that wish to simultaneously communicate with a multiple-antenna receiver. Recent work has proposed the integer-forcing linear receiver architecture as an alternative to conventional linear receivers. The key idea is to first use linear equalization to obtain an integer-valued effective channel, then employ single-user decoders to recover integer-linear combinations of the messages, and finally solve these for the desired messages. For the special case where the channel matrix remains fixed for the duration of the codeword, it has been shown that integer-forcing can operate very close to the performance of optimal joint maximum likelihood decoding. In this paper, we investigate the impact of channel variation on the integer-forcing linear receiver and show it still retains an advantage over conventional linear receivers, despite the fact that the integer coefficients must remain fixed across the codeword duration.

The ergodic interference alignment scheme allows each user in a K-user interference channel to attain half its interference-free rate at any signal-to-noise ratio (SNR). However, this comes at the cost of extraordinarily long delays, since each channel matrix must be paired with a complementary matrix that can cancel out its off-diagonal terms. In this paper, we investigate the opposite approach. Rather than waiting for perfect matches, we simply try to pair together the available channel matrices to attain the highest possible sum rate. We show that this problem is closely connected to the problem of maximum weight matching, which allows us to efficiently evaluate the numerical performance of our scheme.

Consider a cellular network composed of several base stations with overlapping coverage areas. Conventional scheduling algorithms ensure that each base station hears only a single user over each orthogonal sub-channel, i.e., collisions are avoided. Recent work on compute-and-forward has demonstrated that it is possible for a receiver to decode a linear combination of interfering codewords. We examine how the adoption of the compute-and-forward technique affects the scheduling problem for cellular networks. Specifically, instead of avoiding collisions, the base stations can schedule collisions to obtain a set of linear combinations that can be solved for the original messages. For the special case of two base stations, we propose a simple scheduling algorithm that finds the minimal number of sub-channels needed for each user to successfully communicate one packet. For the general case, we formulate an integer program that can be solved using dynamic programming with pseudo-polynomial complexity with respect to the number of users.

We consider a Gaussian multiple-access channel where each user's message is identified with a vector of elements from a finite field, and the receiver's goal is to decode a linear combination of these finite field vectors. It is further assumed that each transmitter can causally observe the channel's output through a clean feedback link. We propose a novel coding scheme for this setup, which can be seen as an extension of the Cover-Leung scheme for the computation problem. This scheme is shown to achieve computation rates higher than the best known computation rates for the same scenario without feedback. In particular, for the symmetric two-user Gaussian multiple-access channel, the proposed scheme attains a symmetric computation rate greater than 1/2 log(3/4 + SNR).

Conventional scheduling algorithms assign users to orthogonal sub-channels in order to avoid collisions. However, recent physical-layer advances, such as the compute-and-forward technique, have demonstrated that it is possible to recover a linear combination of packets when a collision occurs. Recently, we proposed a collision scheduling algorithm that exploits this phenomenon to attain higher throughputs. Here, we argue that the complexity of this algorithm can be significantly reduced in the important special case where each cell only overlaps with a constant number of neighboring cells.

Consider a MIMO uplink channel with channel matrix H and a MIMO downlink channel with channel matrix H⊤. It is well-known that any rate tuple that is achievable on the uplink is also achievable on the downlink under the same total power constraint, i.e., there is an uplink-downlink duality relationship. In this paper, we consider the integer-forcing strategy, in which users steer the channel towards an integer-valued effective channel matrix so that the receiver(s) can decode integer-linear combinations of the transmitted codewords. Recent efforts have demonstrated the benefits of this strategy for uplink, downlink, and interference alignment scenarios. Here, we establish that uplink-downlink duality holds for integer-forcing. Specifically, in the uplink, L transmitters communicate over channel matrix H to an L-antenna receiver with target integer matrix A. In the downlink, an L-antenna transmitter communicates over channel matrix H⊤to L single-antenna receivers with target integer matrix A⊤. We show that any computation rate tuple that is achievable in the uplink is achievable for the same total power in the downlink and vice versa.

Consider a receiver that observes multiple interfering codewords. The compute-and-forward technique makes it possible for the receiver to directly decode linear combinations of the codewords. Previous work has focused on compute-and-forward for linear Gaussian networks. This paper explores the corresponding technique for discrete memoryless networks. As a by-product, this leads to a novel way of attaining non-trivial points on the dominant face of the capacity region of discrete memoryless multiple-access channels.

Interference alignment has emerged as a powerful tool in the analysis of multiuser networks. Despite considerable recent progress, the capacity region of the Gaussian K-user interference channel is still unknown in general, in part due to the challenges associated with alignment on the signal scale using lattice codes. This paper develops a new framework for lattice interference alignment, based on the compute-and-forward approach. Within this framework, each receiver decodes by first recovering two or more linear combinations of the transmitted codewords with integer-valued coefficients and then solving these linear combinations for its desired codeword. For the special case of symmetric channel gains, this framework is used to derive the approximate sum capacity of the Gaussian interference channel, up to an explicitly defined outage set of the channel gains. The key contributions are the capacity lower bounds for the weak through strong interference regimes, where each receiver should jointly decode its own codeword along with part of the interfering codewords. As part of the analysis, it is shown that decoding K linear combinations of the codewords can approach the sum capacity of the K-user Gaussian multiple-access channel up to a gap of no more than K/2 log K bits.

Linear receivers are often used to reduce the implementation complexity of multiple-antenna systems. In a traditional linear receiver architecture, the receive antennas are used to separate out the codewords sent by each transmit antenna, which can then be decoded individually. Although easy to implement, this approach can be highly suboptimal when the channel matrix is near singular. This paper develops a new linear receiver architecture that uses the receive antennas to create an effective channel matrix with integer-valued entries. Rather than attempting to recover transmitted codewords directly, the decoder recovers integer combinations of the codewords according to the entries of the effective channel matrix. The codewords are all generated using the same linear code, which guarantees that these integer combinations are themselves codewords. Provided that the effective channel is full rank, these integer combinations can then be digitally solved for the original codewords. This paper focuses on the special case where there is no coding across transmit antennas and no channel state information at the transmitter(s), which corresponds either to a multiuser uplink scenario or to single-user V-BLAST encoding. In this setting, the proposed integer-forcing linear receiver significantly outperforms conventional linear architectures such as the zero forcing and linear minimum mean-squared error receiver. In the high signal-to-noise ratio regime, the proposed receiver attains the optimal diversity-multiplexing tradeoff for the standard multiple-input multiple-output (MIMO) channel with no coding across transmit antennas. It is further shown that in an extended MIMO model with interference, the integer-forcing linear receiver achieves the optimal generalized degrees of freedom.

We study the three-user interference channel where each transmitter has local feedback of the signal from its targeted receiver. We show that in the important case where the channel coefficients are static, exact alignment can be achieved over two time slots using linear schemes. This is in contrast with the interference channel where no feedback is utilized, where it seems that either an infinite number of channel extensions or infinite precision is required for exact alignment. We also demonstrate, via simulations, that our scheme outperforms time-sharing even at finite SNR.

Consider a three-user time-varying Gaussian interference channel under uniform phase fading. Prior work on ergodic interference alignment has shown that each user can simultaneously achieve half its interference-free rate. In this paper, we combine ideas from ergodic alignment and compute-and-forward to characterize the symmetric ergodic capacity of this channel in the strong and very strong regimes to within a constant gap.

We study layered wireless networks in which destinations decode linear combinations of transmitted messages over a finite field. We propose amplify-and-compute, a simple but effective scheme in which sources encode their messages with lattice codes, relays employ amplify-and-forward relaying, and destinations decode incoming signals to integer combinations of lattice codewords. We focus on the two-user setting and show that, by carefully choosing relay amplification weights, it is possible to align the equivalent end-to-end channel to an arbitrary matrix of non-zero integers (up to a set of channel matrices of zero measure). Such a choice achieves a computation rate to within a gap to capacity that is independent of the SNR. Amplify-and-compute therefore achieves the maximum degrees of freedom while providing good performance at moderate SNR. Finally, we show that amplify-and-compute offers similar performance when applied to layered two-user interference networks.

In this paper, we propose a novel framework, integer-forcing interference alignment, that can simultaneously exploit both signal-space and signal-scale alignment. We consider receivers that can decode integer-linear combinations of desired and interfering streams and then solve for their desired symbols. This is possible by using appropriate lattice codes at the transmitters and can be applied to the class of wireless communication systems that use linear beamforming. At the core of our architecture lies the compute-and-forward framework, which we extend here to encompass asymmetric power allocations. We evaluate the performance of our scheme in the context of the three-user interference channel through simulation results.

Decision feedback equalization (DFE) has been used to improve energy efficiency and/or reduce error rate in communication links. We propose a novel circuit technique which applies DFE techniques to pass transistor logic (PTL)-based computational circuits to mitigate errors, and reduce energy per computation or improve performance. We also present an optimization framework for designing low energy equalized PTL circuits that meet target performance and error rate specifications. On average, for the same operating frequency and error rate, the equalized PTL design consumes between 15% and 30% lower energy per operation than PTL and static complementary logic, respectively.

Consider the following unequal error protection scenario. One special message, dubbed the “red alert” message, is required to have an extremely small probability of missed detection. The remainder of the messages must keep their average probability of error and probability of false alarm below a certain threshold. The goal then is to design a codebook that maximizes the error exponent of the red alert message while ensuring that the average probability of error and probability of false alarm go to zero as the blocklength goes to infinity. This red alert exponent has previously been characterized for discrete memoryless channels. This paper completely characterizes the optimal red alert exponent for additive white Gaussian noise channels with block power constraints.

Consider several source nodes communicating across a wireless network to a destination node with the help of several layers of relay nodes. Recent work by Avestimehr has approximated the capacity of this network up to an additive gap. The communication scheme achieving this capacity approximation is based on compress-and-forward, resulting in noise accumulation as the messages traverse the network. As a consequence, the approximation gap increases linearly with the network depth. This paper develops a computation alignment strategy that can approach the capacity of a class of layered, time-varying wireless relay networks up to an approximation gap that is independent of the network depth. This strategy is based on the compute-and-forward framework, which enables relays to decode deterministic functions of the transmitted messages. Alone, compute-and-forward is insufficient to approach the capacity as it incurs a penalty for approximating the wireless channel with complex-valued coefficients by a channel with integer coefficients. Here, this penalty is circumvented by carefully matching channel realizations across time slots to create integer-valued effective channels that are well suited to compute-and-forward. Unlike prior constant gap results, the approximation gap obtained in this paper also depends closely on the fading statistics, which are assumed to be i.i.d. Rayleigh.

We derive a new achievable sum rate for the symmetric Gaussian K-user interference channel. This sum rate is shown to be within a constant gap of the outer bound on the sum capacity of this channel for all values of interference level outside some outage set. The result is established through the use of lattice interference alignment. A new lattice-based extension to the Han-Kobayshi scheme is also introduced.

We derive an achievable rate region for the Gaussian K-user multiple-access channel (MAC) where all users transmit codewords from a chain of nested lattices. For any set of channel coefficients, this rate region contains points within a constant gap from the sum capacity boundary of the MAC. The main tool used is the recently proposed compute-and-forward framework. A new transformation of a MAC to a modulo-lattice multiple-input multiple-output (MIMO) channel is introduced based on this framework. Specifically, from one noisy linear combination of the transmitted signals the receiver attempts to decode K linearly independent equations with integer-valued coefficients. While the individual rates at which these equations can be decoded are highly sensitive to the exact channel gains, their sum is always within a constant gap from the sum capacity boundary of the MAC. The transformation is then utilized for establishing the desired rate region.

This paper develops a new communication strategy, ergodic interference alignment, for theK-user interference channel with time-varying fading. At any particular time, each receiver will see a superposition of the transmitted signals plus noise. The standard approach to such a scenario results in each transmitter-receiver pair achieving a rate proportional to 1/Kits interference-free ergodic capacity. However, given two well-chosen time indices, the channel coefficients from interfering users can be made to exactly cancel. By adding up these two observations, each receiver can obtain its desired signal without any interference. If the channel gains have independent, uniform phases, this technique allows each user to achieve at least 1/2 its interference-free ergodic capacity at any signal-to-noise ratio. Prior interference alignment techniques were only able to attain this performance as the signal-to-noise ratio tended to infinity. Extensions are given for the case where each receiver wants a message from more than one transmitter as well as the “X channel” case (with two receivers) where each transmitter has an independent message for each receiver. Finally, it is shown how to generalize this strategy beyond Gaussian channel models. For a class of finite field interference channels, this approach yields the ergodic capacity region.

The Compute-and-Forward approach has been proven to be very beneficial for communication over Gaussian networks. While the theoretical results are promising, it is still not completely understood how to best apply this scheme in practice. The objective of this work is to provide a low complexity scheme suitable for Compute-and-Forward. The scheme is based on utilizing linear codes over ℤqwhere q is not restricted to be prime and allows to achieve high transmission rates following Ungerboeck's set partitioning principle.

We consider the transmission of independent messages over a Gaussian relay network with interfering links. Using the compute-and-forward framework, relays can efficiently decode equations of the transmitted messages. The relays can then send their collected equations to the destination, which solves for its desired messages. Here, we study a special case of the inverse compute-and-forward problem: transmitting the equations to a single destination over a multiple-access channel. We observe that if the underlying messages have unequal rates, the set of possible values of an equation is constrained by the value of the other equations. We use this fact to improve the rate region for downloading equations. Interestingly, the rate region achieved over relay networks with interfering links using a combination of compute-and-forward and inverse compute-and-forward is larger than the best rate region achievable in the absence of interfering links. This verifies that interference may be used to beneficially “mix” messages over a wireless network.

We show that the recently proposed integer-forcing linear receiver provides an attractive approach to the problem of mitigating external interference in MIMO channels. The integer-forcing receiver proceeds by first decoding a set of full rank integer linear combinations of the data streams. The resulting full rank equations are then inverted to find the original data. By selecting equation coefficients in a direction that depends on both the interference space and the channel matrix, the impact of external interference can be effectively reduced. We show that this technique attains a non-trivial gain over traditional linear receivers. Furthermore, the integer-forcing linear receiver achieves the same generalized degrees of freedom for the M×M MIMO channel with K dimensional external interference as the joint decoder.

When two or more users in a wireless network transmit simultaneously, their electromagnetic signals are linearly superimposed on the channel. As a result, a receiver that is interested in one of these signals sees the others as unwanted interference. This property of the wireless medium is typically viewed as a hindrance to reliable communication over a network. However, using a recently developed coding strategy, interference can in fact be harnessed for network coding. In a wired network, (linear) network coding refers to each intermediate node taking its received packets, computing a linear combination over a finite field, and forwarding the outcome towards the destinations. Then, given an appropriate set of linear combinations, a destination can solve for its desired packets. For certain topologies, this strategy can attain significantly higher throughputs over routing-based strategies. Reliable physical layer network coding takes this idea one step further: using judiciously chosen linear error-correcting codes, intermediate nodes in a wireless network can directly recover linear combinations of the packets from the observed noisy superpositions of transmitted signals. Starting with some simple examples, this paper explores the core ideas behind this new technique and the possibilities it offers for communication over interference-limited wireless networks.

Interference is usually viewed as an obstacle to communication in wireless networks. This paper proposes a new strategy, compute-and-forward, that exploits interference to obtain significantly higher rates between users in a network. The key idea is that relays should decode linear functions of transmitted messages according to their observed channel coefficients rather than ignoring the interference as noise. After decoding these linear equations, the relays simply send them towards the destinations, which given enough equations, can recover their desired messages. The underlying codes are based on nested lattices whose algebraic structure ensures that integer combinations of codewords can be decoded reliably. Encoders map messages from a finite field to a lattice and decoders recover equations of lattice points which are then mapped back to equations over the finite field. This scheme is applicable even if the transmitters lack channel state information.

Linear receivers are often used to reduce the implementation complexity of multiple antenna systems. In a traditional linear receiver architecture, the receive antennas are used to separate out the codewords sent by each transmit antenna, which can then be decoded individually. Although easy to implement, this approach can be highly sub-optimal when the channel matrix is near singular. In this paper, we develop a new linear architecture that uses the receive antennas to create an effective channel matrix with integer-valued entries. Instead of attempting to recover a transmitted codeword directly, each decoder recovers a different integer combination of the codewords according to the effective channel matrix. If the effective channel is full rank, these linear equations can be digitally solved for the original codewords. By allowing the receiver to equalize the channel to any matrix with integer entries, this scheme can outperform traditional linear architectures such as decorrelators and MMSE receivers while maintaining a similar complexity. Furthermore, in the case where each transmit antenna encodes an independent data stream, the proposed receiver attains the optimal diversity multiplexing tradeoff.

We propose a new framework for MIMO decoding based on a recently developed technique for reliably conveying linear equations over wireless channels. Each transmit antenna sends an independent data stream using the same linear code. As a result, any integer combination of the codewords is itself a codeword. Each receive antenna observes a random complex-valued combination of the codewords according to the fading coefficients. We use a linear pre-processing step at the receiver to transform the effective channel into a (full-rank) integer matrix. A single stream decoder is then used to recover integer combinations of the codewords. These equations of codewords are then translated into equations of the transmitted data streams over a finite field which can be easily solved for the original data. We examine the performance of our scheme in terms of the probability of outage and show that significant gains are possible over standard linear architectures for both i.i.d. and correlated Rayleigh fading.

In this paper, we study a gossip algorithm for distributed averaging over a wireless sensor network. The usual assumption is that, through properly chosen codes, the physical layer is reduced to a set of reliable bit pipes for the distributed averaging algorithm. However, with a new channel coding technique, computation coding, we can exploit the interference property of the wireless medium for efficient averaging. This then provides a new abstraction for the physical layer: reliable linear equations instead of reliable bit pipes. The ldquoneighborhood gossiprdquo algorithm operates modularly on top of this abstraction. We will show that for certain regimes, such an approach can lead to energy savings that are exponential in the network size and time savings that are polynomial.

Consider a K-user interference channel with timevarying fading. At any particular time, each receiver will see a signal from most transmitters. The standard approach to such a scenario results in each transmitter-receiver pair achieving a rate proportional to 1/K the single user rate. However, given two well chosen time indices, the channel coefficients from interfering users can be made to exactly cancel. By adding up these two signals, the receiver can see an interference-free version of the desired transmission. We show that this technique allows each user to achieve at least half its interference-free ergodic capacity at any SNR. Prior work was only able to show that half the interference-free rate was achievable as the SNR tended to infinity. We examine a finite field channel model and a Gaussian channel model. In both cases, the achievable rate region has a simple description and, in the finite field case, we prove it is the ergodic capacity region.

In this paper, we demonstrate the advantage of the inherent algebraic structure of lattice codes, for the uplink channel of a cellular deployment. The out-of-cell interference is assumed to be symmetric, as in Wyner's model. We employ a new relaying technique, compute-and-forward, which allows cell-sites to decode equations of the transmitted bits by exploiting the channel interference. However, the standard compute-and-forward technique is penalized whenever the channel coefficients are non-integer. We develop a superposition strategy to mitigate this penalty. By using part of the power towards a private message, we can effectively modify the channel seen by compute-and-forward. We demonstrate that, in certain regimes, this mixed strategy significantly outperforms decode-and-forward, compress-and-forward, and ordinary compute-and-forward.

In many network communication scenarios, a relay in the network may only need to recover and retransmit an equation of the transmitted messages. In previous work, it has been shown that if each transmitter employs the same lattice code, the interference structure of the channel can be exploited to recover an equation much more efficiently than possible with standard multiple-access strategies. Here, we generalize this compute-and-forward framework to the multiple antenna setting. Our results show that it is often beneficial to use extra antennas at the receiver to rotate the channel coefficients towards the nearest integer vector instead of separating out the transmitted signals. We also demonstrate that in contrast to classical strategies, the multiplexing gain of compute-and-forward increases if the transmitters have channel state information. Finally, we apply our scheme to the two way relay network and observe performance gains over traditional strategies.

For a centralized encoder and decoder, a channel matrix is simply a set of linear equations that can be transformed into parallel channels. We develop a similar approach to multi-user networks: we view interference as creating linear equations of codewords and that a receiverpsilas goal is to collect a full rank set of such equations. Our new relaying technique, compute-and-forward, uses structured codes to reliably compute functions over channels. This allows the relays to efficiently recover a linear functions of codewords without recovering the individual codewords. Thus, our scheme can work with the structure of the interference while removing the effects of the noise at the relay. We apply our scheme to a Gaussian relay network with interference and achieve better rates than either compress-and-forward or decode-and-forward for certain regimes.

We consider the problem of computing the sum of independent Gaussian sources over a Gaussian multiple-access channel (MAC) with respect to a mean-squared error criterion. When the source and channel bandwidths are equal, the best separation-based solution to this problem performs exponentially worse in a distortion sense compared to the optimal solution: uncoded transmission. In this paper, we develop lattice codes for exploiting the structure of the Gaussian MAC when there are more channel uses than source symbols. We also demonstrate the usefulness of these codes in determining the multicast capacity of a simple AWGN network.

The problem of reliably reconstructing a function of sources over a multiple-access channel (MAC) is considered. It is shown that there is no source–channel separation theorem even when the individual sources are independent. Joint source–channel strategies are developed that are optimal when the structure of the channel probability transition matrix and the function are appropriately matched. Even when the channel and function are mismatched, these computation codes often outperform separation-based strategies. Achievable distortions are given for the distributed refinement of the sum of Gaussian sources over a Gaussian multiple-access channel with a joint source–channel lattice code. Finally, computation codes are used to determine the multicast capacity of finite-field multiple-access networks, thus linking them to network coding.

We study the problem of multicasting over a network of multiple-access channels (MACs). The separation-based solution to this problem is to reduce each MAC to a set of noiseless bit pipes via a channel code and then employ network coding. Sometimes, however, the physical-layer structure of the MAC can be exploited more advantageously. In many cases of interest, the MAC output is a (deterministic) function of its inputs, corrupted by noise. We develop structured codes to exploit the natural function of a MAC to reliably compute functions as part of a network code and show that in many scenarios of interest our scheme outperforms the separation-based solution. If each MAC can be written as a sum over some finite field plus noise, then our achievable rate coincides with the max-flow min-cut bound