IEEE Transactions on Information Theory
Journal Prestige (SJR): 1.162 Citation Impact (citeScore): 3 Number of Followers: 29 Hybrid journal (It can contain Open Access articles) ISSN (Print) 00189448 Published by IEEE [228 journals] 
 IEEE Transactions on Information Theory publication information

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 IEEE Transactions on Information Theory information for authors

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Information Constrained Optimal Transport: From Talagrand, to Marton, to
Cover
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yikun Bai;Xiugang Wu;Ayfer Özgür;
Pages: 2059  2073
Abstract: The optimal transport problem studies how to transport one measure to another in the most costeffective way and has wide range of applications from economics to machine learning. In this paper, we introduce and study an information constrained variation of this problem. Our study yields a strengthening and generalization of Talagrand’s celebrated transportation cost inequality. Following Marton’s approach, we show that the new transportation cost inequality can be used to recover old and new concentration of measure results. Finally, we provide an application of this new inequality to network information theory. We show that it can be used to recover almost immediately a recent solution to a longstanding open problem posed by Cover regarding the capacity of the relay channel.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Toward a Definitive Compressibility Measure for Repetitive Sequences

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Tomasz Kociumaka;Gonzalo Navarro;Nicola Prezza;
Pages: 2074  2092
Abstract: While the $k$ th order empirical entropy is an accepted measure of the compressibility of individual sequences on classical text collections, it is useful only for small values of $k$ and thus fails to capture the compressibility of repetitive sequences. In the absence of an established way of quantifying the latter, adhoc measures like the size $z$ of the Lempel–Ziv parse are frequently used to estimate repetitiveness. The size $b le z$ of the smallest bidirectional macro scheme captures better what can be achieved via copypaste processes, though it is NPcomplete to compute, and it is not monotone upon appending symbols. Recently, a more principled measure, the size $gamma $ of the smallest string attractor, was introduced. The measure $gamma le b$ lowerbounds all the previous relevant ones, while length $n$ strings can be represented and efficiently indexed within space $Oleft({gamma log frac {n}{gamma }}right)$ , which also upperbounds many measures, including $z$ . Although $gamma $ is arguably a better measure of repetitiveness than $b$ , it is also NPcomplete to compute and not monotone, and it is unknown if one can represet all strings in $o(gamma log n)$ space. In this paper, we study an even smaller measure, $delta le gamma $ , which can be computed in linear time, is monotone, and allows encoding every string in $Oleft({delta log frac {n}{delta }}right)$ space because $z = Oleft({delta log frac {n}{delta }}right)$ . We argue that $delta $ better captures the compressibility of repetitive strings. Concretely, we show that (1) $delta $ can be strictly smaller than $gamma $ , by up to a logarithmic factor; (2) there are string families needing $Omega left({delta log frac {n}{delta }}right)$ space to be encoded, so this space is optimal for every $n$ and $delta $ ; (3) one can build runlength contextfree grammars of size $Oleft({delta log frac {n}{delta }}right)$ , whereas the smallest (nonrunlength) grammar can be up to $Theta (log n/log log n)$ times larger; and (4) within $Oleft({delta log frac {n}{delta }}right)$ space, we can not only represent a string but also offer lo
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Towards the Optimal Rate Memory Tradeoff in Caching With Coded Placement

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Vijith Kumar K. P.;Brijesh Kumar Rai;Tony Jacob;
Pages: 2093  2112
Abstract: The idea of coded caching for content distribution networks was introduced by MaddahAli and Niesen, who considered the canonical $(N, K)$ cache network in which a server with $N$ files satisfies the demands of $K$ users (each equipped with an independent cache of size $M$ ). The optimal rate memory tradeoff for demands where all files are requested by at least one user has been characterized only for small caches where $Mleq frac {1}{K}$ and large caches where $Mgeq Nfrac {N}{K}$ . For the case $N leq K leq 2N1$ , we derive new lower bounds for small and large caches and propose a new coded caching scheme for large caches. Along with the scheme proposed by GómezVilardebó, this leads to a characterization of the optimal rate memory tradeoff for $Mleq frac {1}{K}+frac {1}{K(N1)}$ and $Mgeq Nfrac {N}{K}frac {N1}{K(K1)}$ . For the case $2N1leq K$ , we derive a new lower bound for large caches, which proves the optimality of the scheme proposed by Yu et al. and leads to a characterization of the optimal rate memory tradeoff for $Mgeq Nfrac {2N}{K}$ . We also derive a new lower bound for small caches, which improves upon previusly known lower bounds.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 NonAsymptotic Bounds of Cumulant Generating Function of Codeword Lengths
in VariableLength Lossy Compression
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Shota Saito;Toshiyasu Matsushima;
Pages: 2113  2119
Abstract: This paper investigates the problem of variablelength source coding with the criteria of the normalized cumulant generating function of codeword lengths and the excess distortion probability. We analyze the nonasymptotic fundamental limit of the normalized cumulant generating function of codeword lengths under the constraint that the excess distortion probability is allowed up to $epsilon in [0,1)$ . Our nonasymptotic achievability and converse bounds are characterized by the quantity related to the Rényi entropy.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Entropy Rate Bounds of IntegerValued Processes via SecondOrder
Statistics
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Ran Tamir;
Pages: 2120  2134
Abstract: This work contains two singleletter upper bounds on the entropy rate of an integervalued stationary stochastic process, which only depend on secondorder statistics, and are primarily suitable for models which consist of relatively large alphabets. The first bound stems from Gaussian maximumentropy considerations and depends on the power spectral density (PSD) function of the process. While the PSD function cannot always be calculated in a closedform, we also propose a second bound, which merely relies on some finite collection of autocovariance values of the process. Both of the bounds consist of a onedimensional integral, while the second bound also consists of a minimization problem over a bounded region, hence they can be efficiently calculated numerically. In some models that appear naturally in various disciplines and that consist of infinitely large alphabets, assessing the related entropy rates may be a complicated numerical problem. In such cases, we argue that the new proposed bounds can still be efficiently calculated. Examples are also provided to show that the new bounds outperform the standard existing ones.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Source Coding With a ListeningHelper

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Shraga I. Bross;
Pages: 2135  2151
Abstract: We consider the cooperative coding of a pair of correlated memoryless source and sideinformation sequences wherein an encoder assisted by a sideinformation aided listeninghelper describe the source and sideinformation to a receiver. We obtain a singleletter characterization of the rate region in both cases: when the decoder reconstructs just the source and when it reconstructs both the source and sideinformation. In the quadratic Gaussian setting we determine the optimal law characterizing the rate region using a technique introduced by Courtade in combination with a conditional version of the converse for the Gaussian CEO problem.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Codebook Mismatch can be Fully Compensated by Mismatched Decoding

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Neri Merhav;Georg Böcherer;
Pages: 2152  2164
Abstract: We consider an ensemble of constant composition codes that are subsets of linear codes: while the encoder uses only the constantcomposition subcode, the decoder operates as if the full linear code was used, with the motivation of simultaneously benefiting both from the probabilistic shaping of the channel input (to achieve higher rates) and from the linear structure of the code (to allow for lower complexity practical decoding). We prove that the codebook mismatch can be fully compensated by using a mismatched additive decoding metric that achieves the random coding error exponent of (nonlinear) constant composition codes. As the coding rate tends to the mutual information, the optimal mismatched metric approaches the maximum a posteriori probability (MAP) metric, showing that codebook mismatch with MAP metric is capacityachieving for the optimal input assignment.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Reliability Function for Streaming Over a DMC With Feedback

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Nian Guo;Victoria Kostina;
Pages: 2165  2192
Abstract: Conventionally, posterior matching is investigated in channel coding and block encoding contexts – the source symbols are equiprobably distributed and are entirely known by the encoder before the transmission. In this paper, we consider a streaming source, whose symbols progressively arrive at the encoder at a sequence of deterministic times. We derive the joint sourcechannel coding (JSCC) reliability function for streaming over a discrete memoryless channel (DMC) with feedback. We propose a novel instantaneous encoding phase that operates during the symbol arriving period and achieves the JSCC reliability function for streaming when followed by a block encoding scheme that achieves the JSCC reliability function for a classical source whose symbols are fully accessible before the transmission. During the instantaneous encoding phase, the evolving message alphabet is partitioned into groups whose priors are close to the capacityachieving distribution, and the encoder determines the group index of the actual sequence of symbols arrived so far and applies randomization to exactly match the distribution of the transmitted index to the capacityachieving one. Surprisingly, the JSCC reliability function for streaming is equal to that for a fully accessible source, implying that the knowledge of the entire symbol sequence before the transmission offers no advantage in terms of the reliability function. For streaming over a symmetric binaryinput DMC, we propose a onephase instantaneous smallenough difference (SED) code that not only achieves the JSCC reliability function, but also, thanks to its singlephase timeinvariant coding rule, can be used to stabilize an unstable linear system over a noisy channel. For equiprobably distributed source symbols, we design low complexity algorithms to implement both the instantaneous encoding phase and the instantaneous SED code. The algorithms group the source sequences into sts we call types, which enable the encoder and the decoder to track the priors and the posteriors of source sequences jointly, leading to a loglinear complexity in time. While the reliability function is derived for nondegenerate DMCs, i.e., DMCs whose transition probability matrix has all positive entries, for degenerate DMCs, we design a code with instantaneous encoding that achieves zero error for all rates below Shannon’s joint sourcechannel coding limit.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Entropic Central Limit Theorem for Order Statistics

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Martina Cardone;Alex Dytso;Cynthia Rush;
Pages: 2193  2205
Abstract: It is well known that central order statistics exhibit a central limit behavior and converge to a Gaussian distribution as the sample size grows. This paper strengthens this known result by establishing an entropic version of the central limit theorem that ensures a stronger mode of convergence using the relative entropy. This upgrade in convergence is shown at the expense of extra regularity conditions, which can be considered as mild. To prove this result, ancillary results on order statistics are derived, which might be of independent interest. For instance, a rather general bound on the moments of order statistics, and an upper bound on the mean squared error of estimating the $p in (0,1)$ th quantile of an unknown cumulative distribution function, are derived. Finally, a discussion on the necessity of the derived conditions for convergence and on the rate of convergence and monotonicity of the relative entropy is provided.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Recursive Decoding of ReedMuller Codes Starting With the HigherRate
Constituent Code
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Mikhail Kamenev;
Pages: 2206  2217
Abstract: Recursive list decoding of ReedMuller (RM) codes, with moderate list size, is known to approach maximumlikelihood (ML) performance of short length $(leq 256)$ RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lowerrate code first, the method in this paper decodes the higherrate code first. This modification enables an efficient permutationbased decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the errorrate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphismbased recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve nearML performance for short RM codes and for RM codes of length $2^{m}$ and order $m3$ with reasonable complexity.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 The ZeroRate Threshold for Adversarial BitDeletions is Less Than 1/2

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Venkatesan Guruswami;Xiaoyu He;Ray Li;
Pages: 2218  2239
Abstract: We prove that there exists an absolute constant $delta>0$ such that any binary code $Csubset {0,1}^{N} vphantom {_{int }}$ tolerating $(1/2delta)N$ adversarial deletions must satisfy $ C le 2^{ mathop {mathrm {poly}} log N}$ and thus have rate asymptotically approaching 0. This is the first constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants $A$ and $delta>0$ such that any set $Csubset {0,1}^{N}$ of $2^{log ^{A} N}$ binary strings must contain two strings $c$ and $c'$ whose longest common subsequence has length at least $(1/2+delta)N$ . As an immediate corollary, we show that $q$ ary codes tolerating a fraction $1(1+2delta)/q$ of adversarial deletions must also have rate approaching 0. Our techniques include string regularity arguments and a structural lemma that lassifies binary strings by their oscillation patterns. Leveraging these tools, we find in any large code two strings with similar oscillation patterns, which is exploited to find a long common subsequence.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 A Bound on the Minimal Field Size of LRCs, and Cyclic MR Codes That Attain
It
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Han Cai;Moshe Schwartz;
Pages: 2240  2260
Abstract: We prove a new lower bound on the field size of locally repairable codes (LRCs). Additionally, we construct maximally recoverable (MR) codes which are cyclic. While a known construction for MR codes has the same parameters, it produces noncyclic codes. Furthermore, we prove both necessary conditions and sufficient conditions that specify when the known noncyclic MR codes may be permuted to become cyclic, thus proving our construction produces cyclic MR codes with new parameters. Furthermore, using our new bound on the field size, we show that the new cyclic MR codes have optimal field size in certain cases. Other known LRCs are also shown to have optimal field size in certain cases.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 ListDecoding and ListRecovery of Reed–Solomon Codes Beyond the Johnson
Radius for Every Rate
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Eitan Goldberg;Chong Shangguan;Itzhak Tamo;
Pages: 2261  2268
Abstract: Understanding the limits of listdecoding and listrecovery of ReedSolomon (RS) codes is of prime interest in coding theory and has attracted a lot of attention in recent decades. However, the best possible parameters for these problems are still unknown, and in this paper, we take a step in this direction. We show the existence of RS codes that are listdecodable or listrecoverable beyond the Johnson radius for every rate, with a polynomial field size in the block length. In particular, we show that for every $epsilon in (0,1)$ there exist RS codes that are listdecodable from radius $1epsilon $ and rate less than $frac {epsilon }{2epsilon }$ , with constant list size. We deduce our results by extending and strengthening a recent result of Ferber, Kwan, and Sauermann on puncturing codes with large minimum distance and by utilizing the underlying code’s linearity.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 AdjacentBitsSwapped Polar Codes: A New Code Construction to Speed up
Polarization
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Guodong Li;Min Ye;Sihuang Hu;
Pages: 2269  2299
Abstract: The construction of polar codes with code length $n=2^{m}$ involves $m$ layers of polar transforms. In this paper, we observe that after each layer of polar transforms, one can swap certain pairs of adjacent bits to accelerate the polarization process. More precisely, if the previous bit is more reliable than its next bit under the successive decoder, then switching the decoding order of these two adjacent bits will make the reliable bit even more reliable and the noisy bit even noisier. Based on this observation, we propose a new family of codes called the AdjacentBitsSwapped (ABS) polar codes. We add a permutation layer after each polar transform layer in the construction of the ABS polar codes. In order to choose which pairs of adjacent bits to swap in the permutation layers, we rely on a new polar transform that combines two independent channels with 4ary inputs. This new polar transform allows us to track the evolution of every pair of adjacent bits through different layers of polar transforms, and it also plays an essential role in the successive cancellation list (SCL) decoder for the ABS polar codes. Extensive simulation results show that ABS polar codes consistently outperform standard polar codes by $0.15 mathop {mathrm {dB}}nolimits $ — $0.3 mathop {mathrm {dB}}nolimits $ when we use CRCaided SCL decoder with list size 32 for both codes. The implementations of all the algorithms in this paper are available at https://github.com/PlumJelly/ABSPolar
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Maximally Recoverable Local Repairable Codes From Subspace Direct Sum
Systems
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Shu Liu;Chaoping Xing;
Pages: 2300  2310
Abstract: Maximally recoverable local repairable codes (MR LRCs for short) have received great attention in the last few years. Various constructions have been proposed in literature. The main focus of this topic is to construct MR LRCs over small fields. An interesting parameter regime for an $(N=nr,r,h, delta)$ MR LRC is the constant global parities $h=O(1)$ . In this parameter setting, all previous constructions require the field size $ell =Omega _{h} (N^{h1o(1)})$ . It remains challenging to improve this bound. In this paper, via subspace direct sum systems, we present a construction of MR LRC with the field size $ell = Oleft({N^{h2+frac {1}{h1}o(1)}}right)$ . In particular, for the interesting cases where $h=2,3$ , we improve previous constructions by either reducing field size or removing constraints. In addition, we also offer some constructions of MR LRCs for larger global parity $h$ . The main techniques used in this paper is through subspace direct sum systems that we introduce.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Generalized bSymbol Weights of Linear Codes and bSymbol MDS Codes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Hongwei Liu;Xu Pan;
Pages: 2311  2323
Abstract: Generalized pair weights of linear codes are generalizations of minimum symbolpair weights, which were introduced by Liu and Pan (2022) recently. Generalized pair weights can be used to characterize the ability of protecting information in the symbolpair read wiretap channels of type II. In this paper, we introduce the notion of generalized $b$ symbol weights of linear codes over finite fields, which is a generalization of generalized Hamming weights and generalized pair weights. We obtain some basic properties and bounds of generalized $b$ symbol weights which are called Singletonlike bounds for generalized $b$ symbol weights. As examples, we calculate the generalized weight matrices for simplex codes and Hamming codes. We provide a necessary and sufficient condition for a linear code to be a $b$ symbol MDS code by using the generator matrix and the parity check matrix of this linear code. Finally, a necessary and sufficient condition of a linear isomorphism preserving $b$ symbol weights between two linear codes is obtained. As a corollary, we get the classical MacWilliams extension theorem when $b=1$ .
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 On the Size of Balls and Anticodes of Small Diameter Under the
FixedLength Levenshtein Metric
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Daniella BarLev;Tuvi Etzion;Eitan Yaakobi;
Pages: 2324  2340
Abstract: The rapid development of DNA storage has brought the deletion and insertion channel to the front line of research. When the number of deletions is equal to the number of insertions, the Fixed Length Levenshtein (FLL) metric is the right measure for the distance between two words of the same length. Similar to any other metric, the size of a ball is one of the most fundamental parameters. In this work, we consider the minimum, maximum, and average size of a ball with radius one, in the FLL metric. The related minimum and the maximum size of a maximal anticode with diameter one are also considered.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Infinite Families of Cyclic and Negacyclic Codes Supporting 3Designs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Xiaoqiang Wang;Chunming Tang;Cunsheng Ding;
Pages: 2341  2354
Abstract: Interplay between coding theory and combinatorial $t$ designs has been a hot topic for many years for combinatorialists and coding theorists. Some infinite families of cyclic codes supporting infinite families of 3designs have been constructed in the past 50 years. However, no infinite family of negacyclic codes supporting an infinite family of 3designs has been reported in the literature. This is the main motivation of this paper. Let $q=p^{m}$ , where $p$ is an odd prime and $m geq 2$ is an integer. The objective of this paper is to present an infinite family of cyclic codes over ${mathrm {GF}}(q)$ supporting an infinite family of 3designs and two infinite families of negacyclic codes over ${mathrm {GF}}(q^{2})$ supporting two infinite families of 3designs. The parameters and the weight distributions of these codes are determined. The subfield subcodes of these negacyclic codes over ${mathrm {GF}}(q)$ are studied. Three infinite families of almost MDS codes are also presented. A constacyclic code over ${mathrm {GF}}(4)$ supporting a 4design and seven open problems are also presented in this paper.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 New Constructions of Optimal Optical Orthogonal Codes Based on
Partitionable Sets and Almost Partitionable Sets
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zijing Wang;Hairong Kong;
Pages: 2355  2363
Abstract: Variableweight optical orthogonal codes (OOCs) were introduced by Yang for multimedia optical CDMA systems with multiple quality of service (QoS) requirements. In this paper, partitionable sets and almost partitionable sets are used to construct variableweight OOCs. Four new recursive constructions for optimal cyclic packing are presented. Consequently, new infinite classes of optimal $(v,W,1,Q)$ OOCs are obtained.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Asynchronous Massive Access and Neighbor Discovery Using OFDMA

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Xu Chen;Lina Liu;Dongning Guo;Gregory W. Wornell;
Pages: 2364  2384
Abstract: The fundamental communication problem in the wireless InternetofThings (IoT) is to discover a massive number of devices and to provide them with reliable access to shared channels. Oftentimes these devices transmit short messages randomly and sporadically. This paper proposes a novel signaling scheme for grantfree massive access, where each device encodes its identity and/or information in a sparse set of tones. Such transmissions are implemented in the form of orthogonal frequencydivision multiple access (OFDMA). Under some mild conditions and assuming device delays to be bounded unknown multiples of sampling intervals, sparse OFDMA is proved to enable arbitrarily reliable asynchronous device identification and message decoding with a codelength that is $O(K(log K+log S + log N))$ , where $N$ denotes the device population, $K$ denotes the actual number of active devices, and $log S$ is essentially equal to the number of information bits each device can send. The computational complexity for discovery and decoding can be made to be $O(K(log K)(log K+log S+log N)+K^{2}log K)$ . As a proof of concept, a specific design is proposed to identify up to 200 active devices out of $N=2^{96}$ possible devices with up to 20 samples of delay, moderate signaltonoise ratios, and fading. If the device population is $N=2^{48}$ instead, each active device can also transmit 48 bits to the access point at the same time. The codelength compares much more favorably with tose of standard slotted ALOHA and carriersensing multiple access (CSMA) schemes.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Proof of a Conjectured 0Rényi Entropy Inequality With Applications to
Multipartite Entanglement
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zhiwei Song;Lin Chen;Yize Sun;Mengyao Hu;
Pages: 2385  2399
Abstract: Characterizing the relations among the three bipartite reduced density operators $ rho _{AB}$ , $ rho _{AC}$ and $ rho _{BC}$ of a tripartite mixed state $ rho _{ABC}$ has been an open problem in quantum information. One of such relations has been reduced by [Cadney et al, LAA. 452, 153, 2014] to a conjectured inequality in terms of matrix rank, namely $r(rho _{AB}) cdot r( rho _{AC})ge r( rho _{BC})$ for any $ rho _{ABC}$ . It is denoted as open problem 41 in the website “Open quantum problemsIQOQI Vienna”. We prove the inequality, and thus establish a complete picture of the fourparty linear inequalities in terms of the 0entropy. Our proof is based on the construction of a novel canonical form of bipartite matrices under local equivalence. We extend our result to inequalities in multipartite systems, as well as the condition when the inequality is saturated.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 OneShot TripleResource TradeOff in Quantum Channel Coding

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Eyuri Wakakuwa;Yoshifumi Nakata;
Pages: 2400  2426
Abstract: We analyze a task in which classical and quantum messages are simultaneously communicated via a noisy quantum channel, assisted with a limited amount of shared entanglement. We derive direct and converse bounds for the oneshot capacity region, represented by the smooth conditional entropies and the error tolerance. The proof is based on the randomized partial decoupling theorem, which is a generalization of the decoupling theorem. The two bounds match in the asymptotic limit of infinitely many uses of a memoryless channel and coincide with the previous result obtained by Hsieh and Wilde. Direct and converse bounds for various communication tasks are obtained as corollaries, both for the oneshot and asymptotic scenarios.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 SimplexBased Proximal Multicategory Support Vector Machine

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Sheng Fu;Piao Chen;Zhisheng Ye;
Pages: 2427  2451
Abstract: The multicategory support vector machine (MSVM) has been widely used for multicategory classification. Despite its widespread popularity, regular MSVM cannot provide direct probabilistic results and suffers from excessive computational cost, as it is formulated on the hinge loss function and it solves a sumtozero constrained quadratic programming problem. In this study, we propose a general refinement of regular MSVM, termed as the simplexbased proximal MSVM (SPMSVM). Our SPMSVM uses a novel family of squared error loss functions in place of the hinge loss and it removes the explicit sumtozero constraint by the simplex structure. Consequently, the SPMSVM only requires solving an unconstrained linear system, leading to closedform solutions. In addition, the SPMSVM can be cast into a weighted regression problem so that it is scalable for largescale applications. Moreover, the SPMSVM naturally yields an estimate of the conditional category probability, which is more informative than regular MSVM. Theoretically, the SPMSVM is shown to include many existing MSVMs as its special cases, and its asymptotic and finitesample statistical properties are well established. Simulations and real examples show that the proposed SPMSVM is a stable, scalable and competitive classifier.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Unique Sparse Decomposition of Low Rank Matrices

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Dian Jin;Xin Bing;Yuqian Zhang;
Pages: 2452  2484
Abstract: The problem of finding a unique low dimensional decomposition of a given matrix has been a fundamental and recurrent problem in many areas. In this paper, we study the problem of seeking a unique decomposition of a low rank matrix $boldsymbol Yin mathbb R ^{ptimes n}$ that admits a sparse representation. Specifically, we consider $boldsymbol Y= boldsymbol A boldsymbol X $ where the matrix $boldsymbol Ain mathbb R^{ptimes r}$ has full column rank, with $r < min {n,p}$ , and the matrix $boldsymbol Xin mathbb R^{rtimes n}$ is elementwise sparse. We prove that this low rank, sparse decomposition of $boldsymbol Y$ can be uniquely identified, up to some intrinsic signed permutation. Our approach relies on solving a nonconvex optimization problem constrained over the unit sphere. Our geometric analysis for its nonconvex optimization landscape shows that any strict local solution is close to the ground truth, and can be recovered by a simple datadriven initialization followed with any second order descent algorithm. Our theoretical findings are corroborated by numerical experiments.1
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 The Connections Among Hamming Metric, bSymbol Metric, and rth
Generalized Hamming Metric
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Minjia Shi;Hongwei Zhu;Tor Helleseth;
Pages: 2485  2493
Abstract: The $r$ th generalized Hamming metric and the $b$ symbol metric are two different generalizations of Hamming metric. The former is used on the wiretap channel of Type II, and the latter is motivated by the limitations of the reading process in highdensity data storage systems and applied to a read channel that outputs overlapping symbols. In this paper, we study the connections among the three metrics (that is, Hamming metric, $b$ symbol metric, and $r$ th generalized Hamming metric) mentioned above and give a conjecture about the $b$ symbol Griesmer Bound for cyclic codes.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Quickest Inference of Network Cascades With Noisy Information

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Anirudh Sridhar;H. Vincent Poor;
Pages: 2494  2522
Abstract: We study the problem of estimating the source of a network cascade given a time series of noisy information about the spread. Initially, there is a single vertex affected by the cascade (the source) and the cascade spreads in discrete time steps across the network. Although the cascade evolution is hidden, one observes a noisy measurement of the evolution at each time step. Given this information, we aim to reliably estimate the cascade source as fast as possible. We investigate Bayesian and minimax formulations of the source estimation problem, and derive nearoptimal estimators for simple cascade dynamics and network topologies. In the Bayesian setting, samples are taken until the error of the Bayesoptimal estimator falls below a threshold. For the minimax setting, we design a novel multihypothesis sequential probability ratio test. These optimal estimators require $log log n / log (k  1)$ observations for a $k$ regular tree network, and $(log n)^{frac {1}{ell + 1}}$ observations for a $ell $ dimensional lattice. We then discuss conjectures on source estimation in general topologies. Finally, we provide simulations which validate our theoretical results on trees and lattices, and illustrate the effectiveness of our methods for estimating the sources of cascades on ErdősRényi graphs.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 DensityConvoluted Support Vector Machines for HighDimensional
Classification
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Boxiang Wang;Le Zhou;Yuwen Gu;Hui Zou;
Pages: 2523  2536
Abstract: The support vector machine (SVM) is a popular classification method which enjoys good performance in many real applications. The SVM can be viewed as a penalized minimization problem in which the objective function is the expectation of hinge loss function with respect to the standard nonsmooth empirical measure corresponding to the true underlying measure. We further extend this viewpoint and propose a smoothed SVM by substituting a kernel density estimator for the measure in the expectation calculation. The resulting method is called density convoluted support vector machine (DCSVM). We argue that the DCSVM is particularly more interesting than the standard SVM in the context of highdimensional classification. We systematically study the rate of convergence of the elasticnet penalized DCSVM under general random design setting. We further develop novel efficient algorithm for computing elasticnet penalized DCSVM. Simulation studies and ten benchmark datasets are used to demonstrate the superior classification performance of elasticnet DCSVM over other competitors, and it is demonstrated in these numerical studies that the computation of DCSVM can be more than 100 times faster than that of the SVM.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 ActiveLATHE: An Active Learning Algorithm for Boosting the Error Exponent
for Learning Homogeneous Ising Trees
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Fengzhuo Zhang;Anshoo Tandon;Vincent Y. F. Tan;
Pages: 2537  2555
Abstract: The Chow–Liu algorithm (IEEE Trans. Inform. Theory, 1968) has been a mainstay for the learning of treestructured graphical models from i.i.d. sampled data vectors. Its theoretical properties have been wellstudied and are wellunderstood. In this paper, we focus on the class of trees that are arguably even more fundamental, namely homogeneous trees in which each pair of nodes that forms an edge has the same correlation $rho $ . We ask whether we are able to further reduce the error probability of learning the structure of the homogeneous tree model when active learning is allowed. Our figure of merit is the error exponent, which quantifies the exponential rate of decay of the error probability with an increasing number of data samples. We design and analyze an algorithm Active Learning Algorithm for Trees with Homogeneous Edges (ACTIVELATHE), which surprisingly boosts the error exponent by at least 40% when $rho $ is at least 0.8. For all other values of $rho $ , we also observe commensurate, but more modest, improvements in the error exponent. Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph in which we are less confident of being correct.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Boundary Conditions for Linear Exit Time Gradient Trajectories Around
Saddle Points: Analysis and Algorithm
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Rishabh Dixit;Mert Gürbüzbalaban;Waheed U. Bajwa;
Pages: 2556  2602
Abstract: Gradientrelated firstorder methods have become the workhorse of largescale numerical optimization problems. Many of these problems involve nonconvex objective functions with multiple saddle points, which necessitates an understanding of the behavior of discrete trajectories of firstorder methods within the geometrical landscape of these functions. This paper concerns convergence of firstorder discrete methods to a local minimum of nonconvex optimization problems that comprise strictsaddle points within the geometrical landscape. To this end, it focuses on analysis of discrete gradient trajectories around saddle neighborhoods, derives sufficient conditions under which these trajectories can escape strictsaddle neighborhoods in linear time, explores the contractive and expansive dynamics of these trajectories in neighborhoods of strictsaddle points that are characterized by gradients of moderate magnitude, characterizes the noncurving nature of these trajectories, and highlights the inability of these trajectories to reenter the neighborhoods around strictsaddle points after exiting them. Based on these insights and analyses, the paper then proposes a simple variant of the vanilla gradient descent algorithm, termed Curvature Conditioned Regularized Gradient Descent (CCRGD) algorithm, which utilizes a check for an initial boundary condition to ensure its trajectories can escape strictsaddle neighborhoods in linear time. Convergence analysis of the CCRGD algorithm, which includes its rate of convergence to a local minimum, is also presented in the paper. Numerical experiments are then provided on a test function as well as a lowrank matrix factorization problem to evaluate the efficacy of the proposed algorithm.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Almost Optimal VarianceConstrained Best Arm Identification

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yunlong Hou;Vincent Y. F. Tan;Zixin Zhong;
Pages: 2603  2634
Abstract: We design and analyze VarianceAwareLower and Upper Confidence Bound (VALUCB), a parameterfree algorithm, for identifying the best arm under the fixedconfidence setup and under a stringent constraint that the variance of the chosen arm is strictly smaller than a given threshold. An upper bound on VALUCB’s sample complexity is shown to be characterized by a fundamental varianceaware hardness quantity $H_{mathrm {VA}}$ . By proving an informationtheoretic lower bound, we show that sample complexity of VALUCB is optimal up to a factor logarithmic in $H_{mathrm {VA}}$ . Extensive experiments corroborate the dependence of the sample complexity on the various terms in $H_{mathrm {VA}}$ . By comparing VALUCB’s empirical performance to a close competitor RiskAverseUCBBAI by David et al. (2018) our experiments suggest that VALUCB has the lowest sample complexity for this class of riskconstrained best arm identification problems, especially for the riskiest instances.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Arbitrarily Varying Wiretap Channels With NonCausal Side Information at
the Jammer
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Carsten Rudolf Janda;Moritz Wiese;Eduard Axel Jorswieck;Holger Boche;
Pages: 2635  2663
Abstract: Secure communication in a potentially hostile environment is becoming more and more critical. The Arbitrarily Varying Wiretap Channel (AVWC) provides informationtheoretical bounds on how much information can be exchanged even in the presence of an active attacker. If the active attacker has noncausal side information, situations in which a legitimate communication system has been hacked can be modeled. We investigate the AVWC with noncausal side information at the jammer for the case that there exists a best channel to the eavesdropper. Noncausal side information means that the transmitted codeword is known to an active adversary before it is transmitted. By considering the maximum error criterion, we also allow messages to be known at the jammer before the corresponding codeword is transmitted. A singleletter formula for the Common Randomness (CR)assisted secrecy capacity is derived. Additionally, we provide a formula for the CRassisted secrecy capacity for the cases where the channel to the eavesdropper is strongly degraded, strongly noisier, or strongly less capable with respect to the main channel. Furthermore, we compare our results to the CRassisted secrecy capacity for the cases of maximum error criterion but without noncausal side information at the jammer (blind adversary), maximum error criterion with noncausal side information of the messages at the jammer (semiblind adversary), and the case of average error criterion without noncausal side information at the jammer (blind adversary).
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Computationally Efficient WorstCase Analysis of FlowControlled Networks
With Network Calculus
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Raffaele Zippo;Giovanni Stea;
Pages: 2664  2690
Abstract: Networks with hopbyhop flow control occur in several contexts, from data centers to systems architectures (e.g., wormholerouting networks on chip). A worstcase endtoend delay in such networks can be computed using Network Calculus (NC), an algebraic theory where traffic and service guarantees are represented as curves in a Cartesian plane. NC uses transformation operations, e.g., the minplus convolution, to model how the traffic profile changes with the traversal of network nodes. NC allows one to model flowcontrolled systems, hence one can compute the endtoend service curve describing the minimum service guaranteed to a flow traversing a tandem of flowcontrolled nodes. However, while the algebraic expression of such an endtoend service curve is quite compact, its computation is often intractable from an algorithmic standpoint: data structures tend to grow quickly to unfeasibly large sizes, making operations intractable, even with as few as three hops. In this paper, we propose computational and algebraic techniques to mitigate the above problem. We show that existing techniques (such as reduction to compact domains) cannot be used in this case, and propose an arsenal of solutions, which include methods to mitigate the data representation space explosion as well as computationally efficient algorithms for the minplus convolution operation. We show that our solutions allow a significant speedup, enable analysis of previously unfeasible case studies, and  since they do not rely on any approximation  still provide exact results.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Unimodular Perfect and Nearly Perfect Sequences: a Variation of
Björck’s Scheme
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: K. T. Arasu;Michael R Clark;Jeffrey R. Hollon;
Pages: 2691  2701
Abstract: Constant Amplitude (CA), Zero Auto Correlation (ZAC) sequences (or CAZAC sequences, aka perfect sequences) have numerous applications. We generalize the CAZAC notion to what we term as CASAC by permitting small autocorrelations (SAC). We extend Björck’s classification result of twovalued CAZAC sequences by providing a complete classification of all almost 2valued (i.e., twovalued except for the first position which uses a third value) CASAC sequences. While Björck’s original work dealt only with primes p, we extend his ideas to any abelian group of order $vequiv 1pmod {4}$ , as opposed to restricting just to the prime fields GF(p). Björck sequences have better ambiguity function than ZadoffChu sequences, making them suitable for radar and communications applications in the presence of high Doppler shifts. In fact, the discrete narrow band ambiguity function has an optimal bound in case of Björck sequences (as opposed to Gauss sequences). A oneparameter infinite family of CASAC we construct would have applications in MultipleInput MultipleOutput (MIMO) areas. Toward MIMO applications, we introduce a performance measure we term as cross merit factor to study cross correlation behavior, generalizing the wellknown notion of Golay Merit Factor (GMF).
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Vectorial BentNegabent Functions—Their Constructions and Bounds

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Enes Pasalic;Sadmir Kudin;Alexandr Polujan;Alexander Pott;
Pages: 2702  2712
Abstract: Boolean bent functions which at the same time have a flat negaHadamard transform are called bentnegabent functions. The known families of these functions mostly stem from the MaioranaMcFarland class of bent functions and their vectorial counterparts have not been considered in the literature. In this article, we introduce the notion of vectorial bentnegabent functions and show that in general for a vectorial bentnegabent function $Fcolon {mathbb {F}} _{2}^{2m} rightarrow {mathbb {F}} _{2}^{k}$ we necessarily have that $k leq m1$ . We specify a class of vectorial bentnegabent functions of maximal output dimension $m1$ by using a set of linear complete mappings. On the other hand, we propose several methods (one of which is generic) of specifying vector spaces of nonlinear complete mappings which then induce vectorial bentnegabent functions (whose dimension is not maximal) having a certain number of component functions outside the completed MaioranaMcFarland class. Finally, we derive an upper bound on the maximum number of bentnegabent components for mappings $Fcolon {mathbb {F}} _{2}^{2m} rightarrow {mathbb {F}} _{2}^{k}$ , where $m leq k leq 2m$ , and identify some families of these functions reaching this upper bound.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

 Statistical Span Property of Binary Run Sequences

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Gangsan Kim;HongYeop Song;
Pages: 2713  2721
Abstract: We define run sequences of period $2^{n}1$ as the binary sequences where the distribution of runs of 0’s and runs of 1’s is exactly same as that for the maximal length linear shift resister sequences of period $2^{n}1$ . We first count the number of all the cyclically distinct run sequences of period $2^{n}1$ . For each $n$ tuple, we consider the average number of occurrences over all the run sequences of period $2^{n}1$ . We identify the $n$ tuples with average number 1 and, in particular, those that occur exactly once in every run sequence of period $2^{n}1$ . We finally prove that, as $n$ increases, the average number of every nonzero $n$ tuple approaches to 1.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)

K Wigner Distribution: Definition, Uncertainty Principles and
TimeFrequency Analysis
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zhichao Zhang;Dong Li;Yangfan He;Yunjie Chen;Jianwei Zhang;Chengxi Zhou;
Pages: 2722  2736
Abstract: To tackle a challenge in highdimensional complex features information processing, this study extends the permanent scale Wigner distribution and the single scale $k$ Wigner distribution (kWD, formerly known as $tau $ Wigner distribution) to a novel multiscale parameterized Wigner distribution. That is the socalled $mathbf {K}$ Wigner distribution (KWD) which is able to use different scales to extract different types of features at different dimensions. Heisenbergtype uncertainty inequalities of the KWD are established, giving rise to the tightest universal attainable lower bound for all functions on the uncertainty product in timeKWD and Fouier transformKWD domains, and two versions of attainable lower bounds for complexvalued functions. The obtained results solve an important concern regarding the limit of the KWD’s timefrequency resolution influenced by the parameter matrix. As an application, the derived uncertainty inequalities are applied to estimate the bandwidth in KWD domains. The timefrequency resolution performance of the multiscale KWD, as compared with that of the single scale kWD, is investigated in details. The optimal parameter matrix of the KWD achieving the best performance is then generated, which solves an important concern regarding the KWD’s parameter matrix selection. Examples are also carried out to demonstrate the usefulness and effectiveness of the proposed technique.
PubDate: April 2023
Issue No: Vol. 69, No. 4 (2023)
