Information Theory (cs.IT)

Abstract: Bounds on information combining are a fundamental tool in coding theory, in particular when analyzing polar codes and belief propagation. They usually bound the evolution of random variables with respect to their Shannon entropy. In recent work this approach was generalized to Renyi $\alpha$-entropies. However, due to the lack of a traditional chain rule for Renyi entropies the picture remained incomplete. In this work we establish the missing link by providing Renyi chain rules connecting different definitions of Renyi entropies by Hayashi and Arimoto. This allows us to provide new information combining bounds for the Arimoto Renyi entropy. In the second part, we generalize the chain rule to the quantum setting and show how they allow us to generalize results and conjectures previously only given for the von Neumann entropy. In the special case of $\alpha=2$ we give the first optimal information combining bounds with quantum side information.

Abstract: Due to the ever increasing data rate demand of beyond 5G networks and considering the wide range of Orthogonal Frequency Division Multipllexing (OFDM) technique in cellular systems, it is critical to reduce pilot overhead of OFDM systems in order to increase data rate of such systems. Due to sparsity of multipath channels, sparse recovery methods can be exploited to reduce pilot overhead. OFDM pilots are utilized as random samples for channel impulse response estimation. We propose a three-step sparsity recovery algorithm which is based on sparsity domain smoothing. Time domain residue computation, sparsity domain smoothing, and adaptive thresholding sparsifying are the three-steps of the proposed scheme. To the best of our knowledge, the proposed sparsity domain smoothing based thresholding recovery method known as SDS-IMAT has not been used for OFDM sparse channel estimation in the literature. Pilot locations are also derived based on the minimization of the measurement matrix coherence. Numerical results verify that the performance of the proposed scheme outperforms other existing thresholding and greedy recovery methods and has a near-optimal performance. The effectiveness of the proposed scheme is shown in terms of mean square error and bit error rate.

Abstract: In this paper, we propose a novel multi-symbol unitary constellation structure for non-coherent single-input multiple-output (SIMO) communications over block Rayleigh fading channels. To facilitate the design and the detection of large unitary constellations at reduced complexity, the proposed constellations are constructed as the Cartesian product of independent amplitude and phase-shift-keying (PSK) vectors, and hence, can be iteratively detected. The amplitude vector can be detected by exhaustive search, whose complexity is still sufficiently low in short packet transmissions. For detection of the PSK vector, we adopt a maximum-A-posteriori (MAP) criterion to improve the reliability of the sorted decision-feedback differential detection (sort-DFDD), which results in near-optimal error performance in the case of the same modulation order of the transmit PSK symbols at different time slots. This detector is called MAP-based-reliability-sort-DFDD (MAP-R-sort-DFDD) and has polynomial complexity. For the case of different modulation orders at different time slots, we observe that undetected symbols with lower modulation orders have a significant impact on the detection of PSK symbols with higher modulation orders. We exploit this observation and propose an improved detector called improved-MAP-R-sort-DFDD, which approaches the optimal error performance with polynomial time complexity. Simulation results show the merits of our proposed multi-symbol unitary constellation when compared to competing low-complexity unitary constellations.

Abstract: The Blahut-Arimoto (BA) algorithm has played a fundamental role in the numerical computation of rate-distortion (RD) functions. This algorithm possesses a desirable monotonic convergence property by alternatively minimizing its Lagrangian with a fixed multiplier. In this paper, we propose a novel modification of the BA algorithm, letting the multiplier be updated in each iteration via a one-dimensional root-finding step with respect to a monotonic univariate function, which can be efficiently implemented by Newton's method. This allows the multiplier to be updated in a flexible and efficient manner, overcoming a major drawback of the original BA algorithm wherein the multiplier is fixed throughout iterations. Consequently, the modified algorithm is capable of directly computing the RD function for a given target distortion, without exploring the entire RD curve as in the original BA algorithm. A theoretical analysis shows that the modified algorithm still converges to the RD function and the convergence rate is $\Theta(1/n)$, where $n$ denotes the number of iterations. Numerical experiments demonstrate that the modified algorithm directly computes the RD function with a given target distortion, and it significantly accelerates the original BA algorithm.

Abstract: Fractional programming (FP) plays a crucial role in wireless network design because many relevant problems involve maximizing or minimizing ratio terms. Notice that the maximization case and the minimization case of FP cannot be converted to each other in general, so they have to be dealt with separately in most of the previous studies. Thus, an existing FP method for maximizing ratios typically does not work for the minimization case, and vice versa. However, the FP objective can be mixed max-and-min, e.g., one may wish to maximize the signal-to-interference-plus-noise ratio (SINR) of the legitimate receiver while minimizing that of the eavesdropper. We aim to fill the gap between max-FP and min-FP by devising a unified optimization framework. The main results are three-fold. First, we extend the existing max-FP technique called quadratic transform to the min-FP, and further develop a full generalization for the mixed case. Second. we provide a minorization-maximization (MM) interpretation of the proposed unified approach, thereby establishing its convergence and also obtaining a matrix extension; another result we obtain is a generalized Lagrangian dual transform which facilitates the solving of the logarithmic FP. Finally, we present three typical applications: the age-of-information (AoI) minimization, the Cramer-Rao bound minimization for sensing, and the secure data rate maximization, none of which can be efficiently addressed by the previous FP methods.

Abstract: Recent studies show that stable distributions are successful in modeling heavy-tailed or impulsive noise. Investigation of the stability of a probability distribution can be greatly facilitated if the corresponding characteristic function (CF) has a closed-form expression. We explore a new family of distribution called the Vertically-Drifted First Arrival Position (VDFAP) distribution, which can be viewed as a generalization of symmetric alpha-stable (S$\alpha$S) distribution with stability parameter $\alpha=1$. In addition, VDFAP distribution has a clear physical interpretation when we consider first-hitting problems of particles following Brownian motion with a driving drift. Inspired by the Fourier relation between the probability density function and CF of Student's $t$-distribution, we extract an integral representation for the VDFAP probability density function. Then, we exploit the Hankel transform to derive a closed-form expression for the CF of VDFAP. From the CF, we discover that VDFAP possesses some interesting stability properties, which are in a weaker form than S$\alpha$S. This calls for a generalization of the theory on alpha-stable distributions.

Abstract: Integer data is typically made differentially private by adding noise from a Discrete Laplace (or Discrete Gaussian) distribution. We study the setting where differential privacy of a counting query is achieved using bit-wise randomized response, i.e., independent, random bit flips on the encoding of the query answer. Binary error-correcting codes transmitted through noisy channels with independent bit flips are well-studied in information theory. However, such codes are unsuitable for differential privacy since they have (by design) high sensitivity, i.e., neighboring integers have encodings with a large Hamming distance. Gray codes show that it is possible to create an efficient sensitivity 1 encoding, but are also not suitable for differential privacy due to lack of noise-robustness. Our main result is that it is possible, with a constant rate code, to simultaneously achieve the sensitivity of Gray codes and the noise-robustness of error-correcting codes (down to the noise level required for differential privacy). An application of this new encoding of the integers is a faster, space-optimal differentially private data structure for histograms.

Abstract: Designing capacity achieving coding schemes for the band-limited additive Gaussian channel with colored noise has been and is still a challenge. In this paper, the capacity of the band-limited additive Gaussian channel with colored noise is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. To this aim, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It has been shown that there exist Gaussian colored noise with a computable continuous noise spectral density whose capacity is a non-computable number. Moreover, it has been demonstrated that for these channels, it is not possible to find a computable sequence of asymptotically sharp upper bounds for their capacity.

Abstract: Integrating sensing functionalities is envisioned as a distinguishing feature of next-generation mobile networks, which has given rise to the development of a novel enabling technology -- \emph{Integrated Sensing and Communication (ISAC)}. Portraying the theoretical performance bounds of ISAC systems is fundamentally important to understand how sensing and communication functionalities interact (e.g., competitively or cooperatively) in terms of resource utilization, while revealing insights and guidelines for the development of effective physical-layer techniques. In this paper, we characterize the fundamental performance tradeoff between the detection probability for target monitoring and the user's achievable rate in ISAC systems. To this end, we first discuss the achievable rate of the user under sensing-free and sensing-interfered communication scenarios. Furthermore, we derive closed-form expressions for the probability of false alarm (PFA) and the successful probability of detection (PD) for monitoring the target of interest, where we consider both communication-assisted and communication-interfered sensing scenarios. In addition, the effects of the unknown channel coefficient are also taken into account in our theoretical analysis. Based on our analytical results, we then carry out a comprehensive assessment of the performance tradeoff between sensing and communication functionalities. Specifically, we formulate a power allocation problem to minimize the transmit power at the base station (BS) under the constraints of ensuring a required PD for perception as well as the communication user's quality of service requirement in terms of achievable rate. Finally, simulation results corroborate the accuracy of our theoretical analysis and the effectiveness of the proposed power allocation solutions.

Abstract: The weight distribution of error correction codes is a critical determinant of their error-correcting performance, making enumeration of utmost importance. In the case of polar codes, the minimum weight $\wm$ (which is equal to minimum distance $d$) is the only weight for which an explicit enumerator formula is currently available. Having closed-form weight enumerators for polar codewords with weights greater than the minimum weight not only simplifies the enumeration process but also provides valuable insights towards constructing better polar-like codes. In this paper, we contribute towards understanding the algebraic structure underlying higher weights by analyzing Minkowski sums of orbits. Our approach builds upon the lower triangular affine (LTA) group of decreasing monomial codes. Specifically, we propose a closed-form expression for the enumeration of codewords with weight $1.5\wm$. Our simulations demonstrate the potential for extending this method to higher weights.

Abstract: 5G new radio (NR) technology is introduced to satisfy more demanding services. Ultra-Reliable Low Latency Communication (URLLC) requires very low delay compared with the previous techniques. This is hard to achieve when hybrid automatic repeat request (HARQ) is applied and especially when the feedback channel is erroneous. In this work, we consider various delay components in incremental redundancy (IR) HARQ systems and minimize the average delay by applying asymmetric feedback detection (AFD) and find the optimal transmission length for each transmission attempt. A M/G/1 queuing model is used in this work to analyze the queuing delay in 5G NR when there are multiple uses in the system. Numerical results show that significant performance gains and lower outage probability can be achieved by applying AFD.

Abstract: The majorizing measure theorem of Fernique and Talagrand is a fundamental result in the theory of random processes. It relates the boundedness of random processes indexed by elements of a metric space to complexity measures arising from certain multiscale combinatorial structures, such as packing and covering trees. This paper builds on the ideas first outlined in a little-noticed preprint of Andreas Maurer to present an information-theoretic perspective on the majorizing measure theorem, according to which the boundedness of random processes is phrased in terms of the existence of efficient variable-length codes for the elements of the indexing metric space.

Abstract: This paper explores the Ziv-Zakai bound (ZZB), which is a well-known Bayesian lower bound on the Minimum Mean Squared Error (MMSE). First, it is shown that the ZZB holds without any assumption on the distribution of the estimand, that is, the estimand does not necessarily need to have a probability density function. The ZZB is then further analyzed in the high-noise and low-noise regimes and shown to always tensorize. Finally, the tightness of the ZZB is investigated under several aspects, such as the number of hypotheses and the usefulness of the valley-filling function. In particular, a sufficient and necessary condition for the tightness of the bound with continuous inputs is provided, and it is shown that the bound is never tight for discrete input distributions with a support set that does not have an accumulation point at zero.