Computing channel capacity is in general intractable because it is given by the limit of a sequence of optimization problems whose dimensionality grows to infinity. As a result, constant-sized characterizations of feedback or non-feedback capacity are known for only a few classes of channels with memory. This paper introducesposet-causal channels—a new formalism of a communication channel in which channel inputs and outputs are indexed by the elements of a partially ordered set (poset). We develop a novel methodology that allows us to establish a single-letter upper bound on the feedback capacity of a subclass of poset-causal channels whose memory structure exhibits a Markov property and symmetry. The methodology is based on symmetry reduction in optimization. Additionally, we establish connections to the literature on graphical models by providing a sufficient condition for our capacity upper bound to be tight, expressed in terms of the running intersection property. We instantiate our method on two channel models: the Noisy Output is the STate (NOST) channel—for which the bound is tight—and a new two-dimensional extension of it.

We study the scalar quantization of random information sources with unknown probability distributions through the lens of distributional robustness. Assuming the true source distribution resides within an ambiguity set of plausible distributions, we formulate the problem of distributionally robust scalar quantization (DRQ) as finding a minimax optimal quantizer that minimizes the mean-squared quantization error (MSQE) under the least favorable distribution in the ambiguity set. Specifically, we define the ambiguity set using the Wasserstein-2 ($\mathrm{W}_{2}$) distance, a statistical measure of distribution shift, as a statistical ball centered around a nominal source distribution. We derive a tractable dual reformulation and establish the necessary optimality conditions for$\mathrm{W}_{2}$-DRQ. Building on these results, we propose a novel fixedpoint iteration algorithm, inspired by the classical Lloyd-Max algorithm, to compute locally optimal DR quantizers. We prove the monotonic convergence of the algorithm and demonstrate its effectiveness through numerical simulations. Our results highlight the performance advantages of the proposed approach under distributional uncertainty, particularly in comparison to the classical Lloyd-Max algorithm.

Prediction with expert advice serves as a fundamental model in online learning and sequential decision-making. However, in many real-world settings, this classical model proves insufficient as the feedback available to the decision-maker is often subject to noise, errors, or communication constraints. This paper provides fundamental limits on performance, quantified by the regret, in the case when the feedback is corrupted by an additive noise. Our general analysis achieves sharp regret bounds for canonical examples of such additive noise as the Gaussian distribution, the uniform distribution, and a general noise with a log-concave density. This analysis demonstrates how different noise characteristics affect regret bounds and identifies how the regret fundamentally scales as a function of the properties of the noise distribution.

Regret minimization in the problem of prediction with expert advice in the presence of noisy feedback is a fundamental challenge in online learning and sequential decision making. A general framework is proposed for designing and analyzing no-regret algorithms in this setting. This analysis, when specialized to several canonical channel models, is shown to lead to tight bounds on the regret thus characterizing how the noise level affects the regret and demonstrating that in some cases it is possible to achieve the same regret as with noiseless feedback.

We consider the problem of remotely stabilizing a linear dynamical system. In this setting, a sensor co-located with the system communicates the system's state to a controller over a noisy communication channel with feedback. The objective of the controller (decoder) is to use the channel outputs to estimate the vector state with finite zero-delay mean squared error (MSE) at the infinite horizon. It has been shown in [1] that for a vector Gauss-Markov source and either a single-input multiple-output (SIMO) or a multiple-input single-output (MISO) channel, linear codes require the minimum capacity to achieve finite MSE. This paper considers the more general problem of linear zero-delay joint-source channel coding (JSCC) of a vector-valued source over a multiple-input multiple-output (MIMO) Gaussian channel with feedback. We study sufficient and necessary conditions for linear codes to achieve finite MSE. For sufficiency, we introduce a coding scheme where each unstable source mode is allocated to a single channel for estimation. Our proof for the necessity of this scheme relies on a matrix-algebraic conjecture that we prove to be true if either the source or channel is scalar. We show that linear codes achieve finite MSE for a scalar source over a MIMO channel if and only if the best scalar sub-channel can achieve finite MSE. Finally, we provide a new counter-example demonstrating that linear codes are generally sub-optimal for coding over MIMO channels.

We consider the rate-distortion function for lossy source compression, as well as the channel capacity for error cor-rection, through the lens of distributional robustness. We assume that the distribution of the source or of the additive channel noise is unknown and lies within a Wasserstein-2 ambiguity set of a given radius centered around a specified nominal distribution, and we look for the worst-case asymptotically optimal coding rate over such an ambiguity set. Varying the radius of the ambiguity set allows us to interpolate between the worst-case and stochastic scenarios using probabilistic tools. Our problem setting fits into the paradigm of compound source / channel models introduced by Sakrison [1] and Blackwell [2], respectively. This paper shows that if the nominal distribution is Gaussian, then so is the worst-case source / noise distribution, and the compound rate-distortion / channel capacity functions admit convex formulations with Linear Matrix Inequality (LMI) constraints. These formulations yield simple closed-form expressions in the scalar case, offering insights into the behavior of Shannon limits with the changing radius of the Wasserstein-2 ambiguity set.

In this paper, we investigate the capacity of finite-state channels (FSCs) in the presence of delayed feedback. We show that the capacity of a FSC with delayed feedback can be computed as that of a new FSC with instantaneous feedback and an extended state. Consequently, graph-based methods to obtain computable upper and lower bounds on the delayed feedback capacity of unifilar FSCs are proposed. Based on these methods, we establish that the capacity of the trapdoor channel with delayed feedback of two time instances is given by$\log _{2}\left ({\frac {3}{2}}\right )$. In addition, we derive an analytical upper bound on the delayed feedback capacity of the binary symmetric channel with a no consecutive ones input constraint. This bound also serves as a novel upper bound on its non-feedback capacity, which outperforms all previously known bounds. Lastly, we demonstrate that feedback does improve the capacity of the dicode erasure channel.

This paper investigates variable-length stop-feedback codes for memoryless channels in point-to-point, multiple access, and random access communication scenarios. The proposed codes employ $L$ decoding times $n_1, n_2, \dots, n_L$ for the point-to-point and multiple access channels and $KL + 1$ decoding times for the random access channel with at most $K$ active transmitters. In the point-to-point and multiple access channels, the decoder uses the observed channel outputs to decide whether to decode at each of the allowed decoding times $n_1, \dots, n_L$, at each time telling the encoder whether or not to stop transmitting using a single bit of feedback. In the random access scenario, the decoder estimates the number of active transmitters at time $n_0$ and then chooses among decoding times $n_{k, 1}, \dots, n_{k, L}$ if it believes that there are $k$ active transmitters. In all cases, the choice of allowed decoding times is part of the code design; given fixed value $L$, allowed decoding times are chosen to minimize the expected decoding time for a given codebook size and target average error probability. The number $L$ in each scenario is assumed to be constant even when the blocklength is allowed to grow; the resulting code therefore requires only sparse feedback. The central results are asymptotic approximations of achievable rates as a function of the error probability, the expected decoding time, and the number of decoding times. A converse for variable-length stop-feedback codes with uniformly-spaced decoding times is included for the point-to-point channel.

This paper studies the third-order characteristic of nonsingular discrete memoryless channels and the Gaussian channel with a maximal-power constraint. The third-order term in our expansions employs a new quantity here called the channel skewness, which affects the approximation accuracy more significantly as the error probability decreases. For the Gaussian channel, evaluating Shannon’s 1959 random coding bound and Vazquez-Vilar’s 2021 meta-converse bound in the central limit theorem (CLT) regime enables exact computation of the channel skewness. For discrete memoryless channels, this work generalizes Moulin’s 2017 bounds on the asymptotic expansion of the maximum achievable message set size for nonsingular channels from the CLT regime to include the moderate deviations (MD) regime, thereby refining Altuğ and Wagner’s 2014 MD result. For an example binary symmetric channel and most practically important$(n, \epsilon)$pairs, including$n \in [{100, 500}]$and$\epsilon \in [10^{-10}, 10^{-1}]$, an approximation up to the channel skewness is the most accurate among several expansions in the literature. A derivation of the third-order term in the type-II error exponent of binary hypothesis testing in the MD regime is also included; the resulting third-order term is similar to the channel skewness.

We study variable-length codes for point-to-point discrete memoryless channels with noiseless unlimited-rate feed-back that occurs in L bursts. We term such codes variable-length bursty-feedback (VLBF) codes. Unlike classical codes with feedback after each transmitted code symbol, bursty feedback fits better with protocols that employ sparse feedback after a packet is sent and also with half-duplex end devices that cannot transmit and listen to the channel at the same time. We present a novel non-asymptotic achievability bound for VLBF codes with L bursts of feedback over any discrete memoryless channel. We numerically evaluate the bound over the binary symmetric channel (BSC). We perform optimization over the time instances at which feedback occurs for both our own bound and Yavas et al.’s non-asymptotic achievability bound for variable-length stop-feedback (VLSF) codes, where only a single bit is sent at each feedback instance. Our results demonstrate the advantages of richer feedback: VLBF codes significantly outperform VLSF codes at short blocklengths, especially as the error probability ϵ decreases. Remarkably, for BSC(0.11) and error probability 10−10, our VLBF code with L = 5 and expected decoding time N ≤ 400 outperforms the achievability bound given by Polyanskiy et al. for VLSF codes with L = ∞, and our VLBF code with L = 3.

Conventionally, posterior matching is investigated in channel coding and block encoding contexts – the source symbols are equiprobably distributed and are entirely known by the encoder before the transmission. In this paper, we consider a streaming source, whose symbols progressively arrive at the encoder at a sequence of deterministic times. We derive the joint source-channel coding (JSCC) reliability function for streaming over a discrete memoryless channel (DMC) with feedback. We propose a novelinstantaneous encoding phasethat operates during the symbol arriving period and achieves the JSCC reliability function for streaming when followed by a block encoding scheme that achieves the JSCC reliability function for a classical source whose symbols are fully accessible before the transmission. During the instantaneous encoding phase, the evolving message alphabet is partitioned into groups whose priors are close to the capacity-achieving distribution, and the encoder determines the group index of the actual sequence of symbols arrived so far and applies randomization to exactly match the distribution of the transmitted index to the capacity-achieving one. Surprisingly, the JSCC reliability function for streaming is equal to that for a fully accessible source, implying that the knowledge of the entire symbol sequence before the transmission offers no advantage in terms of the reliability function. For streaming over a symmetric binary-input DMC, we propose a one-phaseinstantaneous small-enough difference (SED) codethat not only achieves the JSCC reliability function, but also, thanks to its single-phase time-invariant coding rule, can be used to stabilize an unstable linear system over a noisy channel. For equiprobably distributed source symbols, we design low complexity algorithms to implement both the instantaneous encoding phase and the instantaneous SED code. The algorithms group the source sequences into sets we call types, which enable the encoder and the decoder to track the priors and the posteriors of source sequences jointly, leading to a log-linear complexity in time. While the reliability function is derived for non-degenerate DMCs, i.e., DMCs whose transition probability matrix has all positive entries, for degenerate DMCs, we design a code with instantaneous encoding that achieves zero error for all rates below Shannon’s joint source-channel coding limit.

Finding a computable expression for the feedback capacity of channels with colored Gaussian, additive noise is a long standing open problem. In this paper, we solve this problem in the scenario where the channel has multiple inputs and multiple outputs (MIMO) and the noise process is generated as the output of a time-invariant state-space model. Our main result is a computable expression for the feedback capacity in terms of a finite-dimensional convex optimization. The solution to the feedback capacity problem is obtained by formulating the finite-block counterpart of the capacity problem as a sequential convex optimization problem which leads in turn to a single-letter upper bound. This converse derivation integrates tools and ideas from information theory, control, filtering and convex optimization. A tight lower bound is realized by optimizing over a family of time-invariant policies thus showing that time-invariant inputs are optimal even when the noise process may not be stationary. The optimal time-invariant policy is used to construct a capacity-achieving and simple coding scheme for scalar channels, and its analysis reveals an interesting relation between a smoothing problem and the feedback capacity expression.

Conventionally, posterior matching is investigated in channel coding and block encoding contexts – the source symbols are equiprobably distributed and are entirely known by the encoder before the transmission. In this paper, we consider a streaming source, whose symbols progressively arrive at the encoder at a sequence of deterministic times. We derive the joint source-channel coding (JSCC) reliability function for streaming over a discrete memoryless channel (DMC) with feedback under regularity conditions. We propose a novel instantaneous encoding phase that operates during the symbol arriving period and that achieves the JSCC reliability function for streaming when followed by a block encoding scheme that achieves the JSCC reliability function for a classical source whose symbols are fully accessible before the transmission. The instantaneous encoding phase partitions the evolving message alphabet into groups whose priors are close to the capacity-achieving distribution, and randomizes the group indices to ensure that the transmitted group index has the capacity-achieving distribution. Surprisingly, the JSCC reliability function for streaming is equal to that for a fully accessible source, implying that the knowledge of the entire symbol sequence before the transmission offers no advantage in terms of the reliability function.

We consider the feedback capacity of a MIMO channel whose channel output is given by a linear state-space model driven by the channel inputs and a Gaussian process. The generality of our state-space model subsumes all previous studied models such as additive channels with colored Gaussian noise, and channels with an arbitrary dependence on previous channel inputs or outputs. The main result is a computable feedback capacity expression that is given as a convex optimization problem subject to a detectability condition. We demonstrate the capacity result on the auto-regressive Gaussian noise channel, where we show that even a single time-instance delay in the feedback reduces the feedback capacity significantly in the stationary regime. On the other hand, for large regression parameters, the feedback capacity can be achieved with delayed feedback. Finally, we show that the detectability condition is satisfied for scalar models and conjecture that it is true for MIMO models.

In this paper, we are interested in the performance of a variable-length stop-feedback (VLSF) code with m optimal decoding times for the binary-input additive white Gaussian noise channel. We first develop tight approximations to the tail probability of length-n cumulative information density. Building on the work of Yavas et al., for a given information density threshold, we formulate the integer program of minimizing the upper bound on average blocklength over all decoding times subject to the average error probability, minimum gap and integer constraints. Eventually, minimization of locally optimal upper bounds over all thresholds yields the globally minimum upper bound and the above method is called the two-step minimization. Relaxing to allow positive real-valued decoding times activates the gap constraint. We develop gap-constrained sequential differential optimization (SDO) procedure to find the optimal, gap-constrained, real-valued decoding times. In the error regime of practical interest, Polyanskiy's scheme of stopping at zero does not help. In this region, the achievability bounds estimated by the two-step minimization and gap-constrained SDO show that Polyanskiy’s achievability bound for VLSF codes can be approached with a small number of decoding times.

The channel coding problem in the moderate deviations regime is studied; here, the error probability sub-exponentially decays to zero, and the rate approaches the capacity slower than $O(1/\sqrt n )$. The main result refines Altuğ and Wagner’s moderate deviations result by deriving lower and upper bounds on the third-order term in the asymptotic expansion of the maximum achievable message set size. The third-order term of the expansion employs a new quantity called the channel skewness. For the binary symmetric channel and most practically important (n,ϵ) pairs, including n ∈ [100, 500] and ϵ ∈ [10−10,10−1], an approximation up to the channel skewness is the most accurate among several expansions in the literature.

Consider the following distributed optimization scenario. A worker has access to training data that it uses to compute the gradients while a server decides when to stop iterative computation based on its target accuracy or delay constraints. The server receives all its information about the problem instance from the worker via a rate-limited noiseless communication channel. We introduce the principle we calldifferential quantization(DQ) that prescribes compensating the past quantization errors to direct the descent trajectory of a quantized algorithm towards that of its unquantized counterpart. Assuming that the objective function is smooth and strongly convex, we prove thatdifferentially quantized gradient descent (DQ-GD)attains a linear contraction factor of$\max \{\sigma _{\mathrm {GD}}, \rho _{n} 2^{-R}\}$, where$\sigma _{\mathrm {GD}}$is the contraction factor of unquantized gradient descent (GD),$\rho _{n} \geq 1$is the covering efficiency of the quantizer, and$R$is the bitrate per problem dimension$n$. Thus at any$R\geq \log _{2} \rho _{n} /\sigma _{\mathrm {GD}}$bits, the contraction factor of DQ-GD is the same as that of unquantized GD, i.e., there is no loss due to quantization. We show a converse demonstrating that no algorithm within a certain class can converge faster than$\max \{\sigma _{\mathrm {GD}}, 2^{-R}\}$. Since quantizers exist with$\rho _{n} \to 1$as$n \to \infty $(Rogers, 1963), this means that DQ-GD is asymptotically optimal. In contrast, naively quantized GD where the worker directly quantizes the gradient barely attains$\sigma _{\mathrm {GD}} + \rho _{n}2^{-R}$. The principle of differential quantization continues to apply to gradient methods with momentum such as Nesterov’s accelerated gradient descent, and Polyak’s heavy ball method. For these algorithms as well, if the rate is above a certain threshold, there is no loss in contraction factor obtained by the differentially quantized algorithm compared to its unquantized counterpart, and furthermore, the differentially quantized heavy ball method attains the optimal contraction achievable among all (even unquantized) gradient methods. Experimental results on least-squares problems validate our theoretical analysis.

In this paper, we propose a novel code for transmitting a sequence of$n$message bits in real time over a discrete-memoryless channel (DMC) with noiseless feedback, where the message bits stream into the encoder one by one at random time instants. Similar to existing posterior matching schemes with block encoding, the encoder in our work takes advantage of the channel feedback to form channel inputs that contain the information the decoder does not yet have, and that are distributed close to the capacity-achieving input distribution, but dissimilar to the existing posterior matching schemes, the encoder performs instantaneous encoding - it immediately weaves the new message bits into a continuing transmission. A posterior matching scheme by Naghshvar et al. partitions the source messages into groups so that the group posteriors have a small-enough difference (SED) to the capacity-achieving distribution, and transmits the group index that contains the actual message. Our code adopts the SED rule to apply to the evolving message alphabet that contains all the possible variable-length strings that the source could have emitted up to that time. Our instantaneous SED code achieves better delay-reliability tradeoffs than existing feedback codes over 2-input DMCs: we establish this dominance both by simulations and via an analysis comparing the performance of the instantaneous SED code to Burnashev's reliability function. Due to the message alphabet that grows exponentially with time$t$, the complexity of the instantaneous SED code is double-exponential in$t$. To overcome this complexity barrier to practical implementation, we design a low-complexity code for binary symmetric channels that we name the instantaneous type set SED code. It groups the message strings into sets we call type sets and tracks their prior and posterior probabilities jointly, resulting in the reduction of complexity from double-exponential to$O(t^{4})$. Simulation results show that the gap in performance between the instantaneous SED code and the instantaneous type-set SED code is negligible.

Consider the following distributed optimization scenario. A worker has access to training data that it uses to compute the gradients while a server decides when to stop iterative computation based on its target accuracy or delay constraints. The only information that the server knows about the problem instance is what it receives from the worker via a rate-limited noiseless communication channel. We introduce the technique we call differential quantization (DQ) that compensates past quantization errors to make the descent trajectory of a quantized algorithm follow that of its unquantized counterpart. Assuming that the objective function is smooth and strongly convex, we prove that differentially quantized gradient descent (DQ-GD) attains a linear convergence rate of$\max\{\sigma_{\text{GD}}, \rho_{n}2^{-R}\}$, where$\sigma_{\text{GD}}$is the convergence rate of unquantized gradient descent (GD),$\rho_{n}$is the covering efficiency of the quantizer, and$R$is the bitrate per problem dimension$n$. Thus at any$R\geq\log_{2}\rho_{n}/\sigma_{\text{GD}}$, the convergence rate of DQ-GD is the same as that of unquantized GD, i.e., there is no loss due to quantization. We show a converse demonstrating that no GD-like quantized algorithm can converge faster than$\max\{\sigma_{\text{GD}}, 2^{-R}\}$. Since quantizers exist with$\rho_{n}\rightarrow 1$as$n\rightarrow\infty$(Rogers, 1963), this means that DQ-GD is asymptotically optimal. In contrast, naively quantized GD where the worker directly quantizes the gradient attains only$\sigma_{\text{GD}}+\rho_{n}2^{-R}$. The technique of differential quantization continues to apply to gradient methods with momentum such as Nesterov's accelerated gradient descent, and Polyak's heavy ball method. For these algorithms as well, if the rate is above a certain threshold, there is no loss in convergence rate obtained by the differentially quantized algorithm compared to its unquantized counterpart. Experimental results on both simulated and realworld least-squares problems validate our theoretical analysis.

Finding a computable expression for the feedback capacity of channels with non-white Gaussian, additive noise is a long standing open problem. In this paper, we solve this problem in the scenario where the channel has multiple inputs and multiple outputs (MIMO) and the noise process is generated as the output of a state-space model (a hidden Markov model). The main result is a computable characterization of the feedback capacity as a finite-dimensional convex optimization problem. Our solution subsumes all previous solutions to the feedback capacity including the auto-regressive moving-average (ARMA) noise process of first order, even if it is a non-stationary process. The capacity problem can be viewed as the problem of maximizing the measurements' entropy rate of a controlled (policy-dependent) state-space subject to a power constraint. We formulate the finite-block version of this problem as a sequential convex optimization problem, which in turn leads to a single-letter and computable upper bound. By optimizing over a family of time-invariant policies that correspond to the channel inputs distribution, a tight lower bound is realized. We show that one of the optimization constraints in the capacity characterization boils down to a Riccati equation, revealing an interesting relation between explicit capacity formulae and Riccati equations.

We investigate variable-length feedback (VLF) codes for the Gaussian point-to-point channel under maximal power, average error probability, and average decoding time constraints. Our proposed strategy chooses$K < \infty$decoding times$n_{1}, n_{2}, \ldots, n_{K}$rather than allowing decoding at any time$n=0,1,2, \ldots$. We consider stop-feedback, which is one-bit feedback transmitted from the receiver to the transmitter at times$n_{1}, n_{2},\ldots$only to inform her whether to stop. We prove an achievability bound for VLF codes with the asymptotic approximation$\ln M \approx \frac{NC(P)}{1-\epsilon}-\sqrt{N\ \ln_{(K-1)}(N)\frac{V(P)}{1-\epsilon}}$, where$\ln(K)(\cdot)$denotes the$K$-fold nested logarithm function,$N$is the average decoding time, and$C(P)$and$V(P)$are the capacity and dispersion of the Gaussian channel, respectively. Our achievability bound evaluates a non-asymptotic bound and optimizes the decoding times$n_{1}, \ldots, n_{K}$within our code architecture.

This paper investigates variable-length feedback codes for discrete memoryless channels in point-to-point, multiple access, and random access communication. The proposed nested code employs L decoding times $n_{1}, n_{2}, \ldots, n_{L}$ for the point-to-point and multiple access channels and KL decoding times $\left\{n_{k, \ell}: 1 \leq k \leq K, 1 \leq \ell \leq L\right\}$ for the random access channel with at most K active transmitters; in the latter case, decoding times $n_{k, \ell}, 1 \leq \ell \leq L$ are reserved for decoding in the scenario where the decoder believes that the number of active transmitters is k. The code has a nested structure, i.e., codewords used to decode messages from k active transmitters are prefix of codewords used to decode messages from $k+1$ active transmitters. The code employs single-bit, scheduled feedback from the receiver to the transmitters at each potential decoding time to inform the transmitters whether or not it is able to decode. Transmitters cease transmission, thereby truncating their codewords, when no further transmissions are required by the decoder. The choice of decoding times is optimized to minimize the expected decoding time subject to an error probability constraint, and second order achievability bounds are derived.

Consider the following communication scenario. An encoder observes a stochastic process and causally decides when and what to transmit about it, under a constraint on the expected number of bits transmitted per second. A decoder uses the received codewords to causally estimate the process in real time. The encoder and the decoder are synchronized in time. For a class of continuous Markov processes satisfying regularity conditions, we find the optimal encoding and decoding policies that minimize the end-to-end estimation mean-square error under the rate constraint. We show that the optimal encoding policy transmits a 1-bit codeword once the process innovation passes one of two thresholds. The optimal decoder noiselessly recovers the last sample from the 1-bit codewords and codeword-generating time stamps, and uses it to decide the running estimate of the current process, until the next codeword arrives. In particular, we show the optimal causal code for the Ornstein-Uhlenbeck process and calculate its distortion-rate function. Furthermore, we show that the optimal causal code also minimizes the mean-square cost of a continuous-time control system driven by a continuous Markov process and controlled by an additive control signal.

An$n$-dimensional source with memory is observed by$K$isolated encoders via parallel channels, who compress their observations to transmit to the decoder via noiseless rate-constrained links while leveraging their memory of the past. At each time instant, the decoder receives$K$new codewords from the observers, combines them with the past received codewords, and produces a minimum-distortion estimate of the latest block of$n$source symbols. This scenario extends the classical one-shot CEO problem to multiple rounds of communication with communicators maintaining the memory of the past. We extend the Berger-Tung inner and outer bounds to the scenario with inter-block memory, showing that the minimum asymptotically (as$n \to \infty $) achievable sum rate required to achieve a target distortion is bounded by minimal directed mutual information problems. For the Gauss-Markov source observed via$K$parallel AWGN channels, we show that the inner bound is tight and solve the corresponding minimal directed mutual information problem, thereby establishing the minimum asymptotically achievable sum rate. Finally, we explicitly bound the rate loss due to a lack of communication among the observers; that bound is attained with equality in the case of identical observation channels. The general coding theorem is proved via a new nonasymptotic bound that uses stochastic likelihood coders and whose asymptotic analysis yields an extension of the Berger-Tung inner bound to the causal setting. The analysis of the Gaussian case is facilitated by reversing the channels of the observers.

We study the stabilization of a linear control system with an unbounded random system gain where the controller must act based on a rate-limited observation of the state. More precisely, we consider the system Xn+1=AnXn+Wn-Un, where the An's are drawn independently at random at each time n from a known distribution with unbounded support, and where the controller receives at most R bits about the system state at each time from an encoder. We provide a time-varying achievable strategy to stabilize the system in a second-moment sense with fixed, finite R. While our previous result provided a strategy to stabilize this system using a variable-rate code, this work provides an achievable strategy using a fixed-rate code. The strategy we employ to achieve this is time-varying and takes different actions depending on the value of the state. It proceeds in two modes: a normal mode (or zoom-in), where the realization of Anis typical, and an emergency mode (or zoom-out), where the realization of Anis exceptionally large. To analyze the performance of the scheme we construct an auxiliary sequence that bounds the state Xn, and then bound auxiliary sequence in both the zoom-in and zoom-out modes.

This paper provides a precise error analysis for the maximum likelihood estimate â_(ML)(u1n) of the parameter a given samples u1n= (u1, ..., u_n)idrawn from a nonstationary Gauss-Markov process U_i = aU_(i-1) + Z)_i, i ≥ 1, where U0= 0, a > 1, and Ziis are independent Gaussian random variables with zero mean and variance σ2. We show a tight nonasymptotic exponentially decaying bound on the tail probability of the estimation error. Unlike previous works, our bound is tight already for a sample size of the order of hundreds. We apply the new estimation bound to find the dispersion for lossy compression of nonstationary Gauss-Markov sources. We show that the dispersion is given by the same integral formula that we derived previously for the asymptotically stationary Gauss-Markov sources, i.e., |a|<;1. New ideas in the nonstationary case include separately bounding the maximum eigenvalue (which scales exponentially) and the other eigenvalues (which are bounded by constants that depend only on a) of the covariance matrix of the source sequence, and new techniques in the derivation of our estimation error bound.

Consider a random access communication scenario over a channel whose operation is defined for any number of possible transmitters. As in the model recently introduced by Polyanskiy for the Multiple Access Channel (MAC) with a fixed, known number of transmitters, the channel is assumed to be invariant to permutations on its inputs, and all active transmitters employ identical encoders. Unlike the Polyanskiy model, in the proposed scenario, neither the transmitters nor the receiver knows which transmitters are active. We refer to this agnostic communication setup as the Random Access Channel (RAC). Scheduled feedback of a finite number of bits is used to synchronize the transmitters. The decoder is tasked with determining from the channel output the number of active transmitters, k, and their messages but not which transmitter sent which message. The decoding procedure occurs at a time ntdepending on the decoder's estimate, t, of the number of active transmitters, k, thereby achieving a rate that varies with the number of active transmitters. Single-bit feedback at each time ni, i ≤ t, enables all transmitters to determine the end of one coding epoch and the start of the next. The central result of this work demonstrates the achievability on a RAC of performance that is first-order optimal for the MAC in operation during each coding epoch. While prior multiple access schemes for a fixed number of transmitters require 2k- 1 simultaneous threshold rules, the proposed scheme uses a single threshold rule and achieves the same dispersion.

This paper presents finite-blocklength achievability bounds for the Gaussian multiple access channel (MAC) and random access channel (RAC) under average-error and maximal-power constraints. Using random codewords uniformly distributed on a sphere and a maximum likelihood decoder, the derived MAC bound on each transmitter’s rate matches the MolavianJazi-Laneman bound (2015) in its first- and second-order terms, improving the remaining terms to$\frac {1}2\frac {\log {n}}{n}+{O} \left ({\frac {1}{n}}\right)$bits per channel use. The result$\vphantom {\sum ^{R}}$then extends to a RAC model in which neither the encoders nor the decoder knows which of${K}$possible transmitters are active. In the proposed rateless coding strategy, decoding occurs at a time${n}_{t}$that depends on the decoder’s estimate${t}$of the number of active transmitters${k}$. Single-bit feedback from the decoder to all encoders at each potential decoding time${n}_{i}$,${i} \leq {t}$, informs the encoders when to stop transmitting. For this RAC model, the proposed code achieves the same first-, second-, and third-order performance as the best known result for the Gaussian MAC in operation.

Consider the following communication scenario. An encoder observes a stochastic process and causally decides when and what to transmit about it, under a constraint on bits transmitted per second. A decoder uses the received codewords to causally estimate the process in real time. The encoder and the decoder are synchronized in time. We aim to find the optimal encoding and decoding policies that minimize the end-to-end estimation mean-square error under the rate constraint. For a class of continuous Markov processes satisfying regularity conditions, we show that the optimal encoding policy transmits a 1-bit codeword once the process innovation passes one of two thresholds. The optimal decoder noiselessly recovers the last sample from the 1-bit codewords and codeword-generating time stamps, and uses it as the running estimate of the current process, until the next codeword arrives. In particular, we show the optimal causal code for the Ornstein-Uhlenbeck process and calculate its distortion-rate function.

Consider the following communication scenario. An n-dimensional source with memory is observed by K isolated encoders via parallel channels, who causally compress their observations to transmit to the decoder via noiseless rate-constrained links. At each time instant, the decoder receives K new codewords from the observers, combines them with the past received codewords, and produces a minimum-distortion estimate of the latest block of n source symbols. This scenario extends the classical one-shot CEO problem to multiple rounds of communication with communicators maintaining memory of the past. We prove a coding theorem showing that the minimum asymptotically (as n → ∞) achievable sum rate required to achieve a target distortion is equal to the directed mutual information from the observers to the decoder minimized subject to the distortion constraint and the separate encoding constraint. For the Gauss-Markov source observed via K parallel AWGN channels, we solve that minimal directed mutual information problem, thereby establishing the minimum asymptotically achievable sum rate. Finally, we explicitly bound the rate loss due to a lack of communication among the observers; that bound is attained with equality in the case of identical observation channels. The general coding theorem is proved via a new nonasymptotic bound that uses stochastic likelihood coders and whose asymptotic analysis yields an extension of the Berger-Tung inner bound to the causal setting. The analysis of the Gaussian case is facilitated by reversing the channels of the observers.

The stabilization of unstable dynamical systems using rate-limited feedback links is investigated. In the scenario of a constant-rate link and a noise with unbounded support, the fundamental limit of communication is known, but no simple algorithm to achieve it exists. The main challenge in constructing an optimal scheme is to fully exploit the communication resources while occasionally signaling the controller that a special operation needs to be taken due to a large noise observation. In this work, we present a simple and explicit algorithm that stabilizes the dynamical system and achieves the fundamental limits of communication. The new idea is to use a constrained quantizer in which certain patterns of sequences are avoided throughout the quantization process. These patterns are preserved to signal the controller that a zoom-out operation should be initiated due to large noise observation. We show that the constrained quantizer has a negligible effect on the rate, so it achieves the fundamental limit of communication. Specifically, the rate-optimal algorithm is shown to stabilize any β-moment of the state if the noise has a bounded absolute (β + ε)-moment for some ε > 0 regardless of the other noise characteristics.

This paper presents finite-blocklength achievabil- ity bounds for the Gaussian multiple access channel (MAC) and random access channel (RAC) under average-error and maximal-power constraints. Using random codewords uniformly distributed on a sphere and a maximum likelihood decoder, the derived MAC bound on each transmitter's rate matches the MolavianJazi-Laneman bound (2015) in its first- and second-order terms, improving the remaining terms to 1/2 (log n)/n + O(1/n) bits per channel use. The result then extends to a RAC model in which neither the encoders nor the decoder knows which of K possible transmitters are active. In the proposed rateless coding strategy, decoding occurs at a time ntthat depends on the decoder's estimate t of the number of active transmitters k. Single-bit feedback from the decoder to all encoders at each potential decoding time ni, i ≤ t, informs the encoders when to stop transmitting. For this RAC model, the proposed code achieves the same first-, second-, and third-order performance as the best known result for the Gaussian MAC in operation.

This work studies point-to-point, multiple access, and random access lossless source coding in the finite-blocklength regime. In each scenario, a random coding technique is developed and used to analyze third-order coding performance. Asymptotic results include a third-order characterization of the Slepian-Wolf rate region with an improved converse that relies on a connection to composite hypothesis testing. For dependent sources, the result implies that the independent encoders used by Slepian-Wolf codes can achieve the same third-order-optimal performance as a single joint encoder. The concept of random access source coding is introduced to generalize multiple access (Slepian-Wolf) source coding to the case where encoders decide independently whether or not to participate and the set of participating encoders is unknown a priori to both the encoders and the decoder. The proposed random access source coding strategy employs rateless coding with scheduled feedback. A random coding argument proves the existence of a single deterministic code of this structure that simultaneously achieves the third-order-optimal Slepian-Wolf performance for each possible active encoder set.

We propose a two-layer coding architecture for communication of multiple users over a shared slotted medium enabling joint collision resolution and decoding. Each user first encodes its information bits with an outer code for reliability, and then transmits these coded bits with possible repetitions over transmission time slots of the access channel. The transmission patterns are dictated by the inner collision-resolution code and collisions with other users' transmissions may occur. We analyze two types of codes for the outer layer: long-blocklength LDPC codes, and short-blocklength algebraic codes. With LDPC codes, a density evolution analysis enables joint optimization of both outer and inner code parameters for maximum throughput. With algebraic codes, we invoke a similar analysis by approximating their average erasure correcting capability while assuming a large number of active transmitters. The proposed low-complexity schemes operate at a significantly smaller gap to capacity than the state of the art. Our schemes apply both to a multiple access scenario where the number of users within a frame is known a priori, and to a random access scenario where that number is known only to the decoder. In the latter case, we optimize an outage probability due to the variability in user activity.

This paper treats point-to-point, multiple access and random access lossless source coding in the finite-blocklength regime. A random coding technique is developed, and its power in analyzing the third-order coding performance is demonstrated in all three scenarios. Results include a third-order-optimal characterization of the Slepian-Wolf rate region and a proof showing that for dependent sources, the independent encoders used by Slepian-Wolf codes can achieve the same third-order- optimal performance as a single joint encoder. The concept of random access source coding, which generalizes the multiple access scenario to allow for a subset of participating encoders that is unknown a priori to both the encoders and the decoder, is introduced. Contributions include a new definition of the probabilistic model for a random access-discrete multiple source, a general random access source coding scheme that employs a rateless code with sporadic feedback, and an analysis demonstrating via a random coding argument that there exists a deterministic code of the proposed structure that simultaneously achieves the third- order-optimal performance of Slepian-Wolf codes for all possible subsets of encoders.

We consider the problem of communications over the binary symmetric channel with feedback, where the information sequence is made available in a causal, possibly random, fashion. We develop a real-time variant of the renowned Horstein scheme and provide analytical guarantees for its error-probability exponential decay rate. We further use the scheme to stabilize an unstable control plant over a binary symmetric channel and compare the analytical guarantees with its empirical performance as well as with those of anytime-reliable codes.

This paper provides a precise error analysis for the maximum likelihood estimate â(u) of the parameter a given samples u = (u1, ... , un)T drawn from a nonstationary Gauss-Markov process Ui= αUi-1+ Zi, i ≥ 1, where α > 1, U0= 0, and Zz's are independent Gaussian random variables with zero mean and variance σ2. We show a tight nonasymptotic exponentially decaying bound on the tail probability of the estimation error. Unlike previous works, our bound is tight already for a sample size of the order of hundreds. We apply the new estimation bound to find the dispersion for lossy compression of nonstationary Gauss-Markov sources. We show that the dispersion is given by the same integral formula derived in our previous work [1] for the (asymptotically) stationary GaussMarkov sources, i.e., |α|<; 1. New ideas in the nonstationary case include a deeper understanding of the scaling of the maximum eigenvalue of the covariance matrix of the source sequence, and new techniques in the derivation of our estimation error bound.

We present a characterization of the Gaussian CEO rate region, in which the operational point at each boundary is characterized by one free parameter. That parameter determines the water level. Only those sensors whose observation noise is below that water level need to compress and transmit their data. Using that characterization, we present a simple (suboptimal) achievable region, expressed in terms of the difference between the noisy and the noiseless rate-distortion functions. Using that achievable region, we can explicitly bound the rate loss due to lack of cooperation among the compressors.

In successive refinement of information, the decoder refines its representation of the source progressively as it receives more encoded bits. The rate-distortion region of successive refinement describes the minimum rates required to attain the target distortions at each decoding stage. In this paper, we derive a parametric characterization of the rate-distortion region for successive refinement of abstract sources. Our characterization extends Csiszár's result to successive refinement, and generalizes a result by Tuncel and Rose, applicable for finite alphabet sources, to abstract sources. This characterization spawns a family of outer bounds to the rate-distortion region. It also enables an iterative algorithm for computing the rate-distortion region, which generalizes Blahut's algorithm to successive refinement. Finally, it leads a new nonasymptotic converse bound. In all the scenarios where the dispersion is known, this bound is second-order optimal. In our proof technique, we avoid Karush-Kuhn-Tucker conditions of optimality, and we use basic tools of probability theory. We leverage the Donsker-Varadhan lemma for the minimization of relative entropy on abstract probability spaces.

The Gauss-Markov source produces Ui= aUi-1+ Zifor i≥1, where U0= 0, |a|i~N (0,σ2) are i.i.d. Gaussian random variables. We consider lossy compression of a block of n samples of the Gauss-Markov source under squared error distortion. We obtain the Gaussian approximation for the Gauss-Markov source with excess-distortion criterion for any distortion d>0, and we show that the dispersion has a reverse waterfilling representation. This is the first finite blocklength result for lossy compression of sources with memory. We prove that the finite blocklength rate-distortion function R(n,d,ϵ) approaches the rate-distortion function ℝ(d)+√(V(d)/n) Q-1(ϵ)+0(1/√n),where V(d) is the dispersion,ϵ ∈ (0, 1) is the excess-distortion probability, and Q-1is the inverse Q-function. We give a reverse waterfilling integral representation for the dispersion V(d), which parallels that of the rate-distortion functions for Gaussian processes. Remarkably, for all 02/(1+|a|2, R(n,d,ϵ) of the Gauss-Markov source coincides with that of Zi, the i.i.d. Gaussian noise driving the process, up to the second-order term. Among novel technical tools developed in this paper is a sharp approximation of the eigenvalues of the covariance matrix of n samples of the Gauss-Markov source, and a construction of a typical set using the maximum likelihood estimate of the parameter a based on n observation.

Consider a random access communication scenario over a channel whose operation is defined for any number of possible transmitters. Inspired by the model recently introduced for the Multiple Access Channel (MAC) with a fixed, known number of transmitters by Polyanskiy, we assume that the channel is invariant to permutations on its inputs, and that all active transmitters employ identical encoders. Unlike Polyanskiy, we consider a scenario in which neither the transmitters nor the receiver know which or how many transmitters are active. We refer to this agnostic communication setup as the Random Access Channel, or RAC. Limited feedback is used to ensure that the collection of active transmitters remains fixed during each epoch. The decoder is tasked with determining from the channel output the number of active transmitters (k) and their messages but not which transmitter sent which message. The central result of this work demonstrates the achievability on a RAC of performance that is first-order optimal for the MAC in operation during each coding epoch. While prior multiple access schemes for a fixed number of transmitters require 2k- 1 simultaneous threshold rules, the proposed scheme uses a single threshold rule and achieves the same dispersion.

We study the stabilization of an unpredictable linear control system where the controller must act based on a rate-limited observation of the state. More precisely, we consider the system X_(n+1) = A_n X_n +W_n –U_n, where the A_n's are drawn independently at random at each time n from a known distribution with unbounded support, and where the controller receives at most R bits about the system state at each time from an encoder. We provide a time-varying achievable strategy to stabilize the system in a second-moment sense with fixed, finite R. While our previous result provided a strategy to stabilize this system using a variable-rate code, this work provides an achievable strategy using a fixed-rate code. The strategy we employ to achieve this is time-varying and takes different actions depending on the value of the state. It proceeds in two modes: a normal mode (or zoom-in), where the realization of A_n is typical, and an emergency mode (or zoom-out), where the realization of A_n is exceptionally large.

The entropy power inequality (EPI) has a fundamental role in Information Theory, and has deep connections with famous geometric inequalities. In particular, it is often compared to the Brunn-Minkowski inequality in convex geometry. In this article, we further strengthen the relationships between the EPI and geometric inequalities. Specifically, we establish an equivalence between a strong form of reverse EPI and the hyperplane conjecture, which is a long-standing conjecture in high-dimensional convex geometry. We also provide a simple proof of the hyperplane conjecture for a certain class of distributions, as a straightforward consequence of the EPI.

The Gauss-Markov source produces Ui=aUi-1+ Zi for i ≥ 1, where and Zi ~ N(0, σ2) are i.i.d. Gaussian random variables. We consider lossy compression of a block of n samples of the Gauss-Markov source under squared error distortion. We obtain the Gaussian approximation for the Gauss-Markov source with excess-distortion criterion for any distortion d > 0, and we show that the dispersion has a reverse waterfilling representation. This is the first finite blocklength result for lossy compression of sources with memory. We prove that the finite blocklength rate-distortion function R(n, d, ε) approaches the rate-distortion function R(d) as R(n, d, ε) = R(d)+√{[V(d)/n]}Q-1(ε)+o([1/(√n)]), where V(d) is the dispersion, ε ∈ (0,1) is the excess-distortion probability, and Q-1is the inverse of the Q-function. We give a reverse waterfilling integral representation for the dispersion V (d), which parallels that of the rate-distortion functions for Gaussian processes. Remarkably, for all 02,R(n, d, c)of the Gauss-Markov source coincides with that of Zi, the i.i.d. Gaussian noise driving the process, up to the second-order term. Among novel technical tools developed in this paper is a sharp approximation of the eigenvalues of the covariance matrix of n samples of the Gauss-Markov source, and a construction of a typical set using the maximum likelihood estimate of the parameter a based on n observations.

The emergence of networks of many devices in the context of cyber-physical systems motivates novel solutions for communication over random access channels. Currently deployed random access protocols attempt to avoid collisions, and target the performance of a scheduled multiple access system (a strategy known to be only suboptimal from the information-theoretic perspective). In contrast, in this paper, we allow collisions among the transmissions of different users. We consider code design for random access channels with erasures in which the number of users in each frame is unknown at the transmitters but known at the receiver, and we present a two-layer coding architecture for joint contention resolution and erasure correction. For random LDPC codes based on this scheme, the density evolution is asymptotically analyzed, which enables optimized code design for maximized throughput with constrained outage. The results demonstrate that the proposed low-complexity scheme approaches the outage capacity of the random access channel with erasures when the average number of active users is small.

In successive refinement of information, the decoder refines its representation of the source progressively as it receives more encoded bits. The rate-distortion region of successive refinement describes the minimum rates required to attain the target distortions at each decoding stage. In this paper, we derive a parametric characterization of the rate-distortion region for successive refinement of abstract sources. Our characterization extends Csiszar's result [1] to successive refinement, and generalizes a result by Tuncel and Rose [2], applicable for finite alphabet sources, to abstract sources. The new characterization leads to a family of outer bounds to the rate-distortion region. It also enables new nonasymptotic converse bounds.

We derive a lower bound on the differential entropy for symmetric log-concave random variable X in terms of the p-th absolute moment of X, which shows that entropy and p-th absolute moment of a symmetric log-concave random variable are comparable. We apply our bound to study the rate distortion function under distortion measure |x - x̂|rfor sources that follow a log-concave probability distribution. In particular, we establish that the difference between the rate distortion function and the Shannon lower bound is at most log(√2e) ≈ 1.9 bits, independently of r and the target distortion d. For mean-square error distortion, the difference is at most log √πe ≈ 1.55 bits, regardless of d. Our results generalize to the case of vector X. Our proof technique leverages tools from convex geometry.

A key result of classical information theory states that if the rate of a randomly generated codebook is less than the mutual information between the channel's input and output, then the probability that that codebook has negligible error goes to one as the blocklength goes to infinity. In an attempt to bridge the gap between the probabilistic world of classical information theory and the combinatorial world of zero-error information theory, this work derives necessary and sufficient conditions on the rate so that the probability that a randomly generated codebook operated under list decoding (for any fixed list size) has zero error probability goes to one as the blocklength goes to infinity. Furthermore, this work extends the classical birthday problem to an information-theoretic setting, which results in the definition of a “noisy” counterpart of Rényi entropy, analogous to how mutual information can be considered a noisy counterpart of Shannon entropy.

We consider the problem of sequential transmission of Gauss-Markov sources. We show that in the limit of large spatial block lengths, greedy compression with respect to the squared error distortion is optimal; that is, there is no tension between optimizing the distortion of the source in the current time instant and that of future times. We then extend this result to the case where at time t a random compression rate rtis allocated independently of the rate at other time instants. This, in turn, allows us to derive the optimal performance of sequential coding over packet-erasure channels with instantaneous feedback. For the case of packet erasures with delayed feedback, we connect the problem to that of compression with side information that is known at the encoder and may be known at the decoder - where the most recent packets serve as side information that may have been erased, and demonstrate that the loss due to a delay by one time unit is rather small.

This paper quantifies the fundamental limits of variable-length transmission of a general (possibly analog) source over a memoryless channel with noiseless feedback, under a distortion constraint. We consider excess distortion, average distortion, and guaranteed distortion (d-semifaithful codes). In contrast to the asymptotic fundamental limit, a general conclusion is that allowing variable-length codes and feedback leads to a sizable improvement in the fundamental delaydistortion tradeoff. In addition, we investigate the minimum energy required to reproduce k source samples with a given fidelity after transmission over a memoryless Gaussian channel, and we show that the required minimum energy is reduced with feedback and an average (rather than maximal) power constraint.

This paper shows new general nonasymptotic achievability and converse bounds and performs their dispersion analysis for the lossy compression problem in which the compressor observes the source through a noisy channel. While this problem is asymptotically equivalent to a noiseless lossy source coding problem with a modified distortion function, nonasymptotically there is a noticeable gap in how fast their minimum achievable coding rates approach the common rate-distortion function, as evidenced both by the refined asymptotic analysis (dispersion) and the numerical results. The size of the gap between the dispersions of the noisy problem and the asymptotically equivalent noiseless problem depends on the stochastic variability of the channel through which the compressor observes the source.

This paper quantifies the fundamental limits of variable-length transmission of a general (possibly analog) source over a memoryless channel with noiseless feedback, under a distortion constraint. We consider excess distortion, average distortion and guaranteed distortion (d-semifaithful codes). In contrast to the asymptotic fundamental limit, a general conclusion is that allowing variable-length codes and feedback leads to a sizable improvement in the fundamental delay-distortion tradeoff.

We investigate the minimum transmitted energy required to reproduce k source samples with a given fidelity after transmission over a memoryless Gaussian channel. In particular, we analyze the reduction in transmitted energy that accrues thanks to the availability of noiseless feedback. Allowing a nonvanishing excess distortion probability ∈ boosts the asymptotic fundamental limit by a factor of 1-∈, with or without feedback. If feedback is available, achieving guaranteed distortion with finite average energy is possible.

This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability ε, for lossless compression. We give nonasymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit, which is quite accurate for all but small blocklengths: (1 - ε)kH(S) - ((kV(S)/2π))1/2exp[-((Q-1(ε))2/2)], where Q-1(·) is the functional inverse of the standard Gaussian complementary cumulative distribution function, and V(S) is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of 1 - ε, but this asymptotic limit is approached from below, i.e, larger source dispersions and shorter blocklengths are beneficial. Variable-length lossy compression under an excess distortion constraint is shown to exhibit similar properties.

This paper shows the strong converse and the dispersion of memoryless channels with cost constraints and performs a refined analysis of the third-order term in the asymptotic expansion of the maximum achievable channel coding rate, showing that it is equal to (1/2)((log n)/n) in most cases of interest. The analysis is based on a nonasymptotic converse bound expressed in terms of the distribution of a random variable termed the b-tilted information density, which plays a role similar to that of the d-tilted information in lossy source coding. We also analyze the fundamental limits of lossy joint-source-channel coding over channels with cost constraints.

This paper studies the fundamental limits of the minimum average length of variable-length compression when a nonzero error probability ε is tolerated. We give non-asymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit which is quite accurate for all but small blocklengths: equation where Q-1(·) is the functional inverse of the Q-function and V (S) is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of 1-ε, but also this asymptotic limit is approached from below, i.e. a larger source dispersion and shorter blocklengths are beneficial. Further, we show that variable-length lossy compression under excess distortion constraint also exhibits similar properties.

This paper shows the strong converse and the dispersion of memoryless channels with cost constraints. The analysis is based on a new non-asymptotic converse bound expressed in terms of the distribution of a random variable termed the b-tilted information density, which plays a role similar to that of the information density in channel coding without cost constraints. We also analyze the fundamental limits of lossy joint-source-channel coding over channels with cost constraints.

This paper shows new general nonasymptotic achievability and converse bounds and performs their dispersion analysis for the lossy compression problem in which the compressor observes the source through a noisy channel. While this problem is asymptotically equivalent to a noiseless lossy source coding problem with a modified distortion function, nonasymptotically there is a difference in how fast their minimum achievable coding rates approach the rate-distortion function, providing yet another example where at finite blocklengths one must put aside traditional asymptotic thinking.

This paper finds new tight finite-blocklength bounds for the best achievable lossy joint source-channel code rate, and demonstrates that joint source-channel code design brings considerable performance advantage over a separate one in the nonasymptotic regime. A joint source-channel code maps a block ofksource symbols onto a length-nchannel codeword, and the fidelity of reproduction at the receiver end is measured by the probability ε that the distortion exceeds a given thresholdd. For memoryless sources and channels, it is demonstrated that the parameters of the best joint source-channel code must satisfynC-kR(d) ≈ √(nV+k V(d))Q-1(ε), whereCandVare the channel capacity and channel dispersion, respectively;R(d) andV(d) are the source rate-distortion and rate-dispersion functions; andQis the standard Gaussian complementary cumulative distribution function. Symbol-by-symbol (uncoded) transmission is known to achieve the Shannon limit when the source and channel satisfy a certain probabilistic matching condition. In this paper, we show that even when this condition is not satisfied, symbol-by-symbol transmission is, in some cases, the best known strategy in the nonasymptotic regime.

Convexity properties of error rates of a class of decoders, including the maximum-likelihood/min-distance one as a special case, are studied for arbitrary constellations, bit mapping, and coding. Earlier results obtained for the additive white Gaussian noise channel are extended to a wide class of noise densities, including unimodal and spherically invariant noise. Under these broad conditions, symbol and bit error rates are shown to be convex functions of the signal-to-noise ratio (SNR) in the high-SNR regime with an explicitly determined threshold, which depends only on the constellation dimensionality and minimum distance, thus enabling an application of the powerful tools of convex optimization to such digital communication systems in a rigorous way. It is the decreasing nature of the noise power density around the decision region boundaries that ensures the convexity of symbol error rates in the general case. The known high/low-SNR bounds of the convexity/concavity regions are tightened and no further improvement is shown to be possible in general. The high-SNR bound fits closely into the channel coding theorem: all codes, including capacity-achieving ones, whose decision regions include the hardened noise spheres (from the noise sphere hardening argument in the channel coding theorem), satisfy this high-SNR requirement and thus has convex error rates in both SNR and noise power. We conjecture that all capacity-achieving codes have convex error rates. Convexity properties in signal amplitude and noise power are also investigated. Some applications of the results are discussed. In particular, it is shown that fading is convexity-preserving and is never good in low dimensions under spherically invariant noise, which may also include any linear diversity combining.

This paper shows new tight finite-blocklength bounds for the best achievable lossy joint source-channel code rate, and demonstrates that joint source-channel code design brings considerable performance advantage over a separate one in the non-asymptotic regime. A joint source-channel code maps a block of k source symbols onto a length - n channel codeword, and the fidelity of reproduction at the receiver end is measured by the probability ϵ that the distortion exceeds a given threshold d. For memoryless sources and channels, it is demonstrated that the parameters of the best joint source-channel code must satisfy nC - kR(d) ≈ √(nV + kV(d)) Q-1(ϵ), where C and V are the channel capacity and dispersion, respectively; R(d) and V(d) are the source rate-distortion and rate-dispersion functions; and Q is the standard Gaussian complementary cdf.

We revisit the dilemma of whether one should or should not code when operating under delay constraints. In those curious cases when the source and the channel are probabilistically matched so that symbol-by-symbol coding is optimal in terms of the average distortion achieved, we show that it also achieves the dispersion of joint source-channel coding. Moreover, even in the absence of such probabilistic matching between the source and the channel, symbol-by-symbol transmission, though asymptotically suboptimal, might outperform not only separate source-channel coding but also the best known random-coding joint source-channel coding achievability bound in the finite blocklength regime.

This paper studies the minimum achievable source coding rate as a function of blocklengthnand probability ϵ that the distortion exceeds a given leveld. Tight general achievability and converse bounds are derived that hold at arbitrary fixed blocklength. For stationary memoryless sources with separable distortion, the minimum rate achievable is shown to be closely approximated byR(d) + √V(d)/(n)Q-1(ϵ), whereR(d) is the rate-distortion function,V(d) is the rate dispersion, a characteristic of the source which measures its stochastic variability, andQ-1(·) is the inverse of the standard Gaussian complementary cumulative distribution function.

The aim of compressed sensing is to recover attributes of sparse signals using very few measurements. Given an overall bit budget for quantization, this paper demonstrates that there is value to redundant measurement. The measurement matrices considered here are required to have the property that signal recovery is still possible even after dropping certain subsets of D measurements. It introduces the concept of a measurement matrix that is weakly democratic in the sense that the amount of information about the signal carried by each of the designated D-subsets is the same. Examples of deterministic measurement matrices that are weakly democratic are constructed by exponentiating codewords from the binary second order Reed Muller code. The value in rejecting D measurements that are on average larger, is to be able to provide a finer grid for vector quantization of the remaining measurements, even after discounting the original budget by the bits used to identify the reject set. Simulation results demonstrate that redundancy improves recovery SNR, sometimes by a wide margin. Optimum performance occurs when a significant fraction of measurements are rejected.

Several optimization strategies for instantaneous rate and/or power allocation in the coded V-BLAST are studied analytically. Outage probabilities and system capacities of these strategies in a spatial multiplexing system are compared under generic settings. Since the conventional waterfilling algorithm is suboptimal for the coded V-BLAST, a recently-proposed “fractional waterfilling” algorithm is studied, which simultaneously maximizes the system capacity and minimizes the outage probability. A comparative, closed-form performance analysis of this and other algorithms is presented, including bounds on the outage probability and its low-outage approximations. The fractional waterfilling algorithm attains the full MIMO channel diversity and outperforms the other algorithms by a wide margin.

This paper studies the minimum achievable source coding rate as a function of blocklength n and tolerable distortion level d. Tight general achievability and converse bounds are derived that hold at arbitrary fixed blocklength. For stationary memoryless sources with separable distortion, the minimum rate achievable is shown to be q closely approximated by R(d) + √v(d)/nQ-1(ϵ), where R(d) is the rate-distortion function, V (d) is the rate dispersion, a characteristic of the source which measures its stochastic variability, Q-1(·) is the inverse of the standard Gaussian complementary cdf, and ϵ is the probability that the distortion exceeds d. The new bounds and the second-order approximation of the minimum achievable rate are evaluated for the discrete memoryless source with symbol error rate distortion. In this case, the second-order approximation reduces to R(d) + 1/2 log n/n if the source is non-redundant.

For an i.i.d. Gaussian source with variance σ2, we show that it is necessary to spend ½ ln σ2/d + 1/√(2n) Q-1(ε) + O (ln n/n) nats per sample in order to reproduce n source samples within mean-square error d with probability at least 1 - ε, where Q-1(·) is the inverse of the standard Gaussian complementary cdf. The first-order term is the rate-distortion function of the Gaussian source, while the second-order term measures its stochastic variability. We derive new achievability and converse bounds that are valid at any blocklength and show that the second-order approximation is tightly wedged between them, thus providing a concise and accurate approximation of the minimum achievable source coding rate at a given fixed blocklength (unless the blocklength is very small).

An analytical framework for performance analysis and optimization of coded V-BLAST is developed. Average power and/or rate allocations to minimize the outage probability as well as their robustness and dual problems are investigated. Compact, closed-form expressions for the optimum allocations and corresponding system performance are given. The uniform power allocation is shown to be near optimum in the low outage regime in combination with the optimum rate allocation. The average rate allocation provides the largest performance improvement (extra diversity gain), and the average power allocation offers a modest SNR gain limited by the number of transmit antennas but does not increase the diversity gain. The dual problems are shown to have the same solutions as the primal ones. All these allocation strategies are shown to be robust. The reported results also apply to coded multiuser detection and channel equalization systems relying on successive interference cancellation.

Several instantaneous optimization strategies for rate and/or power allocation in the coded V-BLAST are studied analytically. Outage probabilities and system capacities of these strategies in a spatial multiplexing system are compared under generic settings. The conventional waterfilling algorithm is shown to be suboptimal for the coded V-BLAST and a new algorithm ("fractional water-filling") is proposed, which simultaneously maximizes the system capacity and minimizes the outage probability. Closed-form performance analysis of the considered algorithms is given, and the fractional water-filling algorithm is shown to attain the full MIMO channel diversity, significantly outperforming other strategies. Many of the results also apply to generic multi-stream transmission systems (e.g. spatial multiplexing on the channel eigenmodes, OFDM) or the systems relying on successive interference cancelation (multi-user detection, channel equalization).

Motivated by a wide-spread use of convex optimization techniques, convexity properties of bit error rate of the maximum likelihood detector operating in the AWGN channel are studied for arbitrary constellations and bit mappings, which also includes coding under maximum-likelihood decoding. Under this generic setting, the pairwise probability of error and bit error rate are shown to be convex functions of the SNR and noise power in the high SNR/low noise regime with explicitly-determined boundary. Any code, including capacity-achieving ones, whose decision regions include the hardened noise spheres (from the noise sphere hardening argument in the channel coding theorem) satisfies this high SNR requirement and thus has convex error rates in both SNR and noise power. We conjecture that all capacity-achieving codes have convex error rates.

Motivated by a recent surge of interest in convex optimization techniques, convexity/concavity properties of error rates of the maximum likelihood detector operating in the AWGN channel are studied and extended to frequency-flat slow-fading channels. Generic conditions are identified under which the symbol error rate (SER) is convex/concave for arbitrary multidimensional constellations. In particular, the SER is convex in SNR for any one- and two-dimensional constellation, and also in higher dimensions at high SNR. Pairwise error probability and bit error rate are shown to be convex at high SNR, for arbitrary constellations and bit mapping. Universal bounds for the SER first and second derivatives are obtained, which hold for arbitrary constellations and are tight for some of them. Applications of the results are discussed, which include optimum power allocation in spatial multiplexing systems, optimum power/time sharing to decrease or increase (jamming problem) error rate, an implication for fading channels (¿fading is never good in low dimensions¿) and optimization of a unitary-precoded OFDM system. For example, the error rate bounds of a unitary-precoded OFDM system with QPSK modulation, which reveal the best and worst precoding, are extended to arbitrary constellations, which may also include coding. The reported results also apply to the interference channel under Gaussian approximation, to the bit error rate when it can be expressed or approximated as a nonnegative linear combination of individual symbol error rates, and to coded systems.

An analytical framework for minimizing the outage probability of a coded spatial multiplexing system while keeping the rate close to the capacity is developed. Based on this framework, specific strategies of optimum power and rate allocation for the coded V-BLAST architecture are obtained and its performance is analyzed. A fractional waterfilling algorithm, which is shown to optimize both the capacity and the outage probability of the coded V-BLAST, is proposed. Compact, closed-form expressions for the optimum allocation of the average power are given. The uniform allocation of average power is shown to be near optimum at moderate to high SNR for the coded V-BLAST with the average rate allocation (when per-stream rates are set to match the per-stream capacity). The results reported also apply to multiuser detection and channel equalization relying on successive interference cancelation.

A unified analytical framework for optimum power allocation in the unordered V-BLAST algorithm and its comparative performance analysis are presented. Compact closed-form approximations for the optimum power allocation are derived, based on average total and block error rates. The choice of the criterion has little impact on the power allocation and, overall, the optimum strategy is to allocate more power to lower step transmitters and less to higher ones. High-SNR approximations for optimized average block and total error rates are given. The SNR gain of optimization is rigorously defined and studied using analytical tools, including lower and upper bounds, high and low SNR approximations. The gain is upper bounded by the number of transmit antennas, for any modulation format and type of fading channel. While the average optimization is less complex than the instantaneous one, its performance is almost as good at high SNR. A measure of robustness of the optimized algorithm is introduced and evaluated. The optimized algorithm is shown to be robust to perturbations in individual and total transmit powers. Based on the algorithm robustness, a pre-set power allocation is suggested as a low-complexity alternative to the other optimization strategies, which exhibits only a minor loss in performance over the practical SNR range.

Comprehensive performance analysis of the unordered V-BLAST algorithm with various power allocation strategies is presented, which makes use of analytical tools and resorts to Monte-Carlo simulations for validation purposes only. High-SNR approximations for the optimized average block and total error rates are given. The SNR gain of optimization is rigorously defined and studied using analytical tools, including lower and upper bounds, high and low SNR approximations. The gain is upper bounded by the number of transmitters, for any modulation format and any type of fading This upper bound is achieved at high SNR by the considered optimization strategies. While the average optimization is less complex than the instantaneous one, its performance is almost as good at high SNR. A measure of robustness of the optimized algorithm is introduced and evaluated, including compact closed-form approximations. The optimized algorithm is shown to be robust to perturbations in individual and total transmit powers. Based on the algorithm robustness, a pre-set power allocation is suggested as a low-complexity alternative to the other optimization strategies, which exhibits only a minor loss in performance over the practical SNR range.

Convexity/concavity properties of symbol error rates (SER) of the maximum likelihood detector operating in the AWGN channel (non-fading and fading) are studied. Generic conditions are identified under which the SER is a convex/concave function of the SNR. Universal bounds for the SER 1st and 2nd derivatives are obtained, which hold for arbitrary constellations and are tight for some of them. Applications of the results are discussed, which include optimum power allocation in spatial multiplexing systems, optimum power/time sharing to decrease or increase (jamming problem) error rate, and implication for fading channels.