2024-10-22 | | Total: 21
In this work, we consider the target detection problem in a multistatic integrated sensing and communication (ISAC) scenario characterized by the cell-free MIMO communication network deployment, where multiple radio units (RUs) in the network cooperate with each other for the sensing task. By exploiting the angle resolution from multiple arrays deployed in the network and the delay resolution from the communication signals, i.e., orthogonal frequency division multiplexing (OFDM) signals, we formulate a cooperative sensing problem with coherent data fusion of multiple RUs' observations and propose a sparse Bayesian learning (SBL)-based method, where the global coordinates of target locations are directly detected. Intensive numerical results indicate promising target detection performance of the proposed SBL-based method. Additionally, a theoretical analysis of the considered cooperative multistatic sensing task is provided using the pairwise error probability (PEP) analysis, which can be used to provide design insights, e.g., illumination and beam patterns, for the considered problem.
Optimizing network utility in device-to-device networks is typically formulated as a non-convex optimization problem. This paper addresses the scenario where the optimization variables are from a bounded but continuous set, allowing each device to perform power control. The power at each link is optimized to maximize a desired network utility. Specifically, we consider the weighted-sum-rate. The state of the art benchmark for this problem is fractional programming with quadratic transform, known as FPLinQ. We propose a scalarization approach to transform the weighted-sum-rate, developing an iterative algorithm that depends on step sizes, a reference, and a direction vector. By employing the deep unfolding approach, we optimize these parameters by presenting the iterative algorithm as a finite sequence of steps, enabling it to be trained as a deep neural network. Numerical experiments demonstrate that the unfolded algorithm performs comparably to the benchmark in most cases while exhibiting lower complexity. Furthermore, the unfolded algorithm shows strong generalizability in terms of varying the number of users, the signal-to-noise ratio and arbitrary weights. The weighted-sum-rate maximizer can be integrated into a low-complexity fairness scheduler, updating priority weights via virtual queues and Lyapunov Drift Plus Penalty. This is demonstrated through experiments using proportional and max-min fairness.
This paper proposes a general analysis of codeword detection in noncoherent communications. Motivated by the existence of error floors in various regimes, fundamental characteristics of signal design are investigated. In particular, the necessary and sufficient conditions for asymptotically singular detection (i.e. error-free in the limit) are derived from classical results in detection theory. By leveraging tools from linear algebra and the theory of Hilbert spaces, we are able to characterize asymptotic singularity in two main scenarios: the large array and high SNR regimes. The results generalize previous works and extend the notion of unique identification, as well as recontextualize the geometry of Grassmannian constellations from an alternative perspective.
We explore the problem of distributed Hypothesis Testing (DHT) against independence, focusing specifically on Binary Symmetric Sources (BSS). Our investigation aims to characterize the optimal quantizer among binary linear codes, with the objective of identifying optimal error probabilities under the Neyman-Pearson (NP) criterion for short code-length regime. We define optimality as the direct minimization of analytical expressions of error probabilities using an alternating optimization (AO) algorithm. Additionally, we provide lower and upper bounds on error probabilities, leading to the derivation of error exponents applicable to large code-length regime. Numerical results are presented to demonstrate that, with the proposed algorithm, binary linear codes with an optimal covering radius perform near-optimally for the independence test in DHT.
The sum-rank metric generalizes the Hamming and rank metric by partitioning vectors into blocks and defining the total weight as the sum of the rank weights of these blocks, based on their matrix representation. In this work, we explore support-guessing algorithms for decoding sum-rank-metric codes. Support-guessing involves randomly selecting candidate supports and attempting to decode the error under the assumption that it is confined to these supports. While previous works have focused on worst-case scenarios, we analyze the average case and derive an optimal support-guessing distribution in the asymptotic regime. We show that this distribution also performs well for finite code lengths. Our analysis provides exact complexity estimates for unique decoding scenarios and establishes tighter bounds beyond the unique decoding radius. Additionally, we introduce a randomized decoding algorithm for Linearized Reed--Solomon (LRS) codes. This algorithm extends decoding capabilities beyond the unique decoding radius by leveraging an efficient error-and-erasure decoder. Instead of requiring the entire error support to be confined to the guessed support, the algorithm succeeds as long as there is sufficient overlap between the guessed support and the actual error support. As a result, the proposed method improves the success probability and reduces computational complexity compared to generic decoding algorithms. Our contributions offer more accurate complexity estimates than previous works, which are essential for understanding the computational challenges involved in decoding sum-rank-metric codes. This improved complexity analysis, along with optimized support-guessing distributions, provides valuable insights for the design and evaluation of code-based cryptosystems using the sum-rank metric. This is particularly important in the context of quantum-resistant cryptography.
An inductive mean is a mean defined as a limit of a convergence sequence of other means. Historically, this notion of inductive means obtained as limits of sequences was pioneered independently by Lagrange and Gauss for defining the arithmetic-geometric mean. In this note, we first explain several generalizations of the scalar geometric mean to symmetric positive-definite matrices, and then present several inductive mean mechanisms for sets of symmetric positive-definite matrices.
Integrated sensing and communication (ISAC) is a very promising technology designed to provide both high rate communication capabilities and sensing capabilities. However, in Massive Multi User Multiple-Input Multiple-Output (Massive MU MIMO-ISAC) systems, the dense user access creates a serious multi-user interference (MUI) problem, leading to degradation of communication performance. To alleviate this problem, we propose a decentralized baseband processing (DBP) precoding method. We first model the MUI of dense user scenarios with minimizing Cramer-Rao bound (CRB) as an objective function.Hybrid precoding is an attractive ISAC technique, and hybrid precoding using Partially Connected Structures (PCS) can effectively reduce hardware cost and power consumption. We mitigate the MUI between dense users based on ThomlinsonHarashima Precoding (THP). We demonstrate the effectiveness of the proposed method through simulation experiments. Compared with the existing methods, it can effectively improve the communication data rates and energy efficiency in dense user access scenario, and reduce the hardware complexity of Massive MU MIMO-ISAC systems. The experimental results demonstrate the usefulness of our method for improving the MUI problem in ISAC systems for dense user access scenarios.
We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from $\frac{1-\varepsilon}{2}$ fraction of errors and list decodable from $1-\varepsilon$ fraction of errors. We present several improved explicit constructions that achieve near-optimal rates, as well as efficient or even linear-time decoding algorithms. Our contributions are as follows. 1. Explicit Near-Optimal Linear Time Uniquely Decodable Codes: We construct a family of explicit $\mathbb{F}_2$-linear codes with rate $\Omega(\varepsilon)$ and alphabet size $2^{\mathrm{poly} \log(1/\varepsilon)}$, that are capable of correcting $e$ errors and $s$ erasures whenever $2e + s < (1 - \varepsilon)n$ in linear-time. 2. Explicit Near-Optimal List Decodable Codes: We construct a family of explicit list decodable codes with rate $\Omega(\varepsilon)$ and alphabet size $2^{\mathrm{poly} \log(1/\varepsilon)}$, that are capable of list decoding from $1-\varepsilon$ fraction of errors with a list size $L = \exp\exp\exp(\log^{\ast}n)$ in polynomial time. 3. List Decodable Code with Near-Optimal List Size: We construct a family of explicit list decodable codes with an optimal list size of $O(1/\varepsilon)$, albeit with a suboptimal rate of $O(\varepsilon^2)$, capable of list decoding from $1-\varepsilon$ fraction of errors in polynomial time. Furthermore, we introduce a new combinatorial object called multi-set disperser, and use it to give a family of list decodable codes with near-optimal rate $\frac{\varepsilon}{\log^2(1/\varepsilon)}$ and list size $\frac{\log^2(1/\varepsilon)}{\varepsilon}$, that can be constructed in probabilistic polynomial time and decoded in deterministic polynomial time. We also introduce new decoding algorithms that may prove valuable for other graph-based codes.
We investigate coding schemes that map source symbols into multisets of an alphabet set. Such a formulation of source coding is an alternative approach to the traditional framework and is inspired by an object tracking problem over proximity sensor networks. We define a \textit{multiset combinatorial Gray code} as a mulitset code with fixed multiset cardinality that possesses combinatorial Gray code characteristic. For source codes that are organized as a grid, namely an integer lattice, we propose a solution by first constructing a mapping from the grid to the alphabet set, the codes are then defined as the images of rectangular blocks in the grid of fixed dimensions. We refer to the mapping as a \textit{color mapping} and the code as a \textit{color multiset code}. We propose the idea of product multiset code that enables us to construct codes for high dimensional grids based on 1-dimensional (1D) grids. We provide a detailed analysis of color multiset codes on 1D grids, focusing on codes that require the minimal number of colors. To illustrate the application of such a coding scheme, we consider an object tracking problem on 2D grids and show its efficiency, which comes from exploiting transmission parallelism. Some numerical results are presented to conclude the paper.
Recent experiments have demonstrated the feasibility of storing digital information in macromolecules such as DNA and protein. However, the DNA storage channel is prone to errors such as deletions, insertions, and substitutions. During the synthesis and reading phases of DNA strings, many noisy copies of the original string are generated. The problem of recovering the original string from these noisy copies is known as sequence reconstruction. A key concept in this problem is the error ball, which is the set of all possible sequences that can result from a limited number of errors applied to the original sequence. Levenshtein showed that the minimum number of noisy copies required for a given channel to recover the original sequence is equal to one plus the maximum size of the intersection of two error balls. Therefore, deriving the size of the error ball for any channel and any sequence is essential for solving the sequence reconstruction problem. In DNA storage systems, multiple types of errors such as deletion, insertion and substitution in a string could occur simultaneously. In this work, we aim to derive the size of the error ball for channels with multiple types of errors and at most three edits. Specifically, we consider the channels with single-deletion double-substitution, single-deletion double-insertion and single-insertion single-substitution errors.
The soft-output successive cancellation list (SOSCL) decoder provides a methodology for estimating the a-posteriori probability log-likelihood ratios by only leveraging the conventional SCL decoder for polar codes. However, the sequential nature of SCL decoding leads to a high decoding latency for the SO-SCL decoder. In this paper, we propose a soft-output fast SCL (SO-FSCL) decoder by incorporating node-based fast decoding into the SO-SCL framework. Simulation results demonstrate that the proposed SO-FSCL decoder significantly reduces the decoding latency without loss of performance compared with the SO-SCL decoder.
There is a close relationship between linear codes and $t$-designs. Through their research on a class of narrow-sense BCH codes, Ding and Tang made a breakthrough by presenting the first two infinite families of near MDS codes holding $t$-designs with $t=2$ or 3. In this paper, we present an infinite family of MDS codes over $\mathbb{F}_{2^s}$ and two infinite families of almost MDS codes over $\mathbb{F}_{p^s}$ for any prime $p$, by investigating the parameters of the dual codes of two families of BCH codes. Notably, these almost MDS codes include two infinite families of near MDS codes over $\mathbb{F}_{3^s}$, resolving a conjecture posed by Geng et al. in 2022. Furthermore, we demonstrate that both of these almost AMDS codes and their dual codes hold infinite families of $3$-designs over \(\mathbb{F}_{p^s}\) for any prime $p$. Additionally, we study the subfield subcodes of these families of MDS and near MDS codes, and provide several binary, ternary, and quaternary codes with best known parameters.
As the number of low Earth orbit (LEO) satellites rapidly increases, the consideration of frequency sharing or cooperation between geosynchronous Earth orbit (GEO) and LEO satellites is gaining attention. In this paper, we consider a hybrid GEO-LEO satellite network where GEO and LEO satellites are distributed according to independent Poisson point processes (PPPs) and share the same frequency resources. Based on the properties of PPPs, we first analyze satellite-visible probabilities, distance distributions, and association probabilities. Then, we derive an analytical expression for the network's coverage probability. Through Monte Carlo simulations, we verify the analytical results and demonstrate the impact of system parameters on coverage performance. The analytical results effectively estimate the coverage performance in scenarios where GEO and LEO satellites cooperate or share the same resource.
This paper revisits the classical notion of unicity distance from an enlightening perspective grounded in information theory, specifically by framing the encryption process as a noisy transmission channel. Using results from reliable communication theory, we derive a simple information-theoretic proof of the same unicity distance formula as in Shannon's classical result and a channel transmission interpretation of the unicity distance.
We study agents acting in an unknown environment where the agent's goal is to find a robust policy. We consider robust policies as policies that achieve high cumulative rewards for all possible environments. To this end, we consider agents minimizing the maximum regret over different environment parameters, leading to the study of minimax regret. This research focuses on deriving information-theoretic bounds for minimax regret in Markov Decision Processes (MDPs) with a finite time horizon. Building on concepts from supervised learning, such as minimum excess risk (MER) and minimax excess risk, we use recent bounds on the Bayesian regret to derive minimax regret bounds. Specifically, we establish minimax theorems and use bounds on the Bayesian regret to perform minimax regret analysis using these minimax theorems. Our contributions include defining a suitable minimax regret in the context of MDPs, finding information-theoretic bounds for it, and applying these bounds in various scenarios.
The problem of measuring conditional dependence between two random phenomena arises when a third one (a confounder) has a potential influence on the amount of information shared by the original pair. A typical issue in this challenging problem is the inversion of ill-conditioned autocorrelation matrices. This paper presents a novel measure of conditional dependence based on the use of incomplete unbiased statistics of degree two, which allows to re-interpret independence as uncorrelatedness on a finite-dimensional feature space. This formulation enables to prune data according to the observations of the confounder itself, thus avoiding matrix inversions altogether. Moreover, the proposed approach is articulated as an extension of the Hilbert-Schmidt independence criterion, which becomes expressible through kernels that operate on 4-tuples of data.
Solovay reducibility $\redsolovay$ was introduced by Robert M. Solovay in 1975 via translation functions on rationals. In 2022, its totalized version $\redsolovaytotal$ (i.e., Solovay reducibility via a total function on rationals) has been examined by Merkle and Titov (arXiv:2407.14869). In 2020, Kumabe, Miyabe, Mizusawa and Suzuki (arXiv:1903.08625) have discovered that Solovay reducibility can be characterized on left-c.e.\ reals using the notion of a translation function on reals. In 2024, Kumabe, Miyabe, and Suzuki (DOI: 10.3233/COM-230486) have introduced a new reducibility $\redclopen$ on all reals, that uses the notion of a translation function on reals, and its totalized version $\redcllocal$. %They have also shown that $\redcllocal$ implies $\redclopen$, wherein the converse is not true even for left-c.e. reals. In this work, we show that $\redsolovayreal$ implies $\redclopen$ and $\redsolovaytotal$ implies $\redcllocal$ on all reals.
Satellite communications present challenging characteristics. Continuous end-to-end connectivity may not be available due to the large distances between satellites. Moreover, resources such as link capacity and buffer memory may be limited. Routing in satellite networks is therefore both complex and crucial to avoid packet losses and long delays. The Delay Tolerant Network (DTN) paradigm has emerged as an efficient solution for managing these challenging networks. Contact Graph Routing (CGR), a deterministic routing algorithm, is one of the most popular DTN algorithms. CGR is compatible with the ``store, carry, and forward" principle, whereby a node receives a message and stores it in its buffer until a transmission opportunity becomes available. However, CGR relies on simplified models to incorporate potential constraints in the route search. For instance, the linear volume assumption is often used to consider capacity constraints. Moreover, capacity management and buffer management are mostly performed during the forwarding phase, once an issue has occurred. In this paper, we propose to take measures before or during the route search in order to find routes that respect both contact-capacity limits and node-buffer limits. We introduce the contact splitting and edge pruning operations to effectively account for the routing constraints. This ensures that CGR outputs the optimal solution among the subset of valid solutions. The proposed approach can also be used to book resources to be used in case of issues during the forwarding step.
Enumerating the extremal submodular functions defined on subsets of a fixed base set has only been done for base sets up to five elements. This paper reports the results of attempting to generate all such functions on a six-element base set. Using improved tools from polyhedral geometry, we have computed 360 billion of them, and provide the first reasonable estimate of their total number, which is expected to be between 1,000 and 10,000 times this number. The applied Double Description and Adjacency Decomposition methods require an insertion order of the defining inequalities. We introduce two novel orders, which speed up the computations significantly, and provide additional insight into the highly symmetric structure of submodular functions. We also present an improvement to the combinatorial test used as part of the Double Description method, and use statistical analyses to estimate the degeneracy of the polyhedral cone used to describe these functions. The statistical results also highlight the limitations of the applied methods.
In this paper, we consider a class of convex programming problems with linear equality constraints, which finds broad applications in machine learning and signal processing. We propose a new adaptive balanced augmented Lagrangian (ABAL) method for solving these problems. The proposed ABAL method adaptively selects the stepsize parameter and enjoys a low per-iteration complexity, involving only the computation of a proximal mapping of the objective function and the solution of a linear equation. These features make the proposed method well-suited to large-scale problems. We then custom-apply the ABAL method to solve the ISAC beamforming design problem, which is formulated as a nonlinear semidefinite program in a previous work. This customized application requires careful exploitation of the problem's special structure such as the property that all of its signal-to-interference-and-noise-ratio (SINR) constraints hold with equality at the solution and an efficient computation of the proximal mapping of the objective function. Simulation results demonstrate the efficiency of the proposed ABAL method.
Quantum simulation in its current state faces experimental overhead in terms of physical space and cooling. We propose boson sampling as an alternative compact synthetic platform performing at room temperature. Identifying the capability of estimating matrix permanents, we explore the applicability of boson sampling for tackling the dynamics of quantum systems without having access to information about the full state vector. By mapping the time-evolution unitary of a Hamiltonian onto an interferometer via continuous-variable gate decompositions, we present proof-of-principle results of localization characteristics of a single particle. We study the dynamics of one-dimensional tight-binding systems in the clean and quasiperiodic-disordered limits to observe Bloch oscillations and dynamical localization, and the delocalization-to-localization phase transition in the Aubry- Andre-Harper model respectively. Our computational results obtained using boson sampling are in complete agreement with the dynamical and static results of non-interacting tight-binding systems obtained using conventional numerical calculations. Additionally, our study highlights the role of number of sampling measurements or shots for simulation accuracy.