Classical neural network approximation results take the form: for every function f and every error tolerance ϵ > 0, one constructs a neural network whose architecture and weights depend on ϵ. This paper introduces a fundamentally different approximation paradigm that reverses this quantifier order. For each target function f, we construct a single recurrent neural network (RNN) with fixed topology and fixed weights that approximates f to within any prescribed tolerance ϵ > 0 when run for sufficiently many time steps. The key mechanism enabling this quantifier reversal is temporal computation combined with weight sharing: rather than increasing network depth, the approximation error is reduced solely by running the RNN longer. This yields exponentially decaying approximation error as a function of runtime while requiring storage of only a small, fixed set of weights. Such architectures are appealing for hardware implementations where memory is scarce and runtime is comparatively inexpensive. To initiate the systematic development of this novel approximation paradigm, we focus on univariate polynomials. Our RNN constructions emulate the structural calculus underlying deep feed-forward ReLU network approximation theory-parallelization, linear combinations, affine transformations, and, most importantly, a clocked mechanism that realizes function composition within a single recurrent architecture. The resulting RNNs have size independent of the error tolerance ϵ and hidden-state dimension linear in the degree of the polynomial.

We present a condition for 1/2 degree of freedom for each user in constant$K$-user single-antenna interference channels. This condition is sufficient for all and necessary for almost all channel matrices. Moreover, it applies to all channel topologies, i.e., to fully-connected channels as well as channels that have individual links absent, reflected by corresponding zeros in the channel matrix. Moreover, it captures the essence of interference alignment by virtue of being expressed in terms of a generic injectivity condition that guarantees separability of signal and interference. Finally, we provide codebook constructions achieving 1/2 degree of freedom for each user for all channel matrices satisfying the condition we identified.

This paper develops fundamental limits of deep neural network learning by characterizing what is possible if no constraints are imposed on the learning algorithm and on the amount of training data. Concretely, we consider Kolmogorov-optimal approximation through deep neural networks with the guiding theme being a relation between the complexity of the function (class) to be approximated and the complexity of the approximating network in terms of connectivity and memory requirements for storing the network topology and the associated quantized weights. The theory we develop establishes that deep networks are Kolmogorov-optimal approximants for markedly different function classes, such as unit balls in Besov spaces and modulation spaces. In addition, deep networks provide exponential approximation accuracy-i.e., the approximation error decays exponentially in the number of nonzero weights in the network-of the multiplication operation, polynomials, sinusoidal functions, and certain smooth functions. Moreover, this holds true even for one-dimensional oscillatory textures and the Weierstrass function-a fractal function, neither of which has previously known methods achieving exponential approximation accuracy. We also show that in the approximation of sufficiently smooth functions finite-width deep networks require strictly smaller connectivity than finite-depth wide networks.

We present an explicit deep neural network construction that transforms uniformly distributed one-dimensional noise into an arbitrarily close approximation of any two-dimensional Lipschitz-continuous target distribution. The key ingredient of our design is a generalization of the "space-filling" property of sawtooth functions discovered in (Bailey & Telgarsky, 2018). We elicit the importance of depth - in our neural network construction - in driving the Wasserstein distance between the target distribution and the approximation realized by the network to zero. An extension to output distributions of arbitrary dimension is outlined. Finally, we show that the proposed construction does not incur a cost - in terms of error measured in Wasserstein-distance - relative to generating $d$-dimensional target distributions from $d$ independent random variables.

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.

Stotz et al., 2016, reported a sufficient (injectivity) condition for each user in a$K$-user single-antenna constant interference channel to achieve 1/2 degree of freedom. The present paper proves that this condition is necessary as well and hence provides an equivalence characterization of interference channel matrices allowing full degrees of freedom.

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.

Sparsity-based subspace clustering algorithms have attracted significant attention thanks to their excellent performance in practical applications. A prominent example is the sparse subspace clustering (SSC) algorithm by Elhamifar and Vidal, which performs spectral clustering based on an adjacency matrix obtained by sparsely representing each data point in terms of all the other data points via the Lasso. When the number of data points is large or the dimension of the ambient space is high, the computational complexity of SSC quickly becomes prohibitive. Dyer et al. observed that SSC-orthogonal matching pursuit (OMP) obtained by replacing the Lasso by the greedy OMP algorithm results in significantly lower computational complexity, while often yielding comparable performance. The central goal of this paper is an analytical performance characterization of SSC-OMP for noisy data. Moreover, we introduce and analyze the SSC-matching pursuit (MP) algorithm, which employs MP in lieu of OMP. Both SSC-OMP and SSC-MP are proven to succeed even when the subspaces intersect and when the data points are contaminated by severe noise. The clustering conditions we obtain for SSC-OMP and SSC-MP are similar to those for SSC and for the thresholding-based subspace clustering (TSC) algorithm due to Heckel and Bölcskei. Analytical results in combination with numerical results indicate that both SSC-OMP and SSC-MP with a data-dependent stopping criterion automatically detect the dimensions of the subspaces underlying the data. Experiments on synthetic and on real data show that SSC-MP often matches or exceeds the performance of the computationally more expensive SSC-OMP algorithm. Moreover, SSC-MP compares very favorably to SSC, TSC, and the nearest subspace neighbor algorithm, both in terms of clustering performance and running time. In addition, we find that, in contrast to SSC-OMP, the performance of SSC-MP is very robust with respect to the choice of parameters in the stopping criteria.

Deep convolutional neural networks (DCNNs) have led to breakthrough results in numerous practical machine learning tasks, such as classification of images in the ImageNet data set, control-policy-learning to play Atari games or the board game Go, and image captioning. Many of these applications first perform feature extraction and then feed the results thereof into a classifier. The mathematical analysis of DCNNs for feature extraction was initiated by Mallat, 2012. Specifically, Mallat considered so-called scattering networks based on a wavelet transform followed by the modulus non-linearity in each network layer, and proved translation invariance (asymptotically in the wavelet scale parameter) and deformation stability of the corresponding feature extractor. This paper complements Mallat's results by developing a theory that encompasses general convolutional transforms, or in more technical parlance, general semi-discrete frames (including Weyl-Heisenberg filters, curvelets, shearlets, ridgelets, wavelets, and learned filters), general Lipschitz-continuous non-linearities (e.g., rectified linear units, shifted logistic sigmoids, hyperbolic tangents, and modulus functions), and general Lipschitz-continuous pooling operators emulating, e.g., sub-sampling and averaging. In addition, all of these elements can be different in different network layers. For the resulting feature extractor, we prove a translation invariance result of vertical nature in the sense of the features becoming progressively more translation-invariant with increasing network depth, and we establish deformation sensitivity bounds that apply to signal classes such as, e.g., band-limited functions, cartoon functions, and Lipschitz functions.

Many practical machine learning tasks employ very deep convolutional neural networks. Such large depths pose formidable computational challenges in training and operating the network. It is therefore important to understand how fast the energy contained in the propagated signals (a.k.a. feature maps) decays across layers. In addition, it is desirable that the feature extractor generated by the network be informative in the sense of the only signal mapping to the all-zeros feature vector being the zero input signal. This “trivial null-set” property can be accomplished by asking for “energy conservation” in the sense of the energy in the feature vector being proportional to that of the corresponding input signal. This paper establishes conditions for energy conservation (and thus for a trivial null-set) for a wide class of deep convolutional neural network-based feature extractors and characterizes corresponding feature map energy decay rates. Specifically, we consider general scattering networks employing the modulus non-linearity and we find that under mild analyticity and high-pass conditions on the filters (which encompass, inter alia, various constructions of Weyl-Heisenberg filters, wavelets, ridgelets, (α)-curvelets, and shearlets) the feature map energy decays at least polynomially fast. For broad families of wavelets and Weyl-Heisenberg filters, the guaranteed decay rate is shown to be exponential. Moreover, we provide handy estimates of the number of layers needed to have at least ((1-ε) 100)% of the input signal energy be contained in the feature vector.

Many practical machine learning tasks employ very deep convolutional neural networks. Such large depths pose formidable computational challenges in training and operating the network. It is therefore important to understand how many layers are actually needed to have most of the input signal's features be contained in the feature vector generated by the network. This question can be formalized by asking how quickly the energy contained in the feature maps decays across layers. In addition, it is desirable that none of the input signal's features be “lost” in the feature extraction network or, more formally, we want energy conservation in the sense of the energy contained in the feature vector being proportional to that of the corresponding input signal. This paper establishes conditions for energy conservation for a wide class of deep convolutional neural networks and characterizes corresponding feature map energy decay rates. Specifically, we consider general scattering networks, and find that under mild analyticity and high-pass conditions on the filters (which encompass, inter alia, various constructions of Weyl-Heisenberg filters, wavelets, ridgelets,(α)-curvelets, and shearlets) the feature map energy decays at least polynomially. For broad families of wavelets and Weyl-Heisenberg filters, the guaranteed decay rate is shown to be exponential. Our results yield handy estimates of the number of layers needed to have at least ((1 − ε) · 100)% of the input signal energy be contained in the feature vector.

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).

First steps towards a mathematical theory of deep convolutional neural networks for feature extraction were made—for the continuous-time case—in Mallat, 2012, and Wiatowski and Bölcskei, 2015. This paper considers the discrete case, introduces new convolutional neural network architectures, and proposes a mathematical framework for their analysis. Specifically, we establish deformation and translation sensitivity results of local and global nature, and we investigate how certain structural properties of the input signal are reflected in the corresponding feature vectors. Our theory applies to general filters and general Lipschitz-continuous non-linearities and pooling operators. Experiments on handwritten digit classification and facial landmark detection—including feature importance evaluation—complement the theoretical findings.

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.

Performance analyses of subspace algorithms for cisoid parameter estimation available in the literature are predominantly of statistical nature with a focus on asymptotic-either in the sample size or the SNR-statements. This paper presents a deterministic, finite sample size, and finite-SNR performance analysis of the ESPRIT algorithm and the matrix pencil method. Our results are based, inter alia, on a new upper bound on the condition number of Vandermonde matrices with nodes inside the unit disk. This bound is obtained through a generalization of Hilbert's inequality frequently used in large sieve theory.

Wiatowski and Bölcskei, 2015, proved that deformation stability and vertical translation invariance of deep convolutional neural network-based feature extractors are guaranteed by the network structure per se rather than the specific convolution kernels and non-linearities. While the translation invariance result applies to square-integrable functions, the deformation stability bound holds for band-limited functions only. Many signals of practical relevance (such as natural images) exhibit, however, sharp and curved discontinuities and are hence not band-limited. The main contribution of this paper is a deformation stability result that takes these structural properties into account. Specifically, we establish deformation stability bounds for the class of cartoon functions introduced by Donoho, 2001.

Stotz and Bölcskei, 2015, identified an explicit condition for K/2 degrees of freedom (DoF) in constant single-antenna interference channels (ICs). This condition is expressed in terms of linear independence—over the rationals—of monomials in the off-diagonal entries of the IC matrix and is satisfied for almost all IC matrices. There is, however, a prominent class of IC matrices that admits K/2 DoF but fails to satisfy this condition. The main contribution of the present paper is a more general condition for K/2 DoF (in fact for 1/2 DoF for each user) that, inter alia, encompasses this example class. While the existing condition by Stotz and Bölcskei is of algebraic nature, the new condition is canonical in the sense of capturing the essence of interference alignment by virtue of being expressed in terms of a generic injectivity condition that guarantees separability of signal and interference.

This paper continues the Wu-Shamai-Verdú program on characterizing the degrees of freedom (DoF) of interference channels (ICs) through Rényi information dimension. Specifically, we find a single-letter formula for the DoF of vector ICs, encompassing multiple-input multiple-output ICs, time- and/or frequency-selective ICs, and combinations thereof, as well as scalar ICs as considered by Wu et al., 2015. The DoF-formula we obtain lower-bounds the DoF of all channels-with respect to the choice of the channel matrix-and upper-bounds the DoF of almost all channels. It applies to a large class of noise distributions, and its proof is based on an extension of a result by Guionnet and Shlyakthenko, 2007, to the vector case in combination with the Ruzsa triangle inequality for differential entropy introduced by Kontoyiannis and Madiman, 2015. As in scalar ICs, achieving full DoF requires the use of singular input distributions. Strikingly, in the vector case, it suffices to enforce singularity on the joint distribution of each transmit vector. This can be realized through signaling in subspaces of the ambient signal space, which is in accordance with the idea of interference alignment, and, most importantly, allows the scalar entries of the transmit vectors to have non-singular distributions. The DoF-formula for vector ICs we obtain enables a unified treatment of classical interference alignment à la Cadambe and Jafar, 2008, and Maddah-Ali et al., 2008, and the number-theoretic schemes proposed by Motahari et al., 2014, and by Etkin and Ordentlich, 2009. Moreover, it allows to calculate the DoF achieved by new signaling schemes for vector ICs. We furthermore recover the result by Cadambe and Jafar on the non-separability of parallel ICs, 2009, and we show that almost all parallel ICs are separable in terms of DoF. Finally, our results apply to complex vector ICs, thereby extending the main findings of Wu et al., 2015 to the complex case.

We establish a formal connection between the problem of characterizing degrees of freedom (DoF) in constant single-antenna interference channels (ICs) with general channel matrix and the field of additive combinatorics. The theory we develop is based on a recent breakthrough result by Hochman, 2014, in fractal geometry. Our first main contribution is an explicit condition on the channel matrix to admit full, i.e., K/2 DoF; this condition is satisfied for almost all channel matrices. We also provide a construction of corresponding full DoF-achieving input distributions. The second main result is a new DoF-formula exclusively in terms of Shannon entropy. This formula is more amenable to both analytical statements and numerical evaluations than the DoF-formula by Wu et al., 2015, which is in terms of Rényi information dimension. We then use the new DoF-formula to shed light on the hardness of finding the exact number of DoF in ICs with rational channel coefficients, and to improve the best known bounds on the DoF of a well-studied channel matrix.

This paper addresses the problem of identifying a linear time-varying (LTV) system characterized by a (possibly infinite) discrete set of delays and Doppler shifts. We prove that stable identifiability is possible if the upper uniform Beurling density of the delay-Doppler support set is strictly smaller than 1/2 and stable identifiability is impossible for densities strictly larger than 1/2. The proof of this density theorem reveals an interesting relation between LTV system identification and interpolation in the Bargmann-Fock space. Finally, we introduce a subspace method for solving the system identification problem at hand.

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 consider the problem of clustering noisy finite-length observations of stationary ergodic random processes according to their nonparametric generative models without prior knowledge of the model statistics and the number of generative models. Two algorithms, both using the L1-distance between estimated power spectral densities (PSDs) as a measure of dissimilarity, are analyzed. The first algorithm, termed nearest neighbor process clustering (NNPC), to the best of our knowledge, is new and relies on partitioning the nearest neighbor graph of the observations via spectral clustering. The second algorithm, simply referred to as k-means (KM), consists of a single k-means iteration with farthest point initialization and was considered before in the literature, albeit with a different measure of dissimilarity and with asymptotic performance results only. We show that both NNPC and KM succeed with high probability under noise and even when the generative process PSDs overlap significantly, all provided that the observation length is sufficiently large. Our results quantify the tradeoff between the overlap of the generative process PSDs, the noise variance, and the observation length. Finally, we present numerical performance results for synthetic and real data.

Deep convolutional neural networks have led to breakthrough results in practical feature extraction applications. The mathematical analysis of these networks was pioneered by Mallat [1]. Specifically, Mallat considered so-called scattering networks based on identical semi-discrete wavelet frames in each network layer, and proved translation-invariance as well as deformation stability of the resulting feature extractor. The purpose of this paper is to develop Mallat's theory further by allowing for different and, most importantly, general semi-discrete frames (such as, e.g., Gabor frames, wavelets, curvelets, shearlets, ridgelets) in distinct network layers. This allows to extract wider classes of features than point singularities resolved by the wavelet transform. Our generalized feature extractor is proven to be translation-invariant, and we develop deformation stability results for a larger class of deformations than those considered by Mallat. For Mallat's wavelet-based feature extractor, we get rid of a number of technical conditions. The mathematical engine behind our results is continuous frame theory, which allows us to completely detach the invariance and deformation stability proofs from the particular algebraic structure of the underlying frames.

The problem of clustering noisy and incompletely observed high-dimensional data points into a union of low-dimensional subspaces and a set of outliers is considered. The number of subspaces, their dimensions, and their orientations are assumed unknown. We propose a simple low-complexity subspace clustering algorithm, which applies spectral clustering to an adjacency matrix obtained by thresholding the correlations between data points. In other words, the adjacency matrix is constructed from the nearest neighbors of each data point in spherical distance. A statistical performance analysis shows that the algorithm exhibits robustness to additive noise and succeeds even when the subspaces intersect. Specifically, our results reveal an explicit tradeoff between the affinity of the subspaces and the tolerable noise level. We furthermore prove that the algorithm succeeds even when the data points are incompletely observed with the number of missing entries allowed to be (up to a log-factor) linear in the ambient dimension. We also propose a simple scheme that provably detects outliers, and we present numerical results on real and synthetic data.

While spike trains are obviously not band-limited, the theory of super-resolution tells us that perfect recovery of unknown spike locations and weights from low-pass Fourier transform measurements is possible provided that the minimum spacing, Δ, between spikes is not too small. Specifically, for a cutoff frequency of fc, the work of Donoho (1992) shows that exact recovery is possible if Δ > l/fc, but does not specify a corresponding recovery method. On the other hand, Candès and Fernandez-Granda (2013) provide a recovery method based on convex optimization, which provably succeeds as long as Δ > 2/fc. In practical applications one often has access to windowed Fourier transform measurements, i.e., short-time Fourier transform (STFT) measurements, only. In this paper, we develop a theory of super-resolution from STFT measurements, and we propose a method that provably succeeds in recovering spike trains from STFT measurements provided that Δ > l/fc.

Subspace clustering refers to the problem of clustering high-dimensional data points into a union of low-dimensional linear subspaces, where the number of subspaces, their dimensions and orientations are all unknown. In this paper, we propose a variation of the recently introduced thresholding-based subspace clustering (TSC) algorithm, which applies spectral clustering to an adjacency matrix constructed from the nearest neighbors of each data point with respect to the spherical distance measure. The new element resides in an individual and data-driven choice of the number of nearest neighbors. Previous performance results for TSC, as well as for other subspace clustering algorithms based on spectral clustering, come in terms of an intermediate performance measure, which does not address the clustering error directly. Our main analytical contribution is a performance analysis of the modified TSC algorithm (as well as the original TSC algorithm) in terms of the clustering error directly.

We propose a method for inferring the conditional independence graph (CIG) of a high-dimensional discrete-time Gaussian vector random process from finite-length observations. Our approach does not rely on a parametric model (such as, e.g., an autoregressive model) for the vector random process; rather, it only assumes certain spectral smoothness properties. The proposed inference scheme is compressive in that it works for sample sizes that are (much) smaller than the number of scalar process components. We provide analytical conditions for our method to correctly identify the CIG with high probability.

Subspace clustering refers to the problem of clustering unlabeled high-dimensional data points into a union of low-dimensional linear subspaces, assumed unknown. In practice one may have access to dimensionality-reduced observations of the data only, resulting, e.g., from “undersampling” due to complexity and speed constraints on the acquisition device. More pertinently, even if one has access to the high-dimensional data set it is often desirable to first project the data points into a lower-dimensional space and to perform the clustering task there; this reduces storage requirements and computational cost. The purpose of this paper is to quantify the impact of dimensionality-reduction through random projection on the performance of the sparse subspace clustering (SSC) and the thresholding based subspace clustering (TSC) algorithms. We find that for both algorithms dimensionality reduction down to the order of the subspace dimensions is possible without incurring significant performance degradation. The mathematical engine behind our theorems is a result quantifying how the affinities between subspaces change under random dimensionality reducing projections.

It is well known that in K-user constant single-antenna interference channels K/2 degrees of freedom (DoF) can be achieved for almost all channel matrices. Explicit conditions on the channel matrix to admit K/2 DoF are, however, not available. The purpose of this paper is to identify such explicit conditions, which are satisfied for almost all channel matrices. We also provide a construction of corresponding asymptotically DoF-optimal input distributions. The main technical tool used is a recent breakthrough result by Hochman in fractal geometry [1].

We consider the problem of clustering a set of high-dimensional data points into sets of low-dimensional linear subspaces. The number of subspaces, their dimensions, and their orientations are unknown. We propose a simple and low-complexity clustering algorithm based on thresholding the correlations between the data points followed by spectral clustering. A probabilistic performance analysis shows that this algorithm succeeds even when the subspaces intersect, and when the dimensions of the subspaces scale (up to a log-factor) linearly in the ambient dimension. Moreover, we prove that the algorithm also succeeds for data points that are subject to erasures with the number of erasures scaling (up to a log-factor) linearly in the ambient dimension. Finally, we propose a simple scheme that provably detects outliers.

We consider the problem of clustering noisy high-dimensional data points into a union of low-dimensional subspaces and a set of outliers. The number of subspaces, their dimensions, and their orientations are unknown. A probabilistic performance analysis of the thresholding-based subspace clustering (TSC) algorithm introduced recently in [1] shows that TSC succeeds in the noisy case, even when the subspaces intersect. Our results reveal an explicit tradeoff between the allowed noise level and the affinity of the subspaces. We furthermore find that the simple outlier detection scheme introduced in [1] provably succeeds in the noisy case.

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 consider the problem of identifying a linear deterministic operator from its response to a given probing signal. For a large class of linear operators, we show that stable identifiability is possible if the total support area of the operator's spreading function satisfies$ \Delta \leq 1/ 2$. This result holds for an arbitrary (possibly fragmented) support region of the spreading function, does not impose limitations on the total extent of the support region, and, most importantly, does not require the support region to be known prior to identification. Furthermore, we prove that stable identifiability of almost all operators is possible if$ \Delta < 1$. This result is surprising as it says that there is no penalty for not knowing the support region of the spreading function prior to identification. Algorithms that provably recover all operators with$ \Delta \leq 1/ 2$, and almost all operators with$ \Delta < 1$are presented.

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 formulate a unified framework for the separation of signals that are sparse in “morphologically” different redundant dictionaries. This formulation incorporates the so-called “analysis” and “synthesis” approaches as special cases and contains novel hybrid setups. We find corresponding coherence-based recovery guarantees for an ℓ1-norm based separation algorithm. Our results recover those reported in Studer and Baraniuk, ACHA, submitted, for the synthesis setting, provide new recovery guarantees for the analysis setting, and form a basis for comparing performance in the analysis and synthesis settings. As an aside our findings complement the D-RIP recovery results reported in Candès et al., ACHA, 2011, for the “analysis” signal recovery problem minimizex||Ψx̃||1subject to ||y - Ax̃||2≤ ϵ by delivering corresponding coherence-based recovery results.

This paper reports an effort to consolidate numerous coherence-based sparse signal recovery results available in the literature. We present a single theory that applies to general Hilbert spaces with the sparsity of a signal defined as the number of (possibly infinite-dimensional) subspaces participating in the signal's representation. Our general results recover uncertainty relations and coherence-based recovery thresholds for sparse signals, block-sparse signals, multi-band signals, signals in shift-invariant spaces, and signals in finite unions of (possibly infinite-dimensional) subspaces. Moreover, we improve upon and generalize several of the existing results and, in many cases, we find shortened and simplified proofs.

We analyze the two-user single-antenna fading interference channel with perfect receive channel state information (CSI) and no transmit CSI. The diversity-multiplexing tradeoff (DMT) region of a fixed-power-split Han and Kobayashi (HK)-type superposition coding scheme is considered and design criteria for the corresponding superposition codes are derived. We demonstrate that this scheme is DMT optimal under strong and very strong interference by showing that it achieves a DMT region outer bound that we derive. !n addition, we show that, under very strong interference, decoding interference while treating the intended signal as noise, subtracting the result out, and then decoding the desired signal, a process known as “stripping”, achieves the optimal DMT region. Our proofs reveal code design criteria for achieving DMT optimality (in the cases where we can demonstrate it).

The noncoherent capacity of stationary discrete-time fading channels is known to be very sensitive to the fine details of the channel model. More specifically, the measure of the support of the fading-process power spectral density (PSD) determines if noncoherent capacity grows logarithmically with the signal-to-noise ratio (SNR) or slower than logarithmically. Such a result is unsatisfactory from an engineering point of view, as the support of the PSD cannot be determined through measurements. The aim of this paper is to assess whether, for general continuous-time Rayleigh-fading channels, this sensitivity has a noticeable impact on capacity at SNR values of practical interest. To this end, we consider the general class of band-limited continuous-time Rayleigh-fading channels that satisfy the wide-sense stationary uncorrelated-scattering (WSSUS) assumption and are, in addition, under spread. We show that, for all SNR values of practical interest, the noncoherent capacity of every channel in this class is close to the capacity of an additive white Gaussian noise channel with the same SNR and bandwidth, independently of the measure of the support of the scattering function (the 2-D channel PSD). Our result is based on a lower bound on noncoherent capacity, which is built on a discretization of the channel input-output relation induced by projecting onto Weyl-Heisenberg sets. This approach is interesting in its own right as it yields a mathematically tractable way of dealing with the mutual information between certain continuous-time random signals.

We present an uncertainty relation for the representation of signals in two different general (possibly redundant or incomplete) signal sets. This uncertainty relation is relevant for the analysis of signals containing two distinct features each of which can be described sparsely in a suitable general signal set. Furthermore, the new uncertainty relation is shown to lead to im- proved sparsity thresholds for recovery of signals that are sparse in general dictionaries. Specifically, our results improve on the well-known (1 + 1/d)/2-threshold for dictionaries with coherence d by up to a factor of two. Furthermore, we provide probabilistic recovery guarantees for pairs of general dictionaries that also allow us to understand which parts of a general dictionary one needs to randomize over to "weed out" the sparsity patterns that prohibit breaking the square-root bottleneck.

We investigate the recovery of signals exhibiting a sparse representation in a general (i.e., possibly redundant or incomplete) dictionary that are corrupted by additive noise admitting a sparse representation in another general dictionary. This setup covers a wide range of applications, such as image inpainting, super-resolution, signal separation, and recovery of signals that are impaired by, e.g., clipping, impulse noise, or narrowband interference. We present deterministic recovery guarantees based on a novel uncertainty relation for pairs of general dictionaries and we provide corresponding practicable recovery algorithms. The recovery guarantees we find depend on the signal and noise sparsity levels, on the coherence parameters of the involved dictionaries, and on the amount of prior knowledge about the signal and noise support sets.

We consider the problem of identifying a linear deterministic operator from an input-output measurement. For the large class of continuous (and hence bounded) operators, under additional mild restrictions, we show that stable identifiability is possible if the total support area of the operator's spreading function satisfies Δ ≤ 1/2. This result holds for arbitrary (possibly fragmented) support regions of the spreading function, does not impose limitations on the total extent of the support region, and, most importantly, does not require the support region of the spreading function to be known prior to identification. Furthermore, we prove that asking for identifiability of only almost all operators, stable identifiability is possible if Δ ≤ 1. This result is surprising as it says that there is no penalty for not knowing the support region of the spreading function prior to identification.

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.

We investigate the recovery of signals exhibiting a sparse representation in a general (i.e., possibly redundant or incomplete) dictionary that are corrupted by additive noise admitting a sparse representation in another general dictionary. This setup covers a wide range of applications, such as image inpainting, super-resolution, signal separation, and the recovery of signals that are corrupted by, e.g., clipping, impulse noise, or narrowband interference. We present deterministic recovery guarantees based on a recently developed uncertainty relation and provide corresponding recovery algorithms. The recovery guarantees we find depend on the signal and noise sparsity levels, on the coherence parameters of the involved dictionaries, and on the amount of prior knowledge on the support sets of signal and noise.

The large majority of commercially available multiple-input multiple-output (MIMO) radio channel measurement devices (sounders) is based on time-division multiplexed switching (TDMS) of a single transmit/receive radio frequency chain into the elements of a transmit/receive antenna array. While being cost-effective, such a solution can cause significant measurement errors due to phase noise and frequency offset in the local oscillators. In this paper, we systematically analyze the resulting errors and show that, in practice, overestimation of channel capacity by several hundred percent can occur. Overestimation is caused by phase noise (and to a lesser extent frequency offset) leading to an increase of the MIMO channel rank. Our analysis furthermore reveals that the impact of phase errors is, in general, most pronounced if the physical channel has low rank (typical for line-of-sight or poor scattering scenarios). The extreme case of a rank-1 physical channel is analyzed in detail. Finally, we present measurement results obtained from a commercially employed TDMS-based MIMO channel sounder. In the light of the findings of this paper, the results obtained through MIMO channel measurement campaigns using TDMS-based channel sounders should be interpreted with great care.

We analyze the (computational) complexity distribution of sphere decoding (SD) for random infinite lattices. In particular, we show that under fairly general assumptions on the statistics of the lattice basis matrix, the tail behavior of the SD complexity distribution is fully determined by the inverse volume of the fundamental regions of the underlying lattice. Particularizing this result to${N} \times {M},$${N} \geq {M}$, i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we find that the corresponding complexity distribution is of Pareto-type with tail exponent given by${N}-{M}+1$. A more refined analysis reveals that the corresponding average complexity of SD is infinite for${N} = {M}$and finite for${N} > {M}$. Finally, for i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we analyze SD preprocessing techniques based on lattice-reduction (such as the LLL algorithm or layer-sorting according to the V-BLAST algorithm) and regularization. In particular, we show that lattice-reduction does not improve the tail exponent of the complexity distribution while regularization results in a SD complexity distribution with tails that decrease faster than polynomial.

As shown by Tropp, 2008, for the concatenation of two orthonormal bases (ONBs), breaking the square-root bottleneck in compressed sensing does not require randomization over all the positions of the nonzero entries of the sparse coefficient vector. Rather the positions corresponding to one of the two ONBs can be chosen arbitrarily. The two-ONB structure is, however, restrictive and does not reveal the property that is responsible for allowing to break the bottleneck with reduced randomness. For general dictionaries we show that if a sub-dictionary with small enough coherence and large enough cardinality can be isolated, the bottleneck can be broken under the same probabilistic model on the sparse coefficient vector as in the two-ONB case.

We establish a lower bound on the noncoherent capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel. Surprisingly, when the covariance matrix of the channel satisfies a certain technical condition related to the cardinality of its smallest set of linearly dependent rows, this lower bound reveals that the capacity pre-log in the SIMO case is larger than that in the single-input single-output (SISO) case.

We consider Laurent polynomial (LP) matrices defined on the unit circle of the complex plane. QR decomposition of an LP matrix A(s) yields QR factors Q(s) and R(s) that, in general, are neither LP nor rational matrices. In this paper, we present an invertible mapping that transforms Q(s) and R(s) into LP matrices. Furthermore, we show that, given QR factors of sufficiently many samples of A(s), it is possible to obtain QR factors of additional samples ofA(s) through application of this mapping followed by interpolation and inversion of the mapping. The results of this paper find applications in the context of signal processing for multiple-input multiple-output (MIMO) wireless communication systems that employ orthogonal frequency-division multiplexing (OFDM).

We derive bounds on the noncoherent capacity of wide-sense stationary uncorrelated scattering (WSSUS) channels that are selective both in time and frequency, and are underspread, i.e., the product of the channel's delay spread and Doppler spread is small. The underspread assumption is satisfied by virtually all wireless communication channels. For input signals that are peak constrained in time and frequency, we obtain upper and lower bounds on capacity that are explicit in the channel's scattering function, are accurate for a large range of bandwidth, and allow to coarsely identify the capacity-optimal bandwidth as a function of the peak power and the channel's scattering function. We also obtain a closed-form expression for the first-order Taylor series expansion of capacity in the infinite-bandwidth limit, and show that our bounds are tight in the wideband regime. For input signals that are peak constrained in time only (and, hence, allowed to be peaky in frequency), we provide upper and lower bounds on the infinite-bandwidth capacity. Our lower bound is closely related to a result by Viterbi (1967). We find cases where the bounds coincide and, hence, the infinite-bandwidth capacity is characterized exactly. The analysis in this paper is based on a discrete-time discrete-frequency approximation of WSSUS time- and frequency-selective channels. This discretization takes the underspread property of the channel explicitly into account.

Promising approaches for efficient detection in multiple-input multiple-output (MIMO) wireless systems are based on sphere-decoding (SD). The conventional (and optimum) norm that is used to conduct the tree traversal step in SD is thel2-norm. It was, however, recently observed that using thel¿-norm instead reduces the hardware complexity of SD considerably at only a marginal performance loss. These savings result from a reduction in the length of the critical path in the circuit and the silicon area required for metric computation, but are also, as observed previously through simulation results, a consequence of a reduction in the computational (i.e., algorithmic) complexity. The aim of this paper is an analytical performance and computational complexity analysis ofl¿-norm SD. For independent and identically distributed (i.i.d.) Rayleigh fading MIMO channels, we show thatl¿-norm SD achieves full diversity order with an asymptotic SNR gap, compared tol2-norm SD, that increases at most linearly in the number of receive antennas. Moreover, we provide a closed-form expression for the computational complexity ofl¿-norm SD based on which we establish that its complexity scales exponentially in the system size. Finally, we characterize the tree pruning behavior ofl¿-norm SD and show that it behaves fundamentally different from that ofl2-norm SD.

Soft-input soft-output (SISO) detection algorithms form the basis for iterative decoding. The computational complexity of SISO detection often poses significant challenges for practical receiver implementations, in particular in the context of multiple-input multiple-output (MIMO) wireless communication systems. In this paper, we present a low-complexity SISO sphere-decoding algorithm, based on the single tree-search paradigm proposed originally for soft-output MIMO detection in Studer (“Soft-output sphere decoding: Algorithms and VLSI implementation,” IEEE J. Sel. Areas Commun., vol. 26, no. 2, pp. 290-300, Feb. 2008). The new algorithm incorporates clipping of the extrinsic log-likelihood ratios (LLRs) into the tree-search, which results in significant complexity savings and allows to cover a large performance/complexity tradeoff region by adjusting a single parameter. Furthermore, we propose a new method for correcting approximate LLRs - resulting from sub-optimal detectors - which (often significantly) improves detection performance at low additional computational complexity.

We consider compressed sensing of block-sparse signals, i.e., sparse signals that have nonzero coefficients occurring in clusters. Based on an uncertainty relation for block-sparse signals, we define a block-coherence measure and show that a block-version of the orthogonal matching pursuit algorithm recovers block k-sparse signals in no more than k steps if the block-coherence is sufficiently small. The same condition on block-sparsity is shown to guarantee successful recovery through a mixed lscr2/lscr1optimization approach. The significance of the results lies in the fact that making explicit use of block-sparsity can yield better reconstruction properties than treating the signal as being sparse in the conventional sense, thereby ignoring the additional structure in the problem.

We analyze two-user single-antenna fading interference channels with perfect receive channel state information (CSI) and no transmit CSI. For the case of very strong interference, we prove that decoding interference while treating the intended signal as noise, subtracting the result out, and then decoding the desired signal, a process known as ldquostrippingrdquo, achieves the diversity-multiplexing tradeoff (DMT) outer bound derived in Akuiyibo and Leveque, Int. Zurich Seminar on Commun., 2008. The proof is constructive in the sense that it provides corresponding code design criteria for DMT optimality. For general interference levels, we compute the DMT of a fixed-power-split Han and Kobayashi type superposition coding scheme, provide design criteria for the corresponding superposition codes, and find that this scheme is DMT-optimal for certain multiplexing rates.

We consider single-antenna interference networks where M sources, each with an average transmit power of P/M, communicate with M destinations over frequency-selective channels (with L taps each) and each destination has perfect knowledge of its channels from each of the sources. Assuming that there exist error-free non-interfering broadcast feedback links from each destination to all the nodes (i.e., sources and destinations) in the network, we show that naive interference alignment, in conjunction with vector quantization of the impulse response coefficients according to the scheme proposed in Mukkavilli et al., IEEE Trans. IT, 2003, achieves full spatial multiplexing gain of M/2, provided that the number of feedback bits broadcast by each destination is at least M(L-1) log P.

The noncoherent capacity of stationary discrete-time fading channels is known to be very sensitive to the fine details of the channel model. More specifically, the measure of the set of harmonics where the power spectral density of the fading process is nonzero determines if capacity grows logarithmically in SNR or slower than logarithmically. An engineering-relevant problem is to characterize the SNR value at which this sensitivity starts to matter. In this paper, we consider the general class of continuous-time Rayleigh-fading channels that satisfy the wide-sense stationary uncorrelated-scattering (WSSUS) assumption and are, in addition, underspread. For this class of channels, we show that the noncoherent capacity is close to the AWGN capacity for all SNR values of practical interest, independently of whether the scattering function is compactly supported or not. As a byproduct of our analysis, we obtain an information-theoretic pulse-design criterion for orthogonal frequency-division multiplexing systems.

We analyze the (computational) complexity distribution of sphere-decoding (SD) for random infinite lattices. In particular, we show that under fairly general assumptions on the statistics of the lattice basis matrix, the tail behavior of the SD complexity distribution is solely determined by the inverse volume of a fundamental region of the underlying lattice. Particularizing this result to N × M, N ¿ M, i.i.d. Gaussian lattice basis matrices, we find that the corresponding complexity distribution is of Pareto-type with tail exponent given by N - M + 1. We furthermore show that this tail exponent is not improved by lattice-reduction, which includes layer-sorting as a special case.

Bounds are derived on the noncoherent capacity of a very general class of multiple-input multiple-output fading channels that are selective in time and frequency as well as correlated in space. The bounds apply to peak-constrained inputs; they are explicit in the channel's scattering function, are useful for a large range of bandwidth, and allow one to coarsely identify the capacity-optimal combination of bandwidth and number of transmit antennas. Furthermore, a closed-form expression is obtained for the first-order Taylor series expansion of capacity in the limit of infinite bandwidth. From this expression, it is concluded that in the wideband regime: (i) it is optimal to use only one transmit antenna when the channel is spatially uncorrelated; (ii) rank-one statistical beamforming is optimal if the channel is spatially correlated; and (iii) spatial correlation, be it at the transmitter, the receiver, or both, is beneficial.

We establish the optimal diversity-multiplexing (DM) tradeoff of coherent selective-fading multiple-access multiple-input multiple-output (MIMO) channels and provide corresponding code design criteria. As a byproduct, on the conceptual level, we find an interesting relation between the DM tradeoff framework and the notion of dominant error event regions which was first introduced in the AWGN case by Gallager, IEEE Trans. IT, 1985. This relation allows to accurately characterize the error mechanisms in MIMO fading multiple-access channels. In particular, we find that, for a given rate tuple, the maximum achievable diversity order is determined by the error event that dominates the total error probability exponentially in SNR. Finally, we show that the distributed space-time code construction proposed recently by Badr and Belfiore, Int. Zurich Seminar on Commun., 2008, satisfies the code design criteria derived in this paper.

This paper presents bounds on the noncoherent capacity of a very general multiple-input multiple-output channel, which allows for selectivity in time and frequency as well as for spatial correlation. The bounds apply to peak-constrained inputs; they are explicit in the channelpsilas scattering function, are useful for a large range of bandwidth, and allow one to coarsely identify the capacity-optimal combination of bandwidth and number of transmit antennas. Furthermore, a closed-form expression is obtained for the first-order Taylor series expansion of capacity in the limit of infinite bandwidth. From this expression, it is concluded that in the wideband regime: (i) it is optimal to use only one transmit antenna when the channel is spatially uncorrelated; (ii) rank-one statistical beamforming is optimal if the channel is spatially correlated; and (iii) spatial correlation, be it at the transmitter, the receiver, or both, is beneficial.

The most promising approaches for efficient detection in multiple-input multiple-output (MIMO) wireless systems are based on sphere-decoding (SD). The conventional (and optimum) norm that is used to conduct the tree traversal step in SD is the l2-norm. It was, however, recently shown that using the linfin-norm instead significantly reduces the VLSI implementation complexity of SD at only a marginal performance loss. These savings are due to a reduction in the length of the critical path and the silicon area of the circuit, but also, as observed previously through simulation results, a consequence of a reduction in the computational (algorithmic) complexity. The aim of this paper is an analytical performance and computational complexity analysis of linfin-norm SD. For i.i.d. Rayleigh fading MIMO channels, we show that linfin-norm SD achieves full diversity order with an asymptotic SNR gap, compared to l2-norm SD, that increases at most linearly in the number of receive antennas. Moreover, we provide a closed-form expression for the computational complexity of linfin-norm SD.

Soft-input soft-output (SISO) detection algorithms form the basis for iterative decoding. The associated computational complexity often poses significant challenges for practical receiver implementations, in particular in the context of multiple- input multiple-output wireless systems. In this paper, we present a low-complexity SISO sphere decoder which is based on the single tree search paradigm, proposed originally for soft-output detection in Studer et al., IEEE J-SAC, 2008. The algorithm incorporates clipping of the extrinsic log-likelihood ratios in the tree search, which not only results in significant complexity savings, but also allows to cover a large performance/complexity trade-off region by adjusting a single parameter.

Multiple-input multiple-output (MIMO) detection algorithms providing soft information for a subsequent channel decoder pose significant implementation challenges due to their high computational complexity. In this paper, we show how sphere decoding can be used as an efficient tool to implement soft-output MIMO detection with flexible trade-offs between computational complexity and (error rate) performance. In particular, we provide VLSI implementation results which demonstrate that single tree-search, sorted QR-decomposition, channel matrix regularization, log-likelihood ratio clipping, and imposing runtime constraints are the key ingredients for realizing soft-output MIMO detectors with near max-log performance at a chip area that is only 58% higher than that of the best-known hard-output sphere decoder VLSI implementation.

We establish the optimal diversity-multiplexing (DM) tradeoff of coherent time, frequency and time-frequency selective-fading MIMO channels and provide a code design criterion for DM-tradeoff optimality. Our results are based on the analysis of the "Jensen channel" associated to a given selective-fading MIMO channel. While the original problem seems analytically intractable due to the mutual information being a sum of correlated random variables, the Jensen channel is equivalent to the original channel in the sense of the DM-tradeoff and lends itself nicely to analytical treatment. Finally, as a consequence of our results, we find that the classical rank criterion for space-time code design (in selective-fading MIMO channels) ensures optimality in the sense of the DM-tradeoff.

We characterize the capacity of the general class of noncoherent underspread wide-sense stationary uncorrelated scattering (WSSUS) time-frequency-selective Rayleigh fading channels, under peak constraints in time and frequency and in time only. Capacity upper and lower bounds are found which are explicit in the channel's scattering function and allow to identify the capacity-maximizing bandwidth for a given scattering function and a given peak-to-average power ratio.

We analyze the outage characteristics of correlated Ricean fading, coherent multiple-input multiple-output (MIMO) channels. In particular, we establish the notion of a "critical rate", below which communication at zero outage is possible and above which the channel appears as Ricean fading. The critical rate is shown to depend on the "angle" between the subspace spanned by the Ricean component of the channel matrix and the subspace spanned by the correlation matrix of the Rayleigh fading component. A nonzero critical rate is possible only if the correlation matrix of the Rayleigh fading component is rank- deficient. Finally, we provide a complete characterization of the optimum diversity-multiplexing tradeoff for correlated Ricean fading MIMO channels taking into account the existence of the critical rate and thereby establishing the notion of a critical multiplexing gain.

We analyze fading relay networks, where a single-antenna source-destination terminal pair communicates through a set of half-duplex single-antenna relays using a two-hop protocol with linear processing at the relay level. A family of relaying schemes is presented which achieves the entire optimal diversity-multiplexing (DM) tradeoff curve. As a byproduct of our analysis, it follows that delay diversity and phase-rolling at the relay level are optimal with respect to the entire DM-tradeoff curve, provided the delays and the modulation frequencies, respectively, are chosen appropriately.

We analyze fading interference relay networks where$M$single-antenna source–destination terminal pairs communicate concurrently and in the same frequency band through a set of$K$single-antenna relays using half-duplex two-hop relaying. Assuming that the relays have channel state information (CSI), it is shown that in the large-$M$limit, provided$K$grows fast enough as a function of$M$, the network “decouples” in the sense that the individual source–destination terminal pair capacities are strictly positive. The corresponding required rate of growth of$K$as a function of$M$is found to be sufficient to also make the individual source–destination fading links converge to nonfading links. We say that the network“crystallizes”as it breaks up into a set of effectively isolated“wires in the air.”A large-deviations analysis is performed to characterize the “crystallization” rate, i.e., the rate (as a function of$M$,$K$) at which the decoupled links converge to nonfading links. In the course of this analysis, we develop a new technique for characterizing the large-deviations behavior of certain sums of dependent random variables. For the case of no CS

We present results of two indoor ultrawideband channel measurement campaigns in the 2-5 GHz frequency band. In measurement campaign I (MC I), the channel is static and we sample it spatially, while in MCII the transmitting and receiving antennas are fixed and channel variation is induced by people moving in the environment. Transmitter and receiver are separated by up to 27 m in MC I and up to 20 m in MC II. To determine suitable small-scale fading distributions for the tap amplitudes of the discrete-time baseband-equivalent channel impulse response, we use Akaike's information criterion (AIC). Despite the large bandwidth, AIC supports the Rayleigh (MCI) or the Rice distribution (MC II). For data from MC II, we estimate the covariance matrix of the random channel impulse response and demonstrate that the number of corresponding significant eigenvalues, and hence the diversity order of the channel, scales approximately linearly with bandwidth. Contrary to the uncorrected scattering assumption, we find that the channel taps are weakly correlated. The ergodic capacity predicted by the Ricean channel model with parameters estimated from MC II shows good agreement with the ergodic capacity obtained by direct evaluation of the measurement results, while the corresponding outage capacities show a worse fit for low outage probabilities because of shadowing.

We describe the VLSI implementation of MIMO detectors that exhibit close-to optimum error-rate performance, but still achieve high throughput at low silicon area. In particular, algorithms and VLSI architectures for sphere decoding (SD) and K-best detection are considered, and the corresponding trade-offs between uncoded error-rate performance, silicon area, and throughput are explored. We show that SD with a per-block run-time constraint is best suited for practical implementations.

We characterize the infinite bandwidth capacity behavior of the general class of underspread wide-sense stationary uncorrelated scattering (WSSUS) time-frequency selective Rayleigh fading channels. In particular, we propose a signaling scheme, termed time-frequency pulse position modulation (TF-PPM), which is shown to achieve AWGN channel capacity in the infinite bandwidth limit. As a trivial consequence of this result, the infinite bandwidth capacity of WSSUS underspread fading channels, irrespectively of the scattering function, equals the AWGN channel's infinite bandwidth capacity. The wideband slope achieved by TF-PPM is found to be zero, irrespectively of the channel's scattering function, even in the presence of perfect receive channel state information. Our proof techniques use the fact that underspread fading channels have a highly structured set of eigenfunctions and a property of orthogonal signaling schemes first presented in Butman and Klass, Jet Propulsion Lab., Tech. Rep., 1973.

A significant body of results on space-time and space-frequency coding for single-user channels is available in the literature. In contrast, space-time/frequency coding for multiple-access channels (MACs) seems largely unexplored. Building on the framework in Gallager, IEEE Trans. IT, 1985 for characterizing the dominant error event regions in single-antenna additive white Gaussian noise (AWGN) MACs, we derive rate-dependent space-time/frequency code design criteria for fading multiantenna MACs with perfect channel state information at the receiver. It is demonstrated that, depending on the transmission rate tuple, joint designs taking the presence of multiple users explicitly into account may be necessary. Our results furthermore allow to identify the rate regions where, for each user, employing codes designed for the single-user case is optimal. Finally, we show that the number of receive antennas has a significant impact on the dominant error event regions and hence, plays an important role in the code design criteria. As a byproduct of our analysis, we find that the classical code design criteria (based on pairwise error probabilities) are recovered using a completely different approach aimed at minimizing the probability of encountering a bad effective channel realization

In this paper, we consider frequency-selective coherent multiple-input multiple-output (MIMO) multiple-access fading channels. Assuming that each of the users employs orthogonal frequency-division multiplexing (OFDM), we introduce a multiple-access scheme that gradually varies the amount of user collision in signal space by assigning different subsets of the available OFDM tones to different users. The corresponding multiple-access schemes range from frequency-division multiple access (FDMA) (each OFDM tone is assigned to at most one user) to CDMA (each OFDM tone is assigned to all the users). We quantify the effect of signal space collision between the users by computing the ergodic capacity region for the entire family of multiple-access schemes. It is shown that the ergodic capacity region obtained by a fully collision-based scheme (CDMA) is an outer bound to that corresponding to any other multiple-access strategy. In practice, however, minimizing the amount of user collision in frequency is desirable as this minimizes the receiver complexity incurred by having to separate the interfering (colliding) signals. Our analysis shows that the impact of collision on spectral efficiency depends critically on the channel's spatial fading statistics and the number of antennas

The use of multiple antennas at both ends of a wireless link, popularly known as multiple-input multiple-output (MIMO) wireless, has been shown to offer significant improvements in spectral efficiency and link reliability through spatial multiplexing and space-time coding, respectively. This paper demonstrates that similar performance gains can be obtained in wireless relay networks employing terminals with MIMO capability. We consider a setup where a designated source terminal communicates with a designated destination terminal, both equipped with M antennas, assisted by K single-antenna or multiple-antenna relay terminals using a half-duplex protocol. Assuming perfect channel state information (CSI) at the destination and the relay terminals and no CSI at the source, we show that the corresponding network capacity scales as C = (M/2) log(K) + O(1) for fixed M, arbitrary (but fixed) number of (transmit and receive) antennas N at each of the relay terminals, and K rarr infin. We propose a protocol that assigns each relay terminal to one of the multiplexed data streams forwarded in a "doubly coherent" fashion (through matched filtering) to the destination terminal. It is shown that this protocol achieves the cut-set upper bound on network capacity for fixed M and K rarr infin (up to an O(1)-term) by employing independent stream decoding at the destination terminal. Our protocol performs inter-stream interference cancellation in a completely decentralized fashion, thereby orthogonalizing the effective MIMO channel between source and destination terminals. Finally, we discuss the case where the relay terminals do not have CSI and show that simple amplify-and-forward relaying, asymptotically in K, for fixed M and fixed N ges 1, turns the relay network into a point-to-point MIMO link with high-SNR capacity C = (M/2) log(SNR) + O(1), demonstrating that the use of relays as active scatterers can recover spatial multiplexing gain in poor scattering environments

We study the capacity behavior of full-band MIMO-OFDM systems in the absence of channel state information both at the transmitter and the receiver. Based on capacity lower and upper bounds, we quantify the transmission rate penalty due to channel uncertainty as a function of the number of transmit antennas, the number of resolvable taps in the channel, the power delay profile, and the bandwidth. Our analysis reveals that for a given bandwidth and transmit power there is an optimum, capacity-maximizing, number of transmit antennas. Numerical results show that using a large number of transmit antennas in systems employing bandwidths of several GHz (such as in ultrawideband systems) is detrimental from a capacity point of view. Finally, we evaluate the capacity performance of space-frequency unitary codebooks recently introduced in M. Borgmann and H. Bolcskei, (2005)

We study fading interference relay networks where M single-antenna source-destination terminal pairs communicate through a set of K relays using half-duplex two-hop relaying. Two specific protocols are considered, P1 introduced in H. Bolcskei, et al. (2004), H. Bolcskei and R.U. Nabar (2004) and P2 introduced in A.F. Dana and B. Hassibi (2003). P1 relies on the idea of relay partitioning and requires each relay terminal to know one backward and one forward fading coefficient only. P2 requires each relay terminal to know all M backward and M forward fading coefficients and does not need relay partitioning. We prove that in the large-M limit the minimum rate of growth of K for P1 to achieve a strictly positive per source-destination terminal pair capacity is K infin M3whereas in P2 it is K infin M2. The protocols P1 and P2 are thus found to trade off the number of relay terminals for channel state information (CSI) at the relays; more CSI at the relays reduces the total number of relays needed to achieve a strictly positive per source-destination terminal pair capacity in the large-M limit

We present results of two ultra-wideband (UWB) channel measurement campaigns in the 2-5 GHz frequency band, and use Akaike's Information Criterion (AIC) to determine suitable distributions for the channel impulse response taps. Despite the large bandwidth, AIC supports the complex Gaussian tap distribution, with mean depending on the measurement setting. We estimate the empirical covariance matrix of the channel impulse response, and demonstrate that the number of corresponding significant eigenvalues scales approximately linearly with bandwidth, albeit we find that channel taps are correlated

Recently, the use of coherent space-frequency coding in orthogonal frequency-division multiplexing (OFDM)-based frequency-selective multiple-input multiple-output (MIMO) fading channels has been proposed. Acquiring knowledge of the fading coefficients in a MIMO channel is already very challenging in the frequency-flat (fast) fading case. In the frequency-selective case, this task becomes significantly more difficult due to the presence of multiple paths, which results in an increased number of parameters to be estimated. In this paper, we address code design for noncoherent frequency-selective MIMO-OFDM fading links, where neither the transmitter nor the receiver knows the channel. We derive the code design criteria, quantify the maximum achievable diversity gain, and provide explicit constructions of full-diversity (space and frequency) achieving codes along with an analytical and numerical performance assessment. We also demonstrate that unlike in the coherent case, noncoherent space-frequency codes designed to achieve full spatial diversity in the frequency-flat fading case can fail completely to exploit not only frequency diversity but also spatial diversity when used in frequency-selective fading environments. We term such codes "catastrophic.".

In this paper, we examine the basic building block of cooperative diversity systems, a simple fading relay channel where the source, destination and relay terminals are each equipped with single antenna transceivers. We consider three different TDMA-based cooperative protocols that vary the degree of broadcasting and receive collision. For each protocol, the relay terminal simply amplifies-and-forwards the signal received from the source terminal to the destination. We study the ergodic and outage capacity behavior of each of the protocols assuming Gaussian codebooks and show that full spatial diversity (second-order in this case) is achieved by certain protocols provided that appropriate power control is employed. Finally, we establish the superiority (both from a capacity as well as a diversity point-of-view) of a new protocol proposed in this paper.

We consider frequency selective Multiple-Input Multiple-Output (MIMO) multiple access fading channels with perfect channel knowledge in the receiver and no channel state information in the transmitters. Assuming that each of the users employs Orthogonal Frequency Division Multiplexing (OFDM), we introduce a multiple access scheme which allows to gradually vary the amount of user collision in signal space by assigning different subsets of the available OFDM tones to different users. The corresponding multiple access schemes range from FDMA (each OFDM tone is assigned to at most one user) to CDMA (each OFDM tone is assigned to all the users). We quantify the effect of signal space collision between users by computing ergodic capacity regions for joint and single user decoding. In the case of joint decoding, we prove that irrespectively of the spatial receive fading correlation, the ergodic capacity region obtained by a fully collision-based scheme is an outer bound to any other OFDM-based multiple-access strategy, where the users collide only on subsets of the available tones. For single user decoding, we find that the amount of collision maximizing the capacity region depends critically on the number of transmit and receive antennas and the users' receive fading correlation.

This paper considers wireless networks where L single-antenna source-destination terminal pairs communicate concurrently through a common set of K single-antenna relay terminals using one-hop relaying. It is shown that asymptotically in K, the sum capacity of this network scales as C=(L/2) log (K)+O(1) and can be achieved without cooperation between any of the terminals.

This paper presents the geometrical technique investigation of the rank-1 Ricean MIMO channels at high SNR mutual information (MI) for Gaussian code books with no channel state information (CSI) at the transmitter and perfect CSI at the receiver. The analytical approximation for the probability density function (pdf), mean and variance of the MI that reveals the Gaussian nature of MI both in the Rayleigh and the rank-1 Ricean cases are also derived.

Assuming PSK modulation, we derive the system capacity of pulse-shaped orthogonal frequency division multiplexing (OFDM) communications over time-frequency selective fading channels in the absence of channel state information at the transmitter and the receiver. We show that capacity tends to zero in the large bandwidth limit and quantify the impact of spread and shape of the scattering function on finite bandwidth capacity

We quantify the impact of coherence on pulse position modulation (PPM) over wideband fading channels by computing achievable rates and an upper bound on uncoded symbol error probability. We study the influence of channel estimation accuracy on the optimum diversity order and furthermore find that a near-optimum receiver typically needs to estimate a few channel taps only

Cooperative diversity is a transmission technique, where multiple terminals pool their resources to form a virtual antenna array that realizes spatial diversity gain in a distributed fashion. In this paper, we examine the basic building block of cooperative diversity systems, a simple fading relay channel where the source, destination, and relay terminals are each equipped with single antenna transceivers. We consider three different time-division multiple-access-based cooperative protocols that vary the degree of broadcasting and receive collision. The relay terminal operates in either the amplify-and-forward (AF) or decode-and-forward (DF) modes. For each protocol, we study the ergodic and outage capacity behavior (assuming Gaussian code books) under the AF and DF modes of relaying. We analyze the spatial diversity performance of the various protocols and find that full spatial diversity (second-order in this case) is achieved by certain protocols provided that appropriate power control is employed. Our analysis unifies previous results reported in the literature and establishes the superiority (both from a capacity, as well as a diversity point-of-view) of a new protocol proposed in this paper. The second part of the paper is devoted to (distributed) space-time code design for fading relay channels operating in the AF mode. We show that the corresponding code design criteria consist of the traditional rank and determinant criteria for the case of colocated antennas, as well as appropriate power control rules. Consequently space-time codes designed for the case of colocated multiantenna channels can be used to realize cooperative diversity provided that appropriate power control is employed.

High data rate wireless communications, nearing 1 Gb/s transmission rates, is of interest in emerging wireless local area networks and home audio/visual networks. Designing very high speed wireless links that offer good quality-of-service and range capability in non-line-of-sight (NLOS) environments constitutes a significant research and engineering challenge. Ignoring fading in NLOS environments, we can, in principle, meet the 1 Gb/s data rate requirement with a single-transmit single-receive antenna wireless system if the product of bandwidth (measured in hertz) and spectral efficiency (measured in bits per second per hertz) is equal to 10/sup 9/. A variety of cost, technology and regulatory constraints make such a brute force solution unattractive, if not impossible. The use of multiple antennas at transmitter and receiver, popularly known as multiple-input multiple-output (MIMO) wireless, is an emerging cost-effective technology that offers substantial leverages in making 1 Gb/s wireless links a reality. The paper provides an overview of MIMO wireless technology covering channel models, performance limits, coding, and transceiver design.

Cooperative diversity is a transmission technique where multiple users pool their resources to form a virtual antenna array that realizes spatial diversity gain in a distributed fashion. We examine space-time signal design for a simple amplify-and-forward relay channel. We show that the code design criteria for the relay case consist of the traditional rank and determinant criteria as well as appropriate power control rules. While proper signal design and power control can indeed achieve full spatial diversity gain, the potential benefit of relay-assisted communication over direct communication depends strongly on the channel conditions. In particular, we present a switching criterion based on which the source terminal may opt to forego relay-assisted communication and communicate with the destination terminal directly. The criterion is based on the cut-off rate of the effective channel - the physical channel in conjunction with finite constellation and maximum-likelihood (ML) decoding.

The use of spatial multiplexing (SM) in multiple-input multiple-output (MIMO) wireless systems promises a linear (in the minimum of the number of transmit and receive antennas) increase in data rate. In practice, the performance of SM depends critically on a variety of channel conditions, including antenna height and spacing, polarization of antennas, and richness of scattering. Transmit correlation has been shown to be detrimental to the performance of SM, since it leads to the existence of preferred spatial directions. In addition, the presence of an ill-conditioned fixed (possibly line-of-sight) component in the channel can severely degrade performance. We present a simple transmit optimization strategy to mitigate partially the impact of unfavorable channel statistics on the performance of SM. The proposed strategy takes the scalar symbol constellation and the channel statistics into account and relies on simple phase-shifting of the multiplexed symbol streams at the transmitter. The phase shifts are chosen such that the cut-off rate of the effective channel (physical channel in combination with finite constellation and ML decoding) is maximized. We find SNR gains of up to 4 dB over the case when no transmit optimization is employed.

Space-frequency coded orthogonal frequency division multiplexing (OFDM) is capable of realizing both spatial and frequency-diversity gains in multipath multiple-input multiple-output (MIMO) fading channels. This naturally leads to the question of variable allocation of the channel's degrees of freedom to multiplexing and diversity transmission modes. In this paper, we provide a systematic method for the design of space-frequency codes with variable multiplexing-diversity tradeoffs. Simulation results illustrate the performance of the proposed codes.

Previous work on space-frequency coded multiple-input multiple-output orthogonal frequency-division multiplexing (MIMO-OFDM) has been restricted to idealistic propagation conditions. In this paper, using a broadband MIMO channel model taking into account Ricean K-factor, transmit and receive angle spread, and antenna spacing, we study the impact of the propagation environment on the performance of space-frequency coded MIMO-OFDM. For a given space-frequency code, we quantify the achievable diversity order and coding gain as a function of the propagation parameters. We find that while the presence of spatial receive correlation affects all space-frequency codes equally, spatial fading correlation at the transmit array can result in widely varying performance losses. High-rate space-frequency codes such as spatial multiplexing are typically significantly more affected by transmit correlation than low-rate codes such as space-frequency block codes. We show that in the MIMO Ricean case the presence of frequency-selectivity typically results in improved performance compared to the frequency-flat case.

We introduce a new class of finite-dimensional frames with strong symmetry properties, called geometrically uniform (GU) frames, that are defined over a finite Abelian group of unitary matrices and are generated by a single generating vector. The notion of GU frames is then extended to compound GU (CGU) frames which are generated by a finite Abelian group of unitary matrices using multiple generating vectors. The dual frame vectors and canonical tight frame vectors associated with GU frames are shown to be GU and, therefore, also generated by a single generating vector, which can be computed very efficiently using a Fourier transform (FT) defined over the generating group of the frame. Similarly, the dual frame vectors and canonical tight frame vectors associated with CGU frames are shown to be CGU. The impact of removing single or multiple elements from a GU frame is considered. A systematic method for constructing optimal GU frames from a given set of frame vectors that are not GU is also developed. Finally, the Euclidean distance properties of GU frames are discussed and conditions are derived on the Abelian group of unitary matrices to yield GU frames with strictly positive distance spectrum irrespective of the generating vector.

We consider Gaussian multiple-input multiple-output (MIMO) fading channels assuming that the channel is unknown at the transmitter and perfectly known at the receiver. Using results from multivariate statistics, we derive a tight closed-form lower-bound for the ergodic capacity of such channels at any signal-to-noise ratio (SNR). Moreover, we provide an accurate closed-form analytical approximation of ergodic capacity in the high SNR regime. Our analysis incorporates the frequency-selective Rayleigh fading case and/or spatial fading correlation, and allows Important Insights Into optimal (ergodic capacity maximizing) MIMO configurations. Finally, we verify our analytical expressions through comparison with numerical results.

The performance of space-time block codes is well understood from an average (over the random channel) error point of view. However, inherent to the idea of diversity gain is the issue of reliability, which is better captured through an outage analysis indicating the quality of performance guaranteed with a certain level of reliability. In this paper, we study the outage performance of a simple space-time block code, the Alamouti scheme, in the presence of correlated Rayleigh or Ricean fading. We derive expressions for the cumulative distribution function of the uncoded symbol error rate and verify the accuracy of our analytical expressions through comparison with numerical results. In addition, we introduce a quantitative measure to compare the diversity gain offered by two channels at a given outage rate.

This paper deals with the capacity behavior of wireless orthogonal frequency-division multiplexing (OFDM)-based spatial multiplexing systems in broad-band fading environments for the case where the channel is unknown at the transmitter and perfectly known at the receiver. Introducing a physically motivated multiple-input multiple-output (MIMO) broad-band fading channel model, we study the influence of physical parameters such as the amount of delay spread, cluster angle spread, and total angle spread, and system parameters such as the number of antennas and antenna spacing on ergodic capacity and outage capacity. We find that, in the MIMO case, unlike the single-input single-output (SISO) case, delay spread channels may provide advantages over flat fading channels not only in terms of outage capacity but also in terms of ergodic capacity. Therefore, MIMO delay spread channels will in general provide both higher diversity gain and higher multiplexing gain than MIMO flat fading channels

We present a new model for multiple-input-multiple-output (MIMO) outdoor wireless fading channels and their capacity performance. The proposed model is more general and realistic than the usual independent and identically distributed (i.i.d.) model, and allows us to investigate the behavior of channel capacity as a function of the scattering radii at transmitter and receiver, distance between the transmit and receive arrays, and antenna beamwidths and spacing. We show how the MIMO capacity is governed by spatial fading correlation and the condition number of the channel matrix through specific sets of propagation parameters. The proposed model explains the existence of "pinhole" channels which exhibit low spatial fading correlation at both ends of the link but still have poor rank properties, and hence, low ergodic capacity. In fact, the model suggests the existence of a more general family of channels spanning continuously from full rank i.i.d. to low-rank pinhole cases. We suggest guidelines for predicting high rank (and hence, high ergodic capacity) in MIMO channels, and show that even at long ranges, high channel rank can easily be sustained under mild scattering conditions. Finally, we validate our results by simulations using ray tracing techniques. Connections with basic antenna theory are made.

Multiple-input multiple-output (MIMO) wireless systems employ spatial multiplexing to increase data rate. The performance of spatial multiplexing is highly dependent on channel statistics which in turn depend on antenna spacing and richness of scattering. It has been shown Bolcskei and Paulraj, (see Asilomar Conf. on Signals, Systems, and Computers, Pacific Grove, CA, Oct./Nov. 2000) that the presence of transmit correlation can have a detrimental effect on the performance of multi-antenna signaling techniques. We present a novel scheme to (partly) mitigate the performance loss of spatial multiplexing in the presence of highly correlated fading at the transmitter. The adaption to be performed at the transmitter is a form of power allocation and/or relative phase adjustment between the different symbol streams to be multiplexed. We consider the cases of dual-polarized as well as uni-polarized antennas and derive estimates of the uncoded average symbol error rate as a function of channel statistics, power allocation and phase adjustment. We then optimize power allocation and phase adjustment and demonstrate that this form of preprocessing can yield SNR gains of up to 4 dB over the case where no precoding is employed.

In practice large antenna spacings are needed to achieve high capacity gains in multiple-input multiple-output (MIMO) wireless systems. The use of dual-polarized antennas is a promising cost effective alternative where two spatially separated antennas can be replaced by a single antenna element employing orthogonal polarizations. This paper investigates the performance of spatial multiplexing in MIMO wireless systems with dual-polarized antennas. We compute estimates of the symbol error rate as a function of cross-polarization discrimination (XPD) and spatial fading correlations. Using these estimates, we show that dual-polarized antennas can significantly improve the performance of spatial multiplexing systems. It is demonstrated that improvements in terms of symbol error rate of up to an order of magnitude are possible. We furthermore find that in general for a given SNR there is an optimum XPD for which the symbol error rate is minimum. Finally, we present simulation results and we show that our estimates closely match the numerical results.

Wireless systems with multiple transmit and receive antennas (MIMO systems) provide high capacity due to the plurality of modes available in the channel. Previous code designs for MIMO systems have focused primarily on multiplexed signaling for high data rate or diversity signaling for high link reliability. Based on Ganesan and Stoica (2000) and Hassibi and Hochwald (2000), and using results from frame theory, we present a MIMO space-time code design which bridges the gap between multiplexing and diversity and performs well both in terms of ergodic capacity as well as error-probability. In particular, we demonstrate that designs performing well from an ergodic capacity point of view do not necessarily perform well from an error probability point of view. Simulations illustrate performance of the proposed codes in narrowband MIMO Rayleigh fading channels.

Orthogonal frequency-division multiplexing (OFDM) systems are highly sensitive to synchronization errors. We introduce an algorithm for the blind estimation of symbol timing and carrier frequency offset in wireless OFDM systems. The proposed estimator is an extension of the Gini-Giannakis (see IEEE Trans. Commun., vol.46, p.400-411, 1998) estimator for single-carrier systems. It exploits the cyclostationarity of OFDM signals and relies on second-order statistics only. Our method can be applied to pulse shaping OFDM systems with arbitrary time-frequency guard regions, OFDM based on offset quadrature amplitude modulation, and biorthogonal frequency-division multiplexing systems. We furthermore propose the use of different subcarrier transmit powers (subcarrier weighting) and periodic transmitter precoding to achieve a carrier frequency acquisition range of the entire bandwidth of the OFDM signal, and a symbol timing acquisition range of arbitrary length. Finally, we provide simulation results demonstrating the performance of the new estimator.

We introduce two methods for quantization noise reduction in oversampled filter banks. These methods are based on predictive quantization (noise shaping or linear prediction). It is demonstrated that oversampled noise shaping or linear predictive subband coders are well suited for subband coding applications where, for technological or other reasons, low-resolution quantizers have to be used. In this case, oversampling combined with noise shaping or linear prediction improves the effective resolution of the subband coder at the expense of increased rate. Simulation results are provided to assess the achievable quantization noise reduction and resolution enhancement, and to investigate the rate-distortion properties of the proposed methods.

We present a new model for multiple-input multiple-output (MIMO) outdoor wireless fading channels which is more general and realistic than the usual i.i.d. model. We investigate the channel capacity as a function of parameters such as the local scattering radius at the transmitter and the receiver, the distance between the transmit (TX) and receive (RX) arrays, and the antenna beamwidths and spacing. We point out the existence of "pin-hole" channels which exhibit low fading correlation between antennas but still have poor rank properties and hence low capacity. Finally we show that even at long ranges high channel rank can easily be obtained under mild scattering conditions.

We compute the capacity of wireless orthogonal frequency division multiplexing (OFDM)-based spatial multiplexing systems in delay spread environments. Introducing an abstract model to characterize the statistical properties of the space-time channel, we provide a Monte-Carlo method for estimating the capacity cumulative distribution function, expected capacity, and outage capacity for the case where the channel is unknown at the transmitter and perfectly known at the receiver. We study the influence of the propagation environment and system parameters on capacity, and we apply our method to spatial versions of standard channels taken from the GSM recommendations. This allows us to make statements about achievable data rates of OFDM-based spatial multiplexing systems operating in practical broadband propagation environments.

Space-time coding for fading channels is a communication technique that realizes the diversity benefits of multiple transmit antennas. Previous work in this area has focused on the narrowband flat fading case where spatial diversity only is available. We investigate the use of space-time coding in OFDM-based broadband systems where both spatial and frequency diversity are available. We consider a strategy which basically consists of coding across OFDM tones and is therefore called space-frequency coding. For a spatial broadband channel model taking into account physical propagation parameters and antenna spacing, we derive the design criteria for space-frequency codes and we show that space-time codes designed to achieve full spatial diversity in the narrowband case will in general not achieve full space-frequency diversity. Specifically, we show that the Alamouti (see IEEE J. Sel. Areas Comm., vol.16, p.1451-58, 1998) scheme across tones fails to exploit frequency diversity. For a given set of propagation parameters and given antenna spacing, we establish the maximum achievable diversity order. Finally, we provide simulation results studying the influence of delay spread, propagation parameters, and antenna spacing on the performance of space-frequency codes.

Recently, in the context of orthogonal frequency division multiplexing (OFDM), a new method (FAB-method) for constructing tight Gabor frames (with redundancy 2) from a (non-tight) Gaussian g was proposed by LeFloch et al. (see Proc. IEEE, vol.83, no.6, p.982-96, 1995). In this letter, we prove that the FAB-method yields the tight window function canonically associated to the Gaussian. We furthermore provide a necessary and sufficient condition on the initial window function g in the Zak transform domain for the FAB-method to yield a tight Gabor frame. This yields a characterization of all initial window functions g for which the FAB-method works.

We propose a new efficient method for the design of orthogonal and biorthogonal lapped transforms for image coding applications. It is shown how perception related constraints such as decay and smoothness of the filters' impulse responses can be incorporated in the optimization procedure. A decomposition of lapped transforms (orthogonal and biorthogonal) with 50% overlap leads to an efficient recursive optimization procedure, which is robust with respect to initial solutions. The importance of this decomposition lies in the fact that it allows to decouple the design of the even-symmetric and the odd-symmetric filters and hence drastically reduces the number of variables to be optimized. It furthermore reveals all the variables predetermined by perception related and coding-efficiency related constraints imposed on the filters. We present design and coding examples demonstrating the perceptual performance and the rate distortion performance of the resulting transforms.

We introduce a blind algorithm for the joint estimation of symbol timing and carrier frequency offset in pulse shaping OFDM systems. The proposed estimator exploits the cyclostationarity of the received OFDM signal and can be seen as an extension of the Gini-Giannakis estimator (see IEEE Trans. Comm., vol.46, p.400-11, 1998) for single-carrier systems. An important feature of our method is the capability to perform a carrier frequency acquisition over the entire bandwidth of the OFDM signal. Furthermore, our estimator can be applied even if no cyclic prefix is used. We provide simulation results demonstrating the performance of the new estimator.

Orthogonal frequency division multiplexing (OFDM) is a promising technique for high data-rate transmission over wireless channels. In general, wireless channels are time-frequency dispersive. The performance of wireless OFDM therefore depends critically on the time-frequency localization of the pulse shaping filter used. It has been pointed out in Haas (1996) that OFDM systems based on offset QAM (OFDM/OQAM) bypass a major disadvantage of OFDM schemes based on ordinary QAM, namely the fact that well-localized pulse shaping filters are prohibited in the case of a critical time-frequency grid where spectral efficiency is maximal. In this paper, we derive general orthogonality conditions for OFDM/OQAM systems and we propose efficient (FFT-based) design procedures for time-frequency well-localized OFDM/OQAM pulse shaping filters with arbitrary length and arbitrary overlapping factors. Finally, we present design examples.

We consider the error floor of coherently and differentially detected PAM (pulse amplitude modulation) in time-dispersive fading channels; PAM includes PSK (phase shift keying) and QAM as special cases. We introduce a new Zak (1968) transform based method for computing the error floor. This method can be applied to arbitrary modulation formats and a very general class of time-dispersive channels. We prove that unfiltered BPSK exhibits no error floor when the sampling phase is chosen adaptively and (for coherent detection) the basis pulse satisfies a symmetry condition. For filtered BPSK there is an error floor, which depends on the filter bandwidth. For higher-order modulations, there is always an error floor; it can be attributed to I-Q crosstalk.

We show that oversampled filter banks (FBs) offer more design freedom and less noise sensitivity than critically sampled FBs. We provide a parameterization of all synthesis FBs satisfying perfect reconstruction for a given oversampled analysis and we derive bounds and expressions for the variance of the reconstruction error due to noisy subband signals. Finally we introduce noise shaping in oversampled FBs and calculate the optimal noise shaping system.

We propose a lossy image coding scheme based on the previously introduced even-stacked cosine modulated filter banks (CMFBs) that allow linear phase filters in all channels. We describe modifications of the JPEG quantization matrix and zig-zag sequence to match the structure of even-stacked CMFBs. We discuss the efficient design of even-stacked CMFBs. The rate-distortion performance and perceptual performance of the proposed transform coder are demonstrated using simulation results.

Orthonormal Wilson bases with good time-frequency localization have been constructed by Daubechies, Jaffard, and Journe (1991). We extend this construction to Wilson sets and frames with arbitrary oversampling (or redundancy). We state conditions under which dual Weyl-Heisenberg (WH) sets induce dual Wilson sets, and we formulate duality conditions in the time domain and frequency domain. We show that the dual frame of a Wilson frame has again a Wilson structure, and that it is generated by the dual frame of the underlying Weyl-Heisenberg frame. The Wilson frame construction preserves the numerical properties of the underlying Weyl-Heisenberg frame while halving its redundancy.

We apply the theory of Weyl-Heisenberg frames (WHFs) to oversampled FIR and IIR DFT filter banks (FBs). We show that the polyphase matrices provide a matrix representation of the frame operator and we find conditions on a DFT FB to provide a WHF expansion. We also show that paraunitary and biorthogonal DFT FBs correspond to tight and exact WHFs, respectively, and that the same bounds can be obtained by an eigenanalysis of the polyphase matrices. Simulation results demonstrate the importance of the frame bounds for the design of DFT FBs.

We extend the Wigner distribution (WD) to conjugate unitary operators A/sub /spl alpha// and B/sub /spl beta//. The resulting "AB-WD" is defined both as an a-b representation and as a time-frequency representation. Important properties and relations of the WD are generalized to the AB-WD.

We propose classes of quadratic time-frequency distributions that retain the inner structure of Cohen's (see IEEE Trans. Signal Processing, vol.41, no.12, p.3275-3292, 1993) class. Each of these classes is based on a pair of "conjugate" unitary operators producing time-frequency displacements. The classes satisfy covariance and marginal properties corresponding to these operators. For each class, we define a "central member" generalizing the Wigner distribution and the Q-distribution, and we specify a transformation by which the class can be derived from Cohen's class.

Important classes of quadratic time-frequency representations (QTFRs), such as Cohen's (1966) class and the affine, hyperbolic, and power classes, are special cases within a general theory of displacement-covariant QTFRs. We present a theory of quadratic time-frequency energy distributions that satisfy a covariance property and generalized marginal properties. The theory coincides with the characteristic function method of Cohen and Baraniuk (see Proc. ICASSP-94, vol.3, p.357-360, 1994) in the special case of "conjugate operators".