Peer Revenue Publish or profit

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Computer Science Information Theory

cs.IT Watch Information Theory (sign in to use)

Sunday 13 September

Information Theory · Cross-listed from quant-ph

The classical capacity of generalized amplitude-damping channels and its strong-converse exponent

The classical capacity of a quantum channel generally requires regularization because input codewords may be entangled across channel uses. We remove this regularization for generalized amplitude-damping channels (GADCs) and determine their exact strong-converse exponent throughout the full parameter range. The exponent is a single-letter transform of the sandwiched Rényi Holevo information and is attained by product input codewords with collective decoding. The key ingredient is a decomposition of the joint output into positive operators whose triangular factors have identical scalar Gram matrices after norm compression. A sharp triangular Schatten-norm compression inequality then establishes maximum output norm multiplicativity for diagonally sandwiched GADCs tensored with arbitrary completely positive maps. This yields additivity of the sandwiched Rényi Holevo information at every order above one. Consequently, the classical capacity equals the known one-copy Holevo information and admits a scalar optimization. Thus, entangled input codewords improve neither the capacity nor the optimal exponential decay of decoding success above capacity.
Read the full abstract

Information Theory

Universal Estimation of the Fisher Information for Processes with Memory

The Fisher information matrix (FIM) determines the accuracy attainable in an estimation problem. For a parametric process with memory, it has a closed form only for narrow classes of models, and it cannot be computed when the model is available only as a simulator. This paper estimates the Fisher information rate of such a process, the per-observation limit of its FIM, from simulator output alone and without knowledge of the memory length. The construction uses the identity between the FIM and the local curvature of the Kullback–Leibler (KL) divergence. Directional divergence rates are estimated by context-tree weighting (CTW), and the matrix is recovered from them by least squares. We establish strong consistency in an iterated limit and a finite-sample bound, uniform over every working depth at least as large as the true memory length, which gives a mean error of order $n^{-1/3}$. The analysis also delivers a finite-sample rate for CTW-based estimation of the KL divergence rate. Experiments confirm the predicted exponents, show that the accuracy does not degrade as the working depth grows, and use the estimate to plan a sampling budget that attains a prescribed precision. The estimator stays accurate on a hidden-state source that has no finite memory length.
Read the full abstract

Information Theory

On the Generalized Packing and Covering Radii of Codes

The minimum distance and the covering radius are two fundamental properties of the code. Both have been extended: the former to the generalized Hamming weights hierarchy, and the latter to the generalized covering radii hierarchy. In both cases, the lowest level of the hierarchies corresponds to the classical minimum distance and covering radius, respectively. From a geometric point of view, the minimum distance of the code determines the packing radius, which is upper bounded by the covering radius. It was conjectured this relation extends to all other orders of the hierarchy, namely, that the generalized packing radii are upper bounded by the generalized covering radii of the same order. In this paper we prove this conjecture is true for the second order radii. We also prove the conjecture holds for all orders when the code rate is at most $3/5$. Finally, we show that for any code rate in $(0,1)$, for all sufficiently long codes the conjecture holds for all orders.
Read the full abstract

Information Theory

Channel-Aware Selection of Folded Bloom Filters for Distributed Systems

Periodic Bloom-filter transmission can impose substantial overhead in communication-constrained distributed systems. Lossless compression preserves membership behavior but provides a single transmission size, whereas established OR folding produces smaller representations with higher false-positive rates (FPRs) while preserving the no-false-negative property. This paper investigates channel-aware selection among OR-folded representations. The sender retains an unchanged canonical filter, constructs a catalog satisfying a maximum FPR, and selects the FPR-qualified representation with the largest retained length supported by the communication resources available at each reporting opportunity. Unlike folding driven principally by cardinality and false-positive constraints, selection is driven by time-varying communication conditions. Using two phishing URL datasets, the framework is evaluated under Five-State Markov Capacity, Gilbert–Elliott burst-error, and Rayleigh block-fading models. Channel-aware folding improves communication efficiency and receiver freshness relative to complete-filter and lossless-compression baselines when communication opportunities vary substantially. Under the more favorable Gilbert–Elliott model, it remains competitive in efficiency while maintaining the freshest receiver state. These results show that FPR-qualified folded views provide useful transmission operating points when a recent lower-fidelity update is preferable to delaying a larger representation.
Read the full abstract

Information Theory

Hermitian Duality and Syndrome Structure of CSS-Type Codes over the ring $\mathbb{Z}_q[i]$

We study the algebraic structure of principal ideal codes and CSS-type stabilizer constructions over the ring $ R_q=\mathbb Z_q[i],$ where every prime divisor of $q$ is congruent to $1$ modulo $4$. Although such ring-based constructions have recently been considered in the context of classical and quantum error correction, the precise relationship among principal ideal cardinalities, Hermitian duality, algebraic cosets, and stabilizer syndromes requires further structural analysis. We obtain cardinality formulas for principal ideals and their annihilators. For a length-one principal ideal code $C=\langle\alpha\rangle$, we show that its Hermitian dual is $ C^{\perp_H}=\operatorname{Ann}(\sigma(\alpha)). $ For nested codes satisfying $ C_2^{\perp_H}\subseteq C_1\subseteq C_2, $ we determine the corresponding CSS-type stabilizer and prove that the kernel of the physical $X$-error syndrome map is $ \ker(\operatorname{Syn}_X)=C_2. $ Consequently, $C_2/C_1$ parametrizes logical $X$-operator classes and $R_q^n/C_2$ parametrizes physical $X$-error syndrome classes. Using this syndrome quotient, we construct a transversal of $C_2$ in $R_q^n$ whose elements have pairwise distinct physical $X$-error syndromes. The corresponding $X$-type error family is correctable by stabilizer syndrome measurement, yielding a syndrome-based recovery procedure that is consistent with the stabilizer structure. Explicit examples illustrate the resulting duality, cardinality, and syndrome structure.
Read the full abstract

Information Theory

Dependency, Compression, and Synergy: A Unified Information-Theoretic View of Multimodal Learning

Recent advances in multimodal foundation models have intensified the need to understand how different modalities share, preserve, and complement information. Mutual Information (MI), the Information Bottleneck (IB), and Partial Information Decomposition (PID) provide complementary perspectives, yet existing studies often treat them as isolated tools. This survey presents an information-theoretic perspective connecting these principles as progressively refined views of multimodal information processing: MI characterizes inter-modal dependency, IB explains task-oriented information preservation under compression, and PID decomposes preserved information into redundancy, uniqueness, and synergy. We review 170 recent studies (2018–2026) and 12 foundational works, organizing multimodal learning around four challenges: cross-modal alignment, information-efficient fusion, interaction-type characterization, and scaling to multimodal foundation models. Rather than using application domains as primary taxonomy axes, we interpret healthcare, robotics, recommendation systems, affective computing, and wireless communications as empirical validations of these information principles. Beyond taxonomy, we organize existing multimodal paradigms within a single information-theoretic coordinate system – the Generalized Multimodal Information Lagrangian – in which they occupy exact or approximate parameter corners, and whose unoccupied regions name candidate method families the literature has not yet built. We further discuss how emerging multimodal foundation models instantiate these principles at scale and identify open challenges including scalable information estimation in high-dimensional settings, standardized evaluation across information-theoretic methods, combinatorial complexity of multimodal PID, and the transition from post-hoc information analysis toward information-aware multimodal learning.
Read the full abstract

All authors Liangjian Wen, Linjie Li, Jiang Duan, Yong Dai, Jianzhuang Liu, Zhao Kang

Information Theory

Successive Refinement Under Strong-Sense Perfect Perception

We revisit a multiterminal lossy source coding problem named successive refinement and derive the rate-distortion-perception region under the strong-sense perfect perception constraint in the presence of unlimited common randomness. Specifically, in successive refinement, one aims to compress a source sequence and allows two distinct decoders to recover the source sequence at different distortion levels. By imposing the strong-sense perfect perception constraint, our results refine the previous result by analyzing the impact of the perceptual quality. Our achievability proof is inspired by output constrained lossy source coding and our converse proof adapts the proof steps of the standard successive refinement problem. Furthermore, we provide a numerical example of the Bernoulli source to illustrate our result and show that the Bernoulli source under Hamming distortion is successively refinable even with the strong-sense perfect perception constraint.
Read the full abstract

All authors Yu Yang, Changhong Liu, Weijie Yuan, Lin Zhou

Saturday 12 September

Information Theory

Linear Programming Bounds for Locally Recovery Codes II

We give a polynomial-size linear programming bound for $q$-ary all-symbol locally recoverable codes with locality parameters $(r,\delta)$, without assuming linearity. The key idea is to keep, for every ordered pair of codewords and every selected recovery view, the joint Hamming weight on the helper set, the recovered coordinate, and the rest of the code – rather than collapsing this triple into a single distance, as earlier formulations do. Averaging this three-block distribution over recovery views of the same length yields exact identities linking it to the global distance distribution, together with nonnegative product-Krawtchouk constraints that encode locality and spectral positivity simultaneously. The resulting LP has polynomially many variables, its optimum dominates the ordinary Delsarte bound, and an earlier outside-distance formulation, the convex-hull bound of Li–Wei–Xiong, and the dual-based bound of Gruica–Jany–Ravagnani all arise from it as coarser marginals. Exact rational certificates over $q=2,3,4$ show the bound is strictly stronger than the best of these prior LPs in thirteen of fifteen tested cases, pinning down seven exact maximum code sizes and twelve exact maximum linear dimensions.
Read the full abstract

Information Theory · Cross-listed from stat.ME

Finite-Sample FDR Control for Greedy Aggregation over Networks

Distributed multiple testing asks $N$ sites, each holding p-values for its own hypotheses, to control the false discovery rate (FDR) of the discoveries made across the whole network while communicating only a small number of bits. Greedy interval aggregation (Pournaderi and Xiang, IEEE TSIPN, 2023) meets the communication budget but controls FDR only asymptotically, and its FDR can exceed the target at finite sample sizes; the same interval counts both select the rejection regions and calibrate the stopping rule, which biases the selected interval densities upward. We propose budgeted BONuS-GA: each site mixes synthetic uniform p-values into its data, the center ranks candidate p-value intervals across sites using the pooled counts, and each site's false discoveries are estimated from its own synthetic counts under a per-site share of the level. The procedure needs no knowledge of the null proportions, uses every p-value for both selection and inference, and controls $FDR\le\alpha$ at every sample size for any fixed assignment of hypotheses to sites, assuming only that the null p-values are independent uniforms, independent of the non-null p-values. It keeps the original $O(\sqrt m\log m)$ communication, $m$ being the total number of p-values, when $N=O(\sqrt m)$. We also give a sample-splitting alternative, cross-fit greedy aggregation, with finite-sample control under a random-site model, and we quantify the selection bias behind the original procedure's failure. In a monitoring-network simulation the budgeted procedure retains most of the power of its heuristic counterpart at moderate-to-large site sizes.
Read the full abstract

Information Theory

Beam Squint and Aperture–Bandwidth Limitations in Wideband RIS-Assisted THz Links

This paper analyzes the ergodic rate of a wideband reconfigurable intelligent surface (RIS)-assisted terahertz link under beam squint and finite-resolution phase control. Independent Rayleigh fading on the two RIS-assisted hops produces double-Rayleigh cascaded amplitudes. Exact second- and fourth-order channel moments are derived by incorporating the frequency-dependent array response and phase-quantization errors. Moment matching then provides a Gamma approximation for the received power on each subcarrier and a tractable closed-form approximation for the wideband ergodic rate. A first-null bandwidth approximation characterizes the aperture–bandwidth limitation of frequency-flat RIS control. Monte Carlo simulations validate the analytical framework.
Read the full abstract

All authors Waqas Khalid, Chiew Foong Kwong, David Chieng, Qianyu Liu

Information Theory · Cross-listed from quant-ph

No cardinality bound for squashed entanglement

Squashed entanglement is an additive bipartite entanglement measure. For a state $\rho_{AB}$, it is defined as the infimum of all conditional mutual information $I(A:B\mid E)$ evaluated on extensions $\rho_{ABE}$. It was unresolved whether there is a bound on the dimension of the conditioning system, $E$, needed for this optimization. We show that no such cardinality bound is possible. Explicitly, we find that the squashed entanglement for a partially dephased Bell pair on two qubits cannot be achieved for any finite dimensional extension $E$. A crucial ingredient of this proof is a direct sum step, which in a sense, symmetrizes two purifying systems while keeping the conditional mutual information unchanged and the coherence no worse.
Read the full abstract

Information Theory

Polarforming-Enabled Power-Splitting SWIPT: A GNN-Based Optimization Approach

Simultaneous wireless information and power transfer (SWIPT) is a critical technology for the future of the Internet of Things (IoT). However, ensuring a stable power supply in such networks remains a significant challenge. This work introduces dynamic polarization control as an additional degree of freedom (DoF) in SWIPT systems. We propose a system where both the base station (BS) and the users can adjust their antenna polarization, a technique known as polarforming. In addition, each user device is capable of splitting the incident signal to perform simultaneous information decoding (ID) and energy harvesting (EH). The resulting non-convex optimization, with many coupled variables, is solved using a graph neural network (GNN) that learns the sub-optimal beamforming, polarization, and power-splitting variables. Simulation results demonstrate that the proposed GNN-based dynamic polarforming optimization significantly outperforms fixed-polarization schemes, particularly under imperfect channel state information (CSI). Moreover, joint polarforming and GNN-based optimization maintain robust SWIPT performance under both polarization mismatch and imperfect CSI.
Read the full abstract

All authors Hamed Aghaei-Karkaj, Kamran Ebrahimi, Zahra Mehrzad, Mohammad Robat Mili, Symeon Chatzinotas, Ioannis Krikidis

Information Theory

Finite-Mask Gaussian-Process Reconstruction on a Periodic Sensor Ring: Mask-Geometry Dependence, Fourier-Mode Coupling, and Posterior Trace

We analyze how an arbitrary observation mask on a finite periodic ring of equally spaced sensors affects the posterior covariance, Fourier-mode coupling, and normalized posterior trace in Gaussian-process reconstruction. Under a rotationally stationary prior and homogeneous independent measurement noise, complete observation gives independent scalar posterior formulas for the Fourier modes. For an arbitrary mask, however, the matrix $Q_M=F D_MF^\ast$ is generally non-diagonal; its off-diagonal entries are finite Fourier components of the realized mask and couple modes in the posterior precision. Consequently, masks with the same unavailable-channel fraction can have different normalized posterior traces because their geometries differ. A dimensionless 64-channel synthetic benchmark illustrates this finite-matrix effect. A circumferential array of equally spaced wall-mounted microphones at a fixed axial station of a circular fan or compressor duct provides one concrete mechanical-engineering interpretation: failed, saturated, corrupted, or dropped-out channels form the observation mask. The analysis is a finite-dimensional reference calculation under the stated rotational-stationarity and common-noise assumptions, not a performance claim for a nonuniform or unequally instrumented operating duct.
Read the full abstract

Information Theory

GNN-Based Polarforming for Multi-User MISO Short-Packet URLLC under Imperfect CSI

This paper investigates polarization-aware transmission for multi-user multiple-input single-output (MU-MISO) short-packet ultra-reliable low-latency communications (URLLC) under imperfect channel state information (CSI). We consider a system in which the base station (BS) and users are equipped with polarization-reconfigurable antennas that enable adaptive polarization states through controllable polarization coefficients. A multi-objective optimization problem is formulated to jointly maximize the finite-blocklength (FBL) achievable sum rate and minimize the maximum decoding error probability (DEP), subject to transmit-power, latency, reliability, and discrete polarization-control constraints. The resulting multi-objective problem is scalarized using a normalized weighted-sum utility. To enable low-complexity online decision-making, a heterogeneous graph neural network (GNN) is developed to learn the joint mapping from estimated polarized CSI to digital beamforming and transmit/receive polarforming vectors (PFVs) while accounting for the system constraints. Numerical results demonstrate that the proposed GNN-based polarforming (PF) framework substantially improves the FBL sum rate while reducing the maximum DEP compared with conventional fixed-polarization schemes, particularly under channel depolarization and imperfect CSI. This highlights the potential of adaptive polarization control for reliable low-latency transmission.
Read the full abstract

All authors Zahra Mehrzad, Hamed Aghaei-Karkaj, Rahman Saadat Yeganeh, Kamran Ebrahimi, Mohammad Robat Mili, Symeon Chatzinotas, Ioannis Krikidis

Information Theory

A Novel Approach to Counterexamples of the Polujan-Pott Conjecture via Set-Partition Permutations

In this paper, we settle a conjecture of Polujan and Pott by constructing an explicit, infinite family of Maiorana–McFarland bent functions $f_t$ in $2(2^t-1)$ variables with algebraic degree $\deg(f_t) = t + 1$ for any integer $t \ge 2$. Our construction builds upon a minimal commutative algebra $I_t$, which naturally induces a triangular set-partition polynomial permutation $P_t$. By identifying an elementary abelian subgroup within the direct sum $ I_t \oplus I_t^*$, we establish an explicit nonlinear coordinate transformation that pulls $f_t$ back to a canonical quadratic form. This linearizes the translation development $\operatorname{Dev}(D_{f_t})$ under an exotic group structure and proves that it is isomorphic to the classical symplectic design $S^\pm(2(2^t-1))$, thereby fully resolving the conjecture.
Read the full abstract

Information Theory

Adaptive Coding for Two-Way Wiretap Channels with One-Sided Strong Secrecy

We study a discrete memoryless two-way wiretap channel under strong one-sided secrecy, where User 1's message is confidential and User 2's message is not required to be secret. We develop non-adaptive and key-assisted adaptive inner bounds from a common resolvability estimate for selected index components. For the adaptive construction, we prove a multiround leakage theorem that accounts both for information revealed about a key before its later use and for the possibility that an encoder uses an incorrectly decoded key. The proof includes an ideal-to-implemented coupling, deterministic codebook selection, and a growing-round argument that removes the initialization-rate loss. We eliminate the internal component rates exactly and characterize the adaptive gain at each fixed auxiliary distribution. For an open two-parameter family of binary channels, we also prove a converse for arbitrary non-adaptive stochastic codes and obtain an operational adaptive-versus-non-adaptive separation. For one representative channel, the complete non-adaptive strong one-sided secrecy capacity region is identified exactly.
Read the full abstract

Information Theory

Weight spectra of some families of GRM codes

Let $\mathrm{RM}_q(r,m)$ denote the generalized Reed–Muller code of order $r$ and length $q^m$ over the finite field $\mathbb{F}_q$. We completely determine the weight spectra of $\mathrm{RM}_3(2m-i,m)$ for $i=3,4$, $\mathrm{RM}_4(3m-i,m)$ for $i=2,3$, $\mathrm{RM}_5(4m-4,m)$, and $\mathrm{RM}_7(6m-4,m)$, in the ranges of $m$ specified in the corresponding results. The proofs proceed by induction on $m$, using a sumset inclusion for GRM weight spectra together with results on low-weight codewords. The required base cases are established by computations in Magma and, for certain ternary cases, exact constraint solving with Z3.
Read the full abstract

Information Theory

Worse Routes, Fresher Information: Preemption Redefines Which Route is Best

This paper studies joint sampling, route activation, and preemption control over $N$ heterogeneous transmission routes under a long-run objective combining Age of Information (AoI) with sampling and transmission costs. We formulate the problem as an average-cost impulse-control model, derive a vector-form integral average-cost optimality equation over a hybrid state space, and establish structural reductions on the state. We consider a two-route case and compute optimized policies using discretized policy iteration. Surprisingly, the results show that preemption can reverse routing preferences: the optimized policy may exclusively use a route with both a larger mean delay and a larger delay variance while avoiding the seemingly superior route. Relative to baselines that do not allow preemption, the proposed policy reduces average AoI by up to $96\%$.
Read the full abstract

Friday 11 September

Information Theory · Cross-listed from cs.LG

Product-Aware Deterministic Rounding for Quantized Matrix Multiplication

Scalar rounding decisions interact through matrix multiplication. We study deterministic product-aware rounding after scales, clipping bounds, and grids are fixed, with each active scalar choosing between adjacent levels. For dynamic activation rounding, null-space reduction preserves the relaxed product while leaving at most $r$ fractional decisions, where $r$ is the rank of the active gap-weighted weight block. Conditional-expectation completion gives a deterministic polynomial-time algorithm with squared product error at most $ \mathrm{OPT}_{\mathrm{dyn}}+r\nu_{\max}^2/4$, where $\mathrm{OPT}_{\mathrm{dyn}}$ is the best admissible error and $\nu_{\max}$ is the largest row norm of that block. For reusable static weights, the exact expected product-loss metric is the uncentered input second moment with fixed output bias; free bias recalibration yields the centered covariance. Exact optimization is NP-hard even at rank one. In balanced blocks with $K=1024$ and $r=16$, conditional- expectation completion attains a dither-normalized median error of $0.010$, compared with $0.899$ for round-to-nearest. Clipping-aware initialization reduces median normalized error by a factor of $43.4$ at ten-percent clipping. Held-out Digits experiments show that retaining the input mean or correcting the output bias improves median product error over round-to-nearest in all four tested bit-width and calibration-size settings.
Read the full abstract

All authors Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal

Information Theory · Cross-listed from math.CO

A lattice family with kissing numbers $\tau(\mathcal{L}_n) \ge e^{2 \sqrt{n}}$

For all prime powers $q\geq5$, we construct lattices $\mathcal{L}_q\subseteq\mathbb{Z}^q$ with kissing numbers \[ \tau(\mathcal{L}_q)\geq \left(\frac{1}{2\pi e^2}+o(1)\right)\sqrt{q}\,e^{2\sqrt{q}}. \] The same asymptotic bound holds on a set of integer dimensions of natural density $1$, and in every sufficiently large integer dimension $n$ with an additional factor $e^{-\tfrac{1}{2}n^{1/40}}$. The construction is an extension of a previous construction by Bennett-Peikert based on Reed-Solomon codes.
Read the full abstract

Information Theory

From Priors to Projections: Geometry and simplified MIMO demodulation of probabilistic shaping

Probabilistic shaping (PS) is a well-known method to achieve improved performance upon a regular quadrature amplitude modulation (QAM) by taking the target constellation and making the distribution of underlying points non-uniform. It has been extensively studied over the years for the additive white Gaussian noise (AWGN) and Rayleigh fading channels. However, the potential of probabilistic shaping in the multiple-input and multiple-output (MIMO) setting needs further investigations. In this paper, we prove that if shaped symbols follow Maxwell-Boltzmann distribution, the optimal maximum a posteriori (MAP) detection is equivalent to the case of uniform constellation with a simple preprocessing step. Our approach has multiple benefits. It enables to utilize the same processing chain for both shaped and unshaped system, which simplifies the receiver architecture. This technique can be applied for both linear MMSE and nonlinear (near-)MAP demapper types. In addition, the complexity of adaptive methods such as sphere decoding can be reduced.
Read the full abstract

All authors Kirill Ivanov, Wei Yang, Mahmoud Taherzadeh Boroujeni, Jing Jiang

Information Theory · Cross-listed from quant-ph

High quantum local differential privacy breaks entanglement

Differential privacy provides a mathematical framework for guaranteeing privacy for sensitive data. In quantum information processing, the interaction of privacy constraints with quantum resources such as entanglement remains a question of interest. Given that the utility of many protocols, and often the presence of a quantum advantage, relies on quantum resources such as entanglement, it is crucial to understand when a privacy requirement for a quantum channel is compatible with the channel's ability to preserve entanglement. We study this question for quantum local differential privacy (QLDP). Our main result shows that every $\varepsilon$-QLDP channel with a $d$-dimensional input is entanglement-breaking whenever $\varepsilon\leq\log\frac{d}{d-1}$. We also prove an approximate version for $(\varepsilon,\delta)$-QLDP, where channels in the same high-privacy regime are close in diamond norm to an entanglement-breaking channel. We further prove a composition result for a collection of private quantum channels having entangled inputs and global measurements in the high-privacy regime. Finally, we apply our results to private quantum learning theory. We prove that any learning protocol using arbitrary quantum memory on copies of the output of an entanglement-breaking channel can be simulated by a protocol that measures the corresponding unprocessed input copies one at a time while storing only classical information. Combining this result with our high-privacy entanglement-breaking theorem, we show that under sufficiently private local noise, a learning protocol with quantum memory for purity testing and bipartite product testing is subject to the sample complexity lower bounds for protocols with single-copy measurements on the noiseless tasks. We also obtain stronger sample complexity lower bounds when a single highly private channel acts on the entire multipartite input.
Read the full abstract

Information Theory

A New Upper Bound on the Binary Deletion Channel Capacity

We prove that the capacity of the binary deletion channel satisfies $C(d)\le (1-d)/4$ for every $13/20\le d<1$. The proof describes the output from right to left, using a six-bit context to assign a description length. We bound the increase in expected description length minus output entropy when one input bit is added. A relative-entropy identity reduces this bound to finitely many linear inequalities. A potential on input windows of length 26 makes the inequalities telescope, giving a bound for every input word. Deletion composition extends the result from $d=13/20$ to all larger deletion probabilities. We also obtain finite-block bounds on mutual information and decoding error, with explicit $O(\log n/n)$ corrections. The finite certificate is checked using exact integer arithmetic, and the proof is formalized end to end in Lean.
Read the full abstract

Information Theory · Cross-listed from cs.IR

PCGNet: Unifying Shared and Specific Information for Fashion Matching Recommendations

In fashion domain, recommending complementary clothing items that match selected pieces is a crucial cross-selling technique that improves customer satisfaction. Nevertheless, fashion matching presents significant challenges, as recommendations must not only align with individual user fashion preferences but also ensure compatibility between garments. These challenges are twofold. First, existing models often assume an overly simplified decoupled relationship between product compatibility and personalized user preferences, overlooking the natural complexity between the two. Second, existing data-driven approaches are not optimized for real-world fashion data, which is typically sparse and characterized by noisy interactions. To address these challenges, we propose Personalized Compatibility Graph Network, a multi-objective graph learning framework that organically unifies the modeling of product compatibility and personal preferences. PCGNet uses contrastive mutual information maximization to extract and align shared and view-specific patterns, thereby capturing the complex interplay between compatibility and personal preferences. Moreover, we introduce a correlation-aware neighbor sampling and a learnable global graph augmentation, which enhance the model by incorporating self-supervised signals mined directly from the graph, ensuring more stable and informative representations. Finally, PCGNet generates recommendation scores through the joint optimization of BPR ranking loss and multi-view mutual information losses. Experimental validation on two benchmark datasets demonstrates that PCGNet significantly outperforming state-of-the-art methods across all four evaluation metrics.
Read the full abstract

Information Theory

When Do Pilots Matter for OFDM Sensing? Pilot-Data Resource Design for ISAC

Practical OFDM-based integrated sensing and communication (ISAC) signals contain deterministic pilots and random data payloads, yet how these two types of resources jointly affect matched-filter sensing performance remains insufficiently understood. This paper establishes an analytical and optimization framework for pilot-data (P-D) OFDM sensing. We first derive a closed-form mean-square periodic autocorrelation function (MS P-ACF), which characterizes the respective contributions of the average subcarrier power spectrum and data-symbol randomness to sensing sidelobes. Based on this result, we reveal that pilot placement has no impact on normalized sidelobes under uniform power allocation or on the normalized global expected integrated sidelobe level (EISL), whereas it becomes an effective design degree of freedom for reshaping sidelobes under nonuniform power allocation. We further derive the globally optimal two-level pilot-data power allocation for global EISL minimization and characterize pilot placement for peak sidelobe suppression. For region-of-interest (ROI) sensing, we jointly optimize pilot placement and subcarrier power allocation to minimize the normalized ROI-EISL. A strictly uniform pilot placement is proved globally optimal under specified conditions, while a bisection-and-branch-and-bound algorithm is developed for general resource configurations. Numerical results validate the theoretical analysis and demonstrate that the proposed design reduces the ROI sidelobe level by up to 2.19 dB compared with optimized uniform-pilot OFDM, while improving ranging accuracy at an SNR of -10 dB by 84.3$\%$. These results reveal when and how pilot placement can be exploited to regulate the sensing behavior of random OFDM communication signals, providing practical resource-design principles for OFDM-based ISAC.
Read the full abstract

All authors Shengcai Zhou, Luping Xiang, Yi Wang, Kun Yang

Information Theory · Cross-listed from quant-ph

Optimal Hamiltonian Parameter Estimation in the Presence of Nuisance Parameters

In many sensing applications, the quantity of interest is not the only unknown, there are also additional unknown parameters, known as nuisance parameters, that affect the precision of estimation. While the ultimate local precision limit for a target parameter is well understood in the absence of nuisance parameters, the problem becomes significantly more challenging when they are present. In this work, we develop a framework for optimal Hamiltonian parameter estimation in the presence of nuisance parameters. We introduce an effective generator that captures the influence of nuisance parameters on the target precision, providing an explicit characterization of the ultimate precision limit for estimating the target parameter. Finally, we provide explicit optimal protocols, including probe state, control, and measurement that saturate this fundamental limit.
Read the full abstract

All authors Zhiyao Hu, Haidong Yuan, Liang Jiang, Zain H. Saleem

Information Theory · Cross-listed from quant-ph

Log-Sobolev inequality, von Neumann entropy and Entanglement of Formation

We present two results derived from the sharp log-Sobolev inequality for the uniform measure on a complete graph which concern the von Neumann entropy and the Entanglement of Formation of a state of finite and infinite-dimensional quantum systems. The first result is a sharp Lipschitz lower semicontinuity bound for the von Neumann entropy at any mixed state $\rho$ with uniform positive spectrum (i.e. a state proportional to a projector) w.r.t. the fidelity deficit: the inequality $\,S(\rho)-S(\sigma)\leq C_\rho(1-F(\rho,\sigma))\,$ valid for any state $\sigma$, where $C_{\rho}$ is a constant depending on the rank of $\rho$. The second result is a sharp Lipschitz lower semicontinuity bound for the Entanglement of Formation at any pure state $\rho$ with uniform positive spectrum of marginal states w.r.t. the fidelity deficit: the inequality $\,E_F(\rho)-E_F(\sigma)\leq C_\rho(1-\mathrm{Tr}\rho\sigma)\,$ valid for any state $\sigma$, where $C_{\rho}$ is a constant depending on the Schmidt rank of $\rho$. In both cases the optimal constant $C_\rho$ is equal to the optimal constant $K_{d}$ in the log-Sobolev inequality for the complete graph with $d$ vertices: in the first case $d=\mathrm{rank}\rho$, in the second one $d=\mathrm{rank}\rho_A=\mathrm{rank}\rho_B$. The authors are grateful to GPT 5.6 for valuable discussion and technical help in preparing this note.
Read the full abstract

Information Theory

Confusion-Erasure Bounds of Error-Bounded Decoders under QAM

6G is expected to push ultra-reliable low-latency communication (URLLC) toward stringent residual-error targets for mission-critical services, where undetected errors and erasures carry fundamentally different costs. Block error rate (BLER) conflates block confusions (undetected errors) and block erasures, which have fundamentally different impacts on system reliability. This paper extends the confusion and erasure analysis of error-bounded decoders to square quadrature amplitude modulation (QAM) constellations in the finite blocklength (FBL) regime. To handle QAM's heterogeneous symbol energies - which make the per-pair Euclidean distance a distribution rather than a single value - we derive analytical lower and upper bounds on the block confusion rate by, respectively, collapsing this distribution to its root-mean-square (RMS) distance and averaging the pairwise confusion over it. These bounds are proven to be monotonically decreasing in both the average symbol energy and the blocklength, with the decrease rate governed by the constellation order. Numerical results confirm that as the signal-to-noise ratio (SNR) or redundancy increases, the confusion rate falls many orders of magnitude below the reliability target, leaving detectable erasures as the dominant residual error.
Read the full abstract

Information Theory

Error-Rate Reduction in LDPC Decoding via Bit-Aligned Temporal Reinforcement in Parallel Probabilistic-Bit Dynamics

Probabilistic bits (p-bits) provide a physical and algorithmic primitive for stochastic inference, but highly parallel updates can alter their collective dynamics. We study the decoding of random-regular (3, 6) low-density parity-check (LDPC) codes using Jacobi-type p-bit annealing with stochastic partial activation. An additive response-path rule stores each bit's saturated response and reuses it before stochastic readout. High-statistics simulations with independent parameter optimization for each method show pooled bit-error-rate reductions of 33.5%, 74.8%, and 81.8% relative to memoryless probabilistic simulated annealing (pSA) for representative codes of block lengths 96, 192, and 288, respectively. Static gain, normalized averaging, response shuffling, and same-bit binary-state feedback with only its coefficient tuned under the same nonmemory parameters do not reproduce the full saturated-response benefit. Trajectory analysis links the improvement to acquisition of the channel-consistent valid-codeword basin and enhanced post-acquisition stability; the acquisition advantage persists from random and channel-hard-decision starts under the tested conditions. Across all 30 independent code realizations, fixed additive parameter-and-readout packages achieve lower bit- and frame-error rates than separately optimized pSA-specific packages, with neither package retuned for individual codes. These results show that the computational effect of temporal state depends on the retained quantity and its reinjection into stochastic dynamics.
Read the full abstract

Thursday 10 September

Information Theory

The kernel-block rank profiles of the $\mathbb{Z}_2\mathbb{Z}_4$-linear and the $\mathbb{Z}_{2^s}$-linear Hadamard codes, and a complete classification of the $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard codes

The kernel of a binary code containing the zero word partitions the binary coordinates into blocks, two coordinates lying in the same block when every kernel word takes the same value in both, and the kernel-block rank profile is the multiset of the dimensions of its linear span punctured on those blocks. For the family $H^{t_1,t_2,t_3}$ of $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard codes, this invariant is known explicitly and gives a complete classification of the family. In this paper, we compute it for the $\mathbb{Z}_2\mathbb{Z}_4$-linear and $\mathbb{Z}_{2^s}$-linear Hadamard families with which those codes are compared, and we prove that it is constant for every nonlinear $\mathbb{Z}_2\mathbb{Z}_4$-linear Hadamard code and for every nonlinear $\mathbb{Z}_{2^s}$-linear Hadamard code $\bar H^{a_1,\dots,a_s}$ with $s\geq2$. The second statement is obtained without any rank formula, by exhibiting coordinate permutations that preserve the code and act transitively on its kernel blocks, which makes the argument uniform in $s$. We also prove a descent theorem: if $\bar H^{a_1,\dots,a_s}$ is nonlinear and $a_1\geq2$, then the code punctured on one kernel block is the $\mathbb{Z}_{2^{s-1}}$-linear Hadamard code $\bar H^{a_1,\dots,a_{s-1}}$. Consequently, the constant local rank equals $rank(\bar H^{a_1,\dots,a_{s-1}})$ and is at least $t-\kappa+2$, where $2^t$ is the length and $\kappa$ the kernel dimension. These results separate every nonlinear $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard code from every $\mathbb{Z}_4$-linear, $\mathbb{Z}_2\mathbb{Z}_4$-linear and $\mathbb{Z}_{2^s}$-linear Hadamard code of the same length, except for the single infinite family $H^{1,1,t-4}$ and $\bar H^{2,0,t-5}$ with $t\geq5$. The members of this infinite family agree in the rank, kernel dimension and the kernel-block rank profile, but a two-block refinement separates them.
Read the full abstract