# Information Theory

## New submissions

[ total of 32 entries: 1-32 ]
[ showing up to 2000 entries per page: fewer | more ]

### New submissions for Tue, 20 Mar 18

[1]
Title: Coding for Channels with SNR Variation: Spatial Coupling and Efficient Interleaving
Comments: 8 pages, Submitted to IEEE Transactions on Magnetics (TMAG)
Subjects: Information Theory (cs.IT)

In magnetic-recording systems, consecutive sections experience different signal to noise ratios (SNRs). To perform error correction over these systems, one approach is to use an individual block code for each section. However, a section affected by a lower SNR shows a weaker performance compared to a section affected by a higher SNR. A commonly used technique is to perform interleaving across blocks to alleviate negative effects of varying SNR. However, this scheme is typically costly to implement and does not result in the best performance. Spatially-coupled (SC) codes are a family of graph-based codes with capacity approaching performance and low latency decoding. An SC code is constructed by partitioning an underlying block code to several component matrices, and coupling copies of the component matrices together. The contribution of this paper is threefold. First, we present a new partitioning technique to efficiently construct SC codes with column weights 4 and 6. Second, we present an SC code construction for channels with SNR variation. Our SC code construction provides local error correction for each section by means of the underlying codes that cover one section each, and simultaneously, an added level of error correction by means of coupling among the underlying codes. Consequently, and because of the structure of SC codes, more reliable sections can help unreliable ones to achieve an improved performance. Third, we introduce a low-complexity interleaving scheme specific to SC codes that further improves their performance over channels with SNR variation. Our simulation results show that our SC codes outperform individual block codes by more than 1 and 2 orders of magnitudes in the error floor region compared to the block codes with and without regular interleaving, respectively. This improvement is more pronounced by increasing the memory and column weight.

[2]
Title: Frequency-Domain Decoupling for MIMO-GFDM Spatial Multiplexing
Subjects: Information Theory (cs.IT)

Generalized frequency division multiplexing (GFDM) is considered a non-orthogonal waveform and known to encounter difficulties when using in the spatial multiplexing mode of multiple-input-multiple-output (MIMO) scenario. In this paper, a class of GFDM prototype filters, under which the GFDM system is free from inter-subcarrier interference, is investigated, enabling frequency-domain decoupling in the processing at the GFDM receiver. An efficient MIMO-GFDM detection method based on depth-first sphere decoding is then proposed with such class of filters. Numerical results confirm a significant reduction in complexity, especially when the number of subcarriers is large, compared with existing methods presented in recent years.

[3]
Title: Optimizing Information Freshness in Wireless Networks under General Interference Constraints
Subjects: Information Theory (cs.IT); Networking and Internet Architecture (cs.NI)

Age of information (AoI) is a recently proposed metric for measuring information freshness. AoI measures the time that elapsed since the last received update was generated. We consider the problem of minimizing average and peak AoI in wireless networks under general interference constraints. When fresh information is always available for transmission, we show that a stationary scheduling policy is peak age optimal. We also prove that this policy achieves average age that is within a factor of two of the optimal average age. In the case where fresh information is not always available, and packet/information generation rate has to be controlled along with scheduling links for transmission, we prove an important separation principle: the optimal scheduling policy can be designed assuming fresh information, and independently, the packet generation rate control can be done by ignoring interference. Peak and average AoI for discrete time G/Ber/1 queue is analyzed for the first time, which may be of independent interest.

[4]
Title: Distributed Scheduling Algorithms for Optimizing Information Freshness in Wireless Networks
Subjects: Information Theory (cs.IT); Networking and Internet Architecture (cs.NI)

Age of Information (AoI), measures the time elapsed since the last received information packet was generated at the source. We consider the problem of AoI minimization for single-hop flows in a wireless network, under pairwise interference constraints and time varying channel. We consider simple, yet broad, class of distributed scheduling policies, in which a transmission is attempted over each link with a certain attempt probability. We obtain an interesting relation between the optimal attempt probability and the optimal AoI of the link, and its neighboring links. We then show that the optimal attempt probabilities can be computed by solving a convex optimization problem, which can be done distributively.

[5]
Title: Optimizing Age of Information in Wireless Networks with Perfect Channel State Information
Subjects: Information Theory (cs.IT); Networking and Internet Architecture (cs.NI)

Age of information (AoI), defined as the time elapsed since the last received update was generated, is a newly proposed metric to measure the timeliness of information updates in a network. We consider AoI minimization problem for a network with general interference constraints, and time varying channels. We propose two policies, namely, virtual-queue based policy and age-based policy when the channel state is available to the network scheduler at each time step. We prove that the virtual-queue based policy is nearly optimal, up to a constant additive factor, and the age-based policy is at-most factor 4 away from optimality. Comparing with our previous work, which derived age optimal policies when channel state information is not available to the scheduler, we demonstrate a 4 fold improvement in age due to the availability of channel state information.

[6]
Title: Variational Bayesian Inference of Line Spectral Estimation with Multiple Measurement Vectors
Subjects: Information Theory (cs.IT)

In this paper, the line spectral estimation (LSE) problem with multiple measurement vectors (MMVs) is studied utilizing the Bayesian methods. Motivated by the recently proposed variational line spectral estimation (VALSE) method, we extend it to deal with the MMVs setting, which is especially important in array signal processing. The VALSE method can automatically estimate the model order and nuisance parameters such as noise variance and weight variance. In addition, by approximating the probability density function (PDF) of the frequencies with the mixture of von Mises PDFs, closed-form update equation and the uncertainty degree of the estimates can be obtained. Interestingly, we find that the VALSE with MMVs can be viewed as applying the VALSE with single measurement vector (SMV) to each snapshot, and combining the intermediate data appropriately. Furthermore, the proposed prior distribution provides a good interpretation of tradeoff between grid and off-grid based methods. Finally, numerical results demonstrate the effectiveness of the VALSE method, compared to the state-of-the-art methods in the MMVs setting.

[7]
Subjects: Information Theory (cs.IT)

[8]
Title: Two new classes of quantum MDS codes
Subjects: Information Theory (cs.IT)

Let $p$ be a prime and let $q$ be a power of $p$. In this paper, by using generalized Reed-Solomon (GRS for short) codes and extended GRS codes, we construct two new classes of quantum maximum-distance- separable (MDS) codes with parameters $[[tq, tq-2d+2, d]]_{q}$ for any $1 \leq t \leq q, 2 \leq d \leq \lfloor \frac{tq+q-1}{q+1}\rfloor+1$, and $[[t(q+1)+2, t(q+1)-2d+4, d]]_{q}$ for any $1 \leq t \leq q-1, 2 \leq d \leq t+2$ with $(p,t,d) \neq (2, q-1, q)$. Our quantum codes have flexible parameters, and have minimum distances larger than $\frac{q}{2}+1$ when $t > \frac{q}{2}$. Furthermore, it turns out that our constructions generalize and improve some previous results.

[9]
Title: Experimental Verification of Rate Flexibility and Probabilistic Shaping by 4D Signaling
Comments: Presented at OFC'18, San Diego, CA, USA
Subjects: Information Theory (cs.IT)

The rate flexibility and probabilistic shaping gain of $4$-dimensional signaling is experimentally tested for short-reach, unrepeated transmission. A rate granularity of 0.5 bits/QAM symbol is achieved with a distribution matcher based on a simple look-up table.

[10]
Title: A Machine Learning Approach for Power Allocation in HetNets Considering QoS
Comments: 7 pages, 7 figures, IEEE ICC'18
Subjects: Information Theory (cs.IT)

There is an increase in usage of smaller cells or femtocells to improve performance and coverage of next-generation heterogeneous wireless networks (HetNets). However, the interference caused by femtocells to neighboring cells is a limiting performance factor in dense HetNets. This interference is being managed via distributed resource allocation methods. However, as the density of the network increases so does the complexity of such resource allocation methods. Yet, unplanned deployment of femtocells requires an adaptable and self-organizing algorithm to make HetNets viable. As such, we propose to use a machine learning approach based on Q-learning to solve the resource allocation problem in such complex networks. By defining each base station as an agent, a cellular network is modelled as a multi-agent network. Subsequently, cooperative Q-learning can be applied as an efficient approach to manage the resources of a multi-agent network. Furthermore, the proposed approach considers the quality of service (QoS) for each user and fairness in the network. In comparison with prior work, the proposed approach can bring more than a four-fold increase in the number of supported femtocells while using cooperative Q-learning to reduce resource allocation overhead.

[11]
Title: The Optimal Compression Rate of Variable-to-Fixed Length Source Coding with a Non-Vanishing Excess-Distortion Probability
Subjects: Information Theory (cs.IT)

We consider the variable-to-fixed length lossy source coding (VFSC) problem. The optimal compression rate of the average length of variable-to-fixed source coding, allowing a non-vanishing probability of excess-distortion $\varepsilon$, is shown to be equal to $(1-\varepsilon)R(D)$, where $R(D)$ is the rate-distortion function of the source. In comparison to the related results of Koga and Yamamoto as well as Kostina, Polyanskiy, and Verd\'{u} for fixed-to-variable length source coding, our results demonstrate an interesting feature that variable-to-fixed length source coding has the same first-order compression rate as fixed-to-variable length source coding.

[12]
Title: Centralized Caching with Unequal Cache Sizes
Subjects: Information Theory (cs.IT)

We address centralized caching problem with unequal cache sizes. We consider a system with a server of files connected through a shared error-free link to a group of cache-enabled users where one subgroup has a larger cache size than the rest. We investigate caching schemes with uncoded cache placement which minimize the load of worst-case demands over the shared link. We propose a caching scheme which improves upon existing schemes by either having a lower worst-case load, or decreasing the complexity of the scheme while performing within 1.1 multiplicative factor suggested by our numerical simulations.

[13]
Title: Symbol-Level Precoding Design for Max-Min SINR in Multiuser MISO Broadcast Channels
Comments: Submitted to SPAWC 2018, 7 pages, 2 figures
Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)

In this paper, we address the symbol level precoding (SLP) design problem under max-min SINR criterion in the downlink of multiuser multiple-input single-output (MISO) channels. First, we show that the distance preserving constructive interference regions (DPCIR) are always polyhedral angles (shifted pointed cones) for any given constellation point with unbounded decision region. Then we prove that any signal in a given unbounded DPCIR has a norm larger than the norm of the corresponding vertex if and only if the convex hull of the constellation contains the origin. Using these properties, we show that the power of the noiseless received signal lying on an unbounded DPCIR is an strictly increasing function of two parameters. This allows us to reformulate the originally non-convex SLP max-min SINR as a convex optimization problem. We discuss the loss due to our proposed convex reformulation and provide some simulation results.

[14]
Title: Synthesis of Logical Clifford Operators via Symplectic Geometry
Comments: Single column, main text: 20 pages, full length with appendices: 32 pages. Includes pseudo-codes for all algorithms. Part of this work has been submitted to the 2018 IEEE International Symposium on Information Theory
Subjects: Information Theory (cs.IT); Quantum Physics (quant-ph)

Quantum error-correcting codes can be used to protect qubits involved in quantum computation. This requires that logical operators acting on protected qubits be translated to physical operators (circuits) acting on physical quantum states. We propose a mathematical framework for synthesizing physical circuits that implement logical Clifford operators for stabilizer codes. Circuit synthesis is enabled by representing the desired physical Clifford operator in $\mathbb{C}^{N \times N}$ as a partial $2m \times 2m$ binary symplectic matrix, where $N = 2^m$. We state and prove two theorems that use symplectic transvections to efficiently enumerate all symplectic matrices that satisfy a system of linear equations. As an important corollary of these results, we prove that for an $[\![ m,m-k ]\!]$ stabilizer code every logical Clifford operator has $2^{k(k+1)/2}$ symplectic solutions. The desired physical circuits are then obtained by decomposing each solution as a product of elementary symplectic matrices. Our assembly of the possible physical realizations enables optimization over them with respect to a suitable metric. Furthermore, we show that any circuit that normalizes the stabilizer of the code can be transformed into a circuit that centralizes the stabilizer, while realizing the same logical operation. Our method of circuit synthesis can be applied to any stabilizer code, and this paper provides a proof of concept synthesis of universal Clifford gates for the $[\![ 6,4,2 ]\!]$ CSS code. We conclude with a classical coding-theoretic perspective for constructing logical Pauli operators for CSS codes. Since our circuit synthesis algorithm builds on the logical Pauli operators for the code, this paper provides a complete framework for constructing all logical Clifford operators for CSS codes. Programs implementing our algorithms can be found at https://github.com/nrenga/symplectic-arxiv18a.

[15]
Title: Radio bearing of sources with directional antennas in urban environment
Authors: Cezary Ziolkowski, Jan M. Kelner (Military University of Technology, Faculty of Electronics, Institute of Telecommunications, Warsaw, Poland)
Comments: 24 pages, 16 figures, 3 tables; Accepted in International Journal of Microwave and Wireless Technologies (from Cambridge University Press)
Subjects: Information Theory (cs.IT)

This paper focuses on assessing the limitations in the direction-finding process of radio sources with directional antennas in an urbanized environment, demonstrating how signal source antenna parameters, such as beamwidth and maximum radiation direction affect bearing accuracy in non-line-of-sight (NLOS) conditions. These evaluations are based on simulation studies, which use measurement-tested signal processing procedures. These procedures are based on a multi-elliptical propagation model, the geometry of which is related to the environment by the power delay profile or spectrum. The probability density function of the angle of arrival for different parameters of the transmitting antenna is the simulation result. This characteristic allows assessing the effect of the signal source antenna parameters on bearing error. The obtained results are the basis for practical correction bearing error and these show the possibility of improving the efficiency of the radio source location in the urbanized environment.

[16]
Title: Time-Domain Multi-Beam Selection and Its Performance Improvement for mmWave Systems
Comments: Accepted by IEEE International Conference on Communications (ICC), Kansas City, MO, USA, May 2018
Subjects: Information Theory (cs.IT)

Multi-beam selection is one of the crucial technologies in hybrid beamforming systems for frequency-selective fading channels. Addressing the problem in the frequency domain facilitates the procedure of acquiring observations for analog beam selection. However, it is difficult to improve the quality of the contaminated observations at low SNR. To this end, this paper uses an idea that the significant observations are sparse in the time domain to further enhance the quality of signals as well as the beam selection performance. By exploiting properties of channel impulse responses and circular convolutions in the time domain, we can reduce the size of a Toeplitz matrix in deconvolution to generate periodic true values of coupling coefficients plus random noise signals. An arithmetic mean of these signals yields refined observations with minor noise effects and provides more accurate sparse multipath delay information. As a result, only the refined observations associated with the estimated multipath delay indices have to be taken into account for the analog beam selection problem.

### Cross-lists for Tue, 20 Mar 18

[17]  arXiv:1803.06510 (cross-list from stat.ML) [pdf, other]
Title: Hidden Integrality of SDP Relaxation for Sub-Gaussian Mixture Models
Subjects: Machine Learning (stat.ML); Information Theory (cs.IT); Learning (cs.LG); Optimization and Control (math.OC); Statistics Theory (math.ST)

We consider the problem of estimating the discrete clustering structures under Sub-Gaussian Mixture Models. Our main results establish a hidden integrality property of a semidefinite programming (SDP) relaxation for this problem: while the optimal solutions to the SDP are not integer-valued in general, their estimation errors can be upper bounded in terms of the error of an idealized integer program. The error of the integer program, and hence that of the SDP, are further shown to decay exponentially in the signal-to-noise ratio. To the best of our knowledge, this is the first exponentially decaying error bound for convex relaxations of mixture models, and our results reveal the "global-to-local" mechanism that drives the performance of the SDP relaxation.
A corollary of our results shows that in certain regimes the SDP solutions are in fact integral and exact, improving on existing exact recovery results for convex relaxations. More generally, our results establish sufficient conditions for the SDP to correctly recover the cluster memberships of $(1-\delta)$ fraction of the points for any $\delta\in(0,1)$. As a special case, we show that under the $d$-dimensional Stochastic Ball Model, SDP achieves non-trivial (sometimes exact) recovery when the center separation is as small as $\sqrt{1/d}$, which complements previous exact recovery results that require constant separation.

[18]  arXiv:1803.06887 (cross-list from math.FA) [pdf, other]
Title: Lossless Analog Compression
Subjects: Functional Analysis (math.FA); Information Theory (cs.IT)

We establish the fundamental limits of lossless analog compression by considering the recovery of arbitrary m-dimensional real random vectors x from the noiseless linear measurements y=Ax with n x m measurement matrix A. Our theory is inspired by the groundbreaking work of Wu and Verdu (2010) on almost lossless analog compression, but applies to the nonasymptotic, i.e., fixed-m case, and considers zero error probability. Specifically, our achievability result states that, for almost all A, the random vector x can be recovered with zero error probability provided that n > K(x), where the description complexity K(x) is given by the infimum of the lower modified Minkowski dimensions over all support sets U of x. We then particularize this achievability result to the class of s-rectifiable random vectors as introduced in Koliander et al. (2016); these are random vectors of absolutely continuous distribution---with respect to the s-dimensional Hausdorff measure---supported on countable unions of s-dimensional differentiable manifolds. Countable unions of differentiable manifolds include essentially all signal models used in compressed sensing theory, in spectrum-blind sampling, and in the matrix completion problem. Specifically, we prove that, for almost all A, s-rectifiable random vectors x can be recovered with zero error probability from n>s linear measurements. This threshold is, however, found not to be tight as exemplified by the construction of an s-rectifiable random vector that can be recovered with zero error probability from n<s linear measurements. This leads us to the introduction of the new class of s-analytic random vectors, which admit a strong converse in the sense of n greater than or equal to s being necessary for recovery with probability of error smaller than one. The central conceptual tool in the development of our theory is geometric measure theory.

[19]  arXiv:1803.06982 (cross-list from quant-ph) [pdf, other]
Title: Quantifying coherence with quantum addition
Subjects: Quantum Physics (quant-ph); Information Theory (cs.IT)

Quantum addition channels have been recently introduced in the context of deriving entropic power inequalities for finite dimensional quantum systems. We prove a reverse entropy power equality which can be used to analytically prove an inequality conjectured recently for arbitrary dimension and arbitrary addition weight. We show that the relative entropic difference between the output of such a quantum additon channel and the corresponding classical mixture quantitatively captures the amount of coherence present in a quantum system. This new coherence measure admits an upper bound in terms of the relative entropy of coherence and is utilized to formulate a state-dependent uncertainty relation for two observables. Our results may provide deep insights to the origin of quantum coherence for mixed states that truly come from the discrepancy between quantum addition and the classical mixture.

[20]  arXiv:1803.07033 (cross-list from math.OC) [pdf, other]
Title: Natural gradient via optimal transport I
Subjects: Optimization and Control (math.OC); Information Theory (cs.IT)

We study a natural Wasserstein gradient flow on manifolds of probability distributions with discrete sample spaces. We derive the Riemannian structure for the probability simplex from the dynamical formulation of the Wasserstein distance on a weighted graph. We pull back the geometric structure to the parameter space of any given probability model, which allows us to define a natural gradient flow there. In contrast to the natural Fisher-Rao gradient, the natural Wasserstein gradient incorporates a ground metric on sample space. We discuss implementations following the forward and backward Euler methods. We illustrate the analysis on elementary exponential family examples.

### Replacements for Tue, 20 Mar 18

[21]  arXiv:1505.03898 (replaced) [pdf, ps, other]
Title: Pinball Loss Minimization for One-bit Compressive Sensing: Convex Models and Algorithms
Subjects: Information Theory (cs.IT); Numerical Analysis (math.NA); Optimization and Control (math.OC); Machine Learning (stat.ML)
[22]  arXiv:1601.05661 (replaced) [pdf, other]
Title: Distortion Bounds for Source Broadcast Problems
Comments: Revision after the first round of review
Subjects: Information Theory (cs.IT)
[23]  arXiv:1606.09494 (replaced) [pdf, other]
Title: Matched Metrics to the Binary Asymmetric Channels
Subjects: Information Theory (cs.IT)
[24]  arXiv:1611.10268 (replaced) [pdf, other]
Title: On Equivalence of Binary Asymmetric Channels regarding the Maximum Likelihood Decoding
Comments: The presentation was improved with respect to the previous version. New examples, applications and references were included
Subjects: Information Theory (cs.IT)
[25]  arXiv:1702.00131 (replaced) [pdf, ps, other]
Title: Optimal Caching in Content-Centric Mobile Hybrid Networks: A Variable Decoupling Approach
Comments: 19 pages, 7 figures, Part of this paper was presented at the IEEE International Symposium on Information Theory, Barcelona, Spain, July 2016
Subjects: Information Theory (cs.IT); Networking and Internet Architecture (cs.NI)
[26]  arXiv:1702.03062 (replaced) [pdf, other]
Title: Sparsity/Undersampling Tradeoffs in Anisotropic Undersampling, with Applications in MR Imaging/Spectroscopy
Subjects: Information Theory (cs.IT)
[27]  arXiv:1707.05797 (replaced) [pdf]
Title: Low-complexity implementation of convex optimization-based phase retrieval
Subjects: Information Theory (cs.IT); Optimization and Control (math.OC)
[28]  arXiv:1711.04449 (replaced) [pdf, other]
Title: A General Framework for Covariance Matrix Optimization in MIMO Systems
Comments: 16 Pages, 4 Figures, IEEE Communications
Subjects: Information Theory (cs.IT)
[29]  arXiv:1801.09665 (replaced) [pdf, ps, other]
Title: Cooperative repair: Constructions of optimal MDS codes for all admissible parameters
Comments: This version forms a substantive extension of Version 1. We provide a construction of MDS codes that support optimal cooperative repair for all admissible parameters. This resolves the general problem of constructing codes for cooperative repair with minimum repair bandwidth
Subjects: Information Theory (cs.IT)
[30]  arXiv:1803.04315 (replaced) [pdf, other]
Title: Power-Efficient Deployment of UAVs as Relays
Authors: Erdem Koyuncu
Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
[31]  arXiv:1803.05844 (replaced) [pdf, other]
Title: Joint Turbo Receiver for LDPC-Coded MIMO Systems Based on Semi-definite Relaxation
Authors: Kun Wang, Zhi Ding
Comments: 5 pages, 4 figures, conference
Subjects: Information Theory (cs.IT)
[32]  arXiv:1802.05856 (replaced) [pdf, other]
Title: Algorithmic Complexity and Reprogrammability of Chemical Structure Networks