Search

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 that \emph{one} round of adaptivity is sufficient to achieve optimal mean-square error., Comment: Accepted for publication in the IEEE Transactions on Information Theory

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 rate-distortion 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 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., Comment: Second revision. IEEE Transactions on Information Theory

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 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.

We consider the recovery of a continuous-time Wiener process from a quantized or 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. For example using one bit per sample on average, the expected distortion is approximately 1.2 times the standard distortion rate function, indicating a performance loss of about 20% due to sampling. We next consider the distortion when 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 while the latter is strictly greater than the distortion under optimal encoding, the ratio between the two does not exceed 1.027. We therefore conclude that nearly optimal performance is attained even if the encoder is unaware of the sampling rate and encodes the samples without taking into account the continuous-time underlying process., Under review. An extended version of a work presented in ISIT 2016 under the title "Information rates of sampled Wiener processes"

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., Comment: Accepted for publication at the IEEE transactions on information theory

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.

Processing, storing and communicating information that originates as an analog signal involves conversion of this information to bits. This conversion can be described by the combined effect of sampling and quantization, as illustrated in Fig. 1. The digital representation is achieved by first sampling the analog signal so as to represent it by a set of discrete-time samples and then quantizing these samples to a finite number of bits. Traditionally, these two operations are considered separately. The sampler is designed to minimize information loss due to sampling based on characteristics of the continuous-time input. The quantizer is designed to represent the samples as accurately as possible, subject to a constraint on the number of bits that can be used in the representation. The goal of this article is to revisit this paradigm by illuminating the dependency between these two operations. In particular, we explore the requirements on the sampling system subject to constraints on the available number of bits for storing, communicating or processing the analog information., Comment: to appear in "Signal Processing Magazine"

We consider the problem of estimating a Gaussian random walk from a lossy compression of its decimated version. Hence, the encoder operates on the decimated random walk, and the decoder estimates the original random walk from its encoded version under a mean squared error (MSE) criterion. It is well-known that the minimal distortion in this problem is attained by an estimate-and-compress (EC) source coding strategy, in which the encoder first estimates the original random walk and then compresses this estimate subject to the bit constraint. In this work, we derive a closed-form expression for this minimal distortion as a function of the bitrate and the decimation factor. Next, we consider a compress-and-estimate (CE) source coding scheme, in which the encoder first compresses the decimated sequence subject to an MSE criterion (with respect to the decimated sequence), and the original random walk is estimated only at the decoder. We evaluate the distortion under CE in a closed form and show that there exists a non-zero gap between the distortion under the two schemes. This difference in performance illustrates the importance of having the decimation factor at the encoder.

The chaos expansion of a general non-linear function of a Gaussian stationary increment process conditioned on its past realizations is derived. This work combines the Wiener chaos expansion approach to study the dynamics of a stochastic system with the classical problem of the prediction of a Gaussian process based on a realization of its past. This is done by considering special bases for the Gaussian space 𝒢 generated by the process, which allows us to obtain an orthogonal basis for the Fock space of 𝒢 such that each basis element is either measurable or independent with respect to the given samples. This allows us to easily derive the chaos expansion of a random variable conditioned on part of the sample path. We provide a general method for the construction of such basis when the underlying process is Gaussian with stationary increment. We evaluate the basis elements in the case of the fractional Brownian motion, which leads to a prediction formula for this process.

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.

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 problem of estimating the mean of a normal distribution under the following constraint: the estimator can access only a single bit from each sample from this distribution. We study the squared error risk in this estimation as a function of the number of samples and one-bit measurements $n$. We consider an adaptive estimation setting where the single-bit sent at step $n$ is a function of both the new sample and the previous $n-1$ acquired bits. For this setting, we show that no estimator can attain asymptotic mean squared error smaller than $\pi/(2n)+O(n^{-2})$ times the variance. In other words, one-bit restriction increases the number of samples required for a prescribed accuracy of estimation by a factor of at least $\pi/2$ compared to the unrestricted case. In addition, we provide an explicit estimator that attains this asymptotic error, showing that, rather surprisingly, only $\pi/2$ times more samples are required in order to attain estimation performance equivalent to the unrestricted case.

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.

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 obtained per unit time available 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 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 this distortion. Finally, we compare the fundamental limits in the combined source coding and sampling problem to the performance of pulse code modulation (PCM), where each sample is quantized by a scalar quantizer using a fixed number of bits., Comment: 20 pages, 14 figures

The indirect source-coding problem in which a Bernoulli process is compressed in a lossy manner from its noisy observations is considered. These noisy observations are obtained by passing the source sequence through a binary symmetric channel so that the channel crossover probability controls the amount of information available about the source realization at the encoder. We use classic results in rate-distortion theory to compute the rate-distortion function for this model as a solution of an exponential equation. In addition, we derive an upper bound on the rate distortion which has a simple closed-form expression and investigate the coding scheme that attains it. These expressions capture precisely the expected behavior of the rate-distortion function: the noisier the source observations, the smaller the reduction in distortion obtained from increasing the compression rate.

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 optimal sampling frequency in a Sigma-Delta analog-to-digital converter with a fixed bitrate at the output is studied. We consider the mean squared error performance metric where the input signal statistics are known. Fixing the output bitrate introduces a trade-off between the sampling rate and the number of bits used to quantize each sample. That is, while increasing the sampling rate reduces the in-band quantization noise, it also reduces the number of bits available to quantize each sample and therefore increases the magnitude of the quantization noise. The optimal sampling rate is the result of the interplay between these two phenomena. In this work we analyze the sampling rate of a Sigma-Delta modulator of arbitrary order under the approximation that the quantization error behaves like additive white noise that is uncorrelated with the signal. We show that for a signal with a spectrum that is constant over its bandwidth, the optimal sampling rate is either the Nyquist rate or the maximal sampling rate corresponding to the output bitrate. The choice between the two is approximately a function of the Sigma-Delta system order and the bitrate per unit bandwidth.

A general expression for the 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 study the information content of a PAM-modulated signal as a function of its symbol time relative to the bandwidth of the underlying baseband process. 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., Comment: First revision for the IEEE Transactions on Information Theory

Given a Gaussian stationary increment processes, we show that a Skorokhod-Hitsuda stochastic integral with respect to this process, which obeys the Wick-Itô calculus rules, can be naturally defined using ideas taken from Hida's white noise space theory. We use the Bochner-Minlos theorem to associate a probability space to the process, and define the counterpart of the S-transform in this space. We then use this transform to define the stochastic integral and prove an associated Itô formula.