We investigate Stochastic Mirror Descent (SMD) with matrix parameters and vector-valued predictions, a framework relevant to multi-class classification and matrix completion problems. Focusing on the overparameterized regime, where the total number of parameters exceeds the number of training samples, we prove that SMD with matrix mirror functions $ψ(\cdot)$ converges exponentially to a global interpolator. Furthermore, we generalize classical implicit bias results of vector SMD by demonstrating that the matrix SMD algorithm converges to the unique solution minimizing the Bregman divergence induced by $ψ(\cdot)$ from initialization subject to interpolating the data. These findings reveal how matrix mirror maps dictate inductive bias in high-dimensional, multi-output problems.

We investigate Gaussian Universality for data distributions generated via diffusion models. By Gaussian Universality we mean that the test error of a generalized linear model$f(\bf {W})$trained for a classification task on the diffusion data matches the test error of$f(\bf {W})$trained on the Gaussian Mixture with matching means and covariances per class. In other words, the test error depends only on the first and second order statistics of the diffusion-generated data in the linear setting. As a corollary, the analysis of the test error for linear classifiers can be reduced to Gaussian data from diffusion-generated data. Analyzing the performance of models trained on synthetic data is a pertinent problem due to the surge of methods such as [1]. Moreover, we show that, for any 1- Lipschitz scalar function$\phi$,$\phi (\mathbf {x})$is close to$\mathbb {E}\phi (\bf {x})$with high probability for$\bf {x}$sampled from the conditional diffusion model corresponding to each class. Finally, we note that current approaches for proving universality do not apply to diffusion-generated data as the covariance matrices of the data tend to have vanishing minimum singular values, contrary to the assumption made in the literature. This leaves extending previous mathematical universality results as an intriguing open question.

This paper investigates distributionally robust filtering for state-space models subject to exogenous disturbances in state evolution and observation processes. The joint probability distribution of the disturbance process over an arbitrary horizon is unknown but is assumed to reside within a Wasserstein-2 ambiguity set centered around a nominal distribution. We seek to develop a causal estimator that minimizes the worst-case mean squared error (MSE) among all distributions in this ambiguity set. Unlike prior works, our framework accommodates disturbances with arbitrary temporal correlations. In the finite-horizon setting, this problem reduces to a semi-definite program (SDP) whose complexity scales with the time horizon. Consequently, we focus on the infinite-horizon case, where we derive the optimal linear time-invariant (LTI) filter using the Karush-Kuhn-Tucker (KKT) conditions and propose an efficient frequency-domain algorithm to compute it. While the optimal LTI filter generally has a non-rational transfer function, we provide a minimax rational approximation method to approximate the optimal non-rational filter, in the H∞-norm, with a near-optimal finite-order state-space estimator. This approach avoids the computational challenges associated with horizon-dependent scaling in the finite-horizon case. Numerical simulations demonstrate the effectiveness of the proposed method.

Stochastic Mirror Descent (SMD) has emerged as a method for solving various convex optimization problems and, under appropriate conditions, has been shown to exponentially converge to the global optimum when the underlying loss is strongly convex. However, strong convexity of the loss fails to hold when the optimization problem is over a set of over-parameterized linear equations, a scenario that frequently occurs in modern machine learning and signal processing. In this setting, prior literature only guarantees much slower convergence rates. In this paper, we show exponential convergence of the SMD iterates to a global optimum (the one that exhibits the appropriate implicit bias) in such over-parameterized linear models. As an extension of this result, we show the exponential convergence of the related Regularizer Mirror Descent (RMD) iterates to the global optimum of explicitly regularized over-parameterized linear models.

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

A celebrated result by Gordon allows one to compare the min-max behavior of two Gaussian processes if certain inequality conditions are met. The consequences of this result include the Gaussian min-max (GMT) and convex Gaussian min-max (CGMT) theorems which have had far-reaching implications in high-dimensional statistics, machine learning, non-smooth optimization, and signal processing. Both theorems rely on a pair of Gaussian processes, first identified by Slepian, that satisfy Gordon’s comparison inequalities. In this paper, we identify a new pair of Gaussian processes satisfying these inequalities. The resulting theorems extend the classical GMT and CGMT Theorems from the case where the underlying Gaussian matrix in the primary process has iid rows to where it has independent but non-identically-distributed ones. The new CGMT is applied to the problems of multi-source Gaussian regression, as well as to binary classification of general Gaussian mixture models.

We study the infinite-horizon distributionally robust (DR) control of linear systems with quadratic costs, where disturbances have unknown, possibly time-correlated distribution within a Wasserstein-2 ambiguity set. We aim to minimize the worst-case expected regret—the excess cost of a causal policy compared to a non-causal one with access to future disturbance. Though the optimal policy lacks a finite-order state-space realization (i.e., it is non-rational), it can be characterized by a finite-dimensional parameter. Leveraging this, we develop an efficient frequency-domain algorithm to compute this optimal control policy and present a convex optimization method to construct a near-optimal state-space controller that approximates the optimal non-rational controller in the $\mathit{H}_\infty$-norm. This approach avoids solving a computationally expensive semi-definite program (SDP) that scales with the time horizon in the finite-horizon setting.

This paper is eligible for the student paper award. Regularized linear regression is a promising approach for binary classification problems in which the training set has noisy labels since the regularization term can help to avoid interpolating the mislabeled data points. In this paper we provide a systematic study of the effects of the regularization strength on the performance of linear classifiers that are trained to solve binary classification problems by minimizing a regularized least-squares objective. We consider the over-parametrized regime and assume that the classes are generated from a Gaussian Mixture Model (GMM) where a fraction$c < \displaystyle \frac{1}{2}$of the training data is mislabeled. Under these assumptions, we rigorously analyze the classification errors resulting from the application of ridge,$\ell_{1}$, and$\ell_{\infty}$regression. In particular, we demonstrate that ridge regression invariably improves the classification error. We prove that$\ell_{1}$regularization induces sparsity and observe that in many cases one can sparsify the solution by up to two orders of magnitude without any considerable loss of performance, even though the GMM has no underlying sparsity structure. For$\ell_{\infty}$regularization we show that, for large enough regularization strength, the optimal weights concentrate around two values of opposite sign. We observe that in many cases the corresponding “compression” of each weight to a single bit leads to very little loss in performance. These latter observations can have significant practical ramifications. The full version of the manuscript containing full proofs and additional plots can be found in [1].

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

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

We study the precise asymptotic behavior of stochastic mirror descent (SMD) algorithms in over-parameterized binary linear classification using regression. In this over-parameterized regime, the training loss has infinitely many global minima which defines a manifold of interpolating solutions. SMD exhibits implicit regularization and finds the interpolating solution that is closest to the initial weight vector in Bregman divergence (corresponding to the mirror's potential function). It has been empirically observed that different potentials lead to different generalization errors and different distributions of the weights. In this paper, we explicitly compute closed form expressions of the distribution of the solution and characterise its generalization performance on data generated by a Gaussian Mixture model (GMM). The theory presented well matches empirical simulations and can provide insights in understanding the generalization performance of SMD on nonlinear models, such as in deep learning.

We study the problem of transfer learning and fine-tuning in linear models for both regression and binary classification. In particular, we consider the use of stochastic gradient descent (SGD) on a linear model initialized with pretrained weights and using a small training data set from the target distribution. In the asymptotic regime of large models, we provide an exact and rigorous analysis and relate the generalization errors (in regression) and classification errors (in binary classification) for the pretrained and fine-tuned models. In particular, we give conditions under which the fine-tuned model outperforms the pretrained one. An important aspect of our work is that all the results are "universal", in the sense that they depend only on the first and second order statistics of the target distribution. They thus extend well beyond the standard Gaussian assumptions commonly made in the literature. Furthermore, our universality results extend beyond standard SGD training to the test error of a classification task trained using ridge regression.

We provide exact asymptotic expressions for the performance of regression by an $L-$layer deep random feature (RF) model, where the input is mapped through multiple random embedding and non-linear activation functions. For this purpose, we establish two key steps: First, we prove a novel universality result for RF models and deterministic data, by which we demonstrate that a deep random feature model is equivalent to a deep linear Gaussian model that matches it in the first and second moments, at each layer. Second, we make use of the convex Gaussian Min-Max theorem multiple times to obtain the exact behavior of deep RF models. We further characterize the variation of the eigendistribution in different layers of the equivalent Gaussian model, demonstrating that depth has a tangible effect on model performance despite the fact that only the last layer of the model is being trained.

The stochastic mirror descent (SMD) algorithm is a general class of training algorithms that utilizes a mirror potential to influence the implicit bias of the training algorithm and includes stochastic gradient descent (SGD) as a special case. In this paper, we explore the performance of the SMD on mean-field ensemble models and generalize earlier results obtained for SGD. The evolution of the distribution of parameters is mapped to a continuous time process in the space of probability distributions. Our main result gives a nonlinear partial differential equation (PDE) to which the continuous time process converges in the asymptotic of large networks. The impact of the mirror potential appears through a multiplicative term that is equal to the inverse of its Hessian and defines a gradient flow over an appropriate Riemannian manifold. We provide numerical simulations which allow us to study and characterize the effect of the mirror potential on the performance of networks trained with SMD for some binary classification problems.

The stochastic mirror descent (SMD) algorithm is a generalization of the celebrated stochastic gradient descent (SGD)—the workhorse of modern machine learning. In over-parameterized models, such as in deep learning, it is well known that SGD finds the weight vector that interpolates the training data and is closest to the initial weight vector in Euclidean distance. This phenomenon is called "implicit regularization". SMD allows for different implicit regularizations and finds the interpolating solution that is closest to the initial weight vector in Bregman divergence (corresponding to the mirror’s potential function). It has been empirically observed that different potentials lead to different generalization errors and different distributions of the weights. In this paper, we explicitly compute the asymptotic distribution of the optimal weight vector for SMD applied to over-parameterized linear models with Gaussian training vectors. The theory presented well matches empirical simulations and can provide a stepping stone toward the analysis of SMD on nonlinear models, such as in deep learning.

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

In this work, we study model-based reinforcement learning (RL) in unknown stabilizable linear dynamical systems. When learning a dynamical system, one needs to stabilize the unknown dynamics in order to avoid system blow-ups. We propose an algorithm that certifies fast stabilization of the underlying system by effectively exploring the environment with an improved exploration strategy. We show that the proposed algorithm attains $\Tilde{\mathcal{O}}(\sqrt{T})$ regret after $T$ time steps of agent-environment interaction. We also show that the regret of the proposed algorithm has only a polynomial dependence in the problem dimensions, which gives an exponential improvement over the prior methods. Our improved exploration method is simple, yet efficient, and it combines a sophisticated exploration policy in RL with an isotropic exploration strategy to achieve fast stabilization and improved regret. We empirically demonstrate that the proposed algorithm outperforms other popular methods in several adaptive control tasks.

Thompson Sampling (TS) is an efficient method for decision-making under uncertainty, where an action is sampled from a carefully prescribed distribution which is updated based on the observed data. In this work, we study the problem of adaptive control of stabilizable linear-quadratic regulators (LQRs) using TS, where the system dynamics are unknown. Previous works have established that $\tilde{O}(\sqrt{T})$ frequentist regret is optimal for the adaptive control of LQRs. However, the existing methods either work only in restrictive settings, require a priori known stabilizing controllers or utilize computationally intractable approaches. We propose an efficient TS algorithm for the adaptive control of LQRs, TS-based Adaptive Control, TSAC, that attains $\tilde{O}(\sqrt{T})$ regret, even for multidimensional systems, thereby solving the open problem posed in Abeille and Lazaric (2018). TSAC does not require a priori known stabilizing controller and achieves fast stabilization of the underlying system by effectively exploring the environment in the early stages. Our result hinges on developing a novel lower bound on the probability that the TS provides an optimistic sample. By carefully prescribing an early exploration strategy and a policy update rule, we show that TS achieves order-optimal regret in adaptive control of multidimensional stabilizable LQRs. We empirically demonstrate the performance and the efficiency of the proposed algorithm in several adaptive control tasks.

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

With the abundance of data, machine learning applications engaged increased attention in the last decade. An attractive approach to robustify the statistical analysis is to preprocess the data through clustering. This paper develops a low-complexity Riemannian optimization framework for solving optimization problems on the set of positive semidefinite stochastic matrices. The low-complexity feature of the proposed algorithms stems from the factorization of the optimization variable$\mathbf{X}=\mathbf{Y}\mathbf{Y}^{\mathrm{T}}$and deriving conditions on the number of columns of$\mathbf{Y}$under which the factorization yields a satisfactory solution. The paper further investigates the embedded and quotient geometries of the resulting Riemannian manifolds. In particular, the paper explicitly derives the tangent space, Riemannian gradients and Hessians, and a retraction operator allowing the design of efficient first and second-order optimization methods for the graph-based clustering applications of interest. The numerical results reveal that the resulting algorithms present a clear complexity advantage as compared with state-of-the-art Euclidean and Riemannian approaches for graph clustering applications.

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

Most modern learning problems are highly overparameterized, i.e., have many more model parameters than the number of training data points. As a result, the training loss may have infinitely many global minima (parameter vectors that perfectly “interpolate” the training data). It is therefore imperative to understand which interpolating solutions we converge to, how they depend on the initialization and learning algorithm, and whether they yield different test errors. In this article, we study these questions for the family of stochastic mirror descent (SMD) algorithms, of which stochastic gradient descent (SGD) is a special case. Recently, it has been shown that for overparameterized linear models, SMD converges to the closest global minimum to the initialization point, where closeness is in terms of the Bregman divergence corresponding to the potential function of the mirror descent. With appropriate initialization, this yields convergence to the minimum-potential interpolating solution, a phenomenon referred to as implicit regularization. On the theory side, we show that for sufficiently-overparameterized nonlinear models, SMD with a (small enough) fixed step size converges to a global minimum that is “very close” (in Bregman divergence) to the minimum-potential interpolating solution, thus attaining approximate implicit regularization. On the empirical side, our experiments on the MNIST and CIFAR-10 datasets consistently confirm that the above phenomenon occurs in practical scenarios. They further indicate a clear difference in the generalization performances of different SMD algorithms: experiments on the CIFAR-10 dataset with different regularizers,$\ell _{1}$to encourage sparsity,$\ell _{2}$(SGD) to encourage small Euclidean norm, and$\ell _{\infty }$to discourage large components, surprisingly show that the$\ell _{\infty }$norm consistently yields better generalization performance than SGD, which in turn generalizes better than the$\ell _{1}$norm.

We consider the problem of filtering in linear state-space models (e.g., the Kalman filter setting) through the lens of regret optimization. Specifically, we study the problem of causally estimating a desired signal, generated by a linear state-space model driven by process noise, based on noisy observations of a related observation process. We define a novel regret criterion for estimator design as the difference of the estimation error energies between a clairvoyant estimator that has access to all future observations (a so-called smoother) and a causal one that only has access to current and past observations. The regret-optimal estimator is the causal estimator that minimizes the worst-case regret across all bounded-energy noise sequences. We provide a solution for the regret filtering problem at two levels. First, an horizon-independent solution at the operator level is obtained by reducing the regret to the well-known Nehari problem. Secondly, our main result for state-space models is an explicit estimator that achieves the optimal regret. The regret-optimal estimator is represented as a finite-dimensional state-space whose parameters can be computed by solving three Riccati equations and a single Lyapunov equation. We demonstrate the applicability and efficacy of the estimator in a variety of problems and observe that the estimator has average and worst-case performances that are simultaneously close to their optimal values.

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

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

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

We study the convergence, the implicit regularization and the generalization of stochastic mirror descent (SMD) algorithms in overparameterized nonlinear models, where the number of model parameters exceeds the number of training data points. Due to overpa-rameterization, the training loss has infinitely many global minima where they define a manifold of interpolating solutions. To have an understanding of the generalization performance of SMD algorithms, it is important to characterize which global minima the SMD algorithms converge to. In this work, we first theoretically show that in the overparameterized nonlinear setting, if the initialization is close enough to the manifold of global minima, which is usually the case in the high overparameterization setting, using sufficiently small step size, SMD converges to a global minimum. We further prove that this global minimum is approximately the closest one to the initialization in Bregman divergence, demonstrating the approximate implicit regularization of SMD. We then empirically confirm that these theoretical results are observed in practice. Finally, we provide an extensive study of the generalization of SMD algorithms. In our experiments, we show that on the CIFAR-10 dataset, SMD with ℓ10norm potential (as a surrogate for ℓ∞) consistently general-izes better than SGD (corresponding to an ℓ2norm potential), which in turn consistently outperforms SMD with ℓ1norm potential.

Logistic models are commonly used for binary classification tasks. The success of such models has often been attributed to their connection to maximum-likelihood estimators. It has been shown that gradient descent algorithm, when applied on the logistic loss, converges to the max-margin classifier (a.k.a. hard-margin SVM). The performance of the max-margin classifier has been recently analyzed in \cite{montanari2019generalization, deng2019model}. Inspired by these results, in this paper, we present and study a more general setting, where the underlying parameters of the logistic model possess certain structures (sparse, block-sparse, low-rank, etc.) and introduce a more general framework (which is referred to as “Generalized Margin Maximizer”, GMM). While classical max-margin classifiers minimize the $2$-norm of the parameter vector subject to linearly separating the data, GMM minimizes any arbitrary convex function of the parameter vector. We provide a precise analysis of the performance of GMM via the solution of a system of nonlinear equations. We also provide a detailed study for three special cases: ($1$) $\ell_2$-GMM that is the max-margin classifier, ($2$) $\ell_1$-GMM which encourages sparsity, and ($3$) $\ell_{\infty}$-GMM which is often used when the parameter vector has binary entries. Our theoretical results are validated by extensive simulation results across a range of parameter values, problem instances, and model structures.

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

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

Gabidulin codes over fields of characteristic zero were recently constructed by Augot et al., whenever the Galois group of the underlying field extension is cyclic. In parallel, the interest in sparse generator matrices of Reed-Solomon and Gabidulin codes has increased lately, due to applications in distributed computations. In particular, a certain condition pertaining to the intersection of zero entries at different rows, was shown to be necessary and sufficient for the existence of the sparsest possible generator matrix of Gabidulin codes over finite fields. In this paper we complete the picture by showing that the same condition is also necessary and sufficient for Gabidulin codes over fields of characteristic zero. Our proof builds upon and extends tools from the finite-field case, combines them with a variant of the Schwartz-Zippel lemma over automorphisms, and provides a simple randomized construction algorithm whose probability of success can be arbitrarily close to one. In addition, potential applications for low-rank matrix recovery are discussed.

We study the problem of system identification and adaptive control in partially observable linear dynamical systems. Adaptive and closed-loop system identification is a challenging problem due to correlations introduced in data collection. In this paper, we present the first model estimation method with finite-time guarantees in both open and closed-loop system identification. Deploying this estimation method, we propose adaptive control online learning (AdapOn), an efficient reinforcement learning algorithm that adaptively learns the system dynamics and continuously updates its controller through online learning steps. AdapOn estimates the model dynamics by occasionally solving a linear regression problem through interactions with the environment. Using policy re-parameterization and the estimated model, AdapOn constructs counterfactual loss functions to be used for updating the controller through online gradient descent. Over time, AdapOn improves its model estimates and obtains more accurate gradient updates to improve the controller. We show that AdapOn achieves a regret upper bound of $\text{polylog}\left(T\right)$, after $T$ time steps of agent-environment interaction. To the best of our knowledge, AdapOn is the first algorithm that achieves $\text{polylog}\left(T\right)$ regret in adaptive control of \textit{unknown} partially observable linear dynamical systems which includes linear quadratic Gaussian (LQG) control.

Gabidulin codes are the first general construction of linear codes that are maximum rank distant (MRD). They have found applications in linear network coding, for example, when the transmitter and receiver are oblivious to the inner workings and topology of the network (the so-called incoherent regime). The reason is that Gabidulin codes can be used to map information to linear subspaces, which in the absence of errors cannot be altered by linear operations, and in the presence of errors can be corrected if the subspace is perturbed by a small rank. Furthermore, in distributed coding and distributed systems, one is led to the design of error correcting codes whose generator matrix must satisfy a given support constraint. In this paper, we give necessary and sufficient conditions on the support of the generator matrix that guarantees the existence of Gabidulin codes and general MRD codes. When the rate of the code is not very high, this is achieved with the same field size necessary for Gabidulin codes with no support constraint. When these conditions are not satisfied, we characterize the largest possible rank distance under the support constraints and show that they can be achieved by subcodes of Gabidulin codes. The necessary and sufficient conditions are identical to those that appear for MDS codes which were recently proven by Yildiz et al. and Lovett in the context of settling the GM-MDS conjecture.

We investigate practical aspects of a recently introduced blind (noncoherent) communication scheme, called modulation on conjugate-reciprocal zeros (MOCZ). MOCZ is suitable for a reliable transmission of sporadic and short-packets at ultra-low latency and high spectral efficiency via unknown multipath channels, which are assumed to be static over the receive duration of one packet. The information is modulated on the zeros of the transmitted discrete-time baseband signal's z- transform. Because of ubiquitous impairments between the transmitter and receiver clocks, a carrier frequency offset occurs after down-conversion to the baseband. This results in a common rotation of the zeros. To identify fractional rotations of the base angle in the zero-pattern, we propose an oversampled direct zero-testing decoder to identify the most likely one. Integer rotations correspond to cyclic shifts of the binary message, which we determine by cyclically permutable codes (CPC). Additionally, the embedding of CPCs into cyclic codes, enables additive error-correction which reduces the bit-error-rate tremendously. Furthermore, we exploit the trident structure in the signal's autocorrelation for an energy based detector to estimate timing offsets and the effective channel delay spread. We finally demonstrate how this joint data and channel estimation can be largely improved by receive antenna diversity at low SNR.

We consider a discrete-time linear quadratic Gaussian networked control setting where the (full information) observer and controller are separated by a fixed-rate noiseless channel. We study the event-triggered control setup in which the encoder may choose to either transmit a packet or remain silent. We recast this problem into that of fixed-rate quantization with an extra symbol that corresponds to the silence event. This way, controlling the average transmission rate is possible by constraining the minimal probability of the silence symbol. We supplement our theoretical framework with numerical simulations.

We study the performance of a convex data detection method in large multiple-input multiple-output (MIMO) systems. The goal is to recover an n-dimensional complex signal whose entries are from an arbitrary constellation D C C, using m noisy linear measurements. Since the Maximum Likelihood (ML) estimation involves minimizing a loss function over the discrete set Dn, it becomes computationally intractable for large n. One approach is to relax D to a convex set and to utilize convex programing to solve the problem and then to map the answer to the closest point in the set D. We assume an i.i.d. complex Gaussian channel matrix and derive precise expressions for the symbol error probability of the proposed convex method in the limit of m, n → ∞. Prior work was only able to do so for real valued constellations such as BPSK and PAM. The main contribution of this paper is to extend the results to complex valued constellations. In particular, we use our main theorem to calculate the performance of the complex algorithm for PSK and QAM constellations. In addition, we introduce a closed-form formula for the symbol error probability in the high-SNR regime and determine the minimum number of measurements m required for consistent signal recovery.

Stochastic mirror descent (SMD) algorithms have recently garnered a great deal of attention in optimization, signal processing, and machine learning. They are similar to stochastic gradient descent (SGD), in that they perform updates along the negative gradient of an instantaneous (or stochastically chosen) loss function. However, rather than update the parameter (or weight) vector directly, they update it in a "mirrored" domain whose transformation is given by the gradient of a strictly convex differentiable potential function. SMD was originally conceived to take advantage of the underlying geometry of the problem as a way to improve the convergence rate over SGD. In this paper, we study SMD, for linear models and convex loss functions, through the lens of H∞estimation theory and come up with a minimax interpretation of the SMD algorithm which is the counterpart of the H∞-optimality of the SGD algorithm for linear models and quadratic loss. In doing so, we identify a fundamental conservation law that SMD satisfies and use it to study the convergence properties of the algorithm. For constant step size SMD, when the linear model is over-parameterized, we give a deterministic proof of convergence for SMD and show that from any initial point, it converges to the closest point in the space of all parameter vectors that interpolate the data, where closest is in the sense of the Bregman divergence of the potential function. This property is referred to as implicit regularization: with an appropriate choice of the potential function one can guarantee convergence to the minimizer of any desired convex regularizer. For vanishing step size SMD, and in the standard stochastic optimization setting, we give a direct and elementary proof of convergence for SMD to the "true" parameter vector which avoids ergodic averaging or appealing to stochastic differential equations.

We study the problem of estimating a high-dimensional sparse covariance matrix, Σ0, from a finite number of quadratic measurements, i.e., measurements aiTΣ0aiwhich are quadratic forms in the measurement vectors airesulting from the covariance matrix, Σ0. Such a problem arises in applications where we can only make energy measurements of the underlying random variables. We study a simple LASSO-like convex recovery algorithm which involves a squared 2-norm (to match the covariance estimate to the measurements), plus a regularization term (that penalizes the ℓ1-norm of the non-diagonal entries of Σ0to enforce sparsity). When the measurement vectors are i.i.d. Gaussian, we obtain the precise error performance of the algorithm (accurately determining the estimation error in any metric, e.g., 2-norm, operator norm, etc.) as a function of the number of measurements and the underlying distribution of Σ0. In particular, in the noiseless case we determine the necessary and sufficient number of measurements required to perfectly recover Σ0as a function of its sparsity. Our results rely on a novel comparison lemma which relates a convex optimization problem with "quadratic Gaussian" measurements to one which has i.i.d. Gaussian measurements.

Several real-world applications, notably in non-negative matrix factorization, graph-based clustering, and machine learning, require solving a convex optimization problem over the set of stochastic and doubly stochastic matrices. A common feature of these problems is that the optimal solution is generally a low-rank matrix. This paper suggests reformulating the problem by taking advantage of the low-rank factorization X = UVTand develops a Riemannian optimization framework for solving optimization problems on the set of low-rank stochastic and doubly stochastic matrices. In particular, this paper introduces and studies the geometry of the low-rank stochastic multinomial and the doubly stochastic manifold in order to derive first-order optimization algorithms. Being carefully designed and of lower dimension than the original problem, the proposed Riemannian optimization framework presents a clear complexity advantage. The claim is attested through numerical experiments on real-world and synthetic data for Non-negative Matrix Factorization (NFM) applications. The proposed algorithm is shown to outperform, in terms of running time, state-of-the-art methods for NFM.

Gabidulin codes are the first general construction of linear codes that are maximum rank distance (MRD). They have found applications in linear network coding, for example, when the transmitter and receiver are oblivious to the inner workings and topology of the network (the so-called incoherent regime). The reason is that Gabidulin codes can be used to map information to linear subspaces, which in the absence of errors cannot be altered by linear operations, and in the presence of errors can be corrected if the subspace is perturbed by a small rank. Furthermore, in distributed coding and distributed systems, one is led to the design of error correcting codes whose generator matrix must satisfy a given support constraint. In this paper, we give necessary and sufficient conditions on the support of the generator matrix that guarantees the existence of Gabidulin codes and general MRD codes. When the rate of the code is not very high, this is achieved with the same field size necessary for Gabidulin codes with no support constraint. When these conditions are not satisfied, we characterize the largest possible rank distance under the support constraints and show that they can be achieved by subcodes of Gabidulin codes. The necessary and sufficient conditions are identical to those that appear for MDS codes which were recently proven in [1], [2] in the context of settling the GM-MDS conjecture.

We study the problem of recovering a structured signal from independently and identically drawn linear measurements. A convex penalty function $f(\cdot)$ is considered which penalizes deviations from the desired structure, and signal recovery is performed by minimizing $f(\cdot)$ subject to the linear measurement constraints. The main question of interest is to determine the minimum number of measurements that is necessary and sufficient for the perfect recovery of the unknown signal with high probability. Our main result states that, under some mild conditions on $f(\cdot)$ and on the distribution from which the linear measurements are drawn, the minimum number of measurements required for perfect recovery depends only on the first and second order statistics of the measurement vectors. As a result, the required of number of measurements can be determining by studying measurement vectors that are Gaussian (and have the same mean vector and covariance matrix) for which a rich literature and comprehensive theory exists. As an application, we show that the minimum number of random quadratic measurements (also known as rank-one projections) required to recover a low rank positive semi-definite matrix is $3nr$, where $n$ is the dimension of the matrix and $r$ is its rank. As a consequence, we settle the long standing open question of determining the minimum number of measurements required for perfect signal recovery in phase retrieval using the celebrated PhaseLift algorithm, and show it to be $3n$.

Logistic regression is commonly used for modeling dichotomous outcomes. In the classical setting, where the number of observations is much larger than the number of parameters, properties of the maximum likelihood estimator in logistic regression are well understood. Recently, Sur and Candes~\cite{sur2018modern} have studied logistic regression in the high-dimensional regime, where the number of observations and parameters are comparable, and show, among other things, that the maximum likelihood estimator is biased. In the high-dimensional regime the underlying parameter vector is often structured (sparse, block-sparse, finite-alphabet, etc.) and so in this paper we study regularized logistic regression (RLR), where a convex regularizer that encourages the desired structure is added to the negative of the log-likelihood function. An advantage of RLR is that it allows parameter recovery even for instances where the (unconstrained) maximum likelihood estimate does not exist. We provide a precise analysis of the performance of RLR via the solution of a system of six nonlinear equations, through which any performance metric of interest (mean, mean-squared error, probability of support recovery, etc.) can be explicitly computed. Our results generalize those of Sur and Candes and we provide a detailed study for the cases of $\ell_2^2$-RLR and sparse ($\ell_1$-regularized) logistic regression. In both cases, we obtain explicit expressions for various performance metrics and can find the values of the regularizer parameter that optimizes the desired performance. The theory is validated by extensive numerical simulations across a range of parameter values and problem instances.

We study the problem of constructing balanced generator matrices for Reed-Solomon and Tamo-Barg codes. More specifically, we are interested in realizing generator matrices, for the full-length cyclic versions of these codes, where all rows have the same weight and the difference in weight between any columns is at most one. The results presented in this paper translate to computationally balanced encoding schemes, which can be appealing in distributed storage applications. Indeed, the balancedness of these generator matrices guarantees that the computation effort exerted by any storage node is essentially the same. In general, the framework presented can accommodate various values for the required row weight. We emphasize the possibility of constructing sparsest and balanced generator matrices for Reed-Solomon codes, i.e., each row is a minimum distance codeword. The number of storage nodes contacted once a message symbol is updated decreases with the row weight, so sparse constructions are appealing in that context. Results of similar flavor are presented for cyclic Tamo-Barg codes. In particular, we show that for a code with minimum distance d and locality r, a construction in which every row is of weight d+r-1 is possible. The constructions presented are deterministic and operate over the codes' original underlying finite field. As a result, efficient decoding from both errors and erasures is possible thanks to the plethora of efficient decoders available for the codes considered.

We consider the problem of designing optimal linear codes (in terms of having the largest minimum distance) subject to a support constraint on the generator matrix. We show that the largest minimum distance can be achieved by a subcode of a Reed–Solomon code of small field size and with the same minimum distance. In particular, if the code has length$n$, and maximum minimum distance$d$(over all generator matrices with the given support), then an optimal code exists for any field size$q\geq 2n-d$. As a by-product of this result, we settle the GM–MDS conjecture in the affirmative.

We introduce a novel blind (noncoherent) communication scheme, called modulation on conjugate-reciprocal zeros (MOCZ), pronounced as “Moxie,” to reliably transmit sporadic short-packets over unknown wireless multipath channels. In MOCZ, the information is modulated onto the zeros of the transmitted discrete-time baseband signal's z-transform, which yields to a codebook of non-orthogonal signals. In the absence of additive noise, the zero structure of the signal is perfectly preserved at the receiver, no matter what the channel impulse response (CIR) is. Furthermore, by a proper selection of the zeros, we show that MOCZ is not only invariant to the CIR but also robust against additive noise. Starting with the maximum-likelihood estimator, we define a low complexity and reliable decoder and compare it to various state-of-the-art noncoherent multipath schemes, such as OFDM index-modulation (IM), OFDM pilot-aided, OFDM differential-modulation, and pulse-position-modulation. Our scheme outperforms all schemes and maintains its performance even if the length becomes shorter than the CIR.

Given a data matrix with partially observed entries, the low-rank matrix completion problem is one of finding a matrix with the lowest rank that perfectly fits the given observations. While there exist convex relaxations for the low-rank completion problem, the underlying problem is inherently nonconvex, and most algorithms (alternating projection, Riemannian optimization, etc.) heavily depend on the initialization. This paper proposes an improved initialization that relies on successive rank-l updates. Further, the paper proposes theoretical guarantees under which the proposed initialization is closer to the unknown optimal solution than the all zeros initialization in the Frobenius norm. To cope with the problem of local minima, the paper introduces and uses random norms to change the position of the local minima while preserving the global one. Using a Riemannian optimization routine, simulation results reveal that the proposed solution succeeds in completing Gaussian partially observed matrices with a random set of revealed entries close to the information-theoretical limits, thereby significantly improving on prior methods.

Solving a large-scale system of linear equations is a key step at the heart of many algorithms in scientific computing, machine learning, and beyond. When the problem dimension is large, computational and/or memory constraints make it desirable, or even necessary, to perform the task in a distributed fashion. In this paper, we consider a common scenario in which a taskmaster intends to solve a large-scale system of linear equations by distributing subsets of the equations among a number of computing machines/cores. We propose a new algorithm called Accelerated Projection-based Consensus, in which at each iteration every machine updates its solution by adding a scaled version of the projection of an error signal onto the nullspace of its system of equations, and the taskmaster conducts an averaging over the solutions with momentum. The convergence behavior of the proposed algorithm is analyzed in detail and analytically shown to compare favorably with the convergence rate of alternative distributed methods, namely distributed gradient descent, distributed versions of Nesterov's accelerated gradient descent and heavy-ball method, the block Cimmino method, and Alternating Direction Method of Multipliers. On randomly chosen linear systems, as well as on real-world data sets, the proposed method offers significant speed-up relative to all the aforementioned methods. Finally, our analysis suggests a novel variation of the distributed heavy-ball method, which employs a particular distributed preconditioning and achieves the same theoretical convergence rate as that in the proposed consensus-based method.

This paper develops a Riemannian optimization framework for solving optimization problems on the set of symmetric positive semidefinite stochastic matrices. The paper first reformulates the problem by factorizing the optimization variable as $\mathbf{X}=\mathbf{Y}\mathbf{Y}^T$ and deriving conditions on $p$, i.e., the number of columns of $\mathbf{Y}$, under which the factorization yields a satisfactory solution. The reparameterization of the problem allows its formulation as an optimization over either an embedded or quotient Riemannian manifold whose geometries are investigated. In particular, the paper explicitly derives the tangent space, Riemannian gradients and retraction operator that allow the design of efficient optimization methods on the proposed manifolds. The numerical results reveal that, when the optimal solution has a known low-rank, the resulting algorithms present a clear complexity advantage when compared with state-of-the-art Euclidean and Riemannian approaches for graph clustering applications.

Today's massively-sized datasets have made it necessary to often perform computations on them in a distributed manner. In principle, a computational task is divided into subtasks which are distributed over a cluster operated by a taskmaster. One issue faced in practice is the delay incurred due to the presence of slow machines, known as stragglers. Several schemes, including those based on replication, have been proposed in the literature to mitigate the effects of stragglers and more recently, those inspired by coding theory have begun to gain traction. In this work, we consider a distributed gradient descent setting suitable for a wide class of machine learning problems. We adopt the framework of Tandon et al. [1] and present a deterministic scheme that, for a prescribed per-machine computational effort, recovers the gradient from the least number of machines f theoretically permissible, via an O(f2) decoding algorithm. The idea is based on a suitably designed Reed-Solomon code that has a sparsest and balanced generator matrix. We also provide a theoretical delay model which can be used to minimize the expected waiting time per computation by optimally choosing the parameters of the scheme. Finally, we supplement our theoretical findings with numerical results that demonstrate the efficacy of the method and its advantages over competing schemes.

Recovering an unknown complex signal from the magnitude of linear combinations of the signal is referred to as phase retrieval. We present an exact performance analysis of a recently proposed convex-optimization-formulation for this problem, known as PhaseMax. Standard convex-relaxation-based methods in phase retrieval resort to the idea of “lifting” which makes them computationally inefficient, since the number of unknowns is effectively squared. In contrast, PhaseMax is a novel convex relaxation that does not increase the number of unknowns. Instead it relies on an initial estimate of the true signal which must be externally provided. In this paper, we investigate the required number of measurements for exact recovery of the signal in the large system limit and when the linear measurement matrix is random with iid standard normal entries. If n denotes the dimension of the unknown complex signal and m the number of phaseless measurements, then in the large system limit, measurements is necessary and sufficient to recover the signal with high probability, where θ is the angle between the initial estimate and the true signal. Our result indicates a sharp phase transition in the asymptotic regime which matches the empirical result in numerical simulations.

Designing good error correcting codes whose generator matrix has a support constraint, i.e., one for which only certain entries of the generator matrix are allowed to be nonzero, has found many recent applications, including in distributed coding and storage, multiple access networks, and weakly secure data exchange. The dual problem, where the parity check matrix has a support constraint, comes up in the design of locally repairable codes. The central problem here is to design codes with the largest possible minimum distance, subject to the given support constraint on the generator matrix. An upper bound on the minimum distance can be obtained through a set of singleton bounds, which can be alternatively thought of as a cut-set bound. Furthermore, it is well known that, if the field size is large enough, any random generator matrix obeying the support constraint will achieve the maximum minimum distance with high probability. Since random codes are not easy to decode, structured codes with efficient decoders, e.g., Reed-Solomon codes, are much more desirable. The GM-MDS conjecture of Dau et al states that the maximum minimum distance over all codes satisfying the generator matrix support constraint can be obtained by a Reed Solomon code. If true, this would have significant consequences. The conjecture has been proven for several special case: when the dimension of the code k is less than or equal to five, when the number of distinct support sets on the rows of the generator matrix m, say, is less than or equal to three, or when the generator matrix is sparsest and balanced. In this paper, we report on further progress on the GM-MDS conjecture. 1. In particular, we show that the conjecture is true for all m less than equal to six. This generalizes all previous known results (except for the sparsest and balanced case, which is a very special support constraint).

We consider the problem of designing optimal linear codes (in terms of having the largest minimum distance) subject to a support constraint on the generator matrix. We show that the largest minimum distance can be achieved by a subcode of a Reed-Solomon code of small field size and with the same minimum distance. As a by-product of this result, we settle the GM-MDS conjecture of Dau et al. in the affirmative.

The problem of estimating an unknown signal, $\mathbf x_0\in \mathbb R^n$, from a vector $\mathbf y\in \mathbb R^m$ consisting of $m$ magnitude-only measurements of the form $y_i=|\mathbf a_i\mathbf x_0|$, where $\mathbf a_i$'s are the rows of a known measurement matrix $\mathbf A$ is a classical problem known as phase retrieval. This problem arises when measuring the phase is costly or altogether infeasible. In many applications in machine learning, signal processing, statistics, etc., the underlying signal has certain structure (sparse, low-rank, finite alphabet, etc.), opening of up the possibility of recovering $\mathbf x_0$ from a number of measurements smaller than the ambient dimension, i.e., $m

A popular approach for estimating an unknown signal x0∈ ℝnfrom noisy, linear measurements y = Ax0+ z ∈ ℝmis via solving a so called regularized M-estimator: x̂ := arg minx£(y - Ax) + λf(x). Here, £ is a convex loss function, f is a convex (typically, non-smooth) regularizer, and λ > 0 is a regularizer parameter. We analyze the squared error performance ∥x̂-x0∥22of such estimators in the high-dimensional proportional regime where m, n → ∞ and m/n → δ. The design matrix A is assumed to have entries iid Gaussian; only minimal and rather mild regularity conditions are imposed on the loss function, the regularizer, and on the noise and signal distributions. We show that the squared error converges in probability to a nontrivial limit that is given as the solution to a minimax convex-concave optimization problem on four scalar optimization variables. We identify a new summary parameter, termed the expected Moreau envelope to play a central role in the error characterization. The precise nature of the results permits an accurate performance comparison between different instances of regularized M-estimators and allows to optimally tune the involved parameters (such as the regularizer parameter and the number of measurements). The key ingredient of our proof is the convex Gaussian min-max theorem which is a tight and strengthened version of a classical Gaussian comparison inequality that was proved by Gordon in 1988.

We consider the problem of identifying the causal direction between two discrete random variables using observational data. Unlike previous work, we keep the most general functional model but make an assumption on the unobserved exogenous variable: Inspired by Occam's razor, we assume that the exogenous variable is simple in the true causal direction. We quantify simplicity using Renyi entropy. Our main result is that, under natural assumptions, if the exogenous variable has low H0 entropy (cardinality) in the true direction, it must have high H0 entropy in the wrong direction. We establish several algorithmic hardness results about estimating the minimum entropy exogenous variable. We show that the problem of finding the exogenous variable with minimum H1 entropy (Shannon Entropy) is equivalent to the problem of finding minimum joint entropy given n marginal distributions, also known as minimum entropy coupling problem. We propose an efficient greedy algorithm for the minimum entropy coupling problem, that for n=2 provably finds a local optimum. This gives a greedy algorithm for finding the exogenous variable with minimum Shannon entropy. Our greedy entropy-based causal inference algorithm has similar performance to the state of the art additive noise models in real datasets. One advantage of our approach is that we make no use of the values of random variables but only their distributions. Our method can therefore be used for causal inference for both ordinal and also categorical data, unlike additive noise models.

This paper investigates the problem of recovering an n-dimensional BPSK signal x0∈ {−1, 1}nfrom m-dimensional measurement vector y = Ax+z, where A and z are assumed to be Gaussian with iid entries. We consider two variants of decoders based on the regularized least squares followed by hard-thresholding: the case where the convex relaxation is from {−1, 1}nto ℝnand the box constrained case where the relaxation is to [−1, 1]n. For both cases, we derive an exact expression of the bit error probability when n and m grow simultaneously large at a fixed ratio. For the box constrained case, we show that there exists a critical value of the SNR, above which the optimal regularizer is zero. On the other side, the regularization can further improve the performance of the box relaxation at low to moderate SNR regimes. We also prove that the optimal regularizer in the bit error rate sense for the unboxed case is nothing but the MMSE detector.

Phaseless super-resolution refers to the problem of super-resolving a signal from only its low-frequency Fourier magnitude measurements. In this paper, we consider the phaseless super-resolution problem of recovering a sum of sparse Dirac delta functions which can be located anywhere in the continuous time-domain. For such signals in the continuous domain, we propose a novel Semidefinite Programming (SDP) based signal recovery method to achieve the phaseless super-resolution. This work extends the recent work of Jaganathan et al. [1], which considered phaseless super-resolution for discrete signals on the grid.

Binary embedding is the problem of mapping points from a high-dimensional space to a Hamming cube in lower dimension while preserving pairwise distances. An efficient way to accomplish this is to make use of fast embedding techniques involving Fourier transform e.g. circulant matrices. While binary embedding has been studied extensively, theoretical results on fast binary embedding are rather limited. In this work, we build upon the recent literature to obtain significantly better dependencies on the problem parameters. A set of N points in ℝncan be properly embedded into the Hamming cube {±1}kwith δ distortion, by using k ~ δ-3log N samples which is optimal in the number of points N and compares well with the optimal distortion dependency δ-2. Our optimal embedding result applies in the regime log N ≲ n1/3. Furthermore, if the looser condition log N ≲ √n holds, we show that all but an arbitrarily small fraction of the points can be optimally embedded. We believe the proposed techniques can be useful to obtain improved guarantees for other nonlinear embedding problems.

Phaseless super-resolution is the problem of recovering an unknown signal from measurements of the “magnitudes” of the “low frequency” Fourier transform of the signal. This problem arises in applications where measuring the phase, and making high-frequency measurements, are either too costly or altogether infeasible. The problem is especially challenging because it combines the difficult problems of phase retrieval and classical super-resolution. Recently, the authors in [1] demonstrated that by making three phaseless low-frequency measurements, obtained by appropriately “masking” the signal, one can uniquely and robustly identify the phase using convex programming and obtain the same super-resolution performance reported in [2]. However, the masks proposed in [1] are very specific and in many applications cannot be directly implemented. In this paper, we broadly extend the class of masks that can be used to recover the phase and show how their effect can be emulated in coherent diffraction imaging using multiple illuminations, as well as in direction-of-arrival (DoA) estimation using multiple sources to excite the environment. We provide numerical simulations to demonstrate the efficacy of the method and approach.

We consider the problem of crowdsourced clustering of a set of items based on queries of the similarity of triple of objects. Such an approach, called triangle queries, was proposed in [1], where it was shown that, for a fixed query budget, it outperforms clustering based on edge queries (i.e, comparing pairs of objects). In [1] the clustering algorithm for triangle and edge queries was identical and each triangle query response was treated as 3 separate edge query responses. In this paper we directly exploit the triangle structure of the responses by embedding them into a 3-way tensor. Since there are 5 possible responses to each triangle query, it is a priori not clear how best to embed them into the tensor. We give sufficient conditions on non-trivial embedding such that the resulting tensor has a rank equal to the underlying number of clusters (akin to what happens with the rank of the adjacency matrix). We then use an alternating least squares tensor decomposition algorithm to cluster a noisy and partially observed tensor and show, through extensive numerical simulations, that it significantly outperforms methods that make use only of the adjacency matrix.

We analyze an estimator based on the Bregman divergence for recovery of structured models from additive noise. The estimator can be seen as a regularized maximum likelihood estimator for an exponential family where the natural parameter is assumed to be structured. For all such Bregman denoising estimators, we provide an error bound for a natural associated error measure. Our error bound makes it possible to analyze a wide range of estimators, such as those in proximal denoising and inverse covariance matrix estimation, in a unified manner. In the case of proximal denoising, we exactly recover the existing tight normalized mean squared error bounds. In sparse precision matrix estimation, our bounds provide optimal scaling with interpretable constants in terms of the associated error measure.

The BOX-LASSO is a variant of the popular LASSO that includes an additional box-constraint. We propose its use as a decoder in modern Multiple Input Multiple Output (MIMO) communication systems with modulation methods such as the Generalized Space Shift Keying (GSSK) modulation, which produces constellation vectors that are inherently sparse and with bounded elements. In that direction, we prove novel explicit asymptotic characterizations of the squared-error and of the per-element error rate of the BOX-LASSO, under iid Gaussian measurements. In particular, the theoretical predictions can be used to quantify the improved performance of the BOX-LASSO, when compared to the previously used standard LASSO. We include simulation results that validate both these premises and our theoretical predictions.

We construct balanced and sparse generator matrices for Tamo and Barg's Locally Recoverable Codes (LRCs). More specifically, for a cyclic Tamo-Barg code of length n, dimension k and locality r, we show how to deterministically construct a generator matrix where the number of nonzeros in any two columns differs by at most one, and where the weight of every row is d + r - 1, where d is the minimum distance of the code. Since LRCs are designed mainly for distributed storage systems, the results presented in this work provide a computationally balanced and efficient encoding scheme for these codes. The balanced property ensures that the computational effort exerted by any storage node is essentially the same, whilst the sparse property ensures that this effort is minimal. The work presented in this paper extends a similar result previously established for Reed-Solomon (RS) codes, where it is now known that any cyclic RS code possesses a generator matrix that is balanced as described, but is sparsest, meaning that each row has d nonzeros.

We study the problem of identifying the causal relationship between two discrete random variables from observational data. We recently proposed a novel framework called entropie causality that works in a very general functional model but makes the assumption that the unobserved exogenous variable has small entropy in the true causal direction. This framework requires the solution of a minimum entropy coupling problem: Given marginal distributions of m discrete random variables, each on n states, find the joint distribution with minimum entropy, that respects the given marginals. This corresponds to minimizing a concave function of nmvariables over a convex polytope defined by nm linear constraints, called a transportation polytope. Unfortunately, it was recently shown that this minimum entropy coupling problem is NP-hard, even for 2 variables with n states. Even representing points (joint distributions) over this space can require exponential complexity (in n, m) if done naively. In our recent work we introduced an efficient greedy algorithm to find an approximate solution for this problem. In this paper we analyze this algorithm and establish two results: that our algorithm always finds a local minimum and also is within an additive approximation error from the unknown global optimum.

Providing short-message communication and simultaneous channel estimation for sporadic and fast fading scenarios is a challenge for future wireless networks. In this work we propose a novel blind communication and deconvolution scheme by using Huffman sequences, which allows to solve three important tasks at once: (i) determination of the transmit power (ii) identification of the instantaneous discrete-time FIR channel if the channel delay is less than L/2 and (iii) simultaneously communicating L-1 bits of information. Our signal reconstruction uses a recent semi-definite program that can recover two unknown signals from their auto-correlations and cross-correlations. This convex algorithm shows numerical stability and operates fully deterministic without any further channel assumptions.

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

A problem that has been of recent interest in statistical inference, machine learning and signal processing is that of understanding the asymptotic behavior of regularized least squares solutions under random measurement matrices (or dictionaries). The Least Absolute Shrinkage and Selection Operator (LASSO or least-squares with $\ell_1$ regularization) is perhaps one of the most interesting examples. Precise expressions for the asymptotic performance of LASSO have been obtained for a number of different cases, in particular when the elements of the dictionary matrix are sampled independently from a Gaussian distribution. It has also been empirically observed that the resulting expressions remain valid when the entries of the dictionary matrix are independently sampled from certain non-Gaussian distributions. In this paper, we confirm these observations theoretically when the distribution is sub-Gaussian. We further generalize the previous expressions for a broader family of regularization functions and under milder conditions on the underlying random, possibly non-Gaussian, dictionary matrix. In particular, we establish the universality of the asymptotic statistics (e.g., the average quadratic risk) of LASSO with non-Gaussian dictionaries.

We study the channel capacity of a general discrete energy harvesting channel with a finite battery. Contrary to traditional communication systems, the transmitter of such a channel is powered by a device that harvests energy from a random exogenous energy source and has a finite-sized battery. As a consequence, at each transmission opportunity, the system can only transmit a symbol whose energy is no more than the energy currently available. This new type of power supply introduces an unprecedented input constraint for the channel, which is simultaneously random, instantaneous, and influenced by the full history of the inputs and the energy harvesting process. Furthermore, naturally, in such a channel, the energy information is observed causally at the transmitter. Both of these characteristics pose great challenges for the analysis of the channel capacity. In this paper, we use techniques developed for channels with side information and finite-state channels, to obtain lower and upper bounds on the capacity of energy harvesting channels. In particular, in a general case with Markov energy harvesting processes, we use stationarity and ergodicity theory to compute and optimize the achievable rates for the channels, and derive a series of computable capacity upper and lower bounds.

Given n discrete random variables, its entropy vector is the 2n- 1-dimensional vector obtained from the joint entropies of all non-empty subsets of the random variables. It is well known that there is a close relation between such an entropy vector and a certain group-characterizable vector obtained from a finite group and n of its subgroups; indeed, roughly speaking, knowing the region of all such group-characterizable vectors is equivalent to knowing the region of all entropy vectors. This correspondence may be useful for characterizing the space of entropic vectors and for designing network codes. If one restricts attention to abelian groups then not all entropy vectors can be obtained. This is an explanation for the fact shown by Dougherty et al. that linear network codes cannot achieve capacity in general network coding problems (since linear network codes come from abelian groups). All abelian groupcharacterizable vectors, and by fiat all entropy vectors generated by linear network codes, satisfy a linear inequality called the Ingleton inequality. General entropy vectors, however, do not necessarily have this property. It is, therefore, of interest to identify groups that violate the Ingleton inequality. In this paper, we study the problem of finding nonabelian finite groups that yield characterizable vectors, which violate the Ingleton inequality. Using a refined computer search, we find the symmetric group S5 to be the smallest group that violates the Ingleton inequality. Careful study of the structure of this group, and its subgroups, reveals that it belongs to the Ingleton-violating family PGL(2, q) with a prime power q ≥ 5, i.e., the projective group of 2 × 2 nonsingular matrices with entries in Fq. We further interpret this family of groups, and their subgroups, using the theory of group actions and identify the subgroups as certain stabilizers. We also extend the construction to more general groups such as PGL(n, q) and GL(n, q). The families of groups identified here are therefore good candidates for constructing network codes more powerful than linear network codes, and we discuss some considerations for constructing such group network codes.

Many problems in areas such as compressive sensing and coding theory seek to design a set of equal-norm vectors with large angular separation. This idea is essentially equivalent to constructing a frame with low coherence. The elements of such frames can in turn be used to build high-performance spherical codes, quantum measurement operators, and compressive sensing measurement matrices, to name a few applications. In this paper, we allude to the group-frame construction first described by Slepian and further explored in the works of Vale and Waldron. We present a method for selecting representations of a finite group to construct a group frame that achieves low coherence. Our technique produces a tight frame with a small number of distinct inner product values between the frame elements, in a sense approximating a Grassmannian frame. We identify special cases in which our construction yields some previously known frames with optimal coherence meeting the Welch lower bound, and other cases in which the entries of our frame vectors come from small alphabets. In particular, we apply our technique to the problem choosing a subset of rows of an Hadamard matrix so that the resulting columns form a low-coherence frame. Finally, we give an explicit calculation of the average coherence of our frames, and find regimes in which they satisfy the strong coherence property described by Mixon, Bajwa, and Calderbank.

In this paper, we propose a new approach to the design of training sequences that can be used for an accurate estimation of multi-input multi-output channels. The proposed method is particularly instrumental in training sequence designs that deal with three key challenges: 1) arbitrary channel and noise statistics that do not follow specific models, 2) limitations on the properties of the transmit signals, including total power, per-antenna power, having a constant-modulus, discrete-phase, or low peak-to-average-power ratio, and 3) signal design for large-scale or massive antenna arrays. Several numerical examples are provided to examine the proposed method.

Phaseless super-resolution is the problem of reconstructing a signal from its low-frequency Fourier magnitude measurements. It is the combination of two classic signal processing problems: phase retrieval and super-resolution. Due to the absence of phase and high-frequency measurements, additional information is required in order to be able to uniquely reconstruct the signal of interest. In this work, we use masks to introduce redundancy in the phaseless measurements. We develop an analysis framework for this setup, and use it to show that any super-resolution algorithm can be seamlessly extended to solve phaseless superresolution (up to a global phase), when measurements are obtained using a certain set of masks. In particular, we focus our attention on a robust semidefinite relaxation-based algorithm, and provide reconstruction guarantees. Numerical simulations complement our theoretical analysis.

We study the problem of recovering an n-dimensional BPSK signal from m linear noise-corrupted measurements using the box relaxation method which relaxes the discrete set {±1}n to the convex set [-1,1]n to obtain a convex optimization algorithm followed by hard thresholding. When the noise and measurement matrix have iid standard normal entries, we obtain an exact expression for the bit-wise probability of error Pe in the limit of n and m growing and m/n fixed. At high SNR our result shows that the Pe of box relaxation is within 3dB of the matched filter bound (MFB) for square systems, and that it approaches the (MFB) as m grows large compared to n. Our results also indicate that as m, n → ∞, for any fixed set of size k, the error events of the corresponding k bits in the box relaxation method are independent.

We consider the problem of constructing linear MDS error-correcting codes with generator matrices that are sparsest and balanced. In this context, sparsest means that every row has the least possible number of non-zero entries, and balanced means that every column contains the same number of non-zero entries. Codes with this structure minimize the maximal computation time of computing any code symbol, a property that is appealing to systems where computational load-balancing is critical. The problem was studied before by Dau et al. where it was shown that there always exists an MDS code over a sufficiently large field such that its generator matrix is both sparsest and balanced. However, the construction is not explicit and more importantly, the resulting MDS codes do not lend themselves to efficient error correction. With an eye towards explicit constructions with efficient decoding, we show in this paper that the generator matrix of a cyclic Reed-Solomon code of length n and dimension k can always be transformed to one that is both sparsest and balanced, for all parameters n and k where k/n (n - k + 1) is an integer.

We consider the problem of stabilizing an unstable plant driven by bounded noise over a digital noisy communication link, a scenario at the heart of networked control. To stabilize such a plant, one needs real-time encoding and decoding with an error probability profile that decays exponentially with the decoding delay. The works of Schulman and Sahai over the past two decades have developed the notions of tree codes and anytime capacity, and provided the theoretical framework for studying such problems. Nonetheless, there has been little practical progress in this area due to the absence of explicit constructions of tree codes with efficient encoding and decoding algorithms. Recently, linear time-invariant tree codes were proposed to achieve the desired result under maximum-likelihood decoding. In this work, we take one more step towards practicality, by showing that these codes can be efficiently decoded using sequential decoding algorithms, up to some loss in performance (and with some practical complexity caveats). We supplement our theoretical results with numerical simulations that demonstrate the effectiveness of the decoder in a control system setting.

Let X* be a n1× n2matrix with entries in F2and rank r1, n2) (often r ≪ min(n1, n2)). We consider the problem of reconstructing X* given only a subset of its entries. This problem has recently found numerous applications, most notably in network and index coding, where finding optimal linear codes (over some field Fq) can be reduced to finding the minimum rank completion of a matrix with a subset of revealed entries. The problem of matrix completion over reals also has many applications and in recent years several polynomial-time algorithms with provable recovery guarantees have been developed. However, to date, such algorithms do not exist in the finite-field case. We propose a linear algebraic algorithm, based on inferring low-weight relations among the rows and columns of X*, to attempt to complete X* given a random subset of its entries. We establish conditions on the row and column spaces of X* under which the algorithm runs in polynomial time (in the size of X*) and can successfully complete X* with high probability from a vanishing fraction of its entries. We then propose a linear programming-based extension of our basic algorithm, and evaluate it empirically.

We study the problem of clustering a set of data points based on their similarity matrix, each entry of which represents the similarity between the corresponding pair of points. We propose a convex-optimization-based algorithm for clustering using the similarity matrix, which has provable recovery guarantees. It needs no prior knowledge of the number of clusters and it behaves in a robust way in the presence of outliers and noise. Using a generative stochastic model for the similarity matrix (which can be thought of as a generalization of the classical Stochastic Block Model) we obtain precise bounds (not orderwise) on the sizes of the clusters, the number of outliers, the noise variance, separation between the mean similarities inside and outside the clusters and the values of the regularization parameter that guarantee the exact recovery of the clusters with high probability. The theoretical findings are corroborated with extensive evidence from simulations.

A recent line of work has established accurate predictions of the mean squared-error (MSE) performance of non-smooth convex optimization methods when used to recover structured signals (e.g. sparse, low-rank) from noisy linear (and possibly compressed) observations. Specifically, in a recent paper [15] we precisely characterized the MSE performance of a general class of regularized M-estimators using a framework that is based on Gaussian process methods. Here, we extend the framework to the analysis of a general class of Lipschitz performance metrics, which in addition to the standard MSE, includes the ℓ1-reconstruction error, the probability of successfully identifying whether an element belongs to the support of a sparse signal, the empirical distribution of the error, etc. For concreteness, we primarily focus on the problem of sparse recovery under ℓ1-regularized least-squares (aka LASSO). We illustrate the validity of the theoretical predictions through numerical simulations and discuss the importance of their precise nature in optimally tuning the involved parameters of the reconstruction method.

We construct balanced and sparsest generator matrices for cyclic Reed-Solomon codes with any length n and dimension k. By sparsest, we mean that each row has the least possible number of nonzeros, while balanced means that the number of nonzeros in any two columns differs by at most one. Codes allowing such encoding schemes are useful in distributed settings where computational load-balancing is critical. The problem was first studied by Dau et al. who showed, using probabilistic arguments, that there always exists an MDS code over a sufficiently large field such that its generator matrix is both sparsest and balanced. Motivated by the need for an explicit construction with efficient decoding, the authors of the current paper showed that the generator matrix of a cyclic Reed-Solomon code of length n and dimension k can always be transformed to one that is both sparsest and balanced, when n and k are such that k/n (n-k+1) is an integer. In this paper, we lift this condition and construct balanced and sparsest generator matrices for cyclic Reed-Solomon codes for any set of parameters.

Digital crowdsourcing (CS) is a modern approach to perform certain large projects using small contributions of a large crowd. In CS, a taskmaster typically breaks down the project into small batches of tasks and assigns them to so-called workers with imperfect skill levels. The crowdsourcer then collects and analyzes the results for inference and serving the purpose of the project. In this work, the CS problem, as a human-in-the-loop computation problem, is modeled and analyzed in an information theoretic rate-distortion framework. The purpose is to identify the ultimate fidelity that one can achieve by any form of query from the crowd and any decoding (inference) algorithm with a given budget. The results are established by a joint source channel (de)coding scheme, which represent the query scheme and inference, over parallel noisy channels, which model workers with imperfect skill levels. We also present and analyze a query scheme dubbed k-ary incidence coding and study optimized query pricing in this setting.

We consider the task of clustering items using answers from non-expert crowd workers. In such cases, the workers are often not able to label the items directly, however, it is reasonable to assume that they can compare items and judge whether they are similar or not. An important question is what queries to make, and we compare two types: random edge queries, where a pair of items is revealed, and random triangles, where a triple is. Since it is far too expensive to query all possible edges and/or triangles, we need to work with partial observations subject to a fixed query budget constraint. When a generative model for the data is available (and we consider a few of these) we determine the cost of a query by its entropy; when such models do not exist we use the average response time per query of the workers as a surrogate for the cost. In addition to theoretical justification, through several simulations and experiments on two real data sets on Amazon Mechanical Turk, we empirically demonstrate that, for a fixed budget, triangle queries uniformly outperform edge queries. Even though, in contrast to edge queries, triangle queries reveal dependent edges, they provide more reliable edges and, for a fixed budget, many more of them. We also provide a sufficient condition on the number of observations, edge densities inside and outside the clusters and the minimum cluster size required for the exact recovery of the true adjacency matrix via triangle queries using a convex optimization-based clustering algorithm.

In this work, we propose a unified approach to evaluating the CDF and PDF of indefinite quadratic forms in Gaussian random variables. Such a quantity appears in many applications in communications, signal processing, information theory, and adaptive filtering. For example, this quantity appears in the mean-square-error (MSE) analysis of the normalized least-mean-square (NLMS) adaptive algorithm, and SINR associated with each beam in beam forming applications. The trick of the proposed approach is to replace inequalities that appear in the CDF calculation with unit step functions and to use complex integral representation of the the unit step function. Complex integration allows us then to evaluate the CDF in closed form for the zero mean case and as a single dimensional integral for the non-zero mean case. Utilizing the saddle point technique allows us to closely approximate such integrals in non zero mean case. We demonstrate how our approach can be extended to other scenarios such as the joint distribution of quadratic forms and ratios of such forms, and to characterize quadratic forms in isotropic distributed random variables. We also evaluate the outage probability in multiuser beamforming using our approach to provide an application of indefinite forms in communications.

Non-smooth regularized convex optimization procedures have emerged as a powerful tool to recover structured signals (sparse, low-rank, etc.) from (possibly compressed) noisy linear measurements. We focus on the problem of linear regression and consider a general class of optimization methods that minimize a loss function measuring the misfit of the model to the observations with an added structured-inducing regularization term. Celebrated instances include the LASSO, Group-LASSO, Least-Absolute Deviations method, etc.. We develop a quite general framework for how to determine precise prediction performance guaranties (e.g. mean-square-error) of such methods for the case of Gaussian measurement ensemble. The machinery builds upon Gordon’s Gaussian min-max theorem under additional convexity assumptions that arise in many practical applications. This theorem associates with a primary optimization (PO) problem a simplified auxiliary optimization (AO) problem from which we can tightly infer properties of the original (PO), such as the optimal cost, the norm of the optimal solution, etc. Our theory applies to general loss functions and regularization and provides guidelines on how to optimally tune the regularizer coefficient when certain structural properties (such as sparsity level, rank, etc.) are known.

The problem of recovering signals from the Short-Time Fourier Transform (STFT) magnitude is of paramount importance in many areas of engineering and physics. This problem has received a lot of attention over the last few decades, but not much is known about conditions under which the STFT magnitude is a unique signal representation. Also, the recovery techniques proposed by researchers are mostly heuristic in nature. In this work, we first show that almost all signals can be uniquely identified by their STFT magnitude under mild conditions. Then, we consider a semidefinite relaxation-based algorithm and provide the first theoretical guarantees for the same. Numerical simulations complement our theoretical analysis and provide many directions for future work.

We consider ill-posed linear inverse problems involving the estimation of structured sparse signals. When the sensing matrix has i.i.d. standard normal entries, there is a full-fledged theory on the sample complexity and robustness properties. In this work, we propose a way of making use of this theory to get good bounds for the i.i.d. Bernoulli ensemble. We first provide a deterministic relation between the two ensembles that relates the restricted singular values. Then, we show how one can get non-asymptotic results with small constants for the Bernoulli ensemble. While our discussion focuses on Bernoulli measurements, the main idea can be extended to any discrete distribution with little difficulty.

Atomic norm denoising has been recently introduced as a generalization of the Least Absolute Shrinkage and Selection Operator (LASSO) to overcome the problem of off-grid parameters. The method has been found to possess many interesting theoretical properties. However, its implementation has been only discussed in a special case of spectral line estimation by uniform sampling. In this paper, we propose a general numerical method to solve the atomic norm denoising problem. The complexity of the proposed algorithm is proportional to the complexity of a single-parameter search in the parameter space and thus in many interesting cases, including frequency estimation it enjoys fast realization.

A classical problem that arises in numerous signal processing applications asks for the reconstruction of an unknown, k-sparse signal x0∈ ℝnfrom underdetermined, noisy, linear measurements y = Ax0+ z ∈ ℝm. One standard approach is to solve the following convex program x̂ = arg minx∥y - Ax∥2+λ∥x∥1, which is known as the ℓ2-LASSO. We assume that the entries of the sensing matrix A and of the noise vector z are i.i.d Gaussian with variances 1/m and σ2. In the large system limit when the problem dimensions grow to infinity, but in constant rates, we precisely characterize the limiting behavior of the normalized squared error ∥x̂ - x0∥22/σ2. Our numerical illustrations validate our theoretical predictions.

We examine an error-correcting coding framework in which each coded symbol is constrained to be a function of a fixed subset of the message symbols. With an eye toward distributed storage applications, we seek to design systematic codes with good minimum distance that can be decoded efficiently. On this note, we provide theoretical bounds on the minimum distance of such a code based on the coded symbol constraints. We refine these bounds in the case where we demand a systematic linear code. Finally, we provide conditions under which each of these bounds can be achieved by choosing our code to be a subcode of a Reed-Solomon code, allowing for efficient decoding. This problem has been considered in multisource multicast network error correction. The problem setup is also reminiscent of locally repairable codes.

Signal recovery from the magnitude of the Fourier transform, or equivalently, from the autocorrelation, is a classical problem known as phase retrieval. Due to the absence of phase information, some form of additional information is required in order to be able to uniquely identify the underlying signal. In this work, we consider the problem of phase retrieval using masks. Due to our interest in developing robust algorithms with theoretical guarantees, we explore a convex optimization-based framework. In this work, we show that two specific masks (each mask provides 2n Fourier magnitude measurements) or five specific masks (each mask provides n Fourier magnitude measurements) are sufficient for a convex relaxation of the phase retrieval problem to provably recover almost all signals (up to global phase). We also show that the recovery is stable in the presence of measurement noise. This is a significant improvement over the existing results, which require O(log2n) random masks (each mask provides n Fourier magnitude measurements) in order to guarantee unique recovery (up to global phase). Numerical experiments complement our theoretical analysis and show interesting trends, which we hope to explain in a future publication.

We study two channels with causal CSIT: a finite state channel with input constraints and a finite-battery energy harvesting channel, considered in [1] and for the latter [2]-[5]. The capacity of these channels remains open and the calculation of the upper bounds often has a complexity double exponential in the block size N. In this paper we obtain an alternative upper bound which has a complexity linear in N. While, for any N, this bound is looser than the bound in [1], since it can be readily computed for very large values of N, it leads to numerically tighter bounds in many cases. Furthermore, for the energy harvesting channel we calculate the pairwise error probabilities of the ML decoder, which provides a useful guideline for the code design.

As a widely used tool in tackling general quadratic optimization problems, semidefinite relaxation (SDR) promises both a polynomial-time complexity and an a priori known sub-optimality guarantee for its approximate solutions. While attempts at improving the guarantees of SDR in a general sense have proven largely unsuccessful, it has been widely observed that the quality of solutions obtained by SDR is usually considerably better than the provided guarantees. In this paper, we propose a novel methodology that paves the way for obtaining improved data-dependent guarantees in a computational way. The derivations are dedicated to a specific quadratic optimization problem (called m-QP) which lies at the core of many communication and active sensing schemes; however, the ideas may be generalized to other quadratic optimization problems. The new guarantees are particularly useful in accuracy sensitive applications, including decision-making scenarios.

Recently, the precise performance of the Generalized LASSO algorithm for recovering structured signals from compressed noisy measurements, obtained via i.i.d. Gaussian matrices, has been characterized. The analysis is based on a framework introduced by Stojnic and heavily relies on the use of Gordon's Gaussian min-max theorem (GMT), a comparison principle on Gaussian processes. As a result, corresponding characterizations for other ensembles of measurement matrices have not been developed. In this work, we analyze the corresponding performance of the ensemble of isotropically random orthogonal (i.r.o.) measurements. We consider the constrained version of the Generalized LASSO and derive a sharp characterization of its normalized squared error in the large-system limit. When compared to its Gaussian counterpart, our result analytically confirms the superiority in performance of the i.r.o. ensemble. Our second result, derives an asymptotic lower bound on the minimum conic singular values of i.r.o. matrices. This bound is larger than the corresponding bound on Gaussian matrices. To prove our results we express i.r.o. matrices in terms of Gaussians and show that, with some modifications, the GMT framework is still applicable.

Given an unknown signal x0∈ Rnand linear noisy measurements y = Ax0+ σv ∈ Rm, the generalized ℓ22-LASSO solves x̂ := arg minx1/2∥y-Ax ∥22+ σλf(x). Here, f is a convex regularization function (e.g. ℓ1-norm, nuclearnorm) aiming to promote the structure of x0(e.g. sparse, lowrank), and, λ ≥ 0 is the regularizer parameter. A related optimization problem, though not as popular or well-known, is often referred to as the generalized ℓ2-LASSO and takes the form x̂̂̂ := arg minx∥y-Ax∥2+λf(x), and has been analyzed by Oymak, Thrampoulidis and Hassibi. Oymak et al. further made conjectures about the performance of the generalized ℓ22-LASSO. This paper establishes these conjectures rigorously. We measure performance with the normalized squared error NSE(σ) := ∥x-x0∥22/(mσ2). Assuming the entries of A are i.i.d. Gaussian N (0,1/m) and those of v are i.i.d. N(0,1), we precisely characterize the “asymptotic NSE” aNSE := limσ→0NSE(σ) when the problem dimensions tend to infinity in a proportional manner. The role of λ, f and x0is explicitly captured in the derived expression via means of a single geometric quantity, the Gaussian distance to the subdifferential. We conjecture that aNSE = supσ>0NSE(σ). We include detailed discussions on the interpretation of our result, make connections to relevant literature and perform computational experiments that validate our theoretical findings.

Consider estimating an unknown, but structured (e.g. sparse, low-rank, etc.), signal $x_0\in R^n$ from a vector $y\in R^m$ of measurements of the form $y_i=g_i(a_i^Tx_0)$, where the $a_i$'s are the rows of a known measurement matrix $A$, and, $g$ is a (potentially unknown) nonlinear and random link-function. Such measurement functions could arise in applications where the measurement device has nonlinearities and uncertainties. It could also arise by design, e.g., $g_i(x)=sign(x+z_i)$, corresponds to noisy 1-bit quantized measurements. Motivated by the classical work of Brillinger, and more recent work of Plan and Vershynin, we estimate $x_0$ via solving the Generalized-LASSO, i.e., $\hat x=\arg\min_{x}\|y-Ax_0\|_2+\lambda f(x)$ for some regularization parameter $\lambda >0$ and some (typically non-smooth) convex regularizer $f$ that promotes the structure of $x_0$, e.g. $\ell_1$-norm, nuclear-norm. While this approach seems to naively ignore the nonlinear function $g$, both Brillinger and Plan and Vershynin have shown that, when the entries of $A$ are iid standard normal, this is a good estimator of $x_0$ up to a constant of proportionality $\mu$, which only depends on $g$. In this work, we considerably strengthen these results by obtaining explicit expressions for $\|\hat x-\mu x_0\|_2$, for the regularized Generalized-LASSO, that are asymptotically precise when $m$ and $n$ grow large. A main result is that the estimation performance of the Generalized LASSO with non-linear measurements is asymptotically the same as one whose measurements are linear $y_i=\mu a_i^Tx_0+\sigma z_i$, with $\mu=E[\gamma g(\gamma)]$ and $\sigma^2=E[(g(\gamma)-\mu\gamma)^2]$, and, $\gamma$ standard normal. The derived expressions on the estimation performance are the first-known precise results in this context. One interesting consequence of our result is that the optimal quantizer of the measurements that minimizes the estimation error of the LASSO is the celebrated Lloyd-Max quantizer.

A wiretap channel is a communication channel between a transmitter Alice and a legitimate receiver Bob, in the presence of an eavesdropper Eve. The goal of communication is to achieve reliability between Alice and Bob, but also confidentiality despite Eve's presence. Wiretap channels are declined in all kinds of flavors, depending on the underlying channels used by the three players: discrete memoryless channels, additive Gaussian noise channels, or fading channels, to name a few. In this survey, we focus on the case where the three players use multiple-antenna channels with Gaussian noise to communicate. After summarizing known results for multiple-input-multiple-output (MIMO) channels, both in terms of achievable reliable data rate (capacity) and code design, we introduce the MIMO wiretap channel. We then state the MIMO wiretap capacity, summarize the idea of the proof(s) behind this result, and comment on the insights given by the proofs on the physical meaning of the secrecy capacity. We finally discuss design criteria for MIMO wiretap codes.

It is well known that ℓ1minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. Exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from independent identically distributed (i.i.d.) Gaussian measurements, have been computed and are referred to as weak thresholds. In this paper, we introduce a reweighted ℓ1recovery algorithm composed of two steps: 1) a standard ℓ1minimization step to identify a set of entries where the signal is likely to reside and 2) a weighted ℓ1minimization step where entries outside this set are penalized. For signals where the nonsparse component entries are independent and identically drawn from certain classes of distributions, (including most well-known continuous distributions), we prove a strict improvement in the weak recovery threshold. Our analysis suggests that the level of improvement in the weak threshold depends on the behavior of the distribution at the origin. Numerical simulations verify the distribution dependence of the threshold improvement very well, and suggest that in the case of i.i.d. Gaussian nonzero entries, the improvement can be quite impressive-over 20% in the example we consider.

Recovering structured models (e.g., sparse or group-sparse vectors, low-rank matrices) given a few linear observations have been well-studied recently. In various applications in signal processing and machine learning, the model of interest is structured in several ways, for example, a matrix that is simultaneously sparse and low rank. Often norms that promote the individual structures are known, and allow for recovery using an order-wise optimal number of measurements (e.g., 11 norm for sparsity, nuclear norm for matrix rank). Hence, it is reasonable to minimize a combination of such norms. We show that, surprisingly, using multiobjective optimization with these norms can do no better, orderwise, than exploiting only one of the structures, thus revealing a fundamental limitation in sample complexity. This result suggests that to fully exploit the multiple structures, we need an entirely new convex relaxation. Further, specializing our results to the case of sparse and low-rank matrices, we show that a nonconvex formulation recovers the model from very few measurements (on the order of the degrees of freedom), whereas the convex problem combining the 11 and nuclear norms requires many more measurements, illustrating a gap between the performance of the convex and nonconvex recovery problems. Our framework applies to arbitrary structure-inducing norms as well as to a wide range of measurement ensembles. This allows us to give sample complexity bounds for problems such as sparse phase retrieval and low-rank tensor completion.

We explore the problem of deterministically constructing frames and matrices with low coherence, which arises in areas such as compressive sensing, spherical codes, and MIMO communications. In particular, we present a generalization of the familiar harmonic frame by selecting a subset of rows of the generalized discrete Fourier transform matrix over finite groups. We apply our methods to the group SL2(Fq) and show how to produce frames with remarkably low coherence, for which we provide upper bounds.

The problem of finding clusters in a graph arises in several applications such as social networks, data mining and computer networks. A typical, convex optimization-approach, that is often adopted is to identify a sparse plus low-rank decomposition of the adjacency matrix of the graph, with the (dense) low-rank component representing the clusters. In this paper, we sharply characterize the conditions for successfully identifying clusters using this approach. In particular, we introduce the “effective density” of a cluster that measures its significance and we find explicit upper and lower bounds on the minimum effective density that demarcates regions of success or failure of this technique. Our conditions are in terms of (a) the size of the clusters, (b) the denseness of the graph, and (c) regularization parameter of the convex program. We also present extensive simulations that corroborate our theoretical findings.

We investigate the random matrices that have orthonormal rows and provide a comparison to matrices with independent Gaussian entries. We find that, orthonormality provides an inherent advantage for the conditioning. In particular, for any given subset S of ℝn, we show that orthonormal matrices have better restricted eigenvalues compared to Gaussians. We consider implications of this result for the linear inverse problems; in particular, we investigate the noisy sparse estimation setup and applications to restricted isometry property. We relate our findings to the results known for Gaussian processes and precise undersampling theorems. We then discuss and illustrate universality of the noise robustness behavior for partial unitary matrices including Hadamard and Discrete Cosine Transform.

Consider estimating a structured signal x0from linear, underdetermined and noisy measurements y = Ax0+z, via solving a variant of the lasso algorithm: x̂ = arg minx{∥y-Ax∥2+λf(x)}. Here, f is a convex function aiming to promote the structure of x0, say ℓ1-norm to promote sparsity or nuclear norm to promote low-rankness. We assume that the entries of A are independent and normally distributed and make no assumptions on the noise vector z, other than it being independent of A. Under this generic setup, we derive a general, non-asymptotic and rather tight upper bound on the ℓ2-norm of the estimation error ∥x̂ - x0∥2. Our bound is geometric in nature and obeys a simple formula; the roles of λ, f and x0are all captured by a single summary parameter δ(λ∂f(x0)), termed the Gaussian squared distance to the scaled subdifferential. We connect our result to the literature and verify its validity through simulations.

In this paper, a general algorithm is proposed for rate analysis and code design of linear index coding problems. Specifically a solution for minimum rank matrix completion problem over finite fields representing the linear index coding problem is devised in order to find the optimum transmission rate given vector length and size of the field. The new approach can be applied to both scalar and vector linear index coding.

We study two types of channels in this paper: certain channels with states and energy harvesting channels. The first is based on Gallager's finite state channel with input constraints and causal CSIT. The second deals with two different scenarios with regard to the availability of energy information at the transmitter. For both channels we derive new capacity bounds, mostly using bounding techniques of Verdú and Han and Gallager.

Given a set of integers, one can easily construct the set of their pairwise distances. We consider the inverse problem: given a set of pairwise distances, find the integer set which realizes the pairwise distance set. This problem arises in a lot of fields in engineering and applied physics, and has confounded researchers for over 60 years. It is one of the few fundamental problems that are neither known to be NP-hard nor solvable by polynomial-time algorithms. Whether unique recovery is possible also remains an open question. In many practical applications where this problem occurs, the integer set is naturally sparse (i.e., the integers are sufficiently spaced), a property which has not been explored. In this work, we exploit the sparse nature of the integer set and develop a polynomial-time algorithm which provably recovers the set of integers (up to linear shift and reversal) from the set of their pairwise distances with arbitrarily high probability if the sparsity is O(n1/2-ε). Numerical simulations verify the effectiveness of the proposed algorithm.

The problem of designing low coherence matrices and low-correlation frames arises in a variety of fields, including compressed sensing, MIMO communications and quantum measurements. The challenge is that one must control the (n over 2) pairwise inner products of the columns of the matrix. In this paper, we follow the group code approach of David Slepian [1], which constructs frames using unitary group representations and which in general reduces the number of distinct inner products to n-1. We examine representations of cyclic groups as well as generalized dihedral groups, and we expand upon previous results which bound the coherence of the resulting frames.

We consider the problem of recovering signals from their power spectral densities. This is a classical problem referred to in literature as the phase retrieval problem, and is of paramount importance in many fields of applied sciences. In general, additional prior information about the signal is required to guarantee unique recovery as the mapping from signals to power spectral densities is not one-to-one. In this work, we assume that the underlying signals are sparse. Recently, semidefinite programming (SDP) based approaches were explored by various researchers. Simulations of these algorithms strongly suggest that signals upto O(n1/2- ϵ) sparsity can be recovered by this technique. In this work, we develop a tractable algorithm based on reweighted ℓ1-minimization that recovers a sparse signal from its power spectral density for significantly higher sparsities, which is unprecedented. We also discuss the limitations of the existing SDP algorithms and provide a combinatorial algorithm which requires significantly fewer ”phaseless” measurements to guarantee recovery.

We consider the problem of determining the capacity of an energy-harvesting transmitter with finite battery communicating over a discrete memoryless channel. When the battery is unlimited, or zero, the capacity has been determined, but it remains unknown for a finite non-zero battery. In this paper we assume that the harvested energy at each time, the total battery storage, and the transmitter signal energy at each time can be quantized to the same unit (i.e., the same energy interval). Under this assumption, we show that the capacity can be described using the Verdú-Han general framework. If we further assume that the transmitted symbol at each time depends only on the energy currently available, and not on the entire past history of energy harvests and symbols transmitted, then we show that the system reduces to a finite state channel (FSC) with the required ergodic and Markov properties so that lower bounds on the capacity can be readily numerically computed. We conjecture that our numerical bounds are tight. Our numerical results indicate that even the minimal possible battery storage can reap a significant fraction of the infinite battery capacity.

Designing low coherence matrices and low-correlation frames is a point of interest in many fields including compressed sensing, MIMO communications and quantum measurements. The challenge is that one must control the (n2) pairwise inner products between the frame elements. In this paper, we exploit the group code approach of David Slepian [1], which constructs frames using unitary group representations and which in general reduces the number of distinct inner products to n - 1. We demonstrate how to efficiently find optimal representations of cyclic groups, and we show how basic abelian groups can be used to construct tight frames that have the same dimensions and inner products as those arising from certain more complex nonabelian groups. We support our work with theoretical bounds and simulations.

Signal recovery from the amplitudes of the Fourier transform, or equivalently from the autocorrelation function is a classical problem. Due to the absence of phase information, signal recovery requires some form of additional prior information. In this paper, the prior information we assume is sparsity. We develop a convex optimization based framework to retrieve the signal support from the support of the autocorrelation, and propose an iterative algorithm which terminates in a signal with the least sparsity satisfying the autocorrelation constraints. Numerical results suggest that unique recovery up to a global sign change, time shift and/or time reversal is possible with a very high probability for sufficiently sparse signals.

We propose a new algorithm to recover a sparse signal from a system of linear measurements. By projecting the measured signal onto a properly chosen subspace, we can use the projection to zero in on a low-sparsity portion of our original signal, which we can recover using ℓ1-minimization. We can then recover the remaining portion of our signal from an overdetermined system of linear equations. We prove that our scheme improves the threshold of ℓ1-minimization, and we derive an upper bound for this new threshold. We support our theoretical results with numerical simulations which demonstrate that certain classes of signals come close to achieving this upper bound.

In this paper, we analyze the performance of weighted ℓ1minimization over a non-uniform sparse signal model by extending the “Gaussian width” analysis proposed in [1]. Our results are consistent with those of [7] which are currently the best known ones. However, our methods are less computationally intensive and can be easily extended to signals which have more than two sparsity classes. Finally, we also provide a heuristic for estimating the optimal weights, building on a more general model presented in [11]. Our results reinforce the fact that weighted ℓ1minimization is substantially better than regular ℓ1minimization and provide an easy way to calculate the optimal weights.

This paper presents a relaxation of an assumption usually imposed in the recovery of sparse vectors with random support in pairs of orthonormal bases or incoherent dictionaries by basis pursuit. The assumption requires the phases of the entries of the sparse vector to be chosen randomly in [0, 2π). This paper provides probabilistic recovery guarantees for deterministic phases. We prove that, if a phase pattern is fixed, then a sparse vector with random support and corresponding phases can be recovered with high probability. As a result, the phases can take any distribution and can be dependent, as long as they are independent of the support. Furthermore, this improvement does not come at the expense of the maximum recoverable sparsity.

Advances in compressed-sensing (CS) have sparked interest in designing information acquisition systems that process data at close to the information rate. Initial proposals for CS signal acquisition systems utilized random matrix ensembles in conjunction with convex relaxation based signal reconstruction algorithms. While providing universal performance bounds, random matrix based formulations present several practical problems due to: the difficulty in physically implementing key mathematical operations, and their dense representation. In this paper, we present a CS architecture which is based on a sub-linear time recovery algorithm (with minimum memory requirement) that exploits a novel structured matrix. This formulation allows the use of a reconstruction algorithm based on relatively simple computational primitives making it more amenable to implementation in a fully-integrated form. Theoretical recovery guarantees are discussed and a hypothetical physical CS decoder is described.

The problem of signal recovery from the autocorrelation, or equivalently, the magnitudes of the Fourier transform, is of paramount importance in various fields of engineering. In this work, for one-dimensional signals, we give conditions, which when satisfied, allow unique recovery from the autocorrelation with very high probability. In particular, for sparse signals, we develop two non-iterative recovery algorithms. One of them is based on combinatorial analysis, which we prove can recover signals up to sparsity o(n1/3) with very high probability, and the other is developed using a convex optimization based framework, which numerical simulations suggest can recover signals upto sparsity o(n1/2) with very high probability.

We consider the problem of recovering a sparse signal from underdetermined measurements when we have prior information about the sparsity structure of the signal. In particular, we assume that the entries of the signal can be partitioned into two known sets S1, S2 where the relative sparsities over the two sets are different. In this situation it is advantageous to replace classical ℓ1minimization with weighted ℓ1minimization, where the sparser set is given a larger weight. In this paper we give a simple closed form expression for the minimum number of measurements required for successful recovery when the optimal weights are chosen. The formula shows that the number of measurements is upper bounded by the sum of the minimum number of measurements needed had we measured the S1and S2components of the signal separately. In fact, our results indicate that this upper bound is tight and we actually have equality. Our proof technique uses the “escape through a mesh” framework and connects to the Minimax MSE of a certain basis pursuit denisoing problem.

We introduce a novel algorithm for decoding binary linear codes by linear programming (LP). We build on the LP decoding algorithm of Feldman and introduce a postprocessing step that solves a second linear program that reweights the objective function based on the outcome of the original LP decoder output. Our analysis shows that for some LDPC ensembles we can improve the provable threshold guarantees compared to standard LP decoding. We also show significant empirical performance gains for the reweighted LP decoding algorithm with very small additional computational complexity.

The capacity region of multi-pair bidirectional relay networks, in which a relay node facilitates the communication between multiple pairs of users, is studied. This problem is first examined in the context of the linear shift deterministic channel model. The capacity region of this network when the relay is operating at either full-duplex mode or half-duplex mode for arbitrary number of pairs is characterized. It is shown that the cut-set upper-bound is tight and the capacity region is achieved by a so called divide-and-conquer relaying strategy. The insights gained from the deterministic network are then used for the Gaussian bidirectional relay network. The strategy in the deterministic channel translates to a specific superposition of lattice codes and random Gaussian codes at the source nodes and successive interference cancelation at the receiving nodes for the Gaussian network. The achievable rate of this scheme with two pairs is analyzed and it is shown that for all channel gains it achieves to within 3 bits/sec/Hz per user of the cut-set upper-bound. Hence, the capacity region of the two-pair bidirectional Gaussian relay network to within 3 bits/sec/Hz per user is characterized.

We consider the problem of network tomography in probabilistic tree mixture models. We invoke the theory of compressed sensing and prove that the distribution of a random communication network model with n nodes represented by a probabilistic mixture of k trees can be identified using low order routing summaries pertinent to groups of small sizes dlog k), then certain classes of inference algorithms can successfully determine the unknown model, i.e. the topologies of mixing trees and their corresponding probabilities. We show that a variation of ℓ1minimization over the space of all possible trees of n nodes can be used for this purpose. In addition, we propose a novel inference algorithm with a complexity polynomial in nlog k, with the same provable guarantee. The proposed model is applicable to practical situations such as ad-hoc and Peer-to-Peer(P2P) networks, and the presented inference method can lead to distributed protocols for network monitoring and tomography. In particular, we provide preliminary insight and numerical results on how the ideas are amenable to wireless sensor networks.

We present an alternative analysis of weighted ℓ1minimization for sparse signals with a nonuniform sparsity model, and extend our results to nuclear norm minimization for matrices with nonuniform singular vector distribution. In the case of vectors, we find explicit upper bounds for the successful recovery thresholds, and give a simple suboptimal weighting rule. For matrices, the thresholds we find are only implicit, and the optimal weight selection requires an exhaustive search. For the special case of very wide matrices, the relationship is made explicit and the optimal weight assignment is the same as the vector case. We demonstrate through simulations that for vectors, the suggested weighting scheme improves the recovery performance over that of regular ℓ1minimization.

Nuclear norm minimization (NNM) has recently gained attention for its use in rank minimization problems. In this paper, we define weak, sectional and strong recovery for NNM to succeed at finding the low rank solution. We find tight conditions for these and analyze them for the case where the linear measurement operator consists of i.i.d. Gaussian entries. Finally we calculate the so called weak, sectional and strong thresholds for the success of nuclear norm minimization. To obtain our results, we generalize the notion of sign and support from sparse vectors to low rank matrices, and achieve a weak threshold which is much closer to the empirical phase transition curve of nuclear norm minimization than the existing bounds available in the literature.

We show that girth can be used to certify that sparse compressed sensing matrices have good sparse approximation guarantees. This allows us to present the first deterministic measurement matrix constructions that have an optimal number of measurements for ℓ1/ℓ1approximation. Our techniques are coding theoretic and rely on a recent connection of compressed sensing to LP relaxations for channel decoding.

We introduce a new class of measurement matrices for compressed sensing, using low order summaries over binary sequences of a given length. We prove recovery guarantees for three reconstruction algorithms using the proposed measurements, including l1minimization and two combinatorial methods. In particular, one of the algorithms recovers k-sparse vectors of length N in sublinear time poly(k log N), and requires at most O(k log N log log N) measurements. The empirical oversampling constant of the algorithm is significantly better than existing sublinear recovery algorithms such as Chaining Pursuit and Sudocodes. In particular, for 103≤ N ≤ 1012and k = 100, the oversampling factor is between 5 to 25. We provide preliminary insight into how the proposed constructions, and the fast recovery scheme can be used in a number of practical applications such as market basket analysis, and real time compressed sensing implementation.

Nuclear norm minimization (NNM) has recently gained significant attention for its use in rank minimization problems. Using null space characterizations, recovery thresholds for NNM have been previously studied for the case of Gaussian measurements as matrix dimensions tend to infinity. However simulations show that the thresholds are far from optimal, especially in the low rank region. In this paper we apply the recent analysis of Stojnic for ℓ1-minimization to the null space conditions of NNM. The results are significantly better and in particular our weak threshold appears to match with simulation results. Further, our closed form bounds suggest for any rank growing linearly with matrix size n one needs only three times of oversampling (the model complexity) for weak recovery and eight times for strong recovery. Additionally, the results for robustness analysis are given which indicate with slightly more measurements recovery guarantees for approximately low rank matrices can be given.

Matrix rank minimization (RM) problems recently gained extensive attention due to numerous applications in machine learning, system identification and graphical models. In RM problem, one aims to find the matrix with the lowest rank that satisfies a set of linear constraints. The existing algorithms include nuclear norm minimization (NNM) and singular value thresholding. Thus far, most of the attention has been on i.i.d. Gaussian or Bernoulli measurement operators. In this work, we introduce a new class of measurement operators, and a novel recovery algorithm, which is notably faster than NNM. The proposed operators are based on what we refer to as subspace expanders, which are inspired by the well known expander graphs based measurement matrices in compressed sensing. We show that given an n×n PSD matrix of rank r, it can be uniquely recovered from a minimal sampling of O(nr) measurements using the proposed structures, and the recovery algorithm can be cast as matrix inversion after a few initial processing steps.

Recovering sparse vectors and low-rank matrices from noisy linear measurements has been the focus of much recent research. Various reconstruction algorithms have been studied, including ℓ1and nuclear norm minimization as well as ℓpminimization with p <; 1. These algorithms are known to succeed if certain conditions on the measurement map are satisfied. Proofs for the recovery of matrices have so far been much more involved than in the vector case. In this paper, we show how several classes of recovery conditions can be extended from vectors to matrices in a simple and transparent way, leading to the best known restricted isometry and nullspace conditions for matrix recovery. Our results rely on the ability to “vectorize” matrices through the use of a key singular value inequality.

We consider rate R = k/n causal linear codes that map a sequence of k-dimensional binary vectors {bt}t=0∞to a sequence of n-dimensional binary vectors {ct}t=0∞, such that each ctis a function of {bτ}τ=0t. Such a code is called anytime reliable, for a particular binary-input memoryless channel, if at each time instant t, and for all delays d ≥ do, the probability of error P(b̂t-d/t≠bt-d) decays exponentially in d, i.e., P(b̂t-d/t≠bt-d) ≤ η2-βnd, for some β >; 0. Anytime reliable codes are useful in interactive communication problems and, in particular, can be used to stabilize unstable plants across noisy channels. Schulman proved the existence of such codes which, due to their structure, he called tree codes in [1]; however, to date, no explicit constructions and tractable decoding algorithms have been devised. In this paper, we show the existence of anytime reliable “linear” codes with “high probability”, i.e., suitably chosen random linear causal codes are anytime reliable with high probability. The key is to consider time-invariant codes (i.e., ones with Toeplitz generator and parity check matrices) which obviates the need to union bound over all times. For the binary erasure channel we give a simple ML decoding algorithm whose average complexity is constant per time instant and for which the probability that complexity at a given time t exceeds KC3decays exponentially in C. We show the efficacy of the method by simulating the stabilization of an unstable plant across a BEC, and remark on the tradeoffs between the utilization of the communication resources and the control performance.

We consider the MIMO wiretap channel, that is a MIMO broadcast channel where the transmitter sends some confidential information to one user which is a legitimate receiver, while the other user is an eavesdropper. Perfect secrecy is achieved when the transmitter and the legitimate receiver can communicate at some positive rate, while insuring that the eavesdropper gets zero bits of information. In this paper, we compute the perfect secrecy capacity of the multiple antenna MIMO broadcast channel, where the number of antennas is arbitrary for both the transmitter and the two receivers. Our technique involves a careful study of a Sato-like upper bound via the solution of a certain algebraic Riccati equation.

ℓ1minimization is often used for recovering sparse signals from an under-determined linear system. In this paper, we focus on finding sharp performance bounds on recovering approximately sparse signals using ℓ1minimization under noisy measurements. While the restricted isometry property is powerful for the analysis of recovering approximately sparse signals with noisy measurements, the known bounds on the achievable sparsity1 level can be quite loose. The neighborly polytope analysis which yields sharp bounds for perfectly sparse signals cannot be readily generalized to approximately sparse signals. We start from analyzing a necessary and sufficient condition, the “balancedness” property of linear subspaces, for achieving a certain signal recovery accuracy. Then we give a unified null space Grassmann angle-based geometric framework to give sharp bounds on this “balancedness” property of linear subspaces. By investigating the “balancedness” property, this unified framework characterizes sharp quantitative tradeoffs between signal sparsity and the recovery accuracy of ℓ1minimization for approximately sparse signal. As a consequence, this generalizes the neighborly polytope result for perfectly sparse signals. Besides the robustness in the “strong” sense for all sparse signals, we also discuss the notions of “weak” and “sectional” robustness. Our results concern fundamental properties of linear subspaces and so may be of independent mathematical interest.

Performing distributed consensus in a network has been an important research problem for several years, and is directly applicable to sensor networks, autonomous vehicle formation, etc. While there exists a wide variety of algorithms that can be proven to asymptotically reach consensus, in applications involving time-varying parameters and tracking, it is often crucial to reach consensus “as quickly as possible”. In [?] it has been shown that, with global knowledge of the network topology, it is possible to optimize the convergence time in distributed averaging algorithms via solving a semi-definite program (SDP) to obtain the optimal averaging weights. Unfortunately, in most applications, nodes do not have knowledge of the full network topology and cannot implement the required SDP in a distributed fashion. In this paper, we present a symmetric adaptive weight algorithm for distributed consensus averaging on bi-directional noiseless networks. The algorithm uses an LMS (Least Mean Squares) approach to adaptively update the edge weights used to calculate each node's values. The derivation shows that global error can be minimized in a distributed fashion and that the resulting adaptive weights are symmetric - symmetry being critical for convergence to the true average. Simulations show that convergence time is nearly equal to that of a non-symmetric adaptive algorithm developed in [?], and significantly better than that of the non-adaptive Metropolis-Hastings algorithm. Most importantly, our symmetric adaptive algorithm converges to the sample mean, whereas the method of [?] converges to an arbitrary value and results in significant error.

It is now well understood that the ℓ1minimization algorithm is able to recover sparse signals from incomplete measurements and sharp recoverable sparsity thresholds have also been obtained for the ℓ1minimization algorithm. However, even though iterative reweighted ℓ1minimization algorithms or related algorithms have been empirically observed to boost the recoverable sparsity thresholds for certain types of signals, no rigorous theoretical results have been established to prove this fact. In this paper, we try to provide a theoretical foundation for analyzing the iterative reweighted ℓ1algorithms. In particular, we show that for a nontrivial class of signals, the iterative reweighted ℓ1minimization can indeed deliver recoverable sparsity thresholds larger than that given in. Our results are based on a high-dimensional geometrical analysis (Grassmann angle analysis) of the null-space characterization for ℓ1minimization and weighted ℓ1minimization algorithms.

Determining the capacity of networks has been a long-standing issue of interest in the literature. Although for multi-source multi-sink networks it is known that using network coding is advantageous over traditional routing, finding the best coding strategy is not trivial in general. Among different classes of codes that could be potentially used in a network, linear codes due to their simplicity are of particular interest. Although linear codes are proven to be sub-optimal in general, in some cases such as the multicast scenario they achieve the cut-set bound. Since determining the capacity of a network is closely related to the characterization of the entropy region of all its random variables, if one is interested in finding the best linear solution for a network, one should find the region of all linear representable entropy vectors of that network. With this approach, we study the scalar linear solutions over arbitrary network problems with two sources. We explicitly calculate this region for small number of variables and suggest a method for larger networks through finding the best scalar linear solution to a storage problem as an example of practical interest.

It is well known that ℓ1minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from iid Gaussian measurements, have been computed and are referred to as “weak thresholds”. In this paper, we introduce a reweighted ℓ1recovery algorithm composed of two steps: a standard ℓ1minimization step to identify a set of entries where the signal is likely to reside, and a weighted ℓ1minimization step where entries outside this set are penalized. For signals where the non-sparse component has iid Gaussian entries, we prove a “strict” improvement in the weak recovery threshold. Simulations suggest that the improvement can be quite impressive-over 20% in the example we consider.

In principle, network codes derived from non-Abelian groups can be used to attain every point in the capacity region of wired acyclic networks. However, group codes derived from a particular group, and its subgroups, is useful only if it can model independent sources, as well as violate the Ingleton bound which restricts the capacity region obtainable by linear network codes. We study both the independent source and the Ingleton-violating requirement for subgroups of the groups PGL(2, ρ) and GL(2, ρ) with primes ρ ≥ 5. For both these groups we demonstrate that the requirements can be met, which suggests that PGL(2, ρ) and GL(2, ρ) are rich enough groups to construct network codes superior to linear ones. We also construct a model for independent sources using the direct product of the aforementioned groups.

Although determining the space of entropic vectors for n random variables, denoted by Γ*n, is crucial for solving a large class of network information theory problems, there has been scant progress in explicitly characterizing Γ*nfor n ≥ 4. In this paper, we present a certain characterization of quasi-uniform distributions that allows one to numerically stake out the entropic region via a random walk to any desired accuracy. When coupled with Monte Carlo Markov Chain (MCMC) methods, one may “bias” the random walk so as to maximize certain functions of the entropy vector. As an example, we look at maximizing the violation of the Ingleton inequality for four random variables and report a violation well in excess of what has been previously available in the literature. Inspired by the MCMC method, we also propose a framework for designing optimal nonlinear network codes via performing a random walk over certain truth tables. We show that the method can be decentralized and demonstrate its efficacy by applying it to the Vamos network and a certain storage problem from.

In this paper, we present a coding strategy for half duplex wireless relay networks, where we assume no channel knowledge at any of the transmitter, receiver, or relays. The coding scheme uses distributed space-time coding, that is, the relay nodes cooperate to encode the transmitted signal so that the receiver senses a space-time codeword. It is inspired by noncoherent differential techniques. The proposed strategy is available for any number of relays nodes. It is analyzed, and shown to yield a diversity linear in the number of relays. We also study the resistance of the scheme to relay node failures, and show that a network withRrelay nodes anddof them down behaves, as far as diversity is concerned, as a network withR-dnodes. Finally, our construction can be easily generalized to the case where the transmitter and receiver nodes have several antennas.

Estimation of the DNA copy number in a given biological sample is an important problem in genomics. Quantitative polymerase chain reaction (qPCR) systems detect the target DNA molecules by amplifying their number through a series of thermal cycles and measuring the amount of created amplicons in each cycle. Ideally, the number of target molecules doubles at the end of each cycle. However, in practice, due to biochemical noise the efficiency of the qPCR reaction - defined as the fraction of the target molecules which are successfully copied during a cycle - is always less than1. In this paper, we formulate the problem of the joint maximum-likelihood estimation of the qPCR efficiency and the initial DNA copy number. Then, we analytically determine the limits of performance of qPCR by deriving the Cramer-Rao lower bound on the mean-square estimation error. As indicated by simulation studies, the performance of the proposed estimator is superior compared to competing statistical approaches. The proposed approach is validated using experimental data.

In this paper we study a Markov Chain Monte Carlo (MCMC) Gibbs sampler for solving the integer least-squares problem. In digital communication the problem is equivalent to performing maximum likelihood (ML) detection in multiple-input multiple-output (MIMO) systems. While the use of MCMC methods for such problems has already been proposed, our method is novel in that we optimize the "temperature" parameter so that in steady state, i.e. after the Markov chain has mixed, there is only polynomially (rather than exponentially) small probability of encountering the optimal solution. More precisely, we obtain the largest value of the temperature parameter for this to occur, since the higher the temperature, the faster the mixing. This is in contrast to simulated annealing techniques where, rather than being held fixed, the temperature parameter is tended to zero. Simulations suggest that the resulting Gibbs sampler provides a computationally efficient way of achieving approximative ML detection in MIMO systems having a huge number of transmit and receive dimensions. In fact, they further suggest that the Markov chain is rapidly mixing. Thus, it has been observed that even in cases were ML detection using, e.g. sphere decoding becomes infeasible, the Gibbs sampler can still offer a near-optimal solution using much less computations.

This paper studies compressed sensing for the recovery of non-negative sparse vectors from a smaller number of measurements than the ambient dimension of the unknown vector. We focus on measurement matrices that are sparse, i.e., have only a constant number of nonzero (and non-negative) entries in each column. For such measurement matrices we give a simple necessary and sufficient condition for l1optimization to successfully recover the unknown vector. Using a simple ldquoperturbationrdquo to the adjacency matrix of an unbalanced expander, we obtain simple closed form expressions for the threshold relating the ambient dimension n, number of measurements m and sparsity level k, for which l1optimization is successful with overwhelming probability. Simulation results suggest that the theoretical thresholds are fairly tight and demonstrate that the ldquoperturbationsrdquo significantly improve the performance over a direct use of the adjacency matrix of an expander graph.

In this paper, we re-examine the recently proposed distributed state estimators based on quantized innovations. It is widely believed that the error covariance of the Quantized Innovation Kalman filter follows a modified Riccati recursion. We present stable linear dynamical systems for which this is violated and the filter diverges. We propose a Particle Filter that approximates the optimal nonlinear filter and observe that the error covariance of the Particle Filter follows the modified Riccati recursion. We also simulate a Posterior Cramer-Rao bound (PCRB) for this filtering problem.

In an earlier work, we used transform methods from the theory of random matrices to analytically compute the asymptotic eigendistribution of the error covariance matrix of the single-measurement RLS filter. When we have a multiplicity of measurements, as happens in extended RLS filtering, the analysis is much more complicated. In this paper we study the multiple measurement case and obtain a system of two coupled equations for the Stieltjes transform of the asymptotic eigendistribution. Numerical solutions of this system very well predict the actual asymptotic eigendistribution for systems with as low as n = 10 - 20 state dimensions.

In this work, we propose a transparent approach to evaluating the CDF of indefinite quadratic forms in Gaussian random variables and ratios of such forms. This quantity appears in the analysis of different receivers in communication systems and in various applications in signal processing. Instead of attempting to find the pdf of this quantity as is the case in many papers in literature, we focus on finding the CDF. The basic trick that we implement is to replace inequalities that appear in the CDF calculations with the unit step function and replace the latter with its Fourier transform. This produces a multi-dimensional integral that can be evaluated using complex integration. We show how our approach extends to nonzero mean Gaussian real/complex vectors and to the joint distribution of indefinite quadratic forms.

We study the capacity of the Gaussian two-pair fullduplex directional (or two-way) relay network with a single-relay supporting the communication of the pairs. This network is a generalization of the well known bidirectional relay channel, where we have only one pair of users. We propose a novel transmission technique which is based on a specific superposition of lattice codes and random Gaussian codes at the source nodes. The relay attempts to decode the Gaussian codewords and the superposition of the lattice codewords of each pair. Then it forwards this information to all users. We analyze the achievable rate of this scheme and show that for all channel gains it achieves to within 2 bits/sec/Hz per user of the cut-set upper bound on the capacity region of the two-pair bidirectional relay network.

In this paper we study the compressed sensing problem of recovering a sparse signal from a system of underdetermined linear equations when we have prior information about the probability of each entry of the unknown signal being nonzero. In particular, we focus on a model where the entries of the unknown vector fall into two sets, each with a different probability of being nonzero. We propose a weighted ¿1minimization recovery algorithm and analyze its performance using a Grassman angle approach. We compute explicitly the relationship between the system parameters (the weights, the number of measurements, the size of the two sets, the probabilities of being non-zero) so that an iid random Gaussian measurement matrix along with weighted ¿1minimization recovers almost all such sparse signals with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We also provide simulations to demonstrate the advantages of the method over conventional ¿1optimization.

It is well known in compressive sensing that l1minimization can recover the sparsest solution for a large class of underdetermined systems of linear equations, provided the signal is sufficiently sparse. In this paper, we compute sharp performance bounds for several different notions of robustness in sparse signal recovery via l1minimization. In particular, we determine necessary and sufficient conditions for the measurement matrix A under which l1minimization guarantees the robustness of sparse signal recovery in the “weak”, “sectional” and “strong” senses (e.g., robustness for “almost all” approximately sparse signals, or instead for “all” approximately sparse signals). Based on these characterizations, we are able to compute sharp performance bounds on the tradeoff between signal sparsity and signal recovery robustness in these various senses. Our results are based on a high-dimensional geometrical analysis of the null-space of the measurement matrix A. These results generalize the thresholds results for purely sparse signals [1], [3] and also present generalized insights on l1minimization for recovering purely sparse signals from a null-space perspective.

In this paper we study the capacity region of the multi-pair bidirectional (or two-way) wireless relay network, in which a relay node facilitates the communication between multiple pairs of users. This network is a generalization of the well known bidirectional relay channel, where we have only one pair of users. We examine this problem in the context of the deterministic channel interaction model, which eliminates the channel noise and allows us to focus on the interaction between signals. We characterize the capacity region of this network when the relay is operating at either full-duplex mode or half-duplex mode (with non adaptive listen-transmit scheduling). In both cases we show that the cut-set upper bound is tight and, quite interestingly, the capacity region is achieved by a simple equation-forwarding strategy.

We propose a new model of wireless networks which we refer to as "two-scale networks." At a local scale, characterised by nodes being within a distancer, channel strengths are drawn independently and identically from a distance-independent distribution. At a global scale, characterised by nodes being further apart from each other than a distance r, channel connections are governed by a Rayleigh distribution, with the power satisfying a distance-based decay law. Thus, at a local scale, channel strengths are determined primarily by random effects such as obstacles and scatterers whereas at the global scale channel strengths depend on distance. For such networks, we propose a hybrid communications scheme, combining elements of distance-dependent networks and random networks. For particular classes of two-scale networks withNnodes, we show that an aggregate throughput that is slightly sublinear inN, for instance, of the formN/log4Nis achievable. This offers a significant improvement over a throughput scaling behaviour ofO(√(N))that is obtained in other work.

This paper considers the effect of spatial correlation between transmit antennas on the sum-rate capacity of the MIMO Gaussian broadcast channel (i.e., downlink of a cellular system). Specifically, for a system with a large number of users n, we analyze the scaling laws of the sum-rate for the dirty paper coding and for different types of beamforming transmission schemes. When the channel is i.i.d., it has been shown that for large n, the sum rate is equal to M log log n + M log P/M + o(1) where M is the number of transmit antennas, P is the average signal to noise ratio, and o(1) refers to terms that go to zero as n rarr infin. When the channel exhibits some spatial correlation with a covariance matrix R (non-singular with tr(R) = M), we prove that the sum rate of dirty paper coding is M log log n + M log P/M + log det(R) + o(1). We further show that the sum-rate of various beamforming schemes achieves M log log n + M log P/M + M log c + o(1) where c les 1 depends on the type of beamforming. We can in fact compute c for random beamforming proposed in and more generally, for random beamforming with preceding in which beams are pre-multiplied by a fixed matrix. Simulation results are presented at the end of the paper.

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance of sphere decoding of linear block codes. We analyze the performance of soft-decision sphere decoding on AWGN channels and a variety of modulation schemes. A hard-decision sphere decoder is a bounded distance decoder with the corresponding decoding radius. We analyze the performance of hard-decision sphere decoding on binary andq-ary symmetric channels. An upper bound on the performance of maximum-likelihood decoding of linear codes defined overFq(e.g. Reed- Solomon codes) and transmitted overq-ary symmetric channels is derived and used in the analysis. We then discuss sphere decoding of general block codes or lattices with arbitrary modulation schemes. The tradeoff between the performance and complexity of a sphere decoder is then discussed.

It has been shown that random beamforming using partial channel state information (CSI) achieves the same throughput scaling as obtained from dirty paper coding for a broadcast (downlink) channel with M transmit antennas and K users where K is large. In this paper, we apply this scheme to wideband MIMO broadcast channels. By using OFDM, an L-tap wideband channel can be decomposed to N parallel narrowband channels (subcarriers), where N > L . Neighboring subcarriers are highly correlated. Therefore, we consider neighboring subcarriers as a cluster and find the closed form solution for the joint characteristic function of SINR values at two subcarriers in a cluster. We show numerically how the knowledge of the quality of the center subcarrier sheds light about the quality of other subcarriers in the same cluster, and address the issue of cluster size. In addition, through complex and asymptotic analysis, we show that for cluster size of order N/L¿(log K) (for large K), users need only feedback the best SINR at the center subcarrier of each cluster in order for the transmitter to perform opportunistic beamforming and maintain the same throughput scaling as when full CSI is available. Using simulation results, we verify our analytical result and show that even fewer feedback can be tolerated, and larger clusters (N/2L) can be implemented for a small throughput hit.

It has recently been shown that significant reduction in the peak to mean envelope power (PMEPR) can be obtained by altering the sign of each subcarrier in a multicarrier system with n subcarriers. However, finding the best sign not only requires a search over 2npossible signs but also may lead to a substantial rate loss for small size constellations. In this paper, we first propose a greedy algorithm to choose the signs based on p-norm minimization and prove that the resulting PMEPR is guaranteed to be less than c log n where c is a constant independent of n for any n. This approach has lower complexity in each iteration compared to the derandomization approach of while achieving similar PMEPR reduction. We further improve the performance of the proposed algorithm by enlarging the search space using pruning. Simulation results show that PMEPR of a multicarrier signal with 128 subcarriers can be reduced to within 1.6 dB of the PMEPR of a single carrier system. In the second part of the paper, we address the rate loss by proposing a block coding scheme in which only one sign vector is chosen for K different modulating vectors. The sign vector can be computed using the greedy algorithm in n iterations. We show that the multi-symbol encoding approach can reduce the rate loss by a factor of K while achieving the PMEPR of c logKn, i.e., only logarithmic growth in K. Simulation results show that the rate loss can be made smaller than %10 at the cost of only 1 db increase in the resulting PMEPR for a system with 128 subcarriers.

Expander graphs have been recently proposed to construct efficient compressed sensing algorithms. In particular, it has been shown that anyn-dimensional vector that isk-sparse can be fully recovered usingO(klogn) measurements and onlyO(klogn) simple recovery iterations. In this paper, we improve upon this result by considering expander graphs with expansion coefficient beyond3/4and show that, with the same number of measurements, onlyO(k) recovery iterations are required, which is a significant improvement whennis large. In fact, full recovery can be accomplished by at most2kvery simple iterations. The number of iterations can be reduced arbitrarily close tok, and the recovery algorithm can be implemented very efficiently using a simple priority queue with total recovery timeO(nlog(n/k))). We also show that by tolerating a small penalty on the number of measurements, and not on the number of recovery iterations, one can use the efficient construction of a family of expander graphs to come up with explicit measurement matrices for this method. We compare our result with other recently developed expander-graph-based methods and argue that it compares favorably both in terms of the number of required measurements and in terms of the time complexity and the simplicity of recovery. Finally, we will show how our analysis extends to give a robust algorithm that finds the position and sign of theksignificant elements of an almostk-sparse signal and then, using very simple optimization techniques, finds ak-sparse signal which is close to the bestk-term approximation of the original signal.

We consider the deterministic construction of a measurement matrix and a recovery method for signals that are block sparse. A signal that has dimension N = nd, which consists of n blocks of size d, is called (s, d)-block sparse if only s blocks out of n are nonzero. We construct an explicit linear mapping Phi that maps the (s, d) -block sparse signal to a measurement vector of dimension M, where s - dd/d+1) - o(1). We show that if the (s,d)- block sparse signal is chosen uniformly at random then the signal can almost surely be reconstructed from the measurement vector in O(N3) computations.

It is well known that compressed sensing problems reduce to solving large under-determined systems of equations. To assure that the problem is well defined, i.e., that the solution is unique the vector of unknowns is of course assumed to be sparse. Nonetheless, even when the solution is unique, finding it in general may be computationally difficult. However, starting with the seminal work of [2], it has been shown that linear programming techniques, obtained from an l1-norm relaxation of the original non-convex problem, can provably find the unknown vector in certain instances. In particular, using a certain restricted isometry property, [2] shows that for measurement matrices chosen from a random Gaussian ensemble, l1optimization can find the correct solution with overwhelming probability even when the number of non-zero entries of the unknown vector is proportional to the number of measurements (and the total number of unknowns). The subsequent paper [1] uses results on neighborly polytopes from [5] to give a “sharp” bound on what this proportionality should be in the Gaussian case. In the current paper, we observe that what matters is not so much the distribution from which the entries of the measurement matrix A are drawn, but rather the statistics of the null-space of A. Using this observation, we provide an alternative proof of the main result of [2] by analyzing matrices whose null-space is isotropic (of which i.i.d. Gaussian ensembles are a special case).

Conventional fluorescent-based microarrays acquire data after the hybridization phase. During this phase, the target analytes bind to the capturing probes on the array and, by the end of it, supposedly reach a steady state. Therefore, conventional microarrays attempt to detect and quantify the targets with a single data point taken in the steady-state. On the other hand, a novel technique, the so-called real-time microarray, capable of recording the kinetics of hybridization in fluorescent-based microarrays has recently been proposed in (Hassibi, 2007). The richness of the information obtained therein promises higher signal-to-noise ratio, smaller estimation error, and broader assay detection dynamic range compared to conventional microarrays. In the current paper, we develop a probabilistic model for real-time microarrays and describe a procedure for the estimation of target amounts therein. Moreover, leveraging on system identification ideas, we propose a novel technique for the elimination of cross-hybridization.

DNA microarrays comprising tens of thousands of probe spots are currently being employed to test multitude of targets in a single experiment. Typically, each microarray spot contains a large number of copies of a single probe designed to capture a single target, and hence collects only a single data point. This is a wasteful use of the sensing resources in comparative DNA microarray experiments, where a test sample is measured relative to a reference sample. Since only a small fraction of the total number of genes represented by the two samples is differentially expressed, a vast number of probe spots will not provide any useful information. To this end we consider an alternative design, the so-called compressed microarrays, wherein each spot is a composite of several different probes and the total number of spots is potentially much smaller than the number of targets being tested. Fewer spots directly translates to significantly lower costs due to cheaper array manufacturing, simpler image acquisition and processing, and smaller amount of genomic material needed for experiments. To recover signals from compressed microarray measurements, we leverage ideas from compressive sampling. Moreover, we propose an algorithm which has far less computational complexity than the widely-used linear-programming-based methods, and can also recover signals with less sparsity.

The demand for high data rate reliable communications poses great challenges to the next generation wireless systems in highly dynamic mobile environments. In this paper, we investigate the joint maximum-likelihood (ML) channel estimation and signal detection problem for single-input multiple-output (SIMO) wireless systems with general modulation constellations and propose an efficient sequential decoder for finding the exact joint ML solution. Unlike other known methods, the new decoder can even efficiently find the joint ML solution under high spectral efficiency non-constant modulus modulation constellations. In particular, the new algorithm does not need such preprocessing steps as Cholesky or QR decomposition in the traditional sphere decoders for joint ML channel estimation and data detection. The elimination of such preprocessing not only reduces the number of floating point computations, but also will potentially lead to smaller size and power consumption in VLSI implementations while providing better numerical stability.

This paper studies the lossy, wireless packet network of [1], in the case of a multicast requirement and the availability of feedback. In the unicast case, feedback is sufficient to allow a strategy which achieves the throughput-optimal cut-set capacity without requiring network coding [3]. We provide a counter-example to show that source coding and feedback, without network coding, is insufficient to achieve the cut-set capacity for the multicast wireless erasure network. In particular, we examine a network with one source, one relay, and two destinations. We show that even with the highly optimistic assumption of feedback which provides global packet state awareness, this network still fails to reach capacity. This bridges the gap between two previously known results; one, that network coding can achieve the capacity of the wireless erasure network, and two, that feedback allows a capacity achieving scheme which does not require network coding in the unicast wireless erasure network.

Given n (discrete or continuous) random variables Xi, the (2n- 1)-dimensional vector obtained by evaluating the joint entropy of all non-empty subsets of {X1,hellip, Xn} is called an entropic vector. Determining the region of entropic vectors is an important open problem in information theory. Recently, Chan has shown that the entropy regions for discrete and continuous random variables, though different, can be determined from one another. An important class of continuous random variables are those that are vector-valued and jointly Gaussian. It is known that Gaussian random variables violate the Ingleton bound, which many random variables such as those obtained from linear codes over finite fields do satisfy, and they also achieve certain non-Shannon inequalities. In this paper we give a full characterization of the entropy region for three jointly-Gaussian vector-valued random variables and, rather surprisingly, show that the region is strictly smaller than the entropy region for three arbitrary random variables. However, we also show the following result. For any given entropic vector h isin R7, there exists a thetas* > 0, such that for all thetas ges thetas*, the vector 1/thetas h can be generated by three vector-valued jointly Gaussian random variables. This implies that for three random variables the region of entropic vectors can be obtained by considering the cone generated by the space of Gaussian entropic vectors. It also suggests that studying Gaussian random variables for n ges 4 may be a fruitful approach to studying the space of entropic vectors for arbitrary n.

We consider the MIMO wiretap channel, that is a MIMO broadcast channel where the transmitter sends some confidential information to one user which is a legitimate receiver, while the other user is an eavesdropper. Perfect secrecy is achieved when the transmitter and the legitimate receiver can communicate at some positive rate, while insuring that the eavesdropper gets zero bits of information. In this paper, we compute the perfect secrecy capacity of the multiple antenna MIMO broadcast channel, where the number of antennas is arbitrary for both the transmitter and the two receivers. Our technique involves a careful study of a Sato-like upper bound via the solution of a certain algebraic Riccati equation.

Consider a lossy packet network of queues, communicating over a wireless medium. This paper presents a throughput-optimal transmission strategy for a unicast network when feedback is available, which has the following advantages: It requires a very limited form of acknowledgment feedback. It is completely distributed, and independent of the network topology. Finally, communication at the information theoretic cut-set rate requires no network coding and no rateless coding on the packets. This simple strategy consists of each node randomly choosing a packet from its buffer to transmit at each opportunity. However, the packet is only deleted from a nodepsilas buffer once it has been successfully received by the final destination.

It is well known that compressed sensing problems reduce to solving large under-determined systems of equations. If we choose the compressed measurement matrix according to some appropriate distribution and the signal is sparse enough the l1optimization can exactly recover the ideally sparse signal with overwhelming probability [2], [1]. In the current paper, we will consider the case of the so-called approximately sparse signals. These signals are a generalized version of the ideally sparse signals. Letting the zero valued components of the ideally sparse signals to take the values of certain small magnitude one can construct the approximately sparse signals. Using a different but simple proof technique we show that the claims similar to those of [2] and [1] related to the proportionality of the number of large components of the signals to the number of measurements, hold for approximately sparse signals as well. Furthermore, using the same technique we compute the explicit values of what this proportionality can be if the compressed measurement matrix A has a rotationally invariant distribution of the null-space. We also give the quantitative tradeoff between the signal sparsity and the recovery robustness of the l1minimization. As it will turn out in an asymptotic case of the number of measurements the threshold result of [1] corresponds to a special case of our result.

Fast fading wireless environments pose a great challenge for achieving high spectral efficiency in next generation wireless systems. Joint maximum-likelihood (ML) channel estimation and signal detection is of great theoretical and practical interest, especially for multiple-input multiple-output(MIMO) systems where the multiple channel coefficients need to be estimated. However, this is a hard combinatorial optimization problem, for which obtaining efficient exact algorithms has been elusive for the general MIMO systems. In this paper, we propose an efficient branch-estimate-bound non-coherent optimization framework which provably achieves the exact ML joint channel estimation and data detection for general MIMO systems. Numerical results indicate that the exact joint ML method can achieve substantial performance improvements over suboptimal methods including iterative channel estimation and signal detection. We also derive analytical bounds on the computational complexity of the new exact joint ML method and show that its average complexity approaches a constant times the length of the coherence time, as the SNR approaches infinity.

We consider the problem of differentiated rate scheduling for the downlink (i.e., multi-antenna broadcast channel), in the sense that the rates required by different users must satisfy certain constraints on their ratios. When full channel state information (CSI) is available at the transmitter and receivers, the problem can be readily solved using dirty paper coding (DPC) and the application of convex optimization techniques on the dual problem which is the multiple access channel (MAC). Since in many practical application full CSI may not be feasible and computational complexity prohibitive when the number of users is large, we focus on other simple schemes that require very little CSI: time-division opportunistic (TO) beamforming where in different time slots (of different lengths) the transmitter performs opportunistic beamforming to the users requiring the same rate, and weighted opportunistic (WO) beamforming where the random beams are assigned to those users having the largest weighted SINR. For single antenna systems we also look at the capacity-achieving superposition coding (SC) scheme. In all cases, we determine explicit schedules to guarantee the rate constraints and show that, in the limit of large number of users, the throughput loss compared to the unconstrained throughput (sum-rate capacity) tends to zero. We further provide bounds on the rate of convergence of the sum-rates of these schemes to the sum-rate capacity. Finally, we provide simulation results of the performance of different scheduling schemes considered in the paper.

Broadcast (or point to multipoint) communication has attracted a lot of research recently. In this paper, we consider the group broadcast channel where the users' pool is divided into groups, each of which is interested in common information. Such a situation occurs for example in digital audio and video broadcast where the users are divided into various groups according to the shows they are interested in. The paper obtains upper and lower bounds for the sum rate capacity in the large number of users regime and quantifies the effect of spatial correlation on the system capacity. The paper also studies the scaling of the system capacity when the number of users and antennas grow simultaneously. It is shown that in order to achieve a constant rate per user, the number of transmit antennas should scale at least logarithmically in the number of users.

In this paper, we present a coding strategy for wireless relay networks where the relay nodes are small devices with few resources, while the source and sink are equipped with multiple antennas to increase the transmission rate. We assume no channel knowledge at all, and the receiver decodes knowing none of the channel paths. This coding scheme uses distributed space-time coding techniques and is inspired by noncoherent differential space-time coding. It is shown to yield a diversity linear in the minimum number of transmit/receive antennas times the number of relays.

In multi-antenna communication systems, channel information is often not known at the receiver. To fully exploit bandwidth resources of the system and ensure practical feasibility of the receiver, channel parameters are often estimated blindly and then employed in the design of signal detection algorithms. Instead of separating channel estimation from signal detection, in this paper we focus on the joint channel estimation and signal detection problem in a single-input multiple-output (SIMO) system. It is well known that finding solution to this optimization requires solving an integer maximization of a quadratic form and is, in general, an NP hard problem. To solve it, we propose an approximate algorithm based on the semi-definite program (SDP) relaxation. We derive a bound on the pairwise probability of error (PEP) of the proposed algorithm and show that, the algorithm achieves the same diversity as the exact maximum-likelihood (ML) decoder. The computed PEP implies that, over a wide range of system parameters, the proposed algorithm requires moderate increase in the signal-to-noise ratio (SNR) in order to achieve performance comparable to that of the ML decoder but with often significantly lower complexity.

Estimation of DNA copy number in a given biological sample is an extremely important problem in genomics. This problem is especially challenging when the number of the DNA strands is minuscule, which is often the case in applications such as pathogen and genetic mutation detection. A recently developed technique, real-time polymerase chain reaction (PCR), amplifies the number of initial target molecules by replicating them through a series of thermal cycles. Ideally, the number of target molecules doubles at the end of each cycle. However, in practice, due to biochemical noise the efficiency of the PCR reaction, defined as the fraction of target molecules which are successfully copied during a cycle, is always less than 1. In this paper, we formulate the problem of joint maximum-likelihood estimation of the PCR efficiency and the initial DNA copy number. As indicated by simulation studies, the performance of the proposed estimator is superior with respect to competing statistical approaches. Moreover, we compute the Cramer-Rao lower bound on the mean-square estimation error.

In this paper, we consider a multi-user system called the group-broadcast system. In this scenario the users are divided into different groups. Users in each group are interested in a common information independent from that of other groups. Such a situation occurs for example in digital audio and video broadcast systems where the users are divided into various groups according to the shows they are interested in. The paper first obtains upper and lower bounds for the sum rate capacity. Then it looks at system capacity for the large number of users regime and fixed number of antennas. Finally, the case when the number of users and antennas grow simultaneously is studied. It is shown that in order to achieve a constant rate per user the number of transmit antennas should scale at least logarithmically in the number of users.

The problem of determining the region of entropic vectors is a central one in information theory. There has been a great deal of interest in the development of non-Shannon information inequalities, which provide outer bounds to the aforementioned region; however, there has been less work on developing inner bounds. This paper develops an inner bound that applies to any number of random variables and which is tight for 2 and 3 random variables (the only cases where the entropy region is known). The construction is based on probability distributions generated by a lattice. The region is shown to be a polytope generated by a set of linear inequalities. Study of the region for 4 and more random variables is currently under investigation.

Consider a wireless network with m transmitter-receiver pairs and an additional n relay nodes to assist communication. We are interested in the rate/diversity trade-off of such a system. Since the presence of interference is known to reduce diversity significantly, we propose a transmission scheme based on interference cancellation by the relay nodes. This scheme achieves a diversity linear in the number of relay nodes (over all rates up to the maximum possible). Compared to a protocol where receivers decode all transmitted messages, the new scheme is seen to achieve higher diversity at higher rates.

In this paper we consider the problem of the optimal quantum unambiguous detection between two mixed quantum states. More specifically, we consider two mixed quantum states of rank 2 which lie in a Hilbert space of dimension 4. Using duality theory we explicitly characterize the optimal measurement operators. Furthermore, as a by-product of our framework we obtain a closed form solution of unambiguous discrimination between a pure and a mixed quantum state.

In multi-antenna communication systems, channel information is often not known at the receiver. To fully exploit the bandwidth resources of the system and ensure the practical feasibility of the receiver, the channel parameters are often estimated and then employed in the design of signal detection algorithms. However, sometimes communication can occur in the environment where learning the channel coefficients becomes infeasible. In this paper we consider the problem of maximum-likelihood (ML)-detection in single-input multiple-output (SIMO) systems when the channel information is completely unavailable at the receiver and when employed signalling at the transmitter is q-PSK. It is well known that finding the solution to this optimization requires solving an integer maximization of a quadratic form and is, in general, an NP hard problem. To solve it, we propose an approximate algorithm based on the semi-definite program (SDP) relaxation. We derive a bound on the pairwise probability of error (PEP) of the proposed algorithm and show that, the algorithm achieves the same diversity as the exact maximum-likelihood (ML) decoder. Furthermore, we prove that in the limit of large system dimension this bound differs from the corresponding one in the exact ML case by at most 3.92 dB if the transmitted symbols are from 2 or 4-PSK constellations and by at most 2.55 dB if the transmitted symbols are from 8-PSK constellation. This suggests that the proposed algorithm requires moderate increase in the signal-to-noise ratio (SNR) in order to achieve performance comparable to that of the ML decoder but with often significantly lower complexity.

We introduce the notion of normalized entropic vectors-slightly different from the standard definition in the literature in that we normalize entropy by the logarithm of the alphabet size. We argue that this definition is more natural for determining the capacity region of networks and, in particular, that it smooths out the irregularities of the space of non-normalized entropy vectors and renders the closure of the resulting space convex (and compact). Furthermore, the closure of the space remains convex even under constraints imposed by memoryless channels internal to the network. It therefore follows that, for a large class of acyclic memoryless networks, the capacity region for an arbitrary set of sources and destinations can be found by maximization of a linear function over the convex set of channel-constrained normalized entropic vectors and some linear constraints. While this may not necessarily make the problem simpler, it certainly circumvents the "infinite-letter characterization" issue, as well as the nonconvexity of earlier formulations, and exposes the core of the problem. We show that the approach allows one to obtain the classical cutset bounds via a duality argument. Furthermore, the approach readily shows that, for acyclic memorylesswirednetworks, one need only consider the space of unconstrained normalized entropic vectors, thus separating channel and network coding—a result very recently recognized in the literature.

We find the diversity-multiplexing gain trade-off of a multiple-antenna (MIMO) system with M transmit antennas, N receive antennas, R relay nodes, and with independent Rayleigh fading, in which the relays apply a distributed space-time code. In this two-stage scheme the trade-off is shown to coincide with that of a MIMO system with R transmit and min{M,N} receive antennas.

The throughput of a multiple-antenna broadcast channel highly depends on the channel state information (CSI) at the transmitter side. However, due to the time variant nature of wireless channels, having perfect knowledge of the underlying links appears to be a questionable assumption, especially when the number of users and/or antennas increases. Although it can become computationally prohibitive in practice, theoretically any point on the capacity region of a Gaussian broadcast channel is achievable using dirty paper coding (DPC) if full CSI is available.

This paper studies the fundamental limits of MIMO broadcast channels from a high level, determining the sum-rate capacity of the system as a function of system parameters, such as the number of transmit antennas, the number of users, the number of receive antennas, and the total transmit power. The crucial role of channel state information at the transmitter is emphasized, as well as the emergence of opportunistic transmission schemes. The effects of channel estimation errors, training, and spatial correlation are studied, as well as issues related to fairness, delay and differentiated rate scheduling.

In many problems in wireline networks, it is known that achieving capacity on each link or subnetwork is optimal for the entire network operation. In this paper, we present examples of wireless networks in which decoding and achieving capacity on certain links or subnetworks gives us lower rates than other simple schemes, like forwarding. This implies that the separation of channel and network coding that holds for many classes of wireline networks does not, in general, hold for wireless networks. Next, we consider Gaussian and erasure wireless networks where nodes are permitted only two possible operations: nodes can either decode what they receive (and then re-encode and transmit the message) or simply forward it. We present a simple greedy algorithm that returns the optimal scheme from the exponential-sized set of possible schemes. This algorithm will go over each node at most once to determine its operation, and hence, is very efficient. We also present a decentralized algorithm whose performance can approach the optimum arbitrarily closely in an iterative fashion

In this letter, we derive the scaling laws of the sum rate for fading multiple-input multiple-output Gaussian broadcast channels using time sharing to the strongest user, dirty-paper coding (DPC), and beamforming, when the number of users (receivers) n is large. Throughout the letter, we assume a fix average transmit power and consider a block-fading Rayleigh channel. First, we show that for a system with M transmit antennas and users equipped with N antennas, the sum rate scales like MloglognN for DPC, and beamforming when M is fixed and for any N (either growing to infinity or not). On the other hand, when both M and N are fixed, the sum rate of time sharing to the strongest user scales like min(M,N)loglogn. Therefore, the asymptotic gain of DPC over time sharing for the sum rate is (M/min(M,N)) when M and N are fixed. It is also shown that if M grows as logn, the sum rate of DPC and beamforming will grow linearly in M, but with different constant multiplicative factors. In this region, the sum-rate capacity of time -sharing scales like Nloglogn

Cayley space–time codes have been proposed as a solution for coding over noncoherent differential multiple-input multiple-output (MIMO) channels. Based on the Cayley transform that maps the space of Hermitian matrices to the manifold of unitary matrices, Cayley codes are particularly suitable for high data rate, since they have an easy encoding and can be decoded using a sphere-decoder algorithm. However, at high rate, the problem of evaluating if a Cayley code is fully diverse may become intractable, and previous work has focused instead on maximizing a mutual information criterion. The drawback of this approach is that it requires heavy optimization which depends on the number of antennas and rate. In this work, we study Cayley codes in the context of division algebras, an algebraic tool that allows to get fully diverse codes. We present an algebraic construction of fully diverse Cayley codes, and show that this approach naturally yields, without further optimization, codes that perform similarly or closely to previous unitary differential codes, including previous Cayley codes, and codes built from Lie groups.

We consider a single-antenna broadcast block fading channel with n users where the transmission is packet- based. We define the (packet) delay as the minimum number of channel uses that guarantees all n users successfully receive m packets. This is a more stringent notion of delay than average delay and is the worst case (access) delay among the users. A delay optimal scheduling scheme, such as round-robin, achieves the delay of mn. For the opportunistic scheduling (which is throughput optimal) where the transmitter sends the packet to the user with the best channel conditions at each channel use, we derive the mean and variance of the delay for any m and n. For large n and in a homogeneous network, it is proved that the expected delay in receiving one packet by all the receivers scales as nlogn, as opposed to n for the round-robin scheduling. We also show that when m grows faster than (log n)r, for some r > 1, then the delay scales as mn. This roughly determines the time- scale required for the system to behave fairly in a homogeneous network. We then propose a scheme to significantly reduce the delay at the expense of a small throughput hit. We further look into the advantage of multiple transmit antennas on the delay. For a system with M antennas in the transmitter where at each channel use packets are sent to M different users, we obtain the expected delay in receiving one packet by all the users.

To mitigate intercarrier interference (ICI), a two-path algorithm is developed for multicarrier communication systems, including orthogonal frequency division multiplexing (OFDM) systems. The first path employs the regular OFDM algorithm. The second path uses the conjugate transmission of the first path. The combination of both paths forms a conjugate ICI cancellation scheme at the receiver. This conjugate cancellation (CC) scheme provides (1) a high signal to interference power ratio (SIR) in the presence of small frequency offsets (50 dB and 33 dB higher than that of the regular OFDM and linear self-cancellation algorithms (Y. Zhao and S.-G. Haggman, 2001), (J. Armstrong, 1999), respectively, at DeltafT = 0.1% of subcarrier frequency spacing); (2) better bit error rate (BER) performance in both additive white Gaussian noise (AWGN) and fading channels; (3) backward compatibility with the existing OFDM system; (4) no channel equalization is needed for reducing ICI, a simple low cost receiver without increasing system complexity. Although the two-path transmission reduces bandwidth efficiency, the disadvantage can be balanced by increasing signal alphabet sizes

In many communication applications, maximum-likelihood decoding reduces to solving an integer least-squares problem which is NP hard in the worst-case. On the other hand, it has recently been shown that, over a wide range of dimensions and SNR, the sphere decoder can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. In earlier work, we targeted these two regimes attempting to find faster algorithms by pruning the search tree beyond what is done in the standard sphere decoder. The search tree is pruned by computing lower bounds on the possible optimal solution as we proceed to go down the tree. A trade-off between the computational complexity required to compute the lower bound and the size of the pruned tree is readily observed: the more effort we spend in computing a tight lower bound, the more branches that can be eliminated in the tree. Thus, even though it is possible to prune the search tree (and hence the number of points visited) by several orders of magnitude, this may be offset by the computations required to perform the pruning. In this paper, we propose a computationally efficient lower bound which requires solving a single semi-definite program (SDP) at the top of the search tree; the solution to the SDP is then used to deduce the lower bounds on the optimal solution on all levels of the search tree. Simulation results indicate significant improvement in the computational complexity of the proposed algorithm over the standard sphere decoding

The sum rate capacity of the multi-antenna Gaussian broadcast channel has recently been computed. However, the search for computationally efficient practical schemes that achieve it is still in progress. When the channel state information is fully available at the transmitter, the dirty paper coding (DPC) technique is known to achieve the maximal throughput, but is computationally infeasible. In this paper, we analyze the asymptotic behavior of one of its alternatives - the recently suggested so-called vector perturbation technique. We show that for a square channel, where the number of users is large and equal to the number of transmit antennas, its sum rate approaches that of the DPC technique. More precisely, we show that at both low and high signal-to-noise ratio (SNR), the scheme under consideration is asymptotically optimal. Furthermore, we obtain similar results in the case where the number of users is much larger than the number of transmit antennas

In a broadcast channel in which one transmitter serves n receivers, the capacity region highly depends on the amount of channel state information (CSI) at the transmitter. Assuming that the transmitter knows the SNR of all the receivers, opportunistic strategy maximizes the throughput (sum-rate) of the system. It is usually assumed that CSI is accurate, however, evaluating the SNR is basically an estimation problem in the receiver which cannot be done without error. In this paper, we analyze the effect of the noisy estimation of SNR on the throughput of a broadcast channel. We propose a generalization of the opportunistic transmission in which the transmitter still sends to the user with the highest estimated SNR, but backs off on the transmit rate based on the variance of the estimation error. We obtain the optimum amount of back off and compute the throughput for our scheduling scheme. Clearly, the estimation can be improved by using a longer training phase; however, longer training would deteriorate the throughput. In the final part of the paper, we address this trade off and obtain the optimum training strategy that maximizes the throughput of the system

DNA microarray technology relies on the hybridization process which is stochastic in nature. Probabilistic cross-hybridization of non-specific targets, as well as the shot-noise originating from specific targets binding, are among the many obstacles for achieving high accuracy in DNA microarray analysis. In this paper, we use statistical model of hybridization and cross-hybridization processes to derive a lower bound (viz., the Cramer-Rao bound) on the minimum mean-square error of the target concentrations estimation. A preliminary study of the Cramer-Rao bound for estimating the target concentrations suggests that, in some regimes, cross-hybridization may, in fact, be beneficial - a result with potential ramifications for probe design, which is currently focused on minimizing cross-hybridization

This paper considers the effect of spatial correlation between transmit antennas on the sum-rate capacity of the MIMO broadcast channel (i.e., downlink of a cellular system). Specifically, for a system with a large number of users n, we analyze the scaling laws of the sum-rate for the dirty paper coding and for different types of beamforming transmission schemes. When the channel is i.i.d., it has been shown that for large n, the sum rate is equal to M log log n + M log P/M + o(1) where M is the number of transmit antennas, P is the average signal to noise ratio, and o(1) refers to terms that go to zero as n rarr infin. When the channel exhibits some spatial correlation with a covariance matrix R (non-singular with tr(R) = M), we prove that the sum rate of dirty paper coding is M log log n + M log P/M + log det(R) + o(1). We further show that the sum-rate of various beamforming schemes achieves M log log n + M log P/M + M log c + o(1) where c les 1 depends on the type of beamforming. We can in fact compute c for random beamforming proposed in M. Sharif et al. (2005) and more generally, for random beamforming with preceding in which beams are pre-multiplied by a fixed matrix. Simulation results are presented at the end of the paper

In this paper we consider the effect of channel estimation error on the capacity region of MIMO Gaussian broadcast channels. It is assumed that the receivers and the transmitter have (the same) estimates of the channel coefficients (i.e., the feedback channel is noiseless). We obtain an achievable rate region based on the dirty paper coding scheme. We show that this region is given by the capacity region of a dual multi-access channel with a noise covariance that depends on the transmit power. We explore this duality to give the asymptotic behavior of the sum-rate for a system with a large number of user, i.e., n rarr infin. It is shown that as long as the estimation error is of fixed (w.r.t n) variance, the sum-capacity is of order M log log n, where M is the number of antennas deployed at the transmitter. We further obtain the sum-rate loss due to the estimation error. Finally, we consider a training-based scheme for block fading MISO Gaussian broadcast channels. We find the optimum length of the training interval as well as the optimum power used for training in order to maximize the achievable sum-rate

The performance of sphere decoding of block codes over a variety of channels is investigated. We derive a tight bound on the performance of maximum likelihood decoding of linear codes on q-ary symmetric channels. We use this result to bound the performance of q-ary hard decision sphere decoders. We also derive a tight bound on the performance of soft decision sphere decoders on the AWGN channel for BPSK and M-PSK modulated block codes. The performance of soft decision sphere decoding of arbitrary finite lattices or block codes is also analyzed

We propose a new model of wireless networks which we refer to as "two-scale networks". At a local scale, characterized by nodes being within a distance r, channel strengths are drawn independently and identically from a distance-independent distribution. At a global scale, characterized by nodes being further apart from each other than a distance r, channel connections are governed by a Rayleigh distribution, with the power satisfying a distance-based decay law. Thus, at a local scale, channel strengths are determined primarily by random effects such as obstacles and scatterers whereas at the global scale channel strengths depend on distance. For such networks, we propose a hybrid communications scheme, combining elements of P. Gupta et al. (2000) (for distance-dependent networks) and R. Gowaikar et al. (2006) (for random networks). For a particular class of two-scale networks with N nodes, we show that an aggregate throughput of the form N[1divide(t-1)]/log2N is achievable, where t > 2 is a parameter that depends on the distribution of the connection at the local scale and is independent of the decay law that operates at a global scale. For t < 3, this offers a significant improvement over the O(radicN) results of P. Gupta et al. (2000)

This paper studies the design of distributed space-time codes for use in wireless relay networks. Earlier work suggested that a suitable family of codes can be obtained by using linear dispersion codes, provided the basis matrices were unitary. In this paper we construct an explicit algebraic family of such codes where full diversity is proved. The construction uses cyclotomic field theory and yields basis matrices that are indeed unitary. Simulation results show that the codes have better performance than codes designed earlier by ad hoc and random methods, and thus with less encoding complexity

In this letter, we consider the problem of constructing high-rate codes with low peak-to-mean-envelope power ratio (PMEPR) for multicarrier signals. Assuming coefficients of the multicarrier signal are chosen from a symmetric q-ary constellation, we construct codes with rate 1-(1/r)logq2 and PMEPR of less than crlogn for any r and n, where n is the number of subcarriers and c is a constant independent of n and r. The construction is based on dividing n subcarriers into n/r groups of r subcarriers and choosing a sign for each group to minimize the PMEPR. The signs are chosen using a variation of the algorithm proposed by the authors in previous papers. For large n, we can, in fact, construct a code with a rate of 1-O(1/logn) and PMEPR of less than clog2n. For binary phase-shift-keying-modulated signals, this partially solves the problem posed by Litsyn and implies a construction of 2n/2codewords with PMEPR less than 2clogn

The maximum-likelihood (ML) sequence detection problem for channels with memory is investigated. The Viterbi algorithm (VA) provides an exact solution. Its computational complexity is linear in the length of the transmitted sequence, but exponential in the channel memory length. On the other hand, the sphere decoding (SD) algorithm also solves the ML detection problem exactly, and has expected complexity which is a low-degree polynomial (often cubic) in the length of the transmitted sequence over a wide range of signal-to-noise ratios. We combine the sphere-constrained search strategy of SD with the dynamic programming principles of the VA. The resulting algorithm has the worst-case complexity determined by the VA, but often significantly lower expected complexity

In this paper, a special class of wireless networks, called wireless erasure networks, is considered. In these networks, each node is connected to a set of nodes by possibly correlated erasure channels. The network model incorporates the broadcast nature of the wireless environment by requiring each node to send the same signal on all outgoing channels. However, we assume there is no interference in reception. Such models are therefore appropriate for wireless networks where all information transmission is packetized and where some mechanism for interference avoidance is already built in. This paper looks at multicast problems over these networks. The capacity under the assumption that erasure locations on all the links of the network are provided to the destinations is obtained. It turns out that the capacity region has a nice max-flow min-cut interpretation. The definition of cut-capacity in these networks incorporates the broadcast property of the wireless medium. It is further shown that linear coding at nodes in the network suffices to achieve the capacity region. Finally, the performance of different coding schemes in these networks when no side information is available to the destinations is analyzed

We consider the power efficiency of a communications channel, i.e., the maximum bit rate that can be achieved per unit power (energy rate). For additive white Gaussian noise (AWGN) channels, it is well known that power efficiency is attained in the low signal-to-noise ratio (SNR) regime where capacity is proportional to the transmit power. In this paper, we first show that for a random sensory wireless network with n users (nodes) placed in a domain of fixed area, with probability converging to one as n grows, the power efficiency scales at least by a factor of /spl radic/n. In other words, each user in a wireless channel with n nodes can support the same communication rate as a single-user system, but by expending only 1//spl radic/n times the energy. Then we look at a random ad hoc network with n relay nodes and r simultaneous transmitter/receiver pairs located in a domain of fixed area. We show that as long as r/spl les//spl radic/n, we can achieve a power efficiency that scales by a factor of /spl radic/n. We also give a description of how to achieve these gains.

A network of nodes in which pairs communicate over a shared wireless medium is analyzed. We consider the maximum total aggregate traffic flow possible as given by the number of users multiplied by their data rate. The model in this paper differs substantially from the many existing approaches in that the channel connections in this network are entirely random: rather than being governed by geometry and a decay-versus-distance law, the strengths of the connections between nodes are drawn independently from a common distribution. Such a model is appropriate for environments where the first-order effect that governs the signal strength at a receiving node is a random event (such as the existence of an obstacle), rather than the distance from the transmitter. It is shown that the aggregate traffic flow as a function of the number of nodes n is a strong function of the channel distribution. In particular, for certain distributions the aggregate traffic flow is at least n/(logn)/sup d/ for some d>0, which is significantly larger than the O(/spl radic/n) results obtained for many geometric models. The results provide guidelines for the connectivity that is needed for large aggregate traffic. The relation between the proposed model and existing distance-based models is shown in some cases.

We apply the idea of space-time coding devised for multiple-antenna systems to the problem of communications over a wireless relay network with Rayleigh fading channels. We use a two-stage protocol, where in one stage the transmitter sends information and in the other, the relays encode their received signals into a "distributed" linear dispersion (LD) code, and then transmit the coded signals to the receive node. We show that for high SNR, the pairwise error probability (PEP) behaves as (logP/P)min{TH}, with T the coherence interval, that is, the number of symbol periods during which the channels keep constant, R the number of relay nodes, and P the total transmit power. Thus, apart from the log P factor, the system has the same diversity as a multiple-antenna system with R transmit antennas, which is the same as assuming that the R relays can fully cooperate and have full knowledge of the transmitted signal. We further show that for a network with a large number of relays and a fixed total transmit power across the entire network, the optimal power allocation is for the transmitter to expend half the power and for the relays to collectively expend the other half. We also show that at low and high SNR, the coding gain is the same as that of a multiple-antenna system with R antennas. However, at intermediate SNR, it can be quite different, which has implications for the design of distributed space-time codes

The sum rate capacity of the multi-antenna broadcast channel has recently been computed. However, the search for efficient practical schemes that achieve it is still ongoing. In this paper, we focus on schemes with linear preprocessing of the transmitted data. We propose two criteria for the preceding matrix design: one maximizing the sum rate and the other maximizing the minimum rate among all users. The latter problem is shown to be quasiconvex and is solved exactly via a bisection method. In addition to preceding, we employ a signal scaling scheme that minimizes the average bit-error-rate (BER). The signal scaling scheme is posed as a convex optimization problem, and thus can be solved exactly via efficient interior-point methods. In terms of the achievable sum rate, the proposed technique significantly outperforms traditional channel inversion methods, while having comparable (in fact, often superior) BER performance

In wireless communication systems, channel state information is often assumed to be available at the receiver. Traditionally, a training sequence is used to obtain the estimate of the channel. Alternatively, the channel can be identified using known properties of the transmitted signal. However, the computational effort required to find the joint ML solution to the symbol detection and channel estimation problem increases exponentially with the dimension of the problem. To significantly reduce this computational effort, we formulate the joint ML estimation and detection as an integer least-squares problem, and show that for a wide range of signal-to-noise ratios (SNR) and problem dimensions it can be solved via sphere decoding with expected complexity comparable to the complexity of heuristic techniques

In many communications applications, maximum-likelihood decoding reduces to solving an integer least-squares problem which is NP hard in the worst-case. However, as has recently been shown, over a wide range of dimensions and SNRs, the sphere decoder can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. We target these two regimes and attempt to find faster algorithms by pruning the search tree beyond what is done in the standard sphere decoder. The search tree is pruned by computing lower bounds on the possible optimal solution as we proceed down the tree. We observe a trade-off between the computational complexity required to compute the lower bound and the size of the pruned tree: the more effort spent computing a tight lower bound, the more branches that can be eliminated in the tree. Thus, even though it is possible to prune the search tree (and hence the number of points visited) by several orders of magnitude, this may be offset by the computations required to perform the pruning. All of which suggests the need for computationally-efficient tight lower bounds. We present three different lower bounds (based on spherical-relaxation, polytope-relaxation and duality), simulate their performances and discuss their relative merits.

We consider a single-antenna broadcast block fading channel (downlink scheduling) with n users where the transmission is packet-based and all users are backlogged. We define the delay as the minimum number of channel uses that guarantees all n users successfully receive m packets. This is a more stringent notion of delay than average delay and is the worst case delay among the users. A delay optimal scheduling scheme, such as round-robin, achieves the delay of mn. In a heterogeneous network and for the optimal throughput strategy where the transmitter sends the packet to the user with the best channel conditions, we derive the moment generating-function of the delay for any m and n. For large n and in a homogeneous network, the expected delay in receiving one packet by all the receivers scales as n logn, as opposed to n for the round-robin scheduling. We also show that when m grows faster than (logn)/sup r/, for some r>1, then the expected value of delay scales like mn. This roughly determines the time-scale required for the system to behave fairly in a homogeneous network. We then propose a scheme to significantly reduce the delay at the expense of a small throughput hit. We further look into two generalizations of our work: i) the effect of temporal channel correlation and ii) the advantage of multiple transmit antennas on the delay. For a channel with memory of two, we prove that the delay scales again like n logn no matter how severe the correlation is. For a system with M transmit antennas, we prove that the expected delay in receiving one packet by all the users scales like n log n/(M+O(M/sup 2//n)) for large n when M is not growing faster than logn. Thus, when the temporal channel correlation is zero, multiple transmit antenna systems do not reduce the delay significantly. However, when channel correlation is present, they can lead to significant gains by "decorrelating" the effective channel through means such as random beamforming.

In this paper, we look at the capacity region of a special class of broadcast channels with multiple inputs at the transmitter and a number of receivers. The channel between an input of the transmitter and a receiver is modelled as an independent memoryless erasure channel. We assume that the signals coming from different inputs to the receiver do not interfere with each other. Also for each input, the transmitter sends the same signal through the channels outgoing from that input. This class of broadcast channels does not necessarily belong to the class of "more capable". We show that the capacity region of these broadcast channels is achieved by time-sharing between the receivers at each input. Finally, the implications of these results to the more general network setup are discussed

We analyze a network of nodes in which pairs communicate over a shared wireless medium. We are interested in the maximum total aggregate traffic flow that is possible through the network. Our model differs substantially from the many existing approaches in that the channel connections in our network are entirely random: we assume that, rather than being governed by geometry and a decay law, the strength of the connections between nodes is drawn independently from a common distribution. Such a model is appropriate for environments where the first order effect that governs the signal strength at a receiving node is a random event (such as the existence of an obstacle), rather than the distance from the transmitter. We show that the aggregate traffic flow is a strong function of the channel distribution. In particular, we show that for certain distributions, the aggregate traffic flow scales at least as n/(log n)vfor some fixed v > 0, which is significantly larger than the O(radic/n) results obtained for many geometric models

In [1], the idea of distributed space-time coding was proposed to achieve a degree of cooperative diversity in a wireless relay network. In particular, for a relay network with a single-antenna transmitter and receiver and R single-antenna relays, it was shown that the pairwise error probability (PEP) decays as (log P/P)Rwhere P is the total transmit power. In this paper, we extend the results to wireless relay networks where the transmitter, receiver, and/or relays may have multiple antennas. Assuming that the transmitter has M antennas, the receiver has N antennas, the sum of all the antennas at the relay nodes is R, and the coherence interval is long enough, we show that the PEP behaves as (1/P)min{M,N}R, if M ne N, and (log1M/P/P)MR, if M = N. Therefore, for the case of M ne N, distributed space-time coding has the same PEP performance as a multiple-antenna system with min{M, N}R transmit and a single receive antenna. For the case of M = N, the penalty on the PEP compared to a multiple-antenna system is a log1M/ P factor, which is negligible at high SNR. We also show that for a fixed total transmit power across the entire network, the optimal power allocation is for the transmitter to expend half the power and for the relays to share the other half with the power used by each relay being proportional to the number of antennas it has

In this paper, we consider a fading broadcast channel where users have different rate demands. In particular, we assume users are divided into M groups, each group of which requires the same rate, and where the ratio of the rates of the groups are given. The transmitter would like to maximize the throughput (sum of the rates to all users) while maintaining the rational rate constraints. In general, this problem appears to be computationally intractable since the ergodic capacity region is described as the convex hull of (an infinite) set of rates. In this paper, we therefore, focus on the asymptotic regime of many users (large n) where explicit results can be found. In particular, we propose three scheduling schemes to provide the rational rate constraints namely, weighted opportunistic (WO), time division opportunistic (TO), and superposition coding (SC). The WO scheduling is a generalization of the opportunistic scheduling in which we transmit to only the user that has the maximum weighted signal to noise ratio (SNR). In TO, each group has its own time slot in which the transmitter chooses the user with the best SNR from the corresponding group. Superposition coding is the one that achieves the capacity region. For each scheduling we give explicit scheme to guarantee the rational rate constraints. We also analyze the throughput loss due to rate constraints for different schemes. In particular, we show that the throughput loss compared to the maximum throughput (i.e., the sum rate capacity without any rate constraints) tends to zero for large n, and finally, we analyze the convergence rate of all the schemes

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We derive tight upper bounds on the performance of sphere decoding of linear block codes. The performance of soft-decision sphere decoding on AWGN channels as well as that of hard-decision sphere decoding on binary symmetric channels is analyzed.

In this letter, we propose a method to reduce the peak-to-mean-envelope-power ratio (PMEPR) of multicarrier signals by modifying the constellation. For M-ary phase-shift keying constellations, we minimize the maximum of the multicarrier signal over the sign and amplitude of each subcarrier. In order to find an efficient solution to the aforementioned nonconvex optimization problem, we present a suboptimal solution by first optimizing over the signs, and then optimizing over the amplitudes given the signs. We prove that the minimization of the maximum of a continuous multicarrier signal over the amplitude of each subcarrier can be written as a convex optimization problem with linear matrix inequality constraints. We also generalize the idea to other constellations such as 16-quadrature amplitude modulation. Simulation results show that by an average power increase of 0.21 dB, and not sending information over the sign of each subcarrier, PMEPR can be decreased by 5.1 dB for a system with 128 subcarriers.

In multiple-antenna broadcast channels, unlike point-to-point multiple-antenna channels, the multiuser capacity depends heavily on whether the transmitter knows the channel coefficients to each user. For instance, in a Gaussian broadcast channel with M transmit antennas and n single-antenna users, the sum rate capacity scales like Mloglogn for large n if perfect channel state information (CSI) is available at the transmitter, yet only logarithmically with M if it is not. In systems with large n, obtaining full CSI from all users may not be feasible. Since lack of CSI does not lead to multiuser gains, it is therefore of interest to investigate transmission schemes that employ only partial CSI. We propose a scheme that constructs M random beams and that transmits information to the users with the highest signal-to-noise-plus-interference ratios (SINRs), which can be made available to the transmitter with very little feedback. For fixed M and n increasing, the throughput of our scheme scales as MloglognN, where N is the number of receive antennas of each user. This is precisely the same scaling obtained with perfect CSI using dirty paper coding. We furthermore show that a linear increase in throughput with M can be obtained provided that M does not not grow faster than logn. We also study the fairness of our scheduling in a heterogeneous network and show that, when M is large enough, the system becomes interference dominated and the probability of transmitting to any user converges to 1/n, irrespective of its path loss. In fact, using M=/spl alpha/logn transmit antennas emerges as a desirable operating point, both in terms of providing linear scaling of the throughput with M as well as in guaranteeing fairness.

The sum rate capacity of the multi-antenna broadcast channel has recently been computed. However, the search for efficient practical schemes that achieve it is still ongoing. In this paper, we focus on schemes with linear preprocessing of the transmitted data. We propose two criteria for precoding matrix design, one maximizing the sum rate and the other maximizing the minimum rate among all users. The latter problem is shown to be quasiconvex and is solved exactly via the bisection method. In addition to precoding, we employ a signal scaling scheme that minimizes average bit-error-rate (BER). The signal scaling scheme is posed as a convex optimization problem, and thus can be solved exactly via efficient interior-point methods. In terms of achievable sum rate, the proposed technique significantly outperforms traditional channel inversion methods, while having comparable (in fact, often superior) BER performance.

In this paper, we consider the scenario where many sensors co-operate to estimate a process. Only one sensor can take a measurement at any time step. We wish to come up with optimal sensor scheduling algorithms. The problem is motivated by the use of sonar range-finders used by the vehicles on the Caltech multi-vehicle wireless testbed. We see that this problem involves searching a tree in general and propose and analyze two strategies for pruning the tree to keep the computation limited. The first is a sliding window strategy motivated by the Viterbi algorithm, and the second one uses thresholding. We also study a technique that employs choosing the sensors randomly from a probability distribution which can then be optimized. The performance of the algorithms are illustrated with the help of numerical examples.

Fully diverse constellations, i.e., a set of unitary matrices whose pairwise differences are nonsingular, are useful in multi-antenna communications especially in multi-antenna differential modulation, since they have good pairwise error properties. Recently, group theoretic ideals, especially fixed-point-free (fpf) groups, have been used to design fully diverse constellations of unitary matrices. Here we give a systematic method to design space-time codes which are appropriate for three-transmit-antenna differential modulation. The structure of the code is motivated by the Lie group SU(3). The code has a fast decoding algorithm using sphere decode. The diversity product of the code can be easily calculated and simulated performance shows that the code is better than the group-based codes especially at high rates and is as good as the elaborately-designed nongroup code.

In this paper, we propose a method to reduce the peak to mean envelope power ratio (PMEPR) of multicarrier signals by modifying the constellation. For MPSK constellations, we minimize the maximum of the multicarrier signal over the sign and amplitude of each subcarrier. In order to find an efficient solution to the aforementioned non-convex optimization problem, we present a suboptimal solution by first optimizing over the signs using the result of M. Sharif et al. (2003), and then optimizing over the amplitudes given the signs. We prove that the minimization of the maximum of a multicarrier signal over the amplitude of each subcarrier can be written as a convex optimization problem with linear matrix inequality constraints. We also generalize the idea to other constellations such as 16QAM. Simulation results show that by an average power increase of 0.21 db and not sending information over the sign of each subcarrier, PMEPR can be decreased by 5.1 db for a system with 128 subcarriers.

We examine the problem of distributed estimation when only one sensor can take a measurement per time step. We solve for the optimal recursive estimation algorithm when the sensor switching schedule is given. We then consider the effect of noise in communication channels. We also investigate the problem of determining an optimal sensor switching strategy. We see that this problem involves searching a tree in general and propose two strategies for pruning the tree to minimize the computation. The first is a sliding window strategy motivated by the Viterbi algorithm, and the second one uses thresholding. The performance of the algorithms is illustrated using numerical examples.

We look at the power bandwidth trade-off in random sensory and ad-hoc wireless networks with n users and r/spl les/n/sup 1/2/ simultaneous source/destination pairs. Under a specific protocol, we show that the minimum power required for maintaining an achievable scaling law of R/sub sum/=/spl Theta/(f(n)) for the sum-rate in the network, scales like /spl Theta/(f(n)/n/sup 1/2/). The required bandwidth B in this case is of order /spl Theta/(f(n)/r). It is also proved that the minimum achievable energy per information bit (E/sub b//N/sub 0/)/sub min/ for this protocol, scales as /spl Theta/(1/n/sup 1/2/) and in this case the spectral efficiency is nonzero and is of constant order.

We determine the capacity of a certain class of wireless erasure relay networks. We first find a suitable definition for the "cut-capacity" of erasure networks with broadcast at transmission and no interference at reception. With this definition, a maxflow mincut capacity result holds for the capacity of these networks.

For the two-user Gaussian interference channel we show that, up to second order in the signal-to-noise ratio (SNR), the mutual information between each transmitter and intended receiver depends only on the covariance matrices of the input distributions. Our analysis suggests that in the low SNR regime there is an interference threshold above which it is better for the users to alternate signal transmission than to transmit simultaneously.

This paper derives scaling laws of the sum rate throughput for MIMO Gaussian broadcast channels using time-sharing to the strongest user, dirty paper coding (DPC), and beamforming when the number of users (receivers) n is large. Assuming a fixed total average transmit power, we show that for a system with M transmit antennas and users equipped with N antennas, the sum rate scales like M log log nTV for DPC and beamforming when M is fixed and for any N (either growing to infinity or not). On the other hand, when both M and TV are fixed, the sum rate of time-sharing to the strongest user scales like min(M,N) log log n. It is also shown that if M grows as logn, the sum rate of DPC and beamforming will grow linearly in M, but with different constant multiplicative factors. In this region, the sum rate capacity of time-sharing scales like N log log n.

We consider a single-antenna broadcast fading channel with n backlogged users. Assuming the transmission is packet-based, we define the delay as the minimum number of channel uses that guarantees all n users successfully receive m packets. A delay optimal strategy such as round-robin achieves the delay of mn. For the optimal throughput strategy (i.e. transmitting to the user with the best channel condition at each channel use), we derive the mean and variance of the delay for any m and n. For large n, it is proved that the expected delay in receiving the first packet in all users scales like n log n as opposed to n for the round-robin scheduling.

Maximum-likelihood (ML) decoding of linear block codes on a symmetric channel is studied. Exact ML decoding is known to be computationally difficult. We propose an algorithm that finds the exact solution to the ML decoding problem by performing a depth-first search on a tree. The tree is designed from the code generator matrix and pruned based on the statistics of the channel noise. The complexity of the algorithm is a random variable. We characterize the complexity by means of its first moment, which for binary symmetric channels we find in closed-form. The obtained results indicate that the expected complexity of the algorithm is low over a wide range of system parameters.

We apply the idea of space-time coding devised for multiple-antenna systems to the problem of communications over wireless relay networks. A two-stage protocol is used, where in one stage the transmitter sends information and in the other, the relay nodes encode their received signals into a "distributed" linear dispersion code, and then transmit the coded signals to the receiver. We show that for high SNR the proposed system has a diversity of order /spl alpha//sub 0/ min{T, R}, with T the coherence interval, R the number of relay nodes, and /spl alpha//sub 0/ the solution to the equation /spl alpha/ + log/spl alpha//logP = 1 - loglogP/logP, where P is the total transmit power in the network. In particular, we show that the pairwise error probability (PEP) decays no slower than (logP/P)/sup min{T,R}/. Thus, apart from the log P factor and assuming T /spl ges/ R, the system has the same diversity as a multiple-antenna system with R transmit antennas and one receive antenna, which is the same as assuming that the R relay nodes can fully cooperate and have full knowledge of the transmit signal. We further show that for a fixed total transmit power across the entire network, the optimal power allocation is for the transmitter to expend half the power and for the relays to collectively expend the other half. We also show that at low and high SNR, the coding gain is the same as that of multiple-antenna systems. However, at intermediate SNR, it can be quite different. We discuss some of the ramifications of using different space-time codes and finally verify our analysis through the simulation or randomly generated distributed space-time codes.

Fully diverse constellations, i.e., sets of unitary matrices whose pairwise differences are nonsingular, are useful in multiple-antenna communications, especially in multiple-antenna differential modulation, since they have good pairwise error properties. Recently, group theoretic ideas, especially fixed-point-free (fpf) groups, have been used to design fully diverse constellations of unitary matrices. Here we construct four-transmit-antenna constellations appropriate for differential modulation based on the symplectic group Sp(2). They can be regarded as extensions of Alamouti's celebrated two-transmit-antenna orthogonal design which can be constructed from the group Sp(1). We further show that the structure of Sp(2) codes lends itself to efficient maximum-likelihood (ML) decoding via the sphere decoding algorithm. Finally, the performance of Sp(2) codes is compared with that of other existing codes including Alamouti's orthogonal design, a 4/spl times/4 complex orthogonal design, Cayley differential unitary space-time codes and group-based codes.

Wireless channels with multiple transmit/receive antennas are known to provide a high spectral efficiency both when the channel is known to the receiver, and when the channel is not known to the receiver if the signal-to-noise ratio (SNR) is high. Here we analyze such systems at low SNR, which may find application in sensor networks and other low-power devices. The key point is that, since channel estimates are not reliable, it is often not reasonable to assume that the channel is known at the receiver at low SNR. In this unknown channel case, we show that for sensible input distributions, in particular all practical modulation schemes, the capacity is asymptotically quadratic in the SNR, /spl rho/, and thus much less than the known channel case where it exhibits a linear growth in /spl rho/. We show that under various signaling constraints, e.g., Gaussian modulation, unitary space-time modulation, and peak constraints, that mutual information is maximized by using a single transmit antenna. We also show that at low SNR, sending training symbols leads to a rate reduction in proportion to the fraction of training duration time so that it is best not to perform training. Furthermore, we show that the per-channel use mutual information is linear in both the number of receive antennas and the channel coherence interval.

Multicarrier signals exhibit a large peak-to-mean envelope power ratio (PMEPR). In this correspondence, without using a Gaussian assumption, we derive lower and upper probability bounds for the PMEPR distribution when the number of subcarriers n is large. Even though the worst case PMEPR is of the order of n, the main result is that the PMEPR of a random codeword C=(c/sub 1/,...,c/sub n/) is logn with probability approaching one asymptotically, for the following three general cases: i) c/sub i/'s are independent and identically distributed (i.i.d.) chosen from a complex quadrature amplitude modulation (QAM) constellation in which the real and imaginary part of c/sub i/ each has i.i.d. and even distribution (not necessarily uniform), ii) c/sub i/'s are i.i.d. chosen from a phase-shift keying (PSK) constellation where the distribution over the constellation points is invariant under /spl pi//2 rotation, and iii) C is chosen uniformly from a complex sphere of dimension n. Based on this result, it is proved that asymptotically, the Varshamov-Gilbert (VG) bound remains the same for codes with PMEPR of less than logn chosen from QAM/PSK constellations.

In recent years, soft iterative decoding techniques have been shown to greatly improve the bit error rate performance of various communication systems. For multiantenna systems employing space-time codes, however, it is not clear what is the best way to obtain the soft information required of the iterative scheme with low complexity. In this paper, we propose a modification of the Fincke-Pohst (sphere decoding) algorithm to estimate the maximum a posteriori probability of the received symbol sequence. The new algorithm solves a nonlinear integer least squares problem and, over a wide range of rates and signal-to-noise ratios, has polynomial-time complexity. Performance of the algorithm, combined with convolutional, turbo, and low-density parity check codes, is demonstrated on several multiantenna channels. The results for systems that employ space-time modulation schemes seem to indicate that the best performing schemes are those that support the highest mutual information between the transmitted and received signals, rather than the best diversity gain.

In many communications problems, maximum-likelihood (ML) decoding reduces to finding the closest (skewed) lattice point in N-dimensions to a given point x/spl isin/C/sup N/. In its full generality, this problem is known to be NP-complete and requires exponential complexity in N. Recently, the expected complexity of the sphere decoder, a particular algorithm that solves the ML problem exactly, has been computed; it is shown that, over a wide range of rates, SNRs and dimensions, the expected complexity is polynomial in N. We propose an algorithm that, for large N, offers substantial computational savings over the sphere decoder, while maintaining performance arbitrarily close to ML. The method is based on statistically pruning the search space. Simulations are presented to show the algorithm's performance and the computational savings relative to the sphere decoder.

Fully-diverse constellations, i.e., a set of unitary matrices whose pairwise differences are nonsingular, are useful in multi-antenna communications, especially in multi-antenna differential modulation, since they have good pairwise error properties. Recently, group theoretic ideas, especially fixed-point-free (FPF) groups, have been used to design fully-diverse constellations of unitary matrices. Here we construct four-transmit-antenna constellations appropriate for differential modulation based on the symplectic group Sp(2) These can be regarded as extensions of S.M. Alamouti's celebrated two-transmit-antenna orthogonal design which can be constructed from the group Sp(1) (see IEEE J. Sel. Area Commun., p.1451-8, 1998). We further show that the structure of the code lends itself to efficient maximum likelihood (ML) decoding via the sphere decoding algorithm. Finally, the performance of the code is compared with existing methods including Alamouti's scheme, Cayley differential unitary space-time codes and group based codes.

Multicarrier signals often exhibit large peak to mean envelope power ratios (PMEPR) which can be problematic in practice. In this paper, we study adjusting the sign of each subcarrier in order to reduce the PMEPR of a multicarrier signal with n subcarriers. Considering that any randomly chosen codeword has PMEPR of log n with probability one and for large values of n, randomly choosing signs should lead to the PMEPR of log n in the probability sense. Based on the derandomization algorithm suggested in Spencer (1994), we propose a deterministic and efficient algorithm to design signs such that the PMEPR of the resulting codeword is less than c log n for any n where c is a constant independent of n. By using a symmetric q-ary constellation, this algorithm in fact constructs a code with rate 1 - log/sub q/ 2, PMEPR of c log n, and with simple encoding and decoding. We then present simulation results for our algorithm.

In wireless communication systems, channel state information is often assumed to be available at the receiver. Traditionally, a training sequence is used to obtain the estimate of the channel. Alternatively, the channel can be identified using known properties of the transmitted signal. However, the computational effort required to find the joint ML solution to the symbol detection and channel estimation problem increases exponentially with the dimension of the problem. To significantly reduce this computational effort, we formulate the aforementioned problem in a way that makes it possible to solve it via the use of sphere decoding, an algorithm that has polynomial expected complexity. We also provide simulation results and a complexity discussion.

Maximum-likelihood (ML) detection problem for channels with memory is investigated. The Viterbi algorithm provides an elegant solution, but is computationally inefficient when employed for detection on long channels. On the other hand, sphere decoding solves the ML detection problem in polynomial expected time over a wide range of SNRs. The sphere-constrained search strategy of sphere decoding is combined with the dynamic programming principles of the Viterbi algorithm. The resulting algorithm has the worst-case complexity of the Viterbi algorithm, but significantly lower expected complexity.

Multiple subcarrier modulation (MSM) is an attractive technique for optical wireless communication for high speed applications. The main disadvantage of this scheme is its low average power efficiency which is in an analogous problem to the high peak to mean envelope power ratio (PMEPR) of multicarrier signals. In this paper, we consider the achievable average power reduction of MSM signals by using optimized reserved carriers and coding methods. Based on Nehari's result we present a lower bound for maximum average power of the signal after adding the reserved carriers. It is shown that the mean value of the average required power behaves very close to /spl radic/(2n log log n) for a BPSK constellation where n is the number of subcarriers. We then consider finding the optimum values for the carriers and the effect of having finite bandwidth for reserved carriers. In the next section, mainly based on recent coding results for PMEPR of multicarrier signals, we show the existence of very high rate codes with average power of O(/spl radic/(n log n)) for large values of n, and furthermore the existence of codes with non-vanishing to zero rate and the average power of O(/spl radic/n) asymptotically.

Multiple-antenna wireless communication links promise very high data rates with low error probabilities, especially when the wireless channel response is known at the receiver. In practice, knowledge of the channel is often obtained by sending known training symbols to the receiver. We show how training affects the capacity of a fading channel-too little training and the channel is improperly learned, too much training and there is no time left for data transmission before the channel changes. We compute a lower bound on the capacity of a channel that is learned by training, and maximize the bound as a function of the received signal-to-noise ratio (SNR), fading coherence time, and number of transmitter antennas. When the training and data powers are allowed to vary, we show that the optimal number of training symbols is equal to the number of transmit antennas-this number is also the smallest training interval length that guarantees meaningful estimates of the channel matrix. When the training and data powers are instead required to be equal, the optimal number of symbols may be larger than the number of antennas. We show that training-based schemes can be optimal at high SNR, but suboptimal at low SNR.

[Guest Editors introduction to: Special issue on space-time transmission, reception, coding and signal processing] \n \nEvery episode of the classic 1966–1969 television series Star Trek begins with Captain Kirk’s (played by William Shatner) famous words : “Space: The final frontier….” While space may not be the final frontier for the information and communication theory community, it is proving to be an important and fruitful one. \n \nIn the information theory community, the notion of space can be broadly defined as the simultaneous use of multiple, possibly coupled, channels. The notions of space–time and multiple-input multiple-output (MIMO) channels are therefore often used interchangeably. The connection between space and MIMO is most transparent when we view the multiple channels as created by two or more spatially separated antennas at a wireless transmitter or receiver. \n \nA large component of the current interest in space–time methods can be attributed to discoveries in the late 1980s and early 1990s that a rich wireless scattering environment can be beneficial when multiple antennas are used on a point-to-point link. We now know that adding antennas in a rich environment provides proportional increases in point-to-point data rates, without extra transmitted power or bandwidth.

Multiple antenna differential modulation using unitary matrices requires no channel knowledge at the receiver, and so is ideal for use on wireless links where channel tracking is undesirable or infeasible, either because of rapid changes in the channel characteristics or because of limited system resources. Although this basic principle is well understood, it is not known how to generate good-performing constellations of unitary matrices, for any number of transmit and receive antennas and especially at high rates. We propose a class of Cayley codes that works with any number of antennas, and allows for polynomial-time near-maximum-likelihood decoding based on either successive nulling/cancelling or sphere decoding. The codes use the Cayley transform, which maps the highly nonlinear Stiefel manifold of unitary matrices to the linear space of skew-Hermitian matrices. This leads to a simple linear constellation structure in the Cayley transform domain and to an information-theoretic design criterion based on emulating a Cauchy random matrix. Simulations show that Cayley codes allow efficient and effective high-rate data transmission in multi-antenna communication systems without knowing the channel.

A recently proposed method for communicating with multiple antennas over block fading channels is unitary space-time modulation (USTM), so-called because the transmitted signals form a matrix with orthonormal columns. Since channel knowledge is not required at the receiver, USTM schemes are suitable for use on wireless links where channel tracking is undesirable or infeasible. Recent results have shown that, if suitably designed, USTM schemes can achieve full channel capacity at high SNR. While all this is well recognized, what is not clear is how to generate good performing constellations of (non-square) unitary matrices, that lend themselves to efficient encoding/decoding. The schemes proposed so far either exhibit poor performance, especially at high rates, or have no efficient decoding algorithms. In this paper, we propose to use the Cayley transform to design USTM constellations. This work is a generalization, to the non-square case, of the Cayley codes that have been proposed for differential USTM. The codes are designed based on an information-theoretic criterion, and lend themselves to polynomial-time (often cubic) near-maximum-likelihood decoding using a sphere decoding algorithm.

The problem of finding the least-squares solution to a system of linear equations where the unknown vector is comprised of integers, but the matrix coefficient and given vector are comprised of real numbers, arises in many applications: communications, cryptography, GPS, to name a few. The problem is equivalent to finding the closest lattice point to a given point and is known to be NP-hard. In communications applications, however, the given vector is not arbitrary, but rather is an unknown lattice point that has been perturbed by an additive noise vector whose statistical properties are known. Therefore in this paper, rather than dwell on the worst-case complexity of the integer-least-squares problem, we study its expected complexity, averaged over the noise and over the lattice. For the “sphere decoding” algorithm of Fincke and Pohst we find a closed-form expression for the expected complexity and show that for a wide range of noise variances the expected complexity is polynomial, in fact often sub-cubic. Since many communications systems operate at noise levels for which the expected complexity turns out to be polynomial, this suggests that maximum-likelihood decoding, which was hitherto thought to be computationally intractable, can in fact be implemented in realtime—a result with many practical implications.

In recent years, soft iterative decoding techniques have been shown to greatly improve the bit error rate performance of various communication systems. For multiple antenna systems, however, it is not clear what is the best way to obtain the soft-information required of the iterative scheme with low complexity. In this paper, we propose a modification of the Fincke-Pohst (sphere decoder) algorithm to estimate the MAP probability of the received symbol sequence. The new algorithm solves a nonlinear integer leasts-quares problem and, over a wide range of rates and SNRs, has polynomial-time (often cubic) complexity. The performance of the algorithm, combined with convolutional, turbo, and LDPC codes is demonstrated on several multiple antenna channels.

One method for communicating with multiple antennas is to encode the transmitted data differentially using unitary matrices at the transmitter, and to decode differentially without knowing the channel coefficients at the receiver. Since channel knowledge is not required at the receiver, differential schemes are ideal for use on wireless links where channel tracking is undesirable or infeasible, either because of rapid changes in the channel characteristics or because of limited system resources. Although this basic principle is well understood, it is not known how to generate good-performing constellations of unitary matrices, for any number of transmit and receive antennas and for any rate. This is especially true at high rates where the constellations must be rapidly encoded and decoded. We propose a class of Cayley codes that works with any number of antennas, and has efficient encoding and decoding at any rate. The codes are named for their use of the Cayley transform, which maps the highly nonlinear Stiefel manifold of unitary matrices to the linear space of skew-Hermitian matrices. This transformation leads to a simple linear constellation structure in the Cayley transform domain and to an information-theoretic design criterion based on emulating a Cauchy random matrix. Moreover, the resulting Cayley codes allow polynomial-time near-maximum-likelihood (ML) decoding based on either successive nulling/canceling or sphere decoding. Simulations show that the Cayley codes allow efficient and effective high-rate data transmission in multiantenna communication systems without knowing the channel.

Multiple-antenna systems that operate at high rates require simple yet effective space-time transmission schemes to handle the large traffic volume in real time. At rates of tens of bits per second per hertz, Vertical Bell Labs Layered Space-Time (V-BLAST), where every antenna transmits its own independent substream of data, has been shown to have good performance and simple encoding and decoding. Yet V-BLAST suffers from its inability to work with fewer receive antennas than transmit antennas-this deficiency is especially important for modern cellular systems, where a base station typically has more antennas than the mobile handsets. Furthermore, because V-BLAST transmits independent data streams on its antennas there is no built-in spatial coding to guard against deep fades from any given transmit antenna. On the other hand, there are many previously proposed space-time codes that have good fading resistance and simple decoding, but these codes generally have poor performance at high data rates or with many antennas. We propose a high-rate coding scheme that can handle any configuration of transmit and receive antennas and that subsumes both V-BLAST and many proposed space-time block codes as special cases. The scheme transmits substreams of data in linear combinations over space and time. The codes are designed to optimize the mutual information between the transmitted and received signals. Because of their linear structure, the codes retain the decoding simplicity of V-BLAST, and because of their information-theoretic optimality, they possess many coding advantages. We give examples of the codes and show that their performance is generally superior to earlier proposed methods over a wide range of rates and signal-to-noise ratios (SNRs).

An important open problem in multiple-antenna communications theory is to compute the capacity of a wireless link subject to flat Rayleigh block-fading, with no channel-state information (CSI) available either to the transmitter or to the receiver. The isotropically random (i.r.) unitary matrix-having orthonormal columns, and a probability density that is invariant to premultiplication by an independent unitary matrix-plays a central role in the calculation of capacity and in some special cases happens to be capacity-achieving. We take an important step toward computing this capacity by obtaining, in closed form, the probability density of the received signal when transmitting i.r. unitary matrices. The technique is based on analytically computing the expectation of an exponential quadratic function of an i.r. unitary matrix and makes use of a Fourier integral representation of the constituent Dirac delta functions in the underlying density. Our formula for the received signal density enables us to evaluate the mutual information for any case of interest, something that could previously only be done for single transmit and receive antennas. Numerical results show that at high signal-to-noise ratio (SNR), the mutual information is maximized for M=min(N, T/2) transmit antennas, where N is the number of receive antennas and T is the length of the coherence interval, whereas at low SNR, the mutual information is maximized by allocating all transmit power to a single antenna.

We previously showed that arbitrarily reliable communication is possible within a single coherence interval in Rayleigh flat fading as the symbol duration of the coherence interval and the number of transmit antennas grow simultaneously. This effect, where the space-time signals act as their own channel codes, is called autocoding. For relatively short (e.g., 16-symbol) coherence intervals, a codebook of independent isotropically random unitary space-time signals theoretically supports transmission rates that are a significant fraction of autocapacity with an extremely low probability of error. The exploitation of space-time autocoding requires the creation and decoding of extraordinarily large constellations-typically L = 2/sup 80/. We make progress on the first part of the problem through a random, but highly structured, constellation that is completely specified by log/sub 2/ L independent isotropically distributed unitary matrices. The distinguishing property of this construction is that any two signals in the constellation are pairwise statistically independent and isotropically distributed. Thus, the pairwise probability of error, and hence the union bound on the block probability of error, of the structured constellation is identical to that of a fully random constellation of independent signals. We establish the limitations of an earlier construction through a subsidiary result that is interesting in its own right: the square (or for that matter, any integer power greater than one) of an isotropically random unitary matrix is not isotropically random, with the sole exception of the one-by-one unitary matrix.

Multiple-antenna systems that operate at high rates require simple yet effective space-time transmission schemes to handle the large traffic volume in real time. V-BLAST, where every antenna transmits its own independent substream of data, has been shown to have good performance and simple encoding and decoding. Yet its drawbacks include its inability to work with fewer receive antennas than transmit antennas, and its absence of built-in spatial coding. On the other hand, there are many previously-proposed space-time codes that have good fading resistance and simple decoding, but generally poor performance at high data rates or with many antennas. We propose a high-rate coding scheme that can handle any configuration of transmit and receive antennas and that subsumes both V-BLAST (Vertical Bell Labs Layered Space-Time) and many proposed space-time codes as special cases. The scheme transmits substreams of data in linear combinations over space and time and the codes are designed to optimize the mutual information between the transmitted and received signals. Because of their linear structure, the codes retain the decoding simplicity of V-BLAST, and because of their information-theoretic optimality, they possess many coding advantages.

Many communications systems employ training, ie, the transmission of known signals, so that the channel parameters may be learned at the receiver. This has a dual effect: too little training and the channel is improperly learned, too much training and there is no time left for data transmission before the channel changes. We use an information-theoretic approach to find the optimal amount of training for frequency selective channels described by a block-fading model. When the training and data powers are allowed to vary, we show that the optimal number of training symbols is equal to the length of the channel impulse response. When the training and data powers are instead required to be equal, the optimal number of symbols may be larger. We further show that at high SNR training-based schemes are capable of capturing most of the channel capacity, whereas at low SNR they are highly suboptimal.

We approach finite impulse response (FIR) equalization problem from an H ∞ perspective. First, we formulate the calculation of the optimal H ∞ performance for a given equalization setting as a semidefinite programming (SDP) problem. H ∞ criterion provides a set of FIR equalizers with different optimality properties. Among these, we formulate the calculation of risk-sensitive or minimum entropy FIR filter as the constrained analytic centring problem and mixed H 2 / H ∞ problem as another SDP. We provide examples to illustrate the procedures we described.

Prior treatments of space-time communications in Rayleigh flat fading generally assume that channel coding covers either one fading interval-in which case there is a nonzero "outage capacity"-or multiple fading intervals-in which case there is a nonzero Shannon capacity. However, we establish conditions under which channel codes span only one fading interval and yet are arbitrarily reliable. In short, space-time signals are their own channel codes. We call this phenomenon space-time autocoding, and the accompanying capacity the space-time autocapacity. Let an M-transmitter antenna, N-receiver antenna Rayleigh flat fading channel be characterized by an M×N matrix of independent propagation coefficients, distributed as zero-mean, unit-variance complex Gaussian random variables. This propagation matrix is unknown to the transmitter, it remains constant during a T-symbol coherence interval, and there is a fixed total transmit power. Let the coherence interval and number of transmitter antennas be related as T=βM for some constant β. A T×M matrix-valued signal, associated with R·T bits of information for some rate R is transmitted during the T-symbol coherence interval. Then there is a positive space-time autocapacity Ca such that for all R

Multiple antennas can greatly increase the data rate and reliability of a wireless communication link in a fading environment, but the practical success of using multiple antennas depends crucially on our ability to design high-rate space-time constellations with low encoding and decoding complexity. It has been shown that full transmitter diversity, where the constellation is a set of unitary matrices whose differences have nonzero determinant, is a desirable property for good performance. We use the powerful theory of fixed-point-free groups and their representations to design high-rate constellations with full diversity. Furthermore, we thereby classify all full-diversity constellations that form a group, for all rates and numbers of transmitter antennas. The group structure makes the constellations especially suitable for differential modulation and low-complexity decoding algorithms. The classification also reveals that the number of different group structures with full diversity is very limited when the number of transmitter antennas is large and odd. We, therefore, also consider extensions of the constellation designs to nongroups. We conclude by showing that many of our designed constellations perform excellently on both simulated and real wireless channels.

We approach FIR equalization problem from an H∞ perspective. \nFirst, we formulate the calculation of the optimal H∞ performance for a given equalization setting as a semidefinite programming (SDP) problem. H∞ criterion provides a set of FIR equalizers with different optimality properties. \nAmong \nthese, \nwe \nformulate \nthe \ncalculation \nof risk sensitive \nor \nminimum \nentropy \nFIR \nfilter \nas \nthe \nconstrained analytic centring \nproblem \nand \nmixed \nH2/H" \nproblem \nas \nanother \nSDP. We \nprovide an \nexample \nto \nil- \nlustrate the \nprocedures \nwe \ndescribed.

Bell Labs Layered Space-Time (BLAST) is a scheme for transmitting information over a rich-scattering wireless environment using multiple receive and transmit antennas. The main computational bottleneck in the BLAST algorithm is a "nulling and cancellation" step, where the optimal ordering for the sequential estimation and detection of the received signals is determined. To reduce the computational cost of BLAST, we develop an efficient square-root algorithm for the nulling and cancellation step. The main features of the algorithm include efficiency: the computational cost is reduced by 0.7 M, where M is the number of transmit antennas, and numerical stability: the algorithm is division-free and uses only orthogonal transformations. In a 14 antenna system designed for transmission of 1 Mbit/s over a 30 kHz channel, the nulling and cancellation computation is reduced from 190 MFlops/s to 19 MFlops/s, with the overall computations being reduced from 220 MFlops/s to 49 MFlops/s. The numerical stability of the algorithm also make it attractive for implementation in fixed-point (rather than floating-point) architectures.

We study the design of synthesis filters in noisy filter bank systems using an H/sup /spl infin// estimation point of view. The H/sup /spl infin// approach is most promising in situations where the statistical properties of the disturbances (arising from quantization, compression, etc.) in each subband of the filter bank are unknown, or are too difficult to model and analyze. For arbitrary analysis polyphase matrices, standard state-space H/sup /spl infin// techniques can be employed to obtain numerical solutions. When the synthesis filters are restricted to being FIR, as is often the case in practice, the design can be cast as a finite-dimensional semi-definite program. In this case, we can effectively exploit the inherent non-uniqueness of the H/sup /spl infin// solution to optimize for an additional average performance and thus obtain mixed H/sup 2//H/sup /spl infin// optimal FIR synthesis filters.

The paper proposes and investigates a new approach to adaptive spatio-temporal equalization for MIMO (multiple-input multiple-output) channels. A system with n transmit and m (m/spl ges/n) receiver antennas is assumed. A decision feedback equalizer is considered. A least squares solution is first formulated, based on which a recursive solution using Riccati recursions is proposed. The proposed solution is tested by simulating the MIMO system. It is shown that the adaptive solution achieves the same performance as the optimum least squares solution. The effect of the nondiagonal channel elements (acting as interference) on the system performance is also studied. It has been shown that in order to achieve better performance, the interference from nondiagonal channel elements needs to be minimized. This can be done by using orthogonal transmission. Moreover the proposed solution do not require channel identification and will also enable equalizer adaptation to channel changes.

We construct signal constellations for differential transmission with multiple basestation antennas. The signals are derived using the theory of fixed-point-free groups and are especially suitable for mobile cellular applications because they do not require the handset to have more than one antenna or to know the time-varying propagation environment. Yet we achieve full transmitter diversity and excellent performance gains over a single-antenna system.

We study the design of synthesis filters in noisy filter bank systems using an H/sup /spl infin// point of view. For unitary analysis polyphase matrices we obtain an explicit expression for the minimum achievable disturbance attenuation. Numerical examples and comparisons with existing methods are also included.

As an alternative to existing techniques and algorithms, we investigate the merit of the H-infinity approach to the equalization of communication channels. We first look at causal H-infinity equalization problem and then look at the improvement due to finite delay. By introducing the risk sensitive property, we compare the average performance of the central H-infinity equalizer with the MMSE equalizer in equalizing minimum phase channels.

We study the relation between the solutions of two estimation problems with indefinite quadratic forms. We show that a complete link between both solutions can be established by invoking a fundamental set of inertia conditions. While these inertia conditions are automatically satisfied in a standard Hilbert space setting, they nevertheless turn out to mark the differences between the two estimation problems in indefinite metric spaces. They also include, as special cases, the well-known conditions for the existence of H/sup -/spl infin//-filters and controllers. Given two Hermitian matrices {/spl Pi/, W}, a column vector y, and an arbitrary matrix A of appropriate dimensions, we study the relation between two minimization problems with quadratic cost functions, and also refer to the indefinite-weighted least-squares problem.

H/sup /spl infin// optimal estimators guarantee the smallest possible estimation error energy over all possible disturbances of fixed energy, and are therefore robust with respect to model uncertainties and lack of statistical information on the exogenous signals. We have shown that if the prediction error is considered, then the celebrated LMS adaptive filtering algorithm is H/sup /spl infin// optimal. We consider prediction of the filter weight vector itself, and for the purpose of coping with time-variations, exponentially weighted, finite-memory and time-varying adaptive filtering. This results in some new adaptive filtering algorithms that may be useful in uncertain and non-stationary environments. Simulation results are given to demonstrate the feasibility of the algorithms and to compare them with well-known H/sup 2/ (or least-squares based) adaptive filters.

In this communication, necessary and sufficient conditions are presented for the unique blind identification of possibly nonminimum phase channels driven by cyclostationary processes. Using a frequency domain formulation, it is first shown that a channel can be identified by the second-order statistics of the observation if and only if the channel transfer function does not have special uniformly spaced zeros. This condition leads to several necessary and sufficient conditions on the observation spectra and the channel impulse response. Based on the frequency-domain formulation, a new identification algorithm is proposed.>