Information Theory

Date: Fri, 19 Jul 2024 | Total: 12

#1 Energy-Efficient Channel Decoding for Wireless Federated Learning: Convergence Analysis and Adaptive Design [PDF] [Copy] [Kimi]

Authors: Linping Qu ; Yuyi Mao ; Shenghui Song ; Chi-Ying Tsui

One of the most critical challenges for deploying distributed learning, such as federated learning (FL), in wireless networks is the limited battery capacity of mobile devices. While it is a common belief that the major energy consumption of mobile devices comes from the uplink data transmission, this paper presents a novel finding, namely the channel decoding operation also contributes significantly to the overall energy consumption of mobile devices in FL. Motivated by this new observation, we propose an energy-efficient adaptive channel decoding scheme that leverages the intrinsic robustness of FL to model errors. In particular, the robustness is exploited to reduce the energy consumption of channel decoders at mobile devices by adaptively adjusting the number of decoding iterations. We theoretically prove that FL with communication errors can converge at the same rate as error-free communication as long as the bit error rate (BER) is properly constrained. An adaptive channel decoding scheme is then proposed to improve the energy efficiency of FL systems. Experimental results demonstrate that the proposed method maintains the same learning accuracy while reducing the channel decoding energy consumption by 20% when compared to existing approaches.

Subjects: Information Theory ; Machine Learning ; Signal Processing ; Information Theory

Publish: 2024-06-26 08:59:49 UTC

#2 An Algorithm for Computing the Capacity of Symmetrized KL Information for Discrete Channels [PDF] [Copy] [Kimi]

Authors: Haobo Chen ; Gholamali Aminian ; Yuheng Bu

Symmetrized Kullback-Leibler (KL) information (\(I_{\mathrm{SKL}}\)), which symmetrizes the traditional mutual information by integrating Lautum information, has been shown as a critical quantity in communication~\cite{aminian2015capacity} and learning theory~\cite{aminian2023information}. This paper considers the problem of computing the capacity in terms of \(I_{\mathrm{SKL}}\) for a fixed discrete channel. Such a maximization problem is reformulated into a discrete quadratic optimization with a simplex constraint. One major challenge here is the non-concavity of Lautum information, which complicates the optimization problem. Our method involves symmetrizing the KL divergence matrix and applying iterative updates to ensure a non-decreasing update while maintaining a valid probability distribution. We validate our algorithm on Binary symmetric Channels and Binomial Channels, demonstrating its consistency with theoretical values. Additionally, we explore its application in machine learning through the Gibbs channel, showcasing the effectiveness of our algorithm in finding the worst-case data distributions.

Subjects: Information Theory ; Information Theory

Publish: 2024-07-18 12:03:19 UTC

#3 Group Movable Antenna With Flexible Sparsity: Joint Array Position and Sparsity Optimization [PDF] [Copy] [Kimi]

Authors: Haiquan Lu ; Yong Zeng ; Shi Jin ; Rui Zhang

Movable antenna (MA) is a promising technology to exploit the spatial variation of wireless channel for performance enhancement, by dynamically varying the antenna position within a certain region. However, for multi-antenna communication systems, moving each antenna independently not only requires prohibitive complexity to find the optimal antenna positions, but also incurs sophisticated movement control in practice. To address this issue, this letter proposes a new MA architecture termed group MA (GMA), enabling the group movement of all elements collectively in a continuous manner, and simultaneously achieving flexible array architecture by antenna selection (AS). In this letter, we focus on the uniform sparse array based GMA, where equally spaced antenna elements are selected to achieve desired array sparsity. The array position and sparsity level are jointly optimized to maximize the sum rate of the multi-user communication system. Numerical results verify the necessity to optimize the position and sparsity of GMA, and considerable performance gain is achieved as compared to the conventional fixed-position antenna (FPA).

Subjects: Information Theory ; Signal Processing ; Information Theory

Publish: 2024-07-18 09:08:53 UTC

#4 Interleaved Block-Sparse Transform [PDF] [Copy] [Kimi]

Authors: Lei Liu ; Ming Wang ; Shufeng Li ; Yuhao Chi ; Ning Wei ; ZhaoYang Zhang

Low-complexity Bayes-optimal memory approximate message passing (MAMP) is an efficient signal estimation algorithm in compressed sensing and multicarrier modulation. However, achieving replica Bayes optimality with MAMP necessitates a large-scale right-unitarily invariant transformation, which is prohibitive in practical systems due to its high computational complexity and hardware costs. To solve this difficulty, this letter proposes a low-complexity interleaved block-sparse (IBS) transform, which consists of interleaved multiple low-dimensional transform matrices, aimed at reducing the hardware implementation scale while mitigating performance loss. Furthermore, an IBS cross-domain memory approximate message passing (IBS-CD-MAMP) estimator is developed, comprising a memory linear estimator in the IBS transform domain and a non-linear estimator in the source domain. Numerical results show that the IBS-CD-MAMP offers a reduced implementation scale and lower complexity with excellent performance in IBS-based compressed sensing and interleave frequency division multiplexing systems.

Subjects: Information Theory ; Signal Processing ; Information Theory

Publish: 2024-07-18 08:08:26 UTC

#5 Gaussian Channel Simulation with Rotated Dithered Quantization [PDF] [Copy] [Kimi]

Authors: Szymon Kobus ; Lucas Theis ; Deniz Gündüz

Channel simulation involves generating a sample $Y$ from the conditional distribution $P_{Y|X}$, where $X$ is a remote realization sampled from $P_X$. This paper introduces a novel approach to approximate Gaussian channel simulation using dithered quantization. Our method concurrently simulates $n$ channels, reducing the upper bound on the excess information by half compared to one-dimensional methods. When used with higher-dimensional lattices, our approach achieves up to six times reduction on the upper bound. Furthermore, we demonstrate that the KL divergence between the distributions of the simulated and Gaussian channels decreases with the number of dimensions at a rate of $O(n^{-1})$.

Subjects: Information Theory ; Information Theory

Publish: 2024-07-17 19:32:51 UTC

#6 Barycentric bounds on the error exponents of quantum hypothesis exclusion [PDF] [Copy] [Kimi]

Authors: Kaiyuan Ji ; Hemant K. Mishra ; Milán Mosonyi ; Mark M. Wilde

Quantum state exclusion is an operational task that has significance in studying foundational questions related to interpreting quantum theory. In such a task, one is given a system whose state is randomly selected from a finite set, and the goal is to identify a state from the set that is not the true state of the system. An error, i.e., an unsuccessful exclusion, occurs if and only if the state identified is the true state. In this paper, we study the optimal error probability of quantum state exclusion and its error exponent -- the rate at which the error probability decays asymptotically -- from an information-theoretic perspective. Our main finding is a single-letter upper bound on the error exponent of state exclusion given by the multivariate log-Euclidean Chernoff divergence, and we prove that this improves upon the best previously known upper bound. We also extend our analysis to the more complicated task of quantum channel exclusion, and we establish a single-letter and efficiently computable upper bound on its error exponent, even assuming the use of adaptive strategies. We derive both upper bounds, for state and channel exclusion, based on one-shot analysis and formulate them as a type of multivariate divergence measure called a barycentric Chernoff divergence. Moreover, our result on channel exclusion has implications in two important special cases. First, for the special case of two hypotheses, our upper bound provides the first known efficiently computable upper bound on the error exponent of symmetric binary channel discrimination. Second, for the special case of classical channels, we show that our upper bound is achievable by a nonadaptive strategy, thus solving the exact error exponent of classical channel exclusion and generalising a similar result on symmetric binary classical channel discrimination.

Subjects: Quantum Physics ; Information Theory ; Mathematical Physics ; Information Theory ; Mathematical Physics

Publish: 2024-07-18 17:27:36 UTC

#7 Quasi-Fractal UCA Based N-Dimensional OAM Orthogonal Transmission [PDF] [Copy] [Kimi]

Authors: Hongyun Jin ; Wenchi Cheng ; Wei Zhang

The vortex electromagnetic wave carried by multiple orthogonal orbital angular momentum (OAM) modes in the same frequency band can be applied to the field of wireless communications, which greatly increases the spectrum efficiency. The uniform circular array (UCA) structure is widely used to generate or receive vortex electromagnetic waves with multiple OAM-modes. However, the maximum number of orthogonal OAM-modes based on UCA is usually limited to the number of array-elements of the UCA antenna, leaving how to utilize more OAM-modes to achieve higher spectrum efficiency given a fixed number of array-elements as an intriguing question. In this paper, we propose an Ndimensional quasi-fractal UCA (ND QF-UCA) antenna structure in different fractal geometry layouts to break through the limits of array-elements number on OAM-modes number. We develop the N-dimensional OAM modulation (NOM) and demodulation (NOD) schemes for OAM multiplexing transmission with the OAM-modes number exceeding the array-elements number, which is beyond the traditional concept of multiple antenna based wireless communications. Then, we investigate different dimensional multiplex transmission schemes based on the corresponding QF-UCA antenna structure with various array-elements layouts. Simulation results show that our proposed schemes can obtain a higher spectrum efficiency.

Subjects: Signal Processing ; Information Theory ; Information Theory

Publish: 2024-06-09 06:57:53 UTC

#8 Non-Asymptotic Uncertainty Quantification in High-Dimensional Learning [PDF] [Copy] [Kimi1]

Authors: Frederik Hoppe ; Claudio Mayrink Verdun ; Hannah Laus ; Felix Krahmer ; Holger Rauhut

Uncertainty quantification (UQ) is a crucial but challenging task in many high-dimensional regression or learning problems to increase the confidence of a given predictor. We develop a new data-driven approach for UQ in regression that applies both to classical regression approaches such as the LASSO as well as to neural networks. One of the most notable UQ techniques is the debiased LASSO, which modifies the LASSO to allow for the construction of asymptotic confidence intervals by decomposing the estimation error into a Gaussian and an asymptotically vanishing bias component. However, in real-world problems with finite-dimensional data, the bias term is often too significant to be neglected, resulting in overly narrow confidence intervals. Our work rigorously addresses this issue and derives a data-driven adjustment that corrects the confidence intervals for a large class of predictors by estimating the means and variances of the bias terms from training data, exploiting high-dimensional concentration phenomena. This gives rise to non-asymptotic confidence intervals, which can help avoid overestimating uncertainty in critical applications such as MRI diagnosis. Importantly, our analysis extends beyond sparse regression to data-driven predictors like neural networks, enhancing the reliability of model-based deep learning. Our findings bridge the gap between established theory and the practical applicability of such debiased methods.

Subjects: Machine Learning ; Information Theory ; Image and Video Processing ; Information Theory ; Applications ; Machine Learning

Publish: 2024-07-18 16:42:10 UTC

#9 With or Without Replacement? Improving Confidence in Fourier Imaging [PDF] [Copy] [Kimi]

Authors: Frederik Hoppe ; Claudio Mayrink Verdun ; Felix Krahmer ; Marion I. Menzel ; Holger Rauhut

Over the last few years, debiased estimators have been proposed in order to establish rigorous confidence intervals for high-dimensional problems in machine learning and data science. The core argument is that the error of these estimators with respect to the ground truth can be expressed as a Gaussian variable plus a remainder term that vanishes as long as the dimension of the problem is sufficiently high. Thus, uncertainty quantification (UQ) can be performed exploiting the Gaussian model. Empirically, however, the remainder term cannot be neglected in many realistic situations of moderately-sized dimensions, in particular in certain structured measurement scenarios such as Magnetic Resonance Imaging (MRI). This, in turn, can downgrade the advantage of the UQ methods as compared to non-UQ approaches such as the standard LASSO. In this paper, we present a method to improve the debiased estimator by sampling without replacement. Our approach leverages recent results of ours on the structure of the random nature of certain sampling schemes showing how a transition between sampling with and without replacement can lead to a weighted reconstruction scheme with improved performance for the standard LASSO. In this paper, we illustrate how this reweighted sampling idea can also improve the debiased estimator and, consequently, provide a better method for UQ in Fourier imaging.

Subjects: Signal Processing ; Information Theory ; Machine Learning ; Image and Video Processing ; Information Theory ; Applications

Publish: 2024-07-18 15:15:19 UTC

#10 The Language of Infographics: Toward Understanding Conceptual Metaphor Use in Scientific Storytelling [PDF] [Copy] [Kimi]

Authors: Hana Pokojná ; Tobias Isenberg ; Stefan Bruckner ; Barbora Kozlíková ; Laura Garrison

We apply an approach from cognitive linguistics by mapping Conceptual Metaphor Theory (CMT) to the visualization domain to address patterns of visual conceptual metaphors that are often used in science infographics. Metaphors play an essential part in visual communication and are frequently employed to explain complex concepts. However, their use is often based on intuition, rather than following a formal process. At present, we lack tools and language for understanding and describing metaphor use in visualization to the extent where taxonomy and grammar could guide the creation of visual components, e.g., infographics. Our classification of the visual conceptual mappings within scientific representations is based on the breakdown of visual components in existing scientific infographics. We demonstrate the development of this mapping through a detailed analysis of data collected from four domains (biomedicine, climate, space, and anthropology) that represent a diverse range of visual conceptual metaphors used in the visual communication of science. This work allows us to identify patterns of visual conceptual metaphor use within the domains, resolve ambiguities about why specific conceptual metaphors are used, and develop a better overall understanding of visual metaphor use in scientific infographics. Our analysis shows that ontological and orientational conceptual metaphors are the most widely applied to translate complex scientific concepts. To support our findings we developed a visual exploratory tool based on the collected database that places the individual infographics on a spatio-temporal scale and illustrates the breakdown of visual conceptual metaphors.

Subjects: Information Retrieval ; Information Theory ; Information Theory

Publish: 2024-07-18 11:39:50 UTC

#11 Adaptive Foundation Models for Online Decisions: HyperAgent with Fast Incremental Uncertainty Estimation [PDF] [Copy] [Kimi]

Authors: Yingru Li ; Jiawei Xu ; Zhi-Quan Luo

Foundation models often struggle with uncertainty when faced with new situations in online decision-making, necessitating scalable and efficient exploration to resolve this uncertainty. We introduce GPT-HyperAgent, an augmentation of GPT with HyperAgent for uncertainty-aware, scalable exploration in contextual bandits, a fundamental online decision problem involving natural language input. We prove that HyperAgent achieves fast incremental uncertainty estimation with $\tilde{O}(\log T)$ per-step computational complexity over $T$ periods under the linear realizable assumption. Our analysis demonstrates that HyperAgent's regret order matches that of exact Thompson sampling in linear contextual bandits, closing a significant theoretical gap in scalable exploration. Empirical results in real-world contextual bandit tasks, such as automated content moderation with human feedback, validate the practical effectiveness of GPT-HyperAgent for safety-critical decisions. Our code is open-sourced at \url{https://github.com/szrlee/GPT-HyperAgent/}.

Subjects: Machine Learning ; Artificial Intelligence ; Human-Computer Interaction ; Information Theory ; Information Theory ; Machine Learning

Publish: 2024-07-18 06:16:09 UTC

#12 Finite de Finetti bounds in relative entropy [PDF] [Copy] [Kimi]

Authors: Lampros Gavalakis ; Oliver Johnson ; Ioannis Kontoyiannis

We review old and recent finite de Finetti theorems in total variation distance and in relative entropy, and we highlight their connections with bounds on the difference between sampling with and without replacement. We also establish two new finite de Finetti theorems for exchangeable random vectors taking values in arbitrary spaces. These bounds are tight, and they are independent of the size and the dimension of the underlying space.

Subjects: Probability ; Information Theory ; Information Theory

Publish: 2024-07-17 18:00:14 UTC