We gratefully acknowledge support from
the Simons Foundation and member institutions.

Information Theory

New submissions

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

New submissions for Fri, 12 Apr 24

[1]  arXiv:2404.07311 [pdf, ps, other]
Title: Average entropy of Gaussian mixtures
Comments: 24 pages
Subjects: Information Theory (cs.IT)

We calculate the average differential entropy of a $q$-component Gaussian mixture in $\mathbb R^n$. For simplicity, all components have covariance matrix $\sigma^2 {\mathbf 1}$, while the means $\{\mathbf{W}_i\}_{i=1}^{q}$ are i.i.d. Gaussian vectors with zero mean and covariance $s^2 {\mathbf 1}$. We obtain a series expansion in $\mu=s^2/\sigma^2$ for the average differential entropy up to order $\mathcal{O}(\mu^2)$, and we provide a recipe to calculate higher order terms. Our result provides an analytic approximation with a quantifiable order of magnitude for the error, which is not achieved in previous literature.

[2]  arXiv:2404.07515 [pdf, ps, other]
Title: Stability in Phase Retrieval: Characterizing Condition Numbers and the Optimal Vector Set
Subjects: Information Theory (cs.IT); Functional Analysis (math.FA); Numerical Analysis (math.NA)

In this paper, we primarily focus on analyzing the stability property of phase retrieval by examining the bi-Lipschitz property of the map $\Phi_{\boldsymbol{A}}(\boldsymbol{x})=|\boldsymbol{A}\boldsymbol{x}|\in \mathbb{R}_+^m$, where $\boldsymbol{x}\in \mathbb{H}^d$ and $\boldsymbol{A}\in \mathbb{H}^{m\times d}$ is the measurement matrix for $\mathbb{H}\in\{\mathbb{R},\mathbb{C}\}$. We define the condition number $\beta_{\boldsymbol{A}}:=\frac{U_{\boldsymbol{A}}}{L_{\boldsymbol{A}}}$, where $L_{\boldsymbol{A}}$ and $U_{\boldsymbol{A}}$ represent the optimal lower and upper Lipschitz constants, respectively. We establish the first universal lower bound on $\beta_{\boldsymbol{A}}$ by demonstrating that for any ${\boldsymbol{A}}\in\mathbb{H}^{m\times d}$, \begin{equation*} \beta_{\boldsymbol{A}}\geq \beta_0^{\mathbb{H}}:=\begin{cases} \sqrt{\frac{\pi}{\pi-2}}\,\,\approx\,\, 1.659 & \text{if $\mathbb{H}=\mathbb{R}$,}\\ \sqrt{\frac{4}{4-\pi}}\,\,\approx\,\, 2.159 & \text{if $\mathbb{H}=\mathbb{C}$.} \end{cases} \end{equation*} We prove that the condition number of a standard Gaussian matrix in $\mathbb{H}^{m\times d}$ asymptotically matches the lower bound $\beta_0^{\mathbb{H}}$ for both real and complex cases. This result indicates that the constant lower bound $\beta_0^{\mathbb{H}}$ is asymptotically tight, holding true for both the real and complex scenarios. As an application of this result, we utilize it to investigate the performance of quadratic models for phase retrieval. Lastly, we establish that for any odd integer $m\geq 3$, the harmonic frame $\boldsymbol{A}\in \mathbb{R}^{m\times 2}$ possesses the minimum condition number among all $\boldsymbol{A}\in \mathbb{R}^{m\times 2}$. We are confident that these findings carry substantial implications for enhancing our understanding of phase retrieval.

[3]  arXiv:2404.07670 [pdf, ps, other]
Title: On Naisargik Images of Varshamov-Tenengolts and Helberg Codes
Comments: 20 pages, 18 Tables, draft, data is at this https URL
Subjects: Information Theory (cs.IT); Emerging Technologies (cs.ET); Combinatorics (math.CO)

The VT and Helberg codes, both in binary and non-binary forms, stand as elegant solutions for rectifying insertion and deletion errors. In this paper we consider the quaternary versions of these codes. It is well known that many optimal binary non-linear codes like Kerdock and Prepreta can be depicted as Gray images (isometry) of codes defined over $\mathbb{Z}_4$. Thus a natural question arises: Can we find similar maps between quaternary and binary spaces which gives interesting properties when applied to the VT and Helberg codes. We found several such maps called Naisargik (natural) maps and we study the images of quaternary VT and Helberg codes under these maps. Naisargik and inverse Naisargik images gives interesting error-correcting properties for VT and Helberg codes. If two Naisargik images of VT code generates an intersecting one deletion sphere, then the images holds the same weights. A quaternary Helberg code designed to correct $s$ deletions can effectively rectify $s+1$ deletion errors when considering its Naisargik image, and $s$-deletion correcting binary Helberg code can corrects $\lfloor\frac{s}{2}\rfloor$ errors with inverse Naisargik image.

[4]  arXiv:2404.07759 [pdf, other]
Title: RIS-Assisted OTFS Communications: Phase Configuration via Received Energy Maximization
Comments: 6 pages (double column), 5 figures, conference paper
Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)

In this paper, we explore the integration of two revolutionary technologies, reconfigurable intelligent surfaces (RISs) and orthogonal time frequency space (OTFS) modulation, to enhance high-speed wireless communications. We introduce a novel phase shift design algorithm for RIS-assisted OTFS, optimizing energy reception and channel gain in dynamic environments. The study evaluates the proposed approach in a downlink scenario, demonstrating significant performance improvements compared to benchmark schemes in the literature, particularly in terms of bit error rate (BER). Our results showcase the potential of RIS to enhance the system's performance. Specifically, our proposed phase shift design technique outperforms the benchmark solutions by over 4 dB. Furthermore, even greater gains can be obtained as the number of RIS elements increases.

Cross-lists for Fri, 12 Apr 24

[5]  arXiv:2404.07281 (cross-list from quant-ph) [pdf, other]
Title: Certifying almost all quantum states with few single-qubit measurements
Comments: 63 pages, 5 figures
Subjects: Quantum Physics (quant-ph); Information Theory (cs.IT); Machine Learning (cs.LG)

Certifying that an n-qubit state synthesized in the lab is close to the target state is a fundamental task in quantum information science. However, existing rigorous protocols either require deep quantum circuits or exponentially many single-qubit measurements. In this work, we prove that almost all n-qubit target states, including those with exponential circuit complexity, can be certified from only O(n^2) single-qubit measurements. This result is established by a new technique that relates certification to the mixing time of a random walk. Our protocol has applications for benchmarking quantum systems, for optimizing quantum circuits to generate a desired target state, and for learning and verifying neural networks, tensor networks, and various other representations of quantum states using only single-qubit measurements. We show that such verified representations can be used to efficiently predict highly non-local properties that would otherwise require an exponential number of measurements. We demonstrate these applications in numerical experiments with up to 120 qubits, and observe advantage over existing methods such as cross-entropy benchmarking (XEB).

[6]  arXiv:2404.07344 (cross-list from cs.RO) [pdf, other]
Title: Interactive Learning of Physical Object Properties Through Robot Manipulation and Database of Object Measurements
Comments: 8 pages, 8 figures
Subjects: Robotics (cs.RO); Artificial Intelligence (cs.AI); Information Theory (cs.IT)

This work presents a framework for automatically extracting physical object properties, such as material composition, mass, volume, and stiffness, through robot manipulation and a database of object measurements. The framework involves exploratory action selection to maximize learning about objects on a table. A Bayesian network models conditional dependencies between object properties, incorporating prior probability distributions and uncertainty associated with measurement actions. The algorithm selects optimal exploratory actions based on expected information gain and updates object properties through Bayesian inference. Experimental evaluation demonstrates effective action selection compared to a baseline and correct termination of the experiments if there is nothing more to be learned. The algorithm proved to behave intelligently when presented with trick objects with material properties in conflict with their appearance. The robot pipeline integrates with a logging module and an online database of objects, containing over 24,000 measurements of 63 objects with different grippers. All code and data are publicly available, facilitating automatic digitization of objects and their physical properties through exploratory manipulations.

[7]  arXiv:2404.07377 (cross-list from cs.LG) [pdf, other]
Title: Deep Generative Sampling in the Dual Divergence Space: A Data-efficient & Interpretative Approach for Generative AI
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Computer Vision and Pattern Recognition (cs.CV); Information Theory (cs.IT)

Building on the remarkable achievements in generative sampling of natural images, we propose an innovative challenge, potentially overly ambitious, which involves generating samples of entire multivariate time series that resemble images. However, the statistical challenge lies in the small sample size, sometimes consisting of a few hundred subjects. This issue is especially problematic for deep generative models that follow the conventional approach of generating samples from a canonical distribution and then decoding or denoising them to match the true data distribution. In contrast, our method is grounded in information theory and aims to implicitly characterize the distribution of images, particularly the (global and local) dependency structure between pixels. We achieve this by empirically estimating its KL-divergence in the dual form with respect to the respective marginal distribution. This enables us to perform generative sampling directly in the optimized 1-D dual divergence space. Specifically, in the dual space, training samples representing the data distribution are embedded in the form of various clusters between two end points. In theory, any sample embedded between those two end points is in-distribution w.r.t. the data distribution. Our key idea for generating novel samples of images is to interpolate between the clusters via a walk as per gradients of the dual function w.r.t. the data dimensions. In addition to the data efficiency gained from direct sampling, we propose an algorithm that offers a significant reduction in sample complexity for estimating the divergence of the data distribution with respect to the marginal distribution. We provide strong theoretical guarantees along with an extensive empirical evaluation using many real-world datasets from diverse domains, establishing the superiority of our approach w.r.t. state-of-the-art deep learning methods.

[8]  arXiv:2404.07425 (cross-list from eess.SP) [pdf, ps, other]
Title: Precoder Design for User-Centric Network Massive MIMO with Matrix Manifold Optimization
Comments: 13 pages, 9 figures, journal
Subjects: Signal Processing (eess.SP); Information Theory (cs.IT)

In this paper, we investigate the precoder design for user-centric network (UCN) massive multiple-input multiple-output (mMIMO) downlink with matrix manifold optimization. In UCN mMIMO systems, each user terminal (UT) is served by a subset of base stations (BSs) instead of all the BSs, facilitating the implementation of the system and lowering the dimension of the precoders to be designed. By proving that the precoder set satisfying the per-BS power constraints forms a Riemannian submanifold of a linear product manifold, we transform the constrained precoder design problem in Euclidean space to an unconstrained one on the Riemannian submanifold. Riemannian ingredients, including orthogonal projection, Riemannian gradient, retraction and vector transport, of the problem on the Riemannian submanifold are further derived, with which the Riemannian conjugate gradient (RCG) design method is proposed for solving the unconstrained problem. The proposed method avoids the inverses of large dimensional matrices, which is beneficial in practice. The complexity analyses show the high computational efficiency of RCG precoder design. Simulation results demonstrate the numerical superiority of the proposed precoder design and the high efficiency of the UCN mMIMO system.

[9]  arXiv:2404.07721 (cross-list from eess.SP) [pdf, other]
Title: Trainable Joint Channel Estimation, Detection and Decoding for MIMO URLLC Systems
Comments: 17 pages, 12 figures, accepted by IEEE Transactions on Wireless Communications
Subjects: Signal Processing (eess.SP); Information Theory (cs.IT)

The receiver design for multi-input multi-output (MIMO) ultra-reliable and low-latency communication (URLLC) systems can be a tough task due to the use of short channel codes and few pilot symbols. Consequently, error propagation can occur in traditional turbo receivers, leading to performance degradation. Moreover, the processing delay induced by information exchange between different modules may also be undesirable for URLLC. To address the issues, we advocate to perform joint channel estimation, detection, and decoding (JCDD) for MIMO URLLC systems encoded by short low-density parity-check (LDPC) codes. Specifically, we develop two novel JCDD problem formulations based on the maximum a posteriori (MAP) criterion for Gaussian MIMO channels and sparse mmWave MIMO channels, respectively, which integrate the pilots, the bit-to-symbol mapping, the LDPC code constraints, as well as the channel statistical information. Both the challenging large-scale non-convex problems are then solved based on the alternating direction method of multipliers (ADMM) algorithms, where closed-form solutions are achieved in each ADMM iteration. Furthermore, two JCDD neural networks, called JCDDNet-G and JCDDNet-S, are built by unfolding the derived ADMM algorithms and introducing trainable parameters. It is interesting to find via simulations that the proposed trainable JCDD receivers can outperform the turbo receivers with affordable computational complexities.

Replacements for Fri, 12 Apr 24

[10]  arXiv:2304.00201 (replaced) [pdf, ps, other]
Title: Precoder Design for Massive MIMO Downlink with Matrix Manifold Optimization
Comments: 16 pages, 11 figures, journal
Journal-ref: IEEE Transactions on Signal Processing, vol. 72, pp. 1065-1080, 2024
Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
[11]  arXiv:2304.00848 (replaced) [pdf, other]
Title: Towards Goal-Oriented Semantic Communications: New Metrics, Open Challenges, and Future Research Directions
Subjects: Information Theory (cs.IT)
[12]  arXiv:2311.04451 (replaced) [pdf, ps, other]
Title: Pseduo-Random and de Bruijn Array Codes
Authors: Tuvi Etzion
Subjects: Information Theory (cs.IT)
[13]  arXiv:2312.13203 (replaced) [pdf, other]
Title: RIShield: Enabling Electromagnetic Blackout in Radiation-Sensitive Environments
Subjects: Information Theory (cs.IT); Emerging Technologies (cs.ET); Signal Processing (eess.SP)
[14]  arXiv:2403.00556 (replaced) [pdf, other]
Title: Nearest-Neighbours Estimators for Conditional Mutual Information
Comments: 11 pages, 6 figures
Subjects: Information Theory (cs.IT)
[15]  arXiv:2403.04435 (replaced) [pdf, other]
Title: Pilot Spoofing Attack on the Downlink of Cell-Free Massive MIMO: From the Perspective of Adversaries
Subjects: Information Theory (cs.IT)
[16]  arXiv:2404.05538 (replaced) [pdf, other]
Title: Cell-Free Multi-User MIMO Equalization via In-Context Learning
Subjects: Information Theory (cs.IT); Machine Learning (cs.LG); Signal Processing (eess.SP)
[17]  arXiv:2404.06880 (replaced) [pdf, ps, other]
Title: Joint Active And Passive IRS Aided Wireless Communication: Elements Allocation and Achievable Rate
Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
[18]  arXiv:2010.12998 (replaced) [pdf, other]
Title: Demystifying Why Local Aggregation Helps: Convergence Analysis of Hierarchical SGD
Comments: 36 pages, in AAAI 2022
Subjects: Machine Learning (cs.LG); Distributed, Parallel, and Cluster Computing (cs.DC); Information Theory (cs.IT); Optimization and Control (math.OC)
[19]  arXiv:2402.07476 (replaced) [pdf, other]
Title: Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
Comments: Stronger result: constant degree complexes and without product-expansion conjecture
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Information Theory (cs.IT)
[ total of 19 entries: 1-19 ]
[ showing up to 2000 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)

Links to: arXiv, form interface, find, math, recent, 2404, contact, help  (Access key information)