Search

To fully utilize the degree of freedom of multiuser MIMO channels of wireless communication systems, channel state information at the transmitter (CSIT) is desired. From reverse link training, time division duplex (TDD) systems are able to obtain forward link CSIT because of channel reciprocity. We aim to do the same for frequency division duplex (FDD) multiuser MIMO systems, where the conventional method is to obtain CSIT from the feedback from the receiver. Unfortunately, the delay and the amount of feedback consume too much resource, especially in massive MIMO systems. However, if we could accurately estimate the channel parameters from the pilot signals in one frequency band, then the channel state in another frequency band can be calculated from these parameters. Because of the accuracy requirement, we cannot put the parameters on grids, have to treat them as continuous variables, and shall employ the super-resolution estimation algorithms. In this work, we formulate the FDD reciprocity problem as a super-resolution problem, show how to apply super-resolution algorithms to the problem in different ways, and compare the performances.

Horizontal and angular misalignment of coils in WPT systems have been extensively discussed. But as more and more low-power WPT systems are applied to wearable devices, the requirement for physical flexibility is also increasing. Different from conventional WPT coils with rigid and flat structure, bendable coupling coil structure is obviously more attractive, which however brings a new misalignment situation: the bending misalignment. In this paper, a low-power bendable WPT system is designed and the influence of different bending angles on self-inductance and mutual inductance is simulated and analyzed. The bending resistance of three types of coil and different core thicknesses are compared, and a low-power bendable experimental platform was finally constructed.

Wireless power transmission (WPT) has received much attention in recent years due to its convenience, safety, reliability, and weather resistance. Especially with the application of various electric vehicles, the demand for high-power wireless power transmission has become stronger and stronger. This paper proposes and designs a high-power electromagnetic coupling coil with high power density, compact structure, and good heat dissipation performance, and it has been proved to have good transmission characteristics and anti-offset characteristics by finite elements. Finally, a 100kW wireless energy transmission experimental platform based on the SS compensation topology was established to verify the operating characteristics of the axial transmission distance of 30mm ~ 100mm. The maximum efficiency point of the system at a longitudinal distance of 30 mm is 95.1%.

With explosion of data size and limited storage space at a single location, data are often distributed at different locations. We thus face the challenge of performing large-scale machine learning from these distributed data through communication networks. In this paper, we generalize the distributed dual coordinate ascent in a star network to a general tree structured network, and provide the convergence rate analysis of the general distributed dual coordinate ascent. In numerical experiments, we demonstrate that the performance of the distributed dual coordinate ascent in a tree network can outperform that of the distributed dual coordinate ascent in a star network when a network has a lot of communication delays between the center node and its direct child nodes.

We consider the problem of recovering the superposition of $R$ distinct complex exponential functions from compressed non-uniform time-domain samples. Total Variation (TV) minimization or atomic norm minimization was proposed in the literature to recover the $R$ frequencies or the missing data. However, in order for TV minimization and atomic norm minimization to recover the missing data or the frequencies, the underlying $R$ frequencies are required to be well-separated, even when the measurements are noiseless. This paper shows that the Hankel matrix recovery approach can super-resolve the $R$ complex exponentials and their frequencies from compressed nonuniform measurements, regardless of how close their frequencies are to each other. We propose a new concept of orthonormal atomic norm minimization (OANM), and demonstrate that the success of Hankel matrix recovery in separation-free super-resolution comes from the fact that the nuclear norm of a Hankel matrix is an orthonormal atomic norm. More specifically, we show that, in traditional atomic norm minimization, the underlying parameter values must be well separated to achieve successful signal recovery, if the atoms are changing continuously with respect to the continuously-valued parameter. In contrast, for the OANM, it is possible the OANM is successful even though the original atoms can be arbitrarily close.

In this paper, we solve the sum mean-squared error (MSE)-optimal 1-bit quantized precoding problem exactly for small-to-moderate sized multiuser multiple-input multiple-output (MU-MIMO) systems via branch and bound. To this end, we reformulate the original NP-hard precoding problem as a tree search and deploy a number of strategies that improve the pruning efficiency without sacrificing optimality. We evaluate the error-rate performance and the complexity of the resulting 1-bit branch-and-bound (BB-1) precoder, and compare its efficacy to that of existing, suboptimal algorithms for 1-bit precoding in MU-MIMO systems., 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), ISBN:978-1-5386-4658-8, ISBN:978-1-5386-4657-1, ISBN:978-1-5386-4659-5

One major bottleneck in the design of large scale distributed machine learning algorithms is the communication cost. In this paper, we propose and analyze a distributed learning scheme for reducing the amount of communication in distributed learning problems under the feature partition scenario. The motivating observation of our scheme is that, in the existing schemes for the feature partition scenario, large amount of data exchange is needed for calculating gradients. In our proposed scheme, instead of calculating the exact gradient at each iteration, we only calculate the exact gradient sporadically. We provide precise conditions to determine when to perform the exact update, and characterize the convergence rate and bounds for total iterations and communication iterations. We further test our algorithm on real data sets and show that the proposed scheme can substantially reduce the amount of data transferred between distributed nodes.

In this paper, the problem of identifying correlated components in a high-dimensional Gaussian vector is considered. In the setup considered, instead of having to take a full-vector observation at each time index, the observer is allowed to observe any subset or full set of components in the vector, and he has the freedom to design his sampling strategies over time. The observer aims to find an optimal sampling strategy and a decision rule to maximize the error exponent (per sample). We focus on sequential strategies, in which the sampling actions depend on the observations taken so far. We first derive performance bounds of any sequential sampling strategy. We then design a low complexity procedure called sequential diagonal procedure. We show that this low complexity sequential procedure substantially outperforms the optimal non-adaptive strategy when the strength of the signal is strong.

This paper presents the design, fabrication, and testing of a novel 3D-printed triboelectric generator. By adopting the saw-toothed button structure, the friction surface at the interface is enlarged and enclosed, which helps to increase power generation capability and shrink device volume. The major parts of the proposed device is fabricated through 3D-printing, and the entire device is assembled to be the size of an AA battery. Testing results show that maximal voltage spikes of 3.9V peak-to-peak voltage is achieved as the button is repeatedly pressed and released at around 1Hz, proving the functionality of the proposed device.

Novel input-parallel output-parallel (IPOP) DC-DC converter with maximum power point tracking (MPPT) technique is presented in this paper, which consists of two cascaded stages including buck-boost and isolated boost, so as to achieve high voltage gain and galvanic isolation at proper duty ratio and low leakage energy. Using proposed DC-DC converter, multiple distributed generators (DGs) can be connected to DC grid or subsequent power management unit (PMU) through IPOP method, which is conducive to hot plug in and out of DGs in real applications. Open loop MPPT technique is combined with pulse width modulation (PWM) to control the main switch of the DC-DC converter. Simulation results show that for two identical DG inputs of ∼24V, voltage gain reaches 12.6, and total output current is the sum of single unit. For two different DG inputs of ∼24V and ∼36V, output voltage is boosted by an average factor of 15.3. In both conditions, stable output with small ripple are obtained, proving the suitability of the proposed DC-DC converter and grid connection method in DG applications.

We study the problem of recovering an $n$-dimensional vector of $\{\pm1\}^n$ (BPSK) signals from $m$ noise corrupted measurements $\mathbf{y}=\mathbf{A}\mathbf{x}_0+\mathbf{z}$. In particular, we consider the box relaxation method which relaxes the discrete set $\{\pm1\}^n$ to the convex set $[-1,1]^n$ to obtain a convex optimization algorithm followed by hard thresholding. When the noise $\mathbf{z}$ and measurement matrix $\mathbf{A}$ have iid standard normal entries, we obtain an exact expression for the bit-wise probability of error $P_e$ in the limit of $n$ and $m$ growing and $\frac{m}{n}$ fixed. At high SNR our result shows that the $P_e$ of box relaxation is within 3dB of the matched filter bound MFB for square systems, and that it approaches MFB as $m $ grows large compared to $n$. Our results also indicates that as $m,n\rightarrow\infty$, for any fixed set of size $k$, the error events of the corresponding $k$ bits in the box relaxation method are independent., 5 pages, 2 figures

We propose fast algorithms that speed up or improve the performance of recovering spectrally sparse signals from un-derdetermined measurements. Our algorithms are based on a non-convex approach of using alternating projected gradient descent for structured matrix recovery. We apply this approach to two formulations of structured matrix recovery: Hankel and Toeplitz mosaic structured matrix, and Hankel structured matrix. Our methods provide better recovery performance, and faster signal recovery than existing algorithms, including atomic norm minimization.

In this paper, the problem of detecting correlated components in a p-dimensional Gaussian vector is considered. In the setup considered, s unknown components are correlated with a known covariance structure. Hence, there are equation possible hypotheses for the unknown set of correlated components. Instead of taking a full-vector observation at each time index, in this paper we assume that the observer is capable of observing any subset of components in the vector. With this flexibility in taking observations, the observer is interested in finding the optimal sampling strategy to maximize the error exponent (per sample) of the multi-hypothesis testing problem. We show that, when the correlation of these s components is weak, it is optimal for the observer to take full-vector observations; when the correlation is strong, the strategy of taking full-vector observation is not optimal anymore, and the optimal sampling strategy increases the detection error exponent by 25% at least, compared with the full-vector observation strategy.

This paper considers an exact maximum likelihood (ML) joint channel estimation and data detection problem for orthogonal space time block coded (OSTBC) multiple input multiple output (MIMO) systems. We propose an efficient algorithm which achieves exact ML blind data detection even for non-constant-modulus constellations. To the best of our knowledge, this is the first algorithm which efficiently achieves exact ML blind detection for OSTBC MIMO systems with non-constant-modulus constellations. Simulation results validate the performance and the complexity improvements our scheme compare with that of LS channel estimation and data detection scheme.

Recent research in off-the-grid compressed sensing (CS) has demonstrated that, under certain conditions, one can successfully recover a spectrally sparse signal from a few time-domain samples even though the dictionary is continuous. In particular, atomic norm minimization was proposed in [1] to recover 1-dimensional spectrally sparse signal. However, in spite of existing research efforts [2], it was still an open problem how to formulate an equivalent positive semidefinite program for atomic norm minimization in recovering signals with d-dimensional (d ≥ 2) off-the-grid frequencies. In this paper, we settle this problem by proposing equivalent semidefinite programming formulations of atomic norm minimization to recover signals with d-dimensional (d ≥ 2) off-the-grid frequencies.

In this paper, we consider the variable selection problem for a nonlinear non-parametric system. The approach proposed selects a variable by detecting if the corresponding partial derivative is zero or not at the point of interest. The algorithm is shown to have not only the parameter but also the set convergence. This is critical because the variable selection problem is binary, a variable is either selected or not selected. The approach allows the unknown non-parametric nonlinear system to have different local dimensions at different points of interest.

The null space condition is a condition under which k-sparse signal can be recovered uniquely in compressed sensing (CS) problems. In this paper, new efficient algorithms are introduced to verify the null space condition for l 1 minimization in compressed sensing. Suppose A is an (n − m) × n (m > 0) sensing matrix, we can verify whether the sensing matrix A satisfies the null space condition or not for k-sparse signals by computing α k = ‖z K ‖ 1 /‖z ‖ 1 where K represents subsets of {1, 2,…, n}, and |K| is the cardinality of K. However, computing α k is known to be extremely challenging because of high computational complexity. In this paper, a series of new polynomial-time algorithms are proposed to compute upper bounds on α k . Based on these new polynomial-time algorithms, we further design new algorithm, which is called the sandwiching algorithm, to compute the exact a k with much lower complexity than exhaustive search.

In this paper, we consider using total variation minimization to recover signals whose gradients have a sparse support, from a small number of measurements. We establish the proof for the performance guarantee of total variation (TV) minimization in recovering \emph{one-dimensional} signal with sparse gradient support. This partially answers the open problem of proving the fidelity of total variation minimization in such a setting \cite{TVMulti}. In particular, we have shown that the recoverable gradient sparsity can grow linearly with the signal dimension when TV minimization is used. Recoverable sparsity thresholds of TV minimization are explicitly computed for 1-dimensional signal by using the Grassmann angle framework. We also extend our results to TV minimization for multidimensional signals. Stability of recovering signal itself using 1-D TV minimization has also been established through a property called "almost Euclidean property for 1-dimensional TV norm". We further give a lower bound on the number of random Gaussian measurements for recovering 1-dimensional signal vectors with $N$ elements and $K$-sparse gradients. Interestingly, the number of needed measurements is lower bounded by $\Omega((NK)^{\frac{1}{2}})$, rather than the $O(K\log(N/K))$ bound frequently appearing in recovering $K$-sparse signal vectors., Comment: lower bounds added; version with Gaussian width, improved bounds; stability results added

Compressed sensing (CS) theory promises one can recover real-valued sparse signal from a small number of linear measurements. Motivated by network monitoring with link failures, we for the first time consider the problem of recovering signals that contain both real-valued entries and corruptions, where the real entries represent transmission delays on normal links and the corruptions represent failed links. Unlike conventional CS, here a measurement is real-valued only if it does not include a failed link, and it is corrupted otherwise. We prove that O((d + 1)max(d, k) log n) nonadaptive measurements are enough to recover all n-dimensional signals that contain k nonzero real entries and d corruptions. We provide explicit constructions of measurements and recovery algorithms. We also analyze the performance of signal recovery when the measurements contain errors.

In this paper, we study the mixing time of Markov Chain Monte Carlo (MCMC) for integer least-square (LS) optimization problems. It is found that the mixing time of MCMC for integer LS problems depends on the structure of the underlying lattice. More specifically, the mixing time of MCMC is closely related to whether there is a local minimum in the lattice structure. For some lattices, the mixing time of the Markov chain is independent of the signal-to-noise ($SNR$) ratio and grows polynomially in the problem dimension; while for some lattices, the mixing time grows unboundedly as $SNR$ grows. Both theoretical and empirical results suggest that to ensure fast mixing, the temperature for MCMC should often grow positively as the $SNR$ increases. We also derive the probability that there exist local minima in an integer least-square problem, which can be as high as $1/3-\frac{1}{\sqrt{5}}+\frac{2\arctan(\sqrt{5/3})}{\sqrt{5}\pi}$.

In this paper, we review our recent results on sparse recovery over graphs, which was motivated by network tomography problems. Our finding has made a new connection between coding theory and graph theory. We also discuss robustness of our proposed measurement construction.

In this paper, we study the problem of compressive sensing for sparse signal vectors generated over the graphs. The signal vectors to be recovered are sparse vectors representing the parameters of the links over the graphs. The collective additive measurements we are allowed to take must follow connected paths over the underlying graphs. For a sufficiently connected graph with n nodes, using O(k log(n)) path measurements, it is shown that we are able to recover any sparse link vector with no more than k nonzero elements, even though the measurements have to follow the graph path constraints.

In this paper, we investigate the uniqueness of positive semidefinite matrix solution to compressed linear observations. We show that under a necessary and sufficient condition for the linear compressed observations operator, there will be a unique positive semidefinite matrix solution to the compressed linear observations. It is further shown, through concentration of measure phenomenon and sphere covering arguments, that a randomly generated Gaussian linear compressed observations operator will satisfy this necessary and sufficient condition with overwhelmingly large probability.

An unknown vector f in Rn can be recovered from corrupted measurements y = Af + e where Am×n(m ≥ n) is the coding matrix if the unknown error vector e is sparse. We investigate the relationship of the fraction of errors and the recovering ability of l p -minimization (0 p -norm” of y-Ax. We give sharp thresholds of the fraction of errors that is recoverable. If e is an arbitrary unknown vector, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. If e has fixed support and fixed signs on the support, the threshold is ⅔ for all p in (0, 1), and 1 for p = 1.

l 1 minimization, also called Basis Pursuit, has been known to have strong sparse recovery performance both theoretically and empirically. Previously known analytical approaches for l 1 minimization have limitations in deriving custom stability performance bounds for signals with sparsity (the number of nonzero elements) level beyond the l 1 weak recovery threshold [6]. In this paper, instead of focusing on the static decoding results of l 1 minimization, we develop a microscopic analytical approach by studying the dynamics of l 1 minimization. This approach can give useful characterizations of l 1 decoding results and lead to new performance bounds on l 1 decoding error. Contrary to known stability results for l 1 minimization below the l 1 weak threshold, we prove that l 1 minimization decoding errors can experience an explosive growth in terms of the signal tail immediately beyond the l 1 minimization weak threshold. This new analytical approach is motivated by the applications of analyzing the emerging iterative reweighted l 1 minimization algorithms.

It is well known that l 1 minimization 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” [4]. In this paper, we introduce a reweighted l 1 recovery algorithm composed of two steps: a standard l 1 minimization step to identify a set of entries where the signal is likely to reside, and a weighted l 1 minimization 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.

It is now well understood that the l 1 minimization algorithm is able to recover sparse signals from incomplete measurements [2], [1], [3] and sharp recoverable sparsity thresholds have also been obtained for the l 1 minimization algorithm. However, even though iterative reweighted l 1 minimization 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 l 1 algorithms. In particular, we show that for a nontrivial class of signals, the iterative reweighted l 1 minimization can indeed deliver recoverable sparsity thresholds larger than that given in [1], [3]. Our results are based on a high-dimensional geometrical analysis (Grassmann angle analysis) of the null-space characterization for l 1 minimization and weighted l 1 minimization algorithms.

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., Comment: To appear in Globecom 2009

It is now well understood that l 1 minimization algorithm is able to recover sparse signals from incomplete measurements [2], [1], [3] and sharp recoverable sparsity thresholds have also been obtained for the l 1 minimization algorithm. In this paper, we investigate a new iterative reweighted l 1 minimization algorithm and showed that the new algorithm can increase the sparsity recovery threshold of l 1 minimization when decoding signals from relevant distributions. Interestingly, we observed that the recovery threshold performance of the new algorithm depends on the behavior, more specifically the derivatives, of the signal amplitude probability distribution at the origin.

It is well known in compressive sensing that l 1 minimization 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 l 1 minimization. In particular, we determine necessary and sufficient conditions for the measurement matrix A under which l 1 minimization 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 l 1 minimization for recovering purely sparse signals from a null-space perspective.

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 l 1 minimization 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 l 1 minimization 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 l 1 optimization.

It is well known that compressed sensing problems reduce to finding the sparse solutions for large under-determined systems of equations. Although finding the sparse solutions in general may be computationally difficult, starting with the seminal work of [2], it has been shown that linear programming techniques, obtained from an l_(1)-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, l_1 optimization can find the correct solution with overwhelming probability even when the support size of the unknown vector is proportional to its dimension. The paper [1] uses results on neighborly polytopes from [6] to give a ldquosharprdquo bound on what this proportionality should be in the Gaussian measurement ensemble. In this paper we shall focus on finding sharp bounds on the recovery of ldquoapproximately sparserdquo signals (also possibly under noisy measurements). While the restricted isometry property can be used to study the recovery of approximately sparse signals (and also in the presence of noisy measurements), the obtained bounds can be quite loose. On the other hand, the neighborly polytopes technique which yields sharp bounds for ideally sparse signals cannot be generalized to approximately sparse signals. In this paper, starting from a necessary and sufficient condition for achieving a certain signal recovery accuracy, using high-dimensional geometry, we give a unified null-space Grassmannian angle-based analytical framework for compressive sensing. This new framework gives sharp quantitative tradeoffs between the signal sparsity and the recovery accuracy of the l_1 optimization for approximately sparse signals. As it will turn out, the neighborly polytopes result of [1] for ideally sparse signals can be viewed as a special case of ours. Our result concerns fundamental properties of linear subspaces and so may be of independent mathematical interest.

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.

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 Candes and Tao [2005], it has been shown that linear programming techniques, obtained from an l_1-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, Candes and Tao [2005] shows that for measurement matrices chosen from a random Gaussian ensemble, l_1 optimization 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 [Donoho and Tanner, 2005] uses results on neighborly polytopes from [Vershik and Sporyshev, 1992] 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 Candes and Tao [2005] by analyzing matrices whose null-space is isotropic (of which i.i.d. Gaussian ensembles are a special case).

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.

ML and near-ML MIMO detectors have attracted a lot of interest in recent years. However, almost all the reported implementations are delivered in ASICs or FPGAs. Our contribution is optimizing the near-ML MIMO detector for parallel programmable architectures, such as those with ILP and DLP features. In the proposed SSFE (selective spanning with fast enumeration), architecture-friendliness is explicitly introduced from the very beginning of the design flow. Importantly, high level algorithmic transformations make the dataflow pattern and structure fit architecture-characteristics very well. We enable abundant vector-parallelism with highly regular and deterministic dataflow in the SSFE; memory rearrangements, shuffling and non-predictable dynamism are all elaborately excluded. Hence, the SSFE can be easily parallelized and efficiently mapped onto ILP and DLP architectures. Furthermore, to fine-tune the SSFE on parallel architectures, extensive pre-compiler transformations are applied with the help of the application-level information. These optimize not only computation-operations but also address-generations and memory-accesses. Experiments show that the SSFE brings very efficient resource-utilizations on real-life VLIW architectures. Specifically, with the SSFE the percentage of NOPs instructions on VLIW is below 1%, even better than that achieved by the software-pipelined FFT. To the best of our knowledge, this is the first reported work about comprehensive optimizations of near-ML MIMO detectors for parallel programmable architectures.

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 l1 optimization can exactly recover the ideally sparse signal with overwhelming probability by Candes, E. and Tao, T., [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 l_1 minimization. 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.

Compressive sensing is an emerging technology which can recover a sparse signal vector of dimension n via a much smaller number of measurements than n. However, the existing compressive sensing methods may still suffer from relatively high recovery complexity, such as O(n^3), or can only work efficiently when the signal is super sparse, sometimes without deterministic performance guarantees. In this paper, we propose a compressive sensing scheme with deterministic performance guarantees using expander-graphs-based measurement matrices and show that the signal recovery can be achieved with complexity O(n) even if the number of nonzero elements k grows linearly with n. We also investigate compressive sensing for approximately sparse signals using this new method. Moreover, explicit constructions of the considered expander graphs exist. Simulation results are given to show the performance and complexity of the new method.

The problem of exact maximum-likelihood (ML) decoding of general linear codes is well-known to be NP-hard. In this paper, we show that exact ML decoding of a class of asymptotically good low density parity check codes — expander codes — over binary symmetric channels (BSCs) is possible with an average-case polynomial complexity. This offers a new way of looking at the complexity issue of exact ML decoding for communication systems where the randomness in channel plays a fundamental central role. More precisely, for any bit-flipping probability p in a nontrivial range, there exists a rate region of non-zero support and a family of asymptotically good codes which achieve error probability exponentially decaying in coding length n while admitting exact ML decoding in average-case polynomial time. As p approaches zero, this rate region approaches the Shannon channel capacity region. Similar results can be extended to AWGN channels, suggesting it may be feasible to eliminate the error floor phenomenon associated with belief-propagation decoding of LDPC codes in the high SNR regime. The derivations are based on a hierarchy of ML certificate decoding algorithms adaptive to the channel realization. In this process, we propose an efficient O(n^2) new ML certificate algorithm based on the max-flow algorithm. Moreover, exact ML decoding of the considered class of codes constructed from LDPC codes with regular left degree, of which the considered expander codes are a special case, remains NP-hard; thus giving an interesting contrast between the worst-case and average-case complexities.

The problem of finding the closest lattice point arises in several communications scenarios and is known to be NP-hard. We propose a new closest lattice point search algorithm which utilizes a set of new linear inequality constraints to reduce the search of the closest lattice point to the intersection of a polyhedron and a sphere. This set of linear constraints efficiently leverage the geometric structure of the lattice to reduce considerably the number of points that must be visited. Simulation results verify that this algorithm offers substantial computational savings over standard sphere decoding when the dimension of the problem is large.

Compressive sensing is an emerging technology which can recover a sparse signal vector of dimension n via a much smaller number of measurements than n. In this paper, we will give further results on the performance bounds of compressive sensing. We consider the newly proposed expander graph based compressive sensing schemes and show that, similar to the l_1 minimization case, we can exactly recover any k-sparse signal using only O(k log(n)) measurements, where k is the number of nonzero elements. The number of computational iterations is of order O(k log(n)), while each iteration involves very simple computational steps.

This paper concerns the robust receiver design of Multiple-Input Multiple-Output (MIMO) systems in non-Gaussian noise modeled as a symmetric alpha stable process. First, for spatial multiplexing systems, based on the minimum entropy of error (MEE) criterion, we propose a robust receiver (MEE-C), which features excellent robustness and good performance. In order to reduce the computational complexity of MEE-C, which needs to perform an exhaustive search, we design two low-computational receivers on the basis of sphere decoding algorithm (MEE-SD) and sensitive bits algorithm (MEE-SB). Second, for diversity-based systems, we focus on space-time block coding systems (STBC) and transmit antenna selection systems (TAS), and develop robust receivers for both of them, MEE-STBC and MEE-TAS, based on the MEE criterion. Simulations show that the proposed receivers can achieve significant performance gain in the non-Gaussian alpha stable noise.

A novel fast recursive sphere decoder with parallel competing branches (P-SD) is proposed for exact maximum-likelihood (ML) detection in multiple-input multiple-output (MIMO) systems. P-SD introduces a novel competition mechanism which makes P-SD dynamically choose the targeted branch to perform a bounded search among the competing parallel branches. In P-SD, the search radius shrinks to the minimum Euclidean distance as early as possible. Numerical results show that P-SD achieves considerable computational complexity reduction even compared with the Schnorr-Euchner enumeration (SEE) based sphere decoder (SE-SD).

Space-time block codes (STBC) are very effective and simple schemes to utilize the diversity gain in multiple-input multiple-output (MIMO) wireless systems. In previous research on STBC data detection, channel state information is usually assumed to be known at the receiver side, which enables simple maximum-likelihood (ML) decoding at the receiver. We consider the problem of joint ML channel estimation and data detection for STBC systems when the channel state information is not available at the receiver. It is shown that the joint ML channel estimation and data detection for complex STBC system is an integer least-square optimization problem for constant-modulus modulation. We propose novel sphere decoders which provide a low-complexity exact optimal solution to this optimization problem. The proposed sphere decoder visits the minimum number of tree nodes in finding the ML solution. In addition, by modifying the novel sphere decoder, we provide efficient exact ML joint channel estimation and data detection for STBC wireless systems employing non-constant modulus modulation schemes. Considerable performance gain and complexity reduction are achieved with these methods.

In this paper, we investigate the optimum detection of MIMO signals in the presence of channel estimation errors. An efficient tree search based detector is proposed for optimal MIMO signal detection, based on the modified ML criterion, which takes channel estimation errors into account. It is shown that this tree search ML detector is almost as computationally efficient as the corresponding sphere decoder, ignoring channel estimation errors. When applied to the MIMO system, concatenated with an outer channel code, the proposed ML detector, taking into account channel estimation errors, achieves significant gain over sphere detectors ignoring channel estimation errors.

Sphere decoders have gained attention for low-complexity optimum signal detection in multiple-input multiple output (MIMO) wireless systems. In this paper, a new faster sphere decoder by employing two-layer enumeration (TLE-SD) is proposed for exact ML detection in MIMO systems. In TLE-SD, search radius shrinks to the Euclidean distance between received vector and closest lattice point very fast by utilizing the larger diversity order provided by the proposed two-layer enumeration. Theoretical analysis and simulation results show that TLE-SD leads to considerable computation complexity reduction compared with other sphere decoders.

In this paper, the receiver design of MIMO systems is performed in a mixture of Gaussian noise and impulsive noise modeled as a symmetric alpha stable process. Both spatial multiplexing systems (SM-systems) and diversity based systems are considered. The optimal receiver and several suboptimal receivers are developed and the related problems, such as performance and robustness, are discussed. Simulation shows that the proposed receivers can achieve much better performance than the traditional MIMO receivers in the mixed noise.

Low-complexity tree search based exact maximum-likelihood (ML) detectors have gained attention for optimum signal detection in multiple-input multiple output (MIMO) wireless systems. In this paper, taking a fresher look at the closet lattice point search problem, we propose a new fast exact ML sphere decoder with ever-increasing radius (IR-SD). It is shown that IR-SD visits minimum number of tree nodes and is more computationally efficient than existing sphere decoders. IR-SD is also faster and requires less storage than ML stack detector. An upper-bound of expected computation and storage complexity of IR-SD independent of tree radius is derived. Numerical results validate that IR-SD greatly speeds up the ML detection than other sphere detectors while requiring less storage than ML stack algorithm. A factor-of-2.5 speed-up is observed over the depth-first Schnorr-Euchner sphere decoders when utilizing IR-SD in 16-QAM 10/spl times/10 complex MIMO system.