Topic overview

Information Theory

Map preview

Topic at a glance

6710works

10593authors indexed

preprint2015arXiv

Skew cyclic codes over $\mathbb{F}_{q}+v\mathbb{F}_{q}+v^{2}\mathbb{F}_{q}$

In this article, we study skew cyclic codes over ring $R=\mathbb{F}_{q}+v\mathbb{F}_{q}+v^{2}\mathbb{F}_{q}$ , where $q=p^{m}$ , $p$ is an odd prime and $v^{3}=v$ . We describe generator polynomials of skew cyclic codes over this ring and investigate the structural properties of skew cyclic codes over $R$ by a decomposition theorem. We also describe the generator polynomials of the duals of skew cyclic codes. Moreover, the idempotent generators of skew cyclic codes over $\mathbb{F}_{q}$ and $R$ are considered.

preprint2017arXiv

On exact and optimal recovering of missing values for sequences

The paper studies recoverability of missing values for sequences in a pathwise setting without probabilistic assumptions. This setting is oriented on a situation where the underlying sequence is considered as a sole sequence rather than a member of an ensemble with known statistical properties. Sufficient conditions of recoverability are obtained; it is shown that sequences are recoverable if there is a certain degree of degeneracy of the Z-transforms. We found that, in some cases, this degree can be measured as the number of the derivatives of Z-transform vanishing at a point. For processes with non-degenerate Z-transform, an optimal recovering based on the projection on a set of recoverable sequences is suggested. Some robustness of the solution with respect to noise contamination and truncation is established.

preprint2016arXiv

Phase diagram of matrix compressed sensing

In the problem of matrix compressed sensing we aim to recover a low-rank matrix from few of its element-wise linear projections. In this contribution we analyze the asymptotic performance of a Bayes-optimal inference procedure for a model where the matrix to be recovered is a product of random matrices. The results that we obtain using the replica method describe the state evolution of the recently introduced P-BiG-AMP algorithm. We show the existence of different types of phase transitions, their implications for the solvability of the problem, and we compare the results of the theoretical analysis to the performance reached by P-BiG-AMP. Remarkably the asymptotic replica equations for matrix compressed sensing are the same as those for a related but formally different problem of matrix factorization.

preprint2017arXiv

Discrete Lossy Gray-Wyner Revisited: Second-Order Asymptotics, Large and Moderate Deviations

In this paper, we revisit the discrete lossy Gray-Wyner problem. In particular, we derive its optimal second-order coding rate region, its error exponent (reliability function) and its moderate deviations constant under mild conditions on the source. To obtain the second-order asymptotics, we extend some ideas from Watanabe's work (2015). In particular, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú (2012). The converse part uses a perturbation argument by Gu and Effros (2009) in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses two novel elements: (i) a generalization of various type covering lemmas; and (ii) the uniform continuity of the conditional rate-distortion function in both the source (joint) distribution and the distortion level. To obtain the error exponent, for the achievability part, we use the same generalized type covering lemma and for the converse, we use the strong converse together with a change-of-measure technique. Finally, to obtain the moderate deviations constant, we apply the moderate deviation

preprint2017arXiv

Interference Minimization in 5G Heterogeneous Networks

In this paper, we focus on one of the representative 5G network scenarios, namely multi-tier heterogeneous cellular networks. User association is investigated in order to reduce the down-link co-channel interference. Firstly, in order to analyze the multi-tier heterogeneous cellular networks where the base stations in different tiers usually adopt different transmission powers, we propose a Transmission Power Normalization Model (TPNM), which is able to convert a multi-tier cellular network into a single-tier network, such that all base stations have the same normalized transmission power. Then using TPNM, the signal and interference received at any point in the complex multi-tier environment can be analyzed by considering the same point in the equivalent single-tier cellular network model, thus significantly simplifying the analysis. On this basis, we propose a new user association scheme in heterogeneous cellular networks, where the base station that leads to the smallest interference to other co-channel mobile stations is chosen from a set of candidate base stations that satisfy the quality-of-service (QoS) constraint for an intended mobile station. Numerical results show that t

preprint2017arXiv

Entropy and Source Coding for Integer-Dimensional Singular Random Variables

Entropy and differential entropy are important quantities in information theory. A tractable extension to singular random variables-which are neither discrete nor continuous-has not been available so far. Here, we present such an extension for the practically relevant class of integer-dimensional singular random variables. The proposed entropy definition contains the entropy of discrete random variables and the differential entropy of continuous random variables as special cases. We show that it transforms in a natural manner under Lipschitz functions, and that it is invariant under unitary transformations. We define joint entropy and conditional entropy for integer-dimensional singular random variables, and we show that the proposed entropy conveys useful expressions of the mutual information. As first applications of our entropy definition, we present a result on the minimal expected codeword length of quantized integer-dimensional singular sources and a Shannon lower bound for integer-dimensional singular sources.

preprint2016arXiv

The $(n,m,k,λ)$ -Strong External Difference Family with $m \geq 5$ Exists

The notion of strong external difference family (SEDF) in a finite abelian group $(G,+)$ is raised by M. B. Paterson and D. R. Stinson [5] in 2016 and motivated by its application in communication theory to construct $R$ -optimal regular algebraic manipulation detection code. A series of $(n,m,k,λ)$ -SEDF's have been constructed in [5, 4, 2, 1] with $m=2$ . In this note we present an example of (243, 11, 22, 20)-SEDF in finite field $\mathbb{F}_q$ $(q=3^5=243).$ This is an answer for the following problem raised in [5] and continuously asked in [4, 2, 1]: if there exists an $(n,m,k,λ)$ -SEDF for $m\geq 5$ .

preprint2017arXiv

Information-theoretic lower bounds for distributed function computation

We derive information-theoretic converses (i.e., lower bounds) for the minimum time required by any algorithm for distributed function computation over a network of point-to-point channels with finite capacity, where each node of the network initially has a random observation and aims to compute a common function of all observations to a given accuracy with a given confidence by exchanging messages with its neighbors. We obtain the lower bounds on computation time by examining the conditional mutual information between the actual function value and its estimate at an arbitrary node, given the observations in an arbitrary subset of nodes containing that node. The main contributions include: 1) A lower bound on the conditional mutual information via so-called small ball probabilities, which captures the dependence of the computation time on the joint distribution of the observations at the nodes, the structure of the function, and the accuracy requirement. For linear functions, the small ball probability can be expressed by Lévy concentration functions of sums of independent random variables, for which tight estimates are available that lead to strict improvements over existing lower

preprint2016arXiv

Strong converse rates for quantum communication

We revisit a fundamental open problem in quantum information theory, namely whether it is possible to transmit quantum information at a rate exceeding the channel capacity if we allow for a non-vanishing probability of decoding error. Here we establish that the Rains information of any quantum channel is a strong converse rate for quantum communication: For any sequence of codes with rate exceeding the Rains information of the channel, we show that the fidelity vanishes exponentially fast as the number of channel uses increases. This remains true even if we consider codes that perform classical post-processing on the transmitted quantum data. As an application of this result, for generalized dephasing channels we show that the Rains information is also achievable, and thereby establish the strong converse property for quantum communication over such channels. Thus we conclusively settle the strong converse question for a class of quantum channels that have a non-trivial quantum capacity.

preprint2017arXiv

Interactive Schemes for the AWGN Channel with Noisy Feedback

We study the problem of communication over an additive white Gaussian noise (AWGN) channel with an AWGN feedback channel. When the feedback channel is noiseless, the classic Schalkwijk-Kailath (S-K) scheme is known to achieve capacity in a simple sequential fashion, while attaining reliability superior to non-feedback schemes. In this work, we show how simplicity and reliability can be attained even when the feedback is noisy, provided that the feedback channel is sufficiently better than the feedforward channel. Specifically, we introduce a low-complexity low-delay interactive scheme that operates close to capacity for a fixed bit error probability (e.g. $10^{-6}$ ). We then build on this scheme to provide two asymptotic constructions, one based on high dimensional lattices, and the other based on concatenated coding, that admit an error exponent significantly exceeding the best possible non-feedback exponent. Our approach is based on the interpretation of feedback transmission as a side-information problem, and employs an interactive modulo-lattice solution.

preprint2017arXiv

Subspace Learning From Bits

Networked sensing, where the goal is to perform complex inference using a large number of inexpensive and decentralized sensors, has become an increasingly attractive research topic due to its applications in wireless sensor networks and internet-of-things. To reduce the communication, sensing and storage complexity, this paper proposes a simple sensing and estimation framework to faithfully recover the principal subspace of high-dimensional data streams using a collection of binary measurements from distributed sensors, without transmitting the whole data. The binary measurements are designed to indicate comparison outcomes of aggregated energy projections of the data samples over pairs of randomly selected directions. When the covariance matrix is a low-rank matrix, we propose a spectral estimator that recovers the principal subspace of the covariance matrix as the subspace spanned by the top eigenvectors of a properly designed surrogate matrix, which is provably accurate as soon as the number of binary measurements is sufficiently large. An adaptive rank selection strategy based on soft thresholding is also presented. Furthermore, we propose a tailored spectral estimator when th

preprint2017arXiv

On the Performance of Zero-Forcing Processing in Multi-Way Massive MIMO Relay Networks

We consider a multi-way massive multiple-input multiple-output relay network with zero-forcing processing at the relay. By taking into account the time-division duplex protocol with channel estimation, we derive an analytical approximation of the spectral efficiency. This approximation is very tight and simple which enables us to analyze the system performance, as well as, to compare the spectral efficiency with zero-forcing and maximum-ratio processing. Our results show that by using a very large number of relay antennas and with the zero-forcing technique, we can simultaneously serve many active users in the same time-frequency resource, each with high spectral efficiency.

preprint2017arXiv

The second Feng-Rao number for codes coming from telescopic semigroups

In this manuscript we show that the second Feng-Rao number of any telescopic numerical semigroup agrees with the multiplicity of the semigroup. To achieve this result we first study the behavior of Apéry sets under gluings of numerical semigroups. These results provide a bound for the second Hamming weight of one-point Algebraic Geometry codes, which improves upon other estimates such as the Griesmer Order Bound.

preprint2016arXiv

LCD Cyclic Codes over Finite Fields

In addition to their applications in data storage, communications systems, and consumer electronics, LCD codes -- a class of linear codes -- have been employed in cryptography recently. LCD cyclic codes were referred to as reversible cyclic codes in the literature. The objective of this paper is to construct several families of reversible cyclic codes over finite fields and analyse their parameters. The LCD cyclic codes presented in this paper have very good parameters in general, and contain many optimal codes. A well rounded treatment of reversible cyclic codes is also given in this paper.

preprint2016arXiv

Evaluation of Generalized Degrees of Freedom for Sparse Estimation by Replica Method

We develop a method to evaluate the generalized degrees of freedom (GDF), which is a key quantity of a model selection criterion, for linear regression with sparse regularization. Using the replica method, GDF is expressed by the variables that characterize the saddle point of the free energy without depending on the form of the regularization. Within the framework of replica symmetric (RS) analysis, GDF is provided with a physical meaning as the effective density of non-zero components. The validity of our method in the RS phase is supported by the consistency of our results with previous mathematical results. The analytical results in the RS phase are numerically achieved by the belief propagation algorithm.

preprint2016arXiv

A computational investigation of the relationships between single-neuron and network dynamics in the cerebral cortex

Functions of brain areas in complex animals are believed to rely on the dynamics of networks of neurons rather than on single neurons. On the other hand, the network dynamics reflect and arise from the integration and coordination of the activity of populations of single neurons. Understanding how single-neurons and neural-circuits dynamics complement each other to produce brain functions is thus of paramount importance. LFPs and EEGs are good indicators of the dynamics of mesoscopic and macroscopic populations of neurons, while microscopic-level activities can be documented by measuring the membrane potential, the synaptic currents or the spiking activity of individual neurons. In this thesis we develop mathematical modelling and mathematical analysis tools that can help the interpretation of joint measures of neural activity at microscopic and mesoscopic or macroscopic scales. In particular, we develop network models of recurrent cortical circuits that can clarify the impact of several aspects of single-neuron (i.e., microscopic-level) dynamics on the activity of the whole neural population (as measured by LFP). We then develop statistical tools to characterize the relationship b

preprint2017arXiv

Delay on broadcast erasure channels under random linear combinations

We consider a transmitter broadcasting random linear combinations (over a field of size $d$ ) formed from a block of $c$ packets to a collection of $n$ receivers, where the channels between the transmitter and each receiver are independent erasure channels with reception probabilities $\mathbf{q} = (q_1,\ldots,q_n)$ . We establish several properties of the random delay until all $n$ receivers have recovered all $c$ packets, denoted $Y_{n:n}^{(c)}$ . First, we provide lower and upper bounds, exact expressions, and a recurrence for the moments of $Y_{n:n}^{(c)}$ . Second, we study the delay per packet $Y_{n:n}^{(c)}/c$ as a function of $c$ , including the asymptotic delay (as $c \to \infty$ ), and monotonicity (in $c$ ) properties of the delay per packet. Third, we employ extreme value theory to investigate $Y_{n:n}^{(c)}$ as a function of $n$ (as $n \to \infty$ ). Several results are new, some results are extensions of existing results, and some results are proofs of known results using new (probabilistic) proof techniques.

preprint2017arXiv

Another Generalization of the Reed-Muller Codes

The punctured binary Reed-Muller code is cyclic and was generalized into the punctured generalized Reed-Muller code over $\gf(q)$ in the literature. The major objective of this paper is to present another generalization of the punctured binary Reed-Muller code. Another objective is to construct a family of reversible cyclic codes that are related to the newly generalized Reed-Muller codes.

preprint2016arXiv

Compressed sensing and optimal denoising of monotone signals

We consider the problems of compressed sensing and optimal denoising for signals $\mathbf{x_0}\in\mathbb{R}^N$ that are monotone, i.e., $\mathbf{x_0}(i+1) \geq \mathbf{x_0}(i)$ , and sparsely varying, i.e., $\mathbf{x_0}(i+1) > \mathbf{x_0}(i)$ only for a small number $k$ of indices $i$ . We approach the compressed sensing problem by minimizing the total variation norm restricted to the class of monotone signals subject to equality constraints obtained from a number of measurements $A\mathbf{x_0}$ . For random Gaussian sensing matrices $A\in\mathbb{R}^{m\times N}$ we derive a closed form expression for the number of measurements $m$ required for successful reconstruction with high probability. We show that the probability undergoes a phase transition as $m$ varies, and depends not only on the number of change points, but also on their location. For denoising we regularize with the same norm and derive a formula for the optimal regularizer weight that depends only mildly on $\mathbf{x_0}$ . We obtain our results using the statistical dimension tool.

preprint2017arXiv

Compressed sensing with corrupted Fourier measurements

This paper studies a data recovery problem in compressed sensing (CS), given a measurement vector b with corruptions: b=Ax0+f0, can we recover x0 and f0 via the reweighted l1 minimization: minimize |x| + lambda*|f| subject to Ax+f=b? Here the m by n measurement matrix A is a partial Fourier matrix, x0 denotes the n dimensional ground true signal vector, f0 denotes the m-dimensional corrupted noise vector, it is assumed that a positive fraction of entries in the measurement vector b are corrupted by the non-zero entries of f0. This problem had been studied in literatures [1-3], unfortunately, certain random assumptions (which are often hard to meet in practice) are required for the signal x0 in these papers. In this paper, we show that x0 and f0 can be recovered exactly by the solution of the above reweighted l1 minimization with high probability provided that m>O(card(x0)log(n)log(n)) and n is prime, here card(x0) denotes the cardinality (number of non-zero entries) of x0. Except the sparsity, no extra assumption is needed for x0.

preprint2017arXiv

A Low-Complexity Graph-Based LMMSE Receiver for MIMO ISI Channels with M-QAM Modulation

In this paper, we propose a low complexity graph-based linear minimum mean square error (LMMSE) equalizer in order to remove inter-symbol and inter-stream interference in multiple input multiple output (MIMO) communication. The proposed state space representation inflicted on the graph provides linearly increasing computational complexity with block length. Also, owing to the Gaussian assumption used in the presented cycle-free factor graph, the complexity of the suggested equalizer structure is not affected by the size of the signalling space. In addition, we introduce an efficient way of computing extrinsic bit log-likelihood ratio (LLR) values for LMMSE estimation compatible with higher order alphabets which is shown to perform better than the other methods in the literature. Overall, we provide an efficient receiver structure reaching high data rates in frequency selective MIMO systems whose performance is shown to be very close to a genie-aided matched filter bound through extensive simulations.

preprint2016arXiv

On the Capacity of Discrete-Time Laguerre Channel

In this paper, new upper and lower bounds are proposed for the capacity of discrete-time Laguerre channel. Laguerre behavior is used to model various types of optical systems and networks such as optical amplifiers, short distance visible light communication systems with direct detection and coherent code division multiple access (CDMA) networks. Bounds are derived for short distance visible light communication systems and coherent CDMA networks. These bounds are separated in three main cases: when both average and peak power constraints are imposed, when peak power constraint is inactive and when only peak power constraint is active.

preprint2016arXiv

Optimal Transmission Policies for Multi-hop Energy Harvesting Systems

In this paper, we consider a multi-hop energy harvesting (EH) communication system in a full-duplex mode, where arrival data and harvested energy curves in the source and the relays are modeled as general functions. This model includes the EH system with discrete arrival processes as a special case. We investigate the throughput maximization problem considering minimum utilized energy in the source and relays and find the optimal offline algorithm. We show that the optimal solution of the two-hop transmission problem have three main steps: (i) Solving a point-to-point throughput maximization problem at the source; (ii) Solving a point-to-point throughput maximization problem at the relay (after applying the solution of first step as the input of this second problem); (iii) Minimizing utilized energy in the source. In addition, we show that how the optimal algorithm for the completion time minimization problem can be derived from the proposed algorithm for throughput maximization problem. Also, for the throughput maximization problem, we propose an online algorithm and show that it is more efficient than the benchmark one (which is a direct application of an existing point-to-point

preprint2017arXiv

A time-variant channel prediction and feedback framework for interference alignment

In interference channels, channel state information (CSI) can be exploited to reduce the interference signal dimensions and thus achieve the optimal capacity scaling, i.e. degrees of freedom, promised by the interference alignment technique. However, imperfect CSI, due to channel estimation error, imperfect CSI feedback and time selectivity of the channel, lead to a performance loss. In this work, we propose a novel limited feedback algorithm for single-input single-output interference alignment in time-variant channels. The feedback algorithm encodes the channel evolution in a small number of subspace coefficients, which allow for reduced-rank channel prediction to compensate for the channel estimation error due to time selectivity of the fading process and feedback delay. An upper bound for the rate loss caused by feedback quantization and channel prediction is derived. Based on this bound, we develop a dimension switching algorithm for the reduced-rank predictor to find the best tradeoff between quantization- and prediction-error. Besides, we characterize the scaling of the required number of feedback bits in order to decouple the rate loss due to channel quantization from the t

Inspect nearby papers, researchers, institutions and communities without opening a separate graph page.