Search

Recently, there has been a lot of success in using the deterministic approach to provide approximate characterization of Gaussian network capacity. In this paper, we take a deterministic view and revisit the problem of wiretap channel with side information. A precise characterization of the secrecy capacity is obtained for a linear deterministic model, which naturally suggests a coding scheme which we show to achieve the secrecy capacity of the degraded Gaussian model (dubbed as “secret writing on dirty paper”) to within half a bit. [ABSTRACT FROM PUBLISHER]

It is known that there exist mathematical problems of practical relevance which cannot be computed on a Turing machine. An important example is the calculation of the first derivative of continuously differentiable functions. This paper precisely classifies the non-computability of the first derivative, and of the maximum-norm of the first derivative in the Zheng-Weihrauch hierarchy. Based on this classification, the paper investigates whether it is possible that a Turing machine detects this non-computability of the first derivative by observing the data of the problem, and whether it is possible to detect upper bounds for the peak value of the first derivative of continuously differentiable functions. So from a practical point of view, the question is whether it is possible to implement an exit-flag functionality for observing non-computability of the first derivative. This paper even studies two different types of exit-flag functionality. A strong one, where the Turing machine always has to stop, and a weak one, where the Turing machine stops if and only if the input lies within the corresponding set of interest. It will be shown that non-computability of the first derivative is not detectable by a Turing machine for two concrete examples, namely for the problem of computing the input–output behavior of simple analog circuits and for solutions of the three-dimensional wave equation. In addition, it is shown that it is even impossible to detect an upper bound for the maximum norm of the first derivative. In particular, it is shown that all three problems are not even semidecidable. Finally, we briefly discuss implications of these results for analog and quantum computing. [ABSTRACT FROM AUTHOR]

In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, in this paper, we consider the case where the process of encoding is distributed and prone to error. We introduce the problem of distributed encoding, comprised of a set of $K \in \mathbb {N}$ isolated source nodes and $N \in \mathbb {N}$ encoding nodes. Each source node has one symbol from a finite field, which is sent to each of the encoding nodes. Each encoding node stores an encoded symbol from the same field, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of the adversarial nodes, denoted by $\beta \in \mathbb {N}$ , and the cardinality of the set of symbols that each one generates, denoted by $v \in \mathbb {N}$ , the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of $t \in \mathbb {N}$ encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. An important characteristic of a distributed encoding system is $t^{*} \in \mathbb {N}$ , the minimum of such $t$ , which is a function of $K$ , $N$ , $\beta $ , and $v$. In this paper, we study the distributed linear encoding system, i.e. one in which the encoding nodes use linear coding. We show that $t^{*}_{\textrm {Linear}}=K+2\beta (v-1)$ , if $N\ge K+2\beta (v-1)$ , and $t^{*}_{\textrm {Linear}}=N$ , if $N\le K+2\beta (v-1)$. In order to achieve $t^{*}_{\textrm {Linear}}$ , we use random linear coding and show that in any feasible solution that the decoder finds, the messages of the honest nodes are decoded correctly. In order to prove the converse of the fundamental limit, we show that when the adversary behaves in a particular way, it can always confuse the decoder between two feasible solutions that differ in the message of at least one honest node. [ABSTRACT FROM AUTHOR]

Orthogonal/vector approximate message-passing (AMP) is a powerful message-passing (MP) algorithm for signal reconstruction in compressed sensing. This paper proves the convergence of Bayes-optimal orthogonal/vector AMP in the large system limit. The proof strategy is based on a novel long-memory (LM) MP approach: A first step is a construction of LM-MP that is guaranteed to converge systematically. A second step is a large-system analysis of LM-MP via an existing framework of state evolution. A third step is to prove the convergence of state evolution recursions for Bayes-optimal LM-MP via a new statistical interpretation of existing LM damping. The last is an exact reduction of the state evolution recursions for Bayes-optimal LM-MP to those for Bayes-optimal orthogonal/vector AMP. The convergence of the state evolution recursions for Bayes-optimal LM-MP implies that for Bayes-optimal orthogonal/vector AMP. Numerical simulations are presented to show the verification of state evolution results for damped orthogonal/vector AMP and a negative aspect of LM-MP in finite-sized systems. [ABSTRACT FROM AUTHOR]

Let $q\geq 2$ be a prime power. In this paper, we study the distribution of the minimum distance (in the Hamming metric) of a random linear code of dimension $k$ in $\mathbb {F}_{q}^{n}$. We provide quantitative estimates showing that the distribution function of the minimum distance is close (superpolynomially in $n$) to the cumulative distribution function of the minimum of $(q^{k}-1)/(q-1)$ independent binomial random variables with parameters $\frac {1}{q}$ and $n$. The latter, in turn, converges to a Gumbel distribution at integer points when $\frac {k}{n}$ converges to a fixed number in (0, 1). Our result confirms in a strong sense that apart from identification of the weights of proportional codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimum code weight. As a corollary of the main result, we obtain an improvement of the Gilbert–Varshamov bound for $2< q< 49$. [ABSTRACT FROM AUTHOR]

In this paper, we focus on decoding nonbinary low-density parity-check (LDPC) codes in Galois fields of characteristic two via the proximal alternating direction method of multipliers (proximal-ADMM). By exploiting Flanagan/Constant-Weighting embedding techniques and the decomposition technique based on three-variables parity-check equations, two efficient proximal-ADMM decoders for nonbinary LDPC codes are proposed. We show that both of them are theoretically guaranteed convergent to some stationary point of the decoding model and either of their computational complexities in each proximal-ADMM iteration scales linearly with LDPC code’s length and the size of the considered Galois field. Moreover, the decoder based on the Constant-Weight embedding technique satisfies the favorable property of codeword symmetry. Simulation results demonstrate their effectiveness in comparison with state-of-the-art LDPC decoders. [ABSTRACT FROM AUTHOR]

In this study, macroscopic properties of the vector approximate message passing (VAMP) algorithm for inference of generalized linear models are investigated using a non-rigorous heuristic method of statistical mechanics when the true posterior cannot be used and the measurement matrix is a sample from rotation-invariant random matrix ensembles. The focus is on the correspondence between the non-rigorous replica analysis of statistical mechanics and the performance assessment of VAMP in the model-mismatched setting. The correspondence of this kind is well-known when the measurement matrix has independent and identically distributed entries. However, when the measurement matrix follows a general rotation-invariant matrix ensemble, the correspondence has been validated only under limited cases, such as the Bayes optimal inference or the convex empirical risk minimization. The result presented in this paper is to extend the scope of such correspondence. Herein, we heuristically derive the explicit formula of state-evolution equations, which macroscopically describe VAMP dynamics for the current model-mismatched case, and show that their fixed point is generally consistent with the replica symmetric solution obtained by the replica method of statistical mechanics. We also show that the fixed point of VAMP can exhibit a microscopic instability, which indicates that message variables continue to move by VAMP while their macroscopically summarized quantities converge to fixed values. The critical condition the for microscopic instability agrees with that for breaking the replica symmetry that is derived within the non-rigorous replica analysis. The results of the numerical experiments cross-check our findings. [ABSTRACT FROM AUTHOR]

In real life we often deal with independent but not identically distributed observations (i.n.i.d.o), for which the most well-known statistical model is the multiple linear regression model (MLRM) with non-random covariates. While the classical methods are based on the maximum likelihood estimator (MLE), it is well known its lack of robustness to small deviations from the assumed conditions. In this paper, and based on the Rényi’s pseudodistance (RP), we introduce a new family of estimators in case our information about the unknown parameter is given for i.n.i.d.o.. This family of estimators, let us say minimum RP estimators (as they are obtained by minimizing the RP between the assumed distribution and the empirical distribution of the data), contains the MLE as a particular case and can be applied, among others, to the MLRM with non-random covariates. Based on these estimators, we introduce Wald-type tests for testing simple and composite null hypotheses, as an extension of the classical MLE-based Wald test. Influence functions for the estimators and Wald-type tests are also obtained and analysed. Finally, a simulation study is developed in order to asses the performance of the proposed methods and some real-life data are analysed for illustrative purpose. [ABSTRACT FROM AUTHOR]

The $k\text {-means}$ clustering problem concerns finding a partition of the data points into $k$ clusters such that the total within-cluster squared distance is minimized. This optimization objective is non-convex, and not everywhere differentiable. In general, there exist spurious local solutions other than the global optimum. Moreover, the simplest and most popular algorithm for $k\text {-means}$ , namely Lloyd’s algorithm, generally converges to such spurious local solutions both in theory and in practice. In this paper, we investigate the structures of these spurious local solutions under a probabilistic generative model with $k$ ground truth clusters. As soon as $k=3$ , spurious local minima provably exist, even for well-separated clusters. One such local minimum puts two centers at one true cluster, and the third center in the middle of the other two true clusters. We prove that this is essentially the only type of spurious local minima under a separation condition. In particular, any local minimum solution only involves a configuration that puts multiple centers at a true cluster, and one center in the middle of multiple true clusters. Our results pertain to the $k\text {-means}$ formulation for mixtures of Gaussians or bounded distributions, and hold in the over- and under-parametrization regimes where the number of centers in $k\text {-means}$ may not equal to the number of true clusters. Our theoretical results corroborate existing empirical observations and provide justification for popular heuristics for $k\text {-means}$ clustering. [ABSTRACT FROM AUTHOR]

For general memoryless systems, the existing information-theoretic solutions have a "single-letter" form. This reflects the fact that optimum performance can be approached by a random code (or a random binning scheme), generated using independent and identically distributed copies of some scalar distribution. Is that the form of the solution of any (information-theoretic) problem? In fact, some counter examples are known. The most famous one is the "two help one" problem: Körner and Marton showed that if we want to decode the modulo-two sum of two correlated binary sources from their independent encodings, then linear coding is better than random coding. In this paper we provide another counter example, the "doubly-dirty" multiple-access channel (MAC). Like the Körner-Marton problem, this is a multiterminal scenario where side information is distributed among several terminals; each transmitter knows part of the channel interference while the receiver only observes the channel output. We give an explicit solution for the capacity region of the binary doubly-dirty MAC, demonstrate how this region can be approached using a linear coding scheme, and prove that the "best known single-letter region" is strictly contained in it. We also state a conjecture regarding the capacity loss of single-letter characterization in the Gaussian case. [ABSTRACT FROM AUTHOR]

This paper focuses on the problem of separately modulating and jointly estimating two independent continuous-valued parameters sent over a Gaussian multiple-access channel (MAC) under the mean square error (MSE) criterion without bandwidth constraints. To this end, we first improve an existing lower bound on the MSE that is obtained using the parameter modulation-estimation techniques for the single-user additive white Gaussian noise (AWGN) channel. As for the main contribution of this paper, this improved modulation-estimation analysis is generalized to the model of the two-user Gaussian MAC. We present outer bounds to the achievable region in the plane of the MSE’s of the two user parameters, which provides a trade-off between the MSE’s, where we used zero-rate lower bounds on the error probability of Gaussian channels by Shannon and Polyanskiy et al. Numerical results showed that, the multi-user adaptation of the zero-rate lower bound by Polyanskiy et al. provides a tighter overall lower bound on the MSE pairs than the classical Shannon bound. In addition, we introduced upper bounds on the MSE exponents, namely, the exponential decay rates of these MSE’s in the asymptotic regime of long blocks that could make use of any bound on the error exponent of a single-user AWGN channel. The obtained results are numerically evaluated for three different bounds on the reliability function of the Gaussian channel. It is shown that the adaptation of the reliability function by Ashikhmin et al. to the MAC provides a significantly tighter characterization than Shannon’s sphere-packing bound and the divergence bound. [ABSTRACT FROM AUTHOR]

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]

In practical applications, such as direct spread code division multiple access communications, space-time codes and compressed sensing, and codebooks with small inner-product correlation are required. It is extremely difficult to construct codebooks achieving the Levenshtein bound. In this paper, two new constructions of infinitely many codebooks with multiplicative characters of finite fields are presented. These constructions produce complex codebooks asymptotically achieving the Levenshtein bound and codebooks asymptotically achieving the Welch bound. The codebooks presented in this paper have new parameters. [ABSTRACT FROM PUBLISHER]

In low-rank matrix recovery, one aims to reconstruct a low-rank matrix from a minimal number of linear measurements. Within the paradigm of compressed sensing, this is made computationally efficient by minimizing the nuclear norm as a convex surrogate for rank. In this paper, we identify an improved regularizer based on the so-called diamond norm, a concept imported from quantum information theory. We show that—for a class of matrices saturating a certain norm inequality—the descent cone of the diamond norm is contained in that of the nuclear norm. This suggests superior reconstruction properties for these matrices. We explicitly characterize this set of matrices. Moreover, we demonstrate numerically that the diamond norm indeed outperforms the nuclear norm in a number of relevant applications: These include signal analysis tasks, such as blind matrix deconvolution or the retrieval of certain unitary basis changes, as well as the quantum information problem of process tomography with random measurements. The diamond norm is defined for matrices that can be interpreted as order-4 tensors and it turns out that the above condition depends crucially on that tensorial structure. In this sense, this paper touches on an aspect of the notoriously difficult tensor completion problem. [ABSTRACT FROM PUBLISHER]

In this paper, we study the problem of learning a shallow artificial neural network that best fits a training data set. We study this problem in the over-parameterized regime where the numbers of observations are fewer than the number of parameters in the model. We show that with the quadratic activations, the optimization landscape of training, such shallow neural networks, has certain favorable characteristics that allow globally optimal models to be found efficiently using a variety of local search heuristics. This result holds for an arbitrary training data of input/output pairs. For differentiable activation functions, we also show that gradient descent, when suitably initialized, converges at a linear rate to a globally optimal model. This result focuses on a realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted weight coefficients. [ABSTRACT FROM AUTHOR]

This paper is mainly a semi-tutorial introduction to elementary algebraic topology and its applications to Ising-type models of statistical physics, using graphical models of linear and group codes. It contains new material on systematic $(n, k)$ group codes and their information sets; normal realizations of homology and cohomology spaces; dual and hybrid models; and connections with system-theoretic concepts, such as observability, controllability, and input/output realizations. [ABSTRACT FROM AUTHOR]

The problem of adaptive noisy clustering is investigated. Given a set of noisy observations \(Z_{i}=X_{i}+\epsilon _{i}\) , \(i=1, \ldots , n\) , the goal is to design clusters associated with the law of \(X_{i}\) ’s, with unknown density \(f\) with respect to the Lebesgue measure. Since we observe a corrupted sample, a direct approach as the popular \(k\) -means is not suitable in this case. In this paper, we propose a noisy \(k\) -means minimization, which is based on the \(k\) -means loss function and a deconvolution estimator of the density \(f\) . In particular, this approach suffers from the dependence on a bandwidth involved in the deconvolution kernel. Fast rates of convergence for the excess risk are proposed for a particular choice of the bandwidth, which depends on the smoothness of the density \(f\) . Then, we turn out into the main issue of this paper: the data-driven choice of the bandwidth. We state an adaptive upper bound using a modified version of Lespki’s method, called Empirical Risk Comparison, where empirical risks associated with different bandwidths are compared. Eventually, we illustrate that the selection rule can be used in many statistical problems of \(M\) -estimation where the empirical risk depends on a nuisance parameter. [ABSTRACT FROM PUBLISHER]

In this paper, the capacity region of the linear deterministic interference channel with noisy channel-output feedback (LD-IC-NF) is fully characterized. The proof of achievability is based on random coding arguments and rate splitting, block-Markov superposition coding, and backward decoding. The proof of the converse reuses some of the existing outer bounds and includes new ones obtained using genie-aided models. Following the insight gained from the analysis of the LD-IC-NF, an achievability region and a converse region for the two-user Gaussian interference channel with noisy channel-output feedback (G-IC-NF) are presented. Finally, the achievability region and the converse region are proven to approximate the capacity region of the G-IC-NF to within 4.4 bits. [ABSTRACT FROM AUTHOR]

The aim of this paper is to give an interpretation of the linear or nonlinear filtration problem as a quantization problem. Based on this, we extend the optimal filtering equation known from the Stratonovich filtering theory on the quantum process case. In contrast to the Kalman filter often used in such problems, the Stratonovich equation provides the optimal solution for nonlinear observation models. The observation model is based on an indirect measurement method, where the measurement is performed on an ancilla system that is interacted with an unknown one. The latter model is interpreted in case of a single-qudit system. Since the measured random variables and experiment are fundamentally different from each other, the obtained single-qudit observation model has a substantially different physical nature from the two-qubit one. However, in both problems, the Stratonovich optimal filter equation is equally applicable. [ABSTRACT FROM AUTHOR]

We propose a structure of a semiparametric two-component mixture model when one component is parametric and the other is defined through linear constraints on either its distribution function or its quantile measure. Estimation of a two-component mixture model with an unknown component is very difficult when no particular assumption is made on the structure of the unknown component. A symmetry assumption was used in the literature to simplify the estimation. Such method has the advantage of producing consistent and asymptotically normal estimators, and identifiability of the semiparametric mixture model becomes tractable. Still, existing methods, which estimate a semiparametric mixture model have their limits when the parametric component has unknown parameters or the proportion of the parametric part is either very high or very low. We propose in this paper a method to incorporate a prior linear information about the unknown component in order to better estimate the model when existing estimation methods fail. This linear information is either translated by linear constraints, such as moment-type constraints or L-moments constraints (linear constraints over the quantile). The new method is based on $\varphi -$ divergences and has a non classical form since the minimization is carried over both arguments of the divergence. The resulting estimators are proved to be consistent and asymptotically normal under standard assumptions. We show that using the Pearson’s \chi ^{2} divergence our algorithm has a linear complexity when the constraints are moment-type. Simulations on univariate and multivariate mixtures demonstrate the viability and the interest of our novel approach. [ABSTRACT FROM AUTHOR]

Minimum storage regenerating codes have minimum storage of data in each node and therefore are maximal distance separable (for short) codes. Thus, the number of nodes is upper-bounded by 2^ \mathfrak b , where \mathfrak b is the bits of data stored in each node. From both theoretical and practical points of view (see the details in Section 1), it is natural to consider regenerating codes that nearly have minimum storage of data, and meanwhile, the number of nodes is unbounded. One of the candidates for such regenerating codes is an algebraic geometry code. In this paper, we generalize the repairing algorithm of Reed–Solomon codes given by Guruswami and Wotters to algebraic geometry codes and present a repairing algorithm for arbitrary one-point algebraic geometry codes. By applying our repairing algorithm to the one-point algebraic geometry codes based on the Garcia–Stichtenoth tower, one can repair a code of rate 1- \varepsilon and length n over \mathbb Fq with bandwidth (n-1)(1- \tau)\log q for any \varepsilon =2^(\tau -1/2)\log q with a real $\tau \in (0,1/2)$ . In addition, storage in each node for an algebraic geometry code is close to the minimum storage. Due to nice structures of Hermitian curves, repairing of Hermitian codes is also investigated. As a result, we are able to show that algebraic geometry codes are regenerating codes with good parameters. [ABSTRACT FROM AUTHOR]

In this paper, we show that the conditional expectation operators corresponding to a family of source-channel models, defined by natural exponential families with quadratic variance functions and their conjugate priors, have orthonormal polynomials as singular vectors. These models include the Gaussian channel with Gaussian source, the Poisson channel with gamma source, and the binomial channel with beta source. To derive the singular vectors of these models, we prove and employ the equivalent condition that their conditional moments are strictly degree preserving polynomials. [ABSTRACT FROM AUTHOR]

The existence of almost perfect nonlinear (APN) permutations operating on an even number of variables was a long-standing open problem, until an example with six variables was exhibited by Dillon et al. in 2009. However it is still unknown whether this example can be generalized to any even number of inputs. In a recent work, Perrin et al. described an infinite family of permutations, named butterflies, operating on $(4k+2)$ variables and with differential uniformity at most 4, which contains the Dillon APN permutation. In this paper, we generalize this family, and we completely solve the two open problems raised by Perrin et al. Indeed we prove that all functions in this larger family have the best known nonlinearity. We also show that this family does not contain any APN permutation besides the Dillon permutation, implying that all other functions have differential uniformity exactly four. [ABSTRACT FROM PUBLISHER]

Noisy channels are a powerful resource for cryptography as they can be used to obtain information-theoretic secure key agreement, commitment, and oblivious transfer protocols, among others. Oblivious transfer (OT) is a fundamental primitive, since it is complete for secure multi-party computation, and the OT capacity characterizes how efficiently a channel can be used for obtaining string oblivious transfer. Ahlswede and Csiszár (ISIT’07) presented upper and lower bounds on the OT capacity of generalized erasure channels (GECs) against passive adversaries. In the case of GEC with erasure probability at least 1/2, the upper and lower bounds match and, therefore, the OT capacity was determined. It was later proved by Pinto et al. [IEEE Trans. Inf. Theory 57(8)] that the OT capacity is identical for passive and malicious adversaries. In the case of GEC with erasure probability smaller than 1/2, the known lower bound against passive adversaries that was established by Ahlswede and Csiszár does not match their upper bound and it was unknown whether this OT rate could be achieved against malicious adversaries as well. In this paper, we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries. We obtain our results by a new combination of interactive hashing and typicality tests that are suitable for dealing with the case of low erasure probability ( p^* <1/2 ). [ABSTRACT FROM PUBLISHER]

The majority of the human genome consists of repeated sequences. An important type of repeated sequences common in the human genome are tandem repeats, where identical copies appear next to each other. For example, in the sequence AGTC\underline TGTGC , $TGTG$ is a tandem repeat, that may be generated from $AGTCTGC$ by a tandem duplication of length 2. In this paper, we investigate the possibility of generating a large number of sequences from a seed, i.e. a small initial string, by tandem duplications of bounded length. We study the capacity of such a system, a notion that quantifies the system’s generating power. Our results include exact capacity values for certain tandem duplication string systems. In addition, motivated by the role of DNA sequences in expressing proteins via RNA and the genetic code, we define the notion of the expressiveness of a tandem duplication system as the capability of expressing arbitrary substrings. We then completely characterize the expressiveness of tandem duplication systems for general alphabet sizes and duplication lengths. In particular, based on a celebrated result by Axel Thue from 1906, presenting a construction for ternary squarefree sequences, we show that for alphabets of size 4 or larger, bounded tandem duplication systems, regardless of the seed and the bound on duplication length, are not fully expressive, i.e. they cannot generate all strings even as substrings of other strings. Note that the alphabet of size 4 is of particular interest as it pertains to the genomic alphabet. Building on this result, we also show that these systems do not have full capacity. In general, our results illustrate that duplication lengths play a more significant role than the seed in generating a large number of sequences for these systems. [ABSTRACT FROM PUBLISHER]

In order to gain new insights into multiple-input–multiple-output (MIMO) interference networks, the optimality of \sum k=1^{K} Mk/2 (half the cake per user) degrees of freedom is explored for a K -user MIMO interference channel where the cross-channels have arbitrary rank constraints, and the k th transmitter and receiver are equipped with Mk antennas each. The result consolidates and significantly generalizes results from prior studies by Krishnamurthy et al., of rank-deficient interference channels where all users have M antennas; and by Tang et al., of full rank interference channels where the $k$ th user pair has M_{k} antennas. The broader outcome of this paper is a novel class of replication-based outer bounds for arbitrary rank-constrained MIMO interference networks where replicas of existing users are added as auxiliary users and the network connectivity is chosen to ensure that any achievable scheme for the original network also works in the new network. The replicated network creates a new perspective of the problem, so that even simple arguments such as user cooperation become quite powerful when applied in the replicated network, giving rise to stronger outer bounds, than when applied directly in the original network. Remarkably, the replication-based bounds are broadly applicable not only to MIMO interference channels with arbitrary rank-constraints, but much more broadly, even beyond Gaussian settings. [ABSTRACT FROM PUBLISHER]

The capacity region of the $K$ -user Gaussian interference channel (GIC) is a long-standing open problem and even capacity outer bounds are little known in general. A significant progress on degrees-of-freedom (DoF) analysis, a first-order capacity approximation, for the $K$ -user GIC has provided new important insights into the problem of interest in the high signal-to-noise ratio (SNR) limit. However, such capacity approximation has been observed to have some limitations in predicting the capacity at finite SNR. In this paper, we develop a new upper-bounding technique that utilizes a new type of genie signal and applies time sharing to genie signals at $K$ receivers. Based on this technique, we derive new upper bounds on the sum capacity of the three-user GIC with constant, complex channel coefficients and then generalize to the $K$ -user case to better understand sum-rate behavior at finite SNR. We also provide closed-form expressions of our upper bounds on the capacity of the $K$ -user symmetric GIC easily computable for any $K$ . From the perspectives of our results, some sum-rate behavior at finite SNR is in line with the insights given by the known DoF results, while some others are not. In particular, the well-known $K/2$ DoF achievable for almost all constant real channel coefficients turns out to be not embodied as a substantial performance gain over a certain range of the cross-channel coefficient in the $K$ -user symmetric real case especially for large $K$ . We further investigate the impact of phase offset between the direct-channel coefficient and the cross-channel coefficients on the sum-rate upper bound for the three-user complex GIC. As a consequence, we aim to provide new findings that could not be predicted by the prior works on DoF of GICs. [ABSTRACT FROM PUBLISHER]

As a class of optimal combinatorial objects, bent functions have important applications in cryptography, sequence design, and coding theory. Bent idempotents are a subclass of bent functions and of great interest, since they can be stored in less space and allow faster computation of the Walsh-Hadamard transform. The objective of this paper is to present a generic construction of bent functions from known ones. It includes the previous constructions of bent functions by Mesnager and Xu et al. as special cases, and produces new bent functions, which cannot be produced by earlier ones. In particular, it also generates infinite families of bent idempotents over F2^{2m} of any algebraic degree between 2 and $m$ . This together with a recent construction by Su and Tang gives a positive answer to an open problem on bent idempotents proposed by Carlet. In addition, an infinite family of anti-self-dual bent functions is obtained in which the sum of any three distinct functions is again an anti-self-dual bent function in this family. This solves an open problem recently proposed by Mesnager. [ABSTRACT FROM PUBLISHER]

Plateaued functions are very important crypto- graphic functions due to their various desirable cryptographic characteristics. We point out that plateaued functions are more general than bent functions (that is, functions with maximum nonlinearity). Some Boolean plateaued functions have large nonlinearity, which provides protection against fast correlation attacks when they are used as combiners or filters in stream ciphers, and contributes, when they are the component functions of the substitution boxes in block ciphers, to protection against linear cryptanalysis. P-ary plateaued functions have attracted recently some attention in the literature, and many activities on generalized $p$ -ary functions have been carried out. This paper increases our knowledge on plateaued functions in the general context of generalized p$ -ary functions. We first introduce two new versions of plateaued functions, which we shall call generalized plateaued functions and admissible plateaued functions. The generalized plateaued functions extend the standard notion of plateaued p$ -ary functions to those whose outputs are in the ring . Next, we study the generalized plateaued functions and use admissible plateaued functions to characterize the generalized plateaued functions by means of their components. Finally, we provide for the first time two constructions of generalized plateaued functions. In particular, we generalize a known secondary construction of binary generalized bent functions and derive constructions of binary generalized plateaued functions with different amplitudes. [ABSTRACT FROM PUBLISHER]

The nonlinear complexity of a periodic sequence s is the length of the shortest feedback shift register that can generate s, and its value is upper bounded by the least period of s minus 1. In this paper, a recursive approach that generates all periodic sequences with maximum nonlinear complexity is presented, and the total number of such sequences is determined. The randomness properties of these sequences are also examined. [ABSTRACT FROM PUBLISHER]

The problem of one-way file synchronization, henceforth called “file updates”, is studied in this paper. Specifically, a client edits a file, where the edits are modeled by insertions and deletions (InDels). An old copy of the file is stored remotely at a data-centre, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the data-centre to update its old copy to the newly edited file. Two models for the source files and edit patterns are studied: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime, in which the number of insertions and deletions is a small (but constant) fraction of the length of the original file. For both models, information-theoretic lower bounds on the best possible compression rates that enable file updates are derived (up to first order terms). Conversely, a simple compression algorithm using dynamic programming (DP) and entropy coding (EC), henceforth called DP-EC algorithm, achieves rates that are within constant additive gap (which diminishes as the alphabet size increases) to information-theoretic lower bounds for both models. For the RPES-LtRRID model, a dynamic-programming-run-length-compression (DP-RLC) algorithm is proposed, which achieves a compression rate matching the information-theoretic lower bound up to first order terms. Therefore, when the insertion and deletion probabilities are small (such that first order terms dominate), the achievable rate by DP-RLC is nearly optimal for the RPES-LtRRID model. [ABSTRACT FROM PUBLISHER]

In this paper, we analyze the sum-rate capacity of two-user Poisson multiple access channels (MAC), when the receiver is equipped with single antenna. We first characterize the sum-rate capacity of the non-symmetric Poisson MAC when each transmitter has a single antenna. While the sum-rate capacity of the symmetric Poisson MAC with single antenna at each transmitter has been characterized in the literature, the special property exploited in the existing method for the symmetric case does not hold for the non-symmetric channel anymore. We obtain the optimal input that achieves the sum-rate capacity by solving a non-convex optimization problem. We show that, for certain channel parameters, it is optimal for a single user to transmit to achieve the sum-rate capacity. This is in sharp contrast to the Gaussian MAC, in which both users must transmit, either simultaneously or at different times, in order to achieve the sum-rate capacity. We then characterize the sum-rate capacity of the Poisson multiple-input single-output (MISO) MAC with multiple antennas at each transmitter and single antenna at the receiver. By converting a non-convex optimization problem with a large number of variables into a non-convex optimization problem with two variables, we show that the sum-rate capacity of the Poisson MISO MAC with multiple transmit antennas is equivalent to a properly constructed Poisson MAC with a single antenna at each transmitter. [ABSTRACT FROM PUBLISHER]

Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an [n,k,d] - (\alpha ) MSR code \mathbb C over \smash \mathbb F\!q stores a file \mathcal F consisting of \alpha k symbols over \smash {\mathbb {F}_{\!q}} among n$ nodes, each storing \alpha $ symbols, in such a way that: 1) the file k$ of the n$ nodes and 2) the content of any failed node can be reconstructed by accessing any d$ of the remaining symbols from each of these nodes. In practice, the file \mathcal F is typically available in uncoded form on some $k$ of the $n$ nodes, known as systematic nodes, and the defining node-repair condition above can be relaxed to requiring the optimal repair bandwidth for systematic nodes only. Such codes are called systematic–repair MSR codes. Unfortunately, finite– $\alpha $ constructions of $[n,k,d]$ MSR codes are known only for certain special cases: either low rate, namely $k/n \leqslant 0.5$ , or high repair connectivity, namely $d = n-1$ . Our main result in this paper is a finite– $\alpha $ construction of systematic-repair $[n,k,d]$ MSR codes for all possible values of parameters $n,k,d$ . We also introduce a generalized construction for $[n,k]$ MSR codes to achieve the optimal repair bandwidth for all values of $d$ simultaneously. [ABSTRACT FROM PUBLISHER]

We consider the problem of detecting abrupt parameter changes in a stochastic regression with unknown noise distribution. The process changes at some unknown point of time. Under general conditions on the regression function and unknown distributions of observations before and after the disruption, the paper develops a nonparametric cumulative sum procedure (CUSUM). Unlike likelihood-based CUSUM algorithms, constructed mostly on log-likelihood ratio statistics, we use a special system of basic statistics in Page’s procedure. By applying a sequential sampling scheme, which measures time in terms of accumulated Kullback–Leibler (K-L) divergence, we come to a system of statistics with the martingale properties close to those of the log-likelihood ratios. The proposed approach suggests also an alternative performance criterion in the analysis of the procedure by replacing the expected detection delay by the corresponding K-L divergence. We show that, under the false alarm probability constraint, the nonparametric CUSUM rule is optimal in the sense that it ensures the logarithmic asymptotic for the detection delay. [ABSTRACT FROM AUTHOR]

Detection of sparse signals arises in a wide range of modern scientific studies. The focus so far has been mainly on Gaussian mixture models. In this paper, we consider the detection problem under a general sparse mixture model and obtain explicit expressions for the detection boundary under mild regularity conditions. In addition, for Gaussian null hypothesis, we establish the adaptive optimality of the higher criticism procedure for all sparse mixtures satisfying the same conditions. In particular, the general results obtained in this paper recover and extend in a unified manner the previously known results on sparse detection far beyond the conventional Gaussian model and other exponential families. [ABSTRACT FROM PUBLISHER]

In this paper, we derive explicit expressions for the capacity region of the two-user symbol-asynchronous Gaussian vector multiple-access channel. Verdú considered the case where each user linearly modulates a fixed waveform in each symbol period, where the symbol periods for the users are not perfectly aligned at the receiver. He derived explicit capacity region expressions for the case where the transmitters have knowledge of the mutual offset and also for the case where the transmitters have no knowledge of the mutual offset. In this paper, we extend Verdú's results to allow each user to linearly modulate a set of orthonormal waveforms, instead of a single waveform, in each symbol period and with no restrictions imposed on the waveforms. We consider group power constraints, which include individual sum power constraints, as orthonormal waveforms assigned to each user may come from different frequency bands with different power constraints. Similar to the case where each user is allowed to linearly modulate only a single waveform, our results hold regardless of whether or not the transmitters are frame synchronous. In addition, we present some results that are necessary to numerically compute the capacity region expressions with general purpose convex optimization algorithms. Next, we simplify the capacity region expression when there are only individual sum power constraints and when the transmitters know the mutual offset. We also prove a sufficient condition for a similar simplification to hold when the transmitters have no knowledge of the mutual offset. Finally, we consider a specialized algorithm to numerically compute the simplified capacity region expression when the transmitters know the mutual offset. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of determining the weight spectrum of q-ary codes C(3,m) associated with Grassmann varieties G(3,m). For m=6, this was done in a paper by Nogin in 1997. We derive a formula for the weight of a codeword of C(3,m), in terms of certain varieties associated with alternating trilinear forms on \BBFq^{m}. The classification of such forms under the action of the general linear group GL(m, \BBFq) is the other component that is required to calculate the spectrum of C(3,m). For m=7, we explicitly determine the varieties mentioned above. The classification problem for alternating three-forms on \BBFq^{7} was solved in a study by Cohen and Helminck in 1988, which we then use to determine the spectrum of C(3,7). [ABSTRACT FROM AUTHOR]

Sparse superposition codes were recently introduced by Barron and Joseph for reliable communication over the additive white Gaussian noise (AWGN) channel at rates approaching the channel capacity. The codebook is defined in terms of a Gaussian design matrix, and codewords are sparse linear combinations of columns of the matrix. In this paper, we propose an approximate message passing decoder for sparse superposition codes, whose decoding complexity scales linearly with the size of the design matrix. The performance of the decoder is rigorously analyzed and it is shown to asymptotically achieve the AWGN capacity with an appropriate power allocation. Simulation results are provided to demonstrate the performance of the decoder at finite blocklengths. We introduce a power allocation scheme to improve the empirical performance, and demonstrate how the decoding complexity can be significantly reduced by using Hadamard design matrices. [ABSTRACT FROM PUBLISHER]

Both Maximum Distance Separable and Euclidean self-dual codes have theoretical and practical importance and the study of MDS self-dual codes has attracted lots of attention in recent years. In particular, determining the existence of q -ary MDS self-dual codes for various lengths has been investigated extensively. The problem is completely solved for the case where q is even. This paper focuses on the case where q is odd. We construct a few classes of new MDS self-dual codes through generalized Reed–Solomon codes. More precisely, we show that for any given even length n , we have a q and q is sufficiently large (say q\ge 4^{n}\times n^{2}) . Furthermore, we prove that there exists a q -ary MDS self-dual code of length n if q=r^{2} and n$ satisfies one of the three conditions: 1) n\le r$ and n$ is even; 2) q$ is odd and n-1$ is an odd divisor of and $n=2tr$ for any $t\le (r-1)/2$ . [ABSTRACT FROM PUBLISHER]

We consider three channel models: the wiretap channel with M helpers, the K -user multiple access wiretap channel, and the K -user interference channel with an external eavesdropper, when no eavesdropper’s channel state information (CSI) is available at the transmitters. In each case, we establish the optimal sum secure degrees of freedom (s.d.o.f.) by providing achievable schemes and matching converses. We show that the unavailability of the eavesdropper’s channel state information at the transmitter (CSIT) does not reduce the s.d.o.f. of the wiretap channel with helpers. However, there is loss in s.d.o.f. for both the multiple access wiretap channel and the interference channel with an external eavesdropper. In particular, we show that in the absence of eavesdropper’s CSIT, the K -user multiple access wiretap channel reduces to a wiretap channel with (K-1) to \frac K-1K . For the interference channel with an external eavesdropper, the optimal sum s.d.o.f. decreases from \frac K(K-1)2K-1 to \frac K-12 in the absence of the eavesdropper’s CSIT. Our results show that the lack of eavesdropper’s CSIT does not have a significant impact on the optimal s.d.o.f. for any of the three channel models, especially when the number of users is large. This implies that physical layer security can be made robust to the unavailability of eavesdropper CSIT at high signal-to-noise ratio regimes by the careful modification of the achievable schemes as demonstrated in this paper. [ABSTRACT FROM PUBLISHER]

In this paper, we analyze a collaborative filter that answers the simple question: What is popular amongst your “friends”? While this basic principle seems to be prevalent in many practical implementations, there does not appear to be much theoretical analysis of its performance. In this paper, we partly fill this gap. While recent works on this topic, such as the low-rank matrix completion literature, consider the probability of error in recovering the entire rating matrix, we consider probability of an error in an individual recommendation [bit error rate (BER)]. For a mathematical model introduced by Aditya in 2009 and 2011, we identify three regimes of operation for our algorithm (named Popularity Amongst Friends) in the limit as the matrix size grows to infinity. In a regime characterized by large number of samples and small degrees of freedom (defined precisely for the model in the paper), the asymptotic BER is zero; in a regime characterized by large number of samples and large degrees of freedom, the asymptotic BER is bounded away from 0 and 1/2 (and is identified exactly except for a special case); and in a regime characterized by a small number of samples, the algorithm fails. We then compare these results with the performance of the optimal recommender. We also present numerical results for the MovieLens and Netflix datasets. We discuss the empirical performance in light of our theoretical results and compare with an approach based on low-rank matrix completion. [ABSTRACT FROM AUTHOR]

This paper proposes a general adaptive procedure for budget-limited predictor design in high dimensions called two-stage Sampling, Prediction and Adaptive Regression via Correlation Screening (SPARCS). The SPARCS can be applied to high-dimensional prediction problems in experimental science, medicine, finance, and engineering, as illustrated by the following. Suppose that one wishes to run a sequence of experiments to learn a sparse multivariate predictor of a dependent variable Y (disease prognosis for instance) based on a p dimensional set of independent variables \mathrm X=[X1,\ldots , Xp]^{T} (assayed biomarkers). Assume that the cost of acquiring the full set of variables X increases linearly in its dimension. The SPARCS breaks the data collection into two stages in order to achieve an optimal tradeoff between sampling cost and predictor performance. In the first stage, we collect a few ( n ) expensive samples \yi, {\mathrm {x}i\}i=1^{n} , at the full dimension $p\gg n$ of X, winnowing the number of variables down to a smaller dimension $l < p$ using a type of cross correlation or regression coefficient screening. In the second stage, we collect a larger number $(t-n)$ of cheaper samples of the $l$ variables that passed the screening of the first stage. At the second stage, a low-dimensional predictor is constructed by solving the standard regression problem using all $t$ samples of the selected variables. The SPARCS is an adaptive online algorithm that implements false positive control on the selected variables, is well suited to small sample sizes, and is scalable to high dimensions. We establish asymptotic bounds for the familywise error rate, specify high dimensional convergence rates for support recovery, and establish optimal sample allocation rules to the first and second stages. [ABSTRACT FROM PUBLISHER]

Is it possible to find the sparsest vector (direction) in a generic subspace \mathcal S \subseteq \mathbb R ^p with \text dim \left ( \mathcal S \right )=n < p ? This problem can be considered a homogeneous variant of the sparse recovery problem and finds connections to sparse dictionary learning, sparse PCA, and many other problems in signal processing and machine learning. In this paper, we focus on a planted sparse model for the subspace: the target sparse vector is embedded in an otherwise random subspace. Simple convex heuristics for this planted recovery problem provably break down when the fraction of nonzero entries in the target sparse vector substantially exceeds O(1/\sqrt n) . In contrast, we exhibit a relatively simple nonconvex approach based on alternating directions, which provably succeeds even when the fraction of nonzero entries is $\Omega (1)$ . To the best of our knowledge, this is the first practical algorithm to achieve linear scaling under the planted sparse model. Empirically, our proposed algorithm also succeeds in more challenging data models, e.g., sparse dictionary learning. [ABSTRACT FROM AUTHOR]

The auxiliary function of a classical channel appears in two fundamental quantities, the random coding exponent and the sphere-packing exponent, which yield upper and lower bounds on the error probability of decoding, respectively. A crucial property of the auxiliary function is its concavity, and this property consequently leads to several important results in finite blocklength analysis. In this paper, we prove that the auxiliary function of a classical-quantum channel also enjoys the same concavity property, extending an earlier partial result to its full generality. We also prove that the auxiliary function satisfies the data-processing inequality, among various other important properties. Furthermore, we show that the concavity property of the auxiliary function enables a geometric interpretation of the random coding exponent and the sphere-packing exponent of a classical-quantum channel. The key component in our proof is an important result from the theory of matrix geometric means. [ABSTRACT FROM AUTHOR]

Unveiling a fundamental link between information theory and estimation theory, the I-MMSE relationship by Guo et al., together with its numerous extensions, has great theoretical significance and various practical applications. On the other hand, its influences to date have been restricted to channels without feedback or memory, due to the absence of its extensions to such channels. In this paper, we propose the extensions of the I-MMSE relationship to discrete-time and continuous-time Gaussian channels with feedback and/or memory. Our approach is based on a very simple observation, which can be applied to other scenarios, such as a simple and direct proof of the classical de Bruijn’s identity. [ABSTRACT FROM AUTHOR]

This paper considers a linear quasi-cyclic product code of two given quasi-cyclic codes of relatively prime lengths over finite fields. We give the spectral analysis of a quasi-cyclic product code in terms of the spectral analysis of the row and column codes. Moreover, we provide a new lower bound on the minimum Hamming distance of a given quasi-cyclic code and present a new algebraic decoding algorithm. More specifically, we prove an explicit (unreduced) basis of an \ell A {\ell B} -quasi-cyclic product code in terms of the generator matrix in reduced Gröbner basis with respect to the position-over-term (RGB/POT) order form of the \ell A -quasi-cyclic row code and the \ell B -quasi-cyclic column code, respectively. This generalizes the work of Burton and Weldon for the generator polynomial of a cyclic product code (where \ell A= {\ell B}=1 ). Furthermore, we derive the generator matrix in Pre-RGB/POT form of an \ell A {\ell B} -quasi-cyclic product code for two special cases: i) for \ell A=2 and \ell B=1 and ii) if the row code is a one-level \ell A -quasi-cyclic code (for arbitrary \ell A ) and \ell B=1 . For arbitrary \ell A and \ell B , the Pre-RGB/POT form of the generator matrix of an \ell A {\ell B} -quasi-cyclic product code is conjectured. The spectral analysis is applied to the generator matrix of the product of an \ell -quasi-cyclic and a cyclic code, and we propose a new lower bound on the minimum Hamming distance of a given \ell -quasi-cyclic code. In addition, we develop an efficient syndrome-based decoding algorithm for \ell -phased burst errors with guaranteed decoding radius. [ABSTRACT FROM AUTHOR]

The aim of this paper is to show that spatial coupling can be viewed not only as a means to build better graphical models, but also as a tool to better understand uncoupled models. The starting point is the observation that some asymptotic properties of graphical models are easier to prove in the case of spatial coupling. In such cases, one can then use the so-called interpolation method to transfer known results for the spatially coupled case to the uncoupled one. Our main use of this framework is for Low-density parity check (LDPC) codes, where we use interpolation to show that the average entropy of the codeword conditioned on the observation is asymptotically the same for spatially coupled as for uncoupled ensembles. We give three applications of this result for a large class of LDPC ensembles. The first one is a proof of the so-called Maxwell construction stating that the MAP threshold is equal to the area threshold of the BP GEXIT curve. The second is a proof of the equality between the BP and MAP GEXIT curves above the MAP threshold. The third application is the intimately related fact that the replica symmetric formula for the conditional entropy in the infinite block length limit is exact. [ABSTRACT FROM AUTHOR]

Following the seminal work by Zheng and Tse on the diversity and multiplexing tradeoff (DMT) of multiple-input multiple-output (MIMO) channels, in this paper, we introduce the array gain to investigate the fundamental relation between transmission rate and reliability in MIMO systems. The array gain gives information on the power offset that results from exploiting channel state information at the transmitter or as a consequence of the channel model. Hence, the diversity, multiplexing, and array gain (DMA) analysis is able to cope with the limitations of the original DMT and provide an operational meaning in the sense that the DMA gains of a particular system can be directly translated into a parameterized characterization of its associated outage probability performance. In this paper, we derive the best DMA gains achievable by any scheme employing isotropic signaling in uncorrelated Rayleigh, semicorrelated Rayleigh, and uncorrelated Rician block-fading MIMO channels. We use these results to analyze the effect of important channel parameters on the outage performance at different points of the DMT curve. [ABSTRACT FROM PUBLISHER]

This paper focuses on the stationary portion of file download in an unstructured peer-to-peer network, which typically follows for many hours after a flash crowd initiation. The model includes the case that peers can have some pieces at the time of arrival. The contribution of this paper is to identify how much help is needed from the seeds, either fixed seeds or peer seeds (which are peers remaining in the system after obtaining a complete collection), to stabilize the system. The dominant cause for instability is the missing piece syndrome, whereby one piece becomes very rare in the network. It is shown that stability can be achieved with only a small amount of help from peer seeds—even with very little help from a fixed seed, peers need dwell as peer seeds on average only long enough to upload one additional piece. The region of stability is insensitive to the piece selection policy. Network coding can substantially increase the region of stability in case a portion of the new peers arrive with randomly coded pieces. [ABSTRACT FROM PUBLISHER]

In this paper, we consider molecular communication, with information conveyed in the time of release of molecules. These molecules propagate to the transmitter through a fluid medium, propelled by a positive drift velocity and Brownian motion. The main contribution of this paper is the development of a theoretical foundation for such a communication system; specifically, the additive inverse Gaussian noise (AIGN) channel model. In such a channel, the information is corrupted by noise that follows an IG distribution. We show that such a channel model is appropriate for molecular communication in fluid media. Taking advantage of the available literature on the IG distribution, upper and lower bounds on channel capacity are developed, and a maximum likelihood receiver is derived. Results are presented which suggest that this channel does not have a single quality measure analogous to signal-to-noise ratio in the additive white Gaussian noise channel. It is also shown that the use of multiple molecules leads to reduced error rate in a manner akin to diversity order in wireless communications. Finally, some open problems are discussed that arise from the IG channel model. [ABSTRACT FROM PUBLISHER]