Search

In this paper we consider a distributed convex optimization problem over time-varying networks. We propose a dual method that converges R-linearly to the optimal point given that the agents' objective functions are strongly convex and have Lipschitz continuous gradients. The proposed method requires half the amount of variable exchanges per iterate than methods based on DIGing, and yields improved practical performance as empirically demonstrated., Submitted to the 57th IEEE Conference on Decision and Control (CDC) 2018

This paper shows the capability of the alternating direction method of multipliers (ADMM) to track, in a distributed manner, the optimal down-link beam-forming solution in a multiple-input single-output multicell network given a dynamic channel. Each time the channel changes, ADMM is allowed to perform one algorithm iteration. In order to implement the proposed scheme, the base stations are not required to exchange channel state information. They will, however, be required to exchange interference values once. We show ADMM's tracking ability in terms of the algorithm's Lyapunov function. This is shown given that the primal and dual solutions to the convex optimization problem at hand can be understood as a continuous mapping from the problem's parameters. We show that this holds true even considering that the problem loses strong convexity when it is made distributed. We then show that these requirements hold for the down-link, and consequently the up-link, beam-forming case. Numerical examples corroborating the theoretical findings are also provided.

We provide a comprehensive performance comparison of soft-output and hard-output demodulators in the context of non-iterative multiple-input multiple-output bit-interleaved coded modulation (MIMO-BICM). Coded bit error rate (BER), widely used in literature for demodulator comparison, has the drawback of depending strongly on the error correcting code being used. This motivates us to propose the mutual information of the equivalent modulation channel (comprising modulator, wireless channel, and demodulator) as a code-independent performance measure. We present extensive numerical results for spatially independent identically distributed (i.i.d.) ergodic and quasi-static fading channels under perfect and imperfect channel state information. These results reveal that the performance ranking of MIMO demodulators is rate-dependent and provide new insights regarding MIMO-BICM system design, i.e., the choice of antenna configuration, symbol constellation, and demodulator for a given target rate.

The problem of finding the least squares solution s to a system of equations Hs = y is considered, when s is a vector of binary variables and the coefficient matrix H is unknown but of bounded uncertainty. Similar to previous approaches to robust binary least squares, we explore the potential of a min-max design with the aim to provide solutions that are less sensitive to the uncertainty in H. We concentrate on the important case of ellipsoidal uncertainty, i.e., the matrix H is assumed to be a deterministic unknown quantity which lies in a given uncertainty ellipsoid. The resulting problem is NP-hard, yet amenable to convex approximation techniques: Starting from a convenient reformulation of the original problem, we propose an approximation algorithm based on semidefinite relaxation that explicitly accounts for the ellipsoidal uncertainty in the coefficient matrix. Next, we show that it is possible to construct a tighter relaxation by suitably changing the description of the feasible region of the problem, and formulate an approximation algorithm that performs better in practice. Interestingly, both relaxations are derived as Lagrange bidual problems corresponding to the two equivalent problem reformulations. The strength of the proposed tightened relaxation is demonstrated by pertinent simulations.

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

In this letter, the linear predictability of discrete-time stationary stochastic processes with 1/|f|α-shaped power spectral density (PSD) is considered. In particular, the spectral flatness measure (SFM)-which yields a lower bound for the normalized mean-squared-error (NMSE) of any linear one-step-ahead (OSA) predictor-is obtained analytically as a function of α ∈ [0, 1]. By comparing the SFM bound to the NMSE of the p -tap linear minimum-mean-square error (LMMSE) predictor, it is shown that close to optimal NMSE performance may be achieved for relatively moderate values of p. The performance of the LMMSE predictor for the discrete-time fractional Gaussian noise (DFGN), which may be viewed as the conventional discrete-time counterpart of continuous-time processes with 1/|f|α-shaped PSD, shows that the DFGN is more easily predicted than the discrete-time processes considered herein.

In multiple-input multiple-output (MIMO) spatial multiplexing systems, maximum-likelihood (ML) detection achieves maximum diversity at the cost of high computational complexity. In contrast, low-complexity alternatives like zero-forcing (ZF) detection suffer from a significant diversity loss. In this paper, we present a novel detection scheme that allows a continuous tradeoff between diversity order and complexity reduction. The proposed detector consists of two stages: the first stage is a linear pre-equalizer that partially eliminates MIMO interference and improves the channel condition number; the second stage is a mismatched ML detector on the residual channel that ignores the correlation introduced by the equalization stage. This second stage is implemented using a variant of the sphere decoder. ML and ZF detection are extreme special cases of our novel scheme. We give insights into the main effects that determine performance and we provide an explicit expression for the diversity order achieved with the proposed detector. Simulation results confirm that our scheme allows to trade diversity for complexity savings in a continuous manner.

The fixed-complexity sphere decoder (FSD) has been previously proposed for multiple-input multiple-output (MIMO) detection in order to overcome the two main drawbacks of the sphere decoder (SD), namely its variable complexity and its sequential structure. Although the FSD has shown remarkable quasi-maximum-likelihood (ML) performance and has resulted in a highly optimized real-time implementation, no analytical study of its performance existed for an arbitrary MIMO system. Herein, the error probability of the FSD is analyzed, proving that it achieves the same diversity as the maximum-likelihood detector (MLD) independent of the constellation used. In addition, it can also asymptotically yield ML performance in the high-signal-to-noise ratio (SNR) regime. Those two results, together with its fixed complexity, make the FSD a very promising algorithm for uncoded MIMO detection.

We consider the problem of estimating a deterministic unknown vector which depends linearly on noisy measurements, additionally contaminated with (possibly unbounded) additive outliers. The measurement matrix of the model (i.e., the matrix involved in the linear transformation of the sought vector) is assumed known, and comprised of standard Gaussian i.i.d. entries. The outlier variables are assumed independent of the measurement matrix, deterministic or random with possibly unknown distribution. Under these assumptions we provide a simple proof that the minimizer of the Huber penalty function of the residuals converges to the true parameter vector with a root n-rate, even when outliers are dense, in the sense that there is a constant linear fraction of contaminated measurements which can be arbitrarily close to one. The constants influencing the rate of convergence are shown to explicitly depend on the outlier contamination level. QC 20140806

The signal-to-noise ratio (SNR) estimation problem is considered for an amplitude modulated known signal in Gaussian noise. The benchmark method is the maximum-likelihood estimator (MLE), whose merits are well-documented in the literature. In this work, an affinely modified version of the MLE (AMMLE) that uniformly outperforms, over all SNR values, the traditional MLE in terms of the mean-square error (MSE) is obtained in closed-form. However, construction of an AMMLE whose MSE is lower, at every SNR, than the unbiased Cramer-Rao bound (UCRB), is shown to be infeasible. In light of this result, the AMMLE construction rule is modified to provision for an a priori known set, where the SNR lies, and the MSE enhancement target is pursued within. The latter is realized through proper extension of an existing framework, due to Eldar, which settles the design problem by solving a semidefinite program. The analysis is further extended to the general case of vector signal models. Numerical results show that the proposed design demonstrates enhancement of the MSE for all the considered cases. QC 20140227. Updated from accepted to published.

This paper considers lattice decoding for multi-input multi-output (MIMO) detection under PAM constellations. A key aspect of lattice decoding is that it relaxes the symbol bound constraints in the optimal maximum-likelihood (ML) detector for faster implementations. It is known that such a symbol bound relaxation may lead to a damaging effect on the system performance. For this reason, regularization was proposed to mitigate the out-of-bound symbol effects in lattice decoding. However, minimum mean square error (MMSE) regularization is the only method of choice for regularization in the present literature. We propose a systematic regularization optimization approach considering a Lagrangian dual relaxation (LDR) of the ML detection problem. As it turns out, the proposed LDR formulation is to find the best diagonally regularized lattice decoder to approximate the ML detector, and all diagonal regularizations, including the MMSE regularization, can be subsumed under the LDR formalism. We show that for the 2-PAM case, strong duality holds between the LDR and ML problems. Also, for general PAM, we prove that the LDR problem yields a duality gap no worse than that of the well-known semidefinite relaxation method. To physically realize the proposed LDR, the projected subgradient method is employed to handle the LDR problem so that the best regularization can be found. The resultant method can physically be viewed as an adaptive symbol bound control wherein regularized lattice decoding is recursively performed to correct the decision. Simulation results show that the proposed LDR approach can outperform the conventional MMSE-based lattice decoding approach.

Recent work in [1]-[3] quantified, in the form of a complexity exponent, the computational resources required for ML and lattice sphere decoding to achieve a certain diversity-multiplexing performance. For a specific family of layered lattice designs, and a specific set of decoding orderings, this complexity was shown to be an exponential function in the number of codeword bits, and was shown to meet a universal upper bound on complexity exponents. The same results raised the question of whether complexity reductions away from the universal upper bound are feasible, for example, with a proper choice of decoder (ML vs lattice), or with a proper choice of lattice codes and decoding ordering policies. The current work addresses this question by first showing that for almost any full-rate DMT optimal lattice code, there exists no decoding ordering policy that can reduce the complexity exponent of ML or lattice based sphere decoding away from the universal upper bound, i.e., that a randomly picked lattice code (randomly and uniformly drawn from an ensemble of DMT optimal lattice designs) will almost surely be such that no decoding ordering policy can provide exponential complexity reductions away from the universal upper bound. As a byproduct of this, the current work proves the fact that ML and (MMSE-preprocessed) lattice decoding share the same complexity exponent for a very broad setting, which now includes almost any DMT optimal code (again randomly drawn) and all decoding order policies. Under a basic richness of codes assumption, this is in fact further extended to hold, with probability one, over all full-rate codes. Under the same assumption, the result allows for a meaningful rate-reliability-complexity tradeoff that holds, almost surely in the random choice of the full-rate lattice design, and which holds irrespective of the decoding ordering policy. This tradeoff can be used to, for example, describe the optimal achievable diversity gain of ML or lattice sphere decoding in the presence of limited computational resources.

Conjoint analysis (CA) is a classical tool used in preference assessment, where the objective is to estimate the utility function of an individual, or a group of individuals, based on expressed preference data. An example is choice-based CA for consumer profiling, i.e., unveiling consumer utility functions based solely on choices between products. A statistical model for choice-based CA is investigated in this paper. Unlike recent classification-based approaches, a sparsity-aware Gaussian maximum likelihood (ML) formulation is proposed to estimate the model parameters. Drawing from related robust parsimonious modeling approaches, the model uses sparsity constraints to account for outliers and to detect the salient features that influence decisions. Contributions include conditions for statistical identifiability, derivation of the pertinent Cramer-Rao Lower Bound (CRLB), and ML consistency conditions for the proposed sparse nonlinear model. The proposed ML approach lends itself naturally to l1-type convex relaxations which are well-suited for distributed implementation, based on the alternating direction method of multipliers (ADMM). A particular decomposition is advocated which bypasses the apparent need for outlier communication, thus maintaining scalability. The performance of the proposed ML approach is demonstrated by comparing against the associated CRLB and prior state-of-the-art using both synthetic and real data sets.

Recent literature on robust statistical inference suggests that promising outlier rejection schemes can be based on accounting explicitly for sparse gross errors in the modeling, and then relying on compressed sensing ideas to perform the outlier detection. In this paper,we consider two models for recovering a sparse signal from noisy measurements, possibly also contaminated with outliers. The models considered here are a linear regression model, and its natural onebit counterpart where measurements are additionally quantized to a single bit. Our contributions can be summarized as follows: We start by providing conditions for identification and the Cramer-Rao Lower Bounds (CRLBs) for these two models. Then, focusing on the one-bit model, we derive conditions for consistency of the associated Maximum Likelihood estimator, and show the performance of relevant ell1-based relaxation strategies by comparing against the theoretical CRLB. QC 20131210

A new statistical model for choice-based conjoint analysis is proposed. The model uses auxiliary variables to account for outliers and to detect the salient features that influence decisions. Unlike recent classification-based approaches to choice-based conjoint analysis, a sparsity-aware maximum likelihood (ML) formulation is proposed to estimate the model parameters. The proposed approach is conceptually appealing, mathematically tractable, and is also well-suited for distributed implementation. Its performance is tested and compared to the prior state-of-art using synthetic as well as real data coming from a conjoint choice experiment for coffee makers, with very promising results. QC 20121123

This work identifies the first lattice decoding solution that achieves, in the most general outage-limited MIMO setting and the high rate and high SNR limit, both a vanishing gap to the error-performance of the exact solution of regularized lattice decoding, as well as a computational complexity that is subexponential in the number of codeword bits as well as the rate. The proposed solution employs lattice reduction (LR)-aided regularized (lattice) sphere decoding and proper timeout policies. In light of the fact that, prior to this work, a vanishing gap was generally attributed only to full lattice searches that have exponential complexity, in conjunction with the fact that subexponential complexity was generally attributed to early-terminated (linear) solutions which have though a performance gap that can be up to exponential in dimension and/or rate, the work constitutes the first proof that subexponential complexity need not come at the cost of exponential reductions in lattice decoding error performance. Finally, these performance and complexity guarantees hold for the most general MIMO setting, for all reasonable fading statistics, all channel dimensions, and all lattice codes.

We consider the complexity of the sphere decoding (SD) algorithm when decoding a class of full rate space-time block codes that are optimal, over the quasi-static MIMO channel, with respect to the diversity-multiplexing tradeoff (DMT). Towards this we introduce the SD complexity exponent which represents the high signal-to-noise ratio (SNR) exponent of the tightest run-time complexity constraints that can be imposed on the SD algorithm while maintaining arbitrarily close to maximum likelihood (ML) performance. Similar to the DMT exposition, our approach naturally captures the dependence of the SD algorithm's computational complexity on the codeword density, code size and channel randomness, and provides simple closed form solutions in terms of the system dimensions and the multiplexing gain.

Exploiting prior knowledge, we use Bayesian estimation to localize a source heard by a fixed sensor network. The method has two main aspects: Firstly, the probability density function (PDF) of a function of the source location is approximated by a Gaussian mixture model (GMM). This approximation can theoretically be made arbitrarily accurate, and allows a closed form minimum mean square error (MMSE) estimator for that function. Secondly, the source location is retrieved by minimizing the Euclidean distance between the function and its MMSE estimate using a gradient method. Our method avoids the issues of a numerical MMSE estimator but shows comparable accuracy.

Finding the least squares (LS) solution s to a system of linear equations Hs = y where H, y are given and s is a vector of binary variables, is a well known NP-hard problem. In this paper, we consider binary LS problems under the assumption that the coefficient matrix H is also unknown, and lies in a given uncertainty ellipsoid. We show that the corresponding worst-case robust optimization problem, although NP-hard, is still amenable to semidefinite relaxation (SDR)-based approximations. However, the relaxation step is not obvious, and requires a certain problem reformulation to be efficient. The proposed relaxation is motivated using Lagrangian duality and simulations suggest that it performs well, offering a robust alternative over the traditional SDR approaches for binary LS problems.

In the setting of quasi-static multiple-input multiple-output (MIMO) channels, we consider the high signal-to-noise ratio (SNR) asymptotic complexity required by the sphere decoding (SD) algorithm for decoding a large class of full rate linear space-time codes. With SD complexity having random fluctuations induced by the random channel, noise and codeword realizations, the introduced SD complexity exponent manages to concisely describe the computational reserves required by the SD algorithm to achieve arbitrarily close to optimal decoding performance. Bounds and exact expressions for the SD complexity exponent are obtained for the decoding of large families of codes with arbitrary performance characteristics. For the particular example of decoding the recently introduced threaded cyclic division algebra (CDA) based codes -- the only currently known explicit designs that are uniformly optimal with respect to the diversity multiplexing tradeoff (DMT) -- the SD complexity exponent is shown to take a particularly concise form as a non-monotonic function of the multiplexing gain. To date, the SD complexity exponent also describes the minimum known complexity of any decoder that can provably achieve a gap to maximum likelihood (ML) performance which vanishes in the high SNR limit., 19 Pages, 4 figures. Submitted to the IEEE Transactions on Information Theory

We investigate the predictability of RF oscillator phase noise (PHN) when a higher order model than the Wiener process is considered. The increment of the PHN process, i.e., the frequency fluctuation, is modeled as the superposition of a stationary 1/fα process and white noise and predicted by a linear minimum-mean-squared error (LMMSE) predictor. This deviates from the classical Wiener model, which considers white noise increments only. The normalized mean-squared error (NMSE) in one-step-ahead (OSA) prediction of the PHN process is then evaluated from the results obtained and is compared for different signal-to-noise ratio (SNR) values and different PHN characteristics. In many situations the new PHN model shows a good prediction gain compared to the Wiener model, even for low order predictors.

The work establishes fundamental limits with respect to rate, reliability and computational complexity, for a general setting of outage-limited MIMO communications. In the high-SNR regime, the limits are optimized over all encoders, all decoders, and all complexity regulating policies. The work then proceeds to explicitly identify encoder-decoder designs and policies, that meet this optimal tradeoff. In practice, the limits aim to meaningfully quantify different pertinent measures, such as the optimal rate-reliability capabilities per unit complexity and power, the optimal diversity gains per complexity costs, or the optimal number of numerical operations (i.e., flops) per bit. Finally the tradeoff's simple nature, renders it useful for insightful comparison of the rate-reliability-complexity capabilities for different encoders-decoders., 6 pages, no figures. Slide presentation of partial work at ITA 2010. Published at ISIT2010

In the setting of multiple-access MIMO channels, the work establishes the DMT optimality of lattice-reduction (LR)-aided regularized linear decoders. This is achieved irrespective of the lattice design applied by each user. The decoding algorithms employ efficient solutions to the Nearby Vector Problem with Preprocessing in the presence of a regularized non-Euclidean metric, and in the presence of time-outs. The decoders' optimality induces a worst-case computational complexity that is at most linear in the users' sum-rate. This constitutes a substantial improvement over the state of art of DMT optimal decoding, including ML decoders with complexity that is exponential in the sum-rate, or lattice decoders based on solutions to the NP-hard closest vector problem (CVP). The optimality of the efficient decoders is established for all channel statistics, for all channel dimensions, for any number of users, and irrespective of the different rates. The findings directly apply to different computationally intensive multi-user settings such as multi-user MIMO, multi-user cooperative communications, and multi-user MIMO-OFDM.

We consider a generic bit-interleaved coded modulation (BICM) systems with an approximate demodulator or log-likelihood ratio (LLR) computer. The performance of a BICM system with optimal demodulation has previously been characterized by Caire et al. in terms of the capacity of an independent parallel-channel model with binary inputs and (continuous) LLRs as outputs, and by Martinez et al. in terms of the generalized mutual information (GMI) where the BICM decoder is viewed as a mismatched decoder. Whereas GMI and capacity of the parallel-channel model coincide under optimal demodulation, they differ in general for the case of an approximate demodulator. Herein we show (i) that augmenting approximate BICM demodulators with scalar LLR correction increases the GMI and (ii) that the GMI of the LLR-corrected system coincides with the capacity of the parallel-channel model with binary inputs and outputs given by the approximate LLRs.

Currently for the nt x nr MIMO channel, any explicitly constructed space-time (ST) designs that achieve optimality with respect to the diversity multiplexing tradeoff (DMT) are known to do so only when decoded using maximum likelihood (ML) decoding, which may incur prohibitive decoding complexity. In this paper we prove that MMSE regularized lattice decoding, as well as the computationally efficient lattice reduction (LR) aided MMSE decoder, allows for efficient and DMT optimal decoding of any approximately universal lattice-based code. The result identifies for the first time an explicitly constructed encoder and a computationally efficient decoder that achieve DMT optimality for all multiplexing gains and all channel dimensions. The results hold irrespective of the fading statistics., 5 pages, submitted to ISIT 09

We consider vector perturbation (VP) precoding for a multiple antenna broadcast scenario with multiple non-cooperative users. Under an instantaneous transmit power constraint, VP precoding requires the feedforward of a power normalization factor to the users. Simple quantization of the power normalization factor is shown to result in an error floor. To overcome this problem, we propose a new precoding scheme that uses a finite set of power normalization factors and avoids transmission at all when the available power is not sufficient to perform channel equalization at the transmit side. With this scheme, full diversity can be achieved (even with imperfect channel state information) while simultaneously significant amounts of transmit power can be saved.

In multi-input-multi-output (MIMO) detection, semidefinite relaxation (SDR) has been shown to be an efficient high-performance approach. Developed initially for BPSK and QPSK, SDR has been found to be capable of providing near-optimal performance (for those constellations). This has stimulated a number of recent research endeavors that aim to apply SDR to the high-order QAM cases. These independently developed SDRs are different in concept and structure, and presently no serious analysis has been given to compare these methods. This paper analyzes the relationship of three such SDR methods, namely the polynomial-inspired SDR (PI-SDR) by Wiesel et al., the bound-constrained SDR (BC-SDR) by Sidiropoulos and Luo, and the virtually-antipodal SDR (VA-SDR) by Mao et al. The result that we have proven is somehow unexpected: the three SDRs are equivalent. Simply speaking, we show that solving any one SDR is equivalent to solving the other SDRs. This paper also discusses some implications arising from the SDR equivalence, and provides simulation results to verify our theoretical findings., Submitted to IEEE Journal of Selected Topics in Signal Processing, Aug 2008

This work presents new eigenvalue bounds, necessary conditions and existence results for approximately universal linear (lattice) codes that can be drawn from lattices of reduced dimension, and can thus incur reduced decoding complexity. Currently for the n times nr MIMO channel, all known n times T approximately universal codes, except for the Alamouti code for n = 2,nr = 1, draw from lattices of dimension equal to or larger than nT, irrespective of nr. Motivated by the case where nr < n, the work describes construction criteria for lattice codes that maintain their approximate universality even when they are drawn from lattices of reduced dimensionality.

We consider vector perturbation precoding over a quasi-static MIMO channel under the assumption of imperfect channel state information (CSI). This is accomplished via a high SNR analysis, specifically targeting the overall system diversity order and the identification of typical errors. The effects of long-term and short-term power constraints, or power allocation policies, are investigated. Our results indicate that under realistic assumptions regarding the channel estimation error the system is mainly interference limited and as such, the particular power constraint does not significantly affect the asymptotic behavior of the error probability. This is in sharp contrast to the case of perfect CSI.

Lattice reduction by means of the LLL algorithm has been previously suggested as a powerful preprocessing tool that allows to improve the performance of suboptimal detectors and to reduce the complexity of optimal MIMO detectors. The complexity of the LLL algorithm is often cited as polynomial in the dimension of the lattice. In this paper we argue that this statement is not correct when made in the MIMO context. Specifically, we demonstrate that in typical communication scenarios the worst-case complexity of the LLL algorithm is not even finite. For i.i.d. Rayleigh fading channels, we further prove that the average LLL complexity is polynomial and that the probability for an atypically large number of LLL iterations decays exponentially.

Zhang et. al. recently derived upper and lower bounds on the achievable diversity of an N_R x N_T i.i.d. Rayleigh fading multiple antenna system using transmit antenna selection, spatial multiplexing and a linear receiver structure. For the case of L = 2 transmitting (out of N_T available) antennas the bounds are tight and therefore specify the maximal diversity order. For the general case with L, 10 pages. Submitted to the IEEE Transactions on Information Theory

Maximum likelihood (ML) detection of symbols transmitted over a MIMO channel is generally a difficult problem due to its NP-hard nature. However, not every instance of the detection problem is equally hard. Thus, the average complexity of an ML detector may be significantly smaller than its worst-case counterpart. This is typically true in the high SNR regime where the received signals are closer to the noise free transmitted signals. Herein, a method which may be used to lower the average complexity of any ML detector is proposed. The method is based on the ability to verify if a symbol estimate is ML, using an optimality condition provided by the near-ML semidefinite relaxation technique. The average complexity reduction advantage of the proposed method is confirmed by numerical results.

We study the problem of semidefinite relaxation (SDR) for detection of symbols transmitted over a general MIMO channel. In the SDR detector the maximum likelihood detection problem is relaxed into a semidefinite program (SDP) which is solved numerically using an interior-point path-following algorithm. Herein, we provide a criteria which, based on the channel matrix realization, determine the accuracy required by the SDP solver to give a good bit error rate performance of the overall SDR detector. This also reduce the complexity of the SDR detector as it limits the number of interior iterations required in the SDP solver. The performance is demonstrated through simulations.

We consider the detection of binary (antipodal) signals transmitted in a spatially multiplexed fashion over a fading multiple-input multiple-output (MIMO) channel and where the detection is done by means of semidefinite relaxation (SDR). The SDR detector is an attractive alternative to maximum likelihood (ML) detection since the complexity is polynomial rather than exponential. Assuming that the channel matrix is drawn with i.i.d. real valued Gaussian entries, we study the receiver diversity and prove that the SDR detector achieves the maximum possible diversity. Thus, the error probability of the receiver tends to zero at the same rate as the optimal maximum likelihood (ML) receiver in the high signal to noise ratio (SNR) limit. This significantly strengthens previous performance guarantees available for the semidefinite relaxation detector. Additionally, it proves that full diversity detection is in certain scenarios also possible when using a non-combinatorial receiver structure., Comment: Submitted to the IEEE Transactions on Information Theory, June 2006

Receiver diversity is an important measure of a receivers robustness towards fading in wireless communications. For the detection of binary symbols transmitted over a general MIMO channel, the semidefinite relaxation (SDR) detector is a computationally attractive alternative to exact ML detection. In the SDR detector, the hard combinatorial optimization problem arising in the ML detector is relaxed into a simple convex optimization problem followed by component wise threshold decisions. In this work, we argue that the SDR detector will provide an increase in diversity over simpler decoder structures such as the ZF and MMSE detectors. Specifically, for the case of uncoded V-BLAST transmission over a MIMO channel with real valued i.i.d. Gaussian channel coefficients we present an analytic result stating that the SDR detector achieves the maximum possible receiver diversity.

The sphere decoder has emerged as one of the most promising techniques for maximum likelihood detection of symbols transmitted over a general MIMO channel. Although efficient for problems of moderate size it is known that the original sphere decoder is of exponential (expected) complexity which limits its usage for large scale problems. However, at this stage, many alterations and improvements over the original algorithm have appeared in the literature. Herein we study a generic sphere decoder for the i.i.d. Rayleigh fading MIMO channel. The detection ordering and search radius (parameters of the algorithm) are allowed to be arbitrary functions of the decoder input, the only restriction being that the search radius is chosen such that the detection problem is solved. It is shown that the set of problem instances solvable by the sphere decoder in less than exponential time would tend to zero with increasing problem size. This extends previous results by providing a statement which is stronger than exponential expected complexity while relaxing the assumptions regarding the specific decoder implementation.

Optimal maximum likelihood detection of finite alphabet symbols in general requires time consuming exhaustive search methods. The computational complexity of such techniques is exponential in the size of the problem and for large problems sub-optimal algorithms are required. To find a solution in polynomial time, a semidefinite programming approach is taken to estimate binary symbols in a general linear system. A condition under which the proposed method provides optimal solutions is derived. As an application, the proposed algorithm is used as a decoder for a linear space-time block coding system and the results are illustrated with numerical examples.

The sphere decoding algorithm is an efficient algorithm used to solve the maximum likelihood detection problem in several digital communication systems. The sphere decoding algorithm has previously been claimed to have polynomial expected complexity. While it is true that the algorithm has an expected complexity comparable to that of other polynomial time algorithms for problems of moderate size it is a misconception that the expected number of operations asymptotically grow as a polynomial function of the problem size. In order to illustrate this point we derive an exponential lower bound on the expected complexity of the sphere decoder.

An inner space-time block code (STBC) is concatenated with a powerful outer code such as the turbo codes to achieve the low probability of error in a system with multiple antennas at the receiver and the transmitter. We study the overall performance of the system by computing the random coding exponent of the channel by the outer code.

Transmission at rates close to capacity over fading multiple antenna channels can be achieved by concatenating inner space-time block codes and powerful outer codes such as turbo or LDPC codes. However, in such systems, computation of the required soft information, or log-likelihood ratios (LLR), for the bits transmitted over the channel is rather complex and some form of approximations are typically used. Herein, we show how the complexity of computing the max-log approximation of the LLR can be reduced by computing all LLR values simultaneously using a parallel sphere decoder implementation