This paper considers a millimeter-wave wideband point-to-point MIMO system with fully digital transceivers at the base station and the user equipment (UE), focusing on mobile UE scenarios. A main challenge when building a digital UE combining is the large volume of baseband samples to handle. To mitigate computational and hardware complexity, we propose a novel two-stage digital combining scheme at the UE. The first stage reduces the Nrreceived signals to Ncstreams before baseband processing, leveraging channel geometry for dimension reduction and updating at the beam coherence time, which is longer than the channel coherence time of the small-scale fading. By contrast, the second-stage combining is updated per fading realization. We develop a pilot-based channel estimation framework for this hardware setup based on maximum likelihood estimation in both uplink and downlink. Digital precoding and combining designs are proposed, and a spectral efficiency expression that incorporates imperfect channel knowledge is derived. The numerical results demonstrate that the proposed approach outperforms hybrid beamforming, showcasing the attractiveness of using two-stage fully digital transceivers in future systems.

MOTIVATION: Nanopores are highly sensitive sensors that have achieved commercial success in DNA/RNA sequencing, with potential applications in protein sequencing and biomarker identification. Solid-state nanopores, in particular, face challenges such as instability and low signal-to-noise ratios, which lead scientists to adopt data-driven methods for nanopore signal analysis, although data acquisition remains restrictive. RESULTS: We address this data scarcity by augmenting the training samples with traces that emulate Brownian motion effects, based on dynamic models in the literature. We apply this method to a publicly available dataset of a classification task containing nanopore reads of DNA with encoded barcodes. A neural network named QuipuNet was previously published for this dataset, and we demonstrate that our augmentation method produces a noticeable increase in QuipuNet's accuracy. Furthermore, we introduce a novel neural network named YupanaNet, which achieves greater accuracy (95.8%) than QuipuNet (94.6%) on the same dataset. YupanaNet benefits from both the enhanced generalization provided by Brownian motion data augmentation and the incorporation of novel architectures, including skip connections and a soft attention mask. AVAILABILITY AND IMPLEMENTATION: The source code and data are available at: https://github.com/JavierKipen/browDataAug.

Hidden Markov models (HMMs) are frequently used in areas such as speech recognition and bioinformatics. However, implementing HMM algorithms correctly and efficiently is time-consuming and error-prone. Specifically, using model-specific knowledge to improve performance, such as sparsity in the transition probability matrix, ties the implementation to a particular model, making it harder to modify. Previous work has introduced high-level frameworks for defining HMMs, thus lifting the burden of efficiently implementing HMM algorithms from the user. However, existing tools are ill-suited for sparse HMMs with many states. This paper introduces Trellis, a domain-specific language for succinctly defining sparse HMMs that use GPU acceleration to achieve high performance. We show that Trellis outperforms previous work and is on par with a hand-written CUDA kernel implementation for a particular sparse HMM.

Detection of bio-molecules through quantum tunneling currents could lead to the next-generation DNA sequencing methods. In order to analyze the stability of these sensitive devices, it is necessary to characterize their conductance switching statistics. This characterization can be realized by denoising the tunneling current signal and clustering the outcomes. The first step can be done with the CUSUM algorithm, which detects abrupt changes and has been used in similar devices. We found heavy-tailed non-Gaussian noise in the measurement setup of the experimental devices. This paper suggests an approximation in the likelihood ratio step of the CUSUM algorithm that is more robust than the simple Gaussian noise assumption and, at the same time, is computationally more efficient than computing the fitted true likelihoods.

This paper considers a multi-user multiple-input multiple-output (MU-MIMO) system where the precoding matrix is selected in a baseband unit (BBU) and then sent over a digital fronthaul to the transmitting antenna array. The fronthaul has a limited bit resolution with a known quantization behavior. We formulate a new sum rate maximization problem where the precoding matrix elements must comply with the quantizer. We solve this non-convex mixed-integer problem to local optimality by a novel iterative algorithm inspired by the classical weighted minimum mean square error (WMMSE) approach. The precoding optimization subproblem becomes an integer least-squares problem, which we solve with a new algorithm using a sphere decoding (SD) approach. We show numerically that the proposed precoding technique vastly outperforms the baseline of optimizing an infinite-resolution precoder and then quantizing it. We also develop a heuristic quantization-aware precoding that outperforms the baseline while having comparable complexity.

BACKGROUND: Basecalling long DNA sequences is a crucial step in nanopore-based DNA sequencing protocols. In recent years, the CTC-RNN model has become the leading basecalling model, supplanting preceding hidden Markov models (HMMs) that relied on pre-segmenting ion current measurements. However, the CTC-RNN model operates independently of prior biological and physical insights. RESULTS: We present a novel basecaller named Lokatt: explicit duration Markov model and residual-LSTM network. It leverages an explicit duration HMM (EDHMM) designed to model the nanopore sequencing processes. Trained on a newly generated library with methylation-free Ecoli samples and MinION R9.4.1 chemistry, the Lokatt basecaller achieves basecalling performances with a median single read identity score of 0.930, a genome coverage ratio of 99.750%, on par with existing state-of-the-art structure when trained on the same datasets. CONCLUSION: Our research underlines the potential of incorporating prior knowledge into the basecalling processes, particularly through integrating HMMs and recurrent neural networks. The Lokatt basecaller showcases the efficacy of a hybrid approach, emphasizing its capacity to achieve high-quality basecalling performance while accommodating the nuances of nanopore sequencing. These outcomes pave the way for advanced basecalling methodologies, with potential implications for enhancing the accuracy and efficiency of nanopore-based DNA sequencing protocols.

Next-generation single-molecule protein sequencing technologies have the potential to significantly accelerate biomedical research. These technologies offer sensitivity and scalability for proteomic analysis. One auspicious method is fluorosequencing, which involves: cutting naturalized proteins into peptides, attaching fluorophores to specific amino acids, and observing variations in light intensity as one amino acid is removed at a time. The original peptide is classified from the sequence of light-intensity reads, and proteins can subsequently be recognized with this information. The amino acid step removal is achieved by attaching the peptides to a wall on the C-terminal and using a process called Edman Degradation to remove an amino acid from the N-Terminal. Even though a framework (Whatprot) has been proposed for the peptide classification task, processing times remain restrictive due to the massively parallel data acquisicion system. In this paper, we propose a new beam search decoder with a novel state formulation that obtains considerably lower processing times at the expense of only a slight accuracy drop compared to Whatprot. Furthermore, we explore how our novel state formulation may lead to even faster decoders in the future.

One of the first widespread uses of multi-user multiple-input multiple-output (MU-MIMO) is in 5G networks, where each base station has an advanced antenna system (AAS) that is connected to the baseband unit (BBU) with a capacity-constrained fronthaul. In the AAS configuration, multiple passive antenna elements and radio units are integrated into a single box. This paper considers precoded downlink transmission over a single-cell MU-MIMO system. We study optimized linear precoding for AAS with a limited-capacity fronthaul, which requires the precoding matrix to be quantized. We propose a new precoding design that is aware of the fronthaul quantization and minimizes the mean-squared error at the receiver side. We compute the precoding matrix using a sphere decoding (SD) approach. We also propose a heuristic low-complexity approach to quantized precoding. This heuristic is computationally efficient enough for massive MIMO systems. The numerical results show that our proposed precoding significantly outperforms quantization-unaware precoding and other previous approaches in terms of the sum rate. The performance loss for our heuristic method compared to quantization-aware precoding is insignificant considering the complexity reduction, which makes the heuristic method feasible for real-time applications. We consider both perfect and imperfect channel state information (CSI).

Base stations in 5G and beyond use advanced antenna systems (AASs), where multiple passive antenna elements and radio units are integrated into a single box. A critical bottleneck of such a system is the digital fronthaul between the AAS and baseband unit (BBU), which has limited capacity. In this paper, we study an AAS used for precoded down-link transmission over a multi-user multiple-input multiple-output (MU-MIMO) channel. First, we present the baseline quantization-unaware precoding scheme created when a pre-coder is computed at the BBU and then quantized to be sent over the fronthaul. We propose a new precoding design that is aware of the fronthaul quantization. We formulate an optimization problem to minimize the mean squared error at the receiver side. We rewrite the problem to utilize mixed-integer programming to solve it. The numerical results manifest that our proposed precoding greatly outperforms quantization-unaware precoding in terms of sum rate.

A logconcave likelihood is as important to proper statistical inference as a convex cost function is important to variational optimization. Quantization is often disregarded when writing likelihood models, ignoring the limitations of the physical detectors used to collect the data. These two facts call for the question: would including quantization in likelihood models preclude logconcavity? are the true data likelihoods logconcave? We provide a general proof that the same simple assumption that leads to logconcave continuous-data likelihoods also leads to logconcave quantized-data likelihoods, provided that convex quantization regions are used.

The weighted minimum mean square error (WMMSE) algorithm was proposed to provide a locally optimum solution to the otherwise NP-hard weighted sum rate maximization beamforming problem, but it can still be prohibitively complex for real-time implementation. With the success of deep unfolding in trading off complexity and performance, we propose to apply deep unfolding to the WMMSE algorithm. With respect to traditional end-to-end learning, deep unfolding incorporates expert knowledge, with the benefits of immediate and well-grounded architecture selection, fewer trainable parameters, and better explainability. However, the classical formulation of the WMMSE algorithm given by Shi et al. is not amenable for deep unfolding due to matrix inversions, eigendecompositions, and bisection searches. Therefore, we present an alternative formulation that circumvents these operations. By means of simulations, we show that the deep unfolded WMMSE algorithm performs on par with the original WMMSE algorithm, at a lower computational load.

Wireless links use adaptive modulation and coding (AMC) to optimize data transmission over a dynamic channel. Traditional AMC schemes rely on simple heuristics to track the instantaneous channel state. While attractive for their low implementation and operational complexity, these schemes are known to be suboptimal in a large range of operating environments. Further, several such schemes require careful parameter tuning, which can be both expensive and error-prone. In this paper, we propose latent Thompson sampling (LTS) for AMC, which efficiently tracks the wireless channel by modeling a latent, low-dimensional, channel state. LTS features both a low computational complexity and fast learning dynamics, and requires minimal tuning effort. We evaluate LTS in stationary as well as fading wireless channels, where LTS improves the link throughput by up to 100% compared to state-of-the-art schemes.

We address multi-armed bandits (MAB) where the objective is to maximize the cumulative reward under a probabilistic linear constraint. For a few real-world instances of this problem, constrained extensions of the well-known Thompson Sampling (TS) heuristic have recently been proposed. However, finite-time analysis of constrained TS is challenging; as a result, only O( sqrt( T ) ) bounds on the cumulative reward loss (i.e., the regret) are available. In this paper, we describe LinConTS, a TS-based algorithm for bandits that place a linear constraint on the probability of earning a reward in every round. We show that for LinConTS, the regret as well as the cumulative constraint violations are upper bounded by O( log ( T ) ). We develop a proof technique that relies on careful analysis of the dual problem and combine it with recent theoretical work on unconstrained TS. Through numerical experiments on two real-world datasets, we demonstrate that LinConTS outperforms an asymptotically optimal upper confidence bound (UCB) scheme in terms of simultaneously minimizing the regret and the violation.

Clock synchronization and ranging over a wireless network with low communication overhead is a challenging goal with tremendous impact. In this paper, we study the use of time-to-digital converters in wireless sensors, which provides clock synchronization and ranging at negligible communication overhead through a sawtooth signal model for round trip times between two nodes. In particular, we derive Cramér-Rao lower bounds for a linearitzation of the sawtooth signal model, and we thoroughly evaluate simple estimation techniques by simulation, giving clear and concise performance references for this technology.

In this paper we consider distributed convex optimization over time-varying undirected graphs. We propose a linearized version of primarily averaged network dual ascent (PANDA) that keeps the advantages of PANDA while requiring less computational costs. The proposed method, economic primarily averaged network dual ascent (Eco-PANDA), provably converges at R-linear rate to the optimal point given that the agents' objective functions are strongly convex and have Lipschitz continuous gradients. Therefore, the method is competitive, in terms of type of rate, with both DIGing and PANDA. The proposed method halves the communication costs of methods like DIGing while still converging R-linearly and having the same per iterate complexity.

The expectation-maximization algorithm is a commonly employed tool for system identification. However, for a large set of state-space models, the maximization step cannot be solved analytically. In these situations, a natural remedy is to make use of the expectation-maximization gradient algorithm, i.e., to replace the maximization step by a single iteration of Newton's method. We propose alternative expectation-maximization algorithms that replace the maximization step with a single iteration of some other well-known optimization method. These algorithms parallel the expectation-maximization gradient algorithm while relaxing the assumption of a concave objective function. The benefit of the proposed expectation-maximization algorithms is demonstrated with examples based on standard observation models in tracking and localization.

This paper describes an Arduino Due based platform for digital signal processing (DSP) education. The platform consists of an in-house developed shield for robust interfacing with analog audio signals and user inputs, and an off-the-shelf Arduino Due that executes the students' DSP code. This combination enables direct use of the Arduino integrated development environment (IDE), with its low barrier to entry for students, its low maintenance need and cross platform interoperability, and its large user base. Relevant hardware and software features of the platform are discussed throughout, as are design choices made in relation to learning objectives, and the planned use of the platform in our own DSP course.

In this paper, we present a new interpretation of non-negatively constrained convolutional coding problems as blind deconvolution problems with spatially variant point spread function. In this light, we propose an optimization framework that generalizes our previous work on non-negative group sparsity for convolutional models. We then link these concepts to source localization problems that arise in scientific imaging, and provide a visual example on an image derived from data captured by the Hubble telescope.

In the context of wireless communications, we propose a deep learning approach to learn the mapping from the instantaneous state of a frequency selective fading channel to the corresponding frame error probability (FEP) for an arbitrary set of transmission parameters. We propose an abstract model of a bit interleaved coded modulation (BICM) orthogonal frequency division multiplexing (OFDM) link chain and show that the maximum likelihood (ML) estimator of the model parameters estimates the true FEP distribution. Further, we exploit deep neural networks as a general purpose tool to implement our model and propose a training scheme for which, even while training with the binary frame error events (i.e., ACKs / NACKs), the network outputs converge to the FEP conditioned on the input channel state. We provide simulation results that demonstrate gains in the FEP prediction accuracy with our approach as compared to the traditional effective exponential SIR metric (EESM) approach for a range of channel code rates, and show that these gains can be exploited to increase the link throughput.

We present a maximum likelihood estimator for estimating the positions of accelerometers in an inertial sensor array. This method simultaneously estimates the positions of the accelerometers and the motion dynamics of the inertial sensor array and, therefore, does not require a predefined motion sequence nor any external equipment. Using an iterative block coordinate descent optimization strategy, the calibration problem can be solved with a complexity that is linear in the number of time samples. The proposed method is evaluated by Monte-Carlo simulations of an inertial sensor array built out of 32 inertial measurement units. The simulation results show that, if the array experiences sufficient dynamics, the position error is inversely proportional to the number of time samples used in the calibration sequence. Further, results show that for the considered array geometry and motion dynamics in the order of 2000° /s and 2000° /s2, the positions of the accelerometers can be estimated with an accuracy in the order of 10-6m using only 1000 time samples. This enables fast on-the-fly calibration of the geometric errors in an inertial sensor array by simply twisting it by hand for a few seconds.

We consider an interference network with independent links, whose multi-antenna transmitters have access to an imperfect analog estimate of their local channels. Assuming that the receivers treat the interference as noise, we define the outage rate region as the set of rate-tuples that are achievable with a given probability and we characterize the boundary of the region for transmit beamforming. Our study shows that the Pareto-optimal beamforming vectors judiciously balance the desired signal power and the interference power based on the quality of the estimated channel state. Our analysis further reveals that, in contrast to the well-known results by Jorswieck, for the perfect channel side-information case, transmission at full power is not necessarily Pareto-optimal.

Automated tracking of living cells in microscopy image sequences is an important and challenging problem. With this application in mind, we propose a global track linking algorithm, which links cell outlines generated by a segmentation algorithm into tracks. The algorithm adds tracks to the image sequence one at a time, in a way which uses information from the complete image sequence in every linking decision. This is achieved by finding the tracks which give the largest possible increases to a probabilistically motivated scoring function, using the Viterbi algorithm. We also present a novel way to alter previously created tracks when new tracks are created, thus mitigating the effects of error propagation. The algorithm can handle mitosis, apoptosis, and migration in and out of the imaged area, and can also deal with false positives, missed detections, and clusters of jointly segmented cells. The algorithm performance is demonstrated on two challenging datasets acquired using bright-field microscopy, but in principle, the algorithm can be used with any cell type and any imaging technique, presuming there is a suitable segmentation algorithm.

We consider a distributed detection system under communication constraints, where several peripheral nodes observe a common phenomenon and send their observations to a fusion center via error-free but rate-constrained channels. Using the minimum expected error probability as a design criterion, we propose a cyclic procedure for the design of the peripheral nodes using the person-by-person methodology. It is shown that a fine-grained binning idea together with a method for updating the conditional probabilities of the joint index space at the fusion center, decrease the complexity of the algorithm and make it tractable. Also, unlike previous methods which use dissimilarity measures (e.g., the Bhattacharyya distance), a-prior hypothesis probabilities are allowed to contribute to the design in the proposed method. The performance of the proposed method is compared to a method due to Longo et al.'s and it is shown that the new method can significantly outperform the previous one at a comparable complexity.

MOTIVATION: Automatic tracking of cells in multidimensional time-lapse fluorescence microscopy is an important task in many biomedical applications. A novel framework for objective evaluation of cell tracking algorithms has been established under the auspices of the IEEE International Symposium on Biomedical Imaging 2013 Cell Tracking Challenge. In this article, we present the logistics, datasets, methods and results of the challenge and lay down the principles for future uses of this benchmark. RESULTS: The main contributions of the challenge include the creation of a comprehensive video dataset repository and the definition of objective measures for comparison and ranking of the algorithms. With this benchmark, six algorithms covering a variety of segmentation and tracking paradigms have been compared and ranked based on their performance on both synthetic and real datasets. Given the diversity of the datasets, we do not declare a single winner of the challenge. Instead, we present and discuss the results for each individual dataset separately. AVAILABILITY AND IMPLEMENTATION: The challenge Web site (http://www.codesolorzano.com/celltrackingchallenge) provides access to the training and competition datasets, along with the ground truth of the training videos. It also provides access to Windows and Linux executable files of the evaluation software and most of the algorithms that competed in the challenge.

We consider the problem of estimating a deterministic unknown vector which depends linearly on$n$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$\sqrt 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.

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 one-bit 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 Cramér-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 l1-based relaxation strategies by comparing against the theoretical CRLB.

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.

We consider a constrained multi-carrier power allocation problem in interference-limited multi-user systems with a finite set of transmission rates. The Lagrange relaxation is a common technique for decomposing such problems into independently solvable per-subcarrier problems. Deviating from this approach our main contribution is the proposal of a novel spectrum management framework based on a Nonlinear Dantzig-Wolfe problem decomposition. It allows for suboptimal initialization and suboptimal power allocation methods with low complexity. While we show that the combinatorial per-subcarrier problems have polynomial complexity in the number of users, we find that such suboptimal methods are indispensable in large systems. Thus we give an overview of various basic dual heuristics and provide simulation results on a set of thousand digital subscriber line (DSL) networks which show the superior performance of our framework compared to previous power control algorithms.

In the setting of quasi-static multiple-input multiple-output 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-based codes—the only currently known explicit designs that are uniformly optimal with respect to the diversity multiplexing tradeoff—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 performance that vanishes in the high SNR limit.

This study identifies the first lattice decoding solution that achieves, in the general outage-limited multiple-input multiple-output (MIMO) setting and in the high-rate and high-signal-to-noise ratio 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 and in the rate. The proposed solution employs Lenstra-Lenstra-Lovász-based lattice reduction (LR)-aided regularized (lattice) sphere decoding and proper timeout policies. These performance and complexity guarantees hold for most MIMO scenarios, most fading statistics, all channel dimensions, and all full-rate lattice codes. In sharp contrast to the aforementioned very manageable complexity, the complexity of other standard preprocessed lattice decoding solutions is revealed here to be extremely high. Specifically, this study has quantified the complexity of regularized lattice (sphere) decoding and has proved that the computational resources required by this decoder to achieve a good rate-reliability performance are exponential in the lattice dimensionality and in the number of codeword bits, and it in fact matches, in common scenarios, the complexity of ML-based sphere decoders. Through this sharp contrast, this study was able to, for the first time, rigorously demonstrate and quantify the pivotal role of LR as a special complexity reducing ingredient.

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.

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.

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

The work establishes fundamental limits between rate, reliability and computational complexity, for the 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 and interrelated measures, such as the optimal rate-reliability capabilities per unit complexity and power, the optimal diversity gains per complexity costs, or the optimal goodput per flop. Finally the tradeoff's simple nature, renders it useful for insightful comparison of the rate-reliability-complexity capabilities for different encoders-decoders.

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 thep-tap linear minimum-mean-square error (LMMSE) predictor, it is shown that close to optimal NMSE performance may be achieved for relatively moderate values ofp. 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.

This paper identifies the first general, explicit, and nonrandom MIMO encoder-decoder structures that guarantee optimality with respect to the diversity-multiplexing tradeoff (DMT), without employing a computationally expensive maximum-likelihood (ML) receiver. Specifically, the work establishes the DMT optimality of a class of regularized lattice decoders, and more importantly the DMT optimality of their lattice-reduction (LR)-aided linear counterparts. The results hold for all channel statistics, for all channel dimensions, and most interestingly, irrespective of the particular lattice-code applied. As a special case, it is established that the LLL-based LR-aided linear implementation of the MMSE-GDFE lattice decoder facilitates DMT optimal decoding of any lattice code at a worst-case complexity that grows at most linearly in the data rate. This represents a fundamental reduction in the decoding complexity when compared to ML decoding whose complexity is generally exponential in the rate. The results' generality lends them applicable to a plethora of pertinent communication scenarios such as quasi-static MIMO, MIMO-OFDM, ISI, cooperative-relaying, and MIMO-ARQ channels, in all of which the DMT optimality of the LR-aided linear decoder is guaranteed. The adopted approach yields insight, and motivates further study, into joint transceiver designs with an improved SNR gap to ML decoding.

In this paper we consider the vector perturbation (VP) precoding scheme for the multiuser MISO broadcast channel proposed by Hochwald et al. under the practical assumption that the receivers have limited dynamic range. In this case, VP precoding is shown to suffer from an error floor at high signal-to-noise ratio (SNR). As an alternative, we propose precoding with restricted VP (RVP), which takes the limited dynamic range of the receivers explicitly into account by restricting to a finite set of possible perturbation vectors at the transmitter side. We derive the diversity order of this RVP scheme and show that no error floor occurs and that the performance is superior to VP for the entire range of SNRs.

Currently for the nTtimes nRMIMO 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 latticebased 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.

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

There have recently been a large number of papers that derive the diversity order of various, low complexity, suboptimal receiver structures for MIMO communications. In almost all analyses the MIMO channel is assumed to be i.i.d. Rayleigh fading. It is of interest to investigate how these results generalize to other fading models (e.g., correlated Ricean fading). We show in this paper that the diversity achieved by virtually any receiver is preserved within a very general class of fading models (including i.i.d. Rayleigh fading and correlated Ricean fading). This result obviates the need to recalculate the diversity of various receivers for different fading distributions in a piecemeal fashion.

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.

Semidefinite relaxation (SDR) is a high-performance efficient approach to MIMO detection especially for the BPSK or QPSK constellations. Recently, a number of research endeavors have focused on extending SDR to the case of 16-QAM constellations. This paper reports two interesting and useful results on this problem. First, we show that two of the existing 16-QAM SDR receivers, namely the polynomial-inspired SDR (PI-SDR) and bound-constrained SDR (BC-SDR) methods, are equivalent. Second, we develop a specialized interior-point algorithm for the implementation of BCSDR. The proposed algorithm is computationally efficient exploiting the BC-SDR structures, and enables us to handle larger problem sizes in practice.

In this paper, 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 independent identically distributed (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 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 also possible in certain scenarios when using a noncombinatorial receiver structure.

This paper presents a new approach to soft demodulation for MIMO channels. The proposed method is an approximation to the exact a posteriori probability-per-bit computer. The main idea is to marginalize the posterior density for the received data exactly over the subset of the transmitted bits that are received with the lowest signal-to-noise-ratio, and then marginalize this density approximately over the remaining bits. Unlike the exact demodulator, whose complexity is huge due to the need for enumerating all possible combinations of transmitted constellation points, the proposed method has very low complexity. Additionally, its complexity is fixed, which makes it suitable for pipelined implementation. Numerical examples illustrate its performance on slow fading 4times4 and 6times6 complex MIMO channels.

The fixed-complexity sphere decoder (FSD) has been previously proposed for multiple input-multiple output (MIMO) detection to overcome the two main drawbacks of the original sphere decoder (SD), namely its variable complexity and sequential structure. As such, the FSD is highly suitable for hardware implementation and has shown remarkable performance through simulations. Herein, we explore the theoretical aspects of the algorithm and prove that the FSD achieves the same diversity order as the maximum likelihood detector (MLD). Further, we show that the coding loss can be made negligible in the high signal to noise ratio (SNR) regime with a significantly lower complexity than that of the MLD.

Zhang recently derived upper and lower bounds on the achievable diversity of an $N_R \times 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 \leq \min(N_R,N_T)$ transmitting antennas it was conjectured that the maximal diversity is $(N_T-L+1)(N_R-L+1)$ which coincides with the lower bound. Herein, we prove this conjecture for the zero forcing and zero forcing decision feedback (with optimal detection ordering) receiver structures.

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

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.

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.

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.

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.