This paper investigates the sparse channel estimation issue of multiple-input multiple-output orthogonal frequency division multiplexing (MIMO-OFDM) systems. Beginning with the formulation of least squares (LS) solution to sparse MIMO-OFDM channel estimation, a compressed channel sensing (CCS) framework based on the new smoothed l0-norm-regularized least squares (l2-Sl0) algorithm is proposed. Three methods, namely quasi-Newton, conjugate gradient, and optimization in the null and complement spaces of the measurement matrix, are then proposed to solve the l2-Sl0 unconstrained optimization problem. Moreover, the two former are also applied to solve the l2-Sl0 channel estimation. A number of computer simulation-based experiments are conducted showing a better reconstruction accuracy of the l2-Sl0 algorithm as compared with the smoothed l0-norm (Sl0) algorithm in the presence of noise. The proposed CCS approach can save nearly 25% pilot signals to maintain the same mean square error (MSE) and bit error rate (BER) performances as given by the conventional LS method.
The online version of this article (doi:10.1186/1687-1499-2013-282) contains supplementary material, which is available to authorized users.
Competing interests
The authors declare that they have no competing interests.
1. Introduction
Coherent detection and equalization in multiple input multiple output orthogonal frequency division multiplexing (MIMO-OFDM [1]) systems require channel state information (CSI) at the receiver. In real wireless environments, however, the CSI is not known. Therefore, channel estimation is of crucial importance to MIMO-OFDM systems. In various wireless propagation environments, the channel may consist of only a few dominant propagation (non-zero) paths, even though it has a large propagation delay. Thus, the channel impulse response has a sparse nature [2‐4]. However, conventional methods, such as least squares (LS), ignore this prior information about the unknown channel leading to lower spectral efficiency. Recently, sparse channel estimation with an objective of decreasing the training sequence to improve spectral efficiency is becoming a hot research topic.
Previously reported approaches for sparse channel estimation can broadly be categorized into two types, namely the most significant tap (MST) detection and compressed channel sensing (CCS). The MST detection methods [4‐6] used a measure to determine if a channel tap was non-zero (‘active’). The disadvantage of this type of methods is that a large number of pilots are needed to render an accurate MST detection and effective channel estimation. The CCS methods are based on the compressed sensing (CS [7]) technology. In [8], the authors formalized the notion of multipath sparsity and proposed the CCS approach. In [9], the orthogonal matching pursuit (OMP) and basis pursuit (BP) algorithms were applied to estimate underwater acoustic channels with large Doppler spread. In [10], the authors proposed an overcomplete basis for doubly selective channels and a metric called localized coherence for selecting training signals to ensure good estimation performance. In [11], a CCS approach for doubly selective channels and a sparsity-enhancing basis expansion with a method for optimizing it were proposed. In [12], two criteria as guiding principles to optimize the pilot pattern for CCS in OFDM systems were proposed. Methods of this type utilize the prior sparse information of the unknown channel and the advantage of CS and thus can improve the spectral efficiency by reducing the number of pilot symbols to be transmitted.
Anzeige
Different from literatures [9‐12] that used the existing sparse reconstruction algorithms for CCS in OFDM or single carrier systems, we aim to exploit a novel reconstruction algorithm for CCS in MIMO-OFDM systems. The proposed smoothed l0-norm-regularized least squares reconstruction algorithm is named l2-Sl0 in this paper, which differs from the smoothed l0-norm reconstruction algorithm (Sl0[13]) in two aspects. First, Sl0 is a constrained optimization problem which is solved in [13] using the steepest descent approach. However, l2-Sl0 is an unconstrained minimization problem which is to be solved in this paper by using three methods, namely quasi-Newton approach, conjugate gradient approach, and optimization in the null and complement spaces of the measurement matrix. Second, unlike the Sl0 using a fixed step size to control the decrease of the parameter σ, which determines the degree of smoothness and the approximation accuracy of l0-norm, l2-Sl0 uses a variable one. Simulation results show that the proposed l2-Sl0 reconstruction approach outperforms the Sl0 approach in the presence of noise, and at the cost of slightly more computational time, the CCS approach using l2-Sl0 in conjunction with conjugate gradient yields a performance slightly better than that of the CCS method using fast iterative shrinkage-thresholding algorithm (FISTA [14]) or orthogonal matching pursuit (OMP [15]) algorithm.
The remainder of the paper is organized as follows: Section 2 formulates the sparse channel estimation problem of MIMO-OFDM systems based on LS, ideal-LS, and compressed sensing. Section 3 presents three sparse reconstruction algorithms using the proposed l2-Sl0 objective function, based on which a new CS-based sparse channel estimation approach is developed. Section 4 comprises a number of experiments showing a better reconstruction accuracy of the l2-Sl0-based method as compared with the Sl0 algorithm, and a higher spectrum efficiency of the sparse channel estimation employing l2-Sl0 than that using the LS method. Section 5 concludes this paper by highlighting some of the contributions presented.
2. The sparse channel estimation problem of MIMO-OFDM systems
Consider a similar MIMO-OFDM system as described in [16] with NT transmit and NR receive antennas. The MIMO channel can be characterized by an array of L-tap finite impulse response (FIR) filters given by a number of NR × NT matrices H(n), (n = 0,1,…,L − 1), whose (iR,iT)-th element represents the l- th tap of the channel response between the iR-th receive antenna and the iT-th transmit antenna. In the case of uniform sampling, a wireless channel can often be modeled as a sparse channel [17‐19], i.e., only a few elements are nonzero in . If the length of the cyclic prefix (CP) is not less than the channel length L, the received pilot signal in iR-th receiver antenna can be written as
(1)
where and are the pilot signals in the iT-th transmit antenna and iR-th receive antenna, diag(X1,pilot) is a diagonal matrix with Xl,pilot as the main diagonal elements, with , and niR,pilot represents the frequency domain noise. Let FL be a K × L matrix formed by the first L columns of a K × K DFT matrix F, then Fpilot can be formed by taking only the rows of FL associated with the KP pilot sub-carriers.
Anzeige
By letting , , , and , where ⊗ represents Kronecker product, we can get
(2)
which can be solved by the conventional LS method, giving , where † represents the pseudoinverse.
Assuming the positions ld (d = 0,1,…,D-1, and l0 < l1 < … < lD-1) of the MST are correctly estimated, Equation 1 can be rewritten as
(3)
where with , D is the number of nonzero taps, and Wpilot can be formed by taking only the D columns of Fpilot associated with the nonzero tap positions ld. Let and . We can obtain
(4)
When npilot is white noise and the positions ld of MST are correctly estimated, we can obtain the estimate of the MST as . We can also obtain the Cramer-Rao bound of the sparse channel estimate through setting the elements of the positions ld equal to and other elements equal to zero [4]. The above method to obtain the Cramer-Rao bound of is named as ideal-LS for comparison in this paper.
Note that the dimension of Ypilot is proportional to the number of pilot subcarriers, and Equation 2 is an underdetermined problem when the dimension of Ypilot is smaller than that of h. Therefore, the sparse channel estimation in MIMO-OFDM systems can be viewed as solving an underdetermined linear inverse problem with sparsity constraint, i.e.,
(5)
where || · ||0 represents the number of nonzero components named as l0-norm.
3. Sparse channel estimation using l2-Sl0reconstruction algorithm
The sparse signal reconstruction problem in CS is to estimate a sparse vector x ∈ ℂN from an observed vector y ∈ ℂM based on the linear model
(6)
where w ∈ ℂM is unknown noise and Φ ∈ ℂM × N is a known measurement matrix, typically with M ≪ N. This means that the signal x is ‘sensed’ by a reduced or ‘compressed’ number of measurements. Therefore, the signal reconstruction problem can be described as the following constrained minimization problem,
(7)
where the bound ϵ ≥ 0 is used to allow certain error tolerance. In general, ϵ is related to the variance of noise w. Unfortunately, the problem in Equation 7 is a NP-hard combinatorial problem, whose computational complexity grows exponentially with the increase of the signal size and becomes prohibitive even for signals of moderate sizes. Consequently, several techniques have been proposed to tackle this difficult problem. One of the approaches is the convex relaxation, such as BP [20], which replaces ||x||0 with ||x||1 to make the problem easier to solve. Another approach, such as matching pursuit (MP [21]) or OMP, is much faster than BP but is a greedy algorithm and does not have provable reconstruction quality at the level of BP method [22]. Different from the above techniques, the smoothed l0-norm approach [13] is to approximate the discontinuous l0-norm by a suitable continuous one and then minimize it by an optimization algorithm dedicated to continuous functions. For example, the following continuous function
(8)
where σ is a small value, has been proposed to approximate ||x||0 in [13]. In other words, the minimum l0-norm solution is then found by minimizing Fσ(x) for a very small value of σ. The parameter σ determines how smooth the function Fσ(x) would be and the accuracy of the approximation. Generally speaking, for larger values of σ, Fσ(x) is smoother and contains less local minima, but the approximation to l0-norm is worse. On the other hand, for smaller values of σ, a highly nonsmooth Fσ(x) results, which gives a better approximation to l0-norm but a difficult minimization problem. Consequently, the Sl0 approach used a ‘decreasing’ sequence for σ.
The Sl0 reconstruction algorithm is typically 2 to 3 orders of magnitude faster than BP, while resulting in the same or better accuracy [13]. However, in the presence of noise, the accuracy of Sl0 algorithm needs to be improved. Therefore, in the next section, we will propose several improved Sl0 reconstruction algorithms.
3.1 The l2-Sl0-BFGS reconstruction algorithm for channel estimation
Like l1-regularized l2 approach (l2-l1[14, 23, 24]) and lp-regularized l2 algorithm [25], we use a parameter λ > 0 to balance the twin objectives of minimizing both error and sparsity, giving the following unconstrained optimization problem:
(9)
The objective function in Equation 9 remains differentiable, and its gradient can be obtained as
(10)
where g = [g1, g2, …, gN]T with gi being given by
(11)
For a fixed value of σ, the problem in Equation 9 is now solved using a quasi-Newton algorithm where an approximation of the inverse of the Hessian is obtained using the Broyden-Fletcher-Goldfarb-Shanno (BFGS) update formula [26‐28]. As such, the algorithm is referred to as the l2-Sl0-BFGS algorithm.
The quadratic (l2-norm) error term in Equation 9 is a convex function, but the convex region of the approximate l0-norm term depends on parameter is σ. In general, the greater the value of σ, the larger the convex region is. To see this, we compute the gradient of Fσ(x), denoted as , whose element is given by
(12)
Also, the Hessian of Fσ(x) is a diagonal matrix as given by
(13)
Therefore, Fσ(x) is convex if and only if
(14)
Since Equation 14 defines an N-dimensional hypercube whose volume is (2σ)N, the size of the convex region in the x-space is proportional to σ. On the other hand, in order to better approximate the l0-norm, σ must be sufficiently small. Consequently, to avoid getting trapped into local minima, we gradually decrease the value of σ, as in the Sl0 approach. More specifically, for minimum F(x) at σi, the initial point is x*(σi-1) obtained in the previous iteration, which is near the global optimal solution.
Since a broadband wireless channel response h usually consists of a few dominant propagation paths and Equation 2 has a similar form as Equation 6, the estimation of h can be viewed as a sparse signal reconstruction in compressed sensing. Thus, we refer to this kind of sparse channel estimation method as CCS. Using Equations 2, 6, and 9, we can obtain the objective function of CCS based on the l2-Sl0 reconstruction algorithm,
(15)
From the above analysis, the proposed CCS using the l2-Sl0-BFGS algorithm can be implemented by the pseudo-code in Algorithm 1.
Algorithm 1 CCS using the l2-Sl0-BFGS algorithm
Note that in Algorithm 1, the values of δr and rJ are chosen such that 0 < δr < 0.1 and 0.5 < rJ < 1. The method of l2-Sl0 uses a variable factor ri = ri − 1 + δr to control the decrease of the parameter σ. Our idea is to use an ‘increasing’ step size corresponding to the decreasing values of σ.
3.2 The l2-Sl0-CG reconstruction algorithm for channel estimation
The Hessian matrix of the objective function F(x) in Equation 9 can be computed as
(16)
where ∇2Fσ(x) is computed using Equation 13. Since the gradient and Hessian matrix of F(x) can be efficiently evaluated using the closed-form formula in Equations 10 and 16, it is convenient to apply the conjugate gradient method to solve the l2-Sl0 optimization problem. The algorithm is thus referred to as the l2-Sl0-CG algorithm.
In the k-th iteration of the conjugate gradient technique, xk is updated as
(17)
The conjugate direction dk is computed as
(18)
and the k-th step size αk is computed using
(19)
Where gk is the gradient vector computed using Equation 10 and Hk is the Hessian matrix obtained using Equation 16 at x = xk, respectively. The proposed CCS using l2-Sl0- CG algorithm can be implemented by the pseudo-code in Algorithm 2.
Algorithm 2 CCS using l2-Sl0- CG algorithm
3.3 Signal reconstruction via optimization in null and complement spaces of Φ
Let Φ = UΣVT be the singular value decomposition (SVD) of Φ where UM×M and VN×N are unitary matrices, and Σ = [S, 0]M × N with S = diag(s1, …, sM) being a diagonal matrix composed by the singular values of Φ. Let V=[Vr,Vn], where the columns of Vn span the null space of Φ and the columns of Vr span the orthogonal complement of the null space. Using Vn and Vr, a signal x of length N can be expressed as
(20)
Where α and β are vectors of length M and N − M, respectively. Applying the SVD of Φ, the l2-norm term in Equation 9 can be simplified as [25]
(21)
Where Si is the i-th singular value of Φ, αi and are the i-th component of α and , respectively. Using Equations 20 and 21, the optimization problem in Equation 9 can be recast as
(22)
Where Vr,j and Vn,j are the j-th row of Vr and that of Vn, respectively.
An iterative algorithm to solve the optimization problem in Equation 22 is proposed as follows. In the k-th iteration of the optimization process, signal x(k) is updated as
(23)
where
(24)
and the step size μ(k) > 0 is determined by the inexact line search method of Roger Fletcher [26]. Assuming that the updating vectors and are written as
(25)
which are determined by minimizing F(α,β) along each of the directions defined by the column vectors of [Vr,Vn]. Therefore, and become descent directions of F(α,β), and in the case of real Φ and x, can be calculated via iteration as
(26)
Where xj is the j-th component of vector x(k), is the (j,i)-th component of matrix Vr, αi is the i-th component of vector α(k), and is the p-th iteration value of with the initialization value . Similarly, in Equation 25 is given by
(27)
where is the (j,i)-th component of matrix Vn, and is the q-th iteration value of with the initialization value . The derivation of Equations 26 and 27 is given in the Appendix. In addition, the computation of using Equation 26 requires vector α(k) to be computed first as
(28)
The reconstruction algorithm via optimization in null and complement spaces of measurement matrix Φ is referred to hereafter as the l2-Sl0- NC algorithm, which can be implemented by the pseudo-code in Algorithm 3.
Algorithm 3 The l2-Sl0- NC reconstruction algorithm
4. Simulation results
In this section, the reconstruction performance of the proposed approach (l2-Sl0) is evaluated by computer simulations. The spectral efficiency of the CCS using l2-Sl0 algorithm is also discussed. More specifically, the l2-Sl0 algorithm includes l2-Sl0-BFGS, l2-Sl0- CG, and l2-Sl0- NC in the scenario where y, Φ ,x are real-valued. While in complex-valued scenarios, l2-Sl0 only means l2-Sl0- BFGS and l2-Sl0- CG. Note that Equations 26 and 27 are obtained only in the case where y, Φ, x are real-valued. Namely, the l2-Sl0- NC is not suitable to reconstruct complex signals. In all the experiments, the initial value of r is set to 0.5 for both Sl0 and l2-Sl0 algorithms. The values of δr and rJ required by the l2-Sl0 algorithm are chosen as 0.05 and 0.7, respectively.
In experiments 1 and 2, the signal length and the number of measurements are set to N = 1,000 and M = 400, respectively. A K-sparse source x was artificially created as follows: (1) set x to a zero vector of length N, (2) generate a vector z of length K assuming that each element zi is a random value drawn from the normal distribution N(0,1) in the real-valued scenario or from N(0,1/2)+jN(0,1/2) in the complex-valued scenario, and (3) randomly select K components of x and set them to z. Each element of the measurement matrix Φ is randomly generated using the normal distribution N(0,1) or N(0,1)+jN(0,1), and each row is normalized to unity. Then, the mixtures are generated using the noisy model y=Φx+w, where w is an additive white Gaussian noise with covariance matrix σwΙM (IM stands for the M × M identity matrix). To evaluate the estimation accuracy, the signal-to-noise ratio (SNR) defined as is used, where x and denote the true value and its estimate, respectively.
In experiment 1, we compare the reconstruction performance of l2-Sl0 with that of Sl0. Figures 1 and 2 show the reconstruction SNR at different powers of noise σw in real and complex signal scenarios, respectively. For each value of σw, the reconstruction SNR is averaged over 100 runs. It is seen that l2-Sl0 produces a better SNR than Sl0, which shows the robustness of l2-Sl0 against noise. The objective function of l2-Sl0 algorithm in Equation 15 comprises the quadratic error term which permits a small perturbation. Therefore, the l2-Sl0 algorithm has a larger capability to reconstruct sparse signal in the presence of noise than Sl0. For smaller values of σ, Fσ(x) contains more local minima. Therefore, the decrease of σ should not be too quick in the Sl0 and l2-Sl0 algorithms. Moreover, unlike Sl0 using a fixed step size to control the decrease of the parameter σ, l2-Sl0 uses a variable one, and the step size δr slightly increasing with the reduction of σ may also help the l2-Sl0 to improve its estimation accuracy.
×
×
In experiment 2, the l2-Sl0 algorithms are tested using N = 1,000, M = 400, and various K sparse signals with σω = 0.01, to examine the algorithms' performance for signals of different sparsity levels. The results obtained are plotted in Figures 3 and 4 with y, Φ, x being real and complex values, respectively. It is observed that the performance of the l2-Sl0 algorithm is better than the Sl0 algorithm in most cases. In real-valued scenario, the l2-Sl0- BFGS, l2-Sl0- CG, and l2-Sl0- NC are comparable for K smaller than 130, but l2-Sl0- BFGS performs better for K between 130 and 210. In addition, when K is smaller than 90, the final SNR of the Sl0 algorithm increases with the rise of sparsity K. This is because the initial estimate is set to the minimum l2-norm solution of y = Φx + w, which has few zero elements and is far away from the actual signal with many zero elements, and is gradually close to the actual signal with the rise of sparsity K. However, this phenomena is not obvious in l2-Sl0 algorithm, since the initial estimate is set to zeros in l2-Sl0-CG and l2-Sl0-NC, which is near the actual solution for a small value of K. Because of being set to zeros and the thresholds of δ1 and δ2 being not small enough for the value sparsity K above 230, the l2-Sl0-NC performs the worst among the algorithms tested.
×
×
Next, we investigate the accuracy and the spectral efficiency of CCS method using l2-Sl0. We consider a MIMO-OFDM system with two transmit and two receive antennas (NT = NR = 2). The number of subcarriers is 512, and the QPSK modulation is used. The length of cyclic prefix is 20, which equals the length of wireless channel impulse response. In experiment 3, a Rayleigh channel modeled by a 4-tap MIMO-FIR filter is assumed, in which each tap corresponds to a 2 × 2 random matrix whose elements are i.i.d. complex Gaussian variables with zero mean and unit variance, and the position ld of MSTs is {2, 6, 13, 19}. The estimation performance is evaluated in terms of the bit error rate (BER) and mean square error (MSE) given by MSE(Δh) =, where M represents the number of simulations and hi and represent the actual and the estimated channels from the i-th simulation, respectively.
In experiment 3, we investigate the performance and required computational time of the CCS using l2-Sl0-BFGS, l2-Sl0-CG, and Sl0 reconstruction algorithms with 30 pilot signals in each transmit antenna. The simulation consists of 2,000 Monte Carlo runs. Moreover, their performance is compared with those of the CCS using OMP and FISTA. OMP is the most popular one in the type of greedy reconstruction algorithm, and FISTA is the most fast one in the type of l2-l1 reconstruction algorithm. Figures 5 and 6 show the MSE and BER plots resulting from the above five CCS methods and the conventional LS method, respectively. As can be seen, the CCS method using l2-Sl0-CG only needs 30 pilot signals to obtain the approximate performance of the LS method using 40 pilot signals which implies that the CCS using l2-Sl0-CG can save nearly 25% pilot signals. This merit of CCS is due to the prior sparse information of the wireless channel utilized and the efficient reconstruction of sparse signals from a very limited number of measurements allowed by CS. In addition, the CCS applying l2-Sl0-CG or l2-Sl0-BFGS outperforms the CCS using Sl0 more obviously than that in experiment 1, which shows that the l2-Sl0 has a larger capability to reconstruct sparse signal than Sl0 in the case when each row of measurement matrix is not normalized to unity. Since the l2-Sl0 algorithm is halted after a fixed number of iterations, furthermore, the fixed number does not depend on the sparsity of the signal directly; it is convenient to set the number in practical applications.
×
×
We use the CPU time as a measure of complexity. The simulations are performed in MATLAB R2009b environment using an Intel Core i3, 2.53-GHz processor with 2 GB of memory, and under Microsoft Windows XP operating system. The results shown in Figure 7 indicate that the CCS using l2-Sl0 requires more computational time than that using other algorithms tested. The l2-Sl0 algorithm needs an iterative process to find the optimal solution at each value of σ; therefore, the running time of l2-Sl0 is longer than that of others tested. However, at the cost of slightly more computational time, the CCS using l2-Sl0-CG yields slightly better performance than the CCS using OMP or FISTA, and the threshold value for termination iteration in the l2-Sl0 algorithm is easier to be set. More specifically, it is shown in Algorithm 2 that l2-Sl0-CG applies a constant value L to stop the iteration, and the constant value is independent of the sparsity of signal and the power of noise. However, the valid threshold values for termination iteration in the OMP and FISTA algorithms always depend on the power of noise or the sparsity of signal, which are both quite difficult to estimate beforehand in practical applications.
×
In experiment 4, we investigate the BER of the CCS using 30 pilot signals in each transmit antenna under different channel sparsities, namely for different numbers of MSTs. Moreover, the position ld of MST is randomly selected in each Monte Carlo simulation. Figure 8 shows the BER plots of CCS using l2-Sl0-CG and l2-Sl0-BFGS algorithms. The figure shows that a better BER performance can be expected in general for less number of MSTs. In addition, when the length of channel response is 20, the CCS using l2-Sl0-CG and that using l2-Sl0-BFGS are found to yield acceptable BERs for up to 8 and 4 MSTs, respectively.
×
5. Conclusion
In this paper, a new approach for sparse channel estimation of MIMO-OFDM systems based on compressed sensing has been presented. The new approach uses a smoothed l0-norm-regularized least squares (l2-Sl0) objective function and solves the optimization problem by three reconstruction algorithms: quasi-Newton, conjugate gradient (CG), and optimization in the null and complement spaces of measurement matrix (ONCS). The better reconstruction accuracy of the l2-Sl0 as compared with the Sl0 algorithm and the higher spectrum efficiency of the CCS using l2-Sl0-CG or l2-Sl0-BFGS as compared with the conventional LS method have been shown by computer simulations.
Suppose that ei is the i-th column of an M × M identity matrix, and the vectors α and β in Equation 22 are fixed. At point α, a line search along direction ei is carried out by solving the one-dimensional optimization problem
(29)
Where xj is the j-th component of vector x, and is the (j,i)-th component of matrix Vr. By equating the derivative ∂F(α + dr,iei, β)/∂dr,i to zero, for real Φ and x, we can obtain
(30)
Note that dr,i can be solved via iterations with the initial value of dr,i being set to zero in the right side of (30). In a similar manner, dn,i can be obtained as
(31)
where is the (j,i)-th component of matrix Vn.
Acknowledgements
We express our thanks to the anonymous reviewers for their valuable comments to improve the quality and the presentation of this paper. This work is supported by the National Natural Science Foundation of China under grant nos. 61372122 and 61302104 and the Basic Research Program of Jiangsu Province under grant no. BK2011756.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Competing interests
The authors declare that they have no competing interests.