Information Theory
See recent articles
Showing new listings for Thursday, 1 May 2025
- [1] arXiv:2504.21178 [pdf, html, other]
-
Title: Differentially Private Secure Multiplication with Erasures and AdversariesComments: A short version of this article was accepted at ISIT 2025Subjects: Information Theory (cs.IT)
We consider a private distributed multiplication problem involving N computation nodes and T colluding nodes. Shamir's secret sharing algorithm provides perfect information-theoretic privacy, while requiring an honest majority, i.e., N \ge 2T + 1. Recent work has investigated approximate computation and characterized privacy-accuracy trade-offs for the honest minority setting N \le 2T for real-valued data, quantifying privacy leakage via the differential privacy (DP) framework and accuracy via the mean squared error. However, it does not incorporate the error correction capabilities of Shamir's secret-sharing algorithm. This paper develops a new polynomial-based coding scheme for secure multiplication with an honest minority, and characterizes its achievable privacy-utility tradeoff, showing that the tradeoff can approach the converse bound as closely as desired. Unlike previous schemes, the proposed scheme inherits the capability of the Reed-Solomon (RS) code to tolerate erasures and adversaries. We utilize a modified Berlekamp-Welch algorithm over the real number field to detect adversarial nodes.
- [2] arXiv:2504.21234 [pdf, html, other]
-
Title: Realizing Quantum Wireless Sensing Without Extra Reference Sources: Architecture, Algorithm, and Sensitivity MaximizationComments: A self-heterodyne sensing approach, which equivalents to an atomic autocorrelator, is proposed to enable quantum wireless sensingSubjects: Information Theory (cs.IT)
Rydberg Atomic REceivers (RAREs) have shown compelling advantages in the precise measurement of radio-frequency signals, empowering quantum wireless sensing. Existing RARE-based sensing systems primarily rely on the heterodyne-sensing technique, which introduces an extra reference source to serve as the atomic mixer. However, this approach entails a bulky transceiver architecture and is limited in the supportable sensing bandwidth. To address these challenges, we propose self-heterodyne sensing, a novel concept where the self-interference caused by the transmitter acts as the reference signal. It is shown that a self-heterodyne RARE functions as an atomic autocorrelator, eliminating the need for extra reference sources while supporting sensing signals with much wider bandwidth than the conventional heterodyne-sensing method. Next, a two-stage algorithm is devised to estimate the target range for self-heterodyne RAREs. This algorithm is shown to closely approach the Cramer-Rao lower bound. Furthermore, we introduce the power-trajectory (P-trajectory) design for RAREs, which maximizes the sensing sensitivity through time-varying transmission power optimization. A heuristic P-trajectory is developed to capture the profile of the asymptotically optimal time-varying power. This design is then extended to practical P-trajectories by incorporating the transmitter power constraints. Numerical results validate the superiority of the proposed designs for quantum wireless sensing.
- [3] arXiv:2504.21297 [pdf, html, other]
-
Title: Participatory AI, Public Sector AI, Differential Privacy, Conversational Interfaces, Explainable AI, Citizen Engagement in AISubjects: Information Theory (cs.IT); Artificial Intelligence (cs.AI); Computers and Society (cs.CY); Emerging Technologies (cs.ET)
This paper introduces a conversational interface system that enables participatory design of differentially private AI systems in public sector applications. Addressing the challenge of balancing mathematical privacy guarantees with democratic accountability, we propose three key contributions: (1) an adaptive $\epsilon$-selection protocol leveraging TOPSIS multi-criteria decision analysis to align citizen preferences with differential privacy (DP) parameters, (2) an explainable noise-injection framework featuring real-time Mean Absolute Error (MAE) visualizations and GPT-4-powered impact analysis, and (3) an integrated legal-compliance mechanism that dynamically modulates privacy budgets based on evolving regulatory constraints. Our results advance participatory AI practices by demonstrating how conversational interfaces can enhance public engagement in algorithmic privacy mechanisms, ensuring that privacy-preserving AI in public sector governance remains both mathematically robust and democratically accountable.
- [4] arXiv:2504.21321 [pdf, html, other]
-
Title: Universal Encryption of Individual Sequences Under Maximal LeakageComments: 21 pages; submitted for publicationSubjects: Information Theory (cs.IT)
We consider the Shannon cipher system in the framework of individual sequences and finite-state encrypters under the metric of maximal leakage of information. A lower bound and an asymptotically matching upper bound on the leakage are derived, which lead to the conclusion that asymptotically minimum leakage can be attained by Lempel-Ziv compression followed by one-time pad encryption of the compressed bit-stream.
- [5] arXiv:2504.21466 [pdf, html, other]
-
Title: Semantic-aided Parallel Image Transmission Compatible with Practical SystemComments: This paper has been accepted by IEEE Transactions on Wireless CommunicationsSubjects: Information Theory (cs.IT)
In this paper, we propose a novel semantic-aided image communication framework for supporting the compatibility with practical separation-based coding architectures. Particularly, the deep learning (DL)-based joint source-channel coding (JSCC) is integrated into the classical separate source-channel coding (SSCC) to transmit the images via the combination of semantic stream and image stream from DL networks and SSCC respectively, which we name as parallel-stream transmission. The positive coding gain stems from the sophisticated design of the JSCC encoder, which leverages the residual information neglected by the SSCC to enhance the learnable image features. Furthermore, a conditional rate adaptation mechanism is introduced to adjust the transmission rate of semantic stream according to residual, rendering the framework more flexible and efficient to bandwidth allocation. We also design a dynamic stream aggregation strategy at the receiver, which provides the composite framework with more robustness to signal-to-noise ratio (SNR) fluctuations in wireless systems compared to a single conventional codec. Finally, the proposed framework is verified to surpass the performance of both traditional and DL-based competitors in a large range of scenarios and meanwhile, maintains lightweight in terms of the transmission and computational complexity of semantic stream, which exhibits the potential to be applied in real systems.
- [6] arXiv:2504.21632 [pdf, html, other]
-
Title: Fast Sign Retrieval via Sub-band Convolution: An Elementary Extension of Binary ClassificationSubjects: Information Theory (cs.IT); Image and Video Processing (eess.IV)
To efficiently compress the sign information of images, we address a sign retrieval problem for the block-wise discrete cosine transformation~(DCT): reconstruction of the signs of DCT coefficients from their amplitudes. To this end, we propose a fast sign retrieval method on the basis of binary classification machine learning. We first introduce 3D representations of the amplitudes and signs, where we pack amplitudes/signs belonging to the same frequency band into a 2D slice, referred to as the sub-band block. We then retrieve the signs from the 3D amplitudes via binary classification, where each sign is regarded as a binary label. We implement a binary classification algorithm using convolutional neural networks, which are advantageous for efficiently extracting features in the 3D amplitudes. Experimental results demonstrate that our method achieves accurate sign retrieval with an overwhelmingly low computation cost.
- [7] arXiv:2504.21719 [pdf, html, other]
-
Title: Sionna RT: Technical ReportSubjects: Information Theory (cs.IT); Artificial Intelligence (cs.AI); Signal Processing (eess.SP)
Sionna is an open-source, GPU-accelerated library that, as of version 0.14, incorporates a ray tracer for simulating radio wave propagation. A unique feature of Sionna RT is differentiability, enabling the calculation of gradients for the channel impulse responses (CIRs), radio maps, and other related metrics with respect to system and environmental parameters, such as material properties, antenna patterns, and array geometries. The release of Sionna 1.0 provides a complete overhaul of the ray tracer, significantly improving its speed, memory efficiency, and extensibility. This document details the algorithms employed by Sionna RT to simulate radio wave propagation efficiently, while also addressing their current limitations. Given that the computation of CIRs and radio maps requires distinct algorithms, these are detailed in separate sections. For CIRs, Sionna RT integrates shooting and bouncing of rays (SBR) with the image method and uses a hashing-based mechanism to efficiently eliminate duplicate paths. Radio maps are computed using a purely SBR-based approach.
- [8] arXiv:2504.21816 [pdf, html, other]
-
Title: Enumeration of minimum weight codewords of affine Cartesian codesComments: 31 pagesSubjects: Information Theory (cs.IT); Combinatorics (math.CO)
Affine Cartesian codes were first discussed by Geil and Thomsen in 2013 in a broader framework and were formally introduced by López, Rentería-Márquez and Villarreal in 2014. These are linear error-correcting codes obtained by evaluating polynomials at points of a Cartesian product of subsets of the given finite field. They can be viewed as a vast generalization of Reed-Muller codes. In 1970, Delsarte, Goethals and MacWilliams gave a %characterization of minimum weight codewords of Reed-Muller codes and also formula for the minimum weight codewords of Reed-Muller codes. Carvalho and Neumann in 2020 considered affine Cartesian codes in a special setting where the subsets in the Cartesian product are nested subfields of the given finite field, and gave a characterization of their minimum weight codewords. We use this to give an explicit formula for the number of minimum weight codewords of affine Cartesian codes in the case of nested subfields. This is seen to unify the known formulas for the number of minimum weight codewords of Reed-Solomon codes and Reed-Muller codes.
New submissions (showing 8 of 8 entries)
- [9] arXiv:2504.21182 (cross-list from cs.CR) [pdf, html, other]
-
Title: Federated One-Shot Learning with Data Privacy and Objective-HidingSubjects: Cryptography and Security (cs.CR); Distributed, Parallel, and Cluster Computing (cs.DC); Information Theory (cs.IT); Machine Learning (cs.LG); Machine Learning (stat.ML)
Privacy in federated learning is crucial, encompassing two key aspects: safeguarding the privacy of clients' data and maintaining the privacy of the federator's objective from the clients. While the first aspect has been extensively studied, the second has received much less attention.
We present a novel approach that addresses both concerns simultaneously, drawing inspiration from techniques in knowledge distillation and private information retrieval to provide strong information-theoretic privacy guarantees.
Traditional private function computation methods could be used here; however, they are typically limited to linear or polynomial functions. To overcome these constraints, our approach unfolds in three stages. In stage 0, clients perform the necessary computations locally. In stage 1, these results are shared among the clients, and in stage 2, the federator retrieves its desired objective without compromising the privacy of the clients' data. The crux of the method is a carefully designed protocol that combines secret-sharing-based multi-party computation and a graph-based private information retrieval scheme. We show that our method outperforms existing tools from the literature when properly adapted to this setting. - [10] arXiv:2504.21473 (cross-list from math.LO) [pdf, html, other]
-
Title: Invariant Bridges Between Four Successive Points: A New Tool for Data CodingComments: 12 pages, submitted to arXivSubjects: Logic (math.LO); Information Theory (cs.IT)
We introduce a simple yet powerful invariant relation connecting four successive terms of a class of exponentially decaying alternating functions. Specifically, for the sequence defined by f(n) = ((1/2)^n + (-1)^n) / n, we prove that the combination [(n-2)f(n-2) + (n-3)f(n-3)] / [n f(n) + (n-1)f(n-1)] is universally equal to 4 for all integers n >= 4. This invariant bridge across four points opens new possibilities for predictive coding, data compression, and error detection. We demonstrate how the relation can be used to reconstruct missing data, verify data integrity, and reduce redundancy in data streams with minimal computational overhead. The simplicity and universality of this invariant make it a promising tool for a wide range of applications in information theory and coding systems.
- [11] arXiv:2504.21638 (cross-list from quant-ph) [pdf, html, other]
-
Title: A note on the quantum Wielandt inequalityComments: 7 pages; the author was supported in part by US National Science Foundation Grant No. DMS-2153946; comments welcomeSubjects: Quantum Physics (quant-ph); Information Theory (cs.IT); Operator Algebras (math.OA)
In this note, we show how to extend operator algebraic methods introduced by Rahaman to prove that the index of primitivity of any primitive Schwarz map is at most $2(D-1)^2$, where $D$ is the dimension of the underlying matrix algebra. This inequality was first proved by Rahaman for Schwarz maps which were both unital and trace preserving. We show here that the assumption of unitality is automatic (up to normalization) for primitive Schwarz maps, but, in general, not all primitive unital Schwarz maps are trace preserving. Therefore, the precise purpose of this note is to showcase how to apply the proof of Rahaman to arbitrary primitive Schwarz maps. As a corollary of this theorem, we show that the index of primitivity of any primitive 2-positive map is at most $2(D-1)^2$, so in particular this bound holds for arbitrary primitive completely positive maps. We briefly discuss of how this relates to a conjecture of Perez-Garcia, Verstraete, Wolf and Cirac concerning properties of parent Hamiltonians of matrix product states.
- [12] arXiv:2504.21707 (cross-list from cs.LG) [pdf, html, other]
-
Title: Recursive KL Divergence Optimization: A Dynamic Framework for Representation LearningSubjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Information Theory (cs.IT)
We propose a generalization of modern representation learning objectives by reframing them as recursive divergence alignment processes over localized conditional distributions While recent frameworks like Information Contrastive Learning I-Con unify multiple learning paradigms through KL divergence between fixed neighborhood conditionals we argue this view underplays a crucial recursive structure inherent in the learning process. We introduce Recursive KL Divergence Optimization RKDO a dynamic formalism where representation learning is framed as the evolution of KL divergences across data neighborhoods. This formulation captures contrastive clustering and dimensionality reduction methods as static slices while offering a new path to model stability and local adaptation. Our experiments demonstrate that RKDO offers dual efficiency advantages approximately 30 percent lower loss values compared to static approaches across three different datasets and 60 to 80 percent reduction in computational resources needed to achieve comparable results. This suggests that RKDOs recursive updating mechanism provides a fundamentally more efficient optimization landscape for representation learning with significant implications for resource constrained applications.
- [13] arXiv:2504.21787 (cross-list from math.ST) [pdf, html, other]
-
Title: Estimation of discrete distributions in relative entropy, and the deviations of the missing massComments: 54 pagesSubjects: Statistics Theory (math.ST); Information Theory (cs.IT); Machine Learning (cs.LG); Machine Learning (stat.ML)
We study the problem of estimating a distribution over a finite alphabet from an i.i.d. sample, with accuracy measured in relative entropy (Kullback-Leibler divergence). While optimal expected risk bounds are known, high-probability guarantees remain less well-understood. First, we analyze the classical Laplace (add-$1$) estimator, obtaining matching upper and lower bounds on its performance and showing its optimality among confidence-independent estimators. We then characterize the minimax-optimal high-probability risk achievable by any estimator, which is attained via a simple confidence-dependent smoothing technique. Interestingly, the optimal non-asymptotic risk contains an additional logarithmic factor over the ideal asymptotic risk. Next, motivated by scenarios where the alphabet exceeds the sample size, we investigate methods that adapt to the sparsity of the distribution at hand. We introduce an estimator using data-dependent smoothing, for which we establish a high-probability risk bound depending on two effective sparsity parameters. As part of the analysis, we also derive a sharp high-probability upper bound on the missing mass.
- [14] arXiv:2504.21845 (cross-list from quant-ph) [pdf, html, other]
-
Title: On the Efficacy of the Peeling Decoder for the Quantum Expander CodeJefrin Sharmitha Prabhu, Abhinav Vaishya, Shobhit Bhatnagar, Aryaman Manish Kolhe, V. Lalitha, P. Vijay KumarSubjects: Quantum Physics (quant-ph); Information Theory (cs.IT)
The problem of recovering from qubit erasures has recently gained attention as erasures occur in many physical systems such as photonic systems, trapped ions, superconducting qubits and circuit quantum electrodynamics. While several linear-time decoders for error correction are known, their error-correcting capability is limited to half the minimum distance of the code, whereas erasure correction allows one to go beyond this limit. As in the classical case, stopping sets pose a major challenge in designing efficient erasure decoders for quantum LDPC codes. In this paper, we show through simulation, that an attractive alternative here, is the use of quantum expander codes in conjunction with the peeling decoder that has linear complexity. We also discuss additional techniques including small-set-flip decoding, that can be applied following the peeling operation, to improve decoding performance and their associated complexity.
Cross submissions (showing 6 of 6 entries)
- [15] arXiv:2304.12290 (replaced) [pdf, html, other]
-
Title: Joint Message Detection and Channel Estimation for Unsourced Random Access in Cell-Free User-Centric Wireless NetworksComments: 54 pages, 9 figuresJournal-ref: IEEE Transactions on Information Theory, vol. 71, no. 5, pp. 3614-3643, 2025Subjects: Information Theory (cs.IT)
We consider unsourced random access (uRA) in a cell-free (CF) user-centric wireless network, where a large number of potential users compete for a random access slot, while only a finite subset is active. The random access users transmit codewords of length $L$ symbols from a shared codebook, which are received by $B$ geographically distributed radio units (RUs) equipped with $M$ antennas each. Our goal is to devise and analyze a \emph{centralized} decoder to detect the transmitted messages (without prior knowledge of the active users) and estimate the corresponding channel state information. A specific challenge lies in the fact that, due to the geographically distributed nature of the CF network, there is no fixed correspondence between codewords and large-scale fading coefficients (LSFCs). This makes current activity detection approaches which make use of this fixed LSFC-codeword association not directly applicable. To overcome this problem, we propose a scheme where the access codebook is partitioned in location-based subcodes, such that users in a particular location make use of the corresponding subcode. The joint message detection and channel estimation is obtained via a novel {\em Approximated Message Passing} (AMP) algorithm for a linear superposition of matrix-valued sources corrupted by noise. The statistical asymmetry in the fading profile and message activity leads to \emph{different statistics} for the matrix sources, which distinguishes the AMP formulation from previous cases. In the regime where the codebook size scales linearly with $L$, while $B$ and $M$ are fixed, we present a rigorous high-dimensional (but finite-sample) analysis of the proposed AMP algorithm. Exploiting this, we then present a precise (and rigorous) large-system analysis of the message missed-detection and false-alarm rates, as well as the channel estimation mean-square error.
- [16] arXiv:2404.10950 (replaced) [pdf, html, other]
-
Title: Alternating Optimization Approach for Computing $α$-Mutual Information and $α$-CapacitySubjects: Information Theory (cs.IT)
This study presents alternating optimization (AO) algorithms for computing $\alpha$-mutual information ($\alpha$-MI) and $\alpha$-capacity based on variational characterizations of $\alpha$-MI using a reverse channel. Specifically, we derive several variational characterizations of Sibson, Arimoto, Augustin--Csisz{\' a}r, and Lapidoth--Pfister MI and introduce novel AO algorithms for computing $\alpha$-MI and $\alpha$-capacity; their performances for computing $\alpha$-capacity are also compared. The comparison results show that the AO algorithm based on the Sibson MI's characterization has the fastest convergence speed.
- [17] arXiv:2407.07723 (replaced) [pdf, html, other]
-
Title: Lossless data compression by large modelsZiguang Li, Chao Huang, Xuliang Wang, Haibo Hu, Cole Wyeth, Dongbo Bu, Quan Yu, Wen Gao, Xingwu Liu, Ming LiComments: Published by Nature Machine Intelligence at this https URLJournal-ref: Nature Machine Intelligence, 2025, May 1Subjects: Information Theory (cs.IT); Artificial Intelligence (cs.AI)
Modern data compression methods are slowly reaching their limits after 80 years of research, millions of papers, and wide range of applications. Yet, the extravagant 6G communication speed requirement raises a major open question for revolutionary new ideas of data compression. We have previously shown all understanding or learning are compression, under reasonable assumptions. Large language models (LLMs) understand data better than ever before. Can they help us to compress data? The LLMs may be seen to approximate the uncomputable Solomonoff induction. Therefore, under this new uncomputable paradigm, we present LMCompress. LMCompress shatters all previous lossless compression algorithms, doubling the lossless compression ratios of JPEG-XL for images, FLAC for audios, and H.264 for videos, and quadrupling the compression ratio of bz2 for texts. The better a large model understands the data, the better LMCompress compresses.
- [18] arXiv:2409.14148 (replaced) [pdf, html, other]
-
Title: A New Upper Bound for Distributed Hypothesis Testing Using the Auxiliary Receiver ApproachSubjects: Information Theory (cs.IT)
This paper employs the add-and-subtract technique of the auxiliary receiver approach to establish a new upper bound for the distributed hypothesis testing problem. This new bound has fewer assumptions than the upper bound proposed by Rahman and Wagner, is at least as tight as the bound by Rahman and Wagner, and can outperform it in certain Gaussian settings. Conceptually speaking, unlike Rahman and Wagner, who view their additional receiver as side information, we view it as an auxiliary receiver and use a different manipulation for single-letterization.
- [19] arXiv:2410.10312 (replaced) [pdf, html, other]
-
Title: Achievable Second-Order Asymptotics for MAC and RAC with Additive Non-Gaussian NoiseSubjects: Information Theory (cs.IT)
We first study the two-user additive noise multiple access channel (MAC) where the noise distribution is arbitrary. For such a MAC, we use spherical codebooks and either joint nearest neighbor (JNN) or successive interference cancellation (SIC) decoding. Under both decoding methods, we derive second-order achievable rate regions and compare the finite blocklength performance between JNN and SIC decoding. Our results indicate that although the first-order rate regions of JNN and SIC decoding are identical, JNN decoding has better second-order asymptotic performance. When specialized to the Gaussian noise, we provide an alternative achievability proof to the result by MolavianJazi and Laneman (T-IT, 2015). Furthermore, we generalize our results to the random access channel (RAC) where neither the transmitters nor the receiver knows the user activity pattern. We use spherical-type codebooks and a rateless transmission scheme combining JNN/SIC decoding, and derive second-order achievability bounds. Comparing second-order achievability results of JNN and SIC decoding in a RAC, we show that JNN decoding achieves strictly larger first-order asymptotic rate. When specialized to Gaussian noise, our second-order asymptotic results recover the corresponding results of Yavas, Kostina, and Effros (T-IT, 2021) up to second-order.
- [20] arXiv:2501.10099 (replaced) [pdf, html, other]
-
Title: Several Representations of $α$-Mutual Information and Interpretations as Privacy Leakage MeasuresSubjects: Information Theory (cs.IT)
In this paper, we present several novel representations of $\alpha$-mutual information ($\alpha$-MI) in terms of R{\' e}nyi divergence and conditional R{\' e}nyi entropy. The representations are based on the variational characterizations of $\alpha$-MI using a reverse channel. Based on these representations, we provide several interpretations of the $\alpha$-MI as privacy leakage measures using generalized mean and gain functions. Further, as byproducts of the representations, we propose novel conditional R{\' e}nyi entropies that satisfy the property that conditioning reduces entropy and data-processing inequality.
- [21] arXiv:2501.10103 (replaced) [pdf, html, other]
-
Title: Lossless data compression at pragmatic ratesComments: 15 pagesSubjects: Information Theory (cs.IT)
The problem of variable-rate lossless data compression is considered, for codes with and without prefix constraints. Sharp bounds are derived for the best achievable compression rate of memoryless sources, when the excess-rate probability is required to be exponentially small in the blocklength. Accurate nonasymptotic expansions with explicit constants are obtained for the optimal rate, using tools from large deviations and Gaussian approximation. Examples are shown indicating that, in the small excess-rate-probability regime, the approximation to the fundamental limit of the compression rate suggested by these bounds is significantly more accurate than the approximations provided by either normal approximation or error exponents. The new bounds reinforce the crucial operational conclusion that, in applications where the blocklength is relatively short and where stringent guarantees are required on the rate, the best achievable rate is no longer close to the entropy. Rather, it is an appropriate, more pragmatic rate, determined via the inverse error exponent function and the blocklength.
- [22] arXiv:2501.11883 (replaced) [pdf, html, other]
-
Title: An Improved Lower Bound on Oblivious Transfer Capacity Using Polarization and InteractionComments: 7 pages, 1 figure. arXiv admin note: substantial text overlap with arXiv:2401.14965; v2 corrected typosSubjects: Information Theory (cs.IT)
We consider the oblivious transfer (OT) capacities of noisy channels against the passive adversary; this problem has not been solved even for the binary symmetric channel (BSC). In the literature, the general construction of OT has been known only for generalized erasure channels (GECs); for the BSC, we convert the channel to the binary symmetric erasure channel (BSEC), which is a special instance of the GEC, via alphabet extension and erasure emulation. In a previous paper by the authors, we derived an improved lower bound on the OT capacity of BSC by proposing a method to recursively emulate BSEC via interactive communication. In this paper, we introduce two new ideas of OT construction: (i) via ``polarization" and interactive communication, we recursively emulate GECs that are not necessarily a BSEC; (ii) in addition to the GEC emulation part, we also utilize interactive communication in the key agreement part of OT protocol. By these methods, we derive lower bounds on the OT capacity of BSC that are superior to the previous one for a certain range of crossover probabilities of the BSC. Via our new lower bound, we show that, at the crossover probability being zero, the slope of tangent of the OT capacity is unbounded.
- [23] arXiv:2501.14064 (replaced) [pdf, html, other]
-
Title: Switched Feedback for the Multiple-Access ChannelComments: To appear at the 2025 IEEE International Symposium on Information TheorySubjects: Information Theory (cs.IT)
A mechanism called switched feedback is introduced; under switched feedback, each channel output goes forward to the receiver(s) or back to the transmitter(s) but never both. By studying the capacity of the Multiple-Access Channel (MAC) with switched feedback, this work investigates the benefits of feedback, seeking to maximize that benefit under reliable and unreliable feedback scenarios. The study is used to explore the tradeoffs between cooperation and transmission in the context of communication systems. Results include upper and lower bounds on the capacity region of the MAC with switched feedback.
- [24] arXiv:2504.20513 (replaced) [pdf, html, other]
-
Title: Enhancing Binary Search via Overlapping PartitionsSubjects: Information Theory (cs.IT)
This paper considers the task of performing binary search under noisy decisions, focusing on the application of target area localization. In the presence of noise, the classical partitioning approach of binary search is prone to error propagation due to the use of strictly disjoint splits. While existing works on noisy binary search propose techniques such as query repetition or probabilistic updates to mitigate errors, they often lack explicit mechanisms to manage the trade-off between error probability and search complexity, with some providing only asymptotic guarantees. To address this gap, we propose a binary search framework with tunable overlapping partitions, which introduces controlled redundancy into the search process to enhance robustness against noise. We analyze the performance of the proposed algorithm in both discrete and continuous domains for the problem of area localization, quantifying how the overlap parameter impacts the trade-off between search tree depth and error probability. Unlike previous methods, this approach allows for direct control over the balance between reliability and efficiency. Our results emphasize the versatility and effectiveness of the proposed method, providing a principled extension to existing noisy search paradigms and enabling new insights into the interplay between partitioning strategies and measurement reliability.
- [25] arXiv:2410.02833 (replaced) [pdf, other]
-
Title: Asymmetry of the Relative Entropy in the Regularization of Empirical Risk MinimizationSubjects: Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG)
The effect of relative entropy asymmetry is analyzed in the context of empirical risk minimization (ERM) with relative entropy regularization (ERM-RER). Two regularizations are considered: $(a)$ the relative entropy of the measure to be optimized with respect to a reference measure (Type-I ERM-RER); and $(b)$ the relative entropy of the reference measure with respect to the measure to be optimized (Type-II ERM-RER). The main result is the characterization of the solution to the Type-II ERM-RER problem and its key properties. By comparing the well-understood Type-I ERM-RER with Type-II ERM-RER, the effects of entropy asymmetry are highlighted. The analysis shows that in both cases, regularization by relative entropy forces the solution's support to collapse into the support of the reference measure, introducing a strong inductive bias that negates the evidence provided by the training data. Finally, it is shown that Type-II regularization is equivalent to Type-I regularization with an appropriate transformation of the empirical risk function.
- [26] arXiv:2502.07170 (replaced) [pdf, html, other]
-
Title: Practical classical error correction for parity-encoded spin systemsComments: 20 pages, 11 figures, 1 Table, Major revisionSubjects: Quantum Physics (quant-ph); Information Theory (cs.IT)
Quantum annealing (QA) has emerged as a promising candidate for fast solvers for combinatorial optimization problems (COPs) and has attracted the interest of many researchers. Since COP is logically encoded in the Ising interaction among spins, its realization necessitates a spin system with all-to-all connectivity, presenting technical challenges in the physical implementation of large-scale QA devices. W. Lechner, P. Hauke, and P. Zoller proposed a parity-encoding (PE) architecture consisting of an expanded spin system with only local connectivity among them to circumvent this difficulty in developing near-future QA devices. They suggested that this architecture not only alleviates implementation challenges and enhances scalability but also possesses intrinsic fault tolerance. This paper proposes a practical decoding method tailored to correlated spin-flip errors in spin readout of PE architecture. Our work is based on the close connection between PE architecture and classical low-density parity-check (LDPC) codes. We show that the bit-flip (BF) decoding algorithm can correct independent and identically distributed errors in the readout of the SLHZ system with comparable performance to the belief propagation (BP) decoding algorithm. Then, we show evidence that the proposed BF decoding algorithm can efficiently correct correlated spinflip errors by simulation. The result suggests that introducing post-readout BF decoding reduces the computational cost of QA using the PE architecture and improves the performance of global optimal solution search. Our results emphasize the importance of the proper selection of decoding algorithms to exploit the inherent fault tolerance potential of the PE architecture.
- [27] arXiv:2502.15565 (replaced) [pdf, html, other]
-
Title: Benefits of Mutual Coupling in Dynamic Metasurface Antennas for Optimizing Wireless Communications -- Theory and Experimental ValidationComments: 13 pages, 7 figures, submitted to an IEEE JournalSubjects: Applied Physics (physics.app-ph); Information Theory (cs.IT); Signal Processing (eess.SP)
Dynamic metasurface antennas (DMAs) are a promising embodiment of next-generation reconfigurable antenna technology to realize base stations and access points with reduced cost and power consumption. A DMA is a thin structure patterned on its front with reconfigurable radiating metamaterial elements (meta-atoms) that are excited by waveguides or cavities. Mutual coupling between the meta-atoms can result in a strongly non-linear dependence of the DMA's radiation pattern on the configuration of its meta-atoms. However, besides the obvious algorithmic challenges of working with physics-compliant DMA models, it remains unclear how mutual coupling in DMAs influences the ability to achieve a desired wireless functionality. In this paper, we provide theoretical, numerical and experimental evidence that strong mutual coupling in DMAs increases the radiation pattern sensitivity to the DMA configuration and thereby boosts the available control over the radiation pattern, improving the ability to tailor the radiation pattern to the requirements of a desired wireless functionality. Counterintuitively, we hence encourage next-generation DMA implementations to enhance (rather than suppress) mutual coupling, in combination with suitable physics-compliant modeling and optimization. We expect the unveiled mechanism by which mutual coupling boosts the radiation pattern control to also apply to other reconfigurable antenna systems based on tunable lumped elements.
- [28] arXiv:2502.20373 (replaced) [pdf, html, other]
-
Title: Hamiltonian Learning at Heisenberg Limit for Hybrid Quantum SystemsSubjects: Quantum Physics (quant-ph); Information Theory (cs.IT); Numerical Analysis (math.NA); Atomic Physics (physics.atom-ph); Computational Physics (physics.comp-ph)
Hybrid quantum systems with different particle species are fundamental in quantum materials and quantum information science. In this work, we establish a rigorous theoretical framework proving that, given access to an unknown spin-boson type Hamiltonian, our algorithm achieves Heisenberg-limited estimation for all coupling parameters up to error $\epsilon$ with a total evolution time ${O}(\epsilon^{-1})$ using only ${O}({\rm polylog}(\epsilon^{-1}))$ measurements. It is also robust against small state preparation and measurement errors. In addition, we provide an alternative algorithm based on distributed quantum sensing, which significantly reduces the evolution time per measurement. To validate our method, we demonstrate its efficiency in hybrid Hamiltonian learning and spectrum learning, with broad applications in AMO, condensed matter and high energy physics. Our results provide a scalable and robust framework for precision Hamiltonian characterization in hybrid quantum platforms.
- [29] arXiv:2504.14659 (replaced) [pdf, html, other]
-
Title: Markovian Continuity of the MMSEComments: This work has been submitted to the IEEE for possible publication. Fixed typosSubjects: Signal Processing (eess.SP); Information Theory (cs.IT); Statistics Theory (math.ST)
Minimum mean square error (MMSE) estimation is widely used in signal processing and related fields. While it is known to be non-continuous with respect to all standard notions of stochastic convergence, it remains robust in practical applications. In this work, we review the known counterexamples to the continuity of the MMSE. We observe that, in these counterexamples, the discontinuity arises from an element in the converging measurement sequence providing more information about the estimand than the limit of the measurement sequence. We argue that this behavior is uncharacteristic of real-world applications and introduce a new stochastic convergence notion, termed Markovian convergence, to address this issue. We prove that the MMSE is, in fact, continuous under this new notion. We supplement this result with semi-continuity and continuity guarantees of the MMSE in other settings and prove the continuity of the MMSE under linear estimation.