We establish the fundamental limits of lossless analog compression by considering the recovery of arbitrary random vectors x ∈ Rmfrom the noiseless linear measurements y = Ax with measurement matrix A ∈ Rn×m. Our theory is inspired by the groundbreaking work of Wu and Verdú (2010) on almost lossless analog compression but applies to the nonasymptotic, i.e., fixed-m case, and considers zero error probability. Specifically, our achievability result states that, for Lebesgue-almost all A, the random vector x can be recovered with zero error probability provided that n > K(x), where K(x) is given by the infimum of the lower modified Minkowski dimension over all support sets U of x (i.e., sets U ⊆ Rmwith P[x ∈ U] = 1). We then particularize this achievability result to the class of s-rectifiable random vectors as introduced in Koliander et al. (2016); these are random vectors of absolutely continuous distribution-with respect to the s-dimensional Hausdorff measure-supported on countable unions of s-dimensional C1-submanifolds of Rm. Countable unions of C1-submanifolds include essentially all signal models used in the compressed sensing literature such as the standard union of subspaces model underlying much of compressed sensing theory and spectrum-blind sampling, smooth submanifolds, block-sparsity, and low-rank matrices as considered in the matrix completion problem. Specifically, we prove that, for Lebesgue-almost all A, s-rectifiable random vectors x can be recovered with zero error probability from n > s linear measurements. This threshold is, however, found not to be tight as exemplified by the construction of an s-rectifiable random vector that can be recovered with zero error probability from n <; s linear measurements. Motivated by this observation, we introduce the new class of s-analytic random vectors, which admit a strong converse in the sense of n ≥ s being necessary for recovery with probability of error smaller than one. The central conceptual tools in the development of our theory are geometric measure theory and the theory of real analytic functions.

This paper is concerned with a rate-distortion theory for sequences of i.i.d. random variables with general distribution supported on general sets including manifolds and fractal sets. Manifold structures are prevalent in data science, e.g., in compressed sensing, machine learning, image processing, and handwritten digit recognition. Fractal sets find application in image compression and in modeling of Ethernet traffic. We derive a lower bound on the (single-letter) rate-distortion function that applies to random variables$X$of general distribution$\mu_{X}$and for continuous$X$reduces to the classical Shannon lower bound. Moreover, our lower bound is explicit up to a parameter obtained by solving a convex optimization problem in a nonnegative real variable. The only requirement for the bound to apply is the existence of a$\sigma$-finite reference measure$\mu$, for$X$(i.e., a measure$\mu$with$\mu x\ll\mu$and such that the generalized entropy$h_{\mu}(X)$is finite) satisfying a certain subregularity condition. This condition is very general and prevents the reference measure$\mu$from being highly concentrated on balls of small radii. To illustrate the wide applicability of our result, we evaluate the lower bound for a random variable distributed uniformly on a manifold, namely, the unit circle, and a random variable distributed uniformly on a self-similar set, namely, the middle third Cantor set.

We propose an information-theoretic framework for analog signal separation. Specifically, we consider the problem of recovering two analog signals, modeled as general random vectors, from the noiseless sum of linear measurements of the signals. Our framework is inspired by the groundbreaking work of Wu and Verdú (2010) on analog compression and encompasses, inter alia, inpainting, declipping, super-resolution, the recovery of signals corrupted by impulse noise, and the separation of (e.g., audio or video) signals into two distinct components. The main results we report are general achievability bounds for the compression rate, i.e., the number of measurements relative to the dimension of the ambient space the signals live in, under either measurability or Hölder continuity imposed on the separator. Furthermore, we find a matching converse for sources of mixed discrete-continuous distribution. For measurable separators our proofs are based on a new probabilistic uncertainty relation, which shows that the intersection of generic subspaces with general sets of sufficiently small Minkowski dimension is empty. Hölder continuous separators are dealt with by introducing the concept of regularized probabilistic uncertainty relations. The probabilistic uncertainty relations we develop are inspired by embedding results in dynamical systems theory due to Sauer et al. (1991) and-conceptually-parallel classical Donoho-Stark and Elad-Bruckstein uncertainty principles at the heart of compressed sensing theory. Operationally, the new uncertainty relations take the theory of sparse signal separation beyond traditional sparsity-as measured in terms of the number of non-zero entries-to the more general notion of low description complexity as quantified by Minkowski dimension. Finally, our approach also allows to significantly strengthen key results in Wu and Verdú (2010).

We establish the fundamental limits of lossless linear analog compression by considering the recovery of random vectors x ∈ ℝmfrom the noiseless linear measurements y = Ax with measurement matrix A ∈ ℝn×m. Specifically, for a random vector x ∈ ℝmof arbitrary distribution we show that x can be recovered with zero error probability from n > inf dimMB(U) linear measurements, where dimMB(·) denotes the lower modified Minkowski dimension and the infimum is over all sets U ⊆ ℝmwith P[x ∈ U] = 1. This achievability statement holds for Lebesgue almost all measurement matrices A. We then show that s-rectifiable random vectors-a stochastic generalization of s-sparse vectors-can be recovered with zero error probability from n > s linear measurements. From classical compressed sensing theory we would expect n ≥ s to be necessary for successful recovery of x. Surprisingly, certain classes of s-rectifiable random vectors can be recovered from fewer than s measurements. Imposing an additional regularity condition on the distribution of s-rectifiable random vectors x, we do get the expected converse result of s measurements being necessary. The resulting class of random vectors appears to be new and will be referred to as s-analytic random vectors.

Entropy and differential entropy are important quantities in information theory. A tractable extension to singular random variables-which are neither discrete nor continuous- has not been available so far. Here, we present such an extension for the practically relevant class of integer-dimensional singular random variables. The proposed entropy definition contains the entropy of discrete random variables and the differential entropy of continuous random variables as special cases. We show that it transforms in a natural manner under Lipschitz functions, and that it is invariant under unitary transformations. We define joint entropy and conditional entropy for integer-dimensional singular random variables, and we show that the proposed entropy conveys useful expressions of the mutual information. As first applications of our entropy definition, we present a result on the minimal expected codeword length of quantized integer-dimensional singular sources and a Shannon lower bound for integer-dimensional singular sources.

The estimation of a random vector with independent components passed through a linear transform followed by a componentwise (possibly nonlinear) output map arises in a range of applications. Approximate message passing (AMP) methods, based on Gaussian approximations of loopy belief propagation, have recently attracted considerable attention for such problems. For large random transforms, these methods exhibit fast convergence and admit precise analytic characterizations with testable conditions for optimality, even for certain non-convex problem instances. However, the behavior of AMP under general transforms is not fully understood. In this paper, we consider the generalized AMP (GAMP) algorithm and relate the method to more common optimization techniques. This analysis enables a precise characterization of the GAMP algorithm fixed points that applies to arbitrary transforms. In particular, we show that the fixed points of the so-called max-sum GAMP algorithm for MAP estimation are critical points of a constrained maximization of the posterior density. The fixed points of the sum-product GAMP algorithm for estimation of the posterior marginals can be interpreted as critical points of a certain free energy.

We propose an information-theoretic framework for matrix completion. The theory goes beyond the low-rank structure and applies to general matrices of “low description complexity”. Specifically, we consider random matrices X ∈ ℝm×nof arbitrary distribution (continuous, discrete, discrete-continuous mixture, or even singular). With S ⊆ ℝm×nan ε-support set of X, i.e., P[X ∈ S] ≥ 1 - ε, and equation denoting the lower Minkowski dimension of S, we show that equation measurements of the form 〈Ai,X〉, with Aidenoting the measurement matrices, suffice to recover X with probability of error at most ε. The result holds for Lebesgue a.a. Aiand does not need incoherence between the Aiand the unknown matrix X. We furthermore show that equation measurements also suffice to recover the unknown matrix X from measurements taken with rank-one Ai, again this applies to a.a. rank-one Ai. Rank-one measurement matrices are attractive as they require less storage space than general measurement matrices and can be applied faster. Particularizing our results to the recovery of low-rank matrices, we find that k > (m+n-r)r measurements are sufficient to recover matrices of rank at most r. Finally, we construct a class of rank-r matrices that can be recovered with arbitrarily small probability of error from k <; (m + n - r)r measurements.

We propose an information-theoretic framework for phase retrieval. Specifically, we consider the problem of recovering an unknown vector x ∈ ℝnup to an overall sign factor from m = ⌊Rn⌋ phaseless measurements with compression rate R and derive a general achievability bound for R. Surprisingly, it turns out that this bound on the compression rate is the same as the one for almost lossless analog compression obtained by Wu and Verdú (2010): Phaseless linear measurements are “as good” as linear measurements with full phase information in the sense that ignoring the sign of m measurements only leaves us with an ambiguity with respect to an overall sign factor of x.

Entropy and differential entropy are important quantities in information theory. A tractable extension to singular random variables (which are neither discrete nor continuous) has not been available so far. Here, we propose such an extension for the practically relevant class of singular probability measures that are supported on a lower-dimensional subset of Euclidean space. We show that our entropy transforms in a natural manner under Lipschitz functions and that it conveys useful expressions of the mutual information. Potential applications of the proposed entropy definition include capacity calculations for the vector interference channel, compressed sensing in a probabilistic setting, and capacity bounds for block-fading channel models.

We analyze the capacity of a continuous-time, time-selective, Rayleigh block-fading channel in the high signal-to-noise ratio (SNR) regime. The fading process is assumed stationary within each block and to change independently from block to block; furthermore, its realizations are not known a priori to the transmitter and the receiver (noncoherent setting). A common approach to analyzing the capacity of this channel is to assume that the receiver performs matched filtering followed by sampling at symbol rate (symbol matched filtering). This yields a discrete-time channel in which each transmitted symbol corresponds to one output sample. Liang & Veeravalli (2004) showed that the capacity of this discrete-time channel grows logarithmically with the SNR, with a capacity pre-log equal to 1-Q/N. Here, N is the number of symbols transmitted within one fading block, and Q is the rank of the covariance matrix of the discrete-time channel gains within each fading block. In this paper, we show that symbol matched filtering is not a capacity-achieving strategy for the underlying continuous-time channel. Specifically, we analyze the capacity pre-log of the discrete-time channel obtained by oversampling the continuous-time channel output, i.e., by sampling it faster than at symbol rate. We prove that by oversampling by a factor two one gets a capacity pre-log that is at least as large as 1-1/N. Since the capacity pre-log corresponding to symbol-rate sampling is 1-Q/N, our result implies indeed that symbol matched filtering is not capacity achieving at high SNR.

We study the high-signal-to-noise-ratio capacity of generic multiple-input multiple-output (MIMO) Rayleigh block-fading channels in the noncoherent setting where neither transmitter nor receiver has a priori channel state information but both are aware of the channel statistics. In contrast to the well-established constant block-fading model, we allow the fading to vary within each block with a temporal correlation that is generic (in the sense used in the interference-alignment literature). We show that the number of degrees of freedom of a generic MIMO Rayleigh block-fading channel with T transmit antennas and block length N is given by T(1 - 1/N) provided that T <; N and the number of receive antennas is at least T(N - 1)/(N - T). A comparison with the constant block-fading channel (where the fading is constant within each block) shows that, for large block lengths, generic correlation increases the number of degrees of freedom by a factor of up to four.

Future wireline communication systems aspire to boost the throughput in two ways: First, they exploit higher frequencies to gain more bandwidth on shorter lines in combination with vectoring. Second, they use non-differential transmission modes (such as phantom modes, common modes, split-pair modes) to exploit more dimensions. Performance predictions for systems exploiting these techniques are of great importance for upgrading copper networks to provide Internet access or deploying copper-based backhaul systems to connect mobile base-stations. Good predictions require accurate channel models. However, channel modeling for higher frequencies and nondifferential modes is still in its infancy. A mixed deterministic/stochastic channel model is proposed to remedy this problem. The outage rate is derived based on an asymptotic (in the number of participating transceivers) analysis. As application examples, performance predictions in access networks using phantom modes and frequencies up to 200 MHz are presented.

We study the high-SNR capacity of MIMO Rayleigh block-fading channels in the noncoherent setting where neither transmitter nor receiver has a priori channel state information. We show that when the number of receive antennas is sufficiently large and the temporal correlation within each block is “generic” (in the sense used in the interference-alignment literature), the capacity pre-log is given by T(1 - 1/N) for T <; N, where T denotes the number of transmit antennas and N denotes the block length. A comparison with the widely used constant block-fading channel (where the fading is constant within each block) shows that for a large block length, generic correlation increases the capacity pre-log by a factor of about four.

The estimation of a random vector with independent components passed through a linear transform followed by a componentwise (possibly nonlinear) output map arises in a range of applications. Approximate message passing (AMP) methods, based on Gaussian approximations of loopy belief propagation, have recently attracted considerable attention for such problems. For large random transforms, these methods exhibit fast convergence and admit precise analytic characterizations with testable conditions for optimality, even for certain non-convex problem instances. However, the behavior of AMP under general transforms is not fully understood. In this paper, we consider the generalized AMP (GAMP) algorithm and relate the method to more common optimization techniques. This analysis enables a precise characterization of the GAMP algorithm fixed-points that applies to arbitrary transforms. In particular, we show that the fixed points of the so-called max-sum GAMP algorithm for MAP estimation are critical points of a constrained maximization of the posterior density. The fixed-points of the sum-product GAMP algorithm for estimation of the posterior marginals can be interpreted as critical points of a certain mean-field variational optimization.

We propose an information-theoretic framework for analog signal separation. Specifically, we consider the problem of recovering two analog signals from a noiseless sum of linear measurements of the signals. Our framework is inspired by the groundbreaking work of Wu and Verdú (2010) on almost lossless analog compression. The main results of the present paper are a general achievability bound for the compression rate in the analog signal separation problem, an exact expression for the optimal compression rate in the case of signals that have mixed discrete-continuous distributions, and a new technique for showing that the intersection of generic subspaces with subsets of sufficiently small Minkowski dimension is empty. This technique can also be applied to obtain a simplified proof of a key result in Wu and Verdú (2010).

We characterize the capacity of Rayleigh block-fading multiple-input multiple-output (MIMO) channels in the noncoherent setting where transmitter and receiver have no a priori knowledge of the realizations of the fading channel. We prove that unitary space-time modulation (USTM) is not capacity-achieving in the high signal-to-noise ratio (SNR) regime when the total number of antennas exceeds the coherence time of the fading channel (expressed in multiples of the symbol duration), a situation that is relevant for MIMO systems with large antenna arrays (large-MIMO systems). This result settles a conjecture by Zheng & Tse (2002) in the affirmative. The capacity-achieving input signal, which we refer to as Beta-variate space-time modulation (BSTM), turns out to be the product of a unitary isotropically distributed random matrix, and a diagonal matrix whose nonzero entries are distributed as the square-root of the eigenvalues of a Beta-distributed random matrix of appropriate size. Numerical results illustrate that using BSTM instead of USTM in large-MIMO systems yields a rate gain as large as 13% for SNR values of practical interest.

We find the capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel in the noncoherent setting. It is well known that for block-lengthLand rank of the channel covariance matrix equal toQ, the capacity pre-log in the single-input single-output (SISO) case is given by 1-Q/L. Here,Q/Lcan be interpreted as the pre-log penalty incurred by channel uncertainty. Our main result reveals that, by adding only one receive antenna, this penalty can be reduced to 1/Land can, hence, be made to vanish for the block-lengthL→∞, even ifQ/Lremains constant asL→∞. Intuitively, even though the SISO channels between the transmit antenna and the two receive antennas are statistically independent, the transmit signal induces enough statistical dependence between the corresponding receive signals for the second receive antenna to be able to resolve the uncertainty associated with the first receive antenna's channel and thereby make the overall system appear coherent. The proof of our main theorem is based on a deep result from algebraic geometry known as Hironaka's Theorem on the Resolution of Singularities.

We design iterative receiver schemes for a generic communication system by treating channel estimation and information decoding as an inference problem in graphical models. We introduce a recently proposed inference framework that combines belief propagation (BP) and the mean field (MF) approximation and includes these algorithms as special cases. We also show that the expectation propagation and expectation maximization (EM) algorithms can be embedded in the BP-MF framework with slight modifications. By applying the considered inference algorithms to our probabilistic model, we derive four different message-passing receiver schemes. Our numerical evaluation in a wireless scenario demonstrates that the receiver based on the BP-MF framework and its variant based on BP-EM yield the best compromise between performance, computational complexity and numerical stability among all candidate algorithms.

We analyze the capacity of Rayleigh block-fading multiple-input multiple-output (MIMO) channels in the noncoherent setting and prove that unitary space-time modulation (USTM) is not capacity-achieving when the total number of antennas exceeds the coherence time of the fading channel. This situation is relevant for MIMO systems with large antenna arrays (large-MIMO systems). Our result settles a conjecture by Zheng & Tse (2002) in the affirmative. The capacity-achieving input signal, which we refer to as Beta-variate space-time modulation (BSTM), turns out to be the product of a unitary isotropically distributed random matrix, and a diagonal matrix whose nonzero entries are distributed as the square-root of the eigenvalues of a Beta-distributed random matrix of appropriate size. Numerical results illustrate that using BSTM instead of USTM in large-MIMO systems yields a rate gain as large as 13% for SNR values of practical interest.

We establish a lower bound on the noncoherent capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel. Our result holds for arbitrary rank Q of the channel correlation matrix, arbitrary block-length L >; Q, and arbitrary number of receive antennas R, and includes the result in Morgenshtern et al. (2010) as a special case. It is well known that the capacity pre-log for this channel in the single-input single-output (SISO) case is given by 1-Q/L, where Q/L is the penalty incurred by channel uncertainty. Our result reveals that this penalty can be reduced to 1/L by adding only one receive antenna, provided that L ≥ 2Q - 1 and the channel correlation matrix satisfies mild technical conditions. The main technical tool used to prove our result is Hironaka's celebrated theorem on resolution of singularities in algebraic geometry.

An asymptotic approach to derive the ergodic capacity achieving covariance matrix for a multiple-input multiple-output (MIMO) channel is presented. The method is applicable to MIMO channels affected by separately correlated Rician fading and co-channel interference. It is assumed that the number of transmit, receive and interfering antennas grows asymptotically while their ratios, as well as the SNR and the SIR, approach finite constants. Nevertheless, it is shown that the asymptotic results represent an accurate approximation in the case of a finitely many antennas and can be used to derive the ergodic channel capacity. This is accomplished by using an iterative power allocation algorithm based on a water-filling approach. The convergence of a similar algorithm (nicknamed frozen water-filling) was conjectured in a work by Dumont et al. Here, we show that, in the Rayleigh case, the frozen water-filling algorithm may not converge while, in those cases, our proposed algorithm converges. Finally, numerical results are included in order to assess the accuracy of the asymptotic method proposed, which is compared to equivalent results obtained via Monte-Carlo simulations.

In this contribution, a multi-user receiver for M-QAM MIMO-OFDM operating in time-varying and frequency-selective channels is derived. The proposed architecture jointly performs semi-blind estimation of the channel weights and noise inverse variance, serial interference cancellation and decoding in an iterative manner. The scheme relies on a variational message-passing approach, which enables a joint design of all these functionalities or blocks but the last one. Decoding is performed using the sum-product algorithm. This is in contrast to nowadays proposed approaches in which all these blocks are designed and optimized individually. Simulation results show that the proposed receiver outperforms in coded bit-error-rate a state-of-the- art iterative receiver of same complexity, in which all blocks are designed independently. Joint block design and, as a result, the fact that the uncertainty in the channel estimation is accounted for in the proposed receiver explain this better performance.

The statistics of the mutual information of a separately correlated Rician fading multiple-input multiple-output (MIMO) channel in the presence of multiple-access interference are addressed in this paper. The approach followed is asymptotic in the number of transmit, receive, and interfering antennas, which are all assumed to grow asymptotically large while approaching finite ratios. In this asymptotic regime: i) the mean and the variance of the mutual information are calculated; and ii) the mutual information distribution is shown to converge to the Gaussian distribution, specified completely by the mean and variance, under some mild technical conditions. The asymptotic method adopted relies on two powerful tools developed in the context of theoretical physics: the replica method andsuperanalysis. The former has been already successfully applied in several research studies on MIMO systems. The application of these asymptotic results takes advantage of the fact that, in spite of being developed under the assumption of an asymptotically large number of antennas, they still represent a very accurate approximation even when the number of antennas is limited to a few units, as supported by the ample set of numerical results obtained by Monte Carlo simulations and reported in this paper.

Abstract—Channel estimation inaccuracy is known to affect significantly the error performance of coded communication systems. This applies in particular to broadband MIMO channels, often considered in conjunction with OFDM such as in the IEEE 802.11n and 802.16 standards. The focus of this work is on an 802.11n compliant MIMO-OFDM communication system. Different channel estimation techniques (based on pilot symbol insertion) are considered and their relevant error performance is analyzed. More specifically, genie-aided, mismatched, and optimum channel estimation techniques are studied with special emphasis on the last one as far as concerns the relative error performance versus complexity trade-off in suboptimum implementation. It is shown that the optimum receiver can be implemented by limiting the channel processing to the dominant eigenmodes, in order to reduce the ensuing complexity. The approach followed in this work may be seen as an extension of previous results relevant to the narrowband MIMO channel. I.

The ergodic capacity region of a multiple access separately-correlated Rician fading multiple input and multiple output (MIMO) wideband channel is investigated by using an asymptotic approach. Our channel model is sufficiently general to allow for considering different spatial correlation matrices for each user and delay at the transmitter and the receiver. We provide two algorithms which can be used to maximize the (weighted) rate sums in order to obtain the ergodic capacity region. Both algorithms are based on an asymptotic approximation of the single-user wideband mutual information. Moreover, it is shown that sum rate maximization is based on water- filling, similarly to the well known case where the transmitter has perfect channel state information. It is assumed that the number of transmit and receive antennas grows asymptotically approaching finite ratios while the number of users and the signal-to-noise ratios are kept finite. Numerical simulations show that this asymptotic approach is very accurate even when the number of antennas is as low as a few units.

The mutual information of a wideband Rician fading correlated MIMO channel is approximated by an analytic asymptotic method. The method is applied to derive the optimum input signal covariance matrix and the corresponding ergodic capacity. The numerical accuracy of the method is investigated and the effectiveness of covariance optimization is assessed with respect to the level of spatial correlation and the Rice factor.

The ergodic capacity region of a multiple access separately-correlated Rician fading MIMO channel is investigated by using an asymptotic approach. It is assumed that the number of transmit and receive antennas grow asymptotically approaching finite values while the number of users and the SNR are kept finite. It is shown by numerical results that this asymptotic approach is very accurate even when the number of antennas is as low as a few units. The ergodic capacity achieving covariance matrices for all users are derived according to the algorithm provided and the corresponding capacity is compared with the mutual information achieved by iid power allocation. Monte-Carlo simulations are also reported in order to verify the accuracy of the asymptotic results.

The mean and variance of the mutual information of a separately-correlated Rician fading MIMO channel are derived in the presence of multi-access interference, when the number of transmit and receive antennas grows asymptotically large. Perfect receive channel-state information is assumed. The results are based on the replica method and superanalysis, powerful tools developed in the context of theoretical physics. The former allows to derive the moment generating function of the mutual information and the latter is required to cope with the coupling between the signal and interference parts. Analytic asymptotic results are compared with Monte-Carlo simulations to assess the accuracy of this method when the number of antennas is small.

A simple method to derive the ergodic capacity and the corresponding capacity-achieving covariance matrix for a MIMO fading channel with multiuser interference is provided. The method applies when the fading distribution is based on the separately-correlated (Kronecker) Rician fading model (with common receive correlation), as the number of antennas grow asymptotically large. Numerical results are provided to assess the accuracy of the asymptotic analytic method.