Search

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correcting only two deletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct ${d}$ deletions in a codeword of length ${n}$ , successive-cancellation decoding is run separately for each of the $\binom {n}{d}$ possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is ${O}\bigl ({n}^{d+1}\log {n}\bigr)$. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in ${m} = \log _{2} {n}$ decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most $\binom {d+2}{2}$ scenarios at each node, and the overall decoding complexity is only ${O}\bigl ({d}^{3} {n} \log {n}\bigr)$ , which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions ${d}$ is small, i.e. ${d}={o}({n})$. We also conjecture the strong polarization for when ${d}={O}(1)$ and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions. [ABSTRACT FROM AUTHOR]

The study of constant-weight codes in $\ell _{1}$ -metric was motivated by the duplication-correcting problem for data storage in live DNA. It is interesting to determine the maximum size of a code given the length ${n}$ , weight ${w}$ , minimum distance ${d}$ and the alphabet size ${q}$. In this paper, based on graph decompositions, we determine the maximum size of ternary codes with constant weight w and distance $2{w}-2$ for all sufficiently large length ${n}$. Previously, this was known only for a very sparse family ${n}$ of density $4/{w}({w}-1)$. [ABSTRACT FROM AUTHOR]

The paper deals with linear information inequalities valid for entropy functions induced by discrete random variables. Specifically, the so-called conditional Ingleton inequalities are in the center of interest: these are valid under conditional independence assumptions on the inducing random variables. We discuss five inequalities of this particular type, four of which has appeared earlier in the literature. Besides the proof of the new fifth inequality, simpler proofs of (some of) former inequalities are presented. These five information inequalities are used to characterize all conditional independence structures induced by four discrete random variables. [ABSTRACT FROM AUTHOR]

The basic goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items, where $d$ is usually much smaller than $n$. The outcome of a test on a subset of items is positive if the subset has at least $u$ defective items, negative if it has up to $\ell $ defective items, where $0 \leq \ell < u$ , and arbitrary otherwise. This is called threshold group testing. The parameter $g = u - \ell - 1$ is called the gap. In this paper, we focus on the case $g > 0$ , i.e., threshold group testing with a gap. Note that the results presented here are also applicable to the case $g = 0$ ; however, the results are not as efficient as those in related work. Currently, a few reported studies have investigated test designs and decoding algorithms for identifying defective items. Most of the previous studies have not been feasible because there are numerous constraints on their problem settings or the decoding complexities of their proposed schemes are relatively large. Therefore, it is compulsory to reduce the number of tests as well as the decoding complexity, i.e., the time for identifying the defective items, for achieving practical schemes. The work presented here makes five contributions. The first is a more accurate theorem for a non-adaptive algorithm for threshold group testing proposed by Chen and Fu. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing and other tasks such as constructing cover-free families or learning hidden graphs. Specifically, we present a better exact upper bound on the number of tests for disjunct matrices compared with that in related work. The third and fourth contributions are a reduced exact upper bound on the number of tests and a reduced asymptotic bound on the decoding time for identifying defective items in a noisy setting on test outcomes. The fifth contribution is a simulation on the number of tests of the resulting improvements for previous work and the proposed theorems. [ABSTRACT FROM AUTHOR]

This paper focuses on constructions of MDS self-dual codes from (extended) generalized Reed-Solomon (GRS) codes. Let $q = r^{2}$ be an odd prime power. We show that, there exists a $q$ -ary self-dual (extended) GRS code for each even length in the range $[{2r,3r-3}]$ , and for each singly even length in the range $[3r-1,4r]$. This extends the only known consecutive range $[2,2r]$ to $[{2,3r-3}]$ for this case. Furthermore, our general constructions provide many MDS self-dual codes with new parameters which, to the best of our knowledge, were not reported before. [ABSTRACT FROM AUTHOR]

Many clustering problems can be solved using semidefinite programming. Theoretical results in this vein frequently consider data with a planted clustering and a notion of signal strength such that the semidefinite program exactly recovers the planted clustering when the signal strength is sufficiently large. In practice, semidefinite programs are notoriously slow, and so speedups are welcome. In this paper, we show how to sketch a popular semidefinite relaxation of a graph clustering problem known as minimum bisection, and our analysis supports a meta-claim that the clustering task is less computationally burdensome when there is more signal. [ABSTRACT FROM AUTHOR]

The $r$ -parallel set of a set $A \subseteq {\mathbb {R}} ^{d}$ is the set of all points whose distance from $A$ is less than $r$. In this paper, we show that the surface area of an $r$ -parallel set in ${\mathbb {R}}^{d}$ with volume at most $V$ is upper-bounded by $e^{\Theta (d)}V/r$ , whereas its Gaussian surface area is upper-bounded by $\max (e^{\Theta (d)}, e^{\Theta (d)}/r)$. We also derive a reverse form of the Brunn-Minkowski inequality for $r$ -parallel sets, and as an aside a reverse entropy power inequality for Gaussian-smoothed random variables. We apply our results to two problems in theoretical machine learning: (1) bounding the computational complexity of learning $r$ -parallel sets under a Gaussian distribution; and (2) bounding the sample complexity of estimating robust risk, which is a notion of risk in the adversarial machine learning literature that is analogous to the Bayes risk in hypothesis testing. [ABSTRACT FROM AUTHOR]

It is well known that the capacity region of an average transmit power constrained Gaussian Broadcast Channel (GBC) with independent noise realizations at the receivers is enlarged by the presence of causal noiseless feedback. When the noise variances at the receivers are identical, even passive feedback via independent memoryless Gaussian links can lead to a capacity region enlargement. The last fact remains true even when the feedback noise variance is very high, and available only from one of the receivers. While such capacity enlargements are feasible for several other feedback models in the Gaussian BC setting, it is also known that feedback does not change the capacity region for physically degraded broadcast channels. In this paper, we consider a two user GBC with independent noise realizations at the receivers, where the feedback links from the receivers are corrupted by independent additive Gaussian noise processes. We investigate the set of four noise variances, two forward and two feedback, for which no capacity enlargement is possible. A sharp characterization of this region is derived, i.e., any quadruple outside the presented region will lead to a capacity enlargement, whereas quadruples inside will leave the capacity region unchanged. Our results lead to the conclusion that when the forward noise variances are different, too noisy a feedback from one of the receivers alone is not always beneficial for enlarging the capacity region, be it from the stronger user or the weaker one, in sharp contrast to the case of equal forward noise variances. [ABSTRACT FROM AUTHOR]

In a prior paper (Ellingsen et al., 2020), two of us, along with P. Ellingsen, P. Felke, and A. Tkachenko, defined a new (output) multiplicative differential and the corresponding $c$ -differential uniformity, which has the potential of extending differential cryptanalysis. Here, we continue the work by looking at some APN functions through the mentioned concept and showing that their $c$ -differential uniformity increases significantly in some cases. [ABSTRACT FROM AUTHOR]

The hardcore model on a graph $G$ with parameter $\lambda > 0$ is a probability measure on the collection of all independent sets of $G$ , that assigns to each independent set $I$ a probability proportional to $\lambda ^{|I|}$. In this paper we consider the problem of estimating the parameter $\lambda $ given a single sample from the hardcore model on a graph $G$. To bypass the computational intractability of the maximum likelihood method, we use the maximum pseudo-likelihood (MPL) estimator, which for the hardcore model has a surprisingly simple closed form expression. We show that for any sequence of graphs $\{G_{N}\}_{N \geq 1}$ , where $G_{N}$ is a graph on $N$ vertices, the MPL estimate of $\lambda $ is $\sqrt {N}$ -consistent (that is, it converges to the true parameter at rate $1/\sqrt {N}$), whenever the graph sequence has uniformly bounded average degree. We then extend our methods to obtain estimates for the vector of activity parameters in general $H$ -coloring models, in which restrictions between adjacent colors are encoded by a constraint graph $H$. These constitute an important class of Markov random fields that includes all hard-constraint models, which arise in a broad array of fields including combinatorics, statistical physics, and communication networks. Given a single sample from an $H$ -coloring model, we derive sufficient conditions under which the MPL estimate is $\sqrt {N}$ -consistent. Moreover, we verify the sufficient conditions for $H$ -coloring models for which there is at least one ‘unconstrained’ color (that is, there exists at least one vertex in the constraint graph $H$ that is connected to all vertices), as long as the graph sequence has uniformly bounded average degree. This applies to many $H$ -coloring examples such as the Widom-Rowlinson and multi-state hard-core models. On the other hand, for the $q$ -coloring model, which falls outside this class, we show that the condition can fail and consistent estimation may be impossible even for graphs with bounded average degree. Nevertheless, we show that the MPL estimate is $\sqrt {N}$ -consistent in the $q$ -coloring model when $\{G_{N}\}_{N \geq 1}$ has bounded average double neighborhood. The presence of hard constraints, as opposed to soft constraints, leads to new challenges, and our proofs entail applications of the method of exchangeable pairs as well as combinatorial arguments that employ the probabilistic method. [ABSTRACT FROM AUTHOR]

This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. In contrast to most related works, we assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available. We further require the probability of the estimation error to decay either exponentially or sub-exponentially fast (corresponding respectively to the large and moderate deviations regimes in information theory parlance). Based on the training sequences as well as the test sequence consisting of a single change-point, we design a change-point estimator and further show that this estimator is optimal by establishing matching (strong) converses. This leads to a full characterization of the optimal confidence width (i.e., half the width of the confidence interval within which the true change-point is located at with high probability) as a function of the undetected error, under both the large and moderate deviations regimes. [ABSTRACT FROM AUTHOR]

A Goppa code over $\Bbb F_{q^{m}}$ is a well-known subclass of algebraic error-correcting code. If $m=1$ , then it is a generalized Reed-Solomon(GRS) code and its dual code is called a GRS code via a Goppa code. In this paper, we give a necessary and sufficient condition that the dual codes of GRS codes via (expurgated) Goppa codes are also GRS codes via Goppa codes. Under the above condition, we show that the hulls of GRS codes via Goppa codes are still GRS codes via Goppa codes. As an application, we characterize LCD GRS codes and self-dual GRS codes under the above condition. Some numerical examples are also presented to illustrate our main results. Moreover, we also apply our result to entanglement-assisted quantum error correcting codes (EAQECCs) and obtain two new families of MDS EAQECCs with arbitrary parameters. [ABSTRACT FROM AUTHOR]

The nondispersive per-sample channel model for the optical fiber channel is considered. Under certain smoothness assumptions, the problem of finding the minimum amount of noise energy that can render two different input points indistinguishable is formulated. This minimum noise energy is then taken as a measure of distance between the points in the input alphabet. Using the machinery of optimal control theory, necessary conditions that describe the minimum-energy noise trajectories are stated as a system of nonlinear differential equations. It is shown how to find the distance between two input points by solving this system of differential equations. The problem of designing signal constellations with the largest minimum distance subject to a peak power constraint is formulated as a clique-finding problem. As an example, a 16-point constellation is designed and compared with conventional quadrature amplitude modulation. A computationally efficient approximation for the proposed distance measure is provided. It is shown how to use this approximation to design large constellations with large minimum distances. Based on the control-theoretic viewpoint of this paper, a new decoding scheme for such nonlinear channels is proposed. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the error floor of quasi-cyclic (QC) low-density parity-check (LDPC) codes decoded by the sum-product algorithm (SPA) with row layered message-passing scheduling. For this, we develop a linear state-space model of trapping sets (TSs) which incorporates the layered nature of scheduling. We demonstrate that the contribution of each TS to the error floor is not only a function of the topology of the TS, but also depends on the row layers in which different check nodes of the TS are located. This information, referred to as TS layer profile (TSLP), plays an important role in the harmfulness of a TS. As a result, the harmfulness of a TS in particular, and the error floor of the code in general, can significantly change by changing the order in which the information of different layers, corresponding to different row blocks of the parity-check matrix, is updated. We also study the problem of finding a layer ordering that minimizes the error floor, and obtain row layered decoders with error floor significantly lower than that of their flooding counterparts. As part of our analysis, we make connections between the parameters of the state-space model for a row layered schedule and those of the flooding schedule. Simulation results are presented to show the accuracy of analytical error floor estimates. [ABSTRACT FROM AUTHOR]

In image detection, one problem is to test whether the set, though mainly consisting of uniformly scattered points, also contains a small fraction of points sampled from some (a priori unknown) curve, for example, a curve with Cα-norm bounded by β. One approach is to analyze the data by counting membership in multiscale multianisotropic strips, which involves an algorithm that delves into the length of the path connecting many consecutive “significant” nodes. In this paper, we develop the mathematical formalism of this algorithm and analyze the statistical property of the length of the longest significant run. The rate of convergence is derived. Using percolation theory and random graph theory, we present a novel probabilistic model named, pseudo-tree model. Based on the asymptotic results for the pseudo-tree model, we further study the length of the longest significant run in an “inflating” Bernoulli net. We find that the probability parameter p of significant node plays an important role: there is a threshold pc, such that in the cases of p < pc and p > pc, very different asymptotic behaviors of the length of the significant runs are observed. We apply our results to the detection of an underlying curvilinear feature and prove that the test based on our proposed longest run theory is asymptotically powerful. [ABSTRACT FROM AUTHOR]

Modern machine learning algorithms perform poorly on adversarially manipulated data. Adversarial risk quantifies the error of classifiers in adversarial settings; adversarial classifiers minimize adversarial risk. In this paper, we analyze adversarial risk and adversarial classifiers from an optimal transport perspective. We show that the optimal adversarial risk for binary classification with 0–1 loss is determined by an optimal transport cost between the probability distributions of the two classes. We develop optimal transport plans (probabilistic couplings) for univariate distributions such as the normal, the uniform, and the triangular distribution. We also derive optimal adversarial classifiers in these settings. Our analysis leads to algorithm-independent fundamental limits on adversarial risk, which we calculate for several real-world datasets. We extend our results to general loss functions under convexity and smoothness assumptions. [ABSTRACT FROM AUTHOR]

This paper studies the performance and key structural properties of the optimum location-based relay selection policy for wireless networks consisting of homogeneous Poisson distributed relays. The distribution of the channel quality indicator at the optimum relay location is obtained. A threshold-based distributed selective feedback policy is proposed for the discovery of the optimum relay location with finite average feedback load. It is established that the total number of relays feeding back obeys a Poisson distribution and an analytical expression for the average feedback load is derived. The analytical expressions for the average rate and outage probability with and without selective feedback are obtained for general path-loss models. It is shown that the optimum location-based relay selection policy outperforms other common relay selection strategies notably. It is also shown that utilizing location information from five relays on average is enough to achieve almost the same performance with the infinite feedback load case. As generalizations, isotropic Poisson point processes and heterogeneous source-to-relay and relay-to-destination links are also studied. [ABSTRACT FROM AUTHOR]

This paper considers a target localization problem where at any given time an agent can choose a region to query for the presence of the target in that region. The measurement noise is assumed to be increasing with the size of the query region the agent chooses. Motivated by practical applications such as initial beam alignment in array processing, heavy hitter detection in networking, and visual search in robotics, we consider practically important complexity constraints/metrics: time complexity, computational and memory complexity, and the complexity of possible query sets in terms of geometry and cardinality. Two novel search strategy, dyaPM and hiePM, are proposed. Pertinent to the practicality of our solutions, dyaPM and hiePM are of a connected query geometry (i.e. query set is always a connected set) implemented with low computational and memory complexity. Additionally, hiePM has a hierarchical structure and, hence, a further reduction in the cardinality of possible query sets, making hiePM practically suitable for applications such as beamforming in array processing where memory limitations favors a small and predefined query sets. Through a unified analysis with Extrinsic Jensen Shannon (EJS) Divergence, dyaPM is shown to be asymptotically optimal in search time complexity (asymptotic in both resolution (rate) and error (reliability)). On the other hand, hiePM is shown to be near-optimal in rate. In addition, both hiePM and dyaPM are shown to outperform prior work in the non-asymptotic regime. [ABSTRACT FROM AUTHOR]

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes. [ABSTRACT FROM AUTHOR]

Risk estimation is at the core of many learning systems. The importance of this problem has motivated researchers to propose different schemes, such as cross validation, generalized cross validation, and Bootstrap. The theoretical properties of such estimators have been extensively studied in the low-dimensional settings, where the number of predictors p is much smaller than the number of observations n. However, a unifying methodology accompanied with a rigorous theory is lacking in high-dimensional settings. This paper studies the problem of risk estimation under the moderately high-dimensional asymptotic setting n,p → ∞ and n/p → δ > 1 (δ is a fixed number), and proves the consistency of three risk estimators that have been successful in numerical studies, i.e., leave-one-out cross validation (LOOCV), approximate leave-one-out (ALO), and approximate message passing (AMP)-based techniques. A corner stone of our analysis is a bound that we obtain on the discrepancy of the ‘residuals’ obtained from AMP and LOOCV. This connection not only enables us to obtain a more refined information on the estimates of AMP, ALO, and LOOCV, but also offers an upper bound on the convergence rate of each estimator. [ABSTRACT FROM AUTHOR]

Consider a (multiple-access) wireless communication system where users are connected to a unique base station over a shared-spectrum radio links. Each user has a fixed number k of bits to send to the base station, and his signal gets attenuated by a random channel gain (quasi-static fading). In this paper we consider the many-user asymptotics of Chen-Chen-Guo’2017, where the number of users grows linearly with the blocklength. Differently, though, we adopt a per-user probability of error (PUPE) criterion (as opposed to classical joint-error probability criterion). Under PUPE the finite energy-per-bit communication is possible, and we are able to derive bounds on the tradeoff between energy and spectral efficiencies. We reconfirm the curious behaviour (previously observed for non-fading MAC) of the possibility of almost perfect multi-user interference (MUI) cancellation for user densities below a critical threshold. Further, we demonstrate the suboptimality of standard solutions such as orthogonalization (i.e. TDMA/FDMA) and treating interference as noise (i.e. pseudo-random CDMA without multi-user detection). Notably, the problem treated here can be seen as a variant of support recovery in compressed sensing for the unusual definition of sparsity with one non-zero entry per each contiguous section of 2k coordinates. This identifies our problem with that of the sparse regression codes (SPARCs) and hence our results can be equivalently understood in the context of SPARCs with sections of length 2100. Finally, we discuss the relation of the almost perfect MUI cancellation property and the replica-method predictions. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length-n sequences for k = 2 + 2 log (n). This algorithm is then improved to support any value of k of the form k = a log (n), for 1 < a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes. [ABSTRACT FROM AUTHOR]

We consider the use of the well-known dual capacity bounding technique for deriving upper bounds on the capacity of indecomposable finite-state channels (FSCs) with finite input and output alphabets. In this technique, capacity upper bounds are obtained by choosing suitable test distributions on the sequence of channel outputs. We propose test distributions that arise from certain graphical structures called Q-graphs. As we show in this paper, the advantage of this choice of test distribution is that, for the important sub-classes of unifilar and input-driven FSCs, the resulting upper bounds can be formulated as a dynamic programming (DP) problem, which makes the bounds tractable. We illustrate this for several examples of FSCs, where we are able to solve the associated DP problems explicitly to obtain capacity upper bounds that either match or beat the best previously reported bounds. For instance, for the classical trapdoor channel, we improve the best known upper bound of 0.661 (due to Lutz (2014)) to 0.584, shrinking the gap to the best known lower bound of 0.572, all bounds being in units of bits per channel use. [ABSTRACT FROM AUTHOR]

A linear error correcting code is a subspace of a finite-dimensional space over a finite field with a fixed coordinate system. Such a code is said to be locally recoverable with locality r if, for every coordinate, its value at a codeword can be deduced from the value of (certain) r other coordinates of the codeword. These codes have found many recent applications, e.g., to distributed cloud storage. We will discuss the problem of constructing good locally recoverable codes and present some constructions using algebraic surfaces that improve previous constructions and sometimes provide codes that are optimal in a precise sense. The main conceptual contribution of this paper is to consider surfaces fibered over a curve in such a way that each recovery set is constructed from points in a single fiber. This allows us to use the geometry of the fiber to guarantee the local recoverability and use the global geometry of the surface to get a hold on the standard parameters of our codes. We look in detail at situations where the fibers are rational or elliptic curves and provide many examples applying our methods. [ABSTRACT FROM AUTHOR]

Normalized maximum likelihood (NML) distribution of probabilistic model gives the optimal code length function in the sense of minimax regret. Despite its optimal property, the calculation of NML distribution is not easy, and existing efficient methods have been focusing on its asymptotic behavior, or on specific models. This paper gives an efficient way to calculate NML by integral on parameter domain, not on data domain, showing that NML distribution is a Bayesian predictive distribution with a complex prior, based on our novel Fourier expansion approach. Our results provide an integrated way to calculate NML for exponential family and also include a non-asymptotic version of previous work on asymptotic behavior for general cases. The applications of our methodology are not limited to but also include normal distribution, Gamma distribution, Weibull distribution, and von Mises distribution. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of secret key generation with one-way communication through both a rate-limited public channel and a rate-limited secure channels where the public channel is from Alice to Bob and Eve and the secure channel is from Alice to Bob. In this model, we do not pose any constraints on the sources, i.e. Bob is not degraded to or less noisy than Eve. We obtain the optimal secret key rate in this problem, both for the discrete memoryless sources and vector Gaussian sources. The vector Gaussian characterization is derived by suitably applying the enhancement argument, and proving a new extremal inequality. The extremal inequality can be seen as coupling of two extremal inequalities, which are related to the degraded compound MIMO Gaussian broadcast channel, and the vector generalization of Costa’s entropy power inequality, accordingly. [ABSTRACT FROM AUTHOR]

An error model with asymmetric single error with magnitude four is considered. In this paper, the constructions of codes correcting single error of magnitude four over $\mathbb {Z}_{2^{{a}}3^{{b}}{r}}$ are studied which is equivalent to construct $B_{1}[{4}](2^{{a}}3^{{b}}{r})$ sets. Firstly, we reduce the construction of a maximal size ${B}_{1}[{4}](2^{{a}}3^{{b}}{r})$ set for ${a}\geq 4$ and $ \gcd ({r},6)=1$ to the construction of a maximal size ${B}_{1}[{4}](2^{{a}-3}3^{{b}}{r})$ set. Furthermore, we will show that maximal size ${B}_{1}[{4}](8\cdot 3^{{b}}{r})$ sets can be reduced to maximal size ${B}_{1}[{4}](3^{{b}}{r})$ sets and also give lower bounds of maximal size ${B}_{1}[{4}](12{r})$ and ${B}_{1}[{4}](2\cdot 3^{{b}}{r})$ sets. Finally, we give a necessary and sufficient condition on the existence of perfect ${B}_{1}[{4}]({p})$ set for prime $p$. [ABSTRACT FROM AUTHOR]

Information-theoretic formulations of the private information retrieval (PIR) problem have been investigated under a variety of scenarios. Symmetric private information retrieval (SPIR) is a variant where a user is able to privately retrieve one out of K messages from N non-colluding replicated databases without learning anything about the remaining K−1 messages. However, the goal of perfect privacy can be too taxing for certain applications. In this paper, we investigate if the information-theoretic capacity of SPIR (equivalently, the inverse of the minimum download cost) can be increased by relaxing both user and DB privacy definitions. Such relaxation is relevant in applications where privacy can be traded for communication efficiency. We introduce and investigate the Asymmetric Leaky PIR (AL-PIR) model with different privacy leakage budgets in each direction. For user privacy leakage, we bound the probability ratios between all possible realizations of DB queries by a function of a non-negative constant ε. For DB privacy, we bound the mutual information between the undesired messages, the queries, and the answers, by a function of a non-negative constant &#948. We propose a general AL-PIR scheme that achieves an upper bound on the optimal download cost for arbitrary ε and δ. We show that the optimal download cost of AL-PIR is upper-bounded as D*(ε,δ) ≤ 1+ 1/N−1 − δeε/NK−1−1. Second, we obtain an information-theoretic lower bound on the download cost as D*(ε,δ) ≥ 1 + 1/Neε−1 − δ/(Neε)K−1 −1. The gap analysis between the two bounds shows that our AL-PIR scheme is optimal when ε = 0, i.e., under perfect user privacy and it is optimal within a maximum multiplicative gap of N−e−ε/N−1 for any ε > 0 and δ > 0. [ABSTRACT FROM AUTHOR]

Bazzi and Mitter showed that binary dihedral group codes are asymptotically good. In this paper we prove that the dihedral group codes over any finite field with strong duality property are asymptotically good. If the characteristic of the field is even, self-dual dihedral group codes are asymptotically good. If the characteristic of the field is odd, maximal self-orthogonal dihedral group codes and LCD dihedral group codes are asymptotically good. [ABSTRACT FROM AUTHOR]

This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input discrete memoryless channel (BDMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BDMC. We prove a square-root law for the covert identification problem. This states that an ID message of size $\exp (\exp (\Theta (\sqrt {\text {n}})))$ can be transmitted over n channel uses. We then characterize the exact pre-constant in the $\Theta (\cdot)$ notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints. [ABSTRACT FROM AUTHOR]

Compressed sensing is an emerging theory of signal processing and it has wide applications in many frontier fields. The construction of the measurement matrices is still a central problem in compressed sensing. In this paper, two types of deterministic constructions of binary measurement matrices are presented via unitary geometry. Then, the lower bounds of the spark of unitary geometry measurement matrices are theoretically analyzed, and an asymptotic comparison between unitary geometry measurement matrices and projective geometry measurement matrices is given via the worst-case recovery capability. After that, a clipping-embedding operation is proposed for binary matrices to generate measurement matrices with more sizes, which can strongly extend the applicability of the deterministic binary matrices in practice. Finally, simulation results demonstrate that the performance of our measurement matrices is comparable to, sometimes even better than, that of the corresponding Gaussian random matrices under OMP and BP. [ABSTRACT FROM AUTHOR]

This paper studies an information-theoretic one-shot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X;Y) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X;Y) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X,Y). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn,Yn) are observed sequentially and the key is output bit by bit, or in situations where the random source is not an i.i.d. or ergodic process. [ABSTRACT FROM AUTHOR]

This paper investigates reducing sub-packetization of capacity-achieving schemes for uncoded Storage Constrained Private Information Retrieval (SC-PIR) systems. In the SC-PIR system, a user aims to download one out of K files from N servers while revealing nothing about the identity of the requested file to any individual server, in which the K files are stored at the N servers in an uncoded form and each server can store up to μK equivalent files, where μ is the normalized storage capacity of each server. We first prove that there exists a capacity-achieving SC-PIR scheme for a given storage design if and only if all the packets are stored exactly at M ≜ μN servers for μ such that M = μN ∈ {2,3, . . . ,N}. Then, the optimal sub-packetization for capacity-achieving linear SC-PIR schemes is characterized as the solution to an optimization problem, which is typically hard to solve since it involves non-continuous indicator functions. Moreover, a new notion of array called Storage Design Array (SDA) is introduced for the SC-PIR system. With any given SDA, an associated capacity-achieving SC-PIR scheme is constructed. Next, the SC-PIR schemes that have equal-size packets are investigated. Furthermore, the optimal equal-size sub-packetization among all capacity-achieving linear SC-PIR schemes characterized by Woolsey et al. is proved to be N(M−1)/gcd (N,M), which is achieved by a construction of SDA. Finally, by allowing unequal size of packets, a greedy SDA construction is proposed, where the sub-packetization of the associated SC-PIR scheme is upper bounded by N(M−1)/gcd (N,M). Among all capacity-achieving linear SC-PIR schemes, the sub-packetization is optimal when min{M,N−M}|N or M = N, and within a multiplicative gap min{M,N−M}/gcd (N,M) of the optimal one in general. In particular, for the special case N = d ⋅ M ± 1 where the positive integer d ≥ 2, we propose another SDA construction to obtain lower sub-packetization. [ABSTRACT FROM AUTHOR]

The correspondence cited in the above article derived ergodic capacity of the coherent multiple-input multiple-output (MIMO) channel in independent and identically distributed (IID) Rayleigh fading. While the theoretical results are correct, several plots in the paper are incorrect. In this correspondence, we correct the plots. More importantly, the corrected plots present an interesting and compelling contrast between performances of the coherent MIMO systems with and without channel state information at the transmitter; whereas this view is somewhat limited in the above article because of flaws in the capacity curves. [ABSTRACT FROM AUTHOR]

In this paper, we consider a multi-armed bandit in which each arm is a Markov process evolving on a finite state space. The state space is common across the arms, and the arms are independent of each other. The transition probability matrix of one of the arms (the odd arm) is different from the common transition probability matrix of all the other arms. A decision maker, who knows these transition probability matrices, wishes to identify the odd arm as quickly as possible, while keeping the probability of decision error small. To do so, the decision maker collects observations from the arms by pulling the arms in a sequential manner, one at each discrete time instant. However, the decision maker has a trembling hand, and the arm that is actually pulled at any given time differs, with a small probability, from the one he intended to pull. The observation at any given time is the arm that is actually pulled and its current state. The Markov processes of the unobserved arms continue to evolve. This makes the arms restless. For the above setting, we derive the first known asymptotic lower bound on the expected time required to identify the odd arm, where the asymptotics is of vanishing error probability. The continued evolution of each arm adds a new dimension to the problem, leading to a family of Markov decision problems (MDPs) on a countable state space. We then stitch together certain parameterised solutions to these MDPs and obtain a sequence of strategies whose expected times to identify the odd arm come arbitrarily close to the lower bound in the regime of vanishing error probability. Prior works dealt with independent and identically distributed (across time) arms and rested Markov arms, whereas our work deals with restless Markov arms. [ABSTRACT FROM AUTHOR]

The parameters of a q-ary MDS Euclidean self-dual codes are completely determined by its length and the construction of MDS Euclidean self-dual codes with new length has been widely investigated in recent years. In this paper, we give a further study on the construction of MDS Euclidean self-dual codes via generalized Reed-Solomon (GRS) codes and their extended codes. The main idea of our construction is to choose suitable evaluation points such that the corresponding (extended) GRS codes are Euclidean self-dual. Firstly, we consider the evaluation set consists of two disjoint subsets, one of which is based on the trace function, the other one is a union of a subspace and its cosets. Then four new families of MDS Euclidean self-dual codes are constructed. Secondly, we give a simple but useful lemma to ensure that the symmetric difference of two intersecting subsets of finite fields can be taken as the desired evaluation set. Based on this lemma, we generalize our first construction and provide two new families of MDS Euclidean self-dual codes. Finally, by using two multiplicative subgroups and their cosets which have nonempty intersection, we present three generic constructions of MDS Euclidean self-dual codes with flexible parameters. Several new families of MDS Euclidean self-dual codes are explicitly constructed. [ABSTRACT FROM AUTHOR]

Quasi-complementary sequence sets (QCSSs) play an important role in multi-carrier code-division multiple-access (MC-CDMA) systems. They can support more users than perfect complementary sequence sets in MC-CDMA systems. It is desirable to design QCSSs with good parameters that are a trade-off of large set size, small periodic maximum magnitude correlation and small alphabet size. The main results are to construct new infinite families of QCSSs that all have small alphabet size and asymptotically optimal periodic maximum magnitude correlation. In this paper, we propose three new constructions of QCSSs using additive characters over finite fields. Notably, these QCSSs have new parameters and small alphabet sizes. Using the properties of characters and character sums, we determine their maximum periodic correlation magnitudes and prove that these QCSSs are asymptotically optimal with respect to the lower bound. [ABSTRACT FROM AUTHOR]

In this paper, we provide two complementary results for cyclic codes of composite length. First, we give a general construction of cyclic codes of length nr from cyclic codes of length n and a lower bound on the minimum distance. Numerical data show that many cyclic codes of composite length with the best parameters can be obtained in this way. Second, in the other direction, we show that for cyclic codes of length n with a primitive n-th root of unity as a non-zero, the minimum distance is roughly bounded by the square-free part of n. This means that we shall not expect good cyclic codes of length n in general if, for example, the length n is divisible by a high power of a prime. [ABSTRACT FROM AUTHOR]

A coding scheme for transmission of a bit maps a given bit to a sequence of channel inputs (called the codeword associated with the transmitted bit). In this paper, we study the problem of designing the best code for a discrete Poisson channel with memory (under peak-power and total-power constraints). The outputs of a discrete Poisson channel with memory are Poisson distributed random variables with a mean comprising of a fixed additive noise and a linear combination of past input symbols. Assuming a maximum-likelihood (ML) decoder, we search for a codebook that has the smallest possible error probability. This problem is challenging because error probability of a code does not have a closed-form analytical expression. For the case of having only a total-power constraint, the optimal code structure is obtained, provided that the blocklength is greater than the memory length of the channel. For the case of having only a peak-power constraint, the optimal code is derived for arbitrary memory and blocklength in the high-power regime. For the case of having both the peak-power and total-power constraints, the optimal code is derived for memoryless Poisson channels when both the total-power and the peak-power bounds are large. [ABSTRACT FROM AUTHOR]

Line spectral estimation is a classical signal processing problem that aims to estimate the line spectra from their signal which is contaminated by deterministic or random noise. Despite a large body of research on this subject, the theoretical understanding of this problem is still elusive. In this paper, we introduce and quantitatively characterize the two resolution limits for the line spectral estimation problem under deterministic noise: one is the minimum separation distance between the line spectra that is required for exact detection of their number, and the other is the minimum separation distance between the line spectra that is required for a stable recovery of their supports. The quantitative results imply a phase transition phenomenon in each of the two recovery problems, and also the subtle difference between the two. We further propose a sweeping singular-value-thresholding algorithm for the number detection problem and conduct numerical experiments. The numerical results confirm the phase transition phenomenon in the number detection problem. [ABSTRACT FROM AUTHOR]

In this paper we consider high-dimensional multiclass classification by sparse multinomial logistic regression. We propose first a feature selection procedure based on penalized maximum likelihood with a complexity penalty on the model size and derive the nonasymptotic bounds for misclassification excess risk of the resulting classifier. We establish also their tightness by deriving the corresponding minimax lower bounds. In particular, we show that there is a phase transition between small and large number of classes. The bounds can be reduced under the additional low noise condition. To find a penalized maximum likelihood solution with a complexity penalty requires, however, a combinatorial search over all possible models. To design a feature selection procedure computationally feasible for high-dimensional data, we propose multinomial logistic group Lasso and Slope classifiers and show that they also achieve the minimax order. [ABSTRACT FROM AUTHOR]

This paper studies a large random matrix system (LRMS) model involving an arbitrary signal distribution and forward error control (FEC) coding. We establish an area property based on the approximate message passing (AMP) algorithm. Under the assumption that the state evolution for AMP is correct for the coded system, the achievable rate of AMP is analyzed. We prove that AMP achieves the constrained capacity of the LRMS with an arbitrary signal distribution provided that a matching condition is satisfied. As a byproduct, we provide an alternative derivation for the constraint capacity of an LRMS using a proved property of AMP. We discuss realization techniques for the matching principle of binary signaling using irregular low-density parity-check (LDPC) codes and provide related numerical results. We show that the optimized codes demonstrate significantly better performance over un-matched ones under AMP. For quadrature phase shift keying (QPSK) modulation, bit error rate (BER) performance within 1 dB from the constrained capacity limit is observed. [ABSTRACT FROM AUTHOR]

Sparse superposition codes, also referred to as sparse regression codes (SPARCs), are a class of codes for efficient communication over the AWGN channel at rates approaching the channel capacity. In a standard SPARC, codewords are sparse linear combinations of columns of an i.i.d. Gaussian design matrix, while in a spatially coupled SPARC the design matrix has a block-wise structure, where the variance of the Gaussian entries can be varied across blocks. A well-designed spatial coupling structure can significantly enhance the error performance of iterative decoding algorithms such as Approximate Message Passing (AMP). In this paper, we obtain a non-asymptotic bound on the probability of error of spatially coupled SPARCs with AMP decoding. Applying this bound to a simple band-diagonal design matrix, we prove that spatially coupled SPARCs with AMP decoding achieve the capacity of the AWGN channel. The bound also highlights how the decay of error probability depends on each design parameter of the spatially coupled SPARC. An attractive feature of AMP decoding is that its asymptotic mean squared error (MSE) can be predicted via a deterministic recursion called state evolution. Our result provides the first proof that the MSE concentrates on the state evolution prediction for spatially coupled designs. Combined with the state evolution prediction, this result implies that spatially coupled SPARCs with the proposed band-diagonal design are capacity-achieving. Using the proof technique used to establish the main result, we also obtain a concentration inequality for the MSE of AMP applied to compressed sensing with spatially coupled design matrices. Finally, we provide numerical simulation results that demonstrate the finite length error performance of spatially coupled SPARCs. The performance is compared with coded modulation schemes that use LDPC codes from the DVB-S2 standard. [ABSTRACT FROM AUTHOR]

A new method to construct q-ary complementary sequence sets (CSSs) and complete complementary codes (CCCs) of size N is proposed by using desired para-unitary (PU) matrices. The concept of seed PU matrices is introduced and a systematic approach on how to compute the explicit forms of the functions in constructed CSSs and CCCs from the seed PU matrices is given. A general form of these functions only depends on a basis of the functions from ZN to Zq and representatives in the equivalent class of Butson-type Hadamard (BH) matrices. Especially, the realization of Golay pairs from our general form exactly coincides with the standard Golay pairs. The realization of ternary complementary sequences of size 3 is first reported here. For the realization of the quaternary complementary sequences of size 4, almost all the sequences derived here are never reported before. Generalized seed PU matrices and the recursive constructions of the desired PU matrices are also studied, and a large number of new constructions of CSSs and CCCs are given accordingly. From the perspective of this paper, all the known results of CSSs and CCCs with explicit GBF form in the literature (except non-standard Golay pairs) are constructed from the WHT matrices. This suggests that the proposed method with other BH matrices will yield a large number of new CSSs and CCCs with the significantly increasing number of the sequences of low peak-to-mean envelope power ratio. [ABSTRACT FROM AUTHOR]

This paper revisits the ordered statistics decoding (OSD). It provides a comprehensive analysis of the OSD algorithm by characterizing the statistical properties, evolution and the distribution of the Hamming distance and weighted Hamming distance from codeword estimates to the received sequence in the reprocessing stages of the OSD algorithm. We prove that the Hamming distance and weighted Hamming distance distributions can be characterized as mixture models capturing the decoding error probability and code weight enumerator. Simulation and numerical results show that our proposed statistical approaches can accurately describe the distance distributions. Based on these distributions and with the aim to reduce the decoding complexity, several techniques, including stopping rules and discarding rules, are proposed, and their decoding error performance and complexity are accordingly analyzed. Simulation results for decoding various eBCH codes demonstrate that the proposed techniques can significantly reduce the decoding complexity with a negligible loss in the decoding error performance. [ABSTRACT FROM AUTHOR]

This paper proposes Bayes-optimal convolutional approximate message-passing (CAMP) for signal recovery in compressed sensing. CAMP uses the same low-complexity matched filter (MF) for interference suppression as approximate message-passing (AMP). To improve the convergence property of AMP for ill-conditioned sensing matrices, the so-called Onsager correction term in AMP is replaced by a convolution of all preceding messages. The tap coefficients in the convolution are determined so as to realize asymptotic Gaussianity of estimation errors via state evolution (SE) under the assumption of orthogonally invariant sensing matrices. An SE equation is derived to optimize the sequence of denoisers in CAMP. The optimized CAMP is proved to be Bayes-optimal for all orthogonally invariant sensing matrices if the SE equation converges to a fixed-point and if the fixed-point is unique. For sensing matrices with low-to-moderate condition numbers, CAMP can achieve the same performance as high-complexity orthogonal/vector AMP that requires the linear minimum mean-square error (LMMSE) filter instead of the MF. [ABSTRACT FROM AUTHOR]

In this paper we study stopping sets of AG codes over a family of curves, denoted by Xƒ,g, that includes several important curves with applications in coding theory. We present results concerning stopping sets of one-point and m-point codes over Xƒ,g , generalizing some results for Hermitian codes presented by Anderson and Matthews. [ABSTRACT FROM AUTHOR]

Multi-channel sparse blind deconvolution, or convolutional sparse coding, refers to the problem of learning an unknown filter by observing its circulant convolutions with multiple input signals that are sparse. This problem finds numerous applications in signal processing, computer vision, and inverse problems. However, it is challenging to learn the filter efficiently due to the bilinear structure of the observations with respect to the unknown filter and inputs, as well as the sparsity constraint. In this paper, we propose a novel approach based on nonconvex optimization over the sphere manifold by minimizing a smooth surrogate of the sparsity-promoting loss function. It is demonstrated that manifold gradient descent with random initializations will probably recover the filter, up to scaling and shift ambiguity, as soon as the number of observations is sufficiently large under an appropriate random data model. Numerical experiments are provided to illustrate the performance of the proposed method with comparisons to existing ones. [ABSTRACT FROM AUTHOR]

Communication for omniscience (CO) refers to the problem where the users in a finite set V observe a discrete multiple random source and want to exchange data over broadcast channels to reach omniscience, the state where everyone recovers the entire source. This paper studies how to improve the computational complexity for the problem of minimizing the sum-rate for attaining omniscience in V. While the existing algorithms rely on the submodular function minimization (SFM) techniques and complete in O(|V|2⋅SFM (|V|) time, we prove the strict strong map property of the nesting SFM problem. We propose a parametric (PAR) algorithm that utilizes the parametric SFM techniques and reduces the complexity to O(|V| ⋅SFM (|V|). We propose efficient solutions to the successive omniscience (SO): attaining omniscience successively in user subsets. We first focus on how to determine a complimentary subset X* ⊄ V in the existing two-stage SO such that if the local omniscience in X* is reached first, the global omniscience whereafter can still be attained with the minimum sum-rate. It is shown that such a subset can be extracted at one of the iterations of the PAR algorithm. We then propose a novel multi-stage SO strategy: a nesting sequence of complimentary user subsets X*(1) ⊄ . . . ⊆ X*(K) = V, the omniscience in which is attained progressively by the monotonic rate vectors rV(1) ≤ . . . rV(K). We propose algorithms to obtain this K-stage SO from the returned results by the PAR algorithm. The run time of these algorithms is the same as the PAR algorithm. [ABSTRACT FROM AUTHOR]

The quantum capacity of a noisy quantum channel determines the maximal rate at which we can code reliably over asymptotically many uses of the channel, and it characterizes the channel’s ultimate ability to transmit quantum information coherently. In this paper, we derive single-letter upper bounds on the quantum and private capacities of quantum channels. The quantum capacity of a quantum channel is always no larger than the quantum capacity of its extended channels, since the extensions of the channel can be considered as assistance from the environment. By optimizing the parametrized extended channels with specific structures such as the flag structure, we obtain new upper bounds on the quantum capacity of the original quantum channel. Furthermore, we extend our approach to estimating the fundamental limits of private communication and one-way entanglement distillation. As notable applications, we establish improved upper bounds to the quantum and private capacities for fundamental quantum channels of interest in quantum information, some of which are also the sources of noise in superconducting quantum computing. In particular, our upper bounds on the quantum capacities of the depolarizing channel and the generalized amplitude damping channel are strictly better than previously best-known bounds for certain regimes. [ABSTRACT FROM AUTHOR]