Search

The entropy power inequality (EPI) and the Brascamp-Lieb inequality (BLI) are fundamental inequalities concerning the differential entropies of linear transformations of random vectors. The EPI provides lower bounds for the differential entropy of linear transformations of random vectors with independent components. The BLI, on the other hand, provides upper bounds on the differential entropy of a random vector in terms of the differential entropies of some of its linear transformations. In this paper, we define a family of entropy functionals, which we show are subadditive. We then establish that Gaussians are extremal for these functionals by adapting a proof technique from Geng and Nair (2014). As a consequence, we obtain a new entropy inequality that generalizes both the BLI and EPI. By considering a variety of independence relations among the components of the random vectors appearing in these functionals, we also obtain families of inequalities that lie between the EPI and the BLI. [ABSTRACT FROM AUTHOR]

Aim of this short note is to study Shannon’s entropy power along entropic interpolations, thus generalizing Costa’s concavity theorem. We shall provide two proofs of independent interest: the former by $\Gamma $ -calculus, hence applicable to more abstract frameworks; the latter with an explicit remainder term, reminiscent of Villani (IEEE Trans. Inf. Theory, 2006), allowing us to characterize the case of equality. [ABSTRACT FROM AUTHOR]

Comparing probability distributions is an indispensable and ubiquitous task in machine learning and statistics. The most common way to compare a pair of Borel probability measures is to compute a metric between them, and by far the most widely used notions of metric are the Wasserstein metric and the total variation metric. The next most common way is to compute a divergence between them, and in this case almost every known divergences such as those of Kullback–Leibler, Jensen–Shannon, Rényi, and many more, are special cases of the $f$ -divergence. Nevertheless these metrics and divergences may only be computed, in fact, are only defined, when the pair of probability measures are on spaces of the same dimension. How would one quantify, say, a KL-divergence between the uniform distribution on the interval [−1, 1] and a Gaussian distribution on $\mathbb {R}^{3}$ ? We show that these common notions of metrics and divergences give rise to natural distances between Borel probability measures defined on spaces of different dimensions, e.g., one on $\mathbb {R}^{m}$ and another on $\mathbb {R}^{n}$ where $m, n$ are distinct, so as to give a meaningful answer to the previous question. [ABSTRACT FROM AUTHOR]

The mutual information (MI) of Gaussian multi-input multi-output (MIMO) channels has been evaluated by utilizing random matrix theory (RMT) and shown to asymptotically follow Gaussian distribution, where the ergodic mutual information (EMI) converges to a deterministic quantity. However, with non-Gaussian channels, there is a bias between the EMI and its deterministic equivalent (DE), whose evaluation is not available in the literature. This bias of the EMI is related to the bias for the trace of the resolvent in large RMT. In this paper, we first derive the bias for the trace of the resolvent, which is further extended to compute the bias for the linear spectral statistics (LSS). Then, we apply the above results on non-Gaussian MIMO channels to determine the bias for the EMI. It is also proved that the bias for the EMI is −0.5 times of that for the variance of the MI. Finally, the derived bias is utilized to modify the central limit theory (CLT) and calculate the outage probability. Numerical results show that the modified CLT significantly outperforms previous methods in approximating the distribution of the MI and improves the accuracy for the outage probability evaluation. [ABSTRACT FROM AUTHOR]

The generalized Box-Müller algorithm provides a methodology for generating q-Gaussian random variates, which generalizes the Gaussian $(q=1)$. The parameter $-\infty < {q}\le 3$ is related to the shape of the tail decay; ${q} < 1$ for compact-support including parabola $\left ({{q}={\it{ 0}} }\right)$ ; $1 < {q}\le 3$ for heavy-tail including Cauchy $\left ({{q}=2 }\right)$. This addendum clarifies the transformation ${q}^{\prime }=\frac {3{q}-1}{{q}+1}$ within the algorithm is due to a difference in the dimensions d of the generalized logarithm and the generalized distribution. The transformation is clarified by the decomposition of ${q}=1+\frac {2\kappa }{1+{d}\kappa }$ , where the shape parameter $-1 < \kappa \le \infty $ quantifies the magnitude $\vphantom {^{R}}$ of the deformation from exponential. A simpler specification for the generalized Box-Müller algorithm is provided using the shape of the tail decay. [ABSTRACT FROM AUTHOR]

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

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

We investigate shrinkage priors on power spectral densities for complex-valued circular-symmetric autoregressive processes. We construct shrinkage predictive power spectral densities, which asymptotically dominate (i) the Bayesian predictive power spectral density based on the Jeffreys prior and (ii) the estimative power spectral density with the maximum likelihood estimator, where the Kullback–Leibler divergence from the true power spectral density to a predictive power spectral density is adopted as a risk. Furthermore, we propose general constructions of objective priors for Kähler parameter spaces by utilizing a positive continuous eigenfunction of the Laplace–Beltrami operator with a negative eigenvalue. We present numerical experiments on a complex-valued stationary autoregressive model of order 1. [ABSTRACT FROM AUTHOR]

A single-index model is given by y = g*(< x, θ* >) + ε : The scalar response y depends on the covariate vector x both through an unknown (vector) parameter θ* as well as an unknown, non-parametric, univariate link-function g* ∈ G. We study the problem of recovering the parameter θ* from i.i.d. samples of the model when the covariates are drawn from a normal distribution. Our focus is on leveraging information about the (known) function class G in order to design a procedure that adapts to the noise level in the problem, thereby reducing the bias of parameter estimation. We show that when given access to a natural “labeling oracle”, our procedure recovers the underlying parameter at a rate that depends explicitly on how well we are able to estimate a suitably defined “inverse” link function. Both the procedure and its analysis framework are flexible, admitting any black-box estimator for the inverse link function. The resulting rate of parameter estimation significantly improves upon the risk of classical semi-parametric procedures whenever consistent estimates of the inverse link function can be obtained. When the function class G is appropriately structured and empirical risk minimization is used to estimate the inverse function, we provide quantitative upper bounds on the risk that depend on natural complexity measures of the class of inverse functions. We specialize our framework to the case where G is a sub-class of monotone single-index models, showing a computationally efficient, end-to-end algorithm that achieves very fast rates of parameter estimation in the regime in which the signal-to-noise ratio in the problem is large. We also pay particular attention to parameter identifiability in the noiseless model, deriving sharper upper bounds as well as information-theoretic lower bounds. Consequences for some unimodal SIMs and the (real) phase retrieval problem are also discussed. [ABSTRACT FROM AUTHOR]

This paper studies the performance of block coding on an additive white Gaussian noise channel under different power limitations at the transmitter. New lower bounds are presented for the minimum error probability of codes satisfying maximal and average power constraints. These bounds are tighter than previous results in the finite blocklength regime, and yield a better understanding on the structure of good codes under an average power limitation. Evaluation of these bounds for short and moderate blocklengths is also discussed. [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]

We consider the problem of recovering $n$ i.i.d. samples from a zero mean multivariate Gaussian distribution with an unknown covariance matrix, from their modulo wrapped measurements, i.e., measurements where each coordinate is reduced modulo $\Delta $ , for some $\Delta >0$. For this setup, which is motivated by quantization and analog-to-digital conversion, we develop a low-complexity iterative decoding algorithm. We show that if a benchmark informed decoder that knows the covariance matrix can recover each sample with small error probability, and $n$ is large enough, the performance of the proposed blind recovery algorithm closely follows that of the informed one. We complement the analysis with numerical results that show that the algorithm performs well even in non-asymptotic conditions. [ABSTRACT FROM AUTHOR]

The capacity of a complex and discrete-time memoryless additive white Gaussian noise (AWGN) channel under three constraints, namely, input average power, input amplitude and output delivered power is studied. The output delivered power constraint is modelled as the average of linear combination of even moments of the channel input being larger than a threshold. It is shown that the capacity of an AWGN channel under transmit average power and receiver delivered power constraints is the same as the capacity of an AWGN channel under an average power constraint. However, depending on the two constraints, the capacity can be either achieved by a Gaussian distribution or arbitrarily approached by using time-sharing between a Gaussian distribution and On-Off Keying. As an application, a simultaneous wireless information and power transfer (SWIPT) problem is studied, where an experimentally-validated nonlinear model of the harvester is used. It is shown that the delivered power depends on higher order moments of the channel input. Two inner bounds, one based on complex Gaussian inputs and the other based on further restricting the delivered power are obtained for the Rate-Power (RP) region. For Gaussian inputs, the optimal inputs are zero mean and a tradeoff between transmitted information and delivered power is recognized by considering asymmetric power allocations between inphase and quadrature subchannels. Through numerical algorithms, it is observed that input distributions (obtained by restricting the delivered power) attain larger RP region compared to Gaussian input counterparts. The benefits of the newly developed and optimized input distributions are also confirmed and validated through realistic circuit simulations. The results reveal the crucial role played by the energy harvester (EH) nonlinearity on SWIPT and provide new engineering guidelines on how to exploit this nonlinearity in the design of SWIPT modulation, signal and architecture. [ABSTRACT FROM AUTHOR]

The minimum description length (MDL) principle is extended to supervised learning. The MDL principle is a philosophy that the shortest description of given data leads to the best hypothesis about the data source. One of the key theories for the MDL principle is Barron and Cover’s theory (BC theory), which mathematically justifies the MDL principle based on two-stage codes in density estimation (unsupervised learning). Though the codelength of two-stage codes looks similar to the target function of penalized likelihood methods, parameter optimization of penalized likelihood methods is done without quantization of parameter space. Recently, Chatterjee and Barron have provided theoretical tools to extend BC theory to penalized likelihood methods by overcoming this difference. Indeed, applying their tools, they showed that the famous penalized likelihood method ‘lasso’ can be interpreted as an MDL estimator and enjoys performance guarantee by BC theory. An important fact is that their results assume a fixed design setting, which is essentially the same as unsupervised learning. The fixed design is natural if we use lasso for compressed sensing. If we use lasso for supervised learning, however, the fixed design is considerably unsatisfactory. Only random design is acceptable. However, it is inherently difficult to extend BC theory to the random design regardless of whether the parameter space is quantized or not. In this paper, a novel theoretical tool for extending BC theory to supervised learning (the random design setting and no quantization of parameter space) is provided. Applying this tool, when the covariates are subject to a Gaussian distribution, it is proved that lasso in the random design setting can also be interpreted as an MDL estimator, and that lasso enjoys the risk bound of BC theory. The risk/regret bounds obtained have several advantages inherited from BC theory. First, the bounds require remarkably few assumptions. Second, the bounds hold for any finite sample size $n$ and any finite feature number $p$ even if $n\ll p$. Behavior of the regret bound is investigated by numerical simulations. We believe that this is the first extensions of BC theory to supervised learning (random design). [ABSTRACT FROM AUTHOR]

We consider the phase retrieval problem, where the goal is to reconstruct an $n$ -dimensional complex vector from its phaseless scalar products with $m$ sensing vectors, independently sampled from complex normal distributions. We show that, if ${m}\geq Mn^{3/2}\log ^{7/2}n$ for some $M>0$ , then the classical algorithm of alternating minimization with random initialization succeeds with high probability as $n,m\rightarrow \infty $. This is a step toward proving the conjecture in, which conjectures that the algorithm succeeds when $m=O(n)$. The analysis depends on an approach that enables the decoupling of the dependency between the algorithmic iterates and the sensing vectors. [ABSTRACT FROM AUTHOR]

In this note we study a conjecture of Madiman and Wang which predicted that the generalized Gaussian distribution minimizes the Rényi entropy of the sum of independent random variables. Through a variational analysis, we show that the generalized Gaussian fails to be a minimizer for the problem. [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]

The discrete Fourier transform test is a randomness test included in NIST SP800-22. However, the variance of the test statistic is smaller than expected and the theoretical value of the variance is not known. Hitherto, the mechanism explaining why the former variance is smaller than expected has been qualitatively explained based on Parseval’s theorem. In this paper, we explore this quantitatively and derive the variance using Parseval’s theorem under particular assumptions. Numerical experiments are then used to show that this derived variance is robust. [ABSTRACT FROM AUTHOR]

It has been proved that for all stationary and ergodic processes the average Kolmogorov complexity of the first $n$ observations converges almost surely to its Shannon’s conditional entropy. This paper studies the convergence rate of this asymptotic result. In particular, we show that if the process satisfies certain mixing conditions, then a central limit theorem will be respected. Furthermore, we show that under slightly stronger mixing conditions one may obtain non-asymptotic concentration bounds for the Kolmogorov complexity. [ABSTRACT FROM AUTHOR]

We study a two-stage identification problem with pre-processing to enable efficient data retrieval and reconstruction. In the enrollment phase, users’ data are stored into the database in two layers. In the identification phase an observer obtains an observation, which originates from an unknown user in the enrolled database through a memoryless channel. The observation is sent for processing in two stages. In the first stage, the observation is pre-processed, and the result is then used in combination with the stored first layer information in the database to output a list of compatible users to the second stage. Then the second step uses the information of users contained in the list from both layers and the original observation sequence to return the exact user identity and a corresponding reconstruction sequence. The rate-distortion regions are characterized for both discrete and Gaussian scenarios. Specifically, for a fixed list size and distortion level, the compression-identification trade-off in the Gaussian scenario results in three different operating cases characterized by three auxiliary functions. While the choice of the auxiliary random variable for the first layer information is essentially unchanged when the identification rate is varied, the second one is selected based on the dominant function within those three. Due to the presence of a mixture of discrete and continuous random variables, the proof for the Gaussian case is highly non-trivial, which makes a careful measure theoretic analysis necessary. In addition, we study a connection of the previous setting to a two observer identification and a related problem with a lower bound for the list size, where the latter is motivated from privacy concerns. [ABSTRACT FROM AUTHOR]

The learning of mixture models can be viewed as a clustering problem. Indeed, given data samples independently generated from a mixture of distributions, we often would like to find the correct target clustering of the samples according to which component distribution they were generated from. For a clustering problem, practitioners often choose to use the simple $k$ -means algorithm. $k$ -means attempts to find an optimal clustering which minimizes the sum-of-squares distance between each point and its cluster center. In this paper, we consider fundamental (i.e., information-theoretic) limits of the solutions (clusterings) obtained by optimizing the sum-of-squares distance. In particular, we provide sufficient conditions for the closeness of any optimal clustering and the correct target clustering assuming that the data samples are generated from a mixture of spherical Gaussian distributions. We also generalize our results to log-concave distributions. Moreover, we show that under similar or even weaker conditions on the mixture model, any optimal clustering for the samples with reduced dimensionality is also close to the correct target clustering. These results provide intuition for the informativeness of $k$ -means (with and without dimensionality reduction) as an algorithm for learning mixture models. [ABSTRACT FROM AUTHOR]

We derive the optimal second-order rates in joint source-channel coding when the channel is a general discrete memoryless channel and the source is an irreducible and ergodic Markov process. In contrast, previous studies solved it only when the channel satisfies a certain unique-variance condition and the source is subject to an independent and identical distribution. We also compare the joint source-channel scheme with the separation scheme in the second-order regime, while a previous study made a notable comparison with numerical calculation. To discuss these two topics, we introduce two kinds of new distribution families, switched Gaussian convolution distribution and *-product distribution, which are defined by modifying the Gaussian distribution. [ABSTRACT FROM AUTHOR]

We prove that quantum thermal Gaussian input states minimize the output entropy of the multi-mode quantum Gaussian attenuators and amplifiers that are entanglement breaking and of the multi-mode quantum Gaussian phase contravariant channels among all the input states with an given entropy. This is the first time that this property is proven for a multi-mode channel without restrictions on the input states. A striking consequence of this result is a new lower bound on the output entropy of all the multi-mode quantum Gaussian attenuators and amplifiers in terms of the input entropy. We apply this bound to determine new upper bounds to the communication rates in two different scenarios. The first is classical communication to two receivers with the quantum degraded Gaussian broadcast channel. The second is the simultaneous classical communication, quantum communication and entanglement generation or the simultaneous public classical communication, private classical communication, and quantum key distribution with the Gaussian quantum-limited attenuator. [ABSTRACT FROM AUTHOR]

We develop a general method for computing logarithmic and log-gamma expectations of distributions. As a result, we derive series expansions and integral representations of the entropy for several fundamental distributions, including the Poisson, binomial, beta-binomial, negative binomial, and hypergeometric distributions. Our results also establish connections between the entropy functions and to the Riemann zeta function and its generalizations. [ABSTRACT FROM AUTHOR]

Sampling from the lattice Gaussian distribution plays an important role in various research fields. In this paper, the Markov chain Monte Carlo (MCMC)-based sampling technique is advanced in several fronts. First, the spectral gap for the independent Metropolis-Hastings-Klein (MHK) algorithm is derived, which is then extended to Peikert’s algorithm and rejection sampling; we show that independent MHK exhibits faster convergence. Then, the performance of bounded distance decoding (BDD) using MCMC is analyzed, revealing a flexible trade-off between the decoding radius and complexity. MCMC is further applied to trapdoor sampling, again offering a trade-off between security and complexity. Finally, the independent multiple-try Metropolis-Klein (MTMK) algorithm is proposed to enhance the convergence rate. The proposed algorithms allow parallel implementation, which is beneficial for practical applications. [ABSTRACT FROM AUTHOR]

The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding is employed. We extend Lapidoth’s analysis in several directions in this paper. First, we consider refined asymptotics. In particular, when the source is stationary and memoryless, we establish the second-order, moderate, and large deviation asymptotics of the problem. Second, by random Gaussian codebook, Lapidoth referred to a collection of random codewords, each of which is drawn independently and uniformly from the surface of an $n$ -dimensional sphere. To be more precise, we term this as a spherical codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product Gaussian distribution. We derive the second-order, moderate, and large deviation asymptotics when i.i.d. Gaussian codebooks are employed. In contrast to the recent work on the channel coding counterpart by Scarlett, Tan, and Durisi (2017), the dispersions for spherical and i.i.d. Gaussian codebooks are identical. The ensemble excess-distortion exponents for both spherical and i.i.d. Gaussian codebooks are established for all rates. Furthermore, we show that the i.i.d. Gaussian codebook has a strictly larger excess-distortion exponent than its spherical counterpart for any rate greater than the ensemble rate-distortion function derived by Lapidoth. [ABSTRACT FROM AUTHOR]

In this paper, we show that any sequence of infinite lattice constellations which is good for the unconstrained Gaussian channel can be shaped into a capacity-achieving sequence of codes for the power-constrained Gaussian channel under lattice decoding and non-uniform signaling. Unlike previous results in the literature, our scheme holds with no extra condition on the lattices (e.g., quantization-goodness or vanishing flatness factor), thus establishing a direct implication between AWGN-goodness, in the sense of Poltyrev and capacity-achieving codes. Our analysis uses properties of the discrete Gaussian distribution in order to obtain precise bounds on the probability of error and achievable rates. In particular, we obtain a simple characterization of the finite-blocklength behavior of the scheme, showing that it approaches the optimal dispersion coefficient for high signal-to-noise ratio. We further show that for low signal-to-noise ratio, the discrete Gaussian over centered lattice constellations cannot achieve capacity, and thus a shift (or “dither”) is essentially necessary. [ABSTRACT FROM AUTHOR]

Sparse linear inverse problems appear in a variety of settings, but often the noise contaminating observations cannot accurately be described as bounded by or arising from a Gaussian distribution. Poisson observations in particular are a characteristic feature of several real-world applications. Previous work on sparse Poisson inverse problems encountered several limiting technical hurdles. This paper describes a novel alternative analysis approach for sparse Poisson inverse problems that 1) sidesteps the technical challenges present in previous work, 2) admits estimators that can readily be computed using off-the-shelf LASSO algorithms, and 3) hints at a general framework for broad classes of noise in sparse linear inverse problems. At the heart of this new approach lies a weighted LASSO estimator for which data-dependent weights are based on Poisson concentration inequalities. Unlike previous analyses of the weighted LASSO, the proposed analysis depends on conditions which can be checked or shown to hold in general settings with high probability. 2000 Math Subject Classification: 60E15, 62G05, 62G08, and 94A12. [ABSTRACT FROM AUTHOR]

For generalized gamma probability densities, this paper studies the monotonicity of step sizes of optimal symmetric uniform scalar quantizers with respect to mean squared-error distortion. The principal results are that for the special cases of Gaussian, Laplacian, two-sided Rayleigh, and gamma densities, optimal step size monotonically decreases when the number of levels $N$ increases by two, and that for any generalized gamma density and all sufficiently large $N$ , optimal step size again decreases when $N$ increases by two. Also, it is shown that for a Laplacian density and sufficiently large $N$ , optimal step size decreases when $N$ increases by just one. [ABSTRACT FROM AUTHOR]

We investigate the problem of estimating a random variable $Y$ under a privacy constraint dictated by another correlated random variable $X$. When $X$ and $Y$ are discrete, we express the underlying privacy-utility tradeoff in terms of the privacy-constrained guessing probability ${\mathcal {h}}(P_{XY}, \varepsilon)$ , and the maximum probability $\mathsf {P}_{\mathsf {c}}(Y|Z)$ of correctly guessing $Y$ given an auxiliary random variable $Z$ , where the maximization is taken over all $P_{Z|Y}$ ensuring that $\mathsf {P}_{\mathsf {c}}(X|Z)\leq \varepsilon $ for a given privacy threshold $\varepsilon \geq 0$. We prove that ${\mathcal {h}}(P_{XY}, \cdot)$ is concave and piecewise linear, which allows us to derive its expression in closed form for any $\varepsilon $ when $X$ and $Y$ are binary. In the non-binary case, we derive ${\mathcal {h}}(P_{XY}, \varepsilon)$ in the high-utility regime (i.e., for sufficiently large, but nontrivial, values of $\varepsilon $) under the assumption that $Y$ and $Z$ have the same alphabets. We also analyze the privacy-constrained guessing probability for two scenarios in which $X$ , $Y$ , and $Z$ are binary vectors. When $X$ and $Y$ are continuous random variables, we formulate the corresponding privacy-utility tradeoff in terms of ${\mathsf {sENSR}}(P_{XY}, \varepsilon)$ , the smallest normalized minimum mean squared-error (mmse) incurred in estimating $Y$ from a Gaussian perturbation $Z$. Here, the minimization is taken over a family of Gaussian perturbations $Z$ for which the mmse of $f(X)$ given $Z$ is within a factor $1- \varepsilon $ from the variance of $f(X)$ for any non-constant real-valued function $f$. We derive tight upper and lower bounds for ${\mathsf {sENSR}}$ when $Y$ is Gaussian. For general absolutely continuous random variables, we obtain a tight lower bound for ${\mathsf {sENSR}}(P_{XY}, \varepsilon)$ in the high privacy regime, i.e., for small $\varepsilon $. [ABSTRACT FROM AUTHOR]

In some applications, the variance of additive measurement noise depends on the signal that we aim to measure. For instance, additive signal-dependent Gaussian noise (ASDGN) channel models are used in molecular and optical communication. Herein, we provide lower and upper bounds on the capacity of additive signal-dependent noise (ASDN) channels. The first lower bound is based on an extension of majorization inequalities, and the second lower bound utilizes the properties of the differential entropy. The lower bounds are valid for arbitrary ASDN channels. The upper bound is based on a previous idea of the authors (“symmetric relative entropy”) and is applied to the ASDGN channels. These bounds indicate that in the ASDN channels (unlike the classical additive white Gaussian noise channels), the capacity does not necessarily become larger by reducing the noise variance function. We also provide sufficient conditions under which the capacity becomes infinite. This is complemented by some conditions implying that the capacity is finite, and a unique capacity achieving measure exists (in the sense of the output measure). [ABSTRACT FROM AUTHOR]

We propose a coding scheme that achieves the capacity of the compound MIMO channel with algebraic lattices. Our lattice construction exploits the multiplicative structure of number fields and their group of units to absorb ill-conditioned channel realizations. To shape the constellation, a discrete Gaussian distribution over the lattice points is applied. These techniques, along with algebraic properties of the proposed lattices, are then used to construct a sub-optimal de-coupled coding scheme that achieves a constant gap to compound capacity by decoding in a lattice that does not dependent on the channel realization. The gap is characterized in terms of algebraic invariants of the code and is shown to be significantly smaller than previous schemes in the literature. We also exhibit alternative algebraic constructions that achieve the capacity of ergodic (SISO) fading channels. [ABSTRACT FROM AUTHOR]

We study high-dimensional signal recovery from non-linear measurements with design vectors having elliptically symmetric distribution. Special attention is devoted to the situation when the unknown signal belongs to a set of low statistical complexity, while both the measurements and the design vectors are heavy-tailed. We propose and analyze a new estimator that adapts to the structure of the problem, while being robust both to the possible model misspecification characterized by arbitrary non-linearity of the measurements as well as to data corruption modeled by the heavy-tailed distributions. Moreover, this estimator has low computational complexity. Our results are expressed in the form of exponential concentration inequalities for the error of the proposed estimator. On the technical side, our proofs rely on the generic chaining methods, and illustrate the power of this approach for statistical applications. Theory is supported by numerical experiments demonstrating that our estimator outperforms existing alternatives when data are heavy-tailed. [ABSTRACT FROM AUTHOR]

We consider the problem of recovering sparse vectors from underdetermined linear measurements via $\ell _{p}$ -constrained basis pursuit. Previous analyses of this problem based on generalized restricted isometry properties have suggested that two phenomena occur if $p\neq 2$. First, one may need substantially more than $s \log (en/s)$ measurements (optimal for $p=2$ ) for uniform recovery of all $s$ -sparse vectors. Second, the matrix that achieves recovery with the optimal number of measurements may not be Gaussian (as for $p=2$ ). We present a new, direct analysis, which shows that in fact neither of these phenomena occur. Via a suitable version of the null space property, we show that a standard Gaussian matrix provides $\ell _{q}/\ell _{1}$ -recovery guarantees for $\ell _{p}$ -constrained basis pursuit in the optimal measurement regime. Our result extends to several heavier-tailed measurement matrices. As an application, we show that one can obtain a consistent reconstruction from uniform scalar quantized measurements in the optimal measurement regime. [ABSTRACT FROM AUTHOR]

We consider a phase retrieval problem, where we want to reconstruct a $n$ -dimensional vector from its phaseless scalar products with $m$ sensing vectors, independently sampled from complex normal distributions. We show that, with a suitable initialization procedure, the classical algorithm of alternating projections (Gerchberg–Saxton) succeeds with high probability when $m\geq Cn$ , for some $C>0$ . We conjecture that this result is still true when no special initialization procedure is used, and present numerical experiments that support this conjecture. [ABSTRACT FROM PUBLISHER]

Consider a Gaussian multiple-input multiple-output (MIMO) multiple-access channel (MAC) with channel matrix \mathbf H and a Gaussian MIMO broadcast channel (BC) with channel matrix \mathbf H ^\mathsf T . For the MIMO MAC, the integer-forcing architecture consists of first decoding integer-linear combinations of the transmitted codewords, which are then solved for the original messages. For the MIMO BC, the integer-forcing architecture consists of pre-inverting the integer-linear combinations at the transmitter, so that each receiver can obtain its desired codeword by decoding an integer-linear combination. In both the cases, integer-forcing offers higher achievable rates than zero-forcing while maintaining a similar implementation complexity. This paper establishes an uplink-downlink duality relationship for integer-forcing, i.e., any sum rate that is achievable via integer-forcing on the MIMO MAC can be achieved via integer-forcing on the MIMO BC with the same sum power and vice versa. Using this duality relationship, it is shown that integer-forcing can operate within a constant gap of the MIMO BC sum capacity. Finally, the paper proposes a duality-based iterative algorithm for the non-convex problem of selecting optimal beamforming and equalization vectors, and establishes that it converges to a local optimum. [ABSTRACT FROM PUBLISHER]

In this paper, an explicit scheme of wiretap coding based on polar lattices is proposed to achieve the secrecy capacity of the additive white Gaussian noise (AWGN) wiretap channel. First, polar lattices are used to construct secrecy-good lattices for the mod- \Lambda s Gaussian wiretap channel (GWC). Then, we propose an explicit shaping scheme to remove this mod- \Lambda s front end and extend polar lattices to the genuine GWC. The shaping technique is based on the lattice Gaussian distribution, which leads to a binary asymmetric channel at each level for the multilevel lattice codes. By employing the asymmetric polar coding technique, we construct an AWGN-good lattice and a secrecy-good lattice with optimal shaping simultaneously. As a result, the encoding complexity for the sender and the decoding complexity for the legitimate receiver are both $O(N\log N\log (\log N))$ . The proposed scheme is proven to be semantically secure. [ABSTRACT FROM PUBLISHER]

Lattices possess elegant mathematical properties which have been previously used in the literature to show that structured codes can be efficient in a variety of communication scenarios, including coding for the additive white Gaussian noise channel, dirty-paper channel, Wyner–Ziv coding, coding for relay networks, and so forth. We consider the family of single-transmitter multiple-receiver Gaussian channels, where the source transmits a set of common messages to all the receivers (multicast scenario), and each receiver has coded side information, i.e., prior information in the form of linear combinations of the messages. This channel model is motivated by applications to multi-terminal networks, where the nodes may have access to coded versions of the messages from previous signal hops or through orthogonal channels. The capacity of this channel is known and follows from the work of Tuncel (2006), which is based on random coding arguments. In this paper, following the approach of Erez and Zamir, we design lattice codes for this family of channels when the source messages are symbols from a finite field \mathbb Fp of prime size. Our coding scheme utilizes Construction A lattices designed over the same prime field \mathbb Fp , and uses algebraic binning at the decoders to expurgate the channel code and obtain good lattice subcodes, for every possible set of linear combinations available as side information. The achievable rate of our coding scheme is a function of the size $p$ of underlying prime field, and approaches the capacity as $p$ tends to infinity. [ABSTRACT FROM PUBLISHER]

In this paper, we give a complete answer to the conjecture on restricted isometry property (RIP) constants \delta tk (00,\,\,\delta tk<({t}/({4-t}))+\epsilon cannot guarantee the exact recovery of some k -sparse signals. Furthermore, it will be shown that similar characterizations also hold for low-rank matrix recovery. Thus, combined with T. Cai and A. Zhang’s work, a complete characterization for sharp RIP constants \delta _{tk} for all t > 0$ is obtained to guarantee the exact recovery of all k$ -sparse signals and matrices with rank at most k$ by -norm minimization and nuclear norm minimization, respectively. Noisy cases and approximately sparse cases are also considered. To solve the conjecture, we construct a few identities so that RIP of order $tk$ , which is the target of our main results, can be perfectly applied to them. [ABSTRACT FROM PUBLISHER]

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

Sampling from the lattice Gaussian distribution has emerged as an important problem in coding, decoding, and cryptography. In this paper, the classic Metropolis-Hastings (MH) algorithm in Markov chain Monte Carlo methods is adopted for lattice Gaussian sampling. Two MH-based algorithms are proposed, which overcome the limitation of Klein’s algorithm. The first one, referred to as the independent Metropolis-Hastings-Klein (MHK) algorithm, establishes a Markov chain via an independent proposal distribution. We show that the Markov chain arising from this independent MHK algorithm is uniformly ergodic, namely, it converges to the stationary distribution exponentially fast regardless of the initial state. Moreover, the rate of convergence is analyzed in terms of the theta series, leading to predictable mixing time. A symmetric Metropolis-Klein algorithm is also proposed, which is proven to be geometrically ergodic. [ABSTRACT FROM AUTHOR]

The Riemannian geometry of covariance matrices has been essential to several successful applications, in computer vision, biomedical signal and image processing, and radar data processing. For these applications, an important ongoing challenge is to develop Riemannian-geometric tools which are adapted to structured covariance matrices. This paper proposes to meet this challenge by introducing a new class of probability distributions, Gaussian distributions of structured covariance matrices. These are Riemannian analogs of Gaussian distributions, which only sample from covariance matrices having a preassigned structure, such as complex, Toeplitz, or block-Toeplitz. The usefulness of these distributions stems from three features: 1) they are completely tractable, analytically, or numerically, when dealing with large covariance matrices; 2) they provide a statistical foundation to the concept of structured Riemannian barycentre (i.e., Fréchet or geometric mean); and 3) they lead to efficient statistical learning algorithms, which realise, among others, density estimation and classification of structured covariance matrices. This paper starts from the observation that several spaces of structured covariance matrices, considered from a geometric point of view, are Riemannian symmetric spaces. Accordingly, it develops an original theory of Gaussian distributions on Riemannian symmetric spaces, of their statistical inference, and of their relationship to the concept of Riemannian barycentre. Then, it uses this original theory to give a detailed description of Gaussian distributions of three kinds of structured covariance matrices, complex, Toeplitz, and block-Toeplitz. Finally, it describes algorithms for density estimation and classification of structured covariance matrices, based on Gaussian distribution mixture models. [ABSTRACT FROM AUTHOR]

This paper considers a Gaussian channel with one transmitter and two receivers. The goal is to maximize the communication rate at the intended/primary receiver subject to a disturbance constraint at the unintended/secondary receiver. The disturbance is measured in terms of the minimum mean square error (MMSE) of the interference that the transmission to the primary receiver inflicts on the secondary receiver. This paper presents a new upper bound for the problem of maximizing the mutual information subject to an MMSE constraint. The new bound holds for vector inputs of any length and recovers a previously known limiting (when the length of the vector input tends to infinity) expression from the work of Bustin et al. The key technical novelty is a new upper bound on the MMSE. This bound allows one to bound the MMSE for all signal-to-noise ratio (SNR) values below a certain SNR at which the MMSE is known (which corresponds to the disturbance constraint). The bound also complements the “single-crossing point property” of the MMSE that upper bounds the MMSE for all SNR values above a certain value at which the MMSE value is known. The MMSE upper bound provides a refined characterization of the phase-transition phenomenon, which manifests, in the limit as the length of the vector input goes to infinity, as a discontinuity of the MMSE for the problem at hand. For vector inputs of size n=1 , a matching lower bound, to within an additive gap of order O ( \log \log ({1}/{\sf MMSE}) ) (where {\sf MMSE}$ is the disturbance constraint), is shown by means of the mixed inputs technique recently introduced by Dytso et al. [ABSTRACT FROM PUBLISHER]

We show a direct relationship between the variance and the differential entropy for subclasses of symmetric and asymmetric unimodal distributions by providing an upper bound on variance in terms of entropy power. Combining this bound with the well-known entropy power lower bound on variance, we prove that the variance of the appropriate subclasses of unimodal distributions can be bounded below and above by the scaled entropy power. As the differential entropy decreases, the variance is sandwiched between two exponentially decreasing functions in the differential entropy. This establishes that for the subclasses of unimodal distributions, the differential entropy can be used as a surrogate for concentration of the distribution. [ABSTRACT FROM PUBLISHER]

This paper investigates a joint source-channel secrecy problem for the Shannon cipher broadcast system. We suppose list secrecy is applied, i.e., a wiretapper is allowed to produce a list of reconstruction sequences and the secrecy is measured by the minimum distortion over the entire list. For discrete communication cases, we propose a permutation-based uncoded scheme, which cascades a random permutation with a symbol-by-symbol mapping. Using this scheme, we derive an inner bound for the admissible region of secret key rate, list rate, wiretapper distortion, and distortions of legitimate users. For the converse part, we easily obtain an outer bound for the admissible region from an existing result. Comparing the outer bound with the inner bound shows that the proposed scheme is optimal under certain conditions. Besides, we extend the proposed scheme to the scalar and vector Gaussian communication scenarios, and characterize the corresponding performance as well. For these two cases, we also propose another uncoded scheme, orthogonal-transform-based scheme, which achieves the same performance as the permutation-based scheme. Interestingly, by introducing the random permutation or the random orthogonal transform into the traditional uncoded scheme, the proposed uncoded schemes, on one hand, provide a certain level of secrecy, and on the other hand, do not lose any performance in terms of the distortions for legitimate users. [ABSTRACT FROM PUBLISHER]

We construct two new infinite families of trace codes of dimension 2m , over the ring \mathbb {F}_{p}+u\mathbb {F}_{p} , with u^{2}=u , when p is an odd prime. They have the algebraic structure of abelian codes. Their Lee weight distribution is computed by using Gauss sums. By Gray mapping, we obtain two infinite families of linear p -ary codes of respective lengths and 2(p^m-1)^2 . When m is singly even, the first family gives five-weight codes. When m is odd and p\equiv 3 \pmod {4} , the first family yields p$ -ary two-weight codes, which are shown to be optimal by application of the Griesmer bound. The second family consists of two-weight codes that are shown to be optimal, by the Griesmer bound, whenever $p=3$ and $m \ge 3$ , or $p\ge 5$ and $m\ge 4$ . Applications to secret sharing schemes are given. [ABSTRACT FROM PUBLISHER]

We study the spherical cap packing problem with a probabilistic approach. Such probabilistic considerations result in an asymptotic sharp universal uniform bound on the maximal inner product between any set of unit vectors and a stochastically independent uniformly distributed unit vector. When the set of unit vectors are themselves independently uniformly distributed, we further develop the extreme value distribution limit of the maximal inner product, which characterizes its uncertainty around the bound. As applications of the above-mentioned asymptotic results, we derive: 1) an asymptotic sharp universal uniform bound on the maximal spurious correlation, as well as its uniform convergence in distribution when the explanatory variables are independently Gaussian distributed and 2) an asymptotic sharp universal bound on the maximum norm of a low-rank elliptically distributed vector, as well as related limiting distributions. With these results, we develop a fast detection method for a low-rank structure in high-dimensional Gaussian data without using the spectrum information. [ABSTRACT FROM PUBLISHER]

We address the problem of compressed sensing (CS) with prior information: reconstruct a target CS signal with the aid of a similar signal that is known beforehand, our prior information. We integrate the additional knowledge of the similar signal into CS via \ell 1 - \ell 1 and \ell 1 - \ell 2 minimization. We then establish bounds on the number of measurements required by these problems to successfully reconstruct the original signal. Our bounds and geometrical interpretations reveal that if the prior information has good enough quality, \ell 1 - \ell 1 minimization improves the performance of CS dramatically. In contrast, \ell 1 - \ell 2 minimization has a performance very similar to classical CS, and brings no significant benefits. In addition, we use the insight provided by our bounds to design practical schemes to improve prior information. All our findings are illustrated with experimental results. [ABSTRACT FROM PUBLISHER]

We derive the probability that all eigenvalues of a random matrix M lie within an arbitrary interval [a,b] , \psi (a,b)\triangleq \Pr \{a\leq \lambda _{\min }({\text{M}}), \lambda _{\max }({\text{M}})\leq b\} , when M is a real or complex finite-dimensional Wishart, double Wishart, or Gaussian symmetric/Hermitian matrix. We give efficient recursive formulas allowing the exact evaluation of \psi (a,b)$ for Wishart matrices, even with a large number of variates and degrees of freedom. We also prove that the probability that all eigenvalues are within the limiting spectral support (given by the Marčenko-Pastur or the semicircle laws) tends for large dimensions to the universal values 0.6921 and 0.9397 for the real and complex cases, respectively. Applications include improved bounds for the probability that a Gaussian measurement matrix has a given restricted isometry constant in compressed sensing. [ABSTRACT FROM PUBLISHER]

We study the capacity region of the two-user binary fading (or erasure) interference channel, where the transmitters have no knowledge of the channel state information. We develop new inner bounds and outer bounds for this problem. We identify three regimes based on the channel parameters: weak, moderate, and strong interference regimes. Interestingly, this is similar to the generalized degrees of freedom of the two-user Gaussian interference channel, where transmitters have perfect channel knowledge. We show that for the weak interference regime, treating interference as erasure is optimal while for the strong interference regime, decoding interference is optimal. For the moderate interference regime, we provide new inner and outer bounds. The inner bound is based on a modification of the Han–Kobayashi scheme for the erasure channel, enhanced by time-sharing. We study the gap between our inner bound and our outer bounds for the moderate interference regime and compare our results to that of the Gaussian interference channel. Deriving our new outer bounds has three main steps. We first create a contracted channel that has fewer states compared with the original channel, in order to make the analysis tractable. We then prove the correlation lemma that shows an outer bound on the capacity region of the contracted channel and also serves as an outer bound for the original channel. Finally, using the conditional entropy leakage lemma, we derive our outer bound on the capacity region of the contracted channel. [ABSTRACT FROM AUTHOR]