Peer Revenue Impact factor: volatile

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)

Saturday 29 August

Information Theory

Secrecy Outage Analysis over Correlated Composite Generalized-Gamma Fading Channels

This paper investigates physical-layer security (PLS) over correlated composite generalized-Gamma (GG)/GG fading channels, where both shadowing and small-scale fading follow GG distributions. Using Mellin transforms and Fox-H functions, closed-form expressions are derived for the single-link probability density function (PDF), joint distribution, survival function, and zero-rate secrecy outage probability (SOP)/probability of non-zero secrecy capacity (PNZSC). The general-rate SOP is expressed as an exact double series with one residual onedimensional integral per term. The model includes the Nakagamim/GG and Nakagami-m/Gamma channels as special cases. Numerical results validate the analysis and demonstrate the impact of the fading parameters on secrecy performance.
Read the full abstract

Information Theory

On systematicity of linear function-correcting codes

The standard formulation of function-correcting codes uses systematic encodings. We study the redundancy cost of this constraint when both the prescribed function and the encoding are linear. We introduce the function-separation distance and show that several classical unequal error protection parameters are special cases. For linear functions and encodings, this distance is the first relative generalized Hamming weight of the code relative to the encoded kernel. We formulate free and systematic linear separation problems. We prove that the optimal free redundancy depends only on the rank of the function, and determine the optimal systematic redundancy for prescribed separations $d\leq3$.
Read the full abstract

Information Theory

Neural Network-Based Delay-Doppler-Assisted Channel Estimation for OFDM

Conventional orthogonal frequency division multiplexing (OFDM) channel estimation relies on single-tap estimation and time-frequency (TF) interpolation, which becomes unreliable in high-mobility channels because Doppler-induced inter-carrier interference (ICI) invalidates the underlying element-wise TF model. This paper proposes a neural-network-based delay-Doppler (DD)-assisted channel estimation framework for OFDM over doubly selective channels. We first derive an ICI-aware TF domain input-output relation and formulate channel estimation as a DD recovery problem. Unlike conventional sparse recovery approaches, the proposed framework does not require the equivalent DD domain channel vector to be strictly sparse, thereby accommodating the leakage induced by fractional delay and Doppler shifts. Since the data symbols are unknown during channel estimation, the sensing matrix is constructed using only the known pilot symbols. As a result, data-induced interference is not explicitly modeled, leading to a structured mismatch in the pilot observations. To tackle this challenge, the adopted network iteratively exchanges observation- and channel-domain features through the sensing matrix to learn the mapping from these contaminated observations to the equivalent DD domain channel, which is subsequently used to reconstruct the TF-domain channel. Simulation results show that the proposed method achieves lower normalized mean-square error and bit-error rate than conventional OFDM estimators.
Read the full abstract

All authors Mingcheng Nie, Hao Chang, Shuangyang Li, Haiyao Yu, Jiafu Hao, Yonghui Li

Information Theory

DeepHSIC: Deep Learning-based Signal Detector for Hybrid Downlink IM-NOMA

DeepHSIC is introduced as a neural receiver for hybrid downlink IM-NOMA transmission. The considered scheme combines power-domain NOMA with a composite OFDM/OFDM-IM waveform, so that user information is mapped jointly onto constellation symbols, subcarrier-index patterns, and different power levels. Although maximum-likelihood detection can achieve strong reliability for this model, its search space grows rapidly with the number of users and subcarriers. Conventional SIC reduces part of this burden, but its sequential cancellation may still accumulate errors and does not fully exploit the structure of IM-NOMA signals. To address this limitation, the proposed detector embeds dedicated deep neural network modules into the receiver and replaces the most computationally demanding SIC operations with learned inference blocks. The receiver is trained for Rayleigh fading channels and uses preprocessed channel-output features to recover user symbols. Simulation results show that DeepHSIC reaches BER performance close to model-based detectors under both perfect and imperfect CSI while requiring substantially lower detection time. These results indicate that learned SIC-style detection is a practical candidate for scalable hybrid downlink IM-NOMA receivers.
Read the full abstract

All authors Dung Nguyen Tran, Toan D. Gian, Tien-Hoa Nguyen, Mai Xuan Trang, Tien-Cuong Nguyen, Thien Van Luong

Information Theory · Cross-listed from stat.ML

Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO

We determine the sharp restricted isometry threshold for recovery at global minima of the rank-restricted matrix LASSO. For target rank $r_{\star}$, if the rank-$k$ RIP constant satisfies $\delta<\delta_{\mathrm{sharp}}(k/r_{\star})$, where $\delta_{\mathrm{sharp}}(t)=t/(4-t)$ for $0<t<4/3$ and $\delta_{\mathrm{sharp}}(t)=\sqrt{(t-1)/t}$ for $t\ge4/3$, then every global minimizer has Frobenius error $\lesssim\sqrt{r_{\star}}\lambda$ for all $\lambda\gtrsim\|\mathcal{A}^{*}(\xi)\|_{\mathrm{op}}$ and at every search rank $r\ge r_{\star}$. The constants depend only on the RIP constant and $t=k/r_{\star}$, and in particular are independent of the search rank. When the rank restriction is inactive, the result specializes to the ordinary convex matrix LASSO. We also obtain the analogous results for sparsity-restricted vector LASSO. Conversely, we show that the threshold $\delta<\delta_{\mathrm{sharp}}(k/r_{\star})$ cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Universal recovery in approximate quantum error correction

Universal recovery – the existence of a single recovery map that corrects an entire family of error channels – is a central feature of quantum error correction (QEC). In exact QEC, linearity guarantees that a code correcting a given error set also corrects every channel whose Kraus operators lie in its linear span, and that a single recovery map suffices for all such channels. Approximate quantum error correction (AQEC), which relaxes perfect recovery to recovery with controlled error, has traditionally lacked this structure. In a recent paper (arXiv:2607.22995), we developed a theory of approximate quantum error correction showing that a restricted form of linearity persists in the approximate setting, yielding uniform AQEC guarantees for the family of channels controlled by a given error set. In this work, we complete the picture by establishing the second half of universal recovery in the approximate setting: a single recovery map can simultaneously correct every channel controlled by a given error set. The error-set theory we proposed quantifies approximate correctability through two parameters: the environment-leakage distance, governing worst-case performance, and the Knill–Laflamme Hellinger distance, governing average-case performance. We show here that both quantities also control universal decoding. We further study the Petz map naturally associated with an error set as an explicit universal recovery, and obtain uniform average- and worst-case guarantees across the entire family of channels.
Read the full abstract

Friday 28 August

Information Theory

Authentication over Arbitrarily Varying Channels with Causal Adversaries

We study authentication over a discrete memoryless arbitrarily varying channel (AVC) in which the adversary selects the channel state causally based on past channel outputs. We prove that the authentication capacity is positive exactly when the channel is not distribution-overwritable under stochastic encoding, and not I-overwritable under deterministic encoding. In the stochastic case, whenever the authentication capacity is positive, it coincides with the no-adversary Shannon capacity. Both converses follow from a novel wait-and-overwrite attack: the adversary tracks the no-adversary posterior over the message via the posterior guessing probability, and once it concentrates past a threshold, it samples a guess and a decoy from the posterior and overwrites the channel to mimic a no-adversary transmission of the decoy. The positivity results are obtained by constructing positive-rate codes with controlled overlap between codewords, together with a martingale concentration argument that handles adaptive adversarial strategies. For stochastic encoding, the full-capacity achievability further combines a capacity-achieving channel code with an authentication tag. These characterizations separate the causal stochastic-code and causal deterministic-code settings from each other and from the oblivious-adversary setting studied by Kosut and Kliewer.
Read the full abstract

All authors Mayank Bakshi, Vinod M. Prabhakaran, Bikash Kumar Dey, Oliver Kosut

Information Theory · Cross-listed from cs.LG

SemKV: Semantic Mixed-Precision KV Cache Quantization Guided by the Quality Cliff for Long-Context LLM Inference

The key-value (KV) cache is the dominant memory bottleneck of long-context large language model (LLM) inference, growing linearly with context length. We show that uniform KV quantization on a fractional-bit grid does not degrade gracefully: under a prespecified multi-seed statistical protocol, Llama-3.1-8B-Instruct with an affine quantizer is statistically indistinguishable from FP16 KV down to 2.322 code bits/value and collapses at 2.0 bits - a quality cliff in (2.0, 2.322] that reappears in generation-time quantization and multi-turn dialogue and transfers to Mistral-7B. The cliff reframes importance-aware mixed precision: above it, eight model-internal importance indicators are statistically interchangeable, so the benefit of mixing is grid interpolation, reaching average precisions uniform quantization cannot realize. SemKV preserves every token, ranks tokens by a model-internal score, and assigns two adjacent above-cliff precisions, achieving a measured 6.0x storage reduction with no statistically detectable quality difference from full KV (n=900, three seeds), and outperforming FP16 token pruning granted a 1.5x larger memory budget. Replacing the affine base with a distortion-optimized quantizer (TurboQuant-MSE) lowers the cliff in every protocol tested, raising the no-detectable-loss operating point to 7.9x. The recipe: measure the cliff for the target deployment setting, then interpolate above it.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Rényi Entanglement of Purification Is Non-additive

Entanglement of purification is a fundamental measure of total correlations whose additivity remains unresolved. We study its additivity for classical states on two qubits at different Rényi orders. For every $\alpha\in[0,1)$, we prove nonadditivity within this family, witnessed by two copies of a single state. We first solve the one-copy optimization exactly for the entire family at every Rényi order. We then restrict the two-copy optimization to a natural finite set of purifications and exhibit one whose entropy is strictly below the product value. In contrast, for $\alpha\in[2,\infty]$ we prove additivity under tensor products within this family. The interval $\alpha\in[1,2)$, including the von Neumann case $\alpha=1$, remains open, and we conjecture additivity there throughout the same family.
Read the full abstract

Information Theory

A Complete Characterization of Tensorizable $f$-divergences

Csiszar's formulation of the $f$-divergence introduced a vast family of functionals for quantifying dissimilarity between probability distributions. However, many applications in statistics and information theory rely only on a few $f$-divergences, such as the Kullback-Leibler divergence, the $\chi^2$-divergence, and the squared Hellinger distance. These divergences are especially useful because they admit simple compositional formulas under product measures, a property sometimes referred to as tensorization. In this work, we refine a formalism of tensorization previously introduced in the literature. Then, we show that any possible tensorization formula has a multi-affine form characterized by a single parameter, and identify all tensorizable $f$-divergences under our adopted notion of tensorization.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Classical Commitment over Quantum Channels with Limited Entanglement Assistance

We study classical string commitment over quantum channels with limited preshared entanglement. For noninteractive protocols, we determine the commitment capacity of a class of channels with input dimension $d$ that, at each use, sample a pair of classical random variables $(F,Z)$, apply one of the $d^2$ Heisenberg–Weyl operators indexed by $Z$ to the input, and deliver the transformed quantum system together with $F$ to the receiver. If $E$ is the available entanglement rate in bits per channel use, then the capacity is $\min\{H(Z|F),\log_2d+E\}$. This class of channels encompasses quantum erasure and depolarizing channels, as well as families of Pauli channels. Additionally, for interactive protocols, we show that the commitment rate cannot exceed $\log_2d+E$ bits per channel use, so that when $H(Z|F)\geq\log_2d+E$, interactive communication does not increase the capacity. As a consequence, for interactive protocols, we determine the capacity of the quantum erasure channel.
Read the full abstract

Information Theory

Distributed Cross-Layer Optimization for Covert Multi-Hop, Multi-Modal Networks: Exponentially Fast Convergence and Robust Tracking

This paper develops the first distributed cross-layer algorithm for joint congestion control, routing, scheduling, and power control in covert multi-hop, multi-modal wireless networks, where adversarial wardens (Willies) monitor radio modalities via energy detection. The Detection Error Probability (DEP), the probability that a Willie fails to reliably detect ongoing transmissions, is generally non-concave in the transmit powers, making DEP-based covert network optimization challenging. We resolve this by constructing the tightest concave lower bound on the log-DEP, yielding a conservative convex problem that guarantees satisfaction of the original DEP constraints and unifies hard covertness constraints and covertness-utility maximization in a single problem. We develop a Parallel Proximal Alternating Direction Method of Multipliers (PP-ADMM) algorithm for the resulting cross-layer problem and prove global Q-linear convergence, i.e., exponentially fast convergence, to the set of optimal solutions under standard regularity conditions. Numerical results confirm linear convergence and demonstrate robust tracking performance under channel fading and Willie mobility.
Read the full abstract

All authors Sirin Chakraborty, Andrea Panebianco, Yuchen Tian, Kevin S Chan, Fikadu Dagefu, Yin Sun, Ness B. Shroff

Information Theory

Significance-Driven Semantic Communication

In this paper, we study a significance-driven cross- layer semantic communication design problem. Based on sta- tistical decision theory, we introduce an information-theoretic measure of per-sample data significance that quantifies the task-specific value of each individual observation. Using this metric, we formulate a cross-layer optimization problem that simultaneously optimizes (i) physical-layer semantic encoding and inference and (ii) MAC-layer resource allocation, with the objective of maximizing semantic spectrum efficiency, defined as the semantic value delivered per unit bandwidth per unit time. At the physical layer, we develop Meta-Learning Variational Information Bottleneck (Meta-VIB), a new semantic transceiver that employs a meta-learned hypernetwork to compress high- dimensional observations into semantically significant latents, enabling instantaneous adaptation to dynamic channel conditions and varying symbol budgets without online retraining. At the MAC layer, we model channel allocation as a Multi-Action Restless Multi-Armed Bandit (MA-RMAB) and adopt the Q- Maximization algorithm, which dynamically allocates channel resources to sensors based on their semantic value of information. Experimental results on a real-world pedestrian safety dataset demonstrate that our joint design achieves substantial gains in semantic spectrum efficiency over baselines, reaching up to 1000 times gain at an average SNR of 0 dB and 40 times gain at an average SNR of 5 dB.
Read the full abstract

All authors Christian McDowell, Andrea Panebianco, Sirin Chakraborty, Yin Sun

Information Theory

Shortest self-orthogonal and LCD embeddings of linear codes over Fq+uFq

This paper determines the exact lengths of shortest self-orthogonal and LCD embeddings of linear codes over $\mathbb{F}_q+u\mathbb{F}_q$. By decomposing Gram matrices over $\mathbb{F}_q+u\mathbb{F}_q$ into pairs of symmetric matrices over the finite field $\mathbb{F}_q$, the embedding problems are reduced to the congruence classification of symmetric and alternate matrices over finite fields. Complete formulas for the shortest self-orthogonal embedding length are obtained, with two distinct cases arising in both even and odd characteristic. We also show that every self-orthogonal code over $\mathbb{F}_q+u\mathbb{F}_q$ with nonzero free rank can be viewed as a shortest self-orthogonal embedding of another code. We use Witt theory to construct all shortest self-orthogonal embeddings. A complete characterization of shortest LCD embeddings is also established in terms of invertible and arbitrary matrices of prescribed sizes appended to a generator matrix. Examples of self-orthogonal and LCD embeddings with the largest minimum distance for the code considered are also presented, some of whose Gray images are optimal codes over $\mathbb{F}_q$.
Read the full abstract

Information Theory · Cross-listed from stat.ML

Conformal Risk-Averse Decision Making with Optimized Certainty Equivalent Risk Control

We study risk-averse decision making, in which an agent selects actions while being uncertain about the true system state. The risk is measured via optimized certainty equivalent (OCE) metrics, which generalize popular criteria such as mean-variance risk and conditional value-at-risk (CVaR). We characterize the optimal policy under known distributions, and show that it reduces to a prediction set-based solution for the CVaR. This provides an operational interpretation of conformal prediction-type prediction sets. For unknown distributions, we develop a data-driven calibration strategy, based on a synthetic model for the likelihood and held-out calibration data, yielding high-probability control of the OCE risk. The approach is evaluated on two wireless beamforming settings.
Read the full abstract

Information Theory

Fine Difference Structure and Prime-Power Depth of Bent Partitions

A $p$-ary bent partition of $\mathbb{F}_p^n$ is a partition into $K$ nonempty cells such that every balanced assignment of its cells to $\mathbb{F}_p$ produces a bent function. It was asked whether every possible depth $K$ is a power of $p$; for general $p$, previous affirmative results required regularity or cell-symmetry hypotheses. We prove the stronger unconditional statement that, for every nonzero $h$, exactly $p^n/K$ points remain in the same fine cell under translation by $h$. Thus the fine cells form a partitioned difference family and the fine label map is zero-difference balanced. Consequently $K\mid p^n$, so $K=p^t$; nonempty cells further give $1\le t<n$. In even dimension, the classical cell-size theorem yields $K\mid p^{n/2}$. Together with the known odd-dimensional ternary three-fibre parameter restriction, this gives the global bound $t\le\lfloor n/2\rfloor$. The proof is an exact finite average over balanced coarsenings. The main counting identity and selected consequences are formalized and kernel-checked in Lean 4.
Read the full abstract

Information Theory

Ada-TokenCom: Rate-Adaptive Token Communications via Large-Model-Driven Token Compression and Generation

Token Communications (TokenCom) has recently emerged as a new paradigm in which tokens serve as unified units for communication and computation, enabling efficient multimodal semantic and goal-oriented transmission. In this paper, we develop Ada-TokenCom, a rate-adaptive TokenCom framework based on large autoregressive models, which integrates next-token prediction with arithmetic coding to achieve ultra-low bitrate semantic communication at the token level. We propose a mixed reconstruction/generation scheme, where the transmitter encodes and transmits the highly informative tokens at the beginning of the token sequence leveraging a pre-trained autoregressive large model, while the receiver uses an identical model to predict the rest. Moreover, we design a Lyapunov-based algorithm to dynamically optimize both the source compression rate and the modulation and coding scheme, adapting to time-varying network conditions. Simulation results demonstrate that our proposed Ada-TokenCom framework outperforms both digital and deep joint source-channel coding-based semantic communication baselines.
Read the full abstract

All authors Zijun Zhang, Li Qiao, Mahdi Boloursaz Mashhadi, Zhen Gao, Mehdi Bennis, Kaibin Huang

Information Theory

ODMA-based MIMO Massive Unsourced Random Access with Soft-Output Polar Codes

This paper investigates the design of the on-off division multiple access (ODMA) transmission scheme for multiple-input multiple-output (MIMO) massive unsourced random access (URA) systems with soft-output (SO) polar codes. First, a three-segment pilot-uncoupled coding scheme is introduced under the ODMA framework, which reduces the coding rate of the data segment without increasing the transmission overhead, improving the overall system performance. Building upon this architecture, a hierarchical pattern detection framework is developed. Specifically, a coarse-grained candidate set of transmission patterns is first identified through correlation operations. Based on this, a message-passing (MP)-based pattern detection algorithm is developed to iteratively estimate the posterior probabilities of transmission patterns, followed by the maximum a posteriori (MAP) estimation to obtain the precise pattern detection result. Furthermore, a joint pattern detection and data decoding algorithm based on the bit-wise SO information of polar decoder is investigated, where the posterior probability information provided by the polar decoder is exploited to refine the pattern detection and contribute to an improved accuracy. In addition, by leveraging bit-wise SO information of the successive cancellation list polar decoder, an MP-based iterative decoding algorithm is developed to significantly enhance the decoding performance. The proposed scheme simultaneously exploits the transmission gain of uncoupled-ODMA framework, the coding gain of polar codes in the short-blocklength regime, and the iterative decoding gain enabled by SO information, while the computational complexity is significantly reduced through the hierarchical detection framework. Simulation results demonstrate that the proposed scheme achieves strong robustness ...
Read the full abstract

All authors Tianya Li, Xiaoran Zhang, Nan Hu, Yongpeng Wu, Wenjun Zhang, Xiang-Gen Xia, Chengshan Xiao

Information Theory

Finite Sample Bounds for Composite Hypothesis Testing

We investigate composite binary hypothesis testing in the finite sample regime under asymmetric error constraints. Using Rényi divergences, we derive explicit achievability and converse bounds for the optimal Type II error. When the Type I error is constrained to decay exponentially with sample size, the bounds identify a phase transition and yield a strong converse above it. In the composite problem, the phase transition threshold is given by the joint KL projection over the alternative and null classes. Achievability is obtained through a joint Rényi projection whose log likelihood ratio defines a single test with uniform error control over both hypothesis classes, without requiring the projected pair to be least favourable. For compact convex classes with full support on a finite alphabet, we determine the exact error exponents on both sides of the transition and show that the achievable exponent is attained at a unique Rényi order. The same framework recovers the fixed Type I composite Chernoff–Stein exponent and yields a polynomial refinement of the finite sample achievability result. We further identify conditions under which the projected pair is least favourable at finite sample size.
Read the full abstract

Information Theory · Cross-listed from cs.AI

Should I Use This Synthetic Dataset for Training? How to Test with Minimal Real Data

Digital twins (DTs) and learned world models are increasingly used to generate synthetic data that augment the scarce real datasets available for training artificial intelligence (AI) models in engineering systems. Owing to the inevitable simulation-to-reality (sim-to-real) gap, however, augmentation may fail to improve the performance of the trained model on the real data distribution. This paper addresses the resulting decision problem: Given a real dataset, a candidate synthetic dataset, and a fixed learning algorithm, decide whether training on the augmented dataset improves the true, population-level performance, while consuming as few real test data points as possible. Two formulations are considered: a direct test on the mean loss difference between the two trained models, and a symmetry-based test on the paired loss difference, which trades a stronger null assumption for faster evidence accumulation. For the latter, we introduce the {adaptive e-process sign-flip test} (aeSFT), a doubly adaptive procedure that adapts both the number of Monte Carlo sign-flip rounds, and hence the computational cost, and the amount of real test data consumed. aeSFT yields anytime-valid Type-I error control, with no need to pre-specify the test-set size. Experiments on a synthetic-data classification task, a DT-aided wireless packet-scheduling task, and a radio-map prediction task show that aeSFT identifies useful synthetic data using substantially fewer real test samples than mean-based sequential testing, matches the power of fixed-sample sign-flip testing and the paired $t$-test, while keeping the false-positive rate below the target level.
Read the full abstract

All authors Zhenyu Tao, Wei Xu, Xiaohu You, Petar Popovski, Osvaldo Simeone

Information Theory · Cross-listed from physics.comp-ph

Accelerated S-NFC for Million-Chaff RCS Computation Using Low-Rank Compression of Concatenated Block Rows

Sparsification via neglecting far-field coupling (S-NFC) enables fast full-wave radar-cross-section analysis of large-scale chaff clouds by retaining only significant local electromagnetic interactions. This letter further accelerates S-NFC by concatenating the retained off-diagonal interaction blocks associated with each receiving chaff element and applying a joint low-rank factorization with a shared receiving-side basis. Exact self interactions are preserved, while repeated chaff templates reuse precomputed lower–upper factorizations of the self-interaction blocks. The compressed formulation reduces retained-coupling storage and matrix–vector multiplication cost and also decreases the number of iterations required by the generalized conjugate residual solver. Numerical tests with 100,000 chaff elements demonstrate sub-$1\%$ complex-far-field error for low-rank approximations in sparse regimes and identify a practical self-only limit at sufficiently large mean spacing. For a one-million-chaff plume, the proposed compressed S-NFC achieves a $6.92\times$ end-to-end speedup over uncompressed S-NFC while storing only $6.60\%$ of the retained coupling, with a complex-far-field error of $0.253\%$.
Read the full abstract

Information Theory

Low-Altitude Fluid Antenna Network with Multi-Agent Reinforcement Learning

Low-altitude wireless networks (LAWNs) integrate terrestrial and aerial platforms to provide ubiquitous communication, sensing, and localization services for unmanned aerial vehicles (UAVs) and electric vertical takeoff and landing (eVTOL) aircraft. However, dynamic air-ground and air-air channels, abrupt blockages, and heterogeneous interference hinder the realization of this goal. Nevertheless, fluid antenna (FA), a cutting-edge multiple-input multiple-output (MIMO) technique, overcomes these challenges by reconfiguring antenna positions to unlock additional spatial degrees-of-freedom. In this paper, towards bringing low-altitude FA networks into reality, we study the fast and high-performance FA reconfiguration for low-altitude FA networks with multi-agent reinforcement learning (MARL). Specifically, we present an electromagnetic digital twin (EM-DT)-assisted MARL framework. To fill the sim-to-real gap, we introduce a two-stage transfer learning framework. Our case study shows that joint FA positions and beamforming optimization can enhance the system sum-rate by 118.5%, compared to the fixed position baseline. This gain comes from the dynamic millisecond timescale reconfiguration of FA arrays and the adaptive steering of beams toward aerial users with mobility.
Read the full abstract

All authors Tong Zhang, Yanfei Su, Shuai Wang, Wanli Ni, Chengzhong Xu, Huseyin Arslan

Information Theory · Cross-listed from cs.CC

Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families

Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial method argument that controls collisions in sumsets of matching vectors.
Read the full abstract

Information Theory · Cross-listed from math-ph

Difference equations of average entropies

Exact cumulants of entanglement entropies of random state ensembles have traditionally been studied within the random matrix framework. In this work, we propose an alternative approach based on the intrinsic connection to integrable systems. The central idea is to embed entropic quantities into tau functions satisfying Toda-type lattice equations, which in turn yield linear difference equations for their averages. Directly solving the difference equations recovers exact entropy formulas in the literature. The integrable systems approach bypasses the case-by-case, ensemble-dependent derivations required by random matrix methods. The approach also suggests a possible route towards unified and more efficient higher-order cumulant calculations by exploring integrable hierarchies.
Read the full abstract

All authors Youyi Huang, Linfeng Wei, Lu Wei, Peter J. Forrester

Thursday 27 August

Information Theory · Cross-listed from eess.SP

A Nonuniform-Sampling Theory for Static Multi-Threshold Sampling

Multi-Threshold (MT) sampling fixes voltage levels and records when a waveform crosses them. The resulting signal-generated event stream is governed not by a prescribed clock but by the nonuniform geometry of the realized crossing set. Within classical nonuniform sampling, we develop a retained-event MT theory for static, uniformly spaced thresholds. For a realized retained MT time set, Beurling's weak-limit theorem gives the exact necessary-and-sufficient condition for stable sampling of $PW_\Omega$. For a fixed signal class, the same principle gives the a priori criterion: uniform stable MT sampling is equivalent to Bernstein uniqueness for every set in the class weak-limit hull. This criterion reduces to computable forms under structured priors. Periodic templates give finite fiber/rank tests, periodic-gap streams give a Shannon-type complete-interpolation boundary and a stable-sampling density rule, and finite-state gap priors reduce noncritical certification to a maximum-cycle-mean condition. Kadec-type local certificates, retained-density bounds, and finite-matrix tests provide practical sufficient conditions for finite active records, while conditional perturbation bounds quantify how jitter, front-end noise, and threshold error consume a clean sampling margin under event correspondence. The theory also identifies the unavoidable boundary of this model: unrestricted finite-energy retained MT records have zero full-line lower Beurling density and therefore cannot provide a universal prior-free sampling theorem for $PW_\Omega$. Within retained-event point sampling, the MT recovery question is resolved precisely: exact recovery is governed by event-set geometry, computable guarantees require structural priors or finite-dimensional/tail assumptions, and the unrestricted static finite-energy problem is impossible.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Logical Neural Belief Propagation for Linear-Complexity Decoding of Surface Codes

Quantum error correction (QEC) requires accurate and efficient decoders, yet belief propagation (BP), despite its linear decoding complexity, often provides insufficient logical accuracy on surface codes. We propose Logical Neural Belief Propagation (L-NBP), a BP-based neural decoder that redirects the decoding objective from physical-level to logical-level decoding. L-NBP uses a neural BP (NBP) module to produce posterior beliefs, which a logical classifier transforms into a continuous-valued soft syndrome for logical-operator prediction. Trained end-to-end by backpropagation, the NBP module learns soft syndromes that are favorable for logical classification. On surface codes, L-NBP matches or outperforms BP with ordered-statistics decoding (BP-OSD) and minimum-weight perfect matching (MWPM) while retaining the linear complexity of BP, and achieves a threshold of $17.5\%$ under depolarizing noise. Under circuit-level noise, L-NBP matches the accuracy of BP-OSD on the distance-$9$ surface code while requiring only $0.2\%$ of its complexity.
Read the full abstract

All authors Hee-Youl Kwak, Seong-Joon Park, Dae-Young Yun, Eliya Nachmani, Jae-Won Kim

Information Theory

Selective Interference Suppression of Siamese-Net in Heterogeneous Interference Channels

We study an end-to-end learnt short-block codes for a $N$-user real Gaussian interference channel with heterogeneous pairwise interference strengths, while keeping single-user decoding at every receiver. In this paper, we study the case wherein only a few dominant interferers exist and investigate whether Siamese-style coupled training can adapt selectively to encode (& decode) to ensure optimal performance corresponding to best tradeoff between orthogonality and coding gain or it enforces unnecessary global orthogonality oblivious of the reality. Our work focuses on a 4-user unequal-interference configuration with one dominant pair $(1,2)$ (of strength $\Lambda$) and a weak pair (with weak background coupling ($\lambda$)), through which we demonstrate a selective interference suppression phenomenon where the learned codebooks become near-orthogonal primarily for the dominant pair, while weakly coupled pairs retain alignment needed for coding gain. We quantify this behaviour using latent-space cross-user similarity statistics (worst-case coherence measure, average similarity measure, etc) and connect these geometric signatures to the observed BLER robustness under unequal interference. It seems that the SiameseNet selectively suppresses the interferences from various interferring user pairs to yield optimal tradeoff between coding gain and BLER dictated by orthogonality.
Read the full abstract

All authors Arkadeep Sinha, Shubham Paul, R. Manivasakan, Nambi Seshadri, R. David Koilpillai

Information Theory · Cross-listed from quant-ph

Spectral Theory of Semisimple Bivariate Bicycle Codes

Extending the classical theory of two-dimensional cyclic codes, we develop an algebraic approach to bivariate bicycle codes. Using Frobenius-orbit idempotents, formulas for logical dimensions are derived and lower bounds on minimum distances are established. A systematic theory of code symmetries is formulated to construct a structured block-monomial subgroup of coordinate permutations. Several explicit examples show how to generate these codes from first principles without relying on numerical searches. An appendix extends the analysis to BCH-based product constructions.
Read the full abstract

Information Theory · Cross-listed from stat.ML

Towards a mathematical theory of superposition

We develop a mathematical theory of superposition in neural networks using tools from frame theory and compressed sensing. In our model, a sparse binary vector \(x\) of active features is encoded through an overcomplete dictionary \(W\), and feature recovery is performed by applying \(\operatorname{ReLU}(W^\top W x+b)\) with an appropriate bias vector \(b\). We prove several recovery theorems for this model. In the random-support setting, we establish high-probability support recovery for nearly tight, low-coherence dictionaries, with guarantees when the expected sparsity is up to order \(d/\log n\). In the worst-case support setting, we give a sharp and computable criterion for which sparsity levels permit support recovery. We apply this criterion to Gaussian random matrices and equiangular tight frames. For real equiangular tight frames with \(n>d+1\), we determine the exact recovery threshold in terms of the coherence. The proof of this result for real equiangular tight frames relies on a novel characterization—which should be of independent interest to frame theorists—of the distribution of signs in the Gram matrix.
Read the full abstract

All authors Michael I. Ivanitskiy, John Jasper, Emily J. King, Dustin G. Mixon

Information Theory · Cross-listed from quant-ph

Quantized Low-Rank Quantum State Tomography: Hyperbolic Quantization and Riemannian Least-Squares Recovery

We study low-rank quantum state tomography from finite-bit Pauli batch responses. To avoid bias introduced by generic quantization, we propose HyperQuant, a mean-preserving hyperbolic quantizer adapted to the second-moment scale of Pauli responses. We establish minimax distortion guarantees and show that exact mean preservation enables direct rank-constrained least-squares recovery without altering the population target. We derive nonasymptotic recovery guarantees and an explicit bit–shot tradeoff under which finite-bit responses retain the error order of unquantized batch averages using fewer response bits. For efficient computation, we develop QuantRGD, a Riemannian gradient method with provable linear convergence to the corresponding statistical neighborhood under explicit resource conditions. Numerical experiments validate the predicted quantization, recovery, and convergence behavior.
Read the full abstract