Search

Consider several source nodes communicating across a wireless network to a destination node with the help of several layers of relay nodes. Recent work by Avestimehr has approximated the capacity of this network up to an additive gap. The communication scheme achieving this capacity approximation is based on compress-and-forward, resulting in noise accumulation as the messages traverse the network. As a consequence, the approximation gap increases linearly with the network depth. This paper develops a computation alignment strategy that can approach the capacity of a class of layered, time-varying wireless relay networks up to an approximation gap that is independent of the network depth. This strategy is based on the compute-and-forward framework, which enables relays to decode deterministic functions of the transmitted messages. Alone, compute-and-forward is insufficient to approach the capacity as it incurs a penalty for approximating the wireless channel with complex-valued coefficients by a channel with integer coefficients. Here, this penalty is circumvented by carefully matching channel realizations across time slots to create integer-valued effective channels that are well suited to compute-and-forward. Unlike prior constant gap results, the approximation gap obtained in this paper also depends closely on the fading statistics, which are assumed to be i.i.d. Rayleigh. [ABSTRACT FROM PUBLISHER]

The main goal in group testing is to recover a small subset of defective items from a larger population while efficiently reducing the total number of (possibly noisy) required tests/measurements. Under the assumption that the input-output statistical relationship (i.e., channel law) is known to the recovery algorithm, the fundamental as well as the computational limits of the group testing problem are relatively better understood than when these statistical relationships are unknown. Practical considerations, however, render this assumption inapplicable, and “blind” recovery/estimation procedures, independent of the input-output statistics, are desired. In this paper, we analyze the fundamental limits of a general noisy group testing problem, when this relationship is unknown. Specifically, in the first part of this paper, we propose an efficient scheme, based on the idea of separate-decoding of items (where each item is recovered separately), for which we derive sufficient conditions on the number of tests required for exact recovery. The difficulty in obtaining these conditions stems from the fact that we allow the number of defective items to grow with the population size, which in turn requires delicate concentration analysis of certain probabilities. Furthermore, we show that in several scenarios, our proposed scheme achieves the same performance as that of the corresponding non-blind recovery algorithm (where the input-output statistics are known), implying that the proposed blind scheme is robust/universal. Finally, in the second part of this paper, we propose also an inefficient combinatorial-based scheme (or, “joint-decoding”), for which we derive similar sufficient conditions. [ABSTRACT FROM AUTHOR]

In this paper, we consider the cluster estimation problem under the stochastic block model. We show that the semidefinite programming (SDP) formulation for this problem achieves an error rate that decays exponentially in the signal-to-noise ratio. The error bound implies weak recovery in the sparse graph regime with bounded expected degrees as well as exact recovery in the dense regime. An immediate corollary of our results yields error bounds under the censored block model. Moreover, these error bounds are robust, continuing to hold under heterogeneous edge probabilities and a form of the so-called monotone attack. Significantly, this error rate is achieved by the SDP solution itself without any further pre- or post-processing and improves upon existing polynomially decaying error bounds proved using the Grothendieck’s inequality. Our analysis builds on two key ingredients: 1) showing that the graph has a well-behaved spectrum, even in the sparse regime, after discounting an exponentially small number of edges and 2) an order-statistics argument that governs the final error rate. Both arguments highlight the implicit regularization effect of the SDP formulation. [ABSTRACT FROM AUTHOR]

There are various parametric models for analyzing pairwise comparison data, including the Bradley–Terry–Luce (BTL) and Thurstone models, but their reliance on strong parametric assumptions is limiting. In this paper, we study a flexible model for pairwise comparisons, under which the probabilities of outcomes are required only to satisfy a natural form of stochastic transitivity. This class includes parametric models, including the BTL and Thurstone models as special cases, but is considerably more general. We provide various examples of models in this broader stochastically transitive class for which classical parametric models provide poor fits. Despite this greater flexibility, we show that the matrix of probabilities can be estimated at the same rate as in standard parametric models up to logarithmic terms. On the other hand, unlike in the BTL and Thurstone models, computing the minimax-optimal estimator in the stochastically transitive model is non-trivial, and we explore various computationally tractable alternatives. We show that a simple singular value thresholding algorithm is statistically consistent but does not achieve the minimax rate. We then propose and study algorithms that achieve the minimax rate over interesting sub-classes of the full stochastically transitive class. We complement our theoretical results with thorough numerical simulations. [ABSTRACT FROM AUTHOR]

The goal of this paper is to investigate linear approximations of random functions and permutations. Our motivation is twofold. First, before the distinguishability of a practical cipher from an ideal one can be analysed, the cryptanalyst must have an accurate understanding of the statistical behaviour of the ideal cipher. Secondly, this issue has been neglected both in old and in more recent studies, particularly when multiple linear approximations are being used simultaneously. Traditional models have been based on the average behaviour and simplified using other assumptions such as independence of the linear approximations. Multidimensional cryptanalysis was introduced to avoid making artificial assumptions about statistical independence of linear approximations. On the other hand, it has the drawback of including many trivial approximations that do not contribute to the attack but just cause a waste of time and memory. We show for the first time in this paper that the trivial approximations reduce the degree of freedom of the related $\chi ^{2}$ distribution. Previously, the affine linear cryptanalysis was proposed to allow removing trivial approximations and, at the same time, admitting a solid statistical model. In this paper, we identify another type of multidimensional linear approximation, called Davies-Meyer approximation, which has similar advantages, and present full statistical models for both the affine and the Davies-Meyer type of multidimensional linear approximations. The new models given in this paper are realistic, accurate and easy to use. They are backed up by standard statistical tools such as Pearson’s $\chi ^{2}$ test and finite population correction and demonstrated to work accurately using practical examples. [ABSTRACT FROM AUTHOR]

Early stopping of iterative algorithms is a widely used form of regularization in statistics, commonly used in conjunction with boosting and related gradient-type algorithms. Although consistency results have been established in some settings, such estimators are less well-understood than their analogues based on penalized regularization. In this paper, for a relatively broad class of loss functions and boosting algorithms (including $L^{2}$ -boost, LogitBoost, and AdaBoost, among others), we exhibit a direct connection between the performance of a stopped iterate and the localized Gaussian complexity of the associated function class. This connection allows us to show that the local fixed point analysis of Gaussian or Rademacher complexities, now standard in the analysis of penalized estimators, can be used to derive optimal stopping rules. We derive such stopping rules in detail for various kernel classes and illustrate the correspondence of our theory with practice for Sobolev kernel classes. [ABSTRACT FROM AUTHOR]

Let $\mathrm {W}\in \mathbb {C}^{n\times n}$ be a single-spiked Wishart matrix in the class $\mathrm {W}\sim \mathcal {CW}_{n}(m,\mathrm {I}_{n}+ \theta \mathrm {v}\mathrm {v}^{\dagger}) $ with $m\geq n$ , where ${\mathrm {I}}_{n}$ is the $n\times n$ identity matrix, $\mathrm {v}\in \mathbb {C}^{n\times 1}$ is an arbitrary vector with unit Euclidean norm, $\theta \geq 0$ is a non-random parameter, and $(\cdot)^{\dagger} $ represents the conjugate-transpose operator. Let u1 and ${\mathrm {u}}_{n}$ denote the eigenvectors corresponding to the smallest and the largest eigenvalues of W, respectively. This paper investigates the probability density function (p.d.f.) of the random quantity $Z_{\ell }^{(n)}=\left |{\mathrm {v}^{\dagger} \mathrm {u}_\ell }\right |^{2}\in (0,1)$ for $\ell =1,n$. In particular, we derive a finite dimensional closed-form p.d.f. for $Z_{1}^{(n)}$ which is amenable to asymptotic analysis as $m,n$ diverges with $m-n$ fixed. It turns out that, in this asymptotic regime, the scaled random variable $nZ_{1}^{(n)}$ converges in distribution to $\chi ^{2}_{2}/2(1+\theta)$ , where $\chi _{2}^{2}$ denotes a chi-squared random variable with two degrees of freedom. This reveals that u1 can be used to infer information about the spike. On the other hand, the finite dimensional p.d.f. of $Z_{n}^{(n)}$ is expressed as a double integral in which the integrand contains a determinant of a square matrix of dimension $(n-2)$. Although a simple solution to this double integral seems intractable, for special configurations of $n=2,3$ , and 4, we obtain closed-form expressions. [ABSTRACT FROM AUTHOR]

This paper considers the problem of secure parameter estimation when an estimation algorithm is prone to causative attacks. Causative attacks, in general, target decision-making algorithms (e.g., inference or learning algorithm) to alter their decisions in specific scenarios (e.g., distort parameter estimates for specific ranges of the parameter of interest). Such attacks influence the decisions via tampering with the mechanisms through which an algorithm acquires the statistical model of the population about which it aims to form a decision. Such attacks are viable, for instance, by contaminating the historical or training data, or by compromising an expert who provides the statistical model. In the presence of causative attacks, inference algorithms operate under a distorted statistical model for the data samples. This paper introduces a notion of secure parameter estimation and formalizes a framework under which secure estimation can be formulated and analyzed. The central premise underlying the secure estimation framework is that forming secure estimates introduces a new dimension to the estimation objective, pertaining to detecting attacks and isolating the true model. Since detection and isolation decisions themselves are imperfect, their inclusion induces an inherent coupling between the desired secure estimation objective and the auxiliary detection and isolation decisions that need to be formed in conjunction with the estimates. This paper establishes the fundamental interplay among these decisions, and characterizes the general decision rules in closed-forms for any desired estimation cost function. Furthermore, to circumvent the computational complexity associated with growing parameter dimension or attack complexity, a scalable estimation algorithm is provided, which is shown to enjoy certain optimality guarantees. Finally, the theory developed is applied to secure parameter estimation in sensor networks. [ABSTRACT FROM AUTHOR]

This paper introduces a new and ubiquitous framework for establishing achievability results in network information theory problems. The framework uses random binning arguments and is based on a duality between channel and source coding problems. Furthermore, the framework uses pmf approximation arguments instead of counting and typicality. This allows for proving coordination and strong secrecy problems, where certain statistical conditions on the distribution of random variables need to be satisfied. These statistical conditions include independence between messages and eavesdropper’s observations in secrecy problems and closeness to a certain distribution (usually, i.i.d. distribution) in coordination problems. One important feature of the framework is to enable one to add an eavesdropper and obtain a result on the secrecy rates for free. We make a case for generality of the framework by studying examples in a variety of settings including channel coding, lossy source coding, joint source-channel coding, coordination, strong secrecy, feedback, and relaying. In particular, by investigating the framework for the lossy source coding problem over broadcast channel, it is shown that the new framework provides a simple alternative scheme to the hybrid coding scheme. In addition, new results on secrecy rate region (under strong secrecy criterion) of wiretap broadcast channel and wiretap relay channel are derived. In a set of accompanied papers, we have shown the usefulness of the framework to establish achievability results for coordination problems, including interactive channel simulation, coordination via relay and channel simulation via another channel. [ABSTRACT FROM PUBLISHER]

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

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

This paper discovers fundamental principles of the backoff process that governs the performance of IEEE 802.11. A simplistic principle founded upon regular variation theory is that the backoff time has a truncated Pareto-type tail distribution with an exponent of (\log \gamma \!)/\log m ( \boldsymbol m is the multiplicative factor and \gamma is the collision probability). This reveals that the per-node backoff process is heavy-tailed in the strict sense for \gamma > 1/m^2 , and paves the way for the following unifying result. The state-of-the-art theory on the superposition of the heavy-tailed processes is applied to establish a dichotomy exhibited by the aggregate backoff process, putting emphasis on the importance of time-scales on which we view the backoff processes. While the aggregation on normal time-scales leads to a Poisson process, it is approximated by a new limiting process possessing long-range dependence (LRD) on coarse time-scales. This dichotomy turns out to be instrumental in formulating short-term fairness, extending existing formulas to arbitrary population, and to elucidate the absence of LRD in practical situations. A refined wavelet analysis is conducted to strengthen this argument. [ABSTRACT FROM AUTHOR]

Sparse principal component analysis has become one of the most widely used techniques for dimensionality reduction in high-dimensional datasets. While many methods are available for point estimation of eigenstructure in high-dimensional settings, in this paper we propose methodology for uncertainty quantification, such as construction of confidence intervals and tests for the principal eigenvector and the corresponding largest eigenvalue. We base our methodology on an M-estimator with Lasso penalty which achieves minimax optimal rates and is used to construct a de-biased sparse PCA estimator. The novel estimator has a Gaussian limiting distribution and can be used for hypothesis testing or support recovery of the first eigenvector. The empirical performance of the new estimator is demonstrated on synthetic data and we also show that the estimator compares favourably with the classical PCA in moderately high-dimensional regimes. [ABSTRACT FROM AUTHOR]

This paper derives consistency results for estimation in the finite direct sum of reproducing kernel Hilbert spaces (RKHS) for dependent data. The link between penalized and constrained estimation is established. We consider the relation between topological equivalent norms for direct sums of RKHS. These norms have different implications for estimation. Estimation in a ball of the RKHS defined by these norms essentially results in estimation with a ridge and Lasso penalty, respectively. A greedy algorithm for the solution of the estimation problem under these two norms is discussed for general loss functions. [ABSTRACT FROM AUTHOR]

The objective of a genome-wide association study (GWAS) is to associate subsequences of individuals’ genomes to the observable characteristics called phenotypes (e.g., high blood pressure). Motivated by the GWAS problem, in this paper we introduce the information-theoretic problem of associated subsequence retrieval, where a dataset of N (possibly high-dimensional) sequences of length G, and their corresponding observable (binary) characteristics is given. The sequences are chosen independently and uniformly at random from $\mathcal {X}^{\text {G}}$ , where $\mathcal {X}$ is a finite alphabet. The observable (binary) characteristic is only related to a specific unknown subsequence of length $L$ of the sequences, called associated subsequence. For each sequence, if the associated subsequence of it belongs to a universal finite set, then it is more likely to display the observable characteristic (i.e., it is more likely that the observable characteristic is one). The goal is to retrieve the associated subsequence using a dataset of N sequences and their observable characteristics. We demonstrate that as the parameters N, G, and L grow, a threshold effect appears in the curve of probability of error versus the rate which is defined as ${{\it\text { Gh}}(\text {L}/\text {G})}/{\text {N}}$ , where $\text {h}(\cdot)$ is the binary entropy function. This effect allows us to define the capacity of associated subsequence retrieval. We develop an achievable scheme and a matching converse for this problem, and thus characterize its capacity in two scenarios: the zero-error-rate and the $\epsilon $ -error-rate. [ABSTRACT FROM AUTHOR]

In the classical non-adaptive group testing setup, pools of items are tested together, and the main goal of a recovery algorithm is to identify the complete defective set given the outcomes of different group tests. In contrast, the main goal of a non-defective subset recovery algorithm is to identify a subset of non-defective items given the test outcomes. In this paper, we present a suite of computationally efficient and analytically tractable non-defective subset recovery algorithms. By analyzing the probability of error of the algorithms, we obtain bounds on the number of tests required for non-defective subset recovery with arbitrarily small probability of error. Our analysis accounts for the impact of both the additive noise (false positives) and dilution noise (false negatives). By comparing with information theoretic lower bounds, we show that the upper bounds on the number of tests are orderwise tight up to a \log ^2K factor, where $K$ is the number of defective items. We also provide simulation results that compare the relative performance of the different algorithms and reveal insights into their practical utility. The proposed algorithms significantly outperform the straightforward approaches of testing items one-by-one, and of first identifying the defective set and then choosing the non-defective items from the complement set, in terms of the number of measurements required to ensure a given success rate. [ABSTRACT FROM PUBLISHER]

In group testing, simple binary-output tests are designed to identify a small number $t$ of defective items that are present in a large population of $N$ items. Each test takes as input a group of items and produces a binary output indicating whether the group is free of the defective items or contains one or more of them. In this paper, we study a relaxation of the combinatorial group testing problem. A matrix is called $(t,\epsilon )$ -disjunct if it gives rise to a nonadaptive group testing scheme with the property of identifying a uniformly random $t$ -set of defective subjects out of a population of size $N$ with false positive probability of an item at most $\epsilon $ . We establish a new connection between $(t,\epsilon )$ -disjunct matrices and error correcting codes based on the dual distance of the codes and derive estimates of the parameters of codes that give rise to such schemes. Our methods rely on the moments of the distance distribution of codes and inequalities for moments of sums of independent random variables. We also provide a new connection between group testing schemes and combinatorial designs. [ABSTRACT FROM PUBLISHER]

The estimation of a random vector with independent components passed through a linear transform followed by a componentwise (possibly nonlinear) output map arises in a range of applications. Approximate message passing (AMP) methods, based on Gaussian approximations of loopy belief propagation, have recently attracted considerable attention for such problems. For large random transforms, these methods exhibit fast convergence and admit precise analytic characterizations with testable conditions for optimality, even for certain non-convex problem instances. However, the behavior of AMP under general transforms is not fully understood. In this paper, we consider the generalized AMP (GAMP) algorithm and relate the method to more common optimization techniques. This analysis enables a precise characterization of the GAMP algorithm fixed points that applies to arbitrary transforms. In particular, we show that the fixed points of the so-called max-sum GAMP algorithm for MAP estimation are critical points of a constrained maximization of the posterior density. The fixed points of the sum-product GAMP algorithm for estimation of the posterior marginals can be interpreted as critical points of a certain free energy. [ABSTRACT FROM PUBLISHER]

A random variable with distribution P is observed in Gaussian noise and is estimated by a mismatched minimum meansquare estimator that assumes that the distribution is Q, instead of P. This paper shows that the integral over all signal-to-noise ratios (SNRs) of the excess mean-square estimation error incurred by the mismatched estimator is twice the relative entropy D(P||Q) (in nats). This representation of relative entropy can be generalized to nonreal-valued random variables, and can be particularized to give new general representations of mutual information in terms of conditional means. Inspired by the new representation, we also propose a definition of free relative entropy which fills a gap in, and is consistent with, the literature on free probability. [ABSTRACT FROM AUTHOR]

Orthogonal-frequency-division multiplexing (OFDM) transforms a frequency-selective multiple-input multiple-output (MIMO) fading channel into a MIMO-OFDM channel that has a well-defined outage capacity. A transmitter with channel knowledge can achieve this capacity by a combination of eigenbeamforming and water-filling; the eigenbeamforming transforms the MIMO-OFDM channel into a parallel bank of scalar channels, and the water-filling procedure optimally allocates rate and energy to the scalar channels--a form of adaptive modulation. This paper shows that the water-filling procedure is not necessary to approach the zero-outage capacity of the MIMO-OFDM channel; it is sufficient instead to use a combination of eigenbeamforming and a fixed (nonadaptive) rate allocation. The fixed allocation depends only on the statistics of the channel and is independent of the particular channel realization. This paper proves that the capacity penalty incurred by the fixed allocation approaches zero as the number of antennas grows large. Numerical results indicate that the convergence is fast; for example, the fixed allocation suffers an SNR penalty of less than 0.2 dB for a 6-input 6-output Rayleigh-fading MIMO-OFDM channel at 8 bits per signaling interval, when the channel is assumed to be uncorrelated between antennas and between channel taps. A main conclusion is that eigenbeamforming is the most valuable way to exploit knowledge of the channel at the transmitter, and that any subsequent adaptive modulation has minimal relative value. [ABSTRACT FROM AUTHOR]

-In this paper, the conditions for blind identifiability from second-order statistics (SOS) of multiple-input multiple-output (MIMO) channels under orthogonal space-time block coded (OSTBC) transmissions are studied. The main contribution of the paper consists in the proof that, assuming more than one receive antenna, any OSTBC with a transmission rate higher than a given threshold, which is inversely proportional to the number of transmit antennas, permits the blind identification of the MIMO channel from SOS. Additionally, it has been proven that any real OSTBC with an odd number of transmit antennas is identifiable, and that any OSTBC transmitting an odd number of real symbols permits the blind identification of the MIMO channel regardless of the number of receive antennas, which extends previous identifiability results and suggests that any nonidentifiable OSTBC can be made identifiable by slightly reducing its code rate. The implications of these theoretical results include the explanation of previous simulation examples and, from a practical point of view, they show that the only nonidentifiable OSTBCs with practical interest are the Alamouti codes and the real square orthogonal design with four transmit antennas. Simulation examples and further discussion are also provided. [ABSTRACT FROM AUTHOR]

This paper compares the power divergence statistics of orders α > 1 with the information divergence statistic in the problem of testing the uniformity of a distribution. In this problem, the information divergence statistic is equivalent to the entropy statistic. Extending some previously established results about information diagrams, it is proved that the information divergence statistic in this problem is more efficient in the Bahadur sense than any power divergence statistic of order α > 1. This means that the entropy provides in this sense the most efficient way of characterizing the uniformity of a distribution. [ABSTRACT FROM AUTHOR]

The, paper deals with the f-divergences of Csiszár generalizing the discrimination information of Kullback, the total variation distance, the Hellinger divergence, and the Pearson divergence. All basic properties of f-divergences including relations to the decision errors are proved in a new manner replacing the classical Jensen inequality by a new generalized Taylor expansion of convex functions. Some new properties are proved too, e.g., relations to the statistical sufficiency and deficiency. The generalized Taylor expansion also shows very easily that all f-divergences are average statistical informations (differences between prior and posterior Bayes errors) mutually differing only in the weights imposed on various prior distributions. The statistical information introduced by De Groot and the classical information of Shannon are shown to be extremal cases corresponding to α = 0 and α = 1 in the class of the so-called Arimoto α-informations introduced in this paper for 0 < α < 1 by means of the Arimoto α-entropies. Some new examples of f-divergences are introduced as well, namely, the Shannon divergences and the Arimoto α-divergences leading for α ↑ 1 to the Shannon divergences. Square roots of all these divergences are shown to be metrics satisfying the triangle inequality. The last section introduces statistical tests and estimators based on the minimal f-divergence with the empirical distribution achieved in the families of hypothetic distributions. For the Kullback divergence this leads to the classical likelihood ratio test and estimator. [ABSTRACT FROM AUTHOR]

The cutoff rate R0(W) of a discrete memoryless channel (DMC) W is often used as a figure of merit alongside the channel capacity C(W). If a channel W is split into two possibly correlated subchannels W1 , W2, the capacity function always satisfies C(W1) + C(W2) ≤ C(W), while there are examples for which R0 (W1) + R0 (W2) > R0 (W). The fact that cutoff rate can be "created" by channel splitting was noticed by Massey in his study of an optical modulation system. This paper gives a general framework for achieving similar gains in the cutoff rate of arbitrary DMCs by methods of channel combining and splitting. The emphasis is on simple schemes that can be implemented in practice. We give several examples that achieve significant gains in cutoff rate at little extra system complexity. Theoretically, as the complexity grows without bound, the proposed framework is capable of boosting the cutoff rate of a channel to arbitrarily close to its capacity in a sense made precise in the paper. Apart from Massey's work, the methods studied here have elements in common with Forney's concatenated coding idea, a method by Pinsker for cutoff rate improvement, and certain coded-modulation techniques, namely, Ungerboeck's set-partitioning idea and Imai-Hirakawa multilevel coding; these connections are discussed in the paper. [ABSTRACT FROM AUTHOR]

Total Bregman divergences are a recent tweak of ordinary Bregman divergences originally motivated by applications that required invariance by rotations. They have displayed superior results compared with ordinary Bregman divergences on several clustering, computer vision, medical imaging, and machine learning tasks. These preliminary results raise two important problems. First, report a complete characterization of the left and right population minimizers for this class of total Bregman divergences. Second, characterize a principled superset of total and ordinary Bregman divergences with good clustering properties, from which one could tailor the choice of a divergence to a particular application. In this paper, we provide and study one such superset with interesting geometric features, that we call conformal divergences, and focus on their left and right population minimizers. Our results are obtained in a recently coined $(u, v)$ -geometric structure that is a generalization of the dually flat affine connections in information geometry. We characterize both analytically and geometrically the population minimizers. We prove that conformal divergences (resp. total Bregman divergences) are essentially exhaustive for their left (resp. right) population minimizers. We further report new results and extend previous results on the robustness to outliers of the left and right population minimizers, and discuss the role of the $(u, v)$ -geometric structure in clustering. Additional results are also given. [ABSTRACT FROM PUBLISHER]

We consider the high-dimensional discriminant analysis problem. For this problem, different methods have been proposed and justified by establishing exact convergence rates for the classification risk, as well as the \ell 2 convergence results to the discriminative rule. However, sharp theoretical analysis for the variable selection performance of these procedures have not been established, even though model interpretation is of fundamental importance in scientific data analysis. This paper bridges the gap by providing sharp sufficient conditions for consistent variable selection using the sparse discriminant analysis. Through careful analysis, we establish rates of convergence that are significantly faster than the best known results and admit an optimal scaling of the sample size $n$ , dimensionality $p$ , and sparsity level $s$ in the high-dimensional setting. Sufficient conditions are complemented by the necessary information theoretic limits on the variable selection problem in the context of high-dimensional discriminant analysis. Exploiting a numerical equivalence result, our method also establish the optimal results for the ROAD estimator and the sparse optimal scoring estimator. Furthermore, we analyze an exhaustive search procedure, whose performance serves as a benchmark, and show that it is variable selection consistent under weaker conditions. Extensive simulations demonstrating the sharpness of the bounds are also provided. [ABSTRACT FROM AUTHOR]

This paper studies the limiting behavior of a class of robust population covariance matrix estimators, originally due to Maronna in 1976, in the regime where both the number of available samples and the population size grow large. Using tools from random matrix theory, we prove that, for sample vectors made of independent entries having some moment conditions, the difference between the sample covariance matrix and (a scaled version of) such robust estimator tends to zero in spectral norm, almost surely. This result can be applied to various statistical methods arising from random matrix theory that can be made robust without altering their first order behavior. [ABSTRACT FROM PUBLISHER]

This paper studies the sample complexity of searching over multiple populations. We consider a large number of populations, each corresponding to either distribution P0 or P1. The goal of the search problem studied here is to find one population corresponding to distribution P1 with as few samples as possible. The main contribution is to quantify the number of samples needed to correctly find one such population. We consider two general approaches: nonadaptive sampling methods, which sample each population a predetermined number of times until a population following P1 is found, and adaptive sampling methods, which employ sequential sampling schemes for each population. We first derive a lower bound on the number of samples required by any sampling scheme. We then consider an adaptive procedure consisting of a series of sequential probability ratio tests, and show it comes within a constant factor of the lower bound. We give explicit expressions for this constant when samples of the populations follow Gaussian and Bernoulli distributions. An alternative adaptive scheme is discussed which does not require full knowledge of P1, and comes within a constant factor of the optimal scheme. For comparison, a lower bound on the sampling requirements of any nonadaptive scheme is presented. [ABSTRACT FROM AUTHOR]

Given a computable probability measure $P$ over natural numbers or infinite binary sequences, there is no computable, randomized method that can produce an arbitrarily large sample such that none of its members are outliers of $P$. In addition, given a binary predicate $\gamma $ , the length of the smallest program that computes a complete extension of $\gamma $ is less than the size of the domain of $\gamma $ plus the amount of information that $\gamma $ has with the halting sequence. [ABSTRACT FROM AUTHOR]

The problem of estimation of density functionals like entropy and mutual information has received much attention in the statistics and information theory communities. A large class of estimators of functionals of the probability density suffer from the curse of dimensionality, wherein the mean squared error decays increasingly slowly as a function of the sample size T as the dimension d of the samples increases. In particular, the rate is often glacially slow of order O(T^-\gamma /d), where \gamma >0 is a rate parameter. Examples of such estimators include kernel density estimators, k-nearest neighbor (k\-NN) density estimators, k\-NN entropy estimators, intrinsic dimension estimators, and other examples. In this paper, we propose a weighted affine combination of an ensemble of such estimators, where optimal weights can be chosen such that the weighted estimator converges at a much faster dimension invariant rate of O(T^-1). Furthermore, we show that these optimal weights can be determined by solving a convex optimization problem which can be performed offline and does not require training data. We illustrate the superior performance of our weighted estimator for two important applications: 1) estimating the Panter–Dite distortion-rate factor; and 2) estimating the Shannon entropy for testing the probability distribution of a random sample. [ABSTRACT FROM AUTHOR]

We examine the classical joint source-channel coding problem from the viewpoint of statistical physics and demonstrate that in the random coding regime, the posterior probability distribution of the source given the channel output is dominated source sequences, which exhibit a behavior that is highly parallel that of thermal equilibrium between two systems of particles that exchange energy, where one system corresponds to the source and the other corresponds to the channel. The thermodynamical entropies of the dual physical problem are analogous to conditional and unconditional Shannon entropies of the source, and so, their balance in thermal equilibrium yields a simple formula for the mutual information between the source and the channel output, that induced by the typical code in an ensemble of joint source--channel codes under certain conditions. This formula, as well as the statistical- mechanical perspective that leads to it, form the main contribution of this paper. We also demonstrate how our results can be used in applications, like the wiretap channel, and how can be extended to multiuser scenarios, like that of the multiple access channel. [ABSTRACT FROM AUTHOR]

In this paper, the ensembles of repeat multiple-accumulate codes (RAm), which are obtained by interconnecting a repeater with a cascade of m accumulate codes through uniform random interleavers, are analyzed. It is proved that the average spectral shapes of these code ensembles are equal to 0 below a threshold distance &epsilonm and, moreover, they form a nonincreasing sequence in m converging uniformly to the maximum between the average spectral shape of the linear random ensemble and 0. Consequently the sequence E,,, converges to the Gilbert-Varshamov (GV) distance. A further analysis allows to conclude that if m ≥ 2 the RAm are asymptotically good and that cm is the typical normalized minimum distance when the interleaver length goes to infinity. Combining the two results it is possible to conclude that the typical distance of the ensembles RAm converges to the Gilbert-Varshamov bound. [ABSTRACT FROM AUTHOR]

A divergence measure between two probability distributions or positive arrays (positive measures) is a useful tool for solving optimization problems in optimization, signal processing, machine learning, and statistical inference. The Csiszfár f-divergence is a unique class of divergences having information monotonicity, from which the dual α geometrical structure with the Fisher metric is derived. The Bregman divergence is another class of divergences that gives a dually flat geometrical structure different from the α-structure in general. Csiszfár gave an axiomatic characterization of divergences related to inference problems. The Kullback-Leibler divergence is proved to belong to both classes, and this is the only such one in the space of probability distributions. This paper proves that the α-divergences constitute a unique class belonging to both classes when the space of positive measures or positive arrays is considered. They are the canonical divergences derived from the dually flat geometrical structure of the space of positive measures. [ABSTRACT FROM AUTHOR]

This paper analyzes the potential advantages and theoretical challenges of "active learning" algorithms. Active learning involves sequential sampling procedures that use information gleaned from previous samples in order to focus the sampling and accelerate the learning process relative to "passive learning" algorithms, which are based on nonadaptive (usually random) samples. There are a number of empirical and theoretical results suggesting that in certain situations active learning can be significantly more effective than passive learning. However, the fact that active learning algorithms are feedback systems makes their theoretical analysis very challenging. This paper aims to shed light on achievable limits in active learning. Using minimax analysis techniques, we study the achievable rates of classification error convergence for broad classes of distributions characterized by decision boundary regularity and noise conditions. The results clearly indicate the conditions under which one can expect significant gains through active learning. Furthermore, we show that the learning rates derived are tight for "boundary fragment" classes in d-dimensional feature spaces when the feature marginal density is bounded from above and below. [ABSTRACT FROM AUTHOR]

This paper presents models, algorithms and analysis for measurement-based admission control in network applications in which there is high uncertainty concerning source statistics. In the process it extends and unifies several recent approaches to admission control. A new class of algorithms is introduced based on results concerning Markov's canonical distributions. In addition, a new model is developed for the evolution of the number of flows in the admission control system. Performance evaluation is done through both analysis and simulation. Results show that the proposed algorithms minimize buffer-overflow probability among the class of all moment-consistent algorithms. [ABSTRACT FROM AUTHOR]

This paper is concerned with error exponents in testing problems raised by autoregressive (AR) modeling. The tests to be considered are variants of generalized likelihood ratio testing corresponding to traditional approaches to autoregressive moving-average (ARMA) modeling estimation. In several related problems, such as Markov order or hidden Markov model order estimation, optimal error exponents have been determined thanks to large deviations theory. AR order testing is specially challenging since the natural tests rely on quadratic forms of Gaussian processes. In sharp contrast with empirical measures of Markov chains, the large deviation principles (LDPs) satisfied by Gaussian quadratic forms do not always admit an information-theoretic representation. Despite this impediment, we prove the existence of nontrivial error exponents for Gaussian AR order testing. And furthermore, we exhibit situations where the exponents are optimal. These results are obtained by showing that the log-likelihood process indexed by AR models of a given order satisfy an LDP upper bound with a weakened information-theoretic representation. [ABSTRACT FROM AUTHOR]

In this paper, it is shown how to extract a hypothesis with small risk from the ensemble of hypotheses generated by an arbitrary on-line learning algorithm run on an independent and identically distributed (i.i.d.) sample of data. Using a simple large deviation argument, we prove fight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic Mn associated with the on-line performance of the ensemble. Via sharp pointwise bounds on Mn, we then obtain risk tail bounds for kernel Perceptron algorithms in terms of the spectrum of the empirical kernel matrix. These bounds reveal that the linear hypotheses found via our approach achieve optimal tradeoffs between hinge loss and margin size over the class of all linear functions, an issue that was left open by previous results. A distinctive feature of our approach is that the key tools for our analysis come from the model of prediction of individual sequences; i.e., a model making no probabilistic assumptions on the source generating the data. In fact, these tools turn out to be so powerful that we only need very elementary statistical facts to obtain our final risk bounds. [ABSTRACT FROM AUTHOR]

This paper introduces the concept of random context representations for the transition probabilities of a finite-alphabet stochastic process. Processes with these representations generalize context tree processes (also known as variable length Markov chains), and are proved to coincide with processes whose transition probabilities are almost surely continuous functions of the (infinite) past. This is similar to a classical result by Kalikow about continuous transition probabilities. Existence and uniqueness of a minimal random context representation are shown, in the sense that there exists a unique representation that looks into the past as little as possible in order to determine the next symbol. Both this representation and the transition probabilities can be consistently estimated from data, and some finite sample adaptivity properties are also obtained (including an oracle inequality). In particular, the estimator achieves minimax performance, up to logarithmic factors, for the class of binary renewal processes whose arrival distributions have bounded moments of order $2+\gamma $ . [ABSTRACT FROM AUTHOR]

Source coding with a side information “vending machine” is a recently proposed framework in which the statistical relationship between the side information and the source, instead of being given and fixed as in the classical Wyner–Ziv problem, can be controlled by the decoder. This control action is selected by the decoder based on the message encoded by the source node. Unlike conventional settings, the message can thus carry not only information about the source to be reproduced at the decoder, but also control information aimed at improving the quality of the side information. In this paper, the analysis of the tradeoffs between rate, distortion, and cost associated with the control actions is extended from the previously studied point-to-point setup to two basic multiterminal models. First, a distributed source coding model is studied, in which two encoders communicate over rate-limited links to a decoder, whose side information can be controlled. The control actions are selected by the decoder based on the messages encoded by both source nodes. For this setup, inner bounds are derived on the rate-distortion-cost region for both cases in which the side information is available causally and noncausally at the decoder. These bounds are shown to be tight under specific assumptions, including the scenario in which the sequence observed by one of the nodes is a function of the source observed by the other and the side information is available causally at the decoder. Then, a cascade scenario in which three nodes are connected in a cascade and the last node has controllable side information is also investigated. For this model, the rate-distortion-cost region is derived for general distortion requirements and under the assumption of causal availability of side information at the last node. [ABSTRACT FROM AUTHOR]

When transmitting stochastically arriving data over fading channels, there is an inherent tradeoff between the required average transmission power and the average queueing delay experienced by the data. This tradeoff can be exploited by appropriately scheduling the transmission of data over time. In this paper, we study the behavior of the optimal power-delay tradeoff for a single user in the regime of asymptotically small delays. In this regime, we first lower bound how much average power is required as a function of the average queueing delay. We show that the rate at which this bound increases as the delay becomes asymptotically small depends on the behavior of the fading distribution near zero, as well as the arrival statistics. We lower bound this rate for two different classes of fading distributions: one class that requires infinite power to minimize the queueing delay and one class that requires only finite power. We then show that for both classes, the bounds can essentially be achieved by a sequence of simple “channel threshold” policies, which only transmit when the channel gain is greater than a given threshold. We also consider several other transmission scheduling policies and characterize their convergence behavior in the small-delay regime. [ABSTRACT FROM PUBLISHER]

This paper follows the recent work of Helleseth, Kholosha, Johansen, and Ness to study the cross correlation between an m-sequence of period 2m - 1 and the d-decimation of an m-sequence of a shorter period 2n - 1 for an even number m = 2n. Assuming that d satisfies d(2l + 1) = 2i mod 2n - 1) for some l > 0 and i ≥ 0, it is proved that the cross correlation takes on either exactly three or four values depending on whether l and n are coprime or not. The distribution of the cross-correlation values is also completely determined. Our results theoretically confirm the numerical data by Ness and Helleseth. It is conjectured that there are no other decimations that give at most four-valued cross correlation apart from the ones proved here. [ABSTRACT FROM AUTHOR]

Dual-tree wavelet decompositions have recently gained much popularity, mainly due to their ability to provide an accurate directional analysis of images combined with a reduced redundancy. When the decomposition of a random process is performed—which occurs in particular when an additive noise is corrupting the signal to be analyzed—it is useful to characterize the statistical properties of the dual-tree wavelet coefficients of this process. As dual-tree decompositions constitute overcomplete frame expansions, correlation structures are introduced among the coefficients, even when a white noise is analyzed. In this paper, we show that it is possible to provide an accurate description of the covariance properties of the dual-tree coefficients of a wide-sense-stationary process. The expressions of the (cross-) covariance sequences of the coefficients are derived in the one- and two-dimensional cases. Asymptotic results are also provided, allowing to predict the behavior of the second-order moments for large lag values or at coarse resolution. In addition, the cross-correlations between the primal and dual wavelets, which play a primary role in our theoretical analysis, are calculated for a number of classical wavelet families. Simulation results are finally provided to validate these results. [ABSTRACT FROM AUTHOR]

A clock-controlled linear feedback shift register (LFSR) is a simple keystream generator consisting of an LFSR whose clock is controlled by another LFSR so that the output is an irregularly decimated LFSR sequence. Statistical distinguishers for keystream generators are algorithms whose objective is to distinguish the keystream sequence from a purely random sequence. Previously proposed statistical distinguishers for clock-controlled LFSRs are based on detecting binary linear relations in the keystream sequence that hold with a probability sufficiently different from one half. In this paper, a novel approach based on the correlation analysis of clock-controlled LFSRs is introduced. It significantly reduces the required computation time and essentially consists of a probabilistic reconstruction of bits in the regularly clocked LFSR sequence that satisfy the LFSR recurrence or any linear recurrence derived from low-weight multiples of the LFSR characteristic polynomial. The keystream sequence length and the computation time required for a reliable statistical distinction are analyzed both theoretically and experimentally. The new approach shows that there is no need to deal with the majority bits of blocks of LFSR bits as proposed recently. If individual bits or blocks of bits are considered instead, then the underlying probabilities can be computed theoretically instead of heuristically, which in turn allows a simple and general theoretical analysis of the keystream sequence length required. [ABSTRACT FROM AUTHOR]

Multiplicative processes, multifractals, and more recently also infinitely divisible cascades have seen increased popularity in a host of applications requiring versatile multiscale models, ranging from hydrodynamic turbulence to computer network traffic, from image processing to economics. The methodologies prevalent as of today rely to a large extent on iterative schemes used to produce infinite detail and repetitive structure across scales. While appealing, due to their simplicity, these constructions have limited applicability as they lead by default to power law progression of moments through scales, to non- stationary increments and often to inherent log-periodic scaling which favors an exponential set of scales. This paper studies and develops a wide class of infinitely divisible cascades (IDC), thereby establishing the first reported cases of controllable scaling of moments in non-power-law font Embedded in the framework of IDC, these processes exhibit stationary increments and scaling over a continuous range of scales. Criteria for convergence, further statistical properties, as well as MATLAB routines are provided. [ABSTRACT FROM AUTHOR]

In this paper, we present a new class of importance sampling simulation distributions, the universal, distributions. We show that these distributions are universally efficient in the sense that they depend only on a single scalar parameter regardless of the dimensionality of the underlying system or of the error sets to be simulated. [ABSTRACT FROM AUTHOR]

We study the compression of $n$ quantum systems, each prepared in the same state belonging to a given parametric family of quantum states. For a family of states with $f$ independent parameters, we devise an asymptotically faithful protocol that requires a hybrid memory of size $(f/2)\log n$ , including both quantum and classical bits. Our construction uses a quantum version of local asymptotic normality and, as an intermediate step, solves the problem of compressing displaced thermal states of $n$ identically prepared modes. In both cases, we show that $(f/2)\log n$ is the minimum amount of memory needed to achieve asymptotic faithfulness. In addition, we analyze how much of the memory needs to be quantum. We find that the ratio between quantum and classical bits can be made arbitrarily small, but cannot reach zero: unless all the quantum states in the family commute, no protocol using only classical bits can be faithful, even if it uses an arbitrarily large number of classical bits. [ABSTRACT FROM AUTHOR]

Given a sufficient statistic for a parametric family of distributions, one can estimate the parameter without access to the data. However, the memory or code size for storing the sufficient statistic may nonetheless still be prohibitive. Indeed, for $n$ independent samples drawn from a k$ -nomial distribution with d=k-1$ degrees of freedom, the length of the code scales as d\log n+O(1) . We consider errors measured according to the relative entropy and variational distance criteria. For the code constructions, we leverage Rissanen’s minimum description length principle, which yields a non-vanishing error measured according to the relative entropy. For the converse parts, we use Clarke and Barron’s formula for the relative entropy of a parameterized distribution and the corresponding mixture distribution. However, this method only yields a weak converse for the variational distance. We develop new techniques to achieve vanishing errors, and we also prove strong converses. The latter means that even if the code is allowed to have a non-vanishing error, its length must still be at least ({d}/{2})\log n . [ABSTRACT FROM AUTHOR]

We study the top- $K$ ranking problem where the goal is to recover the set of top- $K$ ranked items out of a large collection of items based on partially revealed preferences. We consider an adversarial crowdsourced setting where there are two population sets, and pairwise comparison samples drawn from one of the populations follow the standard Bradley-Terry-Luce model (i.e., the chance of item $i$ beating item $j$ is proportional to the relative score of item $i$ to item $j$ ), while in the other population, the corresponding chance is inversely proportional to the relative score. When the relative size of the two populations is known, we characterize the minimax limit on the sample size required (up to a constant) for reliably identifying the top- $K$ items, and demonstrate how it scales with the relative size. Moreover, by leveraging a tensor decomposition method for disambiguating mixture distributions, we extend our result to the more realistic scenario, in which the relative population size is unknown, thus establishing an upper bound on the fundamental limit of the sample size for recovering the top- $K$ set. [ABSTRACT FROM PUBLISHER]

Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors. It is known that $\exp (\Theta (n^{1/3}))$ traces are necessary and sufficient for mean-based worst-case trace reconstruction over the deletion channel, and this result was also extended to certain channels combining deletions and geometric insertions of uniformly random bits. In this work, we use a simple extension of the original complex-analytic approach to show that these results are examples of a much more general phenomenon. We introduce oblivious synchronization channels, which map each input bit to an arbitrarily distributed sequence of replications and insertions of random bits. This general class captures all previously considered synchronization channels. We show that for any oblivious synchronization channel whose output length follows a sub-exponential distribution either mean-based trace reconstruction is impossible or $\exp (O(n^{1/3}))$ traces suffice for this task. [ABSTRACT FROM AUTHOR]

Variational representations of divergences and distances between high-dimensional probability distributions offer significant theoretical insights and practical advantages in numerous research areas. Recently, they have gained popularity in machine learning as a tractable and scalable approach for training probabilistic models and for statistically differentiating between data distributions. Their advantages include: 1) They can be estimated from data as statistical averages. 2) Such representations can leverage the ability of neural networks to efficiently approximate optimal solutions in function spaces. However, a systematic and practical approach to improving the tightness of such variational formulas, and accordingly accelerate statistical learning and estimation from data, is currently lacking. Here we develop such a methodology for building new, tighter variational representations of divergences. Our approach relies on improved objective functionals constructed via an auxiliary optimization problem. Furthermore, the calculation of the functional Hessian of objective functionals unveils the local curvature differences around the common optimal variational solution; this quantifies and orders the tightness gains between different variational representations. Finally, numerical simulations utilizing neural network optimization demonstrate that tighter representations can result in significantly faster learning and more accurate estimation of divergences in both synthetic and real datasets (of more than 1000 dimensions), often accelerated by nearly an order of magnitude. [ABSTRACT FROM AUTHOR]