We study the problem of testing the goodness of fit of occurrences of items from many categories to a Poisson distribution uniform over the categories, against a class of alternative hypotheses obtained by the removal of an ℓ<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>p</i></sub> ball, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> ≤ 2, of radius ϵ around the sequence of uniform Poisson rates. We characterize the minimax risk for this problem as the expected number of samples <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> and the number of categories <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> go to infinity. Our result enables the comparison at the constant level of the many estimators previously proposed for this problem, rather than at the rate of convergence of the risk or the scaling order of the sample complexity. The minimax test relies exclusively on collisions in the small sample limit but behaves like the chisquared test otherwise. Empirical studies over a range of problem parameters show that the asymptotic risk estimate is accurate in finite samples and that the minimax test is significantly better than the chisquared test or a test that only uses collisions. Our analysis involves the reduciion to a structured subset of alternatives, establishing asymptotic normality for linear statistics, and solving an optimization problem over <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>-dimensional sequences that parallels classical results from Gaussian white noise models.

The gain in the log-likelihood (LLG) of a text under a language model (LM) when the text's summary is provided as a context to the LM, compared to no summary in the context, has been proposed as a reference-free index for the relevance of the summary to the text. We provide an information-theoretic interpretation of the LLG and an empirical analysis of the parts of speech affecting it most. We first show that the LLG describes the reduction in the binary codelength when the summary text is provided as side information to a lossless text compression system involving the LM and an entropy encoder. Consequently, under proper normalization, LLG is a form of the Normalized Compression Distance (NCD) and thus adheres to a universal information distance that is motivated by algorithmic information theory. Empirical results show that an NCD based on LLG is better correlated with human annotators than a gzip-based NCD. Additionally, we empirically show that LLG is affected almost exclusively by tokens associated with the text's content rather than tokens associated with its structure. Our findings support LLG as a natural and useful metric for evaluating text summarization methods.

Rare/Weak models for multiple hypothesis testing assume that only a small proportion of the tested hypotheses concern non-null effects and the individual signals are only moderately large, so that they generally do not stand out individually above the noise level. Such models have been studied in quite a few settings, for example in some cases studies focused on underlying Gaussian means model for the hypotheses being tested; in some others, Poisson. It seems not to have been noticed before that such seemingly different models have asymptotically the following common structure: Summarizing the evidence each test provides by the negative logarithm of its P-value, previous rare/weak model settings are asymptotically equivalent to detection where most negative log P-values have a standard exponential distribution but a small fraction of the P-values might have an alternative distribution which is moderately larger; we do not know which individual tests those might be, or even if there are any such. Moreover, the alternative distribution is approximately noncentral chisquared on one degree of freedom. We characterize the asymptotic performance of several global tests combining these P-values using a phase diagram analysis involving the log-chisquared mixture parameters. Interestingly, the log-chisquared approximation for P-values we use here is different from a classical analysis proposing the log-normal approximation which would be unsuitable for understanding rare/weak multiple testing models.

We consider the problem of estimating the mean of a symmetric log-concave distribution under the constraint that only a single bit per sample from this distribution is available to the estimator. We study the mean squared error as a function of the sample size (and hence the number of bits). We consider three settings: first, a centralized setting, where an encoder may release$n$bits given a sample of size$n$, and for which there is no asymptotic penalty for quantization; second, an adaptive setting in which each bit is a function of the current observation and previously recorded bits, where we show that the optimal relative efficiency compared to the sample mean is precisely the efficiency of the median; lastly, we show that in a distributed setting where each bit is only a function of a local sample, no estimator can achieve optimal efficiency uniformly over the parameter space. We additionally complement our results in the adaptive setting by showing thatoneround of adaptivity is sufficient to achieve optimal mean-square error.

We propose a method to perform two-sample tests on discrete distributions, i.e., an unsupervised discriminator testing whether two frequency tables were each sampled from a single unspecified probability distribution. Our proposal takes feature-by-feature P-values based on a binomial allocation model, and combines the P-values using Higher Criticism. Performance on real-world data (e.g. authorship attribution challenges) shows this to be an effective unsupervised untrained discriminator even in violations of the binomial allocation model. The method has interesting theoretical properties, in the ‘rare/weak departures’ setting where, if two distributions are actually different, they differ only in relatively few features and only by relatively subtle amounts. We perform a phase diagram analysis in which the phase space quantifies how rare and how weak such departures are. Although our proposal does not require any formal specification of an alternative hypothesis, nor does it require any specification of a baseline or null hypothesis, in the limit where word counts are high, the method delivers the optimal phase diagram in the rare/weak setting: it is asymptotically fully powerful inside the region of phase space where a formally specified test would have been fully powerful. In the limit where counts are low, we derive the phase diagram as well, although the optimality of the resulting diagram is not discussed here.

We consider the distributional connection between the lossy compressed representation of a high-dimensional signal X using a random spherical code and the observation of X under an additive white Gaussian noise (AWGN). We show that the Wasserstein distance between a bitrate- R compressed version of X and its observation under an AWGN-channel of signal-to-noise ratio 22R-1 is bounded in the problem dimension. We utilize this fact to connect the risk of an estimator based on the compressed version of X to the risk attained by the same estimator when fed the AWGN-corrupted version of X. We demonstrate the usefulness of this connection by deriving various novel results for inference problems under compression constraints, including minimax estimation, sparse regression, compressed sensing, and universality of linear estimation in remote source coding.

Consider the problem of estimating a latent signal from a lossy compressed version of the data when the compressor is agnostic to the relation between the signal and the data. This situation arises in a host of modern applications when data is transmitted or stored prior to determining the downstream inference task. Given a bitrate constraint and a distortion measure between the data and its compressed version, let us consider the joint distribution achieving Shannon's rate-distortion (RD) function. Given an estimator and a loss function associated with the downstream inference task, define the RD risk as the expected loss under the RD-achieving distribution. We provide general conditions under which the operational risk in estimating from the compressed data is asymptotically equivalent to the RD risk. The main theoretical tools to prove this equivalence are transportation-cost inequalities in conjunction with properties of compression codes achieving Shannon's RD function. Whenever such equivalence holds, a recipe for designing estimators from datasets undergoing lossy compression without specifying the actual compression technique emerges: design the estimator to minimize the RD risk. Our conditions are simplified in the special cases of discrete memoryless or multivariate normal data. For these scenarios, we derive explicit expressions for the RD risk of several estimators and compare them to the optimal source coding performance associated with full knowledge of the relation between the latent signal and the data.

We consider the statistical connection between the quantized representation of a high dimensional signal X using a random spherical code and the observation of X under an additive white Gaussian noise (AWGN). We show that given X, the conditional Wasserstein distance between its bitrate-R quantized version and its observation under AWGN of signal-to-noise ratio 22R- 1 is sub-linear in the problem dimension. We then utilize this fact to connect the mean squared error (MSE) attained by an estimator based on an AWGN-corrupted version of X to the MSE attained by the same estimator when fed with its bitrate-R quantized version.

We consider the recovery of a continuous-time Wiener process from a quantized or a lossy compressed version of its uniform samples under limited bitrate and sampling rate. We derive a closed-form expression for the optimal tradeoff among sampling rate, bitrate, and quadratic distortion in this setting. This expression is given in terms of a reverse waterfilling formula over the asymptotic spectral distribution of a sequence of finite-rank operators associated with the optimal estimator of the Wiener process from its samples. We show that the ratio between this expression and the standard distortion rate function of the Wiener process, describing the optimal tradeoff between bitrate and distortion without a sampling constraint, is only a function of the number of bits per sample. We also consider a sub-optimal lossy compression scheme in which the continuous-time process is estimated from the output of an encoder that is optimal with respect to the discrete-time samples. We show that the latter is strictly greater than the distortion under optimal encoding but only by at most 3%. We, therefore, conclude that near optimal performance is attained even if the encoder is unaware of the continuous-time origin of the samples.

We consider the multiterminal remote source coding problem of estimating a Gaussian signal from a bit-restricted representation of distributed linear measurements corrupted by additive white Gaussian noise. For this problem, we study the performance of the multiterminal compress-and-estimate (CE) coding scheme in which multiple remote encoders compress their measurements so as to minimize a local distortion measure which depends solely on the distribution of these measurements. In reconstruction, the decoder estimates the signal from the lossy-compressed measurements having full knowledge of the statistics of the source signal and the noisy measurements. The CE coding scheme is motivated by the scenario in which source encoders, due to their limited capabilities, operate according to a pre-determined compression strategy and cannot adapt to the sensing environment while the fusion center has full knowledge and computational capabilities. We focus, in particular, on two scenarios: the centralized observation model in which measurements are collected at a single remote encoder and the distributed observation model where measurements are provided to multiple remote sensors. In both scenarios, we investigate the performance attainable through the CE coding scheme in which the measurements are compressed according to a quadratic distortion measure and compare it to the performance of the coding scheme having full system knowledge.

Theoretical and experimental results have shown that compressed sensing with quantization can perform well if the signal is very sparse, the noise is very low, and the bitrate is sufficiently large. However, a precise characterization of the fundamental tradeoffs between these quantities has remained elusive. In our previous work, we considered a quantization scheme that first computes the conditional expectation of the signal. In this paper, we focus on a different approach in which the measurements are encoded directly using Gaussian codebooks. We show that that mean-square error (MSE) distortion of this approach can be analyzed by studying a degraded measurement model without any bitrate constraints. Building upon ideas from statistical physics and random matrix theory, we then provide single-letter formulas for the reconstruction error associated with optimal decoding. These formulas provide an explicit characterization of the mean-squared error (MSE) as a function of: (1) the average quantization bitrate, (2) the prior distribution of the signal, and (3) the spectral distribution of the sensing matrix. These formulas provide upper bounds on the fundamental limits of compressed sensing with quantization. Interestingly, it is shown that in some problem regimes, this method achieves the best known performance, even though the encoding stage does not use any information about the signal distribution other than its mean and variance.

Representing a continuous-time signal by a set of samples is a classical problem in signal processing. We study this problem under the additional constraint that the samples are quantized or compressed in a lossy manner under a limited bitrate budget. To this end, we consider a combined sampling and source coding problem in which an analog stationary Gaussian signal is reconstructed from its encoded samples. These samples are obtained by a set of bounded linear functionals of the continuous-time path, with a limitation on the average number of samples per unit time given in this setting. We provide a full characterization of the minimal distortion in terms of the sampling frequency, the bitrate, and the signal's spectrum. Assuming that the signal's energy is not uniformly distributed over its spectral support, we show that for each compression bitrate there exists a critical sampling frequency smaller than the Nyquist rate, such that the distortion in signal reconstruction when sampling at this frequency is minimal. Our results can be seen as an extension of the classical sampling theorem for bandlimited random processes in the sense that they describe the minimal amount of excess distortion in the reconstruction due to lossy compression of the samples and provide the minimal sampling frequency required in order to achieve this distortion. Finally, we compare the fundamental limits in the combined source coding and sampling problem to the performance of pulse code modulation, where each sample is quantized by a scalar quantizer using a fixed number of bits.

A general expression for the quadratic distortion rate function (DRF) of cyclostationary Gaussian processes in terms of their spectral properties is derived. This expression can be seen as the result of orthogonalization over the different components in the polyphase decomposition of the process. We use this expression to derive, in a closed form, the DRF of several cyclostationary processes arising in practice. We first consider the DRF of a combined sampling and source coding problem. It is known that the optimal coding strategy for this problem involves source coding applied to a signal with the same structure as one resulting from pulse amplitude modulation (PAM). Since a PAM-modulated signal is cyclostationary, our DRF expression can be used to solve for the minimal distortion in the combined sampling and source coding problem. We also analyze in more detail the DRF of a source with the same structure as a PAM-modulated signal, and show that it is obtained by reverse waterfilling over an expression that depends on the energy of the pulse and the baseband process modulated to obtain the PAM signal. This result is then used to explore the effect of the symbol rate in PAM on the DRF of its output. In addition, we also study the DRF of sources with an amplitude-modulation structure, and show that the DRF of a narrow-band Gaussian stationary process modulated by either a deterministic or a random phase sine-wave equals the DRF of the baseband process.

We consider the problem of recovering a sparse vector from a quantized or a lossy compressed version of its noisy random linear projections. We characterize the minimal distortion in this recovery as a function of the sampling ratio, the sparsity rate, the noise intensity and the total number of bits in the quantized representation. We first derive a singe-letter expression that can be seen as the indirect distortion-rate function of the sparse source observed through a Gaussian channel whose signal-to-noise ratio is derived from these parameters. Under the replica symmetry postulation, we prove that there exists a quantization scheme that attains this expression in the asymptotic regime of large system dimensions. In addition, we prove a converse demonstrating that the MMSE in estimating any fixed sub-block of the source from the quantized measurements at a fixed number of bits does not exceed this expression as the system dimensions go to infinity. Thus, under these conditions, the expression we derive describes the excess distortion incurred in encoding the source vector from its noisy random linear projections in lieu of the full source information.

We consider the remote source coding setting in which a source realization is estimated from a lossy compressed sequence of noisy observations. Unlike in the optimal remote source coding problem, however, the encoder is bound to use good codes with respect to the observation sequence, i.e., codes that are optimal for the lossy reconstruction of the observation, rather than the remote source. This encoding strategy is denoted as the compress-and-estimate (CE) scheme. For the case of an i.i.d source observed through a memoryless channel, we show that the distortion in the CE scheme is characterized by a single-letter expression, referred to as the CE distortion-rate function (CE-DRF). In particular, we show that the CE-DRF can be attained by estimating the source from the output of a remote encoder employing any sequence of good codes with respect to the observation sequence. In addition, we show that the limiting distortion in estimating any finite sub-block of the source realization from the output of a remote encoder employing good codes, averaged over all sub-blocks, is also bounded by the CE-DRF.

We consider the remote vector source coding problem in which a vector Gaussian source is estimated from noisy linear measurements. For this problem, we derive the performance of the compress-and-estimate (CE) coding scheme and compare it to the optimal performance. In the CE coding scheme, the remote encoder compresses the noisy source observations so as to minimize a local distortion measure, independent from the joint distribution between the source and the observations. In reconstruction, the decoder, having full knowledge of the joint distribution of the source and observations, estimates the original source realization from the lossy-compressed noisy observations. For the CE scheme in the vector Gaussian case, we show that, if the code rate is less than a specific threshold, then the CE coding scheme attains the same performance as the optimal coding scheme. For code rates above this threshold, we introduce lower and upper bounds on the performance gap between the CE and the optimal scheme. The case of a two-dimensional Gaussian source observed through two noisy measurements is studied to illustrate the behavior of the performance gap.

The minimal distortion attainable in recovering the waveform of a continuous-time Wiener process from an encoded version of its uniform samples is considered. We first introduce a combined sampling and source coding problem and prove an associated source coding theorem. We then derive an upper bound on the minimal distortion attainable under any sampling rate and a prescribed number of bits to encode the samples. We show that this bound is accurate to within a second order term in the sampling rate, and converges to the true distortion-rate function of the Wiener process as the sampling rate goes to infinity. For example, this bound implies that by providing a single bit per sample it is possible to achieve the optimal distortion-rate performance of the Wiener process, given by its distortion-rate function, to within a factor of 1.5. We conclude the distortion-rate function of the Wiener process is strictly smaller than the indirect distortion-rate function from its uniform samples obtained at any finite sampling rate. This is in contrast to stationary infinite bandwidth processes.

We consider a multiterminal source coding problem in which a random source signal is estimated from encoded versions of multiple noisy observations. Each encoded version, however, is compressed so as to minimize a local distortion measure, defined only with respect to the distribution of the corresponding noisy observation. The original source is then estimated from these compressed noisy observations. We denote the minimal distortion under this coding scheme as the compress-and-estimate distortion-rate function (CE-DRF). We derive a single-letter expression for the CE-DRF in the case of an i.i.d source. We evaluate this expression for the case of a Gaussian source observed through multiple parallel AWGN channels and quadratic distortion and in the case of a non-uniform binary i.i.d source observed through multiple binary symmetric channels under Hamming distortion. For the case of a Gaussian source, we compare the performance for centralized encoding versus that of distributed encoding. In the centralized encoding scenario, when the code rates are sufficiently small, there is no loss of performance compared to the indirect source coding distortion-rate function, whereas distributed encoding achieves distortion strictly larger then the optimal multiterminal source coding scheme. For the case of a binary source, we show that even with a single observation, the CE-DRF is strictly larger than that of indirect source coding.

We consider a multiterminal source coding problem in which a source is estimated at a central processing unit from lossy-compressed remote observations. Each lossy-encoded observation is produced by a remote sensor. The sensor first obtains a noisy version of the source, then compresses this observation based on minimizing a local distortion measure that depends only on the marginal distribution of its observation. The central node, on the other hand, has knowledge of the joint distribution of the source and all the observations and produces the source estimate that minimizes a different distortion measure between the source and its reconstruction. In this paper, we investigate the problem of optimally choosing the rate of each lossy-compressed remote estimate so as to minimize the distortion at the central processor, subject to bound on the sum of the communication rate between the sensors and the central unit. We focus, in particular, on two models of practical relevance: the case of a Gaussian source observed in additive Gaussian noise and reconstructed under quadratic distortion, and the case of a binary source observed in bit-flipping noise and reconstructed under Hamming distortion. In both scenarios we show that there exist regimes under which having more remote encoders does not reduce the source distortion. In other words, having fewer, high-quality remote estimates provides a smaller distortion than having more, lower-quality estimates.

The amount of information lost in sub-Nyquist sampling of a continuous-time Gaussian stationary process is quantified. We consider a combined source coding and sub-Nyquist reconstruction problem in which the input to the encoder is a noisy sub-Nyquist sampled version of the analog source. We first derive an expression for the mean squared error in the reconstruction of the process from a noisy and information rate-limited version of its samples. This expression is a function of the sampling frequency and the average number of bits describing each sample. It is given as the sum of two terms: minimum mean square error in estimating the source from its noisy but otherwise fully observed sub-Nyquist samples, and a second term obtained by reverse waterfilling over an average of spectral densities associated with the polyphase components of the source. We extend this result to multi-branch uniform sampling, where the samples are available through a set of parallel channels with a uniform sampler and a pre-sampling filter in each branch. Further optimization to reduce distortion is then performed over the pre-sampling filters, and an optimal set of pre-sampling filters associated with the statistics of the input signal and the sampling frequency is found. This results in an expression for the minimal possible distortion achievable under any analog-to-digital conversion scheme involving uniform sampling and linear filtering. These results thus unify the Shannon-Whittaker-Kotelnikov sampling theorem and Shannon rate-distortion theory for Gaussian sources.

A single-input multiple-output (SIMO) multiple access channel with a large number of uncoded non-cooperating single antenna transmitters and joint processing at a finite precision multi-antenna receiver is considered. We fix the number of receiver antennas per transmitter and investigate the effects of receiver quantization on the recovery of the transmitted signals in the asymptotic limit of a large number of transmitters. Our results suggest that a very fine quantization resolution at the receiver antennas is not necessary; even a modest increase in the number of bits of quantization (with the number of transmitting users) is sufficient to guarantee asymptotic reliability.

The minimal sampling frequency required to achieve the rate-distortion function of a Gaussian stationary process is analyzed. Although the Nyquist rate is the minimal sampling frequency that allows perfect reconstruction of a bandlimited signal from its samples, relaxing perfect reconstruction to a prescribed distortion may allow a lower sampling frequency to achieve the optimal rate-distortion trade-off. We consider a combined sampling and source coding problem in which an analog Gaussian source is reconstructed from its rate-limited sub-Nyquist samples. We show that each point on the distortion-rate curve of the source corresponds to a sampling frequency fDRsmaller than the Nyquist rate, such that this point can be achieved by sampling at frequency fDRor above. This can be seen as an extension of the sampling theorem in the sense that it describes the minimal amount of excess distortion in the reconstruction due to lossy compression of the samples, and provides the minimal sampling frequency required in order to achieve that distortion.

An expression for the distortion rate function of cyclostationary Gaussian processes is derived. This expression is given by water-filling over the eigenvalues of a spectral density matrix associated with the source. For processes in continuous time, the distortion rate function is given in terms of a limiting function of the eigenvalues of this matrix. A lower bound on the distortion-rate function, which does not involve eigenvalue computation, is also derived. This distortion rate function is evaluated for the processes obtained by modulating a Gaussian stationary narrowband pulse by a deterministic sine wave, and is shown to be equal to the distortion rate function of the stationary narrowband pulse.