Date: Wed, 8 May 2024 | Total: 16
Error correction codes are a crucial part of the physical communication layer, ensuring the reliable transfer of data over noisy channels. The design of optimal linear block codes capable of being efficiently decoded is of major concern, especially for short block lengths. While neural decoders have recently demonstrated their advantage over classical decoding techniques, the neural design of the codes remains a challenge. In this work, we propose for the first time a unified encoder-decoder training of binary linear block codes. To this end, we adapt the coding setting to support efficient and differentiable training of the code for end-to-end optimization over the order two Galois field. We also propose a novel Transformer model in which the self-attention masking is performed in a differentiable fashion for the efficient backpropagation of the code gradient. Our results show that (i) the proposed decoder outperforms existing neural decoding on conventional codes, (ii) the suggested framework generates codes that outperform the {analogous} conventional codes, and (iii) the codes we developed not only excel with our decoder but also show enhanced performance with traditional decoding techniques.
The sensing and positioning capabilities foreseen in 6G have great potential for technology advancements in various domains, such as future smart cities and industrial use cases. Channel charting has emerged as a promising technology in recent years for radio frequency-based sensing and localization. However, the accuracy of these techniques is yet far behind the numbers envisioned in 6G. To reduce this gap, in this paper, we propose a novel channel charting technique capitalizing on the time of arrival measurements from surrounding Transmission Reception Points (TRPs) along with their locations and leveraging sensor fusion in channel charting by incorporating laser scanner data during the training phase of our algorithm. The proposed algorithm remains self-supervised during training and test phases, requiring no geometrical models or user position ground truth. Simulation results validate the achievement of a sub-meter level localization accuracy using our algorithm 90% of the time, outperforming the state-of-the-art channel charting techniques and the traditional triangulation-based approaches.
Any continuous curve in a higher dimensional space can be considered a trajectory that can be parameterized by a single variable, usually taken as time. It is well known that a continuous curve can have a fractional dimensionality, which can be estimated using already standard algorithms. However, characterizing a trajectory from an entropic perspective is far less developed. The search for such characterization leads us to use chain coding to discretize the description of a curve. Calculating the entropy density and entropy-related magnitudes from the resulting finite alphabet code becomes straightforward. In such a way, the entropy of a trajectory can be defined and used as an effective tool to assert creativity and pattern formation from a Shannon perspective. Applying the procedure to actual experimental physiological data and modelled trajectories of astronomical dynamics proved the robustness of the entropic characterization in a wealth of trajectories of different origins and the insight that can be gained from its use.
Safety guarantees and security-latency problem of Nakamoto consensus have been extensively studied in the last decade with a bounded delay model. Recent studies have shown that PoW protocol is secure under random delay models as well. In this paper, we analyze the security-latency problem, i.e., how secure a block is, after it becomes k-deep in the blockchain, under general random delay distributions. We provide tight and explicit bounds which only require determining the distribution of the number of Poisson arrivals during the random delay. We further consider potential effects of recent Bitcoin halving on the security-latency problem by extending our results.
Age of Information (AoI), namely the time that has elapsed since the most recently delivered packet was generated, is receiving increasing attention with the emergence of many real-time applications that rely on the exchange of time-sensitive information. AoI captures the freshness of the information from the perspective of the destination. The term "accuracy of information" is used to assess how close the estimate at the destination is to the parameter value measured by the sensor. In this paper, the mean square error (MSE) is used to evaluate the accuracy of information. We focus on a single sensor that monitors a time-sensitive physical process, which is modelled as a random walk. Whenever the state of the random walk changes by more than a specified threshold, the sensor generates a status update packet and transmits it to the destination. When no update packet is received, the destination assumes that the state of the process has not changed. We study the problem of finding the minimum update rate under AoI and accuracy of information constraints. More specifically, we derive analytical expressions for the update rate, the AoI, and the MSE.
Measuring the complexity of real numbers is of major importance in computer science, for the purpose of knowing which computations are allowed. Consider a non-computable real number $s$, i.e. a real number which cannot be stored on a computer. We can store only an approximation of $x$, for instance by considering a finite bitstring representing a finite prefix of its binary expansion. For a fixed approximation error $\varepsilon>0$, the size of this finite bitstring is dependent on the \textit{algorithmic complexity} of the finite prefixes of the binary expansion of $s$. The \textit{algorithmic complexity} of a binary sequence $x$, often referred to as \textit{Kolmogorov complexity}, is the length of the smallest binary sequence $x'$, for which there exists an algorithm, such that when presented with $x'$ as input, it outputs $x$. The algorithmic complexity of the binary expansion of real numbers is widely studied, but the algorithmic complexity of other ways of representing real numbers remains poorly reported. However, knowing the algorithmic complexity of different representations may allow to define new and more efficient strategies to represent real numbers. Several papers have established an equivalence between the algorithmic complexity of the $q$-ary expansions, with $q \in \mathbb{N}$, $q \geq 2$, i.e. representations of real numbers in any integer base. In this paper, we study the algorithmic complexity of the so-called $\beta$-expansions, which are representations of real numbers in a base $\beta \in (1,2)$ that display a much more complex behavior as compared to the $q$-ary expansion. We show that for a given real number $s$, the binary expansion is a minimizer of algorithmic complexity, and that for every given $\beta \in (1,2)$, there exists a $\beta$-expansion of $s$ which achieves the lower bound of algorithmic complexity displayed by the binary expansion of $s$.
In this work, we prove that polar lattices, when tailored for lossy compression, are quantization-good in the sense that their normalized second moments approach $\frac{1}{2\pi e}$ as the dimension of lattices increases. It has been predicted by Zamir et al. \cite{ZamirQZ96} that the Entropy Coded Dithered Quantization (ECDQ) system using quantization-good lattices can achieve the rate-distortion bound of i.i.d. Gaussian sources. In our previous work \cite{LingQZ}, we established that polar lattices are indeed capable of attaining the same objective. It is reasonable to conjecture that polar lattices also demonstrate quantization goodness in the context of lossy compression. This study confirms this hypothesis.
Movable antenna (MA) technology, which can reconfigure wireless channels by flexibly moving antenna positions in a specified region, has great potential for improving communication performance. In this paper, we consider a new setup of MAs-enabled multicasting, where we adopt a simple setting in which a linear MA array-enabled source (${\rm{S}}$) transmits a common message to two single-antenna users ${\rm{U}}_1$ and ${\rm{U}}_2$. We aim to maximize the minimum rate among these two users, by jointly optimizing the transmit beamforming and antenna positions at ${\rm{S}}$. Instead of utilizing the widely-used alternating optimization (AO) approach, we reveal, with rigorous proof, that the above two variables can be optimized separately: i) the optimal antenna positions can be firstly determined via the successive convex approximation technique, based on the rule of maximizing the correlation between ${\rm{S}}$-${\rm{U}}_1$ and ${\rm{S}}$-${\rm{U}}_2$ channels; ii) afterwards, the optimal closed-form transmit beamforming can be derived via simple arguments. Compared to AO, this new approach yields the same performance but reduces the computational complexities significantly. Moreover, it can provide insightful conclusions which are not possible with AO.
Balancing diverse task objectives under limited rate is crucial for developing robust multi-task deep learning (DL) models and improving performance across various domains. In this paper, we consider the lossy compression problem with human-centric and task-oriented metrics, such as perceptual quality and classification accuracy. We investigate two ternary relationships, namely, the rate-distortion-classification (RDC) and rate-perception-classification (RPC). For both RDC and RPC functions, we derive the closed-form expressions of the optimal rate for both binary and Gaussian sources. Notably, both RDC and RPC relationships exhibit distinct characteristics compared to the previous RDP tradeoff proposed by Blau et al. Then, we conduct experiments by implementing a DL-based image compression framework, incorporating rate, distortion, perception, and classification constraints. The experimental results verify the theoretical characteristics of RDC and RPC tradeoffs, providing information-theoretical insights into the design of loss functions to balance diverse task objectives in deep learning.
We consider the problem of reconstructing an undirected graph $G$ on $n$ vertices given multiple random noisy subgraphs or "traces". Specifically, a trace is generated by sampling each vertex with probability $p_v$, then taking the resulting induced subgraph on the sampled vertices, and then adding noise in the form of either (a) deleting each edge in the subgraph with probability $1-p_e$, or (b) deleting each edge with probability $f_e$ and transforming a non-edge into an edge with probability $f_e$. We show that, under mild assumptions on $p_v$, $p_e$ and $f_e$, if $G$ is selected uniformly at random, then $O(p_e^{-1} p_v^{-2} \log n)$ or $O((f_e-1/2)^{-2} p_v^{-2} \log n)$ traces suffice to reconstruct $G$ with high probability. In contrast, if $G$ is arbitrary, then $\exp(\Omega(n))$ traces are necessary even when $p_v=1, p_e=1/2$.
In 5G, the Physical Downlink Control CHannel (PDCCH) carries crucial information enabling the User Equipment (UE) to connect in UL and DL. UEs are unaware of the frequency location at which PDCCH is encoded, hence they need to perform blind decoding over a limited set of possible candidates. We address the problem faced by the gNodeB of selecting PDCCH candidates for each UE to optimize data transmission. We formulate it as a Maximum Weighted Independent Set (MWIS) problem, that is known to be an NP-hard problem and cannot even be approximated. A solution method called Weight-to-Degree Ratio (WDR) Greedy emerges as a strong contender for practical implementations due to its favorable performance-to-complexity trade-off and theoretical performance guarantees.
Semi-algebraic priors are ubiquitous in signal processing and machine learning. Prevalent examples include a) linear models where the signal lies in a low-dimensional subspace; b) sparse models where the signal can be represented by only a few coefficients under a suitable basis; and c) a large family of neural network generative models. In this paper, we prove a transversality theorem for semi-algebraic sets in orthogonal or unitary representations of groups: with a suitable dimension bound, a generic translate of any semi-algebraic set is transverse to the orbits of the group action. This, in turn, implies that if a signal lies in a low-dimensional semi-algebraic set, then it can be recovered uniquely from measurements that separate orbits. As an application, we consider the implications of the transversality theorem to the problem of recovering signals that are translated by random group actions from their second moment. As a special case, we discuss cryo-EM: a leading technology to constitute the spatial structure of biological molecules, which serves as our prime motivation. In particular, we derive explicit bounds for recovering a molecular structure from the second moment under a semi-algebraic prior and deduce information-theoretic implications. We also obtain information-theoretic bounds for three additional applications: factoring Gram matrices, multi-reference alignment, and phase retrieval. Finally, we deduce bounds for designing permutation invariant separators in machine learning.
Channel simulation algorithms can efficiently encode random samples from a prescribed target distribution $Q$ and find applications in machine learning-based lossy data compression. However, algorithms that encode exact samples usually have random runtime, limiting their applicability when a consistent encoding time is desirable. Thus, this paper considers approximate schemes with a fixed runtime instead. First, we strengthen a result of Agustsson and Theis and show that there is a class of pairs of target distribution $Q$ and coding distribution $P$, for which the runtime of any approximate scheme scales at least super-polynomially in $D_\infty[Q \Vert P]$. We then show, by contrast, that if we have access to an unnormalised Radon-Nikodym derivative $r \propto dQ/dP$ and knowledge of $D_{KL}[Q \Vert P]$, we can exploit global-bound, depth-limited A* coding to ensure $\mathrm{TV}[Q \Vert P] \leq \epsilon$ and maintain optimal coding performance with a sample complexity of only $\exp_2\big((D_{KL}[Q \Vert P] + o(1)) \big/ \epsilon\big)$.
Out-of-system (OoS) interference is a potential limitation for distributed networks that operate in unlicensed spectrum or in a spectrum sharing scenario. The OoS interference differs from the in-system interference in that OoS signals and their associated channels (or even their statistics) are completely unknown. In this paper, we propose a novel distributed algorithm that can mitigate OoS interference in the uplink and suppress the signal transmission in the OoS direction in the downlink. To estimate the OoS interference, each access point (AP), upon receiving an estimate of OoS interference from a previous AP, computes a better estimate of OoS interference by rotate-and-average using Procrustes method and forwards the estimates to the next AP. This process continues until the central processing unit (CPU) receives the final estimate. Our method has comparable performance to that of a fully centralized interference rejection combining algorithm and has much lower fronthaul load requirements.
We consider the problem of distilling uniform random bits from an unknown source with a given $p$-entropy using linear hashing. As our main result, we estimate the expected $p$-divergence from the uniform distribution over the ensemble of random linear codes for all integer $p\ge 2$. The proof relies on analyzing how additive noise, determined by a random element of the code from the ensemble, acts on the source distribution. This action leads to the transformation of the source distribution into an approximately uniform one, a process commonly referred to as distribution smoothing. We also show that hashing with Reed-Muller matrices reaches intrinsic randomness of memoryless Bernoulli sources in the $l_p$ sense for all integer $p\ge 2$.
In Internet of Things (IoT) status update systems, where information is sampled and subsequently transmitted from a source to a destination node, the imperative necessity lies in maintaining the timeliness of information and updating the system with optimal frequency. Optimizing information freshness in resource-limited status update systems often involves Constrained Markov Decision Process (CMDP) problems with update rate constraints. Solving CMDP problems, especially with multiple constraints, is a challenging task. To address this, we present a token-based approach that transforms CMDP into an unconstrained MDP, simplifying the solution process. We apply this approach to systems with one and two update rate constraints for optimizing Age of Incorrect Information (AoII) and Age of Information (AoI) metrics, respectively, and explore the analytical and numerical aspects. Additionally, we introduce an iterative triangle bisection method for solving the CMDP problems with two constraints, comparing its results with the token-based MDP approach. Our findings show that the token-based approach yields superior performance over baseline policies, converging to the optimal policy as the maximum number of tokens increases.