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.
Pages: C2  C2
PubDate: June 2023
Issue No: Vol. 69, No. 6 (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.
Pages: C3  C3
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Tradeoff Between Diversity and Multiplexing Gains in Block Fading Optical
Wireless Channels
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: Sufang Yang;Longguang Li;Haoyue Tang;Jintao Wang;
Pages: 3415  3430
Abstract: The diversitymultiplexing tradeoff (DMT) provides a fundamental performance metric for different multipleinput multipleoutput (MIMO) schemes in wireless communications. In this paper, we explore the block fading optical wireless communication (OWC) channels and characterize the DMT in the presence of both optical peak and averagepower constraints. Three different fading distributions are considered, which reflect different channel conditions. In each channel condition, we obtain the optimal DMT when the block length is sufficiently large, and we also derive the lower and upper bounds of the DMT curve when the block length is small. These results are dramatically different from the existing DMT results in radiofrequency (RF) channels. These differences may be due to the fact that the optical input signal is real and bounded, while its RF counterpart is usually complex and unbounded.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Rényi Entropy and Variance Comparison for Symmetric LogConcave
Random Variables
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: Maciej Białobrzeski;Piotr Nayar;
Pages: 3431  3438
Abstract: We show that for any $alpha>0$ the Rényi entropy of order $alpha $ is minimized, among all symmetric logconcave random variables with fixed variance, either for a uniform distribution or for a two sided exponential distribution. The first case occurs for $alpha in (0,alpha ^{ast}]$ and the second case for $alpha in [alpha ^{ast},infty$ ), where $alpha ^{ast}$ satisfies the equation $2 log alpha ^{ast}= (alpha ^{ast}1) log 6$ , that is $alpha ^{ast} approx 1.241$ . We deduce that the onesided exponential distribution minimizes Rényi entropy of order $alpha geq 2$ among all logconcave random variables with fixed variance.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Fundamental Limits of CacheAided MIMO Wireless Networks

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: Antonious M. Girgis;Ozgur Ercetin;Mohammed Nafie;Tamer ElBatt;
Pages: 3439  3459
Abstract: This paper studies the MultiInputMultiOutput (MIMO) interference networks with arbitrary number of transmitters and receivers, where both the transmitters and receivers are equipped with caches. The main goal is to design content placement and delivery schemes that minimize the worst case normalized delivery time (NDT). First, we propose a delivery scheme for the cacheaided SingleInputMultipleOutput (SIMO) interference networks. Then, we obtain the achievable NDT of the cacheaided MIMO interference networks using the decomposition property of splitting each multiantenna transmitter into multiple single antenna transmitters. Furthermore, we derive an informationtheoretic bound on the optimal NDT of the cacheaided MIMO interference network. Analytical results show that the proposed scheme is within a multiplicative gap of 2 from the derived lower bound independent of all system parameters for any uncoded cache placement scheme. We also derive a novel delivery scheme for the cacheaided MultiInputSingleOutput (MISO) interference network outperforming our proposed scheme for the cacheaided MIMO interference network. The numerical results show the superiority of our proposed scheme over the stateoftheart schemes in the literature. Our results show that the coded caching gain has a more significant contribution in reducing the transmission latency than the spatial multiplexing gain. Our results indicate that the receiveantennas become more effective in reducing the NDT than the transmitantennas in the presence of caches at the receiverside. In addition, we show that increasing the number of transmitantennas has a higher gain in reducing the NDT than adding more transmitters in the cacheaided MISO interference network.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Bregman Divergence Based Em Algorithm and its Application to Classical and
Quantum Rate Distortion Theory
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: Masahito Hayashi;
Pages: 3460  3492
Abstract: We formulate em algorithm in the framework of Bregman divergence, which is a general problem setting of information geometry. That is, we address the minimization problem of the Bregman divergence between an exponential subfamily and a mixture subfamily in a Bregman divergence system. Then, we show the convergence and its speed under several conditions. We apply this algorithm to rate distortion and its variants including the quantum setting, and show the usefulness of our general algorithm. In fact, existing applications of ArimotoBlahut algorithm to rate distortion theory make the optimization of the weighted sum of the mutual information and the cost function by using the Lagrange multiplier. However, in rate distortion theory, it is needed to minimize the mutual information under the constant constraint for the cost function. Our algorithm directly solves this minimization. In addition, we have numerically checked the convergence speed of our algorithm in the classical case of rate distortion problem.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Undecidability of Network Coding, Conditional Information Inequalities,
and Conditional Independence Implication
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: Cheuk Ting Li;
Pages: 3493  3510
Abstract: We resolve three longstanding open problems, namely the (algorithmic) decidability of network coding, the decidability of conditional information inequalities, and the decidability of conditional independence implication among random variables, by showing that these problems are undecidable. The proof utilizes a construction inspired by Herrmann’s arguments on embedded multivalued database dependencies, a network studied by Dougherty, Freiling and Zeger, together with a novel construction to represent group automorphisms on top of the network.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 MultiBit Relaying Over a Tandem of Channels

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: Yan Hao Ling;Jonathan Scarlett;
Pages: 3511  3524
Abstract: We study error exponents for the problem of relaying a message over a tandem of two channels sharing the same transition law, in particular moving beyond the 1bit setting studied in recent related works. Our main results show that the 1hop and 2hop exponents coincide in both of the following settings: (i) the number of messages is fixed, and the channel law satisfies a condition called pairwise reversibility, or (ii) the channel is arbitrary, and a zerorate limit is taken from above. In addition, we provide various extensions of our results that relax the assumptions of pairwise reversibility and/or the two channels having identical transition laws, and we provide an example for which the 2hop exponent is strictly below the 1hop exponent.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Achievable Refined Asymptotics for Successive Refinement Using Gaussian
Codebooks
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: Lin Bai;Zhuangfei Wu;Lin Zhou;
Pages: 3525  3543
Abstract: We study the mismatched successive refinement problem where one uses Gaussian codebooks to compress an arbitrary memoryless source with successive minimum Euclidean distance encoding under the quadratic distortion measure. Specifically, we derive achievable refined asymptotics under both the joint excessdistortion probability (JEP) and the separate excessdistortion probabilities (SEP) criteria. For both secondorder and moderate deviations asymptotics, we consider two types of codebooks: the spherical codebook where each codeword is drawn independently and uniformly from the surface of a sphere and the i.i.d. Gaussian codebook where each component of each codeword is drawn independently from a Gaussian distribution. We establish the achievable secondorder rateregion under JEP and we show that under SEP any memoryless source satisfying mild moment conditions is strongly successively refinable. When specialized to a Gaussian memoryless source (GMS), our results provide an alternative achievability proof with specific code design. We show that under JEP and SEP, the same moderate deviations constant is achievable. For large deviations asymptotics, we only consider the i.i.d. Gaussian codebook since the i.i.d. Gaussian codebook has better performance than the spherical codebook in this regime for the one layer mismatched ratedistortion problem (Zhou et al., 2019). We derive achievable exponents of both JEP and SEP and specialize our results to a GMS, which appears to be a novel result of independent interest.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Classification of ΔDivisible Linear Codes Spanned by Codewords of
Weight Δ
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: Michael Kiermaier;Sascha Kurz;
Pages: 3544  3551
Abstract: We classify all $q$ ary $Delta $ divisible linear codes which are spanned by codewords of weight $Delta $ . The basic building blocks are the simplex codes, and for $q=2$ additionally the first order ReedMuller codes and the parity check codes. This generalizes a result of Pless and Sloane, where the binary selforthogonal codes spanned by codewords of weight 4 have been classified, which is the case $q=2$ and $Delta =4$ of our classification. As an application, we give an alternative proof of a theorem of Liu on binary $Delta $ divisible codes of length $4Delta $ in the projective case.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Lossy Compression With Universal Distortion

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: Adeel Mahmood;Aaron B. Wagner;
Pages: 3552  3573
Abstract: We consider a novel variant of $d$ semifaithful lossy coding in which the distortion measure is revealed only to the encoder and only at runtime, as well as an extension of it in which the distortion constraint $d$ is also revealed at runtime. Two forms of rate redundancy are used to analyze the performance, and achievability results of both a pointwise and minimax nature are demonstrated. The first coding scheme uses ideas from VC dimension and growth functions, the second uses appropriate quantization of the space of distortion measures, and the third relies on a random coding argument.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Improved Decoding of Expander 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: Xue Chen;Kuan Cheng;Xin Li;Minghui Ouyang;
Pages: 3574  3589
Abstract: We study the classical expander codes, introduced by Sipser and Spielman, (1996). Given any constants $0 < alpha, varepsilon < 1/2$ , and an arbitrary bipartite graph with $N$ vertices on the left, $M < N$ vertices on the right, and left degree $D$ such that any left subset $S$ of size at most $alpha N$ has at least $(1 varepsilon) S D$ neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly $frac {alpha N}{2 varepsilon }$ . This is strictly better than the best known previous result of $2(1 varepsilon) alpha N$ Sudan, (2000), Viderman, (2013) whenever $varepsilon < 1/2$ , and improves the previous result significantly when $varepsilon $ is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever $varepsilon < frac {1}{4}$ . Finally, we also give a bound on the listdecoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new sizeexpansion tradeoff, which may be of independent interests.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Improved Error Bounds for the Distance Distribution of ReedSolomon 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: Zhicheng Gao;Jiyou Li;
Pages: 3590  3596
Abstract: We use the generating function approach to derive simple expressions for the factorial moments of the distance distribution over ReedSolomon codes. We obtain better upper bounds for the error term of a counting formula given by Li and Wan, which gives nontrivial estimates on the number of polynomials over finite fields with prescribed leading coefficients and a given number of linear factors. This improvement leads to new results on the classification of deep holes of ReedSolomon codes.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Learning Maximum Margin Channel Decoders

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: Amit Tsvieli;Nir Weinberger;
Pages: 3597  3626
Abstract: The problem of learning a channel decoder is considered for two channel models. The first model is an additive noise channel whose noise distribution is unknown and nonparametric. The learner is provided with a fixed codebook and a dataset comprised of independent samples of the noise, and is required to select a precision matrix for a nearest neighbor decoder in terms of the Mahalanobis distance. The second model is a nonlinear channel with additive white Gaussian noise and unknown channel transformation. The learner is provided with a fixed codebook and a dataset comprised of independent inputoutput samples of the channel, and is required to select a matrix for a nearest neighbor decoder with a linear kernel. For both models, the objective of maximizing the margin of the decoder is addressed. Accordingly, for each channel model, a regularized loss minimization problem with a codebookrelated regularization term and hingelike loss function is developed, which is inspired by the support vector machine paradigm for classification problems. Expected generalization error bounds for the error probability loss function are provided for both models, under optimal choice of the regularization parameter. For the additive noise channel, a theoretical guidance for choosing the training signaltonoise ratio is proposed based on this bound. In addition, for the nonlinear channel, a high probability uniform generalization error bound is provided for the hypothesis class. For each channel, a stochastic subgradient descent algorithm for solving the regularized loss minimization problem is proposed, and an optimization error bound is stated. The performance of the proposed algorithms is demonstrated through several examples.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Linear Maximum Rank Distance Codes of Exceptional Type

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: Daniele Bartoli;Giovanni Zini;Ferdinando Zullo;
Pages: 3627  3636
Abstract: Scattered polynomials of a given index over finite fields are intriguing rare objects with many connections within mathematics. Of particular interest are the exceptional ones, as defined in 2018 by the first author and Zhou, for which partial classification results are known. In this paper we propose a unified algebraic description of $mathbb {F}_{q^{n}}$ linear maximum rank distance codes, introducing the notion of exceptional linear maximum rank distance codes of a given index. Such a connection naturally extends the notion of exceptionality for a scattered polynomial in the rank metric framework and provides a generalization of Moore sets in the monomial MRD context. We move towards the classification of exceptional linear MRD codes, by showing that the ones of index zero are generalized Gabidulin codes and proving that in the positive index case the code contains an exceptional scattered polynomial of the same index.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Trapping and Absorbing Set Enumerators for Irregular Generalized
LowDensity ParityCheck Code Ensembles
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: Emna Ben Yacoub;
Pages: 3637  3662
Abstract: The definitions of (elementary) trapping and (fully) absorbing sets are extended to generalized lowdensity paritycheck (GLDPC) codes. In particular, the fully absorbing sets are stable under the bit flipping algorithm. The finitelength (elementary) trapping and (fully) absorbing set enumerators for unstructured irregular GLDPC code ensembles are derived using generating functions. An efficient method to evaluate the asymptotic trapping and (fully) absorbing set distributions is presented, which requires solving a system of equations. Using this method, the asymptotic distribution of trapping and (fully) absorbing sets are evaluated for some example GLDPC code ensembles. Experimental results show that the proposed definitions yield graph structures that are harmful for bit flipping decoders. The generating function approach is also used to derive the finitelength and asymptotic trapping and (elementary) absorbing set enumerators for nonbinary irregular LDPC code ensembles.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 The Covering Radius of the ThirdOrder ReedMuller Code RM(3,7) is 20

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: Jinjie Gao;Haibin Kan;Yuan Li;Qichun Wang;
Pages: 3663  3673
Abstract: We prove the covering radius of the thirdorder ReedMuller code $mathrm {RM}(3,7)$ is 20, which was previously known to be between 20 and 23 (inclusive). The covering radius of $mathrm {RM}(3,7)$ is the maximum thirdorder nonlinearity among all 7variable Boolean functions. It was known that there exist 7variable Boolean functions with thirdorder nonlinearity 20. We prove the thirdorder nonlinearity cannot achieve 21. According to the classification of the quotient space of $mathrm {RM}(6,6)/mathrm {RM}(3,6)$ , we classify all 7variable Boolean functions into 66 types. Firstly, we prove 62 types (among 66) cannot have thirdorder nonlinearity 21; Secondly, we prove that any function in the remaining 4 types can be transformed into a type (6, 10) function, if its thirdorder nonlinearity is 21; Finally, we transform type (6, 10) functions into a specific form, and prove the functions in that form cannot achieve the thirdorder nonlinearity 21 (with the assistance of computers). By the way, we prove that the affine transformation group over any finite field can be generated by two elements.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Online Versus Offline Rate in Streaming Codes for VariableSize Messages

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: Michael Rudow;K. V. Rashmi;
Pages: 3674  3690
Abstract: One pervasive challenge in providing a high qualityofservice for live communication is to recover lost packets in realtime. Streaming codes are a class of erasure codes that are designed for such strict, lowlatency streaming communication settings. Motivated by applications that transmit messages whose sizes vary over time, such as live video streaming, this paper considers the setting of streaming codes under variablesize messages. In practice, streaming codes operate in an “online” setting where the sizes of the future messages are unknown. “Offline” codes, in contrast, have access to the sizes of all messages, including future ones. This paper introduces the first online rateoptimal streaming codes for communicating over a burstonly packet loss channel for two broad parameter regimes. These two online codes match the rates of optimal offline codes for the two settings despite the apparent advantage of the offline setting. This paper further establishes that online codes cannot attain the optimal rate for offline codes for all remaining parameter settings.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 BasisFinding Algorithm for Decoding Fountain Codes for DNABased Data
Storage
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: Xuan He;Kui Cai;
Pages: 3691  3707
Abstract: In this paper, we consider the decoding of fountain codes where the received symbols may have errors. It is motivated by the application of fountain codes in DNAbased data storage systems where the inner code decoding, which generally has undetectable errors, is performed before the outer fountain code decoding. We propose a novel and efficient decoding algorithm, namely basisfinding algorithm (BFA), followed by three implementations. The key idea of the BFA is to find a basis of the received symbols, and then use the most reliable basis elements to recover the source symbols with the inactivation decoding. Gaussian elimination is used to find the basis and to identify the most reliable basis elements. As a result, the BFA has polynomial time complexity. For random fountain codes, we are able to derive some theoretical bounds for the frame error rate (FER) of the BFA. Extensive simulations with Luby transform (LT) codes show that, the BFA has significantly lower FER than the belief propagation (BP) algorithm except for an extremely large amount of received symbols, and the FER of the BFA generally decreases as the average weight of basis elements increases.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Network 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: Allison Beemer;Altan B. Kılıç;Alberto Ravagnani;
Pages: 3708  3730
Abstract: We consider the problem of error control in a coded, multicast network, focusing on the scenario where the errors can occur only on a proper subset of the network edges. We model this problem via an adversarial noise, presenting a formal framework and a series of techniques to obtain upper and lower bounds on the network’s (1shot) capacity, improving on the best currently known results. In particular, we show that traditional cutset bounds are not tight in general in the presence of a restricted adversary, and that the nontightness of these is caused precisely by the restrictions imposed on the noise (and not, as one may expect, by the alphabet size). We also show that, in sharp contrast with the typical situation within network coding, capacity cannot be achieved in general by combining linear network coding with endtoend channel coding, not even when the underlying network has a single source and a single terminal. We finally illustrate how network decoding techniques are necessary to achieve capacity in the scenarios we examine, exhibiting capacityachieving schemes and lower bounds for various classes of networks.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Group Properties of Polar Codes for Automorphism Ensemble 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: Valerio Bioglio;Ingmar Land;Charles Pillet;
Pages: 3731  3747
Abstract: In this paper, we propose an analysis of the automorphism group of polar codes, with the aim of designing codes tailored for automorphism ensemble (AE) decoding. Using a novel description of polar codes as monomial codes through negative monomials, we prove the equivalence between the notion of decreasing monomial codes and the universal partial order (UPO) framework for polar codes; this property is widely believed to hold true but a formal proof was missing. We further provide a rigorous mathematical connection between code word permutations and affine transformations, an important link to understand the considered automorphisms. Based on this mathematical formalisms, we analyze the algebraic properties of the affine automorphisms group of polar codes, providing a novel description of its structure. We classify automorphisms such that all automorphisms in the same class lead to the same result under permutation decoding, which gives rise to the concept of redundant automorphisms. Mathematically this is achieved by introducing equivalence classes of affine automorphisms under AEbased decoding. For practical application, we provide an algorithm to compute representatives for the equivalence classes, such that one automorphism from each equivalence class can be selected for use in AE decoding. A numerical analysis of the error correction performance of AE decoding of polar codes, based on equivalence classes, concludes the paper.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Covering Grassmannian Codes: Bounds and Constructions

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: Bingchen Qian;Xin Wang;Chengfei Xie;Gennian Ge;
Pages: 3748  3758
Abstract: Grassmannian $mathcal {G}_{q}(n,k)$ is the set of all $k$ dimensional subspaces of the vector space $mathbb {F}_{q}^{n}$ . Recently, Etzion and Zhang introduced a new notion called covering Grassmannian code which can be used in network coding solutions for generalized combination networks. An $alpha $  $(n,k,delta)_{q}^{c}$ covering Grassmannian code $mathcal {C}$ is a subset of $mathcal {G}_{q}(n,k)$ such that every set of $alpha $ codewords of $mathcal {C}$ spans a subspace of dimension at least $delta +k$ in $mathbb {F}_{q}^{n}$ . In this paper, we derive new upper and lower bounds on the size of covering Grassmannian codes. These bounds improve and extend the parameter range of known bounds.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 The PartialInverse Approach to Linearized Polynomials and Gabidulin Codes
With Applications to Network 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: JiunHung Yu;HansAndrea Loeliger;
Pages: 3759  3774
Abstract: This paper introduces the partialinverse problem for linearized polynomials and develops its application to decoding Gabidulin codes and lifted Gabidulin codes in linear random network coding. The proposed approach is a natural generalization of its counterpart for ordinary polynomials, thus providing a unified perspective on Reed–Solomon codes for the Hamming metric and for the rank metric. The basic algorithm for solving the partialinverse problem is a common parent algorithm of a Berlekamp–Massey algorithm, a Euclidean algorithm, and yet another algorithm, all of which are obtained as easy variations of the basic algorithm. Decoding Gabidulin codes can be reduced to the partialinverse problem via a key equation with a new converse. This paper also develops new algorithms for interpolating crisscross erasures and for joint decoding of errors, erasures, and deviations in random network coding.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Constructing MSR Codes With Subpacketization 2
n/3 for k + 1 Helper Nodes

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: Ningning Wang;Guodong Li;Sihuang Hu;Min Ye;
Pages: 3775  3792
Abstract: Wang et al. (IEEE Transactions on Information Theory, vol. 62, no. 8, 2016) proposed an explicit construction of an $(n=k+2,k)$ Minimum Storage Regenerating (MSR) code with 2 parity nodes and subpacketization $2^{k/3}$ . The number of helper nodes for this code is $d=k+1=n1$ , and this code has the smallest subpacketization among all the existing explicit constructions of MSR codes with the same $n,k$ and $d$ . In this paper, we present a new construction of MSR codes for a wider range of parameters. More precisely, we still fix $d=k+1$ , but we allow the code length $n$ to be any integer satisfying $nge k+2$ . The field size of our code is linear in $n$ , and the subpacketization of our code is $2^{n/3}$ . This value is slightly larger than the subpacketization of the construction by Wang et al. because their code construction only guarantees optimal repair for all the systematic nodes while our code construction guarantees optimal repair for all nodes.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Corrections to “Analog ErrorCorrecting 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: Ron M. Roth;
Pages: 3793  3794
Abstract: In the above article [1], Lemma 2 contained an error, which also affects the proof of Theorem 1 therein. Specifically, Theorem 1 holds only when $sigma = 0$ or when $tau = 0$ ; otherwise, the “if” part in the theorem requires a stronger condition.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Sensing RISs: Enabling DimensionIndependent CSI Acquisition for
Beamforming
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: Jieao Zhu;Kunzan Liu;Zhongzhichao Wan;Linglong Dai;Tie Jun Cui;H. Vincent Poor;
Pages: 3795  3813
Abstract: Reconfigurable intelligent surfaces (RISs) are envisioned as a potentially transformative technology for future wireless communications. However, RISs’ inability to process signals and the attendant increased channel dimension have brought new challenges to RISassisted systems, including significantly increased pilot overhead required for channel estimation. To address these problems, several prior contributions that enhance the hardware architecture of RISs or develop algorithms to exploit the channels’ mathematical properties have been made, where the required pilot overhead is reduced to be proportional to the number of RIS elements. In this paper, we propose a dimensionindependent channel state information (CSI) acquisition approach in which the required pilot overhead is independent of the number of RIS elements. Specifically, in contrast to traditional signal transmission methods, where signals from the base station (BS) and the users are transmitted in different time slots, we propose a novel method in which signals are transmitted from the BS and the user simultaneously during CSI acquisition. With this method, an electromagnetic interference random field (IRF) will be induced on the RIS, and we propose the structure of sensing RIS to capture its features. Moreover, we develop three algorithms for parameter estimation in this system, in which one of the proposed vMEM algorithm is analyzed with the fixedpoint perturbation method to obtain an asymptotic achievable bound. In addition, we also derive the CramérRao lower bound (CRLB) and an asymptotic expression for characterizing the best possible performance of the proposed algorithms. Simulation results verify that our proposed signal transmission method and the corresponding algorithms can achieve dimensionindependent CSI acquisition for beamforming.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Mutually Unbiased Measurements, Hadamard Matrices, and Superdense 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: Máté Farkas;Jędrzej Kaniewski;Ashwin Nayak;
Pages: 3814  3824
Abstract: Mutually unbiased bases (MUBs) are highly symmetric bases on complex Hilbert spaces, and the corresponding rank1 projective measurements are ubiquitous in quantum information theory. In this work, we study a recently introduced generalisation of MUBs called mutually unbiased measurements (MUMs). These measurements inherit the essential property of complementarity from MUBs, but the Hilbert space dimension is no longer required to match the number of outcomes. This operational complementarity property renders MUMs highly useful for deviceindependent quantum information processing. It has been shown that MUMs are strictly more general than MUBs. In this work we provide a complete proof of the characterisation of MUMs that are direct sums of MUBs. We then construct new examples of MUMs that are not direct sums of MUBs. A crucial technical tool for this construction is a correspondence with quaternionic Hadamard matrices, which allows us to map known examples of such matrices to MUMs that are not direct sums of MUBs. Furthermore, we show that—in stark contrast with MUBs—the number of MUMs for a fixed outcome number is unbounded. Next, we focus on the use of MUMs in quantum communication. We demonstrate how any pair of MUMs with $d$ outcomes defines a $d$ dimensional superdense coding protocol. Using MUMs that are not direct sums of MUBs, we disprove a recent conjecture due to Nayak and Yuen on the rigidity of superdense coding, for infinitely many dimensions. The superdense coding protocols arising in the refutation reveal how shared entanglement may be used in a manner heretofore unknown.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 The Platypus of the Quantum Channel Zoo

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: Felix Leditzky;Debbie Leung;Vikesh Siddhu;Graeme Smith;John A. Smolin;
Pages: 3825  3849
Abstract: Understanding quantum channels and the strange behavior of their capacities is a key objective of quantum information theory. Here we study a remarkably simple, lowdimensional, singleparameter family of quantum channels with exotic quantum informationtheoretic features. As the simplest example from this family, we focus on a qutrittoqutrit channel that is intuitively obtained by hybridizing together a simple degradable channel and a completely useless qubit channel. Such hybridizing makes this channel’s capacities behave in a variety of interesting ways. For instance, the private and classical capacity of this channel coincide and can be explicitly calculated, even though the channel does not belong to any class for which the underlying information quantities are known to be additive. Moreover, the quantum capacity of the channel can be computed explicitly, given a clear and compelling conjecture is true. This “spin alignment conjecture,” which may be of independent interest, is proved in certain special cases and additional numerical evidence for its validity is provided. Finally, we generalize the qutrit channel in two ways, and the resulting channels and their capacities display similarly rich behavior. In a companion paper, we further show that the qutrit channel demonstrates superadditivity when transmitting quantum information jointly with a variety of assisting channels, in a manner unknown before.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Distributed Sketching for Randomized Optimization: Exact Characterization,
Concentration, and Lower 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: Burak Bartan;Mert Pilanci;
Pages: 3850  3879
Abstract: We consider distributed optimization methods for problems where forming the Hessian is computationally challenging and communication is a significant bottleneck. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems. We derive novel approximation guarantees for classical sketching methods and establish tight concentration results that serve as both upper and lower bounds on the error. We then extend our analysis to the accuracy of parameter averaging for distributed sketches. Furthermore, we develop unbiased parameter averaging methods for randomized second order optimization in regularized problems that employ sketching of the Hessian. Existing works do not take the bias of the estimators into consideration, which limits their application to massively parallel computation. We provide closedform formulas for regularization parameters and step sizes that provably minimize the bias for sketched Newton directions. Additionally, we demonstrate the implications of our theoretical findings via large scale experiments on a serverless cloud computing platform.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Multiway Spherical Clustering Via DegreeCorrected Tensor Block Models

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: Jiaxin Hu;Miaoyan Wang;
Pages: 3880  3919
Abstract: We consider the problem of multiway clustering in the presence of unknown degree heterogeneity. Such data problems arise commonly in applications such as recommendation system, neuroimaging, community detection, and hypergraph partitions in social networks. The allowance of degree heterogeneity provides great flexibility in clustering models, but the extra complexity poses significant challenges in both statistics and computation. Here, we develop a degreecorrected tensor block model with estimation accuracy guarantees. We present the phase transition of clustering performance based on the notion of angle separability, and we characterize three signaltonoise regimes corresponding to different statisticalcomputational behaviors. In particular, we demonstrate that an intrinsic statisticaltocomputational gap emerges only for tensors of order three or greater. Further, we develop an efficient polynomialtime algorithm that provably achieves exact clustering under mild signal conditions. The efficacy of our procedure is demonstrated through two data applications, one on human brain connectome project, and another on Peru Legislation network dataset.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Optimal Prediction of Markov Chains With and Without Spectral Gap

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: Yanjun Han;Soham Jana;Yihong Wu;
Pages: 3920  3959
Abstract: We study the following learning problem with dependent data: Observing a trajectory of length $n$ from a stationary Markov chain with $k$ states, the goal is to predict the next state. For $3 leq k leq O(sqrt {n})$ , using techniques from universal compression, the optimal prediction risk in KullbackLeibler divergence is shown to be $Theta left({frac {k^{2}}{n}log frac {n}{k^{2}}}right)$ , in contrast to the optimal rate of $Theta left({frac {log log n}{n}}right)$ for $k=2$ previously shown in Falahatgar et al. (2016). These rates, slower than the parametric rate of $Oleft({frac {k^{2}}{n}}right)$ , can be attributed to the memory in the data, as the spectral gap of the Markov chain can be arbitrarily small. To quantify the memory effect, we study irreducible reversible chains with a prescribed spectral gap. In addition to characterizing the optimal prediction risk for two states, we show that, as long as the spectral gap is not excessively small, the prediction risk in the Markov model is $Oleft({frac {k^{2}}{n}}right)$ , which coincides with that of an iid model with the same number of parameters. Extensions to higherorder Markov chains are also obtained.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Approximation Speed of Quantized Versus Unquantized ReLU Neural Networks
and Beyond
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: Antoine Gonon;Nicolas Brisebarre;Rémi Gribonval;Elisa Riccietti;
Pages: 3960  3977
Abstract: We deal with two complementary questions about approximation properties of ReLU networks. First, we study how the uniform quantization of ReLU networks with realvalued weights impacts their approximation properties. We establish an upperbound on the minimal number of bits per coordinate needed for uniformly quantized ReLU networks to keep the same polynomial asymptotic approximation speeds as unquantized ones. We also characterize the error of nearestneighbour uniform quantization of ReLU networks. This is achieved using a new lowerbound on the Lipschitz constant of the map that associates the parameters of ReLU networks to their realization, and an upperbound generalizing classical results. Second, we investigate when ReLU networks can be expected, or not, to have better approximation properties than other classical approximation families. Indeed, several approximation families share the following common limitation: their polynomial asymptotic approximation speed of any set is bounded from above by the encoding speed of this set. We introduce a new abstract property of approximation families, called $infty $ encodability, which implies this upperbound. Many classical approximation families, defined with dictionaries or ReLU networks, are shown to be $infty $ encodable. This unifies and generalizes several situations where this upperbound is known.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 On
L ^{2}Consistency of Nearest Neighbor
Matching
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: James Sharpnack;
Pages: 3978  3988
Abstract: Biased sampling and missing data complicates statistical problems ranging from causal inference to reinforcement learning. We often correct for biased sampling of summary statistics with matching methods and importance weighting. In this paper, we study nearest neighbor matching (NNM), which makes estimates of population quantities from biased samples by substituting unobserved variables with their nearest neighbors in the biased sample. We show that NNM is $L^{2}$ consistent in the absence of smoothness and boundedness assumptions in finite dimensions. We discuss applications of NNM, outline the barriers to generalizing this work to separable metric spaces, and compare NNM to inverse probability weighting.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Rigorous State Evolution Analysis for Approximate Message Passing With
Side 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: Hangjin Liu;Cynthia Rush;Dror Baron;
Pages: 3989  4013
Abstract: A common goal in many research areas is to reconstruct an unknown signal $mathbf {x}$ from noisy linear measurements. Approximate message passing (AMP) is a class of lowcomplexity algorithms that can be used for efficiently solving such highdimensional regression tasks. Often, it is the case that side information (SI) is available during reconstruction, for example in online learning applications. For this reason, a novel algorithmic framework that incorporates SI into AMP, referred to as approximate message passing with side information (AMPSI), has been recently introduced. In this work, we provide rigorous performance guarantees for AMPSI when there are statistical dependencies between the signal and SI pairs and the entries of the measurement matrix are independent and identically distributed (i.i.d.) Gaussian. We also allow for statistical dependencies within the elements of the signal itself, by considering a flexible AMPSI framework incorporating both separable and nonseparable denoisers. The AMPSI performance is shown to be provably tracked by a scalar iteration referred to as state evolution (SE). Moreover, we provide numerical examples that demonstrate empirically that the SE can predict the AMPSI mean square error accurately.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Inferring the Mixing Properties of a Stationary Ergodic Process From a
Single SamplePath
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: Azadeh Khaleghi;Gabor Lugosi;
Pages: 4014  4026
Abstract: We propose strongly consistent estimators of the $ell _{1}$ norm of the sequence of $alpha $ mixing (respectively $beta $ mixing) coefficients of a stationary ergodic process. We further provide strongly consistent estimators of individual $alpha $ mixing (respectively $beta $ mixing) coefficients for a subclass of stationary $alpha $ mixing (respectively $beta $ mixing) processes with summable sequences of mixing coefficients. The estimators are in turn used to develop strongly consistent goodnessoffit hypothesis tests. In particular, we develop hypothesis tests to determine whether, under the same summability assumption, the $alpha $ mixing (respectively $beta $ mixing) coefficients of a process are upper bounded by a given rate function. Moreover, given a sample generated by a (not necessarily mixing) stationary ergodic process, we provide a consistent test to discern the null hypothesis that the $ell _{1}$ norm of the sequence $boldsymbol {alpha }$ of $alpha $ mixing coefficients of the process is bounded by a given threshold $gamma in [0,inty$ ) from the alternative hypothesis that $left lVert{ boldsymbol {alpha }}right rVert> gamma $ . An analogous goodnessoffit test is proposed for the $ell _{1}$ norm of the sequence of $beta $ mixing coefficients of a stationary ergodic process. Moreover, the procedure gives rise to an asymptotically consistent test for independence.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 The Number of Nonequivalent Monotone Boolean Functions of 8 Variables

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: Marko Carić;Miodrag Živković;
Pages: 4027  4034
Abstract: A Boolean function $f:{0,1}^{n}mapsto {0,1}$ is a monotone Boolean function (MBF) of $n$ variables if for each pair of vectors $x,yin {0,1}^{n}$ from $xleqslant y$ follows $f(x)leqslant f(y)$ . Two MBFs are considered equivalent if one of them can be obtained from the other by permuting the input variables. Let $d_{n}$ be the number of MBFs of $n$ variables (which is known as Dedekind number) and let $r_{n}$ be a number of nonequivalent MBFs of $n$ variables. The numbers $d_{n}$ and $r_{n}$ have been so far calculated for $nleqslant 8$ , and $nleqslant 7$ , respectively. This paper presents the calculation of $r_{8}=1 392 195 548 889 993 358$ . Determining Dedekind numbers and $r_{n}$ is a longstanding problem.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 New Results on the −1 Conjecture on CrossCorrelation of mSequences
Based on Complete Permutation Polynomials
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: Gaofei Wu;Keqin Feng;Nian Li;Tor Helleseth;
Pages: 4035  4044
Abstract: The crosscorrelation between two maximum length sequences ( $m$ sequences) of the same period has been studied since the end of 1960s. One open conjecture by Helleseth states that the crosscorrelation between any two $p$ ary $m$ sequences takes on the value −1 for at least one shift provided that the decimation $d$ obeys $dequiv 1,({mathrm{ mod}}, p1)$ . This was known as the −1 conjecture. Up to now, the −1 conjecture was confirmed for the following decimations: (1) Nihotype decimations, i.e., $d=s(p^{n/{2}}1)+1$ , where $s$ is an integer; (2) all the complete permutation polynomial (CPP) exponents $d$ satisfying $dequiv 1, ({mathrm{ mod}}, p1) $ ; and (3) the additional families of decimations tabulated in this paper. In this paper, we first discuss the connection between the −1 conjecture on crosscorrelation of $m$ sequences and CPP exponents, then we confirm the −1 conjecture for a new type of decimations by giving a new class of CPP exponents. The decimations are of the type $d=1+l{(p^{rtm}1)}/{(r+1)}$ over ${mathbb F}_{p^{rtm}}$ , where $p$ is a prime, $r+1$ is an odd prime satisfying $p^{r/{2}} equiv 1,({mathrm{ mod}}, r+1)$ , $t$ is an odd integer ( $t>2$ if $p=2$ ) with $gcd (t,r)=1$ , and $m$ is a positive integer. We transform the problem of determining whether $d$ is a CPP exponent into that of investigating the existence of irreducible polynomials over $mathbb {F}_{p}$ with degree $t$ satisfying a congruence equation. By a theorem given by Rosen that considered the number of irreducible polynomials with a special congruence relation, we prove that $d$ is a CPP exponent over ${mathbb F}_{p^{rtm}}$ for sufficiently large $t$ . When $m$ is odd, our new CPP exponents are of Niho type; thus, we give a new class of CPP exponents of Niho type. When $m$ is ev
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Constructing CM Fields for NFS to Accelerate DL Computation in NonPrime
Finite Fields
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: Yuqing Zhu;Jiqiang Liu;
Pages: 4045  4055
Abstract: The hardness of discrete logarithm problem (DLP) over finite fields is the security foundation of many cryptographic protocols. When the characteristic is not small, the stateoftheart algorithms for solving DLP are the number field sieve (NFS) and its variants. In the relation collection step, to translate the relations between prime ideals to those of elements one needs to use the Schirokauer map. Besides, if the number field has nontrivial automorphisms, one can use them to accelerate the factorbase logarithms computation. However, the Schirokauer map is not compatible with automorphisms. To exploit automorphism efficiently, we focus on the method to construct fields in NFS such that the fields on both sides have nontrivial automorphisms with the logarithms of units being zero: 1) we construct two families of CM polynomials of arbitrary even degree with small coefficients, corresponding to the automorphisms being $xmapsto x$ or $xmapsto 1/x$ ; 2) we show how to combine these polynomials with the JLSV1 and Conjugation polynomial selection methods on both sides; and 3) we also generalize our method to the multiple number field sieve and the extended tower number field sieve.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 On the Niho Type LocallyAPN Power Functions and Their Boomerang Spectrum

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: Xi Xie;Sihem Mesnager;Nian Li;Debiao He;Xiangyong Zeng;
Pages: 4056  4064
Abstract: This article focuses on the socalled locallyAPN power functions introduced by Blondeau, Canteaut and Charpin, which generalize the wellknown notion of APN functions and possibly more suitable candidates against differential attacks. Specifically, given two coprime positive integers $m$ and $k$ such that $gcd (2^{m}+1,2^{k}+1)=1$ , we investigate the locallyAPNness property of the Niho type power function $F(x)=x^{s(2^{m}1)+1}$ over the finite field $mathbb {F}_{2^{2m}}$ for $s=(2^{k}+1)^{1}$ , where $(2^{k}+1)^{1}$ denotes the multiplicative inverse modulo $2^{m}+1$ . By employing finer studies of the number of solutions of certain equations over finite fields, we prove that $F(x)$ is locallyAPN and determine its differential spectrum. We emphasize that computer experiments show that this class of locallyAPN power functions covers all Niho type locallyAPN power functions for $2leq mleq 10$ . In addition, we also determine the boomerang spectrum of $F(x)$ by using its differential spectrum, which particularly generalizes a recent result by Yan, Zhang and Li.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 Likelihood Scores for Sparse Signal and ChangePoint Detection

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: Shouri Hu;Jingyan Huang;Hao Chen;Hock Peng Chan;
Pages: 4065  4080
Abstract: We consider here the identification of changepoints on largescale data streams. The objective is to find the most efficient way of combining information across data stream so that detection is possible under the smallest detectable change magnitude. The challenge comes from the sparsity of changepoints when only a small fraction of data streams undergo change at any point in time. The most successful approach to the sparsity issue so far has been the application of hard thresholding such that only local scores from data streams exhibiting significant changes are considered and added. However the identification of an optimal threshold is a difficult one. In particular it is unlikely that the same threshold is optimal for different levels of sparsity. We propose here a sparse likelihood score for identifying a sparse signal. The score is a likelihood ratio for testing between the null hypothesis of no change against an alternative hypothesis in which the changepoints or signals are barely detectable. By the NeymanPearson Lemma this score has maximum detection power at the given alternative. The outcome is that we have a scoring of data streams that is successful in detecting at the boundary of the detectable region of signals and changepoints. The likelihood score can be seen as a soft thresholding approach to sparse signal and changepoint detection in which local scores that indicate small changes are downweighted much more than local scores indicating large changes. We are able to show sharp optimality of the sparsity likelihood score in the sense of achieving successful detection at the minimum detectable order of change magnitude as well as the best constant with respect this order of change.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)

 The Inverse Problem of Positive Autoconvolution

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: Lorenzo Finesso;Peter Spreij;
Pages: 4081  4092
Abstract: We pose the problem of approximating optimally a given nonnegative signal with the scalar autoconvolution of a nonnegative signal. The Idivergence is chosen as the optimality criterion being well suited to incorporate nonnegativity constraints. After proving the existence of an optimal approximation, we derive an iterative descent algorithm of the alternating minimization type to find a minimizer. The algorithm is based on the lifting technique developed by Csiszár and Tusnádi and exploits the optimality properties of the related minimization problems in the larger space. We study the asymptotic behavior of the iterative algorithm and prove, among other results, that its limit points are KuhnTucker points of the original minimization problem. Numerical experiments confirm the asymptotic results and exhibit the fast convergence of the proposed algorithm.
PubDate: June 2023
Issue No: Vol. 69, No. 6 (2023)
