Search

The article presents information on the 2005 Communications Society and Information Theory Society Joint Paper Award, which is given annually to an outstanding paper that was published in any of the two societies' publications during the preceding year. This year the award was given to researchers Nihar Jindal, Sriram Vishwanath, and Andrea Goldsmith for their paper "On the Duality of Gaussian Multiple-Access and Broadcast Channels," which appeared in the 2004 issue of the journal "IEEE Transaction on Information Theory." Jindal has done his B.S. in electrical engineering and computer science from the University of California in Berkeley, in 1999. His research work is in the field of the applications of communication and information theory to wireless communication, with a particular focus on multiple-antenna multi-user channels, dynamic resource allocation, sensor and ad hoc networks. Vishwanath's is currently working as an assistant professor in the Department of Electrical and Computer Engineering at the University of Texas in Austin. Goldsmith works as an assistant professor of electric engineering at Stanford University. She has done research in the field of wireless communication, information theory and adaptive resource allocation in wireless networks.

Consider a continuous signal that cannot be observed directly. Instead, one has access to multiple corrupted versions of the signal. The available corrupted signals are correlated because they carry information about the common remote signal. The goal is to reconstruct the original signal from the data collected from its corrupted versions. Known as the indirect or remote reconstruction problem, it has been mainly studied in the literature from an information theoretic perspective. A variant of this problem for a class of Gaussian signals, known as the “Gaussian CEO problem,” has received particular attention; for example, it has been shown that the problem of recovering the remote signal is equivalent with the problem of recovering the set of corrupted signals (separation principle). The information theoretic formulation of the remote reconstruction problem assumes that the corrupted signals are uniformly sampled and the focus is on optimal compression of the samples. On the other hand, in this paper, we revisit this problem from a sampling perspective. More specifically, assuming restrictions on the sampling rate from each corrupted signal, we look at the problem of finding the best sampling locations for each signal to minimize the total reconstruction distortion of the remote signal. In finding the sampling locations, one can take advantage of the correlation among the corrupted signals. The statistical model of the original signal and its corrupted versions adopted in this paper are similar to the one considered for the Gaussian CEO problem; i.e., we restrict to a class of Gaussian signals. Our main contribution is a fundamental lower bound on the reconstruction distortion for any arbitrary nonuniform sampling strategy. This lower bound is valid for any sampling rate. Furthermore, it is tight and matches the optimal reconstruction distortion in low and high sampling rates. Moreover, it is shown that in the low sampling rate region, it is optimal to use a certain nonuniform sampling scheme on all the signals. On the other hand, in the high sampling rate region, it is optimal to uniformly sample all the signals. We also consider the problem of finding the optimal sampling locations to recover the set of corrupted signals, rather than the remote signal. Unlike the information theoretic formulation of the problem in which these two problems were equivalent, we show that they are not equivalent in our setting. Finally, another contribution of this paper is a new reverse majorization inequality that might be of independent interest. [ABSTRACT FROM PUBLISHER]

This paper examines the close interplay between cooperation and adaptation for distributed detection schemes over fully decentralized networks. The combined attributes of cooperation and adaptation are necessary to enable networks of detectors to continually learn from streaming data and to continually track drifts in the state of nature when deciding in favor of one hypothesis or another. The results in this paper establish a fundamental scaling law for the steady-state probabilities of miss detection and false alarm in the slow adaptation regime, when the agents interact with each other according to distributed strategies that employ small constant step-sizes. The latter are critical to enable continuous adaptation and learning. This paper establishes three key results. First, it is shown that the output of the collaborative process at each agent has a steady-state distribution. Second, it is shown that this distribution is asymptotically Gaussian in the slow adaptation regime of small step-sizes. Third, by carrying out a detailed large deviations analysis, closed-form expressions are derived for the decaying rates of the false-alarm and miss-detection probabilities. Interesting insights are gained from these expressions. In particular, it is verified that as the step-size $\mu $ decreases, the error probabilities are driven to zero exponentially fast as functions of $1/\mu $ , and that the exponents governing the decay increase linearly in the number of agents. It is also verified that the scaling laws governing the errors of detection and the errors of estimation over the network behave very differently, with the former having exponential decay proportional to $1/\mu $ , while the latter scales linearly with decay proportional to $\mu $ . Moreover, and interestingly, it is shown that the cooperative strategy allows each agent to reach the same detection performance, in terms of detection error exponents, of a centralized stochastic-gradient solution. The results of this paper are illustrated by applying them to canonical distributed detection problems. [ABSTRACT FROM PUBLISHER]

Several information-theoretic studies on channels with output quantization have identified the capacity-achieving input distributions for different fading channels with 1-bit in-phase and quadrature (I/Q) output quantization. However, an exact characterization of the capacity-achieving input distribution for channels with multi-bit phase quantization has not been provided. In this paper, we consider four different channel models with multi-bit phase quantization at the output and identify the optimal input distribution for each channel model. We first consider a complex Gaussian channel with $b$ -bit phase-quantized output and prove that the capacity-achieving distribution is a rotated $2^{b}$ -phase shift keying (PSK). The analysis is then extended to multiple fading scenarios. We show that the optimality of rotated $2^{b}$ -PSK continues to hold under noncoherent fast fading Rician channels with $b$ -bit phase quantization when line-of-sight (LoS) is present. When channel state information (CSI) is available at the receiver, we identify $\frac {2\pi }{2^{b}}$ -symmetry and constant amplitude as the necessary and sufficient conditions for the ergodic capacity-achieving input distribution; which a $2^{b}$ -PSK satisfies. Finally, an optimum power control scheme is presented which achieves ergodic capacity when CSI is also available at the transmitter. [ABSTRACT FROM AUTHOR]

The class of Fourier matrices is of special importance in compressed sensing (CS). This paper concerns deterministic construction of CS matrices from Fourier matrices. Using Katz’ character sum estimation, we are able to design a deterministic procedure to select rows from a Fourier matrix to form a good CS matrix for sparse recovery. The sparsity bound in our construction is similar to that of binary CS matrices constructed by DeVore, which greatly improves previous results for CS matrices from Fourier matrices. Our approach also provides more flexibility in terms of the dimension of CS matrices. This paper also contains a useful improvement to Katz’ character sum estimation for quadratic extensions, with an elementary and transparent proof. Based on this improvement, we construct a class of special CS matrices consisting of partial Fourier matrices whose columns are a union of orthonormal bases. As a consequence, our construction yields an approximately mutually unbiased bases from Fourier matrices which is of particular interest to quantum information theory. Some numerical examples are also included. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the binary hypothesis testing problem using wireless sensor networks. We analyze the case where sensors transmit their local log-likelihood ratio (LLR) directly to a fusion center (FC) using an analog transmission scheme over multiple-access fading channels. Due to the nature of the wireless medium, the FC receives a superposition of sensor transmissions. The decision is made by the FC and is based on received data from the sensors. In contrast to the case of identical channels and i.i.d observations, the analog transmission of the LLR over multiple-access fading channels does not achieve the centralized error exponent. Large deviation tools are used in this paper to characterize the error exponent in the asymptotic regime (when the number of sensors approaches infinity) in the case of non-i.i.d observations and non-i.i.d fading channels. Chernoff bounding techniques are used to provide bounds on the error probability for a finite number of sensors when the observations and the fading channels are independent across sensors. Specific performance analysis is provided for detection over both i.i.d and spatially correlated Markovian fading channels. Simulation results then illustrate the detector's performance. [ABSTRACT FROM PUBLISHER]

This paper investigates the sequential hypothesis testing problem with online sensor selection and sensor usage constraints. That is, in a sensor network, the fusion center sequentially acquires samples by selecting one “most informative” sensor at each time until a reliable decision can be made. In particular, the sensor selection is carried out in the online fashion since it depends on all the previous samples at each time. Our goal is to develop the sequential test (i.e., stopping rule and decision function) and sensor selection strategy that minimize the expected sample size subject to the constraints on the error probabilities and sensor usages. To this end, we first recast the usage-constrained formulation into a Bayesian optimal stopping problem with different sampling costs for the usage-contrained sensors. The Bayesian problem is then studied under both finite- and infinite-horizon setups, based on which, the optimal solution to the original usage-constrained problem can be readily established. Moreover, by capitalizing on the structures of the optimal solution, a lower bound is obtained for the optimal expected sample size. In addition, we also propose algorithms to approximately evaluate the parameters in the optimal sequential test so that the sensor usage and error probability constraints are satisfied. Finally, numerical experiments are provided to illustrate the theoretical findings, and compare with the existing methods. [ABSTRACT FROM AUTHOR]

Universal hypothesis testing (UHT) refers to the problem of deciding whether samples come from a nominal distribution or an unknown distribution that is different from the nominal distribution. Hoeffding’s test, whose test statistic is equivalent to the empirical Kullback–Leibler divergence (KL divergence), is known to be asymptotically optimal for distributions defined on finite alphabets. With continuous observations, however, the discontinuity of the KL divergence in the distribution functions results in significant complications for UHT. This paper introduces a robust version of the classical KL divergence, defined as the KL divergence from a distribution to the Lévy ball of a known distribution. This robust KL divergence is shown to be continuous in the underlying distribution function with respect to the weak convergence. The continuity property enables the development of an asymptotically optimal test for the university hypothesis testing problem with continuous observations. The optimality is in the same sense as that of the Hoeffding’s test and stronger than that of Zeitouni and Gutman. Perhaps more importantly, the developed test statistic can be computed through convex programs, making it much more meaningful in practice. Numerical experiments are also conducted to evaluate its performance as compared with some kernel based goodness of fit test that has been proposed recently. [ABSTRACT FROM AUTHOR]

In random-access communication systems, the number of active users varies with time, and has considerable bearing on receiver's performance. Thus, techniques aimed at identifying not only the information transmitted, but also that number, play a central role in those systems. An example of application of these techniques can be found in multiuser detection (MUD). In typical MUD analyses, receivers are based on the assumption that the number of active users is constant and known at the receiver, and coincides with the maximum number of users entitled to access the system. This assumption is often overly pessimistic, since many users might be inactive at any given time, and detection under the assumption of a number of users larger than the real one may impair performance. The main goal of this paper is to introduce a general approach to the problem of identifying active users and estimating their parameters and data in a random-access system where users are continuously entering and leaving the system. The tool whose use we advocate is Random-Set Theory (RST): applying this, we derive optimum receivers in an environment where the set of transmitters comprises an unknown number of elements. In addition, we can derive Bayesian-filter equations which describe the evolution with ti me of the a posteriori probability (APP) density of the unknown user parameters, and use this density to derive optimum detectors. In this paper, we restrict ourselves to interferer identification and data detection, while in a companion paper we shall examine the more complex problem of estimating users' parameters. [ABSTRACT FROM AUTHOR]

The problem of detecting a single anomalous process among a finite number $M$ of processes is considered. At each time, a subset of the processes can be observed, and the observations from each chosen process follow two different distributions, depending on whether the process is normal or abnormal. The objective is a sequential search strategy that minimizes the expected detection time subject to an error probability constraint. This problem can be considered as a special case of active hypothesis testing first considered by Chernoff where a randomized strategy, referred to as the Chernoff test, was proposed and shown to be asymptotically (as the error probability approaches zero) optimal. For the special case considered in this paper, we show that a simple deterministic test achieves asymptotic optimality and offers better performance in the finite regime. We further extend the problem to the case where multiple anomalous processes are present. In particular, we examine the case where only an upper bound on the number of anomalous processes is known. [ABSTRACT FROM PUBLISHER]

The problem of detecting correlations from samples of a high-dimensional Gaussian vector has recently received a lot of attention. In most existing work, detection procedures are provided with a full sample. However, following common wisdom in experimental design, the experimenter may have the capacity to make targeted measurements in an on-line and adaptive manner. In this paper, we investigate such adaptive sensing procedures for detecting positive correlations. It is shown that, using the same number of measurements, adaptive procedures are able to detect significantly weaker correlations than their nonadaptive counterparts. We also establish minimax lower bounds that show the limitations of any procedure. [ABSTRACT FROM AUTHOR]

This paper studies sequential methods for recovery of sparse signals in high dimensions. When compared with fixed sample size procedures, in the sparse setting, sequential methods can result in a large reduction in the number of samples needed for reliable signal support recovery. Starting with a lower bound, we show any coordinate-wise sequential sampling procedure fails in the high dimensional limit provided the average number of measurements per dimension is less then \log (s)/D(P0||P1) , where s is the level of sparsity and D(P_{0}||P_{1}) is the Kullback–Leibler divergence between the underlying distributions. A series of sequential probability ratio tests, which require complete knowledge of the underlying distributions is shown to achieve this bound. Motivated by real-world experiments and recent work in adaptive sensing, we introduce a simple procedure termed sequential thresholding, which can be implemented when the underlying testing problem satisfies a monotone likelihood ratio assumption. Sequential thresholding guarantees exact support recovery provided the average number of measurements per dimension grows faster than \log (s)/D(P0||P1) , achieving the lower bound. For comparison, we show any nonsequential procedure fails provided the number of measurements grows at a rate less than \log (n)/D(P_{1}||P_{0})$ , where $n$ is the total dimension of the problem. [ABSTRACT FROM AUTHOR]

Usually, it is very difficult to determine the exact distribution for a test statistic. In this paper, asymptotic distributions of locally most powerful invariant test for independence of complex Gaussian vectors are developed. In particular, its cumulative distribution function (CDF) under the null hypothesis is approximated by a function of chi-squared CDFs. Moreover, the CDF corresponding to the non-null distribution is expressed in terms of non-central chi-squared CDFs for close hypothesis, and Gaussian CDF as well as its derivatives for far hypothesis. The results turn out to be very accurate in terms of fitting their empirical counterparts. Closed-form expression for the detection threshold is also provided. Numerical results are presented to validate our theoretical findings. [ABSTRACT FROM PUBLISHER]

A classical problem in digital communications is to evaluate the symbol error probability (SEP) and bit error probability (BEP) of a multidimensional constellation over an additive white Gaussian noise channel. In this paper, we revisit this problem for nonequally likely symbols and study the behavior of the optimal maximum a posteriori (MAP) detector at asymptotically high signal-to-noise ratios. Exact closed-form asymptotic expressions for SEP and BEP for arbitrary constellations and input distributions are presented. The well-known union bound is proven to be asymptotically tight under general conditions. The performance of the practically relevant maximum likelihood (ML) detector is also analyzed. Although the decision regions with MAP detection converge to the ML regions at high signal-to-noise ratios, the ratio between the MAP and ML detectors in terms of both SEP and BEP approaches a constant, which depends on the constellation and a priori probabilities. Necessary and sufficient conditions for asymptotic equivalence between the MAP and ML detectors are also presented. [ABSTRACT FROM AUTHOR]

Quantum detector tomography is a fundamental technique for calibrating quantum devices and performing quantum engineering tasks. In this paper, a novel quantum detector tomography method is proposed. First, a series of different probe states are used to generate measurement data. Then, using constrained linear regression estimation, a stage-1 estimation of the detector is obtained. Finally, the positive semidefinite requirement is added to guarantee a physical stage-2 estimation. This Two-stage Estimation (TSE) method has computational complexity $O(nd^{2}M)$ , where $n$ is the number of $d$ -dimensional detector matrices and $M$ is the number of different probe states. An error upper bound is established, and optimization on the coherent probe states is investigated. We perform simulation and a quantum optical experiment to testify the effectiveness of the TSE method. [ABSTRACT FROM AUTHOR]

It was shown in the above-titled paper by Rajan and Tepedelenlioglu (see ibid., vol. 59, no. 6, p. 3922–31, June 2013) that the symbol error rate (SER) of an arbitrary multidimensional constellation subject to additive white Gaussian noise is characterized as the product of a completely monotone function with a nonnegative power of signal-to-noise ratio (SNR) under minimum distance detection. In this comment, it is proved that the probability of correct decision of an arbitrary constellation admits a similar representation as well. Based on this fact, it is shown that the stochastic ordering \\leq{\cal G\alpha,\alpha\geq 0\} proposed by the authors as an extension of the existing Laplace transform order to compare the average SERs over two different fading channels actually predicts that the average SERs are equal for any constellation of dimensionality smaller than or equal to 2\alpha. Furthermore, it is noted that there are no positive random variables X1 and X2 such that the proposed stochastic ordering is satisfied in the strict sense, i.e., X1<{\cal G\alpha}X2, when \alpha=N/2 for any positive integer N. Additional remarks are noted about the fading scenarios at low SNR and the generalization to additive compound Gaussian noise originally discussed in the subject paper. [ABSTRACT FROM PUBLISHER]

A phase detection sequence is a length- $n$ cyclic sequence, such that the location of any length- $k$ contiguous subsequence can be determined from a noisy observation of that subsequence. In this paper, we derive bounds on the minimal possible $k$ in the limit of $n\to \infty $ , and describe some sequence constructions. We further consider multiple phase detection sequences, where the location of any length- $k$ contiguous subsequence of each sequence can be determined simultaneously from a noisy mixture of those subsequences. We study the optimal trade-offs between the lengths of the sequences, and describe some sequence constructions. We compare these phase detection problems to their natural channel coding counterparts, and show a strict separation between the fundamental limits in the multiple sequence case. Both adversarial and probabilistic noise models are addressed. [ABSTRACT FROM AUTHOR]

Parallel acquisition systems arise in various applications to moderate problems caused by insufficient measurements in single-sensor systems. These systems allow simultaneous data acquisition in multiple sensors, thus alleviating such problems by providing more overall measurements. In this paper, we consider the combination of compressed sensing with parallel acquisition. We establish the theoretical improvements of such systems by providing nonuniform recovery guarantees for which, subject to appropriate conditions, the number of measurements required per sensor decreases linearly with the total number of sensors. Throughout, we consider two different sampling scenarios—distinct (i.e., independent sampling in each sensor) and identical (i.e., dependent sampling between sensors)—and a general mathematical framework that allows for a wide range of sensing matrices. We also consider not just the standard sparse signal model, but also the so-called sparse in levels signal model. As our results show, optimal recovery guarantees for both distinct and identical sampling are possible under much broader conditions on the so-called sensor profile matrices (which characterize environmental conditions between a source and the sensors) for the sparse in levels model than for the sparse model. To verify our recovery guarantees, we provide numerical results showing phase transitions for different multi-sensor environments. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of recovering the support of structured signals via adaptive compressive sensing. We examine several classes of structured support sets, and characterize the fundamental limits of accurately recovering such sets through compressive measurements, while simultaneously providing adaptive support recovery protocols that perform near optimally for these classes. We show that by adaptively designing the sensing matrix, we can attain significant performance gains over non-adaptive protocols. These gains arise from the fact that adaptive sensing can: 1) better mitigate the effects of noise and 2) better capitalize on the structure of the support sets. [ABSTRACT FROM PUBLISHER]

Recovery of the sparsity pattern (or support) of an unknown sparse vector from a limited number of noisy linear measurements is an important problem in compressed sensing. In the high-dimensional setting, it is known that recovery with a vanishing fraction of errors is impossible if the measurement rate and the per-sample signal-to-noise ratio (SNR) are finite constants, independent of the vector length. In this paper, it is shown that recovery with an arbitrarily small but constant fraction of errors is, however, possible, and that in some cases computationally simple estimators are near-optimal. Bounds on the measurement rate needed to attain a desired fraction of errors are given in terms of the SNR and various key parameters of the unknown vector for several different recovery algorithms. The tightness of the bounds, in a scaling sense, as a function of the SNR and the fraction of errors, is established by comparison with existing information-theoretic necessary bounds. Near optimality is shown for a wide variety of practically motivated signal models. [ABSTRACT FROM PUBLISHER]

This paper introduces a simple and very general theory of compressive sensing. In this theory, the sensing mechanism simply selects sensing vectors independently at random from a probability distribution F; it includes all standard models—e.g., Gaussian, frequency measurements—discussed in the literature, but also provides a framework for new measurement strategies as well. We prove that if the probability distribution F obeys a simple incoherence property and an isotropy property, one can faithfully recover approximately sparse signals from a minimal number of noisy measurements. The novelty is that our recovery results do not require the restricted isometry property (RIP) to hold near the sparsity level in question, nor a random model for the signal. As an example, the paper shows that a signal with s nonzero entries can be faithfully recovered from about s \log n Fourier coefficients that are contaminated with noise. [ABSTRACT FROM AUTHOR]

This paper investigates potential improvement of non-parametric detection performance via addition of noise and evaluates the performance of noise modified nonparametric detectors. Detection performance comparisons are made between the original detectors and noise modified detectors. Conditions for improvability as well as the optimum additive noise distributions of the widely used sign detector, the Wilcoxon detector, and the dead-zone limiter detector are derived. Finally, a simple and fast learning algorithm to find the optimal noise distribution solely based on received data is presented. A near-optimal solution can be found quickly based on a relatively small dataset. [ABSTRACT FROM AUTHOR]

With recent developments in ad hoc networks and sensor networks, random-access protocol without feedback is a technique that deserves a closer look. This paper is based on Massey's model on random-access channel without feedback. A central concept of this model is the idea of protocol sequences. For these sequences, it is desirable that their cross correlation should be as low as possible and that the length of their period should not be too long, even if there is a large number of active users. Another useful feature is to be able to support multirate communication. Based on these considerations, a new family of protocol sequences is proposed in this paper. These new protocol sequences are built on the concept of prime sequences. It is shown that these sequences possess properties that make them suitable candidates for designing random access protocols for certain ad hoc or sensor networks. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of rate/distortion with side information available only at the decoder. For the case of jointly Gaussian source X and side information Y, and mean-squared error distortion, Wyner proved in 1976 that the rate/distortion function for this problem is identical to the conditional rate/distortion function RX∣Y, assuming the side information Y is available at the encoder. In this paper we construct a structured class of asymptotically optimal quantizers for this problem: under the assumption of high correlation between source X and side information Y, we show there exist quantizers within our class whose performance comes arbitrarily close to Wyner's bound. As an application illustrating the relevance of the high-correlation asymptotics, we also explore the use of these quantizers in the context of a problem of data compression for sensor networks, in a setup involving a large number of devices collecting highly correlated measurements within a confined area. An important feature of our formulation is that, although the per-node throughput of the network tends to zero as network size increases, so does the amount of information generated by each transmitter. This is a situation likely to be encountered often in practice, which allows us to cast under new—and more "optimistic"—light some negative results on the transport capacity of large-scale wireless networks. [ABSTRACT FROM AUTHOR]

This paper studies randomly spread code-division multiple access (CDMA) and multiuser detection in the large-system limit using the replica method developed in statistical physics. Arbitrary input distributions and flat fading are considered. A generic multiuser detector in the form of the posterior mean estimator is applied before single-user decoding. The generic detector can be particularized to the matched filter, decorrelator, linear minimum mean-square error (MMSE) detector, the jointly or the individually optimal detector, and others. It is found that the detection output for each user, although in general asymptotically non-Gaussian conditioned on the transmitted symbol, converges as the number of users go to infinity to a deterministic function of a "hidden" Gaussian statistic independent of the interferers. Thus, the multiuser channel can be decoupled: Each user experiences an equivalent single-user Gaussian channel, whose signal-to-noise ratio (SNR) suffers a degradation due to the multiple-access interference (MAI). The uncoded error performance (e.g., symbol error rate) and the mutual information can then be fully characterized using the degradation factor, also known as the multiuser efficiency, which can be obtained by solving a pair of coupled fixed-point equations identified in this paper. Based on a general linear vector channel model, the results are also applicable to multiple-input multiple-output (MIMO) channels such as in multiantenna systems. [ABSTRACT FROM AUTHOR]

In multiple-input multiple-output (MIMO) multi- user detection theory, the QR decomposition of the channel matrix H can be used to form the back-cancellation detector. In this paper, we propose an optimal QR decomposition, which we call the equal-diagonal QR decomposition, or briefly the QRS decomposition. We apply the decomposition to precoded successive-cancellation detection, where we assume that both the transmitter and the receiver have perfect channel knowledge. We show that, for any channel matrix H, there exists a unitary precoder matrix S, such that HS = QR, where the nonzero diagonal entries of the upper triangular matrix H in the QR decomposition of HR are all equal to each other. The precoder and the resulting successive-cancellation detector have the following properties. a) The minimum Euclidean distance between two signal points at the channel output is equal to the minimum Euclidean distance between two constellation points at the precoder input up to a multiplicative factor that equals the diagonal entry in the R-factor. b) The superchannel HS naturally exhibits an optimally ordered column permutation, i.e., the optimal detection order for the vertical Bell Labs layered space-time (V-BLAST) detector is the natural order. c) The precoder S minimizes the block error probability of the QR successive cancellation detector. d) A lower and an upper bound for the free distance at the channel output is expressible in terms Of the diagonal entries of the H-factor in the QR decomposition of a channel matrix. e) The precoder S maximizes, the lower bound of the channel's free distance subject to a power constraint. 1) For the optimal precoder 5, the performance of the QR detector is asymptotically (at large signal-to-noise ratios (SNRs)) equivalent to that of the maximum-likelihood detector (MLD) that uses the same precoder. Further, in this paper we consider two multiplexing schemes: time-division multiple access (TDMA) and orthogonal frequency-division multiplexing (OFDM). We design the optimal precoder for binary phase-shift keying (BPSK) with these multiplexing schemes, but outline the procedure to extend' the method to nonbinary schemes such as pulse amplitude modulation (PAM), phase-shift keying (PSK), and quadrature amplitude modulation (QAM). Finally, examples are given that illustrate the performance of the precoder and the corresponding successive cancellation detector. [ABSTRACT FROM AUTHOR]

Network security is important for information protection in open, secure, or covert communications. One such requirement is to achieve high-rate communications between clients, e.g., terminals or sensors, in the network while hiding information abet the transmitted symbols, signal activity, or other sensitive data from an unintended receiver, e.g., an eavesdropper. For wireless. links, the single-user capacity advantages of deployment of multiple antennas at the transmitter is well known. One of the principal conclusions of this paper is that proper exploitation of space-time diversity at the transmitter can also enhance information security and information-hiding capabilities. In particular, we show that significant gains are achievable when the transmitter and the client receiver are both informed about their channel while the transmitter and eavesdropper receiver are uniformed about their channel. More generally, we compare capacity limits for both informed and uninformed `transmitter and informed receiver scenarios subject to low probability of intercept (LPI) and low probability of detection (LPD) constraints. For several general cases, we can characterize the LPI- and LPD-optimal transmitted source distributions and compare them to the standard optimal source distribution satisfying a power constraint. We assume the standard quasi-static flat Rayleigh-fading channel model for the transmitter-receiver pairs. This paper is a step toward answering the fundamental question: what are the qualitative and quantitative differences between the information-carrying capabilities of open space-time channels versus score space-time channels? [ABSTRACT FROM AUTHOR]

The design of a detection system in which sensors are randomly located to detect a low-power signal emitter in a random location tends to be difficult because the measurements are conditionally dependent in general and the alternative hypothesis is composite. It is shown that there are conditions that allow a system designer to deal with these problems by assuming a least favorable distribution for the emitter location that not only makes the alternative hypothesis simple and ensures a detection performance, but also causes the measurements to become conditionally i.i.d., making models more amenable for analysis. Since a design based on a least favorable distribution may be considered too conservative, this paper proposes the use of a most favorable distribution for the emitter location and uses the theory of asymptotic relative efficiency (ARE) to evaluate how conservative the design based on a least favorable distribution is. It is further shown that, if the system designer can place sensors in an enlarged deployment region, then there are situations in which the design based on a least favorable distribution becomes less and less conservative as the dimensions of the region of interest increase. [ABSTRACT FROM PUBLISHER]

Rare events can potentially occur in many applications. When manifested as opportunities to be exploited, risks to be ameliorated, or certain features to be extracted, such events become of paramount significance. Due to their sporadic nature, the information-bearing signals associated with rare events often lie in a large set of irrelevant signals and are not easily accessible. This paper provides a statistical framework for detecting such events so that an optimal balance between detection reliability and agility, as two opposing performance measures, is established. The core component of this framework is a sampling procedure that adaptively and quickly focuses the information-gathering resources on the segments of the dataset that bear the information pertinent to the rare events. Particular focus is placed on Gaussian signals with the aim of detecting signals with rare mean and variance values. [ABSTRACT FROM AUTHOR]

In this paper, we study the existence of locally most powerful invariant tests (LMPIT) for the problem of testing the covariance structure of a set of Gaussian random vectors. The LMPIT is the optimal test for the case of close hypotheses, among those satisfying the invariances of the problem, and in practical scenarios can provide better performance than the typically used generalized likelihood ratio test (GLRT). The derivation of the LMPIT usually requires one to find the maximal invariant statistic for the detection problem and then derive its distribution under both hypotheses, which in general is a rather involved procedure. As an alternative, Wijsman's theorem provides the ratio of the maximal invariant densities without even finding an explicit expression for the maximal invariant. We first consider the problem of testing whether a set of N-dimensional Gaussian random vectors are uncorrelated or not, and show that the LMPIT is given by the Frobenius norm of the sample coherence matrix. Second, we study the case in which the vectors under the null hypothesis are uncorrelated and identically distributed, that is, the sphericity test for Gaussian vectors, for which we show that the LMPIT is given by the Frobenius norm of a normalized version of the sample covariance matrix. Finally, some numerical examples illustrate the performance of the proposed tests, which provide better results than their GLRT counterparts. [ABSTRACT FROM PUBLISHER]

In many signal detection and classification problems, we have knowledge of the distribution under each hypothesis, but not the prior probabilities. This paper is aimed at providing theory to quantify the performance of detection via estimating prior probabilities from either labeled or unlabeled training data. The error or risk is considered as a function of the prior probabilities. We show that the risk function is locally Lipschitz in the vicinity of the true prior probabilities, and the error of detectors based on estimated prior probabilities depends on the behavior of the risk function in this locality. In general, we show that the error of detectors based on the maximum likelihood estimate (MLE) of the prior probabilities converges to the Bayes error at a rate of n^-1/2, where n is the number of training data. If the behavior of the risk function is more favorable, then detectors based on the MLE have errors converging to the corresponding Bayes errors at optimal rates of the form n^-(1+\alpha)/2, where \alpha > 0 is a parameter governing the behavior of the risk function with a typical value \alpha = 1. The limit \alpha \rightarrow \infty corresponds to a situation where the risk function is flat near the true probabilities, and thus insensitive to small errors in the MLE; in this case, the error of the detector based on the MLE converges to the Bayes error exponentially fast with n. We show that the bounds are achievable no matter given labeled or unlabeled training data and are minimax-optimal in the labeled case. [ABSTRACT FROM AUTHOR]

Decentralized binary detection problem in ad-hoc sensor networks where a link between two sensors is on with a certain probability is considered in this paper. We propose a consensus based detection scheme where sensors exchange their local decisions, update their own decisions based on the exchanges and finally reach a consensus about the state of nature. We analyze the error probability and convergence of this decision consensus scheme. We show that with our scheme, the detection performance in ad-hoc networks is asymptotically equivalent to that of a parallel sensor network where all the local decisions are processed by a central node (fusion center) in the sense that the error exponents are the same. The probability distribution of the consensus time is also studied. Simulation and numerical results are given to verify the theoretical results. [ABSTRACT FROM PUBLISHER]

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia information. AND anti-collusion codes can be used to construct fingerprints resistant to collusion attacks on multimedia contents. In this paper, we first investigate AND anti-collusion codes and related detection algorithms from a combinatorial viewpoint, and then introduce a new concept of logical anti-collusion code to improve the traceability of multimedia fingerprinting. It reveals that frameproof codes have traceability for multimedia contents. Relationships among anti-collusion codes and other structures related to fingerprinting are discussed, and constructions for both AND anti-collusion codes and logical anti-collusion codes are provided. [ABSTRACT FROM AUTHOR]

It is known that the worst case near-far resistance of optimum multiuser detectors for asynchronous Gaussian multiple-access channels can be expressed in terms of a class of block-tridiagonal matrices, and the minimal eigenvalues of such a class of block-tridiagonal matrices serve as a good measure of the worst case near-far resistance. In this paper, we focus on the two-user scenario where each block-tridiagonal matrix under consideration is a tridiagonal matrix. We derive closed-form expressions for the minimal eigenvalues of such a class of tridiagonal matrices in terms of the largest real solution of a trigonometric equation in [0, π]. We also obtain lower bounds and upper bounds on the minimal eigenvalues which improve on previously known results in the literature. [ABSTRACT FROM AUTHOR]

Group testing has been used in many applications to efficiently identify rare events in a large population. In this paper, the concept of group testing is generalized to applications with correlated source models to derive scheduling policies for sensors' adopting cooperative transmissions. The tenet of our work is that in a wireless sensor network it is advantageous to allocate the same channel dimensions to all sensor sources that have the same response to a sequence of queries or tests. That is, nodes that have the same data attributes should transmit as a cooperative super-source. Specifically, we consider the case where sensors' data are modeled spatially as a one-dimensional Markov chain. Two strategies are considered: the recursive algorithm and the tree-based algorithm. The recursive scheme allows us to illustrate the performance of group testing for finite populations while the tree-based algorithm is used to derive the achievable scaling performances of the class of group testing strategies as the number of sensors increases. We show that the total number of queries required to gather all sensors' data scales in the order of the joint entropy. A further generalization of this concept provides the basis of deriving efficient data-gathering algorithms for correlated sources. [ABSTRACT FROM AUTHOR]

Distributed estimation of an unknown signal is a common task in sensor networks. The scenario usually envisioned consists of several nodes, each making an observation correlated with the signal of interest. The acquired data is then wirelessly transmitted to a fusion center that aims at estimating the desired signal within a prescribed accuracy. Motivated by the obvious processing limitations inherent to such distributed infrastructures, we seek to find efficient compression schemes that account for limited available power and communication bandwidth. In this paper, we propose a transform-based approach to this problem where each sensor provides the fusion center with a low-dimensional approximation of its local observation by means of a suitable linear transform. Under the mean squared error criterion, we derive the optimal solution to apply at one sensor assuming all else being fixed. This naturally leads to an iterative algorithm whose optimality properties are exemplified using a simple though illustrative correlation model. The stationarity issue is also investigated. Under restrictive assumptions, we then provide an asymptotic distortion analysis, as the size of the observed vectors becomes large. Our derivation relies on a variation of the Toeplitz distribution theorem, which allows us to provide a reverse "water-filling" perspective to the problem of optimal dimensionality reduction. We illustrate, with a first-order Gauss--Markov model, how our findings allow for the computation of analytical closed-form distortion formulas that provide an accurate estimation of the reconstruction error obtained in the finite-dimensional regime. [ABSTRACT FROM AUTHOR]

A theory of noncoherent decision feedback multiuser detection for nonorthogonal binary modulation is developed that parallels that of coherent decision feedback multiuser detection for single-pulse modulation. In particular, an optimum noncoherent decision feedback detector is obtained that maximizes symmetric energy over a newly defined class of decision feedback detectors. Unlike the usual per-user performance metrics such as asymptotic efficiency or near-far resistance, the symmetric energy measure captures, with a single number, the asymptotic (high signal-to-noise ratio (SNR)) bit-error performance of all users at once. Several properties of the optimum decision feedback detector are established, one of which is that it outperforms the decision feedback generalized-likelihood ratio (GLR) detector in symmetric energy. It is also shown that, regardless of the order in which users are detected, the optimum noncoherent decision feedback detector outperforms its non-decision feedback counterpart in symmetric energy. Furthermore, two simple rules are obtained for determining the order in which users must be detected to guarantee that the optimum decision feedback detector outperforms its non-decision feedback counterpart (which in turn, is superior to the decorrelative GLR detector presented earlier) in terms of asymptotic effective energy for every user. In fact, one of the two (greedy) ordering rules also maximizes symmetric energy among all possible orderings. Such ordering rules are not available for the noncoherent decision feedback GLR detector in earlier work of the authors. Feasible sets of received energies are characterized in which it is possible, with power control, to achieve quality-of-service objectives for each user. None of the results in this paper make simplifying assumptions about the effects of error propagation. The term "noncoherent" in this work is used to denote that the receiver has no knowledge of the carrier phases and received signal energies of any of the users. [ABSTRACT FROM AUTHOR]

We investigate covert communication under a sequential change-point detection (SCPD) framework, where a transmitter, Alice, attempts to communicate reliably with a receiver, Bob, over an additive white Gaussian noise channel, while simultaneously ensuring covertness (low probability of detection) with respect to an adversary, Willie. Different from the binary hypothesis test based detection framework considered in prior works where Willie collects all signal samples together and makes a decision in a batch manner, we view Willie’s detection process as an SCPD process that works in a real-time manner. We establish a new criterion to evaluate the covertness of the communication between Alice and Bob, and investigate the performance of covert communication accordingly. Subject to the proposed constraint on covertness, we investigate the feasible transmit power and transmission duration under three SCPD algorithms, namely, the Shewhart test, the finite moving average chart (FMAC), and the cumulative sum (CUSUM) test, and characterize how the covert communication throughput scales with the average run length to false alarm (ARL2FA) of Willie’s detector as the ARL2FA increases without bound. Our theoretical results can be viewed as upper bounds on the covert communication throughput that can be achieved, and we show that compared with the case where Willie performs the CUSUM test, Alice and Bob achieve a higher covert communication throughput if Willie performs the Shewhart test or the FMAC. [ABSTRACT FROM AUTHOR]

We extend the result by Tse and Verdú on the optimum asymptotic multiuser efficiency of randomly spread code division multiple access (CDMA) with binary phase shift keying input. Random Gaussian and random binary antipodal spreading are considered. We obtain the optimum asymptotic multiuser efficiency of a K -user system with spreading gain N when K and N\rightarrow \infty , grows logarithmically with K under some conditions. It is shown that the optimum detector in a Gaussian randomly spread CDMA system has a performance close to the single user system at high signal-to-noise ratio when K and N\rightarrow \infty , is kept less than ({\log _{3}K}/{2}) . Random binary antipodal matrices are also studied and a lower bound for the optimum asymptotic multiuser efficiency is obtained. Furthermore, we investigate the connection between detecting matrices in the coin weighing problem and optimum asymptotic multiuser efficiency. We obtain a condition such that for any binary input, an N \times K$ random matrix, whose entries are chosen randomly from a finite set, is a detecting matrix as $K$ and $N\rightarrow \infty $ . [ABSTRACT FROM AUTHOR]

We consider the problem of 20 questions with noise for multiple players under the minimum entropy criterion in the setting of stochastic search, with application to target localization. Each player yields a noisy response to a binary query governed by a certain error probability. First, we propose a sequential policy for constructing questions that queries each player in sequence and refines the posterior of the target location. Second, we consider a joint policy that asks all players questions in parallel at each time instant and characterize the structure of the optimal policy for constructing the sequence of questions. This generalizes the single player probabilistic bisection method for stochastic search problems. Third, we prove an equivalence between the two schemes showing that, despite the fact that the sequential scheme has access to a more refined filtration, the joint scheme performs just as well on average. Fourth, we establish convergence rates of the mean-square error and derive error exponents. Finally, we obtain an extension to the case of unknown error probabilities. This framework provides a mathematical model for incorporating a human in the loop for active machine learning systems. [ABSTRACT FROM PUBLISHER]

A recent paper by Jedwab and Wodlinger renewed interest in a problem of multislit spectrometer design first proposed by Golay in 1951 but subsequently forgotten. It is shown that Golay's formulation of the problem in terms of 0/1 binary sequences is unduly restrictive. By relaxing the restrictions, infinitely many spectrometer designs satisfying all the original physical criteria can be found. Three constructions for such spectrometer designs are presented, involving Golomb rulers and variants. These constructions explain all nontrivial examples involving at most 26 slits. [ABSTRACT FROM PUBLISHER]

The max-log-MAP (MLM) receiver is an approximated version of the well-known Bahl–Cocke–Jelinek-Raviv algorithm. The MLM algorithm is attractive due to its implementation simplicity. In practice, sliding-window implementations are preferred, whereby truncated signaling neighborhoods (around each transmission time instant) are considered. In this paper, we consider binary signaling sliding-window MLM receivers, where the MLM detector is truncated to a length-m signaling neighborhood. Here, truncation is used to ease the burden of analysis. For any number n of chosen times instants, we derive exact expressions for both 1) the joint distribution of the MLM symbol reliabilities, and 2) the joint probability of the erroneous MLM symbol detections. We show that the obtained expressions can be efficiently evaluated using Monte–Carlo techniques. The most computationally expensive operation (in each Monte–Carlo trial) is an eigenvalue decomposition of a size 2mn \times 2mn matrix. The proposed method handles various scenarios such as correlated noise distributions, modulation coding, etc. [ABSTRACT FROM PUBLISHER]

Compressed sensing with sparse frame representations is seen to have much greater range of practical applications than that with orthonormal bases. In such settings, one approach to recover the signal is known as \ell 1-analysis. We expand in this paper the performance analysis of this approach by providing a weaker recovery condition than existing results in the literature. Our analysis is also broadly based on general frames and alternative dual frames (as analysis operators). As one application to such a general-dual-based approach and performance analysis, an optimal-dual-based technique is proposed to demonstrate the effectiveness of using alternative dual frames as analysis operators. An iterative algorithm is outlined for solving the optimal-dual-based \ell 1-analysis problem. The effectiveness of the proposed method and algorithm is demonstrated through several experiments. [ABSTRACT FROM PUBLISHER]

Tree detection techniques are often used to reduce the complexity of a posteriori probability (APP) detection in multiantenna wireless communication systems. In this paper, we introduce an efficient soft-input soft-output tree detection algorithm that employs a new type of look-ahead path metric in the process of branch pruning (or sorting). While conventional path metrics depend only on symbols on a visited path, the new path metric accounts for unvisited parts of the tree in advance through an unconstrained linear estimator and adds a bias term that reflects the contribution of as-yet undecided symbols. By applying the linear estimate-based look-ahead path metric to an M-algorithm that selects the best M paths for each level of the tree, we develop a new soft-input soft-output tree detector, called an improved soft-input soft-output M-algorithm (ISS-MA). Based on an analysis of the probability of correct path loss, we show that the improved path metric offers substantial performance gain over the conventional path metric. We also demonstrate through simulations that the proposed ISS-MA can be a promising candidate for soft-input soft-output detection in high-dimensional systems. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment p (BPDQ_p), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed subject to a data-fidelity constraint expressed in the \ell_p-norm of the residual error for 2\leqslant p\leqslant \infty. [ABSTRACT FROM AUTHOR]

The concept of distributed transmit beamforming is implicit in many key results of network information theory. However, its implementation in a wireless network involves the fundamental challenge of ensuring phase coherence of the radio frequency signals from the different transmitters in the presence of unknown phase offsets between the transmitters and unknown channel gains from the transmitters to the receiver. In this paper, it is shown that such phase alignment can be achieved using distributed adaptation by the transmitters with minimal feedback from the receiver. Specifically, each transmitter independently makes a small random adjustment to its phase at each iteration, while the receiver broadcasts a single bit of feedback, indicating whether the signal-to-noise ratio (SNR) improved or worsened after the current iteration. The transmitters keep the "good" phase adjustments and discard the "bad" ones, thus implementing a distributed ascent algorithm. It is shown that, for a broad class of distributions for the random phase adjustments, this procedure leads to asymptotic phase coherence with probability one. A simple analytical model, borrowing ideas from statistical mechanics, is used to characterize the progress of the algorithm, and to provide guidance on parameter choices. This analytical model is based on a conjecture on the distribution of the received phases when the number of transmitters becomes large. Finally, the proposed system is shown to be scalable: the random phase perturbations can be chosen such that the convergence time is linear in the number of collaborating nodes. [ABSTRACT FROM AUTHOR]

In this paper, the communication direction problem of a two-sensor tandem binary decision system is considered. Rigorous analysis shows that the performance of communication from the sensor with higher noise power to the sensor with lower noise power is not always better than the performance of the reverse communication direction when the signal and sensor noises are both Gaussian. This result can be extended to a more general two-sensor tandem binary decision system without the assumption of a specific data distribution. This seems somewhat counterintuitive but has significance for optimization design of sensor communication direction. Computer experiments support our analytic results and illustrate interesting information which requires need further study. [ABSTRACT FROM AUTHOR]

The detection of information flows by timing analysis is considered. Given transmission timestamps of monitored nodes, the problem is to decide whether there is an information flow through these nodes by analyzing the transmission patterns. Due to constraints that packets from an information flow need to be delivered within certain delay or the relay nodes have bounded memory, transmission patterns of an information flow are statistically different from those of independent traffic. The main result of this paper is a tight characterization of the maximum amount of chaff noise such that Chernoff-consistent detection is achievable. The direct part of the result is an explicit construction of a detector that has vanishing false alarm and miss probabilities as the sample size increases whenever the noise level is below certain threshold. Conversely, when the noise level is above this threshold, there exist means to hide the information flow such that it is indistinguishable from independent traffic. Explicit characterization of the noise threshold is provided for Poisson transmission schedules. It is also shown that while information flows can be hidden among chaff noise for a small number of hops, the rate of information flow diminishes as the number of hops increases. [ABSTRACT FROM AUTHOR]

In this paper, we consider the detection of binary (antipodal) signals transmitted in a spatially multiplexed fashion over a fading multiple-input--multiple-output (MIMO) channel and where the detection is done by means of semidefinite relaxation (SDR). The SDR detector is an attractive alternative to maximum-likelihood (ML) detection since the complexity is polynomial rather than exponential. Assuming that the channel matrix is drawn with independent identically distributed (i.i.d.) real-valued Gaussian entries, we study the receiver diversity and prove that the SDR detector achieves the maximum possible diversity. Thus, the error probability of the receiver tends to zero at the same rate as the optimal ML receiver in the high signal-to-noise ratio (SNR) limit. This significantly strengthens previous performance guarantees available for the semidefinite relaxation detector. Additionally, it proves that full diversity detection is also possible in certain scenarios when using a noncombinatorial receiver structure. [ABSTRACT FROM AUTHOR]

Multiple-antenna concepts for wireless communication systems promise high spectral efficiency and low error rates by proper exploitation of the randomness in multipath propagation. In this paper, we investigate the impact of channel uncertainty caused by channel estimation errors on the error rate performance. We consider a training-based multiple-antenna system that reserves a portion of time to sound the channel. Training symbols are used to estimate the channel by means of an arbitrary linear filter at the receiver. No channel state information (CSI) is assumed at the transmitter. We present a new framework to analyze training-based multiple-antenna systems by introducing an equivalent system model that specifies the channel by the estimated (and hence, known) channel coefficients and an uncorrelated, data-dependent, multiplicative noise. We derive the maximum-likelihood (ML) detector and highlight its behavior in the limiting cases of perfect CSI and no CSI, and its relation to several mismatched detectors. We deduce new exact expressions and Chernoff bounds of the pairwise error probability (PEP) used to assess word-error and bit-error rate bounds for ML and mismatched detection. Finally, we review the code design guidelines in terms of the deleterious effect of channel uncertainty for coherent and noncoherent signaling schemes, and present numerical results. [ABSTRACT FROM AUTHOR]