Search

Testing the independence of the entries of multidimensional Gaussian observations is a very important problem in statistics, with a number of applications in signal processing, radar, cognitive radio, seismography, and multiple other fields. Typically, the problem is formulated as a binary hypothesis test, whereby the presence of correlation is declared when the value of a certain statistic is higher than a certain predetermined threshold. Most of the statistics for correlation tests are constructed from the sample correlation matrix (also known as sample coherence matrix in signal processing), which is defined as a power-normalized version of the sample covariance matrix. In this paper, correlation tests constructed from linear spectral statistics (LSS) of the sample correlation matrix are analyzed under the asymptotic framework where both sample size and observation dimension become large but comparable in magnitude. A central limit theorem (CLT) is established on this class of statistics, which is valid for generally correlated Gaussian observations. Results show that LSS asymptotically fluctuate as Gaussian random variables under both the hypotheses, with an asymptotic mean and variance that can be established for each particular test. In particular, this general CLT can be used to establish the asymptotic behavior of two of the most important correlation test statistics, namely the generalized likelihood ratio test and the Frobenius norm test, under both null and alternative hypotheses. As a by-product, it is established that LSS of sample covariance and sample correlation matrices have exactly the same first order behavior, but quite different asymptotic fluctuations in the second-order regime. In both the cases, the LSS asymptotically behave as Gaussian random variables, although with quite different asymptotic means and variances. [ABSTRACT FROM PUBLISHER]

This paper introduces a convenient strategy for coding and predicting sequences of independent, identically distributed random variables generated from a large alphabet of size $m$ . In particular, the size of the sample is allowed to be variable. The employment of a Poisson model and tilting method simplifies the implementation and analysis through independence. The resulting strategy is optimal within the class of distributions satisfying a moment condition, and it is close to optimal for the class of all i.i.d distributions on strings of a given length. The method also can be used to code and predict strings with a condition on the tail of the ordered counts, and it can be applied to distributions in an envelope class. Moreover, we show that our model permits exact computation of the minimax optimal code, for all alphabet sizes, when conditioning on the size of the sample. [ABSTRACT FROM PUBLISHER]

We consider random number conversion (RNC) through random number storage with restricted size. We clarify the relation between the performance of RNC and the size of storage in the framework of the first- and second-order asymptotics, and derive their rate regions. Then, we show that the results for RNC with restricted storage recover those for conventional RNC without storage in the limit of storage size. To treat RNC via restricted storage, we introduce a new kind of probability distributions named generalized Rayleigh-normal distributions. Using the generalized Rayleigh-normal distributions, we can describe the second-order asymptotic behavior of RNC via restricted storage in a unified manner. As an application to quantum information theory, we analyze LOCC conversion via entanglement storage with restricted size. Moreover, we derive the optimal LOCC compression rate under a constraint of conversion accuracy. [ABSTRACT FROM PUBLISHER]

In this paper, we study the problem of obtaining 1-of-2 string oblivious transfer (OT) between users Alice and Bob, in the presence of a passive eavesdropper Eve. The resource enabling OT in our setup is a noisy broadcast channel from Alice to Bob and Eve. Apart from the OT requirements between the users, Eve is not allowed to learn anything about the users’ inputs. When Alice and Bob are honest-but-curious and the noisy broadcast channel is made up of two independent binary erasure channels (connecting Alice–Bob and Alice–Eve), we derive the 1-of-2 string OT capacity for both 2-privacy (when Eve can collude with either Alice or Bob) and 1-privacy (when no such collusion is allowed). We generalize these capacity results to 1-of- $N$ string OT and study other variants of this problem. When Alice and/or Bob are malicious, we present a different scheme based on interactive hashing. This scheme is shown to be optimal for certain parameter regimes. We present a new formulation of multiple, simultaneous OTs between Alice–Bob and Alice–Cathy. For this new setup, we present schemes and outer bounds that match in all but one regime of parameters. Finally, we consider the setup where the broadcast channel is made up of a cascade of two independent binary erasure channels (connecting Alice–Bob and Bob–Eve) and 1-of-2 string OT is desired between Alice and Bob with 1-privacy. For this setup, we derive an upper and lower bound on the 1-of-2 string OT capacity which match in one of two possible parameter regimes. [ABSTRACT FROM PUBLISHER]

In this paper, we revisit the discrete lossy Gray-Wyner problem. In particular, we derive its optimal second-order coding rate region, its error exponent (reliability function), and its moderate deviations constant under mild conditions on the source. To obtain the second-order asymptotics, we extend some ideas from Watanabe’s work. In particular, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú. The converse part uses a perturbation argument by Gu and Effros in their strong converse proof of the discrete Gray–Wyner problem. The achievability part uses two novel elements: 1) a generalization of various type covering lemmas and 2) the uniform continuity of the conditional rate-distortion function in both the source (joint) distribution and the distortion level. To obtain the error exponent, for the achievability part, we use the same generalized type covering lemma, and for the converse, we use the strong converse together with a change-of-measure technique. Finally, to obtain the moderate deviations constant, we apply the moderate deviations theorem to probabilities defined in terms of information spectrum quantities. [ABSTRACT FROM PUBLISHER]

An information theoretical analysis of nonadaptive group testing schemes based on sparse pooling graphs is presented. A pooling graph is a bipartite graph for which the adjacency matrix is a pooling matrix. The binary status of the objects to be tested are modeled by independent identically distributed. Bernoulli random variables with probability $p$ . An $(l, r, n)$ -regular pooling graph is a bipartite graph in which the left nodes have degree $l$ , the right nodes have degree $r$ , and $n$ is the number of left nodes. The main contribution of this paper is a direct coding theorem that gives the conditions for the existence of an estimator that can achieve an arbitrarily small probability of error. An estimator is a function that uses observations to infer the state of an object. The direct coding theorem is proved by averaging the upper bound on the probability of the estimation error of the typical set estimator over an $(l, r, n)$ -regular pooling graph ensemble. Numerical results indicate sharp threshold behaviors in the asymptotic regime. These results can provide a concrete benchmark for nonadaptive group testing of existing and emerging detection algorithms over a noiseless system. [ABSTRACT FROM PUBLISHER]

Treating interference as noise (TIN) as the most appropriate approach in dealing with interference and the conditions on its optimality has attracted the interest of researchers recently. However, our knowledge on necessary and sufficient conditions of TIN is restricted to a few setups with limited number of users. In this paper, we study the optimality of TIN in terms of the generalized degrees of freedom (GDoF) for a fundamental network, namely, the $M\times 2$ X-channel. To this end, the achievable GDoF of TIN with power allocations at the transmitters is studied. It turns out that the transmit power allocation maximizing the achievable GDOF is given by on–off signaling as long as the receivers use TIN. This leads to two variants of TIN, namely, P2P-TIN and 2-IC-TIN. While in the first variant the $M\times 2$ X-channel is reduced to a point-to-point (P2P) channel, in the second variant, the setup is reduced to a two-user interference channel in which the receivers use TIN. The optimality of these two variants is studied separately. To this end, novel genie-aided upper bounds on the capacity of the X-channel are established. The conditions on the optimality of P2P-TIN can be summarized as follows. P2P-TIN is GDoF-optimal if there exists a dominant multiple access channel or a dominant broadcast channel embedded in the X channel. Furthermore, the necessary and sufficient conditions on the GDoF-optimality of 2-IC-TIN are presented. Interestingly, it turns out that operating the $M\times 2$ X-channel in the 2-IC-TIN mode might be still GDOF optimal, although the conditions given by Geng et al. are violated. However, 2-IC-TIN is sub-optimal if there exists a single interferer which causes sufficiently strong interference at both receivers. The comparison of the results with the state of the art shows that the GDOF optimality of TIN is expanded significantldy. [ABSTRACT FROM PUBLISHER]

The impact of cooperation on interference management is investigated by studying an elemental wireless network, the so-called symmetric interference relay channel (IRC), from a generalized degrees of freedom (GDoF) perspective. This is motivated by the fact that the deployment of relays is considered as a remedy to overcome the bottleneck of current systems in terms of achievable rates. The focus of this paper is on the regime in which the interference link is weaker than the source-relay link in the IRC. Our approach toward studying the GDoF goes through the capacity analysis of the linear deterministic IRC (LD-IRC). New upper bounds on the sum capacity of the LD-IRC based on genie-aided approaches are established. These upper bounds together with some existing upper bounds are achieved by using four novel transmission schemes. Extending the upper bounds and the transmission schemes to the Gaussian case, the GDoF of the Gaussian IRC is characterized for the aforementioned regime. This completes the GDoF results available in the literature for the symmetric GDoF. It turns out that even if the incoming and outgoing links of the relay are both weaker than the desired channel, involving a relay can increase the GDoF. Interestingly, utilizing the relay in this case can increase the slope of the GDoF from −2 [in the interference channel (IC)] to −1 or 0. This shrinks the regime where ignoring the interference by treating it as noise is optimal. Furthermore, the analysis shows that if the relay ingoing and outgoing links are sufficiently strong, the relay is able to neutralize the interference completely. In this case, the bottleneck of the transmission will be the interference links, and hence, the GDoF increases if the interference link gets stronger. It is shown that in the strong interference regime, in contrast to the IC, the GDoF can be a monotonically decreasing function of the interference level. [ABSTRACT FROM PUBLISHER]

This paper gives improved Rényi entropy power inequalities (R-EPIs). Consider a sum Sn = \sum k=1^{n} Xk of n independent continuous random vectors taking values on {\mathbb {R}}^{d} , and let \alpha \in [1, \infty ] . An R-EPI provides a lower bound on the order- \alpha Rényi entropy power of S_{n} that, up to a multiplicative constant (which may depend in general on n, \alpha , d$ ), is equal to the sum of the order- \alpha $ Rényi entropy powers of the n$ random vectors . For $\alpha =1$ , the R-EPI coincides with the well-known entropy power inequality by Shannon. The first improved R-EPI is obtained by tightening the recent R-EPI by Bobkov and Chistyakov, which relies on the sharpened Young’s inequality. A further improvement of the R-EPI also relies on convex optimization and results on rank-one modification of a real-valued diagonal matrix. [ABSTRACT FROM PUBLISHER]

Let N be a random variable distributed according to some appropriate distribution over the set of products of two primes, such that factoring N is believed to be hard. The RSA assumption states that, given an a chosen uniformly at random from and an e \in {\mathbb {N}} \setminus \{1\} such that \gcd (e, \phi (N)) = 1 , it is computationally hard to find an x\in \mathbb Z N such that x^{e} - a \equiv 0 \pmod N . When complexity-theoretic (relative) lower bounds for certain cryptographic problems in a general model of computation seem to elude discovery, a common practice in cryptography is to give proofs of computational security in meaningful restricted models of computation. An example of such a restricted model that is interesting in cryptography is the generic group model that has been used for proving lower bounds for the discrete logarithm problem and other related problems. A generic model captures that an algorithm does not exploit the bit representation of the elements other than for testing equality. In this paper, we prove that the problem of factoring $N$ can be efficiently reduced to solving the RSA problem on {\mathbb {Z}}_{N} in the generic ring model of computation, where an algorithm can perform ring operations, inverse ring operations, and test equality. This provides evidence toward the soundness of the RSA encryption and digital signature scheme, in particular showing that under the factoring assumption, they are not vulnerable to certain kinds of cryptanalytic attacks. [ABSTRACT FROM AUTHOR]

Let \mathcal N=\1,\ldots ,n\ . The entropy function h of a set of n discrete random variables \{X_{i}:i\in \mathcal {N} \} is a 2^{n} -dimensional vector whose entries are \text h( \mathcal A)\triangleq H(X \mathcal A) , \mathcal A\subset \mathcal {N} , the (joint) entropies of the subsets of the set of n random variables with H(X_\emptyset )=0 by convention. The set of all entropy functions for n discrete random variables, denoted by , is called the entropy region for n . Characterization of \Gamma ^*n and its closure \overline {\Gamma ^*n} are well-known open problems in information theory. They are important not only because they play key roles in information theory problems but also they are related to other subjects in mathematics and physics. In this paper, we consider partition-symmetrical entropy functions. Let p=\ \mathcal N1,\ldots , \mathcal {Nt\} be a t -partition of \mathcal {N} . An entropy function \bf h is called p -symmetrical if for all {\mathcal{ A}},{\mathcal{ B}} \subset {\mathcal{ N}} , \text {h}({\mathcal{ A}}) = \text {h}({\mathcal{ B}}) whenever \mathcal A \cap \mathcal Ni = {\mathcal{ B}} \cap \mathcal Ni , i = 1, \ldots ,t . The set of all the p -symmetrical entropy functions, denoted by \Psi ^{*}_{p} , is called p -symmetrical entropy function region. We prove that \overline \Psi ^*p , the closure of \Psi ^{*}p , is completely characterized by Shannon-type information inequalities if and only if $p$ is the 1-partition or a 2-partition with one of its blocks being a singleton. The characterization of the partition-symmetrical entropy functions can be useful for solving some information theory and related problems where symmetry exists in the structure of the problems. [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]

The best known inner bound for the two-user discrete memoryless interference channel is the Han–Kobayashi rate region. The coding schemes that achieve this region are based on rate-splitting and superposition coding. In this paper, we develop a multicoding scheme to achieve the same rate region. A key advantage of the multicoding nature of the proposed coding scheme is that it can be naturally extended to more general settings, such as when encoders have state information or can overhear each other. In particular, we extend our coding scheme to characterize the capacity region of the state-dependent deterministic Z-interference channel when noncausal state information is available at the interfering transmitter. We specialize our results to the case of the linear deterministic model with ON/OFF interference, which models a wireless system where a cognitive transmitter is noncausally aware of the times it interferes with a primary transmission. For this special case, we provide an explicit expression for the capacity region and discuss some interesting properties of the optimal strategy. We also extend our multicoding scheme to find the capacity region of the deterministic Z-interference channel when the signal of the interfering transmitter can be overheard at the other transmitter (also known as unidirectional partial cribbing). [ABSTRACT FROM PUBLISHER]

This paper extends the empirical minimum divergence approach for models, which satisfy linear constraints with respect to the probability measure of the underlying variable (moment constraints) to the case where such constraints pertain to its quantile measure (called here semiparametric quantile models). The case when these constraints describe shape conditions as handled by the L-moments is considered, and both the description of these models as well as the resulting nonclassical minimum divergence procedures are presented. These models describe neighbourhoods of classical models used mainly for their tail behavior, for example, neighborhoods of Pareto or Weibull distributions, with which they may share the same first L-moments. The properties of the resulting estimators are illustrated by simulated examples comparing maximum likelihood estimators on Pareto and Weibull models to the minimum chi-square empirical divergence approach on semiparametric quantile models, and others. [ABSTRACT FROM PUBLISHER]

Consider a memoryless degraded broadcast channel (DBC) in which the channel output is a single-letter function of the channel input and the channel noise. As examples, for the Gaussian broadcast channel (BC), this single-letter function is real scalar addition and for the binary-symmetric BC, this single-letter function is modulo-two addition. This paper identifies several classes of discrete memoryless DBCs for which a relatively simple encoding scheme, which we call natural encoding, achieves capacity. Natural encoding (NE) combines symbols from independent codebooks (one for each receiver) using the same single-letter function that adds distortion to the channel. The alphabet size of each NE codebook is bounded by that of the channel input. This paper also defines the input-symmetric DBC, introduces permutation encoding for the input-symmetric DBC, and proves its optimality. Because it is a special case of permutation encoding, NE is capacity achieving for the two-receiver group-operation DBC. Combining the broadcast Z channel and group-operation DBC results yields a proof that NE is also optimal for the discrete multiplication DBC. Along the way, the paper also provides explicit parametric expressions for the two-receiver binary-symmetric DBC and broadcast Z channel. [ABSTRACT FROM AUTHOR]

The focus of this paper is to study the performance of the quantize-and-forward (QF) scheme over a half-duplex relay channel that is slowly fading, with the assumption that the channel state information (CSI) is available only at the receiver side. In order to do so, three steps are taken. The first step is to characterize the achievable rate of the QF scheme over a discrete memoryless half-duplex relay channel. Then, the achievable rate over a corresponding additive white Gaussian noise channel is obtained (the specific assumption regarding the CSI in this paper makes this step nontrivial). With the results from the first two steps, performance measures such as outage probability, expected rate, and diversity-multiplexing tradeoff (DMT) over slow fading channels are evaluated. It is shown that the QF scheme can significantly outperform the compress-and-forward scheme at finite signal-to-noise ratio (SNR) and it can achieve the optimal DMT at asymptotically high SNR. Moreover, it is shown that simple feedback from the destination node to the relay node can further improve the performance of the QF scheme. [ABSTRACT FROM AUTHOR]

This paper focuses on illustrating 1) the equivalence between Stein's identity and De Bruijn's identity, and 2) two extensions of De Bruijn's identity. First, it is shown that Stein's identity is equivalent to De Bruijn's identity under additive noise channels with specific conditions. Second, for arbitrary but fixed input and noise distributions under additive noise channels, the first derivative of the differential entropy is expressed by a function of the posterior mean, and the second derivative of the differential entropy is expressed in terms of a function of Fisher information. Several applications over a number of fields, such as signal processing and information theory, are presented to support the usefulness of the developed results in this paper. [ABSTRACT FROM AUTHOR]

The achievable information rate region problem of multisource multisink network coding for general acyclic networks with arbitrary transmission requirements has previously been studied, where inner and outer bounds on the region were derived in terms of \Gamma^\ast, the fundamental region of entropy functions. In this paper, we derive the exact characterization of the achievable rate region in terms of entropic functions, thus closing the gap between the existing inner and outer bounds. [ABSTRACT FROM AUTHOR]

This paper studies Brownian distributions on compact Lie groups. These are defined as the marginal distributions of Brownian processes and are intended as a natural extension of the well-known normal distributions to compact Lie groups. It is shown that this definition preserves key properties of normal distributions. In particular, Brownian distributions transform in a nice way under group operations and satisfy an extension of the central limit theorem. Brownian distributions on a compact Lie group G belong to one of two parametric families NL(g,C) and NR(g,C)—g \in G and C a positive-definite symmetric matrix. In particular, the parameter g appears as a location parameter. An approach based on the extrinsic mean for estimation of the parameters g and C is studied in detail. It is shown that g is the unique extrinsic mean for a Brownian distribution NL(g,C) or NR(g,C). Resulting estimates are proved to be consistent and asymptotically normal. While they may also be used to simultaneously estimate g and C, it is seen this requires that G be embedded into a higher dimensional matrix Lie group. Going beyond Brownian distributions, it is shown the extrinsic mean can be used to recover the location parameter for a wider class of distributions arising more generally from Lévy processes. The compact Lie group structure places limitations on the analogy between normal distributions and Brownian distributions. This is illustrated by the study of multivariate Brownian distributions. These are introduced as Brownian distributions on some product group—e.g., G \times G. This paper describes their covariance structure and considers its transformation under group operations. [ABSTRACT FROM PUBLISHER]

In this paper, the diversity-multiplexing gain tradeoff (DMT) of single-source, single-sink (ss-ss), multihop relay networks having slow-fading links is studied. In particular, the two end-points of the DMT of ss-ss full-duplex networks are determined, by showing that the maximum achievable diversity gain is equal to the min-cut and that the maximum multiplexing gain is equal to the min-cut rank, the latter by using an operational connection to a deterministic network. Also included in the paper, are several results that aid in the computation of the DMT of networks operating under amplify-and-forward (AF) protocols. In particular, it is shown that the colored noise encountered in amplify-and-forward protocols can be treated as white for the purpose of DMT computation, lower bounds on the DMT of lower-triangular channel matrices are derived and the DMT of parallel MIMO channels is computed. All protocols appearing in the paper are explicit and rely only upon AF relaying. Half-duplex networks and explicit coding schemes are studied in a companion paper. [ABSTRACT FROM AUTHOR]

Two new schemes are proposed for transmitting a Gaussian source over a Gaussian channel. These schemes directly generalize previous results of Bross and Puri A scaled version of either the source itself or the quantization error is superimposed on the digital information, and thus serves as effective channel state information (CSI) unknown to the receiver. It is shown that for any power allocation between the coded and uncoded components of transmission, optimal distortion can be achieved by a continuum of auxiliary random variables (rather than only Costa's) if the decoded auxiliary codeword is properly used. This observation provides a new degree of freedom in point-to-point transmission. This freedom, in turn, can be utilized in multiterminal scenarios, as is demonstrated with an example. [ABSTRACT FROM AUTHOR]

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]

We study the problem of optimal reduced-dimension linear transform coding and reconstruction of a signal based on distributed correlated observations of the signal. In the mean square estimation context this involves finding the optimal signal representation based on multiple incomplete or only partial observations that are correlated. In particular, this leads to the study of finding the optimal Karhunen-Loève basis based on the censored observations. The problem has been considered previously by Gastpar, Dragotti, and Vetterli in the context of jointly Gaussian random variables based on using conditional covariances. In this paper, we derive the estimation results in the more general setting of second-order random variables with arbitrary distributions, using entirely different techniques based on the idea of innovations. We explicitly solve the single transform coder case, give a characterization of optimality in the multiple distributed transform coders scenario and provide additional insights into the structure of the problem. [ABSTRACT FROM AUTHOR]

A fundamental function performed by a sensory network is the retrieval of data gathered collectively by sensor nodes. The metrics that measure the efficiency of this data collection process are time and energy. In this paper, we study via simple discrete mathematical models, the statistics of the data collection time in sensory networks. Specifically, we analyze the average minimum delay in collecting randomly located/distributed sensors data for networks of various topologies when the number of nodes becomes large. Furthermore, we analyze the impact of various parameters such as size of packet, transmission range, and channel erasure probability on the optimal time performance. Our analysis applies to directional antenna systems as well as omnidirectional ones. This paper focuses on directional antenna systems and briefly presents results on omnidirectional antenna systems. Finally, a simple comparative analysis shows the respective advantages of the two systems. [ABSTRACT FROM AUTHOR]

Phase retrieval refers to algorithmic methods for recovering a signal from its phaseless measurements. There has been recent interest in understanding the performance of local search algorithms that work directly on the non-convex formulation of the problem. Due to the non-convexity of the problem, the success of these local search algorithms depends heavily on their starting points. The most widely used initialization scheme is the spectral method, in which the leading eigenvector of a data-dependent matrix is used as a starting point. Recently, the performance of the spectral initialization was characterized accurately for measurement matrices with independent and identically distributed entries. This paper aims to obtain the same level of knowledge for isotropically random column-orthogonal matrices, which are substantially better models for practical phase retrieval systems. Towards this goal, we consider the asymptotic setting in which the number of measurements $m$ , and the dimension of the signal, $n$ , diverge to infinity with $m/n = \delta \in (1,\infty)$ , and obtain a simple expression for the overlap between the spectral estimator and the true signal vector. [ABSTRACT FROM AUTHOR]

This paper studies convergence of empirical measures smoothed by a Gaussian kernel. Specifically, consider approximating $P\ast \mathcal {N}_\sigma $ , for $\mathcal {N}_\sigma \triangleq \mathcal {N}(0,\sigma ^{2} \mathrm {I}_{d})$ , by $\hat {P}_{n}\ast \mathcal {N}_\sigma $ under different statistical distances, where $\hat {P}_{n}$ is the empirical measure. We examine the convergence in terms of the Wasserstein distance, total variation (TV), Kullback-Leibler (KL) divergence, and $\chi ^{2}$ -divergence. We show that the approximation error under the TV distance and 1-Wasserstein distance ($\mathsf {W}_{1}$) converges at the rate $e^{O(d)} n^{-1/2}$ in remarkable contrast to a (typical) $n^{-\frac {1}{d}}$ rate for unsmoothed $\mathsf {W}_{1}$ (and $d\ge 3$). Similarly, for the KL divergence, squared 2-Wasserstein distance ($\mathsf {W}_{2}^{2}$), and $\chi ^{2}$ -divergence, the convergence rate is $e^{O(d)} n^{-1}$ , but only if $P$ achieves finite input-output $\chi ^{2}$ mutual information across the additive white Gaussian noise (AWGN) channel. If the latter condition is not met, the rate changes to $\omega \left ({n^{-1}}\right)$ for the KL divergence and $\mathsf {W}_{2}^{2}$ , while the $\chi ^{2}$ -divergence becomes infinite – a curious dichotomy. As an application we consider estimating the differential entropy $h(S+Z)$ , where $S\sim P$ and $Z\sim \mathcal {N}_\sigma $ are independent $d$ -dimensional random variables. The distribution $P$ is unknown and belongs to some nonparametric class, but n independently and identically distributed (i.i.d) samples from it are available. Despite the regularizing effect of noise, we first show that any good estimator (within an additive gap) for this problem must have a sample complexity that is exponential in d. We then leverage the above empirical approximation results to show that the absolute-error risk of the plug-in estimator converges as $e^{O(d)} n^{-1/2}$ , thus attaining the parametric rate in n. This establishes the plug-in estimator as minimax rate-optimal for the considered problem, with sharp dependence of the convergence rate both in n and d. We provide numerical results comparing the performance of the plug-in estimator to that of general-purpose (unstructured) differential entropy estimators (based on kernel density estimation (KDE) or k nearest neighbors (kNN) techniques) applied to samples of $S+Z$. These results reveal a significant empirical superiority of the plug-in to state-of-the-art KDE and kNN methods. As a motivating utilization of the plug-in approach, we estimate information flows in deep neural networks and discuss Tishby’s Information Bottleneck and the compression conjecture, among others. [ABSTRACT FROM AUTHOR]

Recently, two extensions of Wyner’s common information—exact and Rényi common informations—were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner’s and $\alpha $ -Rényi common informations, the relative entropy and Rényi divergence with order $\alpha $ were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner’s common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and $\infty $ -Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and $\infty $ -Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner’s. This answers an open problem posed by KLE. Furthermore, we extend Wyner’s, $\infty $ -Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources. [ABSTRACT FROM AUTHOR]

KSG mutual information estimator, which is based on the distances of each sample to its $k$ -th nearest neighbor, is widely used to estimate mutual information between two continuous random variables. Existing work has analyzed the convergence rate of this estimator for random variables whose densities are bounded away from zero in its support. In practice, however, KSG estimator also performs well for a much broader class of distributions, including not only those with bounded support and densities bounded away from zero, but also those with bounded support but densities approaching zero, and those with unbounded support. In this paper, we analyze the convergence rate of the error of KSG estimator for smooth distributions, whose support of density can be both bounded and unbounded. As KSG mutual information estimator can be viewed as an adaptive recombination of KL entropy estimators, in our analysis, we also provide convergence analysis of KL entropy estimator for a broad class of distributions. [ABSTRACT FROM AUTHOR]

The problem of finding a vector $\boldsymbol {x}$ which obeys a set of quadratic equations $| \boldsymbol {a}_{\text {k}}^\top \boldsymbol {x} |^{2}=\text {y}_{\text {k}}$ , $\text {k}=1,\cdots,\text {m}$ , plays an important role in many applications. In this paper we consider the case when both $\boldsymbol {x}$ and $\boldsymbol {a}_{k}$ are real-valued vectors of length n. A new loss function is constructed for this problem, which combines the smooth quadratic loss function with an activation function. Under the Gaussian measurement model, we establish that with high probability the target solution $\boldsymbol {x}$ is the only minimizer (up to a global sign) of the new loss function provided $\text {m}\gtrsim \text {n}$. Moreover, the loss function always has a negative directional curvature around its saddle points. [ABSTRACT FROM AUTHOR]

This paper provides conditions on the observation probability distribution in Bayesian localization and optimal filtering so that the conditional mean estimate satisfies convex stochastic dominance. Convex dominance allows us to compare the unconditional mean square error between two optimal Bayesian state estimators over arbitrary time horizons instead of using brute force Monte-Carlo computations. The proof uses two key ideas from microeconomics, namely, integral precision dominance and aggregation of single crossing. The convex dominance result is then used to give sufficient conditions so that the optimal policy of a controlled sensing two-state partially observed Markov decision process (POMDP) is lower bounded by a myopic policy. Numerical examples are presented where the Shannon capacity of the observation distribution using one sensor dominates that of another, and convex dominance holds but Blackwell dominance does not hold. These illustrate the usefulness of the main result in localization, filtering and controlled sensing applications. [ABSTRACT FROM AUTHOR]

Genomic evolution can be viewed as string-editing processes driven by mutations. An understanding of the statistical properties resulting from these mutation processes is of value in a variety of tasks related to biological sequence data, e.g., estimation of model parameters and compression. At the same time, due to the complexity of these processes, designing tractable stochastic models and analyzing them are challenging. In this paper, we study two kinds of systems, each representing a set of mutations. In the first system, tandem duplications and substitution mutations are allowed and in the other, interspersed duplications. We provide stochastic models and, via stochastic approximation, study the evolution of substring frequencies for these two systems separately. Specifically, we show that $k$ -mer frequencies converge almost surely and determine the limit set. Furthermore, we present a method for finding upper bounds on entropy for such systems. [ABSTRACT FROM AUTHOR]

In this paper, we study tail inequalities of the largest eigenvalue of a matrix infinitely divisible (i.d.) series, which is a finite sum of fixed matrices weighted by i.d. random variables. We obtain several types of tail inequalities, including Bennett-type and Bernstein-type inequalities. This allows us to further bound the expectation of the spectral norm of a matrix i.d. series. Moreover, by developing a new lower-bound function for $Q(s)=(s+1)\log (s+1)-s$ that appears in the Bennett-type inequality, we derive a tighter tail inequality of the largest eigenvalue of the matrix i.d. series than the Bernstein-type inequality when the matrix dimension is high. The resulting lower-bound function is of independent interest and can improve any Bennett-type concentration inequality that involves the function $Q(s)$. The class of i.d. probability distributions is large and includes Gaussian and Poisson distributions, among many others. Therefore, our results encompass the existing work on matrix Gaussian series as a special case. Lastly, we show that the tail inequalities of a matrix i.d. series have applications in several optimization problems including the chance constrained optimization problem and the quadratic optimization problem with orthogonality constraints. In addition, we also use the resulting tail bounds to show that random matrices constructed from i.d. random variables satisfy the restricted isometry property (RIP) when it acts as a measurement matrix in compressed sensing. [ABSTRACT FROM AUTHOR]

It is well known that superposition coding, namely separately encoding the independent sources, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999) for any $L\geq 2$ , where $L$ is the number of levels of the coding system. However, the characterization of the coding rate region therein involves uncountably many linear inequalities and the constant term (i.e., the lower bound) in each inequality is given in terms of the solution of a linear optimization problem. Thus this implicit characterization of the coding rate region does not enable the determination of the achievability of a given rate tuple. In principle, the achievability of a given rate tuple can be determined by direct computation, but the complexity is prohibitive even for $L=5$. In this paper, for any fixed $L$ , we obtain in closed form a finite set of linear inequalities for characterizing the coding rate region. We further show by the symmetry of the problem that only a much smaller subset of this finite set of inequalities needs to be verified in determining the achievability of a given rate tuple. Yet, the cardinality of this smaller set grows at least exponentially fast with $L$. We also present a subset entropy inequality, which together with our explicit characterization of the coding rate region, is sufficient for proving the optimality of superposition coding. [ABSTRACT FROM AUTHOR]

The entropy accumulation theorem states that the smooth min-entropy of an $n$ -partite system $A = (A_{1}, \ldots, A_{n})$ is lower-bounded by the sum of the von Neumann entropies of suitably chosen conditional states up to corrections that are sublinear in $n$. This theorem is particularly suited to proving the security of quantum cryptographic protocols, and in particular so-called device-independent protocols for randomness expansion and key distribution, where the devices can be built and preprogrammed by a malicious supplier. However, while the bounds provided by this theorem are optimal in the first order, the second-order term is bounded more crudely, in such a way that the bounds deteriorate significantly when the theorem is applied directly to protocols where parameter estimation is done by sampling a small fraction of the positions, as is done in most QKD protocols. The objective of this paper is to improve this second-order sublinear term and remedy this problem. On the way, we prove various bounds on the divergence variance, which might be of independent interest. [ABSTRACT FROM AUTHOR]

In 1959, Rényi proposed the information dimension and the $d$ -dimensional entropy to measure the information content of general random variables. This paper proposes a generalization of information dimension to stochastic processes by defining the information dimension rate as the entropy rate of the uniformly quantized stochastic process divided by minus the logarithm of the quantizer step size $1/m$ in the limit as $m\to \infty $. It is demonstrated that the information dimension rate coincides with the rate-distortion dimension, defined as twice the rate-distortion function $R(D)$ of the stochastic process divided by $-\log (D)$ in the limit as $D\downarrow 0$. It is further shown that among all multivariate stationary processes with a given (matrix-valued) spectral distribution function (SDF), the Gaussian process has the largest information dimension rate and the information dimension rate of multivariate stationary Gaussian processes is given by the average rank of the derivative of the SDF. The presented results reveal that the fundamental limits of almost zero-distortion recovery via compressible signal pursuit and almost lossless analog compression are different in general. [ABSTRACT FROM AUTHOR]

In this paper, a free deterministic equivalent is proposed for the capacity analysis of the multi-input multi-output (MIMO) multiple access channel (MAC) with a more general channel model compared to previous works. In particular, a MIMO MAC with one base station (BS) equipped with several distributed antenna sets is considered. Each link between a user and a BS antenna set forms a jointly correlated Rician fading channel. The analysis is based on operator-valued free probability theory, which broadens the range of applicability of free probability techniques tremendously. By replacing independent Gaussian random matrices with operator-valued random variables satisfying certain operator-valued freeness relations, the free deterministic equivalent of the considered channel Gram matrix is obtained. The Shannon transform of the free deterministic equivalent is derived, which provides an approximate expression for the ergodic input-output mutual information of the channel. The sum-rate capacity achieving input covariance matrices are also derived based on the approximate ergodic input-output mutual information. The free deterministic equivalent results are easy to compute, and simulation results show that these approximations are numerically accurate and computationally efficient. [ABSTRACT FROM PUBLISHER]

We consider low-density parity-check (LDPC) code ensembles over non-binary Galois fields when used for transmission over arbitrary discrete memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter, we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles. [ABSTRACT FROM AUTHOR]

In this paper, we investigate problems of communication over physically degraded, state-dependent broadcast channels (BCs) with cooperating decoders. Two different setups are considered, and their capacity regions are characterized. First, we study a setting in which one decoder can use a finite capacity link to send the other decoder information regarding the messages or the channel states. In this scenario, we analyze two cases: one, where noncausal state information, is available to the encoder and the strong decoder, and the other, where state information, is available only to the encoder in a causal manner. Second, we examine a setting in which the cooperation between the decoders is limited to taking place before the outputs of the channel are given. In this case, one decoder, which is informed of the state sequence noncausally, can cooperate only to send the other decoder rate-limited information about the state sequence. The proofs of the capacity regions introduce a new idea of coding for channels with cooperation between different users, where we exploit the link between the decoders for multiple binnings. Finally, we discuss the optimality of using rate-splitting techniques when coding for cooperative BCs. In particular, we show that rate splitting is not necessarily optimal when coding for cooperative BCs by solving an example in which our method of coding outperforms rate splitting. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of generating arbitrary three-party correlations from a combination of public and secret correlations. Two parties—called Alice and Bob—share perfectly correlated bits that are secret from a collaborating third party, Charlie. At the same time, all three parties have access to a separate source of correlated bits, and their goal is to convert these two resources into multiple copies of some given tripartite distribution \mathbb P(XYZ) . We obtain a single-letter characterization of the tradeoff between public and private bits that are needed to achieve this task. The rate of private bits is shown to generalize Wyner’s classic notion of common information held between a pair of random variables. The problem we consider can be contrasted fruitfully with the task of secrecy formation, in which \mathbb P(XYZ) is generated using public communication and local randomness but with Charlie functioning as an adversary instead of a collaborator. We describe in detail the differences between the collaborative and adversarial scenarios. [ABSTRACT FROM AUTHOR]

Explicit characterization of the capacity region of communication networks is a long-standing problem. While it is known that network coding can outperform routing and replication, the set of feasible rates is not known in general. Characterizing the network coding capacity region requires the determination of the set of all entropic vectors. Furthermore, computing the explicitly known linear programming bound is infeasible in practice due to an exponential growth in complexity as a function of network size. This paper focuses on the fundamental problems of characterization and computation of outer bounds for multi-source multi-sink networks. Starting from the known local functional dependence induced by the communication network, we introduce the notion of irreducible sets, which characterize implied functional dependence. We provide recursions for the computation of all maximal irreducible sets. These sets act as information-theoretic bottlenecks, and provide an easily computable outer bound for networks with correlated sources. We extend the notion of irreducible sets (and resulting outer bound) for networks with independent sources. We compare our bounds with existing bounds in the literature. We find that our new bounds are the best among the known graph theoretic bounds for networks with correlated sources and for networks with independent sources. [ABSTRACT FROM AUTHOR]

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, and more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton’s inner bound and the UV outer bound. [ABSTRACT FROM AUTHOR]

Wyner’s common information was originally defined for a pair of dependent discrete random variables. Its significance is largely reflected in, and also confined to, several existing interpretations in various source coding problems. This paper attempts to expand its practical significance by providing a new operational interpretation. In the context of the Gray–Wyner network, it is established that Wyner’s common information has a new lossy source coding interpretation. Specifically, it is established that, under suitable conditions, Wyner’s common information equals to the smallest common message rate when the total rate is arbitrarily close to the rate distortion function with joint decoding for the Gray–Wyner network. A surprising observation is that such equality holds independent of the values of distortion constraints as long as the distortions are within some distortion region. The new lossy source coding interpretation provides the first meaningful justification for defining Wyner’s common information for continuous random variables and the result can also be extended to that of multiple variables. Examples are given for characterizing the rate distortion region for the Gray–Wyner lossy source coding problem and for identifying conditions under which Wyner’s common information equals that of the smallest common rate. As a by-product, the explicit expression for the common information between a pair of Gaussian random variables is obtained. [ABSTRACT FROM AUTHOR]

Let X be an arbitrary continuous random variable and Z be an independent Gaussian random variable with zero mean and unit variance. For t>0 , Costa proved that is concave in t , where the proof hinged on the first and second order derivatives of h(X+\sqrt tZ) . In particular, these two derivatives are signed, i.e., ( \partial / \partial t)h(X+\sqrt tZ) \geq 0 and ( \partial ^2/ \partial t^2)h(X+\sqrt tZ) \leq 0 . In this paper, we show that the third order derivative of h(X+\sqrt tZ) is nonnegative, which implies that the Fisher information J(X+\sqrt tZ) is convex in t . We further show that the fourth order derivative of _{\vphantom {\{}} the first four derivatives, we make two conjectures on h(X+\sqrt tZ) : the first is that ({\partial ^{n}}/{\partial t^{n}}) h(X+\sqrt {t}Z)$ is nonnegative in t$ if n$ is odd, and nonpositive otherwise; the second is that is convex in t$ . The first conjecture can be rephrased in the context of completely monotone functions: t$ . The history of the first conjecture may date back to a problem in mathematical physics studied by McKean in 1966. Apart from these results, we provide a geometrical interpretation to the covariance-preserving transformation and study the concavity of , revealing its connection with Costa’s entropy power inequality. [ABSTRACT FROM PUBLISHER]

Mrs. Gerber’s Lemma lower bounds the entropy at the output of a binary symmetric channel in terms of the entropy of the input process. In this paper, we lower bound the output entropy via a different measure of input uncertainty, pertaining to the minimum mean squared error prediction cost of the input process. We show that in many cases our bound is tighter than the one obtained from Mrs. Gerber’s Lemma. As an application, we evaluate the bound for binary hidden Markov processes, and obtain new estimates for the entropy rate. [ABSTRACT FROM PUBLISHER]

Hilberg’s conjecture about natural language states that the mutual information between two adjacent long blocks of text grows like a power of the block length. The exponent in this statement can be upper bounded using the pointwise mutual information estimate computed for a carefully chosen code. The bound is the better, the lower the compression rate is, but there is a requirement that the code be universal. So as to improve a received upper bound for Hilberg’s exponent, in this paper, we introduce two novel universal codes, called the plain switch distribution and the preadapted switch distribution. Generally speaking, switch distributions are certain mixtures of adaptive Markov chains of varying orders with some additional communication to avoid the so-called catch-up phenomenon. The advantage of these distributions is that they both achieve a low compression rate and are guaranteed to be universal. Using the switch distributions, we obtain that a sample of a text in English is non-Markovian with Hilberg’s exponent being ≤0.83, which improves over the previous bound ≤0.94 obtained using the Lempel–Ziv code. [ABSTRACT FROM PUBLISHER]

In 1733, Georges-Louis Leclerc, Comte de Buffon in France, set the ground of geometric probability theory by defining an enlightening problem: what is the probability that a needle thrown randomly on a ground made of equispaced parallel strips lies on two of them? In this paper, we show that the solution to this problem, and its generalization to N dimensions, allows us to discover a quantized form of the Johnson-Lindenstrauss (JL) lemma, i.e., one that combines a linear dimensionality reduction procedure with a uniform quantization of precision \delta >0 . In particular, given a finite set \mathcal S \subset \mathbb R ^N of S points and a distortion level \epsilon >0 , as soon as M > M_{0} = O(\epsilon ^{-2} \log S) , we can (randomly) construct a mapping from ( \mathcal S, \ell _{2}) to ( \delta \mathbb Z^M, \ell 1) that approximately preserves the pairwise distances between the points of \mathcal S . Interestingly, compared with the common JL lemma, the mapping is quasi-isometric and we observe both an additive and a multiplicative distortions on the embedded distances. These two distortions, however, decay as O((\log S/M)^1/2) when M increases. Moreover, for coarse quantization, i.e., for high \delta compared with the set radius, the distortion is mainly additive, while for small \delta we tend to a Lipschitz isometric embedding. Finally, we prove the existence of a nearly quasi-isometric embedding of into ( \delta \mathbb Z^{M}, \ell _{2}) . This one involves a non-linear distortion of the \ell _{2}$ -distance in \mathcal S$ that vanishes for distant points in this set. Noticeably, the additive distortion in this case is slower, and decays as O((\log S/M)^{1/4}) . [ABSTRACT FROM PUBLISHER]

We consider the problem of channel state amplification in a Gaussian channel with additive Gaussian channel states, where the encoder observes noncausally a noisy version of these states. A complete characterization is provided for the minimum reconstruction distortion under a transmitter power constraint, and it is shown that a simple analog scheme with power control is optimal. More precisely, if the power available to the encoder is below certain threshold, the analog scheme using full power is optimal, however, when the power available to the encoder is above that threshold, analog transmission using only a fixed amount of the available power is optimal. Furthermore, the problem of simultaneous message transmission and Gaussian state amplification with noisy observations is studied, for which an inner bound and two nontrivial outer bounds to the optimal tradeoff between the transmission rate and the state reconstruction distortion are provided. The coding scheme underlying the inner bound combines analog signaling and Gelfand-Pinsker coding, where the latter deviates from the operating point of Costa’s dirty paper coding. The first outer bound is obtained by extending the channel decomposition technique, while the second outer bound requires a strategic analysis of the covariance matrix of the relevant random variables. [ABSTRACT FROM AUTHOR]

Non-locality is the phenomenon of observing strong correlations among the outcomes of local measurements of a multipartite physical system. No-signaling boxes are the abstract objects for studying non-locality, and wirings are local operations on the space of no-signaling boxes. This means that, no matter how non-local the nature is, the set of physical non-local correlations must be closed under wirings. Then, one approach to identify the non-locality of nature is to characterize the closed sets of non-local correlations. Although non-trivial examples of wirings of no-signaling boxes are known, there is no systematic way to study wirings. In particular, given a set of no-signaling boxes, we do not know a general method to prove that it is closed under wirings. In this paper, we propose the first general method to construct such closed sets of non-local correlations. We show that a well-known measure of correlation, called maximal correlation, when appropriately defined for non-local correlations, is monotonically decreasing under wirings. This establishes a conjecture about the impossibility of simulating isotropic boxes from each other, implying the existence of a continuum of closed sets of non-local boxes under wirings. To prove our main result, we introduce some mathematical tools that may be of independent interest: we define a notion of maximal correlation ribbon as a generalization of maximal correlation, and provide a connection between it and a known object called hypercontractivity ribbon; we show that these two ribbons are monotone under wirings too. [ABSTRACT FROM AUTHOR]

We consider two secret key generation problems under a pairwise independent network model, and propose low complexity key generation schemes in a framework that connects our problems to network flow problems in graphs. Our schemes have two components: 1) local key generation and 2) global key propagation. In the local key generation, we use point-to-point source coding with side information to establish pairwise keys, from which we construct a graph with the capacity of each edge being the key rate of the corresponding point-to-point local key. In the global key propagation, depending on the particular problem, secret keys are delivered to users in the network using various network flow algorithms. In particular, in the first problem in which one is required to generate a group key for a group of users in the network, we propose a network coding-based global key propagation approach. This approach has a low complexity and has a better performance than the existing approach. In the second problem, in which one is required to generate multiple keys simultaneously for different pairs of users, we propose a multicommodity flow-based global key propagation approach. We show that the proposed approach is optimal for the case of generating two keys. For the general case of generating more than two keys, we show that the sum rate of the proposed scheme is larger than an upper bound characterized in this paper divided by a constant. [ABSTRACT FROM AUTHOR]

Suppose $M$ records are replicated in $N$ servers (each storing all $M$ records), a user wants to privately retrieve one record by accessing the servers such that the identity of the retrieved record is secret against any up to $T$ servers. A scheme designed for this purpose is called a $T$ -private information retrieval (PIR) scheme. In practice, capacity-achieving and small sub-packetization are both desired for PIR schemes, because the former implies the highest download rate and the latter means simple realization. Meanwhile, sub-packetization is the key technique for achieving capacity. In this paper, we characterize the optimal sub-packetization for linear capacity-achieving $T$ -PIR schemes. First, a lower bound on the sub-packetization $L$ for linear capacity-achieving $T$ -PIR schemes is proved, i.e., $L\geq dn^{M-1}$ , where $d={\mathrm{ gcd}}(N,T)$ and $n=N/d$. Then, for general values of $M$ and $N>T\geq 1$ , a linear capacity-achieving $T$ -PIR scheme with sub-packetization $dn^{M-1}$ is designed. Comparing with the first capacity-achieving $T$ -PIR scheme given by Sun and Jafar in 2016, our scheme reduces the sub-packetization from $N^{M}$ to the optimal and further reduces the field size by a factor of $Nd^{M-2}$. [ABSTRACT FROM AUTHOR]