Information Theory (math.IT)

  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.

Recent comments

gae Jul 26 2017 21:19 UTC

For those interested in the literature on teleportation simulation of quantum channels, a detailed and *comprehensive* review is provided in Supplementary Note 8 of https://images.nature.com/original/nature-assets/ncomms/2017/170426/ncomms15043/extref/ncomms15043-s1.pdf
The note describes well the t

...(continued)
Stefano Pirandola May 05 2017 05:45 UTC

Today I have seen on the arXiv the version 2 of this paper on quantum reading. I am sorry to say that this revision still misses to acknowledge important contributions from previous works, especially in relation to the methods on channel simulation and teleportation that are crucial for its claims.

...(continued)
Samad Khabbazi Oskouei Sep 05 2016 11:34 UTC

I think that we have missed the "semi-" at the conclusion. Because, the proof of the theorem 4.3 is based on the using universal semi-density matrix concept which is not computable. The semi-computability concept used here is like the Kolmogorov complexity which is not computable and so the Cubic co

...(continued)
Toby Cubitt Sep 01 2016 11:14 UTC

I could well be missing something. But as far as I could tell from a rather quick read through the paper, all they show is that the quantum capacity of a channel with computable matrix elements is given by the regularised coherent information optimised over input ensembles with computable matrix ele

...(continued)
Māris Ozols Aug 30 2016 17:52 UTC

Do I understand correctly that this paper claims to show that quantum capacity is computable?

> After defining the algorithmic quantum capacity we have proved that it
> equals the standard one. Furthermore we have shown that it is
> computable.

Richard Kueng Jul 28 2015 07:01 UTC

fyi: our quantum implications are presented in Subsection 2.2 (pp 7-9).

Marco Tomamichel May 31 2015 22:07 UTC

Thanks for the comment! This is a good idea, I will do that in the next arXiv version.

Patrick Hayden May 28 2015 17:31 UTC

Wonderful! I've been waiting for a book like this for a while now! Thanks, Marco.

I do have one trivial comment from a 30 second preliminary scan, though: please consider typesetting the proofs with a font size matching the main text. If us readers are already squinting hard trying to understand

...(continued)
Marco Tomamichel Apr 02 2015 03:21 UTC

This is a preliminary version and I am happy to incorporate feedback I receive in the coming month. Any comments are welcome.