# arXiv Information Theory

Computer Science -- Information Theory (cs.IT) updates on the arXiv.org e-print archive
Updated: hace 7 horas 51 mins

### Approximate Gradient Coding via Sparse Random Graphs. (arXiv:1711.06771v1 [stat.ML])

7 horas 51 mins ago

Distributed algorithms are often beset by the straggler effect, where the slowest compute nodes in the system dictate the overall running time. Coding-theoretic techniques have been recently proposed to mitigate stragglers via algorithmic redundancy. Prior work in coded computation and gradient coding has mainly focused on exact recovery of the desired output. However, slightly inexact solutions can be acceptable in applications that are robust to noise, such as model training via gradient-based algorithms. In this work, we present computationally simple gradient codes based on sparse graphs that guarantee fast and approximately accurate distributed computation. We demonstrate that sacrificing a small amount of accuracy can significantly increase algorithmic robustness to stragglers.

Categorías: research

### Exact alignment recovery for correlated Erdos Renyi graphs. (arXiv:1711.06783v1 [cs.IT])

7 horas 51 mins ago

We consider the problem of perfectly recovering the vertex correspondence between two correlated \ER (ER) graphs on the same vertex set. The correspondence between the vertices can be obscured by randomly permuting the vertex labels of one of the graphs. We determine the information-theoretic threshold for exact recovery, i.e. the conditions under which the entire vertex correspondence can be correctly recovered given unbounded computational resources.

Categorías: research

### Random Access in Massive MIMO by Exploiting Timing Offsets and Excess Antennas. (arXiv:1711.06830v1 [eess.SP])

7 horas 51 mins ago

Massive MIMO systems, where base stations are equipped with hundreds of antennas, are an attractive way to handle the rapid growth of data traffic. As the number of user equipments (UEs) increases, the initial access and handover in contemporary networks will be flooded by user collisions. In this paper, a random access protocol is proposed that resolves collisions and performs timing estimation by simply utilizing the large number of antennas envisioned in Massive MIMO networks. UEs entering the network perform spreading in both time and frequency domains and their timing offsets are estimated at the base station in closed-form using a subspace decomposition approach. This information is used to compute channel estimates that are subsequently employed by the base station to communicate with the detected UEs. The favorable propagation conditions of Massive MIMO suppress interference among UEs whereas the inherent timing misalignments improve the detection capabilities of the protocol. Numerical results are used to validate the performance of the proposed procedure in cellular networks under uncorrelated and correlated fading channels. With $10^4$ UEs that may simultaneously become active in a given random block with probability $1\%$, it turns out that the proposed procedure can successfully detect a relatively high number of UEs, compared to the available resources (i.e., number of codes in time- and frequency-domains), while providing reliable timing estimates.

Categorías: research

### Joint User Scheduling and Beam Selection Optimization for Beam-Based Massive MIMO Downlinks. (arXiv:1711.06915v1 [cs.IT])

7 horas 51 mins ago

In beam-based massive multiple-input multiple-output systems, signals are processed spatially in the radio-frequency (RF) front-end and thereby the number of RF chains can be reduced to save hardware cost, power consumptions and pilot overhead. Most existing work focuses on how to select, or design analog beams to achieve performance close to full digital systems. However, since beams are strongly correlated (directed) to certain users, the selection of beams and scheduling of users should be jointly considered. In this paper, we formulate the joint user scheduling and beam selection problem based on the Lyapunov-drift optimization framework and obtain the optimal scheduling policy in a closed-form. For reduced overhead and computational cost, the proposed scheduling schemes are based only upon statistical channel state information. Towards this end, asymptotic expressions of the downlink broadcast channel capacity are derived. To address the weighted sum rate maximization problem in the Lyapunov optimization, an algorithm based on block coordinated update is proposed and proved to converge to the optimum of the relaxed problem. To further reduce the complexity, an incremental greedy scheduling algorithm is also proposed, whose performance is proved to be bounded within a constant multiplicative factor. Simulation results based on widely-used spatial channel models are given. It is shown that the proposed schemes are close to optimal, and outperform several state-of-the-art schemes.

Categorías: research

### Enhanced Group Sparse Beamforming for Green Cloud-RAN: A Random Matrix Approach. (arXiv:1711.06983v1 [cs.IT])

7 horas 51 mins ago

Group sparse beamforming is a general framework to minimize the network power consumption for cloud radio access networks (Cloud-RANs), which, however, suffers high computational complexity. In particular, a complex optimization problem needs to be solved to obtain the remote radio head (RRH) ordering criterion in each transmission block, which will help to determine the active RRHs and the associated fronthaul links. In this paper, we propose innovative approaches to reduce the complexity of this key step in group sparse beamforming. Specifically, we first develop a smoothed $\ell_p$-minimization approach with the iterative reweighted-$\ell_2$ algorithm to return a Karush-Kuhn-Tucker (KKT) point solution, as well as enhancing the capability of inducing group sparsity in the beamforming vectors. By leveraging the Lagrangian duality theory, we obtain closed-form solutions at each iteration to reduce the computational complexity. The well-structured solutions provide the opportunities to apply the large-dimensional random matrix theory to derive deterministic approximations for the RRH ordering criterion. Such an approach helps to guide the RRH selection only based on the statistical channel state information (CSI), which does not require frequent update, thereby significantly reducing the computation overhead. Simulation results shall demonstrate the performance gains of the proposed $\ell_p$-minimization approach, as well as the effectiveness of the large system analysis based framework for computing RRH ordering criterion.

Categorías: research

### On the Stability of a N-class Aloha Network. (arXiv:1711.07116v1 [cs.IT])

7 horas 51 mins ago

Necessary and sufficient conditions are established for the stability of a high-mobility N-class Aloha network, where the position of the sources follows a Poisson point process, each source has an infinity capacity buffer, packets arrive according to a Bernoulli distribution and the link distance between source and destination follows a Rayleigh distribution. It is also derived simple formulas for the stationary packet success probability and mean delay.

Categorías: research

### Optimal binary linear locally repairable codes with disjoint repair groups. (arXiv:1711.07138v1 [cs.IT])

7 horas 51 mins ago

In recent years, several classes of codes are introduced to provide some fault-tolerance and guarantee system reliability in distributed storage systems, among which locally repairable codes (LRCs for short) play an important role. However, most known constructions are over large fields with sizes close to the code length, which lead to the systems computationally expensive. Due to this, binary LRCs are of interest in practice. In this paper, we focus on binary linear LRCs with disjoint repair groups. We first derive an explicit bound for the dimension k of such codes, which can be served as a generalization of the bounds given in [11, 36, 37]. We also give several new constructions of binary LRCs with minimum distance $d = 6$ based on weakly independent sets and partial spreads, which are optimal with respect to our newly obtained bound. In particular, for locality $r\in \{2,3\}$ and minimum distance $d = 6$, we obtain the desired optimal binary linear LRCs with disjoint repair groups for almost all parameters.

Categorías: research

### On the Feasibility of Interference Alignment in Compounded MIMO Broadcast Channels with Antenna Correlation and Mixed User Classes. (arXiv:1711.07175v1 [cs.IT])

7 horas 51 mins ago

This paper presents a generalized closed-form beamforming technique that can achieve the maximum degrees of freedom in compounded multiple-input multiple-output (MIMO) broadcast channels with mixed classes of multiple-antenna users. The contribution is firstly described within the context of a three-cell network and later extended to the general multi-cell scenario where we also show how to determine the conditions required to align the interference in a subspace that is orthogonal to the one reserved for the desired signals. This is then followed by an analysis of the impact of antenna correlation for different channel state information acquisition models. The proposed scheme is examined under both conventional and Large-scale MIMO systems. It will be shown that the proposed technique enables networks with any combination of user classes to achieve superior performance even under significant antenna correlation, particularly in the case of the Large-scale MIMO systems.

Categorías: research

### Method to Design UF-OFDM Filter and its Analysis. (arXiv:1711.07197v1 [cs.IT])

7 horas 51 mins ago

Orthogonal Frequency Division Multiplexing (OFDM) systems have been widely used as a communication system. In OFDM systems, there are two main problems. One of them is that OFDM signals have high Peak-to-Average Power Ratio (PAPR). The other problem is that OFDM signals have large side-lobes. In particular, to reduce side-lobes, Universal-Filtered OFDM (UF-OFDM) systems have been proposed. In this paper, we show criteria for designing filters for UF-OFDM systems and a method to obtain the filter as a solution of an optimization problem. Further, we evaluate PAPR with UF-OFDM systems. Our filters have smaller side-lobes and lower Bit Error Rate than the Dolph-Chebyshev filter. However, the PAPR for signals with our filters and the Dolph-Chebyshev filter are higher PAPR than those with conventional OFDM signals.

Categorías: research

### List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians. (arXiv:1711.07211v1 [cs.DS])

7 horas 51 mins ago

We study the problem of list-decodable Gaussian mean estimation and the related problem of learning mixtures of separated spherical Gaussians. We develop a set of techniques that yield new efficient algorithms with significantly improved guarantees for these problems.

{\bf List-Decodable Mean Estimation.} Fix any $d \in \mathbb{Z}_+$ and $0< \alpha <1/2$. We design an algorithm with runtime $O (\mathrm{poly}(n/\alpha)^{d})$ that outputs a list of $O(1/\alpha)$ many candidate vectors such that with high probability one of the candidates is within $\ell_2$-distance $O(\alpha^{-1/(2d)})$ from the true mean. The only previous algorithm for this problem achieved error $\tilde O(\alpha^{-1/2})$ under second moment conditions. For $d = O(1/\epsilon)$, our algorithm runs in polynomial time and achieves error $O(\alpha^{\epsilon})$. We also give a Statistical Query lower bound suggesting that the complexity of our algorithm is qualitatively close to best possible.

{\bf Learning Mixtures of Spherical Gaussians.} We give a learning algorithm for mixtures of spherical Gaussians that succeeds under significantly weaker separation assumptions compared to prior work. For the prototypical case of a uniform mixture of $k$ identity covariance Gaussians we obtain: For any $\epsilon>0$, if the pairwise separation between the means is at least $\Omega(k^{\epsilon}+\sqrt{\log(1/\delta)})$, our algorithm learns the unknown parameters within accuracy $\delta$ with sample complexity and running time $\mathrm{poly} (n, 1/\delta, (k/\epsilon)^{1/\epsilon})$. The previously best known polynomial time algorithm required separation at least $k^{1/4} \mathrm{polylog}(k/\delta)$.

Our main technical contribution is a new technique, using degree-$d$ multivariate polynomials, to remove outliers from high-dimensional datasets where the majority of the points are corrupted.

Categorías: research

### Evaluating the Performance of eMTC and NB-IoT for Smart City Applications. (arXiv:1711.07268v1 [cs.IT])

7 horas 51 mins ago

Low power wide area network (LPWAN) is a wireless telecommunication network that is designed for interconnecting devices with low bitrate focusing on long range and power efficiency. In this paper, we study two recent technologies built from existing Long-Term Evolution (LTE) functionalities: Enhanced machine type communications (eMTC) and Narrow band internet of things (NB-IoT). These technologies are designed to coexist with existing LTE infrastructure, spectrum, and devices. We first briefly introduce both systems and then compare their performance in terms of energy consumption, latency and scalability. We introduce a model for calculating the energy consumption and study the effect of clock drift and propose a method to overcome it. We also propose a model for analytically evaluating the latency and the maximum number of devices in a network. Furthermore, we implement the main functionality of both technologies and simulate the end-to-end latency and maximum number of devices in a discrete-event network simulator NS-3. Numerical results show that 8 years battery life time can be achieved by both technologies in a poor coverage scenario and that depending on the coverage conditions and data length, one technology consumes less energy than the other. The results also show that eMTC can serve more devices in a network than NB-IoT, while providing a latency that is 10 times lower.

Categorías: research

### Backscatter Communications for the Internet of Things: A Stochastic Geometry Approach. (arXiv:1711.07277v1 [cs.IT])

7 horas 51 mins ago

Powering the massive number of small computing devices in the Internet of Things (IoT) is a major challenge because replacing their batteries or powering them with wires is very expensive and impractical. A viable option to enable a perpetual network operation is through the use of far-field Wireless Power Transfer (WPT). We study a large network architecture that uses a combination of WPT and backscatter communication. The network consists of power beacons (PBs) and passive backscatter nodes (BNs), and their locations are modeled as points of independent Poisson point processes (PPPs). The PBs transmit a sinusoidal continuous wave (CW) and the BNs reflect back a portion of this signal while harvesting the remaining part. A BN harvests energy from multiple nearby PBs and modulates its information bits on the composite CW through backscatter modulation. The analysis poses real challenges due to the double fading channel, and its dependence on the PPPs of both BNs and PBs. With the help of stochastic geometry, we derive the coverage probability and the capacity of the network in tractable and easily computable expressions. These expressions depend on the density of both PB and BN, both forward and backward path loss exponents, transmit power of the PB, backscattering efficiency, and number of PBs in a harvesting region. We observe that the coverage probability decreases with an increase in the density of the BNs, while the capacity of the network improves. We compare the performance of this network with a regular powered network in which the BNs have a reliable power source and show that for certain parameters the coverage of the former network approaches that of the regular powered network.

Categorías: research

### Performance of In-band Transmission of System Information in Massive MIMO Systems. (arXiv:1711.07307v1 [cs.IT])

7 horas 51 mins ago

We consider transmission of system information in massive MIMO. This information needs to be reliably delivered to inactive users in the cell without any channel state information at the base station. Downlink transmission entails the use of downlink pilots and a special type of precoding that aims to reduce the dimension of the downlink channel and the pilot overhead, which would otherwise scale with the number of base station antennas. We consider a scenario in which the base station transmits over a small number of coherence intervals, providing little time/frequency diversity. The system information is transmitted with orthogonal space-time block codes to increase reliability and performance is measured using outage rates. Several different codes are compared, both for spatially correlated and uncorrelated channels and for varying amount of time/frequency diversity. We show that a massive MIMO base station can outperform a single-antenna base station in all considered scenarios.

Categorías: research

### On DNA Codes using the Ring Z4 + wZ4. (arXiv:1711.07324v1 [cs.IT])

7 horas 51 mins ago

In this work, we study the DNA codes from the ring R = Z4 + wZ4, where w^2 = 2+2w with 16 elements. We establish a one to one correspondence between the elements of the ring R and all the DNA codewords of length 2 by defining a distance preserving Gau map phi. Using this map, we give several new classes of the DNA codes which satisfies reverse and reverse complement constraints. Some of the constructed DNA codes are optimal.

Categorías: research

### On the Ergodic Rate of OFDMA Cognitive Radios under Imperfect Cross-Link Information. (arXiv:1711.07371v1 [cs.IT])

7 horas 51 mins ago

The ergodic rate performance and limits of orthogonal frequency-division multiple access (OFDMA) cognitive radios (CRs) is studied under imperfect cross-link knowledge. We propose a novel stochastic interference management and exploitation technique to mitigate and control the imposed interference by CRs on licensed users in underlay spectrum sharing. The optimum downlink channel-adaptive resource allocation (RA) algorithm is designed to maximize the CRs functionality subject to the satisfying average transmit and probabilistic peak interference power constraints. An expression of the cumulative density function (cdf) of CRs' received signal-to-interference-plus-noise ratio (SINR) is developed to evaluate the resultant ergodic rate. Simulation studies are conducted to examine the proposed RA algorithm and investigate the impact of parameters uncertainty on the overall system performance.

Categorías: research

### Adaptive M-QAM for Indoor Wireless Environments : Rate & Power Adaptation. (arXiv:1711.07386v1 [cs.IT])

7 horas 51 mins ago

This letter presents a detailed study for indoor wireless environments, where transmit power, rate and target bit error rate (BER) are varied to increase spectral efficiency. The study is conducted for the recently proposed joint fading and two-path shadowing (JFTS) channel model, which is shown to be accurate for modeling non-Gaussian indoor WLAN environments. Analysis is done for both average and instantaneous BER constraints without channel coding, where only a discrete finite set of constellations is available. Numerical results show that, for a JFTS channel i) varying only the transmission rate (modulation constellation size) achieves more improvement in spectral efficiency compared to varying transmit power only, and ii) varying rate and/or power subject to instantaneous BER (IBER) constraint offers better performance than when subject to average BER (A-BER) constraint.

Categorías: research

### Matrix Factorization for Nonparametric Multi-source Localization Exploiting Unimodal Properties. (arXiv:1711.07457v1 [cs.IT])

7 horas 51 mins ago

Herein, the problem of simultaneous localization of multiple sources given a number of energy samples at different locations is examined. The strategies do not require knowledge of the signal propagation models, nor do they exploit the spatial signatures of the source. A nonparametric source localization framework based on a matrix observation model is developed. It is shown that the source location can be estimated by localizing the peaks of a pair of location signature vectors extracted from the incomplete energy observation matrix. A robust peak localization algorithm is developed and shown to decrease the source localization mean squared error (MSE) faster than O(1/M^1.5) with M samples. To extract the source signature vectors from a matrix with mixed energy from multiple sources, a unimodal-constrained matrix factorization (UMF) problem is formulated, and two rotation techniques are developed to solve the UMF efficiently. Our numerical experiments demonstrate that the proposed scheme achieves similar performance as the kernel regression baseline using only 1/5 energy measurement samples in detecting a single source, and the performance gain is more significant in the cases of detecting multiple sources.

Categorías: research

### Modeling and Energy Optimization of LDPC Decoder Circuits with Timing Violations. (arXiv:1503.03880v5 [cs.IT] UPDATED)

7 horas 51 mins ago

This paper proposes a "quasi-synchronous" design approach for signal processing circuits, in which timing violations are permitted, but without the need for a hardware compensation mechanism. The case of a low-density parity-check (LDPC) decoder is studied, and a method for accurately modeling the effect of timing violations at a high level of abstraction is presented. The error-correction performance of code ensembles is then evaluated using density evolution while taking into account the effect of timing faults. Following this, several quasi-synchronous LDPC decoder circuits based on the offset min-sum algorithm are optimized, providing a 23%-40% reduction in energy consumption or energy-delay product, while achieving the same performance and occupying the same area as conventional synchronous circuits.

Categorías: research

### Strong Data Processing Inequalities for Input Constrained Additive Noise Channels. (arXiv:1512.06429v2 [cs.IT] UPDATED)

7 horas 51 mins ago

This paper quantifies the intuitive observation that adding noise reduces available information by means of non-linear strong data processing inequalities. Consider the random variables $W\to X\to Y$ forming a Markov chain, where $Y=X+Z$ with $X$ and $Z$ real-valued, independent and $X$ bounded in $L_p$-norm. It is shown that $I(W;Y) \le F_I(I(W;X))$ with $F_I(t)<t$ whenever $t>0$, if and only if $Z$ has a density whose support is not disjoint from any translate of itself. A related question is to characterize for what couplings $(W,X)$ the mutual information $I(W;Y)$ is close to maximum possible. To that end we show that in order to saturate the channel, i.e. for $I(W;Y)$ to approach capacity, it is mandatory that $I(W;X)\to\infty$ (under suitable conditions on the channel). A key ingredient for this result is a deconvolution lemma which shows that post-convolution total variation distance bounds the pre-convolution Kolmogorov-Smirnov distance. Explicit bounds are provided for the special case of the additive Gaussian noise channel with quadratic cost constraint. These bounds are shown to be order-optimal. For this case simplified proofs are provided leveraging Gaussian-specific tools such as the connection between information and estimation (I-MMSE) and Talagrand's information-transportation inequality.

Categorías: research

### Combination of LMS Adaptive Filters with Coefficients Feedback. (arXiv:1608.03248v2 [math.OC] UPDATED)

7 horas 51 mins ago

Parallel combinations of adaptive filters have been effectively used to improve the performance of adaptive algorithms and address well-known trade-offs, such as convergence rate vs. steady-state error. Nevertheless, typical combinations suffer from a convergence stagnation issue due to the fact that the component filters run independently. Solutions to this issue usually involve conditional transfers of coefficients between filters, which although effective, are hard to generalize to combinations with more filters or when there is no clearly faster adaptive filter. In this work, a more natural solution is proposed by cyclically feeding back the combined coefficient vector to all component filters. Besides coping with convergence stagnation, this new topology improves tracking and supervisor stability, and bridges an important conceptual gap between combinations of adaptive filters and variable step size schemes. We analyze the steady-state, tracking, and transient performance of this topology for LMS component filters and supervisors with generic activation functions. Numerical examples are used to illustrate how coefficients feedback can improve the performance of parallel combinations at a small computational overhead.

Categorías: research