 Subjects -> ELECTRONICS (Total: 207 journals)
| A B C D E F G H I J K L M N O P Q R S T U V W X Y Z | | The end of the list has been reached or no journals were found for your choice. |
|
|
- IEEE Transactions on Information Theory publication information
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Authors:
Sufang Yang;Longguang Li;Haoyue Tang;Jintao Wang;
Pages: 3415 - 3430
Abstract: The diversity-multiplexing tradeoff (DMT) provides a fundamental performance metric for different multiple-input multiple-output (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 average-power 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 radio-frequency (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 Log-Concave
Random Variables-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 log-concave 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 one-sided exponential distribution minimizes Rényi entropy of order $alpha geq 2$ among all log-concave random variables with fixed variance.
PubDate:
June 2023
Issue No: Vol. 69, No. 6 (2023)
- Fundamental Limits of Cache-Aided MIMO Wireless Networks
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 Multi-Input-Multi-Output (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 cache-aided Single-Input-Multiple-Output (SIMO) interference networks. Then, we obtain the achievable NDT of the cache-aided MIMO interference networks using the decomposition property of splitting each multi-antenna transmitter into multiple single antenna transmitters. Furthermore, we derive an information-theoretic bound on the optimal NDT of the cache-aided 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 cache-aided Multi-Input-Single-Output (MISO) interference network outperforming our proposed scheme for the cache-aided MIMO interference network. The numerical results show the superiority of our proposed scheme over the state-of-the-art 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 receive-antennas become more effective in reducing the NDT than the transmit-antennas in the presence of caches at the receiver-side. In addition, we show that increasing the number of transmit-antennas has a higher gain in reducing the NDT than adding more transmitters in the cache-aided 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 Arimoto-Blahut 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Authors:
Cheuk Ting Li;
Pages: 3493 - 3510
Abstract: We resolve three long-standing 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)
- Multi-Bit Relaying Over a Tandem of Channels
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 1-bit setting studied in recent related works. Our main results show that the 1-hop and 2-hop 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 zero-rate 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 2-hop exponent is strictly below the 1-hop exponent.
PubDate:
June 2023
Issue No: Vol. 69, No. 6 (2023)
- Achievable Refined Asymptotics for Successive Refinement Using Gaussian
Codebooks-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 excess-distortion probability (JEP) and the separate excess-distortion probabilities (SEP) criteria. For both second-order 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 second-order rate-region 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 rate-distortion 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 Reed-Muller codes and the parity check codes. This generalizes a result of Pless and Sloane, where the binary self-orthogonal 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 run-time, as well as an extension of it in which the distortion constraint $d$ is also revealed at run-time. 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 list-decoding 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 size-expansion 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 Reed-Solomon Codes
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 Reed-Solomon 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 Reed-Solomon codes.
PubDate:
June 2023
Issue No: Vol. 69, No. 6 (2023)
- Learning Maximum Margin Channel Decoders
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 non-linear channel with additive white Gaussian noise and unknown channel transformation. The learner is provided with a fixed codebook and a dataset comprised of independent input-output 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 codebook-related regularization term and hinge-like 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 signal-to-noise ratio is proposed based on this bound. In addition, for the non-linear channel, a high probability uniform generalization error bound is provided for the hypothesis class. For each channel, a stochastic sub-gradient 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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
Low-Density Parity-Check Code Ensembles-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 low-density parity-check (GLDPC) codes. In particular, the fully absorbing sets are stable under the bit flipping algorithm. The finite-length (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 finite-length and asymptotic trapping and (elementary) absorbing set enumerators for non-binary irregular LDPC code ensembles.
PubDate:
June 2023
Issue No: Vol. 69, No. 6 (2023)
- The Covering Radius of the Third-Order Reed-Muller Code RM(3,7) is 20
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 third-order Reed-Muller 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 third-order nonlinearity among all 7-variable Boolean functions. It was known that there exist 7-variable Boolean functions with third-order nonlinearity 20. We prove the third-order nonlinearity cannot achieve 21. According to the classification of the quotient space of $mathrm {RM}(6,6)/mathrm {RM}(3,6)$ , we classify all 7-variable Boolean functions into 66 types. Firstly, we prove 62 types (among 66) cannot have third-order nonlinearity 21; Secondly, we prove that any function in the remaining 4 types can be transformed into a type (6, 10) function, if its third-order nonlinearity is 21; Finally, we transform type (6, 10) functions into a specific form, and prove the functions in that form cannot achieve the third-order 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 Variable-Size Messages
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 quality-of-service for live communication is to recover lost packets in real-time. Streaming codes are a class of erasure codes that are designed for such strict, low-latency 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 variable-size 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 rate-optimal streaming codes for communicating over a burst-only 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)
- Basis-Finding Algorithm for Decoding Fountain Codes for DNA-Based Data
Storage-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 DNA-based 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 basis-finding 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 (1-shot) capacity, improving on the best currently known results. In particular, we show that traditional cut-set bounds are not tight in general in the presence of a restricted adversary, and that the non-tightness 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 end-to-end 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 capacity-achieving 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 AE-based 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 Partial-Inverse Approach to Linearized Polynomials and Gabidulin Codes
With Applications to Network Coding-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Authors:
Jiun-Hung Yu;Hans-Andrea Loeliger;
Pages: 3759 - 3774
Abstract: This paper introduces the partial-inverse 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 partial-inverse 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 partial-inverse 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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=n-1$ , 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 Error-Correcting Codes”
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 Dimension-Independent CSI Acquisition for
Beamforming-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 RIS-assisted 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 dimension-independent 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 vM-EM algorithm is analyzed with the fixed-point perturbation method to obtain an asymptotic achievable bound. In addition, we also derive the Cramér-Rao 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 dimension-independent CSI acquisition for beamforming.
PubDate:
June 2023
Issue No: Vol. 69, No. 6 (2023)
- Mutually Unbiased Measurements, Hadamard Matrices, and Superdense Coding
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 rank-1 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 device-independent 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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, low-dimensional, single-parameter family of quantum channels with exotic quantum information-theoretic features. As the simplest example from this family, we focus on a qutrit-to-qutrit 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 closed-form 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 Degree-Corrected Tensor Block Models
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 degree-corrected 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 signal-to-noise regimes corresponding to different statistical-computational behaviors. In particular, we demonstrate that an intrinsic statistical-to-computational gap emerges only for tensors of order three or greater. Further, we develop an efficient polynomial-time 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 Kullback-Leibler 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 higher-order 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 real-valued weights impacts their approximation properties. We establish an upper-bound 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 nearest-neighbour uniform quantization of ReLU networks. This is achieved using a new lower-bound on the Lipschitz constant of the map that associates the parameters of ReLU networks to their realization, and an upper-bound 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 upper-bound. Many classical approximation families, defined with dictionaries or ReLU networks, are shown to be $infty $ -encodable. This unifies and generalizes several situations where this upper-bound is known.
PubDate:
June 2023
Issue No: Vol. 69, No. 6 (2023)
- On L
2-Consistency of Nearest Neighbor
Matching-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 low-complexity algorithms that can be used for efficiently solving such high-dimensional 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 (AMP-SI), has been recently introduced. In this work, we provide rigorous performance guarantees for AMP-SI 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 AMP-SI framework incorporating both separable and non-separable denoisers. The AMP-SI 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 AMP-SI 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 Sample-Path-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 goodness-of-fit 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,in-ty$ ) from the alternative hypothesis that $left lVert{ boldsymbol {alpha }}right rVert> gamma $ . An analogous goodness-of-fit 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 non-equivalent 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 long-standing problem.
PubDate:
June 2023
Issue No: Vol. 69, No. 6 (2023)
- New Results on the −1 Conjecture on Cross-Correlation of m-Sequences
Based on Complete Permutation Polynomials-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Authors:
Gaofei Wu;Keqin Feng;Nian Li;Tor Helleseth;
Pages: 4035 - 4044
Abstract: The cross-correlation 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 cross-correlation 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}}, p-1)$ . This was known as the −1 conjecture. Up to now, the −1 conjecture was confirmed for the following decimations: (1) Niho-type 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}}, p-1) $ ; and (3) the additional families of decimations tabulated in this paper. In this paper, we first discuss the connection between the −1 conjecture on cross-correlation 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 Non-Prime
Finite Fields-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 state-of-the-art 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 non-trivial automorphisms, one can use them to accelerate the factor-base 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 non-trivial 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 Locally-APN Power Functions and Their Boomerang Spectrum
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 so-called locally-APN power functions introduced by Blondeau, Canteaut and Charpin, which generalize the well-known 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 locally-APN-ness 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 locally-APN and determine its differential spectrum. We emphasize that computer experiments show that this class of locally-APN power functions covers all Niho type locally-APN 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 Change-Point Detection
-
Free pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 change-points on large-scale 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 change-points 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 change-points or signals are barely detectable. By the Neyman-Pearson 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 change-points. The likelihood score can be seen as a soft thresholding approach to sparse signal and change-point detection in which local scores that indicate small changes are down-weighted 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 pre-print version: Loading...
Rate this result:
What is this?
Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print 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 I-divergence 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 Kuhn-Tucker 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)
|
Hybrid journal (It can contain Open Access articles)
