Search

This work considers the cooperative sequential hypothesis testing problem in a distributed network with quantized communication channels. The sensors observe independent sequences of samples and in the meantime, exchange their local information in the form of quantized statistics at every sampling interval. The communication links are represented as an undirected graph. In this distributed setup, every sensor performs its own sequential test based on the local samples and the messages from the neighbour sensors. Our goal is to devise the distributed sequential test that comprises the quantization scheme, the message-exchange protocol and the test procedure such that every sensor in the network fully exploits the network diversity and achieves the (asymptotically) optimal performance in terms of the stopping time. In particular, two distributed sequential tests are proposed based on different quantization schemes and a quantized message-exchange protocol that satisfies certain conditions. The first quantization scheme uniformly quantizes the local statistic at each sensor and at every sampling interval; the second one hinges on a modified level-triggered quantization technique, and resembles the Lebesgue sampling of the running local statistic. Our analyses show that the uniform quantization based distributed sequential test yields sub-optimal performance, while the one based on level-triggered quantization achieves the order-2 asymptotically optimal performance at every sensor for any fixed quantization step-size. Furthermore, we generalize the proposed sequential tests to the cluster-based network. Numerical results are provided to corroborate our analyses and demonstrate the effectiveness of the proposed sequential tests.

Noiseless compressed sensing refers to the problem of recovering a (high-dimensional) signal from its under-determined linear measurements. For compressed sensing to be feasible, the signal needs to be structured. While the main focus of the field has been on simple structures such as sparsity, there has been a growing interest in moving beyond sparsity and having a comprehensive compressed sensing framework that covers general structures. Two recent approaches that aim at developing such a framework from different perspectives are i) Quantized maximum a posteriori (Q-MAP), a Bayesian method that assumes full knowledge of the source distribution, and ii) Lagrangian minimum entropy pursuit (L-MEP), a universal recovery method that requires no prior knowledge about the distribution of the source. In this paper, by establishing theoretical connections between L-MEP and Q-MAP, it is shown how the two methods are complementary to each other and lead to a theoretically-founded learning-based recovery method that applies to sources with general structures. Unlike a Bayesian or a universal method, a learning-based method is able to extract the source structure from training data. The effect of error in estimating the source structure on the performance of the learning-based compressed sensing recovery method is characterized.

It is revealed that there is a link between the quantization approach employed and the dimension of the vector parameter which can be accurately estimated by a quantized estimation system. A critical quantity called inestimable dimension for quantized data (IDQD) is introduced, which does not depend on the quantization regions and the statistical models of the observations but instead depends only on the number of sensors and on the precision of the vector quantizers employed by the system. It is shown that the IDQD describes a quantization-induced fundamental limitation on the estimation capabilities of the system. To be specific, if the dimension of the desired vector parameter is larger than the IDQD of the quantized estimation system, then the Fisher information matrix for estimating the desired vector parameter is singular, and, moreover, there exist infinitely many nonidentifiable vector parameter points in the vector parameter space. Furthermore, it is shown that under some common assumptions on the statistical models of the observations and the quantization system, a smaller IDQD can be obtained, which can specify an even more limiting quantization induced fundamental limitation on the estimation capabilities of the system.

The aim of this paper is to give an interpretation of the linear or nonlinear filtration problem as a quantization problem. Based on this, we extend the optimal filtering equation known from the Stratonovich filtering theory on the quantum process case. In contrast to the Kalman filter often used in such problems, the Stratonovich equation provides the optimal solution for nonlinear observation models. The observation model is based on an indirect measurement method, where the measurement is performed on an ancilla system that is interacted with an unknown one. The latter model is interpreted in case of a single-qudit system. Since the measured random variables and experiment are fundamentally different from each other, the obtained single-qudit observation model has a substantially different physical nature from the two-qubit one. However, in both problems, the Stratonovich optimal filter equation is equally applicable.

We consider the problem of recovering a high-dimensional structured signal from independent Gaussian linear measurements each of which is quantized to $b$ bits. The focus is on a specific method of signal recovery that extends a procedure originally proposed by Plan and Vershynin for one-bit quantization to a multi-bit setting. At the heart of this paper is a characterization of the optimal trade-off between the number of measurements $m$ and the bit depth per measurement $b$ given a total budget of $B = m \cdot b$ bits when the goal is to minimize the expected $\ell _{2}$ -error in estimating the signal. It turns out that the choice $b = 1$ is optimal for estimating the unit vector (direction) corresponding to the signal for any level of additive Gaussian noise before quantization as well as for a specific model of adversarial noise, whereas in a noiseless setting the choice $b = 2$ is optimal for estimating the direction and the norm (scale) of the signal. Moreover, Lloyd–Max quantization is shown to be an optimal quantization scheme with respect to $\ell _{2}$ -estimation error. Our analysis is corroborated by the numerical experiments showing nearly perfect agreement with our theoretical predictions. This paper is complemented by an empirical comparison to alternative methods of signal recovery. The results of that comparison point to a regime change depending on the noise level: in a low-noise setting, the approach under study falls short of more sophisticated competitors while being competitive in moderate- and high-noise settings.

We present a new iterative quantization procedure for oversampled frames with guaranteed convergence and stability. The procedure uses similar concepts to that of turbo decoding in the context of error control coding. The quantization process is modeled as a quadratic integer-programming problem. A trellis structure is introduced to solve the problem, where the quantized coefficients represent a path through the trellis diagram. The quantization metric is iteratively improved through turbo iterations by exchanging quantization extrinsic information. The proposed procedure is shown to provide significant improvement over prior art in quantization and integer programming.

This paper considers the quantization problem on the Grassmann manifold \mathcal{G}_{n,p}, the set of all p-dimensional planes (through the origin) in the n-dimensional Euclidean space. The chief result is a closed-form formula for the volume of a metric ball in the Grassmann manifold when the radius is sufficiently small. This volume formula holds for Grassmann manifolds with arbitrary dimension n and p, while previous results pertained only to p=1, or a fixed p with asymptotically large n. Based on this result, several quantization bounds are derived for sphere packing and rate distortion tradeoff. We establish asymptotically equivalent lower and upper bounds for the rate distortion tradeoff. Since the upper bound is derived by constructing random codes, this result implies that the random codes are asymptotically optimal. The above results are also extended to the more general case, in which \mathcal{G}_{n,q} is quantized through a code in \mathcal{G}_{n,p}, where p and q are not necessarily the same. Finally, we discuss some applications of the derived results to multi-antenna communication systems., 26 pages, 7 figures, submitted to IEEE Transactions on Information Theory in Aug, 2005

In a system utilizing multiuser diversity, regular feedback of channel-quality predictions to the base station is required for each user. Typically, the measure of channel quality must be quantized at each mobile station before it can be sent back. In this paper, we present two distributed scalar quantization schemes that optimize two different performance criteria: a) the minimization of the probability P e of incorrectly identifying the user with the best channel quality and b) maximization of the resulting throughput R. For a typical Rayleigh-fading system with 30 users per sector, numerical optimization results show that the Pe and R realized by the uniform quantization strategy with 16 quantization levels for each user can be achieved by only three quantization levels using the two proposed strategies. A practical approximation of the proposed schemes is studied and is shown to provide near-optimal performance for both performance criteria as the number of quantization levels becomes large

Representing signals using coarsely quantized coefficients of redundant expansions is an interesting source coding paradigm, the most important practical case of which is oversampled analog-to-digital (A/D) conversion. Signal reconstruction from quantized redundant expansions and the accuracy of such representations are problems which are not well understood and we study them in this paper for uniform scalar quantization in finite-dimensional spaces. To give a more global perspective, we first present an analysis of the resilience of redundant expansions to degradation by additive noise in general, and then focus on the effects of uniform scalar quantization. The accuracy of signal representations obtained by applying uniform scalar quantization to coefficients of redundant expansions, measured as the mean-squared Euclidean norm of the reconstruction error, has been previously shown to be lower-bounded by an 1/r/sup 2/ expression. We establish some general conditions under which the 1/r/sup 2/ accuracy can actually be attained, and under those conditions prove a 1/r/sup 2/ upper error bound. For a particular kind of structured expansions, which includes many popular frame classes, we propose reconstruction algorithms which attain the 1/r/sup 2/ accuracy at low numerical complexity. These structured expansions, moreover, facilitate efficient encoding of quantized coefficients in a manner which requires only a logarithmic bit-rate increase in redundancy, resulting in an exponential error decay in the bit rate. Results presented in this paper are immediately applicable to oversampled A/D conversion of periodic bandlimited signals.

Distributed multiple sensor detection problems with quantized observations are investigated for cases of nonbinary hypothesis and possibly statistically dependent observations from sensor to sensor conditioned on the hypothesis. The observations available at each sensor are quantized to produce a multiple digit sensor decision which is sent to a fusion center. At the fusion center, the sensor decisions are combined to form a final decision using a predetermined fusion rule. First, it is demonstrated that there is a maximum number of digits that should be used to communicate the sensor decision from a given sensor to the fusion center. This maximum is based on the number of digits used to communicate the decisions from all the other sensors to the fusion center. If more than this maximum number of digits is used, the performance of the optimum scheme will not be improved. In some special cases of great interest, the upper bound on the number of digits that should be used can be made significantly smaller. Secondly, the optimum way to allocate a fixed overall number of digits across sensors is investigated. Illustrative numerical results are also presented in this correspondence.

Signal estimation from a sequential encoding in the form of quantized noisy measurements is considered. As an example context, this problem arises in a number of remote sensing applications, where a central site estimates an information-bearing signal from low-bandwidth digitized information received from remote sensors, and may or may not broadcast feedback information to the sensors. We demonstrate that the use of an appropriately designed and often easily implemented additive control input before signal quantization at the sensor can significantly enhance overall system performance. In particular, we develop efficient estimators in conjunction with optimized random, deterministic, and feedback-based control inputs, resulting in a hierarchy of systems that trade performance for complexity.

The accuracy of oversampled analog-to-digital (A/D) conversion, the dependence of accuracy on the sampling interval /spl tau/ and on the bit rate R are characteristics fundamental to A/D conversion but not completely understood. These characteristics are studied for oversampled A/D conversion of band-limited signals in L/sup 2/ (R). We show that the digital sequence obtained in the process of oversampled A/D conversion describes the corresponding analog signal with an error which tends to zero as /spl tau//sup 2/ in energy, provided that the quantization threshold crossings of the signal constitute a sequence of stable sampling in the respective space of band-limited functions. Further, we show that the sequence of quantized samples can be represented in a manner which requires only a logarithmic increase in the bit rate with the sampling frequency, R=O(|log/spl tau/|), and hence that the error of oversampled A/D conversion actually exhibits an exponential decay in the bit rate as the sampling interval tends to zero.

It is common signal detection practice to base tests on quantized data and frequently, as in decentralized detection, this quantization is extreme: to a single bit. As to the accompanying degradation in performance, certain cases (such as that of an additive signal model and an efficacy measure) are well-understood. However, there has been little treatment of more general cases. In this correspondence we explore the possible performance loss from two perspectives. We examine the Chernoff exponent and discover a nontrivial lower bound on the relative efficiency of an optimized one-bit quantized detector as compared to unquantized. We then examine the case of finite sample size and discover a family of nontrivial bounds. These are upper bounds on the probability of detection for an unquantized system given a specified quantized performance, given that both systems operate at the same false-alarm rate.

Vector quantization is a data compression method by which a set of data points is encoded by a reduced set of reference vectors: the codebook. A vector quantization strategy is discussed that jointly optimizes distortion errors and the codebook complexity, thereby determining the size of the codebook. A maximum entropy estimation of the cost function yields an optimal number of reference vectors, their positions, and their assignment probabilities. The dependence of the codebook density on the data density for different complexity functions is investigated in the limit of asymptotic quantization levels. How different complexity measures influence the efficiency of vector quantizers is studied for the task of image compression. The wavelet coefficients of gray-level images are quantized, and the reconstruction error is measured. The approach establishes a unifying framework for different quantization methods like K-means clustering and its fuzzy version, entropy constrained vector quantization or topological feature maps, and competitive neural networks. >

Orthogonal quantization is a partition of signal space that is achieved by independent quantization of each of its M orthogonal axes. A closed form expression is derived for the quantized channel cutoff rate and for the optimum orthogonal quantization similar to the one that has been derived for binary signaling. While orthogonal quantization is natural for communication systems in which the transmitted signals are themselves orthogonal, it can also be profitably applied to other signals, e.g., a simplex set in a lower dimensional space. Though orthogonal quantization is inferior to optimal quantization, it is essentially simpler and does not incur great loss in performance. A numerical example illustrates the relative merits of optimal and orthogonal quantization for the simplex set in the plane.

Asymptotic properties of the r th power distortion measure associated with quantized k -dimensional random variables are considered. Subject only to a moment condition, it is shown that the infimum over all N level quantizers of the quantity N^{r/k} times the r th power average distortion converges to a finite constant as N \rightarrow \infty .

The degradation of the signal-to-noise ratio of signals quantized with one, two, or three bits and matched with the correlation function and sequential similarity detection algorithm is investigated. Except for the one-bit case, the correlation function produces a better signal-to-noise ratio for the low-level quantizers considered.

Quantum communication is studied under the cutoff-rate criterion for transmission of M coherent states of real amplitude (M=2, . . ., 7). Comparison with other measurement operators of interest, such as the number and the quasi-classical operators, is made. The effect of quantization of the decision level on the cutoff rate is considered. >

Sequences of integers which represent the output of a time sampled and quantized information source are considered. If the sequences are known to have first differences less than a given positive integer s or if they are known to be monotonic (either increasing or decreasing) and have first differences satisfying the above property, optimal encoding schemes are presented, in terms of s , the number of samples m , and the number of quantization levels q . The encoding schemes are presented as simple algorithms which may be implemented in a special purpose computer on board scientific spacecraft.

A random surface is a sample function of a random process \{f(x, y)\} depending on two real parameters. Examples of random surfaces would be: photographs or television pictures; topographic maps; atmospheric pressure charts; and the like. A number of statistical properties of the contours of such surfaces are derived. An application of the results to the problem of obtaining bounds on the information content of quantized random surfaces is outlined.

In order to transmit television pictures over a digital channel, it is necessary to send a binary code which represents the intensity level at each point in the picture. For good picture quality using standard PCM transmission, at least six bits are required at each sample point, since the eye is very sensitive to the small intensity steps introduced by quantization. However, by simply adding some noise to the signal before it is quantized and subtracting the same noise at the receiver, the quantization steps can be broken up and the source rate reduced to three bits per sample. Pseudo-random number generators can be synchronized at the transmitter and receiver to provide the identical "noise" which makes the process possible. Thus, with the addition of only a small amount of equipment, the efficiency of a PCM channel can be doubled.

We wish to \int_{S}|Z-f(Z)|^{2},S the unit square, over all choices of f(Z) which take just n values. For large n it is shown that f(Z) approaches that function which on each face of a "hexagonal mesh" has the value of the centroid of that face. This problem in the design of quantizers for a pulse-code modulation (PCM) system arose in which pairs of adjacent samples are quantized in an effort to capitalize on the correlation between samples and on the geometry of the plane.

Companding is a widely used method of implementing nonuniform quantizers. There are, however, problems in extending this technique to the multidimensional case. It is known, for example, that not all input probability densities can be quantized optimally in this fashion. In this note we characterize the class of probability density functions that can be optimally quantized with a multidimensional companding-type implementation.