An official website of the United States government
We consider the problem of estimating a $$p$$ -dimensional vector $$\beta$$ from $$n$$ observations $$Y=X\beta+W$$ , where $$\beta_{j}\mathop{\sim}^{\mathrm{i.i.d}.}\pi$$ for a real-valued distribution $$\pi$$ with zero mean and unit variance’ $$X_{ij}\mathop{\sim}^{\mathrm{i.i.d}.}\mathcal{N}(0,1)$$ , and $$W_{i}\mathop{\sim}^{\mathrm{i.i.d}.}\mathcal{N}(0,\ \sigma^{2})$$ . In the asymptotic regime where $$n/p\rightarrow\delta$$ and $$p/\sigma^{2}\rightarrow$$ snr for two fixed constants $$\delta,\ \mathsf{snr}\in(0,\ \infty)$$ as $$p\rightarrow\infty$$ , the limiting (normalized) minimum mean-squared error (MMSE) has been characterized by a single-letter (additive Gaussian scalar) channel. In this paper, we show that if the MMSE function of the single-letter channel converges to a step function, then the limiting MMSE of estimating $$\beta$$ converges to a step function which jumps from 1 to 0 at a critical threshold. Moreover, we establish that the limiting mean-squared error of the (MSE-optimal) approximate message passing algorithm also converges to a step function with a larger threshold, providing evidence for the presence of a computational-statistical gap between the two thresholds.
more »
« less
When is the zero-error capacity positive in the relay, multiple-access, broadcast and interference channels?
Shannon determined that the zero-error capacity of a point-to-point channel whose channel p(y|x) has confusability graph GX|Y is positive if and only if there exist two inputs that are “non-adjacent”, or “non-confusable”. Equivalently, it is non-zero if and only if the independence number of GX|Y is strictly greater than 1. A multi-letter expression for the zero-error capacity of the channel with confusability graph GX|Y is known, and is given by the normalized limit as the blocklength n → 1 of the maximum independent set of the n-fold strong product of GX|Y. This is not generally computable with known methods. In this paper, we look at the zero-error capacity of four multi-user channels: the relay, the multiple-access (MAC), the broadcast (BC), and the interference (IC) channels. As a first step towards finding a multi-letter expression for the capacity of such channels, we find necessary and sufficient conditions under which the zero-error capacity is strictly positive.
more »
« less
- Award ID(s):
- 1645381
- PAR ID:
- 10025321
- Date Published:
- Journal Name:
- Communication, Control, and Computing (Allerton), 2016 54th Annual Allerton Conference on
- Page Range / eLocation ID:
- 672 to 678
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study reliable communication over point-to-point adversarial channels in which the adversary can observe the transmitted codeword via some function that takes the n-bit codeword as input and computes an r*n-bit output for some given r in [0,1]. We consider the scenario where the r*n -bit observation is computationally bounded - the adversary is free to choose an arbitrary observation function as long as the function can be computed using a polynomial amount of computational resources. This observation-based restriction differs from conventional channel-based computational limitations, where in the later case, the resource limitation applies to the computation of the (adversarial) channel error/corruption. For all r in [0,1−H(p)] where H(.) is the binary entropy function and p is the adversary’s error budget, we characterize the capacity of the above channel and find that the capacity is identical to the completely oblivious setting (r=0). This result can be viewed as a generalization of known results on myopic adversaries and on channels with active eavesdroppers for which the observation process depends on a fixed distribution and fixed-linear structure, respectively, that cannot be chosen arbitrarily by the adversary.more » « less
-
On finite-length analysis and channel dispersion for broadcast packet erasure channels with feedbackMotivated by the applications for low-delay communication networks, the finite-length analysis, or channel dispersion identification, of the multi-user channel is very important. Recent studies also incorporate the effects of feedback in point-to-point and common-message broadcast channels (BCs). However, with private messages and feedback, finite-length results for BCs are much more scarce. Though it is known that feedback can strictly enlarge the capacity, the ultimate feedback capacity regions remain unknown for even some classical channels including Gaussian BCs. In this work, we study the two-user broadcast packet erasure channel (PEC) with causal feedback, which is one of the cleanest feedback capacity results and the capacity region can be achieved by elegant linear network coding (LNC). We first derive a new finite-length outer bound for any LNCs and then accompanying inner bound by analyzing a three-phase LNC. For the outer-bound, we adopt a linear-space-based framework, which can successfully find the LNC capacity. However, naively applying this method in finite-length regime will result in a loose outer bound. Thus a new bounding technique based on carefully labelling each time slot according to the type of LNC transmitted is proposed. Simulation results show that the sum-rate gap between our inner and outer bounds is within 0.02 bits/channel use. Asymptotic analysis also shows that our bounds bracket the channel dispersion of LNC feedback capacity for broadcast PEC to within a factor of Q-l (E/2)/Q-l (E).more » « less
-
In this paper, we study a sampling and transmission scheduling problem for multi-source remote estimation, where a scheduler determines when to take samples from multiple continuous-time Gauss-Markov processes and send the samples over multiple channels to remote estimators. The sample transmission times are i.i.d. across samples and channels. The objective of the scheduler is to minimize the weighted sum of the time-average expected estimation errors of these Gauss-Markov sources. This problem is a continuous-time Restless Multi-armed Bandit (RMAB) problem with a continuous state space. We prove that the bandits are indexable and derive an exact expression of the Whittle index. To the extent of our knowledge, this is the first Whittle index policy for multi-source signal-aware remote estimation of Gauss-Markov processes. We further investigate signal-agnostic remote estimation and develop a Whittle index policy for multi-source Age of Information (AoI) minimization over parallel channels with i.i.d. random transmission times. Our results unite two theoretical frameworks for remote estimation and AoI minimization: threshold-based sampling and Whittle index-based scheduling. In the single-source, single-channel scenario, we demonstrate that the optimal solution to the sampling and scheduling problem can be equivalently expressed as both a threshold-based sampling strategy and a Whittle index-based scheduling policy. Notably, the Whittle index is equal to zero if and only if two conditions are satisfied: (i) the channel is idle, and (ii) the estimation error is precisely equal to the threshold in the threshold-based sampling strategy. Moreover, the methodology employed to derive threshold-based sampling strategies in the single-source, single-channel scenario plays a crucial role in establishing indexability and evaluating the Whittle index in the more intricate multi-source, multi-channel scenario. Our numerical results show that the proposed policy achieves high performance gain over the existing policies when some of the Gauss-Markov processes are highly unstable.more » « less
-
Abstract When can noiseless quantum information be sent across noisy quantum devices? And at what maximum rate? These questions lie at the heart of quantum technology, but remain unanswered because of non-additivity— a fundamental synergy which allows quantum devices (aka quantum channels) to send more information than expected. Previously, non-additivity was known to occur in very noisy channels with coherent information much smaller than that of a perfect channel; but, our work shows non-additivity in a simple low-noise channel. Our results extend even further. We prove a general theorem concerning positivity of a channel’s coherent information. A corollary of this theorem gives a simple dimensional test for a channel’s capacity. Applying this corollary solves an open problem by characterizing all qubit channels whose complement has non-zero capacity. Another application shows a wide class of zero quantum capacity qubit channels can assist an incomplete erasure channel in sending quantum information. These results arise from introducing and linking logarithmic singularities in the von-Neumann entropy with quantum transmission: changes in entropy caused by this singularity are a mechanism responsible for both positivity and non-additivity of the coherent information. Analysis of such singularities may be useful in other physics problems.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ALLERTON.2016.7852296
