Search

In pliable index coding, we consider a server with m messages and n clients, where each client has as side information a subset of the messages. We seek to minimize the number of broadcast transmissions, so that each client can recover any one unknown message she does not already have. Previous work has shown that the pliable index coding problem is NP-hard and requires at most \mathcal O(\log ^2(n)) broadcast transmissions, which indicates exponential savings over the conventional index coding that requires in the worst case \mathcal O(n) transmissions. In this paper, building on a decoding criterion that we propose, we first design a deterministic polynomial-time algorithm that can realize the exponential benefits, by achieving, in the worst case, a performance upper bounded by \mathcal O(\log ^2(n)) broadcast transmissions. We extend our algorithm to the t -requests case, where each client requires t unknown messages that she does not have, and show that our algorithm requires at most \mathcal O(t\log (n)+\log ^2(n)) broadcast transmissions. We construct lower bound instances that require at least \Omega (\log (n)) transmissions for linear pliable index coding and at least $\Omega (t+\log (n))$ transmissions for the t$ -requests case, indicating that both our upper and lower bounds are polynomials of \log (n)$ and differ within a factor of . We provide a probabilistic analysis over random instances and show that the required number of transmissions is almost surely $\Theta (\log (n))$ , as compared with the $\Theta (n/\log (n))$ for index coding. In addition, we show that these upper and lower bounds also hold for vector pliable index coding in the worst case instances and the random graph instances, implying that vector coding does not provide benefits in terms of these bounds. Our numerical experiments show that our algorithm outperforms existing algorithms for pliable index coding by up to 50% less transmissions. [ABSTRACT FROM AUTHOR]

This paper gives upper and lower bounds on the minimum error probability of Bayesian $M$ -ary hypothesis testing in terms of the Arimoto–Rényi conditional entropy of an arbitrary order $\alpha $ . The improved tightness of these bounds over their specialized versions with the Shannon conditional entropy ( $\alpha =1$ ) is demonstrated. In particular, in the case where $M$ is finite, we show how to generalize Fano’s inequality under both the conventional and list-decision settings. As a counterpart to the generalized Fano’s inequality, allowing $M$ to be infinite, a lower bound on the Arimoto–Rényi conditional entropy is derived as a function of the minimum error probability. Explicit upper and lower bounds on the minimum error probability are obtained as a function of the Arimoto–Rényi conditional entropy for both positive and negative $\alpha $ . Furthermore, we give upper bounds on the minimum error probability as functions of the Rényi divergence. In the setup of discrete memoryless channels, we analyze the exponentially vanishing decay of the Arimoto–Rényi conditional entropy of the transmitted codeword given the channel output when averaged over a random-coding ensemble. [ABSTRACT FROM PUBLISHER]

This paper is composed of two main parts related to the nonlinearity of vectorial functions. The first part is devoted to maximally nonlinear (n,m) functions (the so-called bent vectorial functions), which contribute to an optimal resistance to both linear and differential attacks on symmetric cryptosystems. They can be used in block ciphers at the cost of additional diffusion/compression/expansion layers, or as building blocks for the construction of substitution boxes (S-boxes), and they are also useful for constructing robust codes and algebraic manipulation detection codes. A main issue on bent vectorial functions is to characterize bent monomial functions Tr_{m}^{n} (\lambda x^{d}) from \mathbb {F}_{2^{n}} to \mathbb F2^{m} (where m is a divisor of n ) leading to a classification of those bent monomials. We also treat the case of functions with multiple trace terms involving general results and explicit constructions. Furthermore, we investigate some open problems raised by Pasalic et al. and Muratović-Ribić et al. in a series of papers on vectorial functions. The second part is devoted to the nonlinearity of (n,m) -functions. No tight upper bound is known when \frac n2

This paper investigates the asymptotic expansion for the maximum rate of fixed-length codes over a parallel Gaussian channel with feedback under the following setting: a peak power constraint is imposed on every transmitted codeword, and the average error probabilities of decoding the transmitted message are non-vanishing as the blocklength increases. The main contribution of this paper is a self-contained proof of an upper bound on the first- and second-order asymptotics of the parallel Gaussian channel with feedback. The proof techniques involve developing an information spectrum bound followed by using Curtiss’ theorem to show that a sum of dependent random variables associated with the information spectrum bound converges in distribution to a sum of independent random variables, thus facilitating the use of the usual central limit theorem. Combined with existing achievability results, our result implies that the presence of feedback does not improve the first- and second-order asymptotics. [ABSTRACT FROM PUBLISHER]

A regular Hilberg process is a stationary process that satisfies both a hyperlogarithmic growth of maximal repetition and a power-law growth of topological entropy, which are a kind of dual conditions. The hyperlogarithmic growth of maximal repetition has been experimentally observed for texts in natural language, whereas the power-law growth of topological entropy implies a vanishing Shannon entropy rate and thus probably does not hold for natural language. In this paper, we provide a constructive example of regular Hilberg processes, which we call random hierarchical association (RHA) processes. Our construction does not apply the standard cutting and stacking method. For the constructed RHA processes, we demonstrate that the expected length of any uniquely decodable code is the orders of magnitude larger than the Shannon block entropy of the ergodic component of the RHA process. Our proposition supplements the classical result by Shields concerning nonexistence of universal redundancy rates. [ABSTRACT FROM PUBLISHER]

Non-overlapping codes are a set of codewords in $\bigcup _{n \ge 2} \mathbb {Z}_{q}^{n}$ , where $\mathbb {Z}_{q} = \{0,1, {\dots },q-1\}$ , such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$ -ary ones for $q > 2$ , and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate $q$ -ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$ -ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes. [ABSTRACT FROM AUTHOR]

In this paper we prove several coordinate-ordering-free upper bounds on the insdel distances of linear codes. Our bounds are stronger than some previous known bounds. We apply these upper bounds to AGFC codes from some cyclic codes and one algebraic-geometric code with any rearrangement of coordinate positions. A strong upper bound on the insdel distances of Reed-Muller codes with the special coordinate ordering is also given. [ABSTRACT FROM AUTHOR]

In high-dimensional sparse regression, would increasing the signal-to-noise ratio while fixing the sparsity level always lead to better model selection? For high-dimensional sparse regression problems, surprisingly, in this paper we answer this question in the negative in the regime of linear sparsity for the Lasso method, relying on a new concept we term effect size heterogeneity. Roughly speaking, a regression coefficient vector has high effect size heterogeneity if its nonzero entries have significantly different magnitudes. From the viewpoint of this new measure, we prove that the false and true positive rates achieve the optimal trade-off uniformly along the Lasso path when this measure is maximal in a certain sense, and the worst trade-off is achieved when it is minimal in the sense that all nonzero effect sizes are roughly equal. Moreover, we demonstrate that the first false selection occurs much earlier when effect size heterogeneity is minimal than when it is maximal. The underlying cause of these two phenomena is, metaphorically speaking, the “competition” among variables with effect sizes of the same magnitude in entering the model. Taken together, our findings suggest that effect size heterogeneity shall serve as an important complementary measure to the sparsity of regression coefficients in the analysis of high-dimensional regression problems. Our proofs use techniques from approximate message passing theory as well as a novel technique for estimating the rank of the first false variable. [ABSTRACT FROM AUTHOR]

One of the important unsolved problems in information theory is the conjecture that the undirected multiple-unicast network information capacity is the same as the routing capacity. This conjecture is verified only for a handful of networks and network classes. Moreover, only two explicit upper bounds on information capacity are known for general undirected networks: the sparsest cut bound and the linear programming bound. In this paper, we present an information-theoretic upper bound, called the partition bound, on the capacity of general undirected multiple-unicast networks. We show that a decision version problem of computing the bound is NP-complete. We present two classes of undirected multiple-unicast networks such that the partition bound is achievable by routing. Thus, the conjecture is proved for these classes of networks. Recently, the conjecture was proved for a new class of networks defined by properties relating to cut-set and source-sink paths. We show the existence of a network outside of this new class of networks such that the partition bound is achievable by routing. [ABSTRACT FROM AUTHOR]

This paper considers fundamental limits for solving sparse inverse problems in the presence of Poisson noise with physical constraints. Such problems arise in a variety of applications, including photon-limited imaging systems based on compressed sensing (CS). Most prior theoretical results in CS and related inverse problems apply to idealized settings where the noise is independent identically distributed and do not account for signal-dependent noise and physical sensing constraints. Prior results on Poisson CS with signal-dependent noise and physical constraints provided upper bounds on mean-squared error (MSE) performance for a specific class of estimators. However, it was unknown whether those bounds were tight or if other estimators could achieve significantly better performance. This paper provides minimax lower bounds on MSE for sparse Poisson inverse problems under physical constraints. The lower bounds are complemented by minimax upper bounds which match the lower bounds for certain problem sizes and noise levels. The source of the mismatch between upper and lower bounds for other problem sizes and noise levels is discussed. The upper and lower bounds reveal that due to the interplay between the Poisson noise model, the sparsity constraint and the physical constraints: 1) the MSE upper bound does not depend on the sample size $n$ other than to ensure the sensing matrix satisfies Restricted Isometry Property-like conditions and the intensity T$ of the input signal plays a critical role and 2) the MSE upper bound has two distinct regimes, corresponding to low and high intensities, and the transition point from the low-intensity to high-intensity regime depends on the sparsifying basis D$ . In the low-intensity regime, the MSE upper bound is independent of T , where $s$ is the sparsity level, $p$ is the number of pixels or parameters, and $T$ is the signal intensity. [ABSTRACT FROM PUBLISHER]

In this paper, the difference between the redundancy of the optimal asymmetric/symmetric fix-free code, and that of the optimal prefix-free code is considered as the penalty of benefiting from the desired properties of fix-free codes. This penalty is studied from different perspectives. In particular, it is shown that the average penalty of asymmetric fix-free codes is less than 0.21 bit per symbol. Moreover, it is proved that when the source alphabet size is sufficiently large, for almost all sources, the penalty is less than or equal to 0.182 bit per symbol. Regarding symmetric fix-free codes, it is shown that the average penalty tends to infinity as the source alphabet size increases. [ABSTRACT FROM AUTHOR]

In this paper, we study a simple question: when are dynamic relaying strategies essential in optimizing the diversity-multiplexing tradeoff (DMT) in half-duplex wireless relay networks? This is motivated by apparently two contrasting results even for a simple three-node network with a single half-duplex relay. When all channels in the system are assumed to be independent and identically fading, a static schedule where the relay listens half the time and transmits half the time combined with quantize-map-and-forward (QMF) relaying is known to achieve the full-duplex performance. However, when there is no direct link between the source and the destination, a dynamic decode-and-forward (DDF) strategy is needed to achieve the optimal tradeoff. In this case, a static schedule is strictly suboptimal and the optimal tradeoff is significantly worse than the full-duplex performance. In this paper, we study the general case when the direct link is neither as strong as the other links nor fully nonexistent, and identify regimes where dynamic schedules are necessary and those where static schedules are enough. We identify four qualitatively different regimes for the single-relay channel, where the tradeoff between diversity and multiplexing is significantly different. We show that in all these regimes one of the above two strategies is sufficient to achieve the optimal tradeoff by developing a new upper bound on the best achievable tradeoff under channel state information available only at the receivers. A natural next question is whether these two strategies are sufficient to achieve the DMT of more general half-duplex wireless networks with a larger number of relays. We propose a generalization of the two existing schemes through a dynamic QMF (DQMF) strategy, where the relay listens for a fraction of time depending on received channel state information but not long enough to be able to decode. We show that such a DQMF strategy is needed to achieve the optimal DMT in a parallel channel with two relays, outperforming both DDF and static QMF strategies. [ABSTRACT FROM AUTHOR]

The objective of this paper is the characterization of the Wyner–Ziv rate-distortion function for memoryless continuous sources, when the correlation between the sources is modeled via an additive noise channel. Modeling the distribution of the correlation noise via a Gaussian mixture, with discrete or continuous mixing variable, provides a unified signal model able to describe a wide class of distributions, useful in the context of practical applications. The Wyner–Ziv rate-distortion function associated with this signal model cannot, in general, be obtained in analytical form. This paper contributes a method for its analysis, by providing computable upper and lower bounds. [ABSTRACT FROM AUTHOR]

In this paper, Bayesian quickest change detection problems with sampling right constraints are considered. In particular, there is a sequence of random variables whose probability density function will change at an unknown time. The goal is to detect this change in a way such that a linear combination of the average detection delay and the false alarm probability is minimized. Two types of sampling right constrains are discussed. The first one is a limited sampling right constraint, in which the observer can take at most \(N\) observations from this random sequence. Under this setup, we show that the cost function can be written as a set of iterative functions, which can be solved by Markov optimal stopping theory. The optimal stopping rule is shown to be a threshold rule. An asymptotic upper bound of the average detection delay is developed as the false alarm probability goes to zero. This upper bound indicates that the performance of the limited sampling right problem is close to that of the classic Bayesian quickest detection for several scenarios of practical interest. The second constraint discussed in this paper is a stochastic sampling right constraint, in which sampling rights are consumed by taking observations and are replenished randomly. The observer cannot take observations if there are no sampling rights left. We characterize the optimal solution, which has a very complex structure. For practical applications, we propose a low complexity algorithm, in which the sampling rule is to take observations as long as the observer has sampling rights left and the detection scheme is a threshold rule. We show that this low complexity scheme is first order asymptotically optimal as the false alarm probability goes to zero. [ABSTRACT FROM AUTHOR]

In this paper, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers \(q\) and \(m\) , where \(q\) is an odd prime and \(m \leq q\) . In the literature, the minimum/stopping distance of these codes (denoted by \(d(q,m)\) and \(h(q,m)\) , respectively) has been thoroughly studied for \(m \leq 5\) . Both exact results, for small values of \(q\) and \(m\) , and general (i.e., independent of \(q\) ) bounds have been established. For \(m=6\) , the best known minimum distance upper bound, derived by Mittelholzer, is \(d(q,6) \leq 32\) . In this paper, we derive an improved upper bound of \(d(q,6) \leq 20\) and a new upper bound \(d(q,7) \leq 24\) by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of \(q\) using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for \(m \leq 7\) and low-to-moderate values of \(q \leq 79\) . [ABSTRACT FROM AUTHOR]

This paper investigates the problem of characterizing the capacity of Half-Duplex (HD) line networks, where a source node communicates to a destination node through a multi-hop path of $N$ relays. If the relays operate in Full-Duplex (FD), it is well known that the capacity of the line network equals the minimum among the point-to-point link capacities in the path. In contrast, this paper considers a different case where the relays operate in HD. In the first part of the paper, it is shown that the approximate capacity (optimal up to a constant additive gap that only depends on the number of nodes in the network) of an HD $N$ -relay line network equals half the minimum of the harmonic means of the point-to-point link capacities of each two consecutive links in the path. It is then proved that the $N+1$ listen/transmit states (out of the $2^{N}$ possible ones) sufficient to characterize the approximate capacity can be found in linear time. In the second part of the paper, it is shown that the problem of finding the path that has the largest HD approximate capacity in a network that can be represented as a graph is NP-hard. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-time algorithm can indeed be designed. [ABSTRACT FROM AUTHOR]

The tight lower bound on the redundancy of optimal prefix-free codes in terms of a given symbol probability (not necessarily the largest or the smallest one) has been derived in the literature. The first goal of this paper is to derive the tight lower bounds in terms of $j$ ($j>1$) known symbol probabilities of the source using some properties of Kullback-Leibler distance. Since fix-free codes are special prefix-free codes (for which no codeword is a suffix of the other codewords), it is clear that all lower bounds on the redundancy of optimal prefix-free codes are also valid for fix-free ones. Accordingly, the second question of the paper is on the tightness of the derived lower bounds for optimal fix-free codes. It is proven that these lower bounds are tight for optimal fix-free codes if $j\leq 3$ , and are not tight for $j\geq 4$. Also, it is shown that the tight lower bound in terms of the probability of the most likely symbol is the same for optimal prefix-free and optimal fix-free codes. [ABSTRACT FROM AUTHOR]

Let $\mathbb {F}_{q}$ be the finite field of $q$ elements. In this paper we obtain bounds on the following counting problem: given a polynomial $f(x)\in \mathbb {F}_{q} [x]$ of degree $k+m$ and a non-negative integer $r$ , count the number of polynomials $g(x)\in \mathbb {F}_{q} [x]$ of degree at most $k-1$ such that $f(x)+g(x)$ has exactly $r$ roots in $\mathbb {F}_{q}$. Previously, explicit formulas were known only for the cases $m=0, 1, 2$. As an application, we obtain an asymptotic formula on the list size of the standard Reed-Solomon code $[q, k, q-k+1]_{q}$. [ABSTRACT FROM AUTHOR]

Fractional repetition (FR) codes form a special class of minimum bandwidth regenerating codes by providing uncoded repairs via a table-based repair model. For a given file size, it is desirable to design FR codes that minimize the reconstruction degree, which is defined as the number of storage nodes required for data retrieval. In this paper, we first consider a lower bound on the reconstruction degree of FR codes obtained by Silberstein and Etzion. We present several families of FR codes that attain this lower bound, which are derived from combinatorial designs and regular graphs. We further provide a new lower bound on the reconstruction degree of FR codes, which is tighter than the existing one. Moreover, we show that for an FR code with reconstruction degree achieving the lower bounds, the corresponding dual code attains upper bounds on the supported file size. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRC) have been studied from two approaches to locally repair multiple failed nodes: 1) parallel approach, in which a coordinate $i$ of an $[n,k,d]$ linear code is said to have locality $r$ and availability $t$ if there exist $t$ disjoint repair sets each of which contains at most $r$ other coordinates that can recover the value of the $i$ -th coordinate; 2) sequential approach, in which the erased symbols (failed nodes) are repaired, one by one, and any previously repaired node can be used to repair the remaining failed nodes. In this paper, we first consider LRC aiming at joint sequential-parallel repairing multiple failed nodes, and study the $(n,k,r,t,u)$ -ELRCs (Exact locally repairable codes) which are $[n,k]$ linear codes with the property that any set of failed nodes of size at most $t$ can be simultaneously repaired in parallel mode, and each element of a set $E$ of failed nodes of size at most $u$ can be sequentially repaired by $r$ ($r< k$) other coordinates. We present a method by which with a given parity-check matrix of an $(n,k,r,t,u)$ -ELRC with minimum Hamming distance $d$ , a new ELRC with minimum Hamming distance $2d$ and availability $t+1$ is constructed that can repair each set of failed nodes $E$ of size at most $2u+1$ in sequential mode and this repair is done in at most $u-t+2$ steps. We construct a big family of LRCs by making use of orthogonal Latin rectangles and permutation cubes and some other combinatorial designs; the constructed codes contain the family of direct product codes; we also use $m$ -dimensional permutation cubes to construct LRCs with short block length for each $r$. [ABSTRACT FROM AUTHOR]

Locally recoverable (LRC) codes provide ways of recovering erased coordinates of the codeword without having to access each of the remaining coordinates. A subfamily of LRC codes with hierarchical locality (H-LRC codes) provides added flexibility to the construction by introducing several tiers of recoverability for correcting different numbers of erasures. We present a general construction of codes with 2-level hierarchical locality from maps between algebraic curves and specialize it to several code families obtained from quotients of curves by a subgroup of the automorphism group, including rational, elliptic, Kummer, and Artin–Schreier curves. We further address the question of H-LRC codes with availability, and suggest a general construction of such codes from fiber products of curves. Detailed calculations of parameters for H-LRC codes with availability are performed for Reed–Solomon- and Hermitian-like code families. Finally, we construct asymptotically good families of H-LRC codes from curves related to the Garcia–Stichtenoth tower. [ABSTRACT FROM AUTHOR]

In this paper, we establish a new bound tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper bound on the correlation between the outputs of these functions. The upper bound may find applications in problems in many areas which deal with common information. We build upon Witsenhausen’s result on maximum correlation. The present upper bound takes into account the effective length of the Boolean functions in characterizing the correlation. We use the new bound to characterize the communication-cooperation tradeoff in multi-terminal communications. We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider an ensemble of BBCs which is randomly generated using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to bound the correlation between the outputs of two distributed BBCs. Finally, the upper bound is used to show that the large blocklength single-letter coding schemes studied in the literature are sub-optimal in various multi-terminal communication settings. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) have gained significant interest for the design of large distributed storage systems as they allow a small number of erased nodes to be recovered by accessing only a few others. Several works have thus been carried out to understand the optimal rate–distance tradeoff, but only recently the size of the alphabet has been taken into account. In this paper, a novel definition of locality is proposed to keep track of the precise number of nodes required for a local repair when the repair sets do not yield MDS codes. Then, a new alphabet-dependent bound is derived, which applies both to the new definition and the initial definition of locality. The new bound is based on consecutive residual codes and intrinsically uses the Griesmer bound. A special case of the bound yields both the extension of the Cadambe–Mazumdar bound and the Singleton-type bound for codes with locality $(r,\delta)$ , implying that the new bound is at least as good as these bounds. Furthermore, an upper bound on the asymptotic rate–distance tradeoff of LRCs is derived, and yields the tightest known upper bound for large relative minimum distances. Achievability results are also provided by deriving the locality of the family of Simplex codes together with a few examples of optimal codes. [ABSTRACT FROM AUTHOR]

Due to wide applications of binary sequences with a low correlation to communications, various constructions of such sequences have been proposed in the literature. Many efforts have been made to construct good binary sequences with various lengths. However, most of the known constructions make use of the multiplicative cyclic group structure of finite field $\mathbb {F}_{2^{n}}$ for a positive integer $n$. It is often overlooked in this community that all $2^{n}+1$ rational places (including “the place at infinity”) of the rational function field over $\mathbb {F}_{2^{n}}$ form a cyclic structure under an automorphism of order $2^{n}+1$. In this paper, we make use of this cyclic structure to provide an explicit construction of binary sequences with a low correlation of length $2^{n}+1$ via cyclotomic function fields over $\mathbb {F}_{2^{n}}$. Each family of our sequences has size $2^{n}-1$ and its correlation is upper bounded by $\lfloor 2^{(n+2)/2}\rfloor $. To the best of our knowledge, this is the first construction of binary sequences with a low correlation of length $2^{n}+1$. Moreover, our sequences can be constructed explicitly and have competitive parameters. In particular, compared with the Gold sequences of length $2^{n}-1$ for even $n$ , our sequences have a smaller correlation and a larger length although the family size of our sequences is slightly smaller. [ABSTRACT FROM AUTHOR]

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly-noisy tests, and has numerous practical applications. One of the defining features of group testing is whether the tests are adaptive (i.e., a given test can be chosen based on all previous outcomes) or non-adaptive (i.e., all tests must be chosen in advance). In this paper, building on the success of binary splitting techniques in noiseless group testing (Hwang, 1972), we introduce noisy group testing algorithms that apply noisy binary search as a subroutine. We provide three variations of this approach with increasing complexity, culminating in an algorithm that succeeds using a number of tests that matches the best known previously (Scarlett, 2019), while overcoming fundamental practical limitations of the existing approach, and more precisely capturing the dependence of the number of tests on the error probability. We provide numerical experiments demonstrating that adaptive group testing strategies based on noisy binary search can be highly effective in practice, using significantly fewer tests compared to state-of-the-art non-adaptive strategies. [ABSTRACT FROM AUTHOR]

In this paper we consider the diversity-multiplexing gain tradeoff (DMT) of so-called minimum delay asymmetric space-time codes for the $n \times m$ MIMO channel. Such codes correspond to lattices in $M_{n}(\mathbb {C})$ with dimension smaller than $2n^{2}$. Currently, very little is known about their DMT, except in the case $m=1$ , corresponding to the multiple input single output (MISO) channel. Further, apart from the MISO case, no DMT optimal asymmetric codes are known. We first discuss previous criteria used to analyze the DMT of space-time codes and comment on why these methods fail when applied to asymmetric codes. We then consider two special classes of asymmetric codes where the code-words are restricted to either real or quaternion matrices. We prove two separate diversity-multiplexing gain trade-off (DMT) upper bounds for such codes and provide a criterion for a lattice code to achieve these upper bounds. We also show that lattice codes based on $\mathbb {Q}$ -central division algebras satisfy this optimality criterion. As a corollary this result provides a DMT classification for all $\mathbb {Q}$ -central division algebra codes that are based on standard embeddings. While the $\mathbb {Q}$ -central division algebra based codes achieve the largest possible DMT of a code restricted to either real or quaternion space, they still fall short of the optimal DMT apart from the MISO case. [ABSTRACT FROM AUTHOR]

This paper studies properties of binary runlength-limited sequences with additional constraints on their Hamming weight and/or their number of runs of identical symbols. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained by using the methods of multivariate analytic combinatorics, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for weight-preserving and run-preserving channels (e.g., the run-preserving insertion-deletion channel), a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences. In addition, the asymptotics of a closely related notion— $q$ -ary sequences with fixed Manhattan weight—is briefly discussed, and an application in coding for molecular timing channels is illustrated. [ABSTRACT FROM AUTHOR]

We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. In contrast, for sources with semi-unbounded support, there may be a finite upper bound on the number of bins in equilibrium depending on certain conditions stated explicitly. Moreover, we prove that for log-concave sources, the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove convergence to the unique equilibrium under best response dynamics which starts with a given number of bins, making a connection with the classical theory of optimal quantization and convergence results of Lloyd’s method. In addition, we consider more general sources which satisfy certain assumptions on the tail(s) of the distribution and we show that there exist equilibria with infinitely many bins for sources with two-sided unbounded support. Further explicit characterizations are provided for sources with exponential, Gaussian, and compactly-supported probability distributions. [ABSTRACT FROM AUTHOR]

A general class of Bayesian lower bounds when the underlying loss function is a Bregman divergence is demonstrated. This class can be considered as an extension of the Weinstein–Weiss family of bounds for the mean squared error and relies on finding a variational characterization of Bayesian risk. This approach allows for the derivation of a version of the Cramér–Rao bound that is specific to a given Bregman divergence. This new generalization of the Cramér–Rao bound reduces to the classical one when the loss function is taken to be the Euclidean norm. In order to evaluate the effectiveness of the new lower bounds, the paper also develops upper bounds on Bayesian risk, which are based on optimal linear estimators. The effectiveness of the new bound is evaluated in the Poisson noise setting. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the combinatorial error model of Mazumdar et al. that models errors in high-density magnetic recording caused by lack of knowledge of grain boundaries in the recording medium. We present new upper bounds on the cardinality/rate of binary block codes that correct errors within this model. All our bounds, except for one, are obtained using combinatorial arguments based on hypergraph fractional coverings. The exception is a bound derived via an information-theoretic argument. Our bounds significantly improve upon existing bounds from the prior literature. [ABSTRACT FROM PUBLISHER]

Binary almost instantaneous fixed-to-variable length (AIFV) codes are lossless codes that generalize the class of instantaneous fixed-to-variable length codes. The code uses two code trees and assigns source symbols to incomplete internal nodes as well as to leaves. AIFV codes are empirically shown to attain better compression ratio than Huffman codes. Nevertheless, an upper bound on the redundancy of optimal binary AIFV codes is only known to be 1, which is the same as the bound of Huffman codes. In this paper, the upper bound is improved to 1/2, which is shown to coincide with the worst-case redundancy of the codes. Along with this, the worst-case redundancy is derived for sources with p\max \geq 1 /2, where p\max is the probability of the most likely source symbol. In addition, we propose an extension of binary AIFV codes, which use $m$ code trees and allow at most $m$ -bit decoding delay. We show that the worst-case redundancy of the extended binary AIFV codes is $1/m$ for $m \leq 4$ . [ABSTRACT FROM AUTHOR]

In order to scale economically, data centers are increasingly evolving their data storage methods from simple data replication to more powerful erasure codes, which provide the same level of reliability as replication, but at a significantly lower storage cost. In particular, it is well known that maximum-distance-separable (MDS) codes, such as Reed–Solomon codes, can achieve a target reliability with the maximum storage efficiency. While the use of codes for providing improved reliability in archival storage systems, where data is less frequently accessed (or so-called “cold data”), is well understood, the role of codes in storing more frequently accessed and active “hot data”, where latency is the key metric, is less clear. In this paper, we study data storage systems based on MDS codes through the lens of queueing theory, and term the queueing system arising under codes as an “MDS queue.” We provide lower and upper bounds on the average job latency for both centralized and decentralized versions of MDS queues. We also provide extensive simulations to corroborate our analysis as well as obtain additional insights. [ABSTRACT FROM PUBLISHER]

In this paper, we address the problem of the universal coding of natural numbers. A new numeration system is introduced, which is based on variable- $r$ meta-Fibonacci sequences and it is a generalization of the Zeckendorf numeration system. This new numeration system is used to construct binary, prefix-free, uniquely decodable universal codes called meta-Fibonacci codes. The main advantage of these codes is that they are parametrized by a sequence of numbers, the sequence o. By controlling the growth of the values of this sequence, we can control the length of the code word. This means that we can provide a general framework for building efficient universal coders for natural numbers. Such framework is applied to the upper bounds of the code word length defined by Leung-Yan-Cheong and Cover (1978), Levenshtein (1968), and Ahlswede (1997). There is no other code meeting these bounds. In each case, we build meta-Fibonacci codes and demonstrate that the upper bound of their code word length is satisfied up to an additive constant, thereby solving these open problems. The framework may be applied to other upper bounds that satisfy Kraft inequality. [ABSTRACT FROM PUBLISHER]

The noise model of deletions poses significant challenges in coding theory, with basic questions like the capacity of the binary deletion channel still being open. In this paper, we study the harder model of worst case deletions, with a focus on constructing efficiently decodable codes for the two extreme regimes of high-noise and high-rate. Specifically, we construct polynomial-time decodable codes with the following tradeoffs (for any \varepsilon > 0 ): 1) codes that can correct a fraction 1- \varepsilon of deletions with rate \mathop \mathrm poly\nolimits ( \varepsilon ) over an alphabet of size \mathop \mathrm poly\nolimits (1/ \varepsilon ) ; 2) binary codes of rate 1-\tilde O(\sqrt \varepsilon ) that can correct a fraction $ \varepsilon $ of deletions; and 3) Binary codes that can be list-decoded from a fraction (1/2- \varepsilon )$ of deletions with rate \mathop {\mathrm {poly}}\nolimits ( \varepsilon ) . This paper gives the first efficient constructions which meet the qualitative goals of correcting a deletion fraction approaching 1 over bounded alphabets, and correcting a constant fraction of bit deletions with rate approaching 1 over a fixed alphabet. The above-mentioned results bring our understanding of deletion code constructions in these regimes to a similar level as worst case errors. [ABSTRACT FROM PUBLISHER]

Shannon’s analysis of the fundamental capacity limits for memoryless communication channels has been refined over time. In this paper, the maximum volume M_ \mathrm avg^*(n,\epsilon ) of length- n codes subject to an average decoding error probability \epsilon is shown to satisfy the following tight asymptotic lower and upper bounds as n \to \infty : , where C is the Shannon capacity, V_\epsilon is the \epsilon -channel dispersion, or second-order coding rate, Q and \overline A_\epsilon are explicitly identified. This expression holds under mild regularity assumptions on the channel, including nonsingularity. The gap \overline A_\epsilon - \underline A_\epsilon is one nat for weakly symmetric channels in the Cover–Thomas sense, and typically a few nats for other symmetric channels, for the binary symmetric channel, and for the $Z$ channel. The derivation is based on strong large-deviations analysis and refined central limit asymptotics. A random coding scheme that achieves the lower bound is presented. The codewords are drawn from a capacity-achieving input distribution modified by an O(1/\sqrt {n}) correction term. [ABSTRACT FROM PUBLISHER]

This paper studies problems in data reconstruction, an important area with numerous applications. In particular, we examine the reconstruction of binary and nonbinary sequences from synchronization (insertion/deletion-correcting) codes. These sequences have been corrupted by a fixed number of symbol insertions (larger than the minimum edit distance of the code), yielding a number of distinct traces to be used for reconstruction. We wish to know the minimum number of traces needed for exact reconstruction. This is a general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding an upper bound on the number of distinct traces necessary to guarantee exact reconstruction. Without specific knowledge of the code words, this upper bound is tight. We apply our results to the famous single deletion/insertion-correcting Varshamov–Tenengolts (VT) codes and show that a significant number of VT code word pairs achieve the worst case number of outputs needed for exact reconstruction. We also consider extensions to other channels, such as adversarial deletion and insertion/deletion channels and probabilistic channels. [ABSTRACT FROM PUBLISHER]

In many applications including communications, one may encounter a linear model where the parameter vector \hat x is an integer vector in a box. To estimate \hat x , a typical method is to solve a box-constrained integer least squares problem. However, due to its high complexity, the box-constrained Babai integer point x^ \scriptscriptstyle \text BB is commonly used as a suboptimal solution. In this paper, we first derive formulas for the success probability P^ \scriptscriptstyle \text BB of x^ \scriptscriptstyle \text BB and the success probability P^ \scriptscriptstyle \text OB of the ordinary Babai integer point x^ \scriptscriptstyle \text OB when \hat x is uniformly distributed over the constraint box. Some properties of P^ \scriptscriptstyle \text BB and P^ \scriptscriptstyle \text OB and the relationship between them are studied. Then, we investigate the effects of some column permutation strategies on P^ \scriptscriptstyle \text BB . In addition to V-BLAST and SQRD, we also consider the permutation strategy involved in the LLL lattice reduction, to be referred to as LLL-P. On the one hand, we show that when the noise is relatively small, LLL-P always increases P^ \scriptscriptstyle \text BB and argue why both V-BLAST and SQRD often increase P^ \scriptscriptstyle \text BB ; and on the other hand, we show that when the noise is relatively large, LLL-P always decreases P^ \scriptscriptstyle \text BB and argue why both V-BLAST and SQRD often decrease P^ \scriptscriptstyle \text BB . We also derive a column permutation invariant bound on P^ \scriptscriptstyle \text BB , which is an upper bound and a lower bound under these two opposite conditions, respectively. Numerical results demonstrate our findings. Finally, we consider a conjecture concerning x^ \scriptscriptstyle \text OB proposed by Ma et al. We first construct an example to show that the conjecture does not hold in general, and then show that it does hold under some conditions. [ABSTRACT FROM PUBLISHER]

In this paper, list decoding of crisscross errors in arrays over finite fields is considered. For this purpose, the so-called cover metric is used, where the cover of a matrix is a set of rows and columns which contains all non-zero elements of the matrix. A Johnson-like upper bound on the maximum list size in the cover metric is derived, showing that the list of codewords has polynomial size up to a certain radius. Furthermore, a simple list decoding algorithm for a known optimal code construction is presented, which decodes errors in the cover metric up to our upper bound. These results reveal significant differences between the cover metric and the rank metric and show that the cover metric is more suitable for correcting crisscross errors. [ABSTRACT FROM PUBLISHER]

This paper starts with new aliasing-truncation error upper bounds in the sampling theorem for non-bandlimited stochastic signals. Then, it investigates Lp([0,T]) approximations of the sub-Gaussian random signals. Explicit truncation error upper bounds are established. The obtained rate of convergence provides a constructive algorithm for determining the sampling rate and the sample size in the truncated Whittaker-Kotel’nikov-Shannon expansions to ensure the approximation of the sub-Gaussian signals with given accuracy and reliability. Some numerical examples are presented. [ABSTRACT FROM AUTHOR]

In this paper, we investigate an instance of the Heegard–Berger problem with two sources and arbitrarily correlated side information sequences at two decoders, in which the reconstruction sets at the decoders are degraded. Specifically, two sources are to be encoded in a manner that one of the two is reproduced losslessly by both the decoders, and the other is reproduced within some prescribed distortion level at one of the two decoders. We establish a single-letter characterization of the rate-distortion function for this model. In particular, we show that the optimal coding scheme for this setting is one in which the common description to be recovered by both the decoders should allow to involve all or part of the source that is to be reproduced at only one decoder. Furthermore, we also generalize our result to the setting in which the source component that is to be recovered by both users is reconstructed in a lossy fashion, under the requirement that all terminals (i.e., the encoder and both the decoders) can share an exact copy of the compressed version of this source component, i.e., a common encoder–decoder reconstruction constraint. For this model as well, we establish a single-letter characterization of the associated rate-distortion function. [ABSTRACT FROM PUBLISHER]

Reed-Muller codes are error-correcting codes used in many areas related to coding theory, such as electrical engineering and computer science. The binary $r^{th}$ -order Reed-Muller code $RM(r,n)$ can be viewed as the set of all $n$ -variable Boolean functions of algebraic degree at most $r$. Despite the intense work on these codes, many problems are known to be hard (notably, determining their covering radius) and remain open to this day. Fourteen years ago, Carlet and Mesnager improved in [IEEE Transactions on Information Theory, “Improving the Upper Bounds on the Covering Radii of Binary Reed-Muller Codes”, 53(1), 2007] the upper bound on the covering radius of the Reed-Muller code of order 2, and they deduced improved upper bounds on the covering radii of the Reed-Muller codes of higher orders. Until 2021, these upper bounds remained the best ones in the literature. The Reed-Muller code $RM(n-3,n)$ , which corresponds to the dual of the Reed-Muller code $RM(2,n)$ , has attracted much attention. One of the main reasons is that it is precisely the code that has been considered to get the upper bounds derived by Carlet and Mesnager. Those upper bounds have been obtained thanks to the characterization of the codewords of the Reed-Muller code, whose Hamming weights are strictly less than 2.5 times the minimum distance $2^{n-r}$ due to Kasami, Tokura, and Azumi. Despite their impressive work in the seventieth, a more refined study and profound description of those codewords of ${RM}({n-3},{n})$ whose Hamming weight equals 16, and especially 18, seem necessary, as it could help us significantly in improving the covering radius of Reed-Muller codes. In this paper, we push further the known results on the Reed-Muller codes by focusing on the Reed-Muller code ${RM}({n-3},{n})$. We provide a classification of the codewords of weights 16 and 18 of the Reed-Muller code $RM(n-3,n)$. Our algebraic descriptions allow us to count the number of such codewords and to enumerate all of them explicitly. [ABSTRACT FROM AUTHOR]

This paper employs auxiliary receivers as a mathematical tool to identify Gallager-type auxiliary random variables and write outer bounds for some basic multiuser settings. This approach is then applied to the relay, interference, and broadcast channel settings, yielding new outer bounds that improve on existing outer bounds and strictly outperform classical outer bounds. For instance, we strictly improve on: the cutset outer bound for the scalar Gaussian relay channel, the outer bounds for the Gaussian Z-interference channel, and the outer bounds for the two receiver broadcast channel. [ABSTRACT FROM AUTHOR]

Minimal linear codes are in one-to-one correspondence with special types of blocking sets of projective spaces over a finite field, which are called strong or cutting blocking sets. Minimal linear codes have been studied since decades but their tight connection with cutting blocking sets of finite projective spaces was unfolded only in the past few years, and it has not been fully exploited yet. In this paper we apply finite geometric and probabilistic arguments to contribute to the field of minimal codes. We prove an upper bound on the minimal length of minimal codes of dimension $k$ over the $q$ -element Galois field which is linear in both $q$ and $k$ , hence improve the previous superlinear bounds. This result determines the minimal length up to a small constant factor. We also improve the lower and upper bounds on the size of so called higgledy-piggledy line sets in projective spaces and apply these results to present improved bounds on the size of covering codes and saturating sets in projective spaces as well. [ABSTRACT FROM AUTHOR]

The zero capacity region for hexagonal $(d,k)$ run-length constraints is known for many, but not all, $d$ and $k$. The pairs $(d,k)$ for which it has been unproven whether the capacity is zero or positive consist of: (i) $k=d+2$ when $d\ge 2$ ; (ii) $k=d+3$ when $d \ge 1$ ; (iii) $k=d+4$ when either $d=4$ or $d$ is odd and $d \ge 3$ ; and (iv) $k=d+5$ when $d=4$. Here, we prove that the capacity is zero for all of case (i), and for case (ii) whenever $d \ge 7$. The method used in this paper is to reduce an infinite search space of valid labelings to a finite set of configurations that we exhaustively examine using backtracking. In Part II of this two-part series, we use automated procedures to prove that the capacity is zero in case (i) when $2 \le d \le 9$ , in case (ii) when $3 \le d \le 11$ , and in case (iii) when $d \in \{ 4,5,7,9 \}$ , and that the capacity is positive in case (ii) when $d \in \{1,2\}$ , in case (iii) when $d = 3$ , and in case (iv). Thus, the only remaining unknown cases are now when $k=d+4$ , for any odd $d \ge 11$. [ABSTRACT FROM AUTHOR]

Meta-learning automatically infers an inductive bias by observing data from a number of related tasks. The inductive bias is encoded by hyperparameters that determine aspects of the model class or training algorithm, such as initialization or learning rate. Meta-learning assumes that the learning tasks belong to a task environment, and that tasks are drawn from the same task environment both during meta-training and meta-testing. This, however, may not hold true in practice. In this paper, we introduce the problem of transfer meta-learning, in which tasks are drawn from a target task environment during meta-testing that may differ from the source task environment observed during meta-training. Novel information-theoretic upper bounds are obtained on the transfer meta-generalization gap, which measures the difference between the meta-training loss, available at the meta-learner, and the average loss on meta-test data from a new, randomly selected, task in the target task environment. The first bound, on the average transfer meta-generalization gap, captures the meta-environment shift between source and target task environments via the KL divergence between source and target data distributions. The second, PAC-Bayesian bound, and the third, single-draw bound, account for this shift via the log-likelihood ratio between source and target task distributions. Furthermore, two transfer meta-learning solutions are introduced. For the first, termed Empirical Meta-Risk Minimization (EMRM), we derive bounds on the average optimality gap. The second, referred to as Information Meta-Risk Minimization (IMRM), is obtained by minimizing the PAC-Bayesian bound. IMRM is shown via experiments to potentially outperform EMRM. [ABSTRACT FROM AUTHOR]

Let $n (>3)$ be a prime number and ${\mathbb {F}}_{2^{n}}$ a finite field of $2^{n}$ elements. Let $L ={\mathbb {F}}_{2^{n}}\cup \{\infty \}$ be the support set and $g(x)$ an irreducible polynomial of degree 6 over ${\mathbb {F}}_{2^{n}}$. In this paper, we obtain an upper bound on the number of extended irreducible binary Goppa codes $\Gamma (L, g)$ of degree 6 and length $2^{n}+1$. [ABSTRACT FROM AUTHOR]

We study the stability of low-density parity-check codes under blockwise or bitwise maximum a posteriori decoding, where transmission takes place over a binary-input memoryless output-symmetric channel. Our study stems from the consideration of constructing universal capacity-achieving codes under low-complexity decoding algorithms, where universality refers to the fact that we are considering a family of channels with equal capacity. Consider, e.g., the right-regular sequence by Shokrollahi and the heavy-tail Poisson sequence by Luby et al. Both sequences are provably capacity-achieving under belief propagation decoding when transmission takes place over the binary erasure channel. In this paper we show that many existing capacity-achieving sequences of low-density parity-check codes are not universal under belief propagation decoding. We reveal that the key to showing this non-universality result is determined by the stability of the underlying codes. More concretely, for an ordered and complete channel family and a sequence of low-density parity-check code ensembles, we determine a stability threshold associated with them, which gives rise to a sufficient condition under which the sequence is not universal under belief propagation decoding. Moreover, we show that the same stability threshold applies to blockwise or bitwise maximum a posteriori decoding as well. We demonstrate how the stability threshold can determine an upper bound on the corresponding blockwise or bitwise maximum a posteriori threshold, revealing the operational significance of the stability threshold. [ABSTRACT FROM AUTHOR]

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may either fail to return a codeword or miscorrect to an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of error matrices decodable by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known. [ABSTRACT FROM AUTHOR]

It has recently been observed that the permanent of a nonnegative square matrix, i.e., of a square matrix containing only nonnegative real entries, can very well be approximated by solving a certain Bethe free energy function minimization problem with the help of the sum–product algorithm. We call the resulting approximation of the permanent the Bethe permanent. In this paper, we give reasons why this approach to approximating the permanent works well. Namely, we show that the Bethe free energy function is convex and that the sum–product algorithm finds its minimum efficiently. We then discuss the fact that the permanent is lower bounded by the Bethe permanent, and we comment on potential upper bounds on the permanent based on the Bethe permanent. We also present a combinatorial characterization of the Bethe permanent in terms of permanents of so-called lifted versions of the matrix under consideration. Moreover, we comment on possibilities to modify the Bethe permanent so that it approximates the permanent even better, and we conclude the paper with some observations and conjectures about permanent-based pseudocodewords and permanent-based kernels. [ABSTRACT FROM AUTHOR]

In this paper, we explore some of the fundamentals of synchronous Code Division Multiple Access (CDMA) as applied to wireless and optical communication systems under very general settings (of any size) for the user symbols and the signature matrix entries. The channel is modeled by real/complex additive noise of arbitrary distribution. Two problems are addressed. The first problem concerns whether uniquely detectable overloaded matrices exist in the absence of additive noise under these general settings, and if so, whether there are any practical optimum detection algorithms. The second one is about the bounds for the sum channel capacity when user data and signature matrices employ any real or complex alphabets (finite or infinite). In response to the first problem, we have developed practical maximum likelihood detection algorithms for overloaded CDMA systems for a large class of alphabets. In response to the second problem, a general theorem has been developed in which the sum capacity lower bounds with respect to the number of users, spreading gain, and signal-to-noise ratio can be derived. To show the power and utility of the main theorem, a number of sum capacity bounds for special cases are evaluated. An important conclusion of this paper is that the lower and upper bounds of the sum capacity for small/medium-size CDMA systems depend on both the input and the signature symbols; this is contrary to the asymptotic results for large-scale systems reported in the literature (also confirmed in this paper) where the signature symbols and statistics disappear for signature matrices and input vectors with i.i.d. entries. Furthermore, upper and asymptotic bounds are derived and compared to other derivations. [ABSTRACT FROM AUTHOR]